Lower bounds for the smallest singular value of structured random\n matrices

Abstract

We obtain lower tail estimates for the smallest singular value of random\nmatrices with independent but non-identically distributed entries.\nSpecifically, we consider $n\\times n$ matrices with complex entries of the form\n\\[ M = A\\circ X + B = (a_{ij}\\xi_{ij} + b_{ij}) \\] where $X=(\\xi_{ij})$ has iid\ncentered entries of unit variance and $A$ and $B$ are fixed matrices. In our\nmain result we obtain polynomial bounds on the smallest singular value of $M$\nfor the case that $A$ has bounded (possibly zero) entries, and $B= Z\\sqrt{n}$\nwhere $Z$ is a diagonal matrix with entries bounded away from zero. As a\nbyproduct of our methods we can also handle general perturbations $B$ under\nadditional hypotheses on $A$, which translate to connectivity hypotheses on an\nassociated graph. In particular, we extend a result of Rudelson and Zeitouni\nfor Gaussian matrices to allow for general entry distributions satisfying some\nmoment hypotheses. Our proofs make use of tools which (to our knowledge) were\npreviously unexploited in random matrix theory, in particular Szemer\\'edi's\nRegularity Lemma, and a version of the Restricted Invertibility Theorem due to\nSpielman and Srivastava.\n