1 Introduction
The least singular value of a random matrix is a basic hard-edge observable in random matrix theory. This paper studies a related extremal quantity: the minimum of the least singular value over all square row submatrices of a tall Gaussian matrix. The number of such submatrices is exponential in the dimension and the main point is to show that their strong dependence does not change the exponential scale predicted by the one-matrix hard-edge small-ball exponent.
Let
$\mathbb {F}\in \{\mathbb {R},\mathbb {C}\}$
and let
$d_{\mathbb {F}}=\dim _{\mathbb {R}}\mathbb {F}$
, so that
$d_{\mathbb {R}}=1$
and
$d_{\mathbb {C}}=2$
. A standard Gaussian variable over
$\mathbb {R}$
is
$N(0,1)$
; a standard Gaussian variable over
$\mathbb {C}$
is
$(\xi +i\eta )/\sqrt 2$
, where
$\xi ,\eta $
are independent
$N(0,1)$
variables. For
$A\in \mathbb {F}^{N\times m}$
and
$T\subset [N]$
,
$A_T$
denotes the submatrix formed from the rows indexed by T. Define
Our main result identifies the limiting exponential base for (1.1) for every fixed row aspect ratio
$\gamma>1$
.
Theorem 1.1 (Extremal square submatrices).
Let
$\mathbb {F}\in \{\mathbb {R},\mathbb {C}\}$
and
$d_{\mathbb {F}}=\dim _{\mathbb {R}}\mathbb {F}$
. Let
$A_m\in \mathbb {F}^{N_m\times m}$
have independent standard Gaussian entries and assume
$N_m/m\to \gamma>1$
. Put
Then,
Equivalently,
If in addition
$N_m=\gamma m+O(1)$
, for instance,
$N_m=\lfloor \gamma m\rfloor $
, then for every fixed
$\varepsilon>0$
,
The constant
$c_\gamma $
is the exponential growth rate of the relevant binomial coefficient:
$\binom {N_m}{m}=\exp \{h(\gamma )m+o(m)\}$
. For one
$m\times m$
Gaussian matrix over
$\mathbb {F}$
, the probability that
$\sigma _{\mathrm {min}}$
is at most t is of order
$t^{d_{\mathbb {F}}}$
at the origin, up to powers of m. If the square submatrices behaved independently, the minimum over
$\exp \{h(\gamma )m+o(m)\}$
of them would therefore be expected at scale
$\exp \{-h(\gamma )m/d_{\mathbb {F}}+o(m)\}$
. Theorem 1.1 proves that this heuristic gives the correct exponential scale.
A closely related question was studied by Rademacher and Shu [Reference Rademacher and Shu11] in the smoothed analysis of Frank–Wolfe methods. In our row notation, their results show that, when the number of Gaussian rows is a fixed factor larger than the dimension, some square submatrix has exponentially small least singular value, and all square submatrices have least singular value bounded below at a possibly different exponential scale. The present paper refines that picture by identifying the exact exponential rate, by treating both real and complex Gaussian matrices, and by extracting the sharp Gaussian base in the Balan–Wang phase retrieval stability question.
The motivating application is the stability of real finite-dimensional phase retrieval; this is the setting of Randomstrasse Open Problem 21. If
$A\in \mathbb {R}^{N\times m}$
has rows
$a_1,\ldots ,a_N$
, the real phaseless measurement map is
$x\bmod \{\pm 1\}\mapsto |Ax|=(|\langle a_i,x\rangle |)_{i=1}^N$
. The finite-dimensional frame formulation goes back to Balan, Casazza and Edidin [Reference Balan, Casazza and Edidin2]; see also [Reference Bandeira, Cahill, Mixon and Nelson5, Reference Conca, Edidin, Hering and Vinzant7, Reference Grohs, Koppensteiner and Rathmair10] for injectivity and stability background. In the real case, injectivity is characterised by the complement property: for every partition of the rows, one side must span
$\mathbb {R}^m$
. Thus, the sharp generic threshold is
$N=2m-1$
.
Balan and Wang introduced quantitative stability parameters measuring the conditioning of spanning subfamilies and related these parameters to Lipschitz bounds for phaseless inversion [Reference Balan and Wang3] (see also [Reference Balan1, Reference Balan and Zou4, Reference Eldar and Mendelson9]). At the real critical threshold, for a full-spark
$A\in \mathbb {R}^{(2m-1)\times m}$
, define
Balan and Wang conjectured an exponential upper bound
with universal constants
$C>0$
and
$0<b<1$
. Randomstrasse Open Problem 21 asks for the value of
$\omega (A)$
for independent and identically distributed Gaussian A and for the corresponding value of the exponential base in (1.5) [Reference Bandeira, Dmitriev, Lucca, Nizić-Nikolac and Rödder6]. Thus, the following real critical case is not just an example of Theorem 1.1; it is the stated Gaussian Balan–Wang open problem.
For full-spark
$A\in \mathbb {R}^{(2m-1)\times m}$
, (1.4) reduces to the minimum over square row submatrices:
Indeed, the rank-deficient sets J are exactly those with
$|J|\le m-1$
and adding rows can only increase the Gram matrix. Applying Theorem 1.1 with
$\mathbb {F}=\mathbb {R}$
and
$N_m=2m-1$
gives the following answer.
Corollary 1.2 (Gaussian Balan–Wang base).
Let
$A_m\in \mathbb {R}^{(2m-1)\times m}$
have independent standard Gaussian entries. Then,
with the rate
for every fixed
$\varepsilon>0$
. Equivalently,
$\omega (A_m)=4^{-m+o_P(m)}$
.
Let
$R_m=\max _{1\le i\le 2m-1}\|a_i\|$
. For every
$b>1/4$
,
$\mathbb {P}\{\omega (A_m)\le R_m b^m\}\to 1$
. For every
$b<1/4$
and every fixed
$C<\infty $
,
$\mathbb {P}\{\omega (A_m)\le C R_m b^m\}\to 0$
. Thus, the Gaussian critical base in the Balan–Wang question is
$1/4$
.
The complex part of Theorem 1.1 is not a statement about the complex phase retrieval threshold. It is the corresponding square-submatrix random matrix theorem over
$\mathbb {C}$
. For example, when
$N_m/m\to 2$
, one obtains
$M_m^{\mathbb {C}}(A_m)=2^{-m+o_P(m)}$
, reflecting the two-real-dimensional small-ball exponent of a complex Gaussian scalar.
2 One-matrix lower tails and binomial growth
We first record the elementary one-matrix estimate needed for the lower bound. It is deliberately weaker than the sharp hard-edge asymptotics of Edelman [Reference Edelman8] and subsequent work such as [Reference Rudelson and Vershynin12, Reference Tao and Vu13]; the polynomial loss is harmless at the exponential scale considered here.
Lemma 2.1 (Polynomial least-singular-value tail).
Let
$G\in \mathbb {F}^{m\times m}$
have independent standard Gaussian entries, where
$\mathbb {F}\in \{\mathbb {R},\mathbb {C}\}$
and
$d_{\mathbb {F}}=\dim _{\mathbb {R}}\mathbb {F}$
. There is a constant
$C_{\mathbb {F}}$
such that, for all
$m\ge 1$
and all
$t>0$
,
Proof. Let
$R_1,\ldots ,R_m$
be the rows of G, let
$H_i=\operatorname {span}_{\mathbb {F}}\{R_j:j\ne i\}$
and set
$d_i=\operatorname {\mathrm {dist}}(R_i,H_i)$
. Almost surely G is invertible. The negative second moment identity gives
For completeness, if
$y_i=G^{-1}e_i$
, then
$y_i\perp H_i$
and
$\langle R_i,y_i\rangle =1$
; hence,
$\|y_i\|=d_i^{-1}$
. Summing
$\|y_i\|^2=e_i^*(GG^*)^{-1}e_i$
over i proves (2.2).
If
$\sigma _{\mathrm {min}}(G)\le t$
, then the left-hand side of (2.2) is at least
$t^{-2}$
, so some i satisfies
$d_i\le \sqrt m\,t$
. Conditional on the other rows,
$d_i$
has the same distribution as
$|g_{\mathbb {F}}|$
, where
$g_{\mathbb {R}}\sim N(0,1)$
and
$g_{\mathbb {C}}$
is a standard complex Gaussian; hence,
$\mathbb {P}\{|g_{\mathbb {R}}|\le u\}\le \sqrt {2/\pi }\,u$
and
$\mathbb {P}\{|g_{\mathbb {C}}|\le u\}=1-e^{-u^2}\le u^2$
. A union bound over i gives (2.1).
We also use the following elementary asymptotic form of Stirling’s formula.
Lemma 2.2 (Binomial scale).
Let
$N_m/m\to \gamma>1$
. Then,
$m^{-1}\log \binom {N_m}{m}\to h(\gamma )$
, with h as in (1.2). If
$N_m=\gamma m+O(1)$
, then
$\binom {N_m-1}{m-1}=\Theta _\gamma (m^{-1/2}e^{h(\gamma )m})$
.
3 Lower bound: no square submatrix is much smaller
Proposition 3.1 (Lower estimate).
Under the assumptions of Theorem 1.1, for every fixed
$\varepsilon>0$
,
If
$N_m=\gamma m+O(1)$
, the probability in (3.1) is bounded by
$C_{\gamma ,\varepsilon ,\mathbb {F}}m^{1+d_{\mathbb {F}}/2}e^{-d_{\mathbb {F}}\varepsilon m}$
for all large m.
Proof. Let
$t>0$
. By a union bound and Lemma 2.1,
Take
$t=\exp [-(h(\gamma )/d_{\mathbb {F}}+\varepsilon )m]$
. Since
$m^{-1}\log \binom {N_m}{m}\to h(\gamma )$
, the bound tends to zero. The stated quantitative bound follows from Lemma 2.2 when
$N_m=\gamma m+O(1)$
.
4 Upper bound: one row and many random hyperplanes
The matching upper estimate is the main point. We fix one row and compare it with all hyperplanes generated by
$m-1$
of the remaining rows. Let
$A_m$
have rows
$a_1,\ldots ,a_N$
, with
$N=N_m$
. Put
$x=a_N$
and
$b_i=a_i$
for
$1\le i\le N-1$
, and define
For
$S\in \mathcal {S}$
, let
$H_S=\operatorname {span}_{\mathbb {F}}\{b_i:i\in S\}$
, almost surely a hyperplane in
$\mathbb {F}^m$
. Choose a unit normal
$u_S$
to
$H_S$
(over
$\mathbb {C}$
determined up to a phase; all events below are phase-invariant). For
$t>0$
, set
If
$Z_t>0$
, then for some S, the row x lies within distance t of
$H_S$
; for
$T=S\cup \{N\}$
and a unit vector
$v\perp H_S$
,
$\|A_{m,T}v\|=|\langle x,v\rangle |=\operatorname {\mathrm {dist}}(x,H_S)\le t$
. Thus,
4.1 Pair geometry
Lemma 4.1 (Normals for two overlapping row sets).
Fix distinct
$S,T\in \mathcal {S}$
. Let
$r=|S\cap T|$
and
$D=m-r$
. Then,
$D\ge 2$
. Conditional on the rows indexed by
$S\cap T$
, the two normal lines
$\mathbb {F} u_S$
and
$\mathbb {F} u_T$
are independent Haar-distributed lines in the D-dimensional space
$E^\perp $
, where
$E=\operatorname {span}_{\mathbb {F}}\{b_i:i\in S\cap T\}$
. Equivalently, for all phase-invariant events, one may take
$u_S,u_T$
to be independent Haar unit vectors in
$E^\perp $
.
Proof. Almost surely
$\dim _{\mathbb {F}} E=r$
, so
$\dim _{\mathbb {F}} E^\perp =D$
. The sets
$S\setminus T$
and
$T\setminus S$
each contain
$D-1$
rows, and the corresponding row families are independent conditional on the rows in
$S\cap T$
. Projecting the rows in
$S\setminus T$
to
$E^\perp $
gives
$D-1$
independent standard Gaussian vectors in
$E^\perp $
; their span is a hyperplane and by rotational invariance, its normal line is Haar-distributed. The same argument applies to
$T\setminus S$
, independently.
For
$D\ge 2$
, define, with
$u,v$
independent Haar unit vectors in
$\mathbb {F}^D$
and g an independent standard Gaussian vector in
$\mathbb {F}^D$
,
where
$g_{\mathbb {F}}$
is a standard scalar Gaussian over
$\mathbb {F}$
.
Lemma 4.2 (Two-slab and two-disk estimate).
For each
$\mathbb {F}\in \{\mathbb {R},\mathbb {C}\}$
, there is a constant
$C_{\mathbb {F}}$
such that, for
$0<t\le 1$
,
and
$q_2^{\mathbb {F}}(t)\le p_{\mathbb {F}}(t)$
.
Proof. The case
$D=2$
is immediate, since the joint event is contained in
$\{|\langle g,u\rangle |\le t\}$
. Assume
$D\ge 3$
. For
$\mathbb {F}=\mathbb {R}$
, conditional on
$u,v$
, write
$\rho =\langle u,v\rangle $
and
$s=(1-\rho ^2)^{1/2}$
; the pair
$(\langle g,u\rangle ,\langle g,v\rangle )$
is a centred real Gaussian vector with covariance determinant
$s^2$
and density at the origin
$(2\pi s)^{-1}$
, so
For independent Haar unit vectors in
$\mathbb {R}^D$
,
by the gamma-ratio asymptotics. Averaging (4.5) and using
$p_{\mathbb {R}}(t)=\sqrt {2/\pi }\,t+O(t^3)$
gives (4.4) over
$\mathbb {R}$
. For
$\mathbb {F}=\mathbb {C}$
, conditional on
$u,v$
, write
$s^2=1-|\rho |^2$
with
$\rho =\langle u,v\rangle $
; the pair is a centred complex Gaussian vector in
$\mathbb {C}^2$
with covariance determinant
$s^2$
and density at the origin
$(\pi ^2 s^2)^{-1}$
, so the probability of the product of the two disks of radius t is at most
$t^4/(1-|\rho |^2)$
. For independent Haar unit vectors in
$\mathbb {C}^D$
,
$|\rho |^2$
has the
$\mathrm {Beta}(1,D-1)$
distribution; hence,
$\mathbb {E}(1-|\rho |^2)^{-1}=(D-1)/(D-2)\le 1+C/D$
for
$D\ge 3$
. Since
$p_{\mathbb {C}}(t)=1-e^{-t^2}=t^2+O(t^4)$
, averaging gives (4.4) over
$\mathbb {C}$
.
Lemma 4.3 (Overlap combinatorics).
Let
$S,T$
be independent uniform elements of
$\mathcal {S}=\{S\subset [N-1]: |S|=m-1\}$
and set
$D=m-|S\cap T|$
. Then, for
$d\ge 1$
,
with the convention that binomial coefficients outside their natural range vanish. Moreover,
Proof. Fix S. To have
$D=d$
, the set T omits
$d-1$
elements of S and includes
$d-1$
elements from
$[N-1]\setminus S$
(of size
$N-m$
); this gives (4.6). With
$n=N-1$
and
$k=m-1$
,
using
$(j+1)^{-1}\binom kj=(k+1)^{-1}\binom {k+1}{j+1}$
and Vandermonde’s identity. Hence,
The value of
$\mathbb {P}\{D=2\}$
is (4.6) at
$d=2$
.
4.2 The second moment
Proposition 4.4 (Upper estimate).
Under the assumptions of Theorem 1.1, for every fixed
$\varepsilon>0$
,
If
$N_m=\gamma m+O(1)$
, the probability in (4.7) is
$O_{\gamma ,\varepsilon ,\mathbb {F}}(m^{-1})$
.
Proof. Take
$0<\varepsilon <h(\gamma )/d_{\mathbb {F}}$
. First, assume
$N_m=\gamma m+O(1)$
and write
$h=h(\gamma )$
,
$d=d_{\mathbb {F}}$
,
$t=\exp [-(h/d-\varepsilon )m]\in (0,1]$
for large m. With
$Z_t$
as in (4.1) and
$L=\binom {N-1}{m-1}$
,
$\mu :=\mathbb {E} Z_t=L\,p_{\mathbb {F}}(t)$
. Since
$p_{\mathbb {F}}(t)\ge c_{\mathbb {F}} t^d$
for
$0<t\le 1$
and
$L\ge c_\gamma m^{-1/2}e^{hm}$
(Lemma 2.2),
For
$S\ne T$
, Lemma 4.1 and the independence of x from all
$b_i$
give
$\mathbb {E}[X_SX_T]=q_{D(S,T)}^{\mathbb {F}}(t)$
with
$D(S,T)=m-|S\cap T|$
(projecting x to
$E^\perp $
makes it a standard Gaussian vector there, independent of
$u_S,u_T$
). It follows that, for
$S,T$
independent uniform in
$\mathcal {S}$
and
$D=m-|S\cap T|$
,
By Lemmas 4.2 and 4.3, the
$D\ge 3$
part is at most
$(1+C_{\mathbb {F}} t^2)\big (1+C_{\mathbb {F}}\,\mathbb {E}[1/D]\big )\le 1+C_{\mathbb {F}} t^2+C_{\gamma ,\mathbb {F}}/m$
(using
$\mathbb {E}[1/D]=O(1/m)$
). Further, the
$D=2$
part is at most
$\mathbb {P}\{D=2\}/p_{\mathbb {F}}(t)\le C_{\gamma ,\mathbb {F}}m^{5/2}e^{-d\varepsilon m}$
. With (4.8),
so by Chebyshev,
$\mathbb {P}\{Z_t=0\}\le \operatorname {Var}(Z_t)/\mu ^2=O(m^{-1})$
. With (4.2), this proves (4.7) and its rate when
$N_m=\gamma m+O(1)$
. For a general sequence
$N_m/m\to \gamma $
, repeat the proof with
$h(N_m/m)$
in place of
$h(\gamma )$
and use
$h(N_m/m)\to h(\gamma )$
.
5 Proofs of the main theorem and the phase retrieval corollary
Proof of Theorem 1.1.
By Propositions 3.1 and 4.4, for every
$\varepsilon\kern1.3pt{>}\kern1.3pt 0$
,
$m^{-1}\log M_m^{\mathbb {F}}(A_m)$
is below
$-h(\gamma )/d_{\mathbb {F}}-\varepsilon $
and above
$-h(\gamma )/d_{\mathbb {F}}+\varepsilon $
, each with probability
$\to 0$
; this is convergence in probability. When
$N_m=\gamma m+O(1)$
, the lower probability is exponentially small and the upper probability is
$O(m^{-1})$
, giving (1.3).
Proof of Corollary 1.2.
For Gaussian
$A_m\in \mathbb {R}^{(2m-1)\times m}$
, every m rows are independent almost surely, so the reduction (1.6) holds almost surely. Theorem 1.1 with
$\mathbb {F}=\mathbb {R}$
,
$N_m=2m-1$
and
$h(2)=\log 4$
gives (1.7)–(1.8). For the base in (1.5), note
$m^{-1}\log R_m\xrightarrow {P}0$
: the upper tail follows from a union bound and
$\mathbb {P}\{\|g\|\ge e^{\eta m}\}\le \exp (-c e^{2\eta m})$
for fixed
$\eta>0$
, and
$R_m\ge 1$
with high probability. If
$b>1/4$
, pick
$\varepsilon $
with
$e^{-(\log 4-\varepsilon )}<b$
; then with high probability,
$\omega (A_m)\le e^{-(\log 4-\varepsilon )m}\le b^m\le R_m b^m$
. If
$b<1/4$
and
$C<\infty $
, pick
$\varepsilon ,\eta $
with
$e^\eta b<e^{-(\log 4+\varepsilon )}$
; then with high probability,
$\omega (A_m)\ge e^{-(\log 4+\varepsilon )m}$
and
$R_m\le e^{\eta m}$
, so
$CR_m b^m\le C(e^\eta b)^m <e^{-(\log 4+\varepsilon )m}$
for large m, whence
$\mathbb {P}\{\omega (A_m)\le CR_m b^m\}\to 0$
.
Remark 5.1 (What drives the constants).
The theorem separates the two inputs that determine the exponential base. The combinatorial input is the entropy
$\binom {N_m}{m}=\exp \{h(\gamma )m+o(m)\}$
. The small-ball input is the real dimension of the scalar field:
$\mathbb {P}\{|g_{\mathbb {R}}|\le t\}\asymp t$
, while
$\mathbb {P}\{|g_{\mathbb {C}}|\le t\}\asymp t^2$
. Thus, the same binomial entropy is divided by
$d_{\mathbb {F}}=1$
over
$\mathbb {R}$
and by
$d_{\mathbb {F}}=2$
over
$\mathbb {C}$
.
6 Universality and the necessity of continuity
The lower estimate is insensitive to the entry law, provided it has a bounded density.
Proposition 6.1 (Universal lower estimate).
Let
$A_m\in \mathbb {R}^{N_m\times m}$
have independent and identically distributed entries with density bounded by K, and
$N_m/m\to \gamma>1$
. Then, for every fixed
$\varepsilon>0$
,
$\mathbb {P}\{M_m^{\mathbb {R}}(A_m)\le e^{-(h(\gamma )+\varepsilon )m}\}\to 0$
.
Proof. The identity (2.2) is purely algebraic. For
$G\in \mathbb {R}^{m\times m}$
with rows
$R_i$
and
$n_i$
the unit normal to
$\operatorname {span}\{R_j:j\ne i\}$
, the variable
$\langle R_i,n_i\rangle =\sum _j (R_i)_j (n_i)_j$
is, conditionally on the other rows, a sum of independent terms; the term with
$|(n_i)_{j^\ast }|=\max _j|(n_i)_j|\ge 1/\sqrt m$
has density at most
$K/|(n_i)_{j^\ast }|\le K\sqrt m$
, so the convolution has density at most
$K\sqrt m$
and
$\mathbb {P}\{d_i\le s\}\le 2K\sqrt m\,s$
. Hence,
$\mathbb {P}\{\sigma _{\mathrm {min}}(G)\le t\}\le 2Km^2 t$
and a union bound over
$\binom {N_m}{m}=e^{h(\gamma )m+o(m)}$
blocks tends to
$0$
at
$t=e^{-(h(\gamma )+\varepsilon )m}$
.
Remark 6.2 (Continuity is necessary).
For atomic entries, the lower estimate fails. If the entries are
$\pm 1$
Bernoulli and
$N=2m-1$
, every
$m\times m$
submatrix is singular with probability at least
$\mathbb {P}\{R_1=R_2\}=2^{-m}$
, so the expected number of singular
$m\times m$
submatrices is at least
$\binom {2m-1}{m}2^{-m}\ge c\,2^m/\sqrt m\to \infty $
. Thus, the first-moment heuristic behind Proposition 6.1 breaks down and a bounded-density assumption (in particular, Gaussianity) cannot be removed.
Remark 6.3 (Towards a universal upper estimate).
The upper estimate is expected to persist for independent and identically distributed sub-Gaussian entries with bounded density. The only use of Gaussianity is Lemma 4.1, where rotational invariance makes the hyperplane normals Haar-distributed. For bounded-density entries, the normals are delocalised with high probability, so a density-level local central limit theorem yields
$\mathbb {P}\{|\langle x,u_S\rangle |\le t\}=\Theta (t)$
together with the matching pair estimate; making this uniform over the
$\binom {N-1}{m-1}$
hyperplanes requires a delocalisation bound we do not pursue here. A Berry–Esseen estimate does not suffice at the scale
$t=e^{-\Theta (m)}$
, since its
$O(m^{-1/2})$
error dwarfs the signal; a density-level statement is needed.
Acknowledgement
During the preparation of this work, the author used generative AI tools (large language model assistants) to assist with drafting, revision and bibliographic organisation. After using these tools, the author reviewed and edited the content as needed and takes full responsibility for the content of the manuscript.
Open access
