Invertibility of Sparse Complex Gaussian Matrices

Abstract

Let ${\sigma }_n(\cdot )$ denote the least singular value of a $n\times n$ matrix. It is well-known that $\mathbb{P}[{\sigma }_n(A)\le \epsilon ]\le \epsilon n$ if $A$ is drawn from the real Ginibre ensemble of $n\times n$ matrices and $\mathbb{P}[{\sigma }_n(A)\le \epsilon ]\le {\epsilon }^2{n}^2$ if $A$ is drawn from the complex Ginibre ensemble. In this paper, we will show a similar phenomenon occurs for sparse random matrices.

23 pages. This paper was part of my senior thesis at UC Berkeley