Lower bounds for the smallest singular value of structured random matrices

Understand

We obtain lower tail estimates for the smallest singular value of random matrices with independent but non-identically distributed entries.

• Specifically, we consider $n\times n$ matrices with complex entries of the form \[ M = A\circ X + B = (a_{ij}\xi_{ij} + b_{ij}) \] where $X=(\xi_{ij})$ has iid centered entries of unit variance and $A$ and $B$ are fixed matrices.
• In our main result we obtain polynomial bounds on the smallest singular value of $M$ for the case that $A$ has bounded (possibly zero) entries, and $B= Z\sqrt{n}$ where $Z$ is a diagonal matrix with entries bounded away from zero.
• As a byproduct of our methods we can also handle general perturbations $B$ under additional hypotheses on $A$, which translate to connectivity hypotheses on an associated graph.