Extreme least singular values of Gaussian row submatrices and a phase retrieval stability problem

Abstract

Let $\mathbb{F}\in \{\mathbb{R},\mathbb{C}\}$ and $d_{\mathbb{F}}={\dim }_{\mathbb{R}}\mathbb{F}$. If $A_m\in {\mathbb{F}}^{N_m\times m}$ has independent standard Gaussian entries and $N_m/m\to \gamma >1$, then \[ \min_{\substack{T\subset[N_m]\\ |T|=m}} σ_{\min}(A_{m,T}) = \left(\frac{γ^γ}{(γ-1)^{γ-1}}\right)^{-m/d_{\mathbb F}+o_P(m)} . \] If $N_m=\gamma m+O(1)$, the convergence of $m^{-1}\log M_m^{\mathbb{F}}$ has probability error $O(m^{-1})$. In particular, at the real phase-retrieval threshold $N=2m-1$, \[ ω(A_m)=4^{-m+o_P(m)}, \] so the Gaussian Balan--Wang critical exponential base is $1/4$.