Introduction and main results
Let A ∈ R N × m A \in\mathbb{R}^{N \times m} A ∈ R N × m , with N ≥ m N \ge m N ≥ m . For an integer 0 ≤ r ≤ N − m 0 \le r \le N-m 0 ≤ r ≤ N − m , define
M m , r ( A ) : = min T ⊂ [ N ] ∣ T ∣ = m + r σ m ( A T ) , M m ( A ) : = M m , 0 ( A ) , (1) M_{m,r}(A) := \min_{\substack{T \subset[N] \\ |T|=m+r}} \sigma_m(A_T), \qquad M_m(A) := M_{m,0}(A), \tag*{(1)} M m , r ( A ) := T ⊂ [ N ] ∣ T ∣ = m + r min σ m ( A T ) , M m ( A ) := M m , 0 ( A ) , (1)
where A T A_T A T is the row submatrix indexed by T T T . For any matrix B B B with m m m columns, we use the convention
σ m ( B ) : = inf ∥ x ∥ 2 = 1 ∥ B x ∥ 2 \sigma_m(B) := \inf_{\lVert x\rVert_2=1} \lVert Bx\rVert_2 σ m ( B ) := ∥ x ∥ 2 = 1 inf ∥ B x ∥ 2
to denote it’s least singular value. In particular, σ m ( B ) = 0 \sigma_m(B)=0 σ m ( B ) = 0 when B B B has rank less than m m m , including when it has fewer than m m m rows. The quantity M m , r ( A ) M_{m,r}(A) M m , r ( A ) measures the smallest least singular value among the ( m + r ) × m (m+r) \times m ( m + r ) × m row submatrices; the square case is r = 0 r=0 r = 0 .
For background on least singular values of i.i.d. random matrices, see [7 , 12 ] . Even when the entries of A A A are independent, the family in (1) contains exponentially many strongly dependent matrices. A one-matrix estimate alone therefore does not settle the problem. Related exponential conditioning questions occur in smoothed analyses of random polytopes and Frank–Wolfe methods; see [9 ] .
For γ > 1 \gamma> 1 γ > 1 , set
h ( γ ) : = γ log γ − ( γ − 1 ) log ( γ − 1 ) . (2) h(\gamma) := \gamma\log\gamma- (\gamma- 1)\log(\gamma- 1). \tag*{(2)} h ( γ ) := γ log γ − ( γ − 1 ) log ( γ − 1 ) . (2)
If N m / m → γ N_m/m \to\gamma N m / m → γ , then
( N m m ) = exp { h ( γ ) m + o ( m ) } . \binom{N_m}{m} = \exp\{h(\gamma)m + o(m)\}. ( m N m ) = exp { h ( γ ) m + o ( m )} .
Shmalo [10 ] established the square-row law for real standard Gaussian entries,
1 m log M m ( A m ) → P − h ( γ ) , \frac{1}{m}\log M_m(A_m) \xrightarrow{\mathbb{P}} -h(\gamma), m 1 log M m ( A m ) P − h ( γ ) ,
and the complex Gaussian exponent − h ( γ ) / 2 -h(\gamma)/2 − h ( γ ) /2 . The corresponding real Gaussian results with surplus rows are developed in [11 ] . The lower-tail argument extends to bounded-density entries by projection-density estimates. Obtaining the matching upper bound requires control of exponentially small small-ball probabilities over a strongly dependent family of random hyperplanes. Our main theorems establish the real bounded-density subgaussian law for both fixed and moderately growing surplus.
Main theorems
Throughout the paper, ξ \xi ξ is a centered, variance-one real subgaussian random variable with a bounded Lebesgue density f ξ f_\xi f ξ . Write
K : = ∥ f ξ ∥ ∞ < ∞ . K := \lVert f_\xi\rVert_\infty< \infty. K := ∥ f ξ ∥ ∞ < ∞.
All matrix entries are independent copies of ξ \xi ξ . No smoothness of f ξ f_\xi f ξ is assumed.
Theorem 1.1 (Fixed-surplus law). Let r ≥ 0 r \ge0 r ≥ 0 be a fixed integer, and let A m ∈ R N m × m A_m \in\mathbb{R}^{N_m \times m} A m ∈ R N m × m have independent entries distributed as ξ \xi ξ . Assume N m / m → γ > 1 N_m/m \to\gamma> 1 N m / m → γ > 1 and N m ≥ m + r N_m \ge m + r N m ≥ m + r for all large m m m . Then
1 m log M m , r ( A m ) → P − h ( γ ) r + 1 (3) \frac{1}{m}\log M_{m,r}(A_m) \xrightarrow{\mathbb{P}} -\frac{h(\gamma)}{r+1} \tag*{(3)} m 1 log M m , r ( A m ) P − r + 1 h ( γ ) (3)
Remark 1.2. Note that the normalization Var ( ξ ) = 1 \operatorname{Var}(\xi) = 1 Var ( ξ ) = 1 is adopted only for notational convenience. In fact, the theorem remains valid for any fixed positive variance. The reasons are as follows: assume Var ( ξ ) = σ 2 \operatorname{Var}(\xi) = \sigma^2 Var ( ξ ) = σ 2 , since ξ \xi ξ is subgaussian and has a Lebesgue density, 0 < σ < ∞ 0 < \sigma< \infty 0 < σ < ∞ . Define ξ ~ = ξ / σ \widetilde{\xi} = \xi/\sigma ξ = ξ / σ , A ~ m = A m / σ \widetilde{A}_m = A_m/\sigma A m = A m / σ . Then ξ ~ \widetilde{\xi} ξ is centered, variance one, subgaussian, and has density f ξ ~ ( x ) = σ f ξ ( σ x ) f_{\widetilde{\xi}}(x) = \sigma f_\xi(\sigma x) f ξ ( x ) = σ f ξ ( σ x ) , so that ∥ f ξ ~ ∥ ∞ ≤ σ K \lVert f_{\widetilde{\xi}}\rVert_\infty\le\sigma K ∥ f ξ ∥ ∞ ≤ σ K . Moreover, M m , r ( A m ) = σ M m , r ( A ~ m ) M_{m,r}(A_m) = \sigma M_{m,r}(\widetilde{A}_m) M m , r ( A m ) = σ M m , r ( A m ) . We have
1 m log M m , r ( A m ) = log σ m + 1 m log M m , r ( A ~ m ) . \frac{1}{m}\log M_{m,r}(A_m) = \frac{\log\sigma}{m} + \frac{1}{m}\log M_{m,r}(\widetilde{A}_m). m 1 log M m , r ( A m ) = m log σ + m 1 log M m , r ( A m ) .
Now since for every fixed ε ∈ ( 0 , h ( γ ) ) \varepsilon\in(0,h(\gamma)) ε ∈ ( 0 , h ( γ )) , ∣ log σ ∣ / m ≤ ε / 2 \lvert\log\sigma\rvert/m \le\varepsilon/2 ∣ log σ ∣ / m ≤ ε /2 for sufficiently large m m m ,
P { ∣ 1 m log M m , r ( A m ) + h ( γ ) r + 1 ∣ > ε } = P { ∣ log σ m + 1 m log M m , r ( A ~ m ) + h ( γ ) r + 1 ∣ > ε } ≤ P { ∣ 1 m log M m , r ( A ~ m ) + h ( γ ) r + 1 ∣ > ε 2 } . \mathbb{P}\left\{\left|\frac{1}{m}\log M_{m,r}(A_m) + \frac{h(\gamma)}{r+1}\right| > \varepsilon\right\}
= \mathbb{P}\left\{\left|\frac{\log\sigma}{m} + \frac{1}{m}\log M_{m,r}(\widetilde{A}_m) + \frac{h(\gamma)}{r+1}\right| > \varepsilon\right\}
\le\mathbb{P}\left\{\left|\frac{1}{m}\log M_{m,r}(\widetilde{A}_m) + \frac{h(\gamma)}{r+1}\right| > \frac{\varepsilon}{2}\right\}. P { m 1 log M m , r ( A m ) + r + 1 h ( γ ) > ε } = P { m log σ + m 1 log M m , r ( A m ) + r + 1 h ( γ ) > ε } ≤ P { m 1 log M m , r ( A m ) + r + 1 h ( γ ) > 2 ε } .
Thus, it is enough to establish the desired estimate for the normalized matrix A ~ m \widetilde{A}_m A m , i.e., under the assumption Var ( ξ ) = 1 \operatorname{Var}(\xi) = 1 Var ( ξ ) = 1 . For the remainder of the proof we impose this normalization.
If r r r is not fixed, we have the following moderate-surplus form.
Theorem 1.3 (Moderate-surplus law). Let N m N_m N m and r m r_m r m be integer-valued sequences, and let A m ∈ R N m × m A_m \in\mathbb{R}^{N_m \times m} A m ∈ R N m × m have i.i.d. entries distributed as ξ \xi ξ . Suppose
N m m ⟶ γ > 1 , k m = r m + 1 ∈ N , k m log m = o ( m ) , 0 ≤ r m ≤ N m − m \frac{N_m}{m} \longrightarrow\gamma> 1,\qquad k_m=r_m+1\in\mathbb{N},\qquad k_m\log m=o(m),\qquad0\le r_m\le N_m-m m N m ⟶ γ > 1 , k m = r m + 1 ∈ N , k m log m = o ( m ) , 0 ≤ r m ≤ N m − m for all large m m m . Then
k m m log M m , r m ( A m ) → P − h ( γ ) . (4) \frac{k_m}{m}\log M_{m,r_m}(A_m) \xrightarrow{\mathbb{P}} -h(\gamma). \tag*{(4)} m k m log M m , r m ( A m ) P − h ( γ ) . (4)
The deviation estimates proved below are summable. Consequently, if the matrices A m A_m A m are defined on a common probability space, the limits in Theorems 1.1 and 1.3 hold almost surely, without any independence assumption across dimensions; see Corollary 6.7 . In the phase-retrieval setting, the same argument gives almost-sure logarithmic laws for the obstruction ω ( A m ) \omega(A_m) ω ( A m ) and the optimal lower Lipschitz constant L A m L_{A_m} L A m , together with the corresponding condition-number rate in Corollary 6.8 .
The scale in Theorem 1.3 comes from balancing the number of candidate row sets against the probability of satisfying the smallness constraints. Write k = k m = r m + 1 k=k_m=r_m+1 k = k m = r m + 1 . There are exp { h ( γ ) m + o ( m ) } \exp\{h(\gamma)m+o(m)\} exp { h ( γ ) m + o ( m )} candidate row sets. An ( m − 1 ) (m-1) ( m − 1 ) -row base set determines a unit normal u u u , and adjoining k k k rows whose scalar products with u u u have absolute value at most t / k t/\sqrt{k} t / k produces an ( m + k − 1 ) × m (m+k-1)\times m ( m + k − 1 ) × m matrix with least singular value at most t t t . For a delocalized normal, each independent constraint has probability comparable to t / k t/\sqrt{k} t / k . Their combined cost is therefore t k exp { O ( k log ( k + 1 ) ) } t^k\exp\{O(k\log(k+1))\} t k exp { O ( k log ( k + 1 ))} . Since k log m = o ( m ) k\log m=o(m) k log m = o ( m ) , balancing this cost against the number of candidates suggests k log t ∼ − h ( γ ) m k\log t\sim-h(\gamma)m k log t ∼ − h ( γ ) m . The upper-bound proof makes this heuristic rigorous despite dependence, by reserving a small proportion of the rows and imposing the constraints sequentially while controlling the surviving pairs of candidate normals.
Remark 1.4 (Scope of the assumptions). The assumptions on ξ \xi ξ are sufficient and are not asserted to be optimal. Absolute continuity of the joint entry distribution implies that every prescribed row or column submatrix has its maximal possible rank almost surely: rank deficiency forces a nonzero minor polynomial to vanish, and its zero set has Lebesgue measure zero. Taking a finite union gives the simultaneous rank properties needed at each dimension. Thus the logarithms and normal lines used below are well defined without any smoothness assumption.
The bounded-density hypothesis supplies the projection-density bounds in Theorem 2.1 , including the one- and two-dimensional anti-concentration estimates, and the density bounds for the blocks used in Lemma 2.4 . The density-level Berry–Esseen estimate itself requires bounded densities and the stated variance and third-moment bounds, not differentiability of the entry density. Subgaussianity provides those moment bounds, the operator-norm tails, and the normal-vector delocalization estimate of Theorem 4.1 . Atomic laws fall outside these assumptions and require separate treatment; some such laws also have exact phase-retrieval obstructions.
Application to phase retrieval
The row-submatrix problem also arises naturally in real phase retrieval, where one seeks to recover a signal from the magnitudes of its linear measurements. For a measurement matrix A ∈ R N × m A\in\mathbb{R}^{N\times m} A ∈ R N × m , the amplitude map is
Φ A : R m / { ± 1 } ⟶ R N Φ A ( x ) = ∣ A x ∣ \Phi_A:\mathbb{R}^m/\{\pm1\}\longrightarrow\mathbb{R}^N\qquad\Phi_A(x)=|Ax| Φ A : R m / { ± 1 } ⟶ R N Φ A ( x ) = ∣ A x ∣
with the absolute value taken coordinatewise. The quotient accounts for the unavoidable ambiguity between x x x and − x -x − x . Besides the uniqueness of recovery, a basic question is how sensitively the recovered signal can depend on perturbations of the measured amplitudes.
The connection with row submatrices comes from the loss of sign information. When two signals x x x and y y y have similar measurement magnitudes, their signed measurements can be close either with the same sign or with opposite signs. The measurement rows can therefore be partitioned into a set J J J , on which A J ( x − y ) A_J(x-y) A J ( x − y ) is small, and its complement, on which A J c ( x + y ) A_{J^c}(x+y) A J c ( x + y ) is small. If the signals are separated up to sign, both x − y x-y x − y and x + y x+y x + y are bounded away from zero. Such a pair can consequently occur only when both complementary row blocks have small least singular values. Conversely, directions that are poorly detected by complementary blocks can be combined to produce signals with similar amplitude measurements. This connects phase-retrieval stability to the extreme singular values of row submatrices. For random measurement matrices, our estimates quantify the resulting instability near the critical measurement count.
Balan, Casazza, and Edidin [1 ] characterized injectivity in the real case by the complement property: for every J ⊂ [ N ] J \subset[N] J ⊂ [ N ] , either the rows of A J A_J A J or those of A J c A_{J^c} A J c span R m \mathbb{R}^m R m . Consequently, 2 m − 1 2m-1 2 m − 1 is the sharp generic measurement threshold for recovery of every real signal up to sign. Below this count no measurement family has the complement property, whereas at or above it every full-spark matrix does. Here full-spark means that every m m m rows are linearly independent. This holds almost surely under our absolute-continuity assumption.
Injectivity at each dimension leaves open the quantitative behavior of the inverse as the dimension grows. With d ± ( x , y ) = min { ∥ x − y ∥ 2 , ∥ x + y ∥ 2 } d_{\pm}(x,y) = \min\{\lVert x-y\rVert_2,\lVert x+y\rVert_2\} d ± ( x , y ) = min {∥ x − y ∥ 2 , ∥ x + y ∥ 2 } , the optimal lower Lipschitz constant and the associated condition number are
L A : = inf x ≠ ± y ∥ Φ A ( x ) − Φ A ( y ) ∥ 2 d ± ( x , y ) κ p h ( A ) : = ∥ A ∥ o p L A L_A := \inf_{x\ne\pm y}\frac{\lVert\Phi_A(x)-\Phi_A(y)\rVert_2}{d_{\pm}(x,y)}
\qquad
\kappa_{\mathrm{ph}}(A) := \frac{\lVert A\rVert_{\mathrm{op}}}{L_A} L A := x = ± y inf d ± ( x , y ) ∥ Φ A ( x ) − Φ A ( y ) ∥ 2 κ ph ( A ) := L A ∥ A ∥ op
where the latter is defined when L A > 0 L_A>0 L A > 0 . The optimal upper Lipschitz constant is ∥ A ∥ o p \lVert A\rVert_{\mathrm{op}} ∥ A ∥ op . Thus a small L A L_A L A means that some separated signals have nearly indistinguishable amplitude measurements, while κ p h ( A ) \kappa_{\mathrm{ph}}(A) κ ph ( A ) measures global conditioning independently of a common rescaling of the measurements.
Quantitative versions of the complement property connect this stability problem to singular values of complementary row blocks. Balan and Wang [2 ] identified the optimal lower Lipschitz constant through an exact partition formula. Bandeira, Cahill, Mixon, and Nelson [3 ] introduced the strong complement property and established quantitative stability estimates for Gaussian measurements. In particular, for each fixed measurement-to-dimension ratio strictly greater than two, their estimates give a condition number bounded independently of dimension with probability tending to one. This raises the question of how conditioning deteriorates when the measurement count approaches the injectivity threshold.
The connection with our row minima is particularly direct when N = 2 m − 1 + r N=2m-1+r N = 2 m − 1 + r and A A A is full spark. The Balan–Wang obstruction then satisfies
ω ( A ) : = min J ⊂ [ N ] rank ( A J ) < m σ m ( A J c ) = M m , r ( A ) , L A ≤ ω ( A ) \omega(A) := \min_{\substack{J\subset[N]\\ \operatorname{rank}(A_J)<m}}\sigma_m(A_{J^c}) = M_{m,r}(A),\qquad L_A\le\omega(A) ω ( A ) := J ⊂ [ N ] rank ( A J ) < m min σ m ( A J c ) = M m , r ( A ) , L A ≤ ω ( A )
At the critical count r = 0 r=0 r = 0 , every partition has a rank-deficient side, and the partition formula yields L A = ω ( A ) = M m , 0 ( A ) L_A=\omega(A)=M_{m,0}(A) L A = ω ( A ) = M m , 0 ( A ) . With additional rows, both sides can have full rank, so identifying the rate of L A L_A L A requires further estimate; see Proposition 6.1 and Lemma 6.3 .
For Gaussian entries and fixed surplus r r r , the results in [10 , 11 ] identify the exponential decay of the row minimum through m − 1 log M m , r ( A m ) → P − h ( γ ) / ( r + 1 ) m^{-1}\log M_{m,r}(A_m)\xrightarrow{\mathbb{P}}-h(\gamma)/(r+1) m − 1 log M m , r ( A m ) P − h ( γ ) / ( r + 1 ) when N m / m → γ > 1 N_m/m\to\gamma>1 N m / m → γ > 1 , yielding the rate − log 4 -\log4 − log 4 at the critical phase-retrieval count N m = 2 m − 1 N_m=2m-1 N m = 2 m − 1 . At the critical count, Häggblom [14 ] obtained finer localization of L A = ω ( A ) L_A=\omega(A) L A = ω ( A ) around the scale ( m ( 2 m − 1 m ) ) − 1 \left(\sqrt{m}\binom{2m-1}{m}\right)^{-1} ( m ( m 2 m − 1 ) ) − 1 , up to arbitrary diverging subexponential factors. The present paper establishes logarithmic universality for bounded-density subgaussian entries and treats both fixed and moderately growing surplus.
More precisely, let r m ≥ 0 r_m \ge0 r m ≥ 0 be intergers, let A m A_m A m have entries satisfying the standing assumptions, and suppose
N m = 2 m − 1 + r m , k m = r m + 1 , k m log m = o ( m ) N_m = 2m - 1 + r_m,\qquad k_m = r_m + 1,\qquad k_m \log m = o(m) N m = 2 m − 1 + r m , k m = r m + 1 , k m log m = o ( m )
Then N m / m → 2 N_m/m \to2 N m / m → 2 and h ( 2 ) = log 4 h(2) = \log4 h ( 2 ) = log 4 , so Theorem 1.3 determines the logarithmic rate of ω ( A m ) \omega(A_m) ω ( A m ) . Corollaries 6.5 and 6.8 establish
k m m log L A m → P − log 4 k m m log κ p h ( A m ) → P log 4 \frac{k_m}{m}\log L_{A_m} \xrightarrow{\mathbb{P}} -\log4 \qquad\frac{k_m}{m}\log\kappa_{\mathrm{ph}}(A_m) \xrightarrow{\mathbb{P}} \log4 m k m log L A m P − log 4 m k m log κ ph ( A m ) P log 4
The lower estimate for L A m L_{A_m} L A m combines the partition formula with independent small-ball estimates for complementary blocks and a union bound, following the strategy of the Gaussian strong-complement argument in [3 Theorem 20] . The matching upper estimate follows from L A m ≤ ω ( A m ) L_{A_m} \le\omega(A_m) L A m ≤ ω ( A m ) and our row-minimum theorem. These limits also hold almost surely on any common probability space, without independence across dimensions, by Corollaries 6.7 and 6.8.
These conclusions distinguish exact recovery from robust recovery. Under our assumptions, the measurements determine every signal up to sign almost surely at each dimension. Nevertheless, some distinct signals produce measurement vectors that are extremely close together. To interpret this independently of the overall measurement scale, normalize A m A_m A m by ∥ A m ∥ o p \lVert A_m\rVert_{\mathrm{op}} ∥ A m ∥ op . The resulting amplitude map has optimal upper Lipschitz constant one and optimal lower Lipschitz constant 1 / κ p h ( A m ) 1/\kappa_{\mathrm{ph}}(A_m) 1/ κ ph ( A m ) . Thus there are signal pairs separated by unit distance, modulo sign, whose normalized measurement vectors are separated by only 1 / κ p h ( A m ) 1/\kappa_{\mathrm{ph}}(A_m) 1/ κ ph ( A m ) . Measurement perturbations of this order can make such signals indistinguishable. This difficulty is intrinsic to the measurements. Any reconstruction method that recovers all signals must contend with the corresponding worst-case sensitivity.
For fixed surplus r r r , this sensitivity grows exponentially with dimension, at logarithmic rate log 4 / ( r + 1 ) \log4/(r + 1) log 4/ ( r + 1 ) . Additional measurements therefore reduce the rate of deterioration, but a fixed number of rows beyond the injectivity threshold does not prevent exponential ill-conditioning. The conclusion also covers growing surplus. Whenever ( r m + 1 ) log m = o ( m ) (r_m + 1)\log m = o(m) ( r m + 1 ) log m = o ( m ) , the condition number exceeds every fixed power of m m m with probability tending to one. In particular, the additional measurements in this regime are insufficient to obtain even a polynomial bound on the global condition number, despite guaranteeing uniqueness of recovery.
The result therefore quantifies the gap between uniqueness and uniform robustness near the critical measurement count. Its interpretation is a worst-case one, concerning recovery uniformly over all signals. Particular signals or restricted signal classes may have substantially better stability. The common logarithmic rate of L A m L_{A_m} L A m and ω ( A m ) \omega(A_m) ω ( A m ) identifies the scale of this global instability, without asserting equality of these quantities for redundant matrices or a precise multiplicative asymptotic.
Comparison with the Gaussian argument
The Gaussian proof uses rotational invariance to describe hyperplane normals by Haar-distributed directions. For general i.i.d. entries, we instead use the following ingredients.
A density-level local central limit estimate gives a uniform positive density near zero for ⟨ X , u ⟩ \langle X,u\rangle ⟨ X , u ⟩ when u u u is sufficiently delocalized.
(ii) The Nguyen–Vu normal-vector estimate, followed by averaging and Markov’s inequality, shows that a positive fraction of the candidate hyperplanes have delocalized normals.
(iii) Except for an exponentially small fraction of pairs, the normals have a fixed positive projective separation. This follows from an operator-norm bound and fresh-row small-ball estimates.
(iv) The reserved rows are split into k m k_m k m independent groups. A one-row second-moment argument provides a fixed positive success probability; selection within each group amplifies this probability. The surviving candidates and exceptional pairs are controlled through all k m k_m k m restrictions.
Preliminaries
Notation
We use the usual small o o o and big O O O notation. For a real random variable Y Y Y , let dens ( Y ) \operatorname{dens}(Y) dens ( Y ) denote its Lebesgue density and let ∥ dens ( Y ) ∥ ∞ \|\operatorname{dens}(Y)\|_\infty ∥ dens ( Y ) ∥ ∞ denote the essential supremum of that density. We use the Orlicz convention
∥ Y ∥ ψ 2 : = inf { s > 0 : E exp ( Y 2 / s 2 ) ≤ 2 } , \|Y\|_{\psi_2}:=\inf\{s>0:\mathbb{E}\exp(Y^2/s^2)\le2\}, ∥ Y ∥ ψ 2 := inf { s > 0 : E exp ( Y 2 / s 2 ) ≤ 2 } ,
and say that Y Y Y is subgaussian when ∥ Y ∥ ψ 2 < ∞ \|Y\|_{\psi_2}<\infty ∥ Y ∥ ψ 2 < ∞ .
Throughout the proof, constants denoted by c c c , C C C , C 1 , … C_1,\ldots C 1 , … may change from line to line. Constants in distributional lemmas depend only on the law of ξ \xi ξ ; constants in tail estimates may also depend on fixed parameters such as γ \gamma γ and ε \varepsilon ε , but never on m m m .
For unit vectors u , v ∈ R m u,v\in\mathbb{R}^m u , v ∈ R m , define their projective distance by
d p r ( u , v ) : = min { ∥ u − v ∥ 2 , ∥ u + v ∥ 2 } . (5) d_{\mathrm{pr}}(u,v):=\min\{\|u-v\|_2,\|u+v\|_2\}. \tag*{(5)} d pr ( u , v ) := min { ∥ u − v ∥ 2 , ∥ u + v ∥ 2 } . (5)
Upper bounds for projection densities
We first record the projection-density theorem of Rudelson and Vershynin [8 ] . The distinction between its general d d d -dimensional form and its sharp one-dimensional form is important for the two-dimensional estimate below.
Theorem 2.1 (Densities of projections). Let X = ( X 1 , … , X n ) X=(X_1,\ldots,X_n) X = ( X 1 , … , X n ) have independent real-valued coordinates whose densities are bounded by K K K almost everywhere. If P P P is the orthogonal projection in R n \mathbb{R}^n R n onto a d d d -dimensional subspace, then the density of P X PX P X , with respect to d d d -dimensional Lebesgue measure on that subspace, is bounded by ( C R V K ) d (C_{\mathrm{RV}}K)^d ( C RV K ) d almost everywhere, where C R V > 0 C_{\mathrm{RV}}>0 C RV > 0 is an absolute constant. In dimension d = 1 d=1 d = 1 , the sharper bound 2 K \sqrt{2}K 2 K holds.
Lemma 2.2 (One- and two-dimensional marginal bounds). Let ξ \xi ξ be as in Theorem 1.1 , and let X = ( ξ 1 , … , ξ m ) X=(\xi_1,\ldots,\xi_m) X = ( ξ 1 , … , ξ m ) have independent coordinates distributed as ξ \xi ξ . Then, for every deterministic unit vector u ∈ R m u\in\mathbb{R}^m u ∈ R m ,
∥ dens ( ⟨ X , u ⟩ ) ∥ ∞ ≤ 2 K . (6) \|\operatorname{dens}(\langle X,u\rangle)\|_\infty\le\sqrt{2}K. \tag*{(6)} ∥ dens (⟨ X , u ⟩) ∥ ∞ ≤ 2 K . (6) Furthermore, for unit vectors u , v ∈ R m u,v\in\mathbb{R}^m u , v ∈ R m with ρ = ⟨ u , v ⟩ \rho=\langle u,v\rangle ρ = ⟨ u , v ⟩ and ∣ ρ ∣ < 1 |\rho|<1 ∣ ρ ∣ < 1 ,
∥ dens ( ⟨ X , u ⟩ , ⟨ X , v ⟩ ) ∥ ∞ ≤ C R V 2 K 2 1 − ρ 2 . (7) \|\operatorname{dens}(\langle X,u\rangle,\langle X,v\rangle)\|_\infty\le\frac{C_{\mathrm{RV}}^2K^2}{\sqrt{1-\rho^2}}. \tag*{(7)} ∥ dens (⟨ X , u ⟩ , ⟨ X , v ⟩) ∥ ∞ ≤ 1 − ρ 2 C RV 2 K 2 . (7)
Proof. Let E = span ( u ) E = \operatorname{span}(u) E = span ( u ) and let P E P_E P E be the orthogonal projection onto E E E . Since P E X = ⟨ X , u ⟩ u P_E X = \langle X,u\rangle u P E X = ⟨ X , u ⟩ u , the isometry t ↦ t u t \mapsto tu t ↦ t u identifies the density of P E X P_E X P E X on E E E with the density of ⟨ X , u ⟩ \langle X,u\rangle ⟨ X , u ⟩ . The sharp one-dimensional part of Theorem 2.1 therefore gives (6) .
For the two-dimensional estimate, let E = span ( u , v ) E = \operatorname{span}(u,v) E = span ( u , v ) and choose the orthonormal basis
e 1 = u , e 2 = v − ρ u 1 − ρ 2 . e_1 = u,\qquad e_2 = \frac{v-\rho u}{\sqrt{1-\rho^2}}. e 1 = u , e 2 = 1 − ρ 2 v − ρ u .
Set Y = ( ⟨ X , e 1 ⟩ , ⟨ X , e 2 ⟩ ) Y = (\langle X,e_1\rangle,\langle X,e_2\rangle) Y = (⟨ X , e 1 ⟩ , ⟨ X , e 2 ⟩) . The general d = 2 d=2 d = 2 part of Theorem 2.1 gives
∥ dens ( Y ) ∥ ∞ ≤ C R V 2 K 2 . \left\lVert\operatorname{dens}(Y)\right\rVert_\infty\le C_{\mathrm{RV}}^2 K^2. ∥ dens ( Y ) ∥ ∞ ≤ C RV 2 K 2 .
Moreover,
( ⟨ X , u ⟩ , ⟨ X , v ⟩ ) = B Y , B = ( 1 0 ρ 1 − ρ 2 ) , (\langle X,u\rangle,\langle X,v\rangle) = BY,\qquad B = \begin{pmatrix} 1 & 0 \\ \rho& \sqrt{1-\rho^2} \end{pmatrix}, (⟨ X , u ⟩ , ⟨ X , v ⟩) = B Y , B = ( 1 ρ 0 1 − ρ 2 ) ,
and ∣ det B ∣ = 1 − ρ 2 \lvert\det B\rvert= \sqrt{1-\rho^2} ∣ det B ∣ = 1 − ρ 2 . The change-of-variables formula for densities yields
∥ dens ( B Y ) ∥ ∞ ≤ ∥ dens ( Y ) ∥ ∞ ∣ det B ∣ , \left\lVert\operatorname{dens}(BY)\right\rVert_\infty\le\frac{\left\lVert\operatorname{dens}(Y)\right\rVert_\infty}{\lvert\det B\rvert}, ∥ dens ( B Y ) ∥ ∞ ≤ ∣ det B ∣ ∥ dens ( Y ) ∥ ∞ ,
which is exactly (7) .
We next extract the one-dimensional form of the density-level Berry–Esseen theorem needed below.
Theorem 2.3 (Density-level Berry–Esseen theorem). Let Y 1 , … , Y r Y_1,\ldots,Y_r Y 1 , … , Y r be independent centered real random variables such that
∑ ℓ = 1 r Var ( Y ℓ ) = r . \sum_{\ell=1}^{r} \operatorname{Var}(Y_\ell)=r. ℓ = 1 ∑ r Var ( Y ℓ ) = r . Assume that, for fixed positive constants b b b , M M M , B B B , every ℓ \ell ℓ satisfies
Var ( Y ℓ ) ≤ b , ∥ dens ( Y ℓ ) ∥ ∞ ≤ M , E ∣ Y ℓ ∣ 3 ≤ B . \operatorname{Var}(Y_\ell)\le b,\qquad\left\lVert\operatorname{dens}(Y_\ell)\right\rVert_\infty\le M,\qquad\mathbb{E}\lvert Y_\ell\rvert^3\le B. Var ( Y ℓ ) ≤ b , ∥ dens ( Y ℓ ) ∥ ∞ ≤ M , E ∣ Y ℓ ∣ 3 ≤ B . If f r f_r f r is the density of r − 1 / 2 ∑ ℓ = 1 r Y ℓ r^{-1/2}\sum_{\ell=1}^{r}Y_\ell r − 1/2 ∑ ℓ = 1 r Y ℓ and φ \varphi φ is the standard Gaussian density, then
sup x ∈ R ∣ f r ( x ) − φ ( x ) ∣ ≤ C ( b , M , B ) r . (8) \sup_{x\in\mathbb{R}}\lvert f_r(x)-\varphi(x)\rvert\le\frac{C(b,M,B)}{\sqrt{r}}. \tag*{(8)} x ∈ R sup ∣ f r ( x ) − φ ( x )∣ ≤ r C ( b , M , B ) . (8)
Proof. Apply the one-dimensional case of [4 Theorem 1, inequality (1.1)] , with n = r n=r n = r , X ℓ = Y ℓ X_\ell=Y_\ell X ℓ = Y ℓ , and Z n = r − 1 / 2 ∑ ℓ = 1 r Y ℓ Z_n=r^{-1/2}\sum_{\ell=1}^{r}Y_\ell Z n = r − 1/2 ∑ ℓ = 1 r Y ℓ . In that theorem the parameters are
σ 2 = max ℓ Var ( Y ℓ ) , M ∗ = max ℓ ∥ dens ( Y ℓ ) ∥ ∞ , β 3 = 1 r ∑ ℓ = 1 r E ∣ Y ℓ ∣ 3 . \sigma^2=\max_{\ell}\operatorname{Var}(Y_\ell),\qquad M_*=\max_{\ell}\left\lVert\operatorname{dens}(Y_\ell)\right\rVert_\infty,\qquad\beta_3=\frac{1}{r}\sum_{\ell=1}^{r}\mathbb{E}\lvert Y_\ell\rvert^3. σ 2 = ℓ max Var ( Y ℓ ) , M ∗ = ℓ max ∥ dens ( Y ℓ ) ∥ ∞ , β 3 = r 1 ℓ = 1 ∑ r E ∣ Y ℓ ∣ 3 .
The variance normalization here is precisely the normalization there. Consequently,
∥ f r − φ ∥ ∞ ≤ C σ M ∗ 2 β 3 r ≤ C b M 2 B r , \left\lVert f_r-\varphi\right\rVert_\infty\le\frac{C\sigma M_*^2\beta_3}{\sqrt{r}}\le\frac{C\sqrt{b}M^2B}{\sqrt{r}}, ∥ f r − φ ∥ ∞ ≤ r C σ M ∗ 2 β 3 ≤ r C b M 2 B ,
which proves (8) . No smoothness of the densities is required.
The advantage of this density-level estimate is that its integrated error scales with the length of the interval. If ∥ f − φ ∥ ∞ ≤ δ \lVert f-\varphi\rVert_{\infty}\le\delta ∥ f − φ ∥ ∞ ≤ δ , then for every t > 0 t>0 t > 0 ,
∣ ∫ − t t f ( x ) d x − ∫ − t t φ ( x ) d x ∣ ≤ 2 t δ . \left|\int_{-t}^{t}f(x)\,\mathrm{d}x-\int_{-t}^{t}\varphi(x)\,\mathrm{d}x\right|\le2t\delta. ∫ − t t f ( x ) d x − ∫ − t t φ ( x ) d x ≤ 2 t δ .
Thus a sufficiently small uniform density error gives a useful relative estimate even when t t t is exponentially small. An approximation of distribution functions with uniform error δ \delta δ gives only an absolute interval error at most 2 δ 2\delta 2 δ , which may exceed the probability being estimated.
Combining Lemma 2.2 with Theorem 2.3 gives the local lower bound used in the upper-tail argument. The point is that, when u u u is delocalized, no single summand u j ξ j u_j\xi_j u j ξ j contributes appreciably to ⟨ u , X ⟩ \langle u,X\rangle ⟨ u , X ⟩ . The resulting sum lies in a local central-limit regime, so its density is uniformly positive near the origin.
A local lower bound for projection densities
Lemma 2.4 (Uniform local lower density). There are constants η , c 0 > 0 \eta,c_0>0 η , c 0 > 0 , depending only on the law of ξ \xi ξ , such that for every m m m and every unit vector u ∈ R m u\in\mathbb{R}^m u ∈ R m with ∥ u ∥ ∞ ≤ η \lVert u\rVert_{\infty}\le\eta ∥ u ∥ ∞ ≤ η , a version f u f_u f u of the density of ⟨ X , u ⟩ \langle X,u\rangle ⟨ X , u ⟩ satisfies
f u ( x ) ≥ c 0 , ∀ ∣ x ∣ ≤ 1. (9) f_u(x)\ge c_0,\qquad\forall|x|\le1. \tag*{(9)} f u ( x ) ≥ c 0 , ∀∣ x ∣ ≤ 1. (9)
Proof. Fix an integer q ≥ 1 q\ge1 q ≥ 1 , to be chosen sufficiently large in terms of the distribution of ξ \xi ξ . We first assume that
max 1 ≤ j ≤ m u j 2 ≤ 1 4 q . \max_{1\le j\le m}u_j^2\le\frac{1}{4q}. 1 ≤ j ≤ m max u j 2 ≤ 4 q 1 .
Set w j : = u j 2 w_j:=u_j^2 w j := u j 2 . Since ∥ u ∥ 2 = 1 \lVert u\rVert_2=1 ∥ u ∥ 2 = 1 , we have ∑ j = 1 m w j = 1 \sum_{j=1}^{m}w_j=1 ∑ j = 1 m w j = 1 .
We partition the nonzero weights w j w_j w j into consecutive blocks by the following greedy procedure. Starting with an empty block, add nonzero weights until their sum first becomes at least 1 / q 1/q 1/ q , then close the block and repeat with the remaining weights. Since each weight is at most 1 / ( 4 q ) 1/(4q) 1/ ( 4 q ) , every completed block has total weight between 1 / q 1/q 1/ q and 5 / ( 4 q ) 5/(4q) 5/ ( 4 q ) . At the end there may remain a terminal collection of total mass less than 1 / q 1/q 1/ q ; merge it into the last completed block. Because the total mass is one, at least one block is completed. We obtain nonempty disjoint blocks B 1 , … , B r B_1,\ldots,B_r B 1 , … , B r whose union contains all j j j with u j ≠ 0 u_j\ne0 u j = 0 , and, with w ℓ : = ∑ j ∈ B ℓ u j 2 w_\ell:=\sum_{j\in B_\ell}u_j^2 w ℓ := ∑ j ∈ B ℓ u j 2 ,
1 q ≤ w ℓ ≤ 9 4 q , ∑ ℓ = 1 r w ℓ = 1. \frac{1}{q}\le w_\ell\le\frac{9}{4q},\qquad\sum_{\ell=1}^{r}w_\ell=1. q 1 ≤ w ℓ ≤ 4 q 9 , ℓ = 1 ∑ r w ℓ = 1.
The upper bound follows because the last completed block has weight at most 5 / ( 4 q ) 5/(4q) 5/ ( 4 q ) before the terminal remainder, while the remainder has weight less than 1 / q 1/q 1/ q . Consequently,
4 q 9 ≤ r ≤ q . \frac{4q}{9}\le r\le q. 9 4 q ≤ r ≤ q .
For ℓ = 1 , … , r \ell=1,\ldots,r ℓ = 1 , … , r , define
Z ℓ : = r ∑ j ∈ B ℓ u j ξ j . Z_\ell:=\sqrt{r}\sum_{j\in B_\ell}u_j\xi_j. Z ℓ := r j ∈ B ℓ ∑ u j ξ j .
The variables Z 1 , … , Z r Z_1,\ldots,Z_r Z 1 , … , Z r are independent and centered. Since Var ( ξ ) = 1 \operatorname{Var}(\xi)=1 Var ( ξ ) = 1 ,
Var ( Z ℓ ) = r ∑ j ∈ B ℓ u j 2 = r w ℓ , \operatorname{Var}(Z_\ell)=r\sum_{j\in B_\ell}u_j^2=rw_\ell, Var ( Z ℓ ) = r j ∈ B ℓ ∑ u j 2 = r w ℓ ,
and therefore
4 9 ≤ Var ( Z ℓ ) ≤ 9 4 , ∑ ℓ = 1 r Var ( Z ℓ ) = r . \frac{4}{9} \le\operatorname{Var}(Z_\ell) \le\frac{9}{4}, \qquad\sum_{\ell=1}^{r} \operatorname{Var}(Z_\ell)=r. 9 4 ≤ Var ( Z ℓ ) ≤ 4 9 , ℓ = 1 ∑ r Var ( Z ℓ ) = r .
We next establish a uniform density bound. If B ℓ B_\ell B ℓ contains at least two indices, put a j : = u j / w ℓ a_j:=u_j/\sqrt{w_\ell} a j := u j / w ℓ for j ∈ B ℓ j\in B_\ell j ∈ B ℓ . Then ∑ j ∈ B ℓ a j 2 = 1 \sum_{j\in B_\ell}a_j^2=1 ∑ j ∈ B ℓ a j 2 = 1 , so Lemma 2.2 gives
∥ dens ( ∑ j ∈ B ℓ a j ξ j ) ∥ ∞ ≤ 2 K . \left\|\operatorname{dens}\left(\sum_{j\in B_\ell}a_j\xi_j\right)\right\|_\infty\le\sqrt{2}K. dens j ∈ B ℓ ∑ a j ξ j ∞ ≤ 2 K .
Since
Z ℓ = r w ℓ ∑ j ∈ B ℓ a j ξ j , Z_\ell=\sqrt{r w_\ell}\sum_{j\in B_\ell}a_j\xi_j, Z ℓ = r w ℓ j ∈ B ℓ ∑ a j ξ j ,
the scaling rule for densities yields
∥ dens ( Z ℓ ) ∥ ∞ ≤ 2 K r w ℓ ≤ 3 2 2 K . \|\operatorname{dens}(Z_\ell)\|_\infty\le\frac{\sqrt{2}K}{\sqrt{r w_\ell}}\le\frac{3\sqrt{2}}{2}K. ∥ dens ( Z ℓ ) ∥ ∞ ≤ r w ℓ 2 K ≤ 2 3 2 K .
If B ℓ = { j } B_\ell=\{j\} B ℓ = { j } is a singleton, then Z ℓ = r u j ξ j Z_\ell=\sqrt{r}u_j\xi_j Z ℓ = r u j ξ j , and
∥ dens ( Z ℓ ) ∥ ∞ ≤ K r ∣ u j ∣ = K r w ℓ ≤ 3 2 K . \|\operatorname{dens}(Z_\ell)\|_\infty\le\frac{K}{\sqrt{r}|u_j|}=\frac{K}{\sqrt{r w_\ell}}\le\frac{3}{2}K. ∥ dens ( Z ℓ ) ∥ ∞ ≤ r ∣ u j ∣ K = r w ℓ K ≤ 2 3 K .
Thus ∥ dens ( Z ℓ ) ∥ ∞ ≤ C 1 K \|\operatorname{dens}(Z_\ell)\|_\infty\le C_1K ∥ dens ( Z ℓ ) ∥ ∞ ≤ C 1 K in all cases. The third moments are also uniformly bounded. Since ξ \xi ξ is subgaussian and the coordinates are independent and centered, the standard subgaussian inequality for linear combinations [13 Proposition 2.6.1] gives
∥ ∑ j ∈ B ℓ u j ξ j ∥ ψ 2 ≤ C ∥ ξ ∥ ψ 2 ( ∑ j ∈ B ℓ u j 2 ) 1 / 2 . \left\|\sum_{j\in B_\ell}u_j\xi_j\right\|_{\psi_2}\le C\|\xi\|_{\psi_2}\left(\sum_{j\in B_\ell}u_j^2\right)^{1/2}. j ∈ B ℓ ∑ u j ξ j ψ 2 ≤ C ∥ ξ ∥ ψ 2 j ∈ B ℓ ∑ u j 2 1/2 .
Consequently,
∥ Z ℓ ∥ ψ 2 ≤ C ∥ ξ ∥ ψ 2 r w ℓ ≤ 3 C 2 ∥ ξ ∥ ψ 2 , \|Z_\ell\|_{\psi_2}\le C\|\xi\|_{\psi_2}\sqrt{r w_\ell}\le\frac{3C}{2}\|\xi\|_{\psi_2}, ∥ Z ℓ ∥ ψ 2 ≤ C ∥ ξ ∥ ψ 2 r w ℓ ≤ 2 3 C ∥ ξ ∥ ψ 2 ,
so E ∣ Z ℓ ∣ 3 ≤ C 2 \mathbb{E}|Z_\ell|^3\le C_2 E ∣ Z ℓ ∣ 3 ≤ C 2 , where C 2 C_2 C 2 depends only on the law of ξ \xi ξ . We may therefore apply Theorem 2.3 with b = 9 / 4 b=9/4 b = 9/4 , M = C 1 K M=C_1K M = C 1 K , and B = C 2 B=C_2 B = C 2 . Since
1 r ∑ ℓ = 1 r Z ℓ = ∑ j = 1 m u j ξ j = ⟨ X , u ⟩ , \frac{1}{\sqrt{r}}\sum_{\ell=1}^{r}Z_\ell=\sum_{j=1}^{m}u_j\xi_j=\langle X,u\rangle, r 1 ℓ = 1 ∑ r Z ℓ = j = 1 ∑ m u j ξ j = ⟨ X , u ⟩ ,
if f u f_u f u denotes the density of ⟨ X , u ⟩ \langle X,u\rangle ⟨ X , u ⟩ , then
sup x ∈ R ∣ f u ( x ) − φ ( x ) ∣ ≤ C 3 r ≤ 3 C 3 2 q . \sup_{x\in\mathbb{R}}|f_u(x)-\varphi(x)|\le\frac{C_3}{\sqrt{r}}\le\frac{3C_3}{2\sqrt{q}}. x ∈ R sup ∣ f u ( x ) − φ ( x ) ∣ ≤ r C 3 ≤ 2 q 3 C 3 .
Choose q q q sufficiently large that 3 C 3 / ( 2 q ) ≤ φ ( 1 ) / 2 3C_3/(2\sqrt{q})\le\varphi(1)/2 3 C 3 / ( 2 q ) ≤ φ ( 1 ) /2 . Then, for ∣ x ∣ ≤ 1 |x|\le1 ∣ x ∣ ≤ 1 ,
f u ( x ) ≥ φ ( x ) − φ ( 1 ) 2 ≥ φ ( 1 ) 2 . f_u(x)\ge\varphi(x)-\frac{\varphi(1)}{2}\ge\frac{\varphi(1)}{2}. f u ( x ) ≥ φ ( x ) − 2 φ ( 1 ) ≥ 2 φ ( 1 ) .
Set
η : = 1 2 q , c 0 : = φ ( 1 ) 2 . \eta:=\frac{1}{2\sqrt{q}},\qquad c_0:=\frac{\varphi(1)}{2}. η := 2 q 1 , c 0 := 2 φ ( 1 ) .
If ∥ u ∥ ∞ ≤ η \|u\|_\infty\le\eta ∥ u ∥ ∞ ≤ η , then max j u j 2 ≤ 1 / ( 4 q ) \max_j u_j^2\le1/(4q) max j u j 2 ≤ 1/ ( 4 q ) , so all preceding estimates apply and we get (9) . □
The lower estimate
The lower estimate follows from a small-ball bound for one rectangular matrix and a union bound over row sets. We first record the required count and then state the one-matrix estimate separately.
Lemma 3.1 (Binomial estimates). Let N m / m → γ > 1 N_m/m \to\gamma> 1 N m / m → γ > 1 , let k m ≥ 1 k_m \ge1 k m ≥ 1 be integers, and assume k m log m = o ( m ) k_m \log m = o(m) k m log m = o ( m ) . Then
log ( N m m + k m − 1 ) = h ( γ ) m + o ( m ) . \log\binom{N_m}{m+k_m-1} = h(\gamma)m + o(m). log ( m + k m − 1 N m ) = h ( γ ) m + o ( m ) .
Proof. Set a m = ( m + k m − 1 ) / m a_m=(m+k_m-1)/m a m = ( m + k m − 1 ) / m and b m = N m / m b_m=N_m/m b m = N m / m . Then a m → 1 a_m \to1 a m → 1 and b m → γ b_m \to\gamma b m → γ . Stirling’s formula gives
1 m log ( N m m + k m − 1 ) = b m log b m − a m log a m − ( b m − a m ) log ( b m − a m ) + o ( 1 ) ⟶ h ( γ ) . \frac{1}{m}\log\binom{N_m}{m+k_m-1}=b_m\log b_m-a_m\log a_m-(b_m-a_m)\log(b_m-a_m)+o(1)\longrightarrow h(\gamma). m 1 log ( m + k m − 1 N m ) = b m log b m − a m log a m − ( b m − a m ) log ( b m − a m ) + o ( 1 ) ⟶ h ( γ ) .
Lemma 3.2 (Rectangular small-ball estimate). Let B B B be an ( m + d − 1 ) × m (m+d-1)\times m ( m + d − 1 ) × m matrix whose entries are independent and have Lebesgue densities bounded by K K K , where m , d ≥ 1 m,d\ge1 m , d ≥ 1 are integers. There is an absolute constant C R V > 0 C_{\mathrm{RV}}>0 C RV > 0 such that, for every t > 0 t>0 t > 0 ,
P { σ m ( B ) ≤ t } ≤ m ( C R V K ) d v d ( m t ) d ≤ m ( D m t ) d , (10) \mathbb{P}\{\sigma_m(B)\le t\}\le m(C_{\mathrm{RV}}K)^d v_d(\sqrt{m}t)^d\le m(D\sqrt{m}t)^d, \tag*{(10)} P { σ m ( B ) ≤ t } ≤ m ( C RV K ) d v d ( m t ) d ≤ m ( D m t ) d , (10) where v d v_d v d is the volume of the Euclidean unit ball in R d \mathbb{R}^d R d and D : = max { 1 , 2 C R V K } D:=\max\{1,2C_{\mathrm{RV}}K\} D := max { 1 , 2 C RV K } depends only on K K K .
Proof. Write C 1 , … , C m C_1,\ldots,C_m C 1 , … , C m for the columns of B B B , and set
H j : = span { C ℓ : ℓ ≠ j } , δ j : = dist ( C j , H j ) . H_j:=\operatorname{span}\{C_\ell:\ell\ne j\},\qquad\delta_j:=\operatorname{dist}(C_j,H_j). H j := span { C ℓ : ℓ = j } , δ j := dist ( C j , H j ) .
Absolute continuity implies full column rank almost surely, both for B B B and for each matrix obtained by removing one column. The negative second-moment identity is
∑ i = 1 m σ i ( B ) − 2 = tr ( ( B T B ) − 1 ) = ∑ j = 1 m δ j − 2 . (11) \sum_{i=1}^{m}\sigma_i(B)^{-2}=\operatorname{tr}\left((B^{T}B)^{-1}\right)=\sum_{j=1}^{m}\delta_j^{-2}. \tag*{(11)} i = 1 ∑ m σ i ( B ) − 2 = tr ( ( B T B ) − 1 ) = j = 1 ∑ m δ j − 2 . (11)
Indeed, the j j j th diagonal entry of ( B T B ) − 1 (B^{T}B)^{-1} ( B T B ) − 1 is δ j − 2 \delta_j^{-2} δ j − 2 . If σ m ( B ) ≤ t \sigma_m(B)\le t σ m ( B ) ≤ t , then some δ j ≤ m t \delta_j\le\sqrt{m}t δ j ≤ m t . Condition on all columns except C j C_j C j . The subspace H j ⊥ H_j^\perp H j ⊥ has dimension d d d almost surely, and C j C_j C j is independent of it. Theorem 2.1 therefore gives
P { δ j ≤ m t ∣ ( C ℓ ) ℓ ≠ j } ≤ ( C R V K ) d v d ( m t ) d . \mathbb{P}\{\delta_j\le\sqrt{m}t\mid(C_\ell)_{\ell\ne j}\}\le(C_{\mathrm{RV}}K)^d v_d(\sqrt{m}t)^d. P { δ j ≤ m t ∣ ( C ℓ ) ℓ = j } ≤ ( C RV K ) d v d ( m t ) d .
Take expectations and sum over j j j . Finally, v d ≤ 2 d v_d\le2^d v d ≤ 2 d , since the unit ball is contained in [ − 1 , 1 ] d [-1,1]^d [ − 1 , 1 ] d . This proves (10) .
Proposition 3.3 (Lower estimate). Under the assumptions of Theorem 1.3 , for every ε > 0 \varepsilon>0 ε > 0 ,
P { M m , r m ( A m ) ≤ exp [ − ( h ( γ ) + ε ) m k m ] } ≤ exp { − ε m + o ( m ) } ⟶ 0. (12) \mathbb{P}\left\{M_{m,r_m}(A_m)\le\exp\left[-(h(\gamma)+\varepsilon)\frac{m}{k_m}\right]\right\}\le\exp\{-\varepsilon m+o(m)\}\longrightarrow0. \tag*{(12)} P { M m , r m ( A m ) ≤ exp [ − ( h ( γ ) + ε ) k m m ] } ≤ exp { − ε m + o ( m )} ⟶ 0. (12)
Proof. There are ( N m m + k m − 1 ) \binom{N_m}{m+k_m-1} ( m + k m − 1 N m ) row submatrices of the required size. By Lemma 3.2 with d = k m d=k_m d = k m , for every t > 0 t>0 t > 0 ,
P { M m , r m ( A m ) ≤ t } ≤ ( N m m + k m − 1 ) m ( D m t ) k m . \mathbb{P}\{M_{m,r_m}(A_m)\le t\}\le\binom{N_m}{m+k_m-1}m(D\sqrt{m}t)^{k_m}. P { M m , r m ( A m ) ≤ t } ≤ ( m + k m − 1 N m ) m ( D m t ) k m .
For t = exp [ − ( h ( γ ) + ε ) m / k m ] t=\exp[-(h(\gamma)+\varepsilon)m/k_m] t = exp [ − ( h ( γ ) + ε ) m / k m ] , the logarithm of the right-hand side is
h ( γ ) m + o ( m ) + log m + k m log D + k m 2 log m − ( h ( γ ) + ε ) m = − ε m + o ( m ) , h(\gamma)m+o(m)+\log m+k_m\log D+\frac{k_m}{2}\log m-(h(\gamma)+\varepsilon)m=-\varepsilon m+o(m), h ( γ ) m + o ( m ) + log m + k m log D + 2 k m log m − ( h ( γ ) + ε ) m = − ε m + o ( m ) ,
using k m log m = o ( m ) k_m\log m=o(m) k m log m = o ( m ) . This proves the claim.
The upper estimate
The upper estimate is substantially more delicate than the lower estimate. Indeed, the lower estimate only requires ruling out the existence of an exceptionally ill-conditioned row submatrix, and therefore follows from a one-matrix small-ball bound combined with a union bound. In the opposite direction, the upper estimate must prove that at least one such submatrix actually exists. Although there are exponentially many candidate row submatrices, they are strongly dependent because different candidates typically share a large number of rows.
A further difficulty is that the Gaussian argument [11 ] uses rotational invariance of the normal vectors. For general i.i.d. entries, those normals need not be Haar distributed. The necessary small-ball estimates must instead hold uniformly, or on average, over an exponentially large family of random hyperplanes, at the exponentially small scale
t = exp ( − Θ ( m k ) ) . t=\exp\left(-\Theta\left(\frac{m}{k}\right)\right). t = exp ( − Θ ( k m ) ) .
Moreover, pairs of candidate normals may be nearly parallel, in which case their small-ball events can be highly correlated. The proof must therefore control not only individual random normals but also the dependence between different candidate hyperplanes.
Proof map for the upper estimate.
For convenience, write
k = k m = r m + 1 , λ = h ( γ ) − ε , t = exp ( − λ m k ) . k=k_m=r_m+1,\qquad\lambda=h(\gamma)-\varepsilon,\qquad t=\exp\left(-\lambda\frac{m}{k}\right). k = k m = r m + 1 , λ = h ( γ ) − ε , t = exp ( − λ k m ) .
Our goal is to prove that, with probability tending to one, there is a set of m + k − 1 = m + r m m+k-1=m+r_m m + k − 1 = m + r m rows whose least singular value is at most t t t .
We begin by choosing k b kb k b rows and call them the marked rows, where b = ⌊ δ m k ⌋ b=\left\lfloor\frac{\delta m}{k}\right\rfloor b = ⌊ k δ m ⌋ , and divide them into k k k disjoint groups of b b b rows each. The remaining
n m : = N m − k b n_m:=N_m-kb n m := N m − k b
rows will be called the base rows. Since k b = δ m + O ( k ) kb=\delta m+O(k) k b = δ m + O ( k ) and k = o ( m ) k=o(m) k = o ( m ) ,
n m m ⟶ β : = γ − δ . \frac{n_m}{m}\longrightarrow\beta:=\gamma-\delta. m n m ⟶ β := γ − δ .
For every set S S S of m − 1 m-1 m − 1 base rows, let u S u_S u S be a unit vector orthogonal to all rows indexed by S S S . The number of such sets is
L = ( n m m − 1 ) = exp { h ( β ) m + o ( m ) } . L=\binom{n_m}{m-1}=\exp\{h(\beta)m+o(m)\}. L = ( m − 1 n m ) = exp { h ( β ) m + o ( m )} .
We choose δ > 0 \delta>0 δ > 0 sufficiently small that h ( β ) > λ h(\beta)>\lambda h ( β ) > λ . The reason for this choice will appear below: the initial number of sets S S S grows like exp { h ( β ) m } \exp\{h(\beta)m\} exp { h ( β ) m } , whereas the k k k conditions imposed later produce a main factor exp ( − λ m ) \exp(-\lambda m) exp ( − λm ) . The strict inequality h ( β ) > λ h(\beta)>\lambda h ( β ) > λ ensures that some sets S S S remain after all k k k conditions have been imposed.
§ 4 establishes the estimates needed to compare the normal vectors u S u_S u S . First, it shows that at least half of them have sufficiently small coordinates. For such a vector u S u_S u S and an independent row X X X , the probability of
∣ ⟨ X , u S ⟩ ∣ ≤ s |\langle X,u_S\rangle|\le s ∣ ⟨ X , u S ⟩ ∣ ≤ s
is bounded above and below by constant multiples of s s s . Geometrically, this inequality means that X X X is close to the hyperplane spanned by the rows indexed by S S S . Second, § 4 shows that only a very small proportion of pairs ( S , T ) (S,T) ( S , T ) have normal vectors u S u_S u S and u T u_T u T that are close to each other, up to a change of sign. For all other pairs, the probability that
∣ ⟨ X , u S ⟩ ∣ ≤ s and ∣ ⟨ X , u T ⟩ ∣ ≤ s |\langle X,u_S\rangle|\le s \quad\text{and}\quad|\langle X,u_T\rangle|\le s ∣ ⟨ X , u S ⟩ ∣ ≤ s and ∣ ⟨ X , u T ⟩ ∣ ≤ s
hold simultaneously is bounded by a constant multiple of s 2 s^2 s 2 . These one-vector and two-vector estimates allow us to control both the number of sets that remain and the dependence between different sets.
We then use the k k k reserved groups one at a time. Set s = t / k s=t/\sqrt{k} s = t / k . In each round j j j , we examine the b b b rows in the j j j -th group and choose one row X j X_j X j . After choosing X j X_j X j , we keep only those sets S S S for which
∣ ⟨ X j , u S ⟩ ∣ ≤ s . |\langle X_j,u_S\rangle|\le s. ∣ ⟨ X j , u S ⟩ ∣ ≤ s .
Lemma 5.3 shows that each independent row has a fixed positive probability of keeping sufficiently many sets S S S while preserving the pairwise estimates needed for the next round. Since each group contains b ≳ m / k b\gtrsim m/k b ≳ m / k independent rows, the probability that no row in a given group works is at most
exp ( − c m k ) . \exp\left(-c\frac{m}{k}\right). exp ( − c k m ) .
Repeating this argument for all k k k groups gives rows X 1 , … , X k X_1,\ldots,X_k X 1 , … , X k and at least one set S S S satisfying
∣ ⟨ X j , u S ⟩ ∣ ≤ s , 1 ≤ j ≤ k . |\langle X_j,u_S\rangle|\le s,\qquad1\le j\le k. ∣ ⟨ X j , u S ⟩ ∣ ≤ s , 1 ≤ j ≤ k .
The fact that at least one set remains follows from h ( β ) > λ h(\beta)>\lambda h ( β ) > λ and k log k = o ( m ) k\log k=o(m) k log k = o ( m ) .
Finally, form a matrix B B B from the m − 1 m-1 m − 1 base rows indexed by S S S and the selected rows X 1 , … , X k X_1,\ldots,X_k X 1 , … , X k . The matrix B B B has
m − 1 + k = m + r m m-1+k=m+r_m m − 1 + k = m + r m
rows. Since the base rows indexed by S S S are orthogonal to u S u_S u S ,
∥ B u S ∥ 2 2 = ∑ j = 1 k ∣ ⟨ X j , u S ⟩ ∣ 2 ≤ k s 2 = t 2 . \lVert Bu_S\rVert_2^2=\sum_{j=1}^{k}|\langle X_j,u_S\rangle|^2\le ks^2=t^2. ∥ B u S ∥ 2 2 = j = 1 ∑ k ∣ ⟨ X j , u S ⟩ ∣ 2 ≤ k s 2 = t 2 .
Because ∥ u S ∥ 2 = 1 \lVert u_S\rVert_2 = 1 ∥ u S ∥ 2 = 1 , the variational characterization of the least singular value gives
σ m ( B ) ≤ ∥ B u S ∥ 2 ≤ t . \sigma_m(B) \le\lVert Bu_S\rVert_2 \le t. σ m ( B ) ≤ ∥ B u S ∥ 2 ≤ t .
Therefore M m , r m ( A m ) ≤ t M_{m,r_m}(A_m) \le t M m , r m ( A m ) ≤ t . The probability that the construction fails is bounded by
C e − c m + k exp ( − c m k ) , Ce^{-cm} + k\exp\left(-c\frac{m}{k}\right), C e − c m + k exp ( − c k m ) ,
which tends to zero under the assumption k log m = o ( m ) k\log m = o(m) k log m = o ( m ) .
Geometry of random hyperplane normals
Because the entry law is absolutely continuous, with probability one every row family of size at most m m m that appears below has the expected rank. We work on this full-probability event and choose each normal measurably, for example by requiring its first nonzero coordinate to be positive.
We use the largest-coordinate estimate [6 Theorem 1.4, equation (6)] . The variables denoted by n n n and m m m in that estimate correspond to m m m and s s s , respectively, in the formulation below.
Theorem 4.1 (Nguyen–Vu). Let B B B be an ( m − 1 ) × m (m-1)\times m ( m − 1 ) × m matrix with i.i.d. entries distributed as ξ \xi ξ , and let u u u be a measurably chosen unit normal to its rows. There are constants C , C 1 > 0 C,C_1>0 C , C 1 > 0 , depending only on the entry law, such that, for all sufficiently large m m m and every s ≥ C 1 log m s\ge C_1\log m s ≥ C 1 log m ,
P { ∥ u ∥ ∞ ≥ s m } ≤ C m 2 e − s / C . (13) \mathbb{P}\left\{\lVert u\rVert_\infty\ge\sqrt{\frac{s}{m}}\right\} \le Cm^2e^{-s/C}. \tag*{(13)} P { ∥ u ∥ ∞ ≥ m s } ≤ C m 2 e − s / C . (13)
Theorem 4.1 provides a delocalization estimate for the unit normal of a single random hyperplane. The following lemma shows that, with high probability, at least half of the hyperplanes generated by the random rows have delocalized normals.
Lemma 4.2 (Many hyperplanes have delocalized normals). Let n = n m ≥ m n=n_m\ge m n = n m ≥ m , let R 1 , … , R n R_1,\ldots,R_n R 1 , … , R n be independent rows with i.i.d. coordinates distributed as ξ \xi ξ , and for every S ⊂ [ n ] S\subset[n] S ⊂ [ n ] with ∣ S ∣ = m − 1 |S|=m-1 ∣ S ∣ = m − 1 let u S u_S u S be a unit normal to the rows indexed by S S S . Put
S : = { S ⊂ [ n ] : ∣ S ∣ = m − 1 } , L : = ∣ S ∣ = ( n m − 1 ) , \mathcal{S}:=\{S\subset[n]: |S|=m-1\}, \qquad L:=|\mathcal{S}|=\binom{n}{m-1}, S := { S ⊂ [ n ] : ∣ S ∣ = m − 1 } , L := ∣ S ∣ = ( m − 1 n ) , and, with η \eta η from Lemma 2.4 , define the set of good hyperplanes
G : = { S ∈ S : ∥ u S ∥ ∞ ≤ η } . \mathcal{G}:=\{S\in\mathcal{S}: \lVert u_S\rVert_\infty\le\eta\}. G := { S ∈ S : ∥ u S ∥ ∞ ≤ η } . Then there are constants C , c > 0 C,c>0 C , c > 0 such that
P { ∣ G ∣ < L / 2 } ≤ C m 2 e − c m (14) \mathbb{P}\{|\mathcal{G}|<L/2\}\le Cm^2e^{-cm} \tag*{(14)} P { ∣ G ∣ < L /2 } ≤ C m 2 e − c m (14) for all sufficiently large m m m .
Proof. Fix S ∈ S S\in\mathcal{S} S ∈ S . The matrix whose rows are indexed by S S S is an ( m − 1 ) × m (m-1)\times m ( m − 1 ) × m random matrix with independent entries distributed as ξ \xi ξ , so Theorem 4.1 applies to u S u_S u S . Let s m : = ⌊ η 2 m ⌋ s_m:=\lfloor\eta^2m\rfloor s m := ⌊ η 2 m ⌋ . For all sufficiently large m m m , one has s m ≥ C 1 log m s_m\ge C_1\log m s m ≥ C 1 log m and s m / m ≤ η \sqrt{s_m/m}\le\eta s m / m ≤ η . Consequently,
{ S ∉ G } = { ∥ u S ∥ ∞ > η } ⊆ { ∥ u S ∥ ∞ ≥ s m m } . \{S\notin\mathcal{G}\}=\{\lVert u_S\rVert_\infty>\eta\}\subseteq\left\{\lVert u_S\rVert_\infty\ge\sqrt{\frac{s_m}{m}}\right\}. { S ∈ / G } = {∥ u S ∥ ∞ > η } ⊆ { ∥ u S ∥ ∞ ≥ m s m } .
Applying Theorem 4.1 gives
P { S ∉ G } ≤ C m 2 e − s m / C . \mathbb{P}\{S \notin\mathcal{G}\} \leq C m^{2} e^{-s_m/C}. P { S ∈ / G } ≤ C m 2 e − s m / C .
For all sufficiently large m m m , s m ≥ η 2 m / 2 s_m \geq\eta^{2}m/2 s m ≥ η 2 m /2 , and hence
P { S ∉ G } ≤ C m 2 e − c m . \mathbb{P}\{S \notin\mathcal{G}\} \leq C m^{2} e^{-c m}. P { S ∈ / G } ≤ C m 2 e − c m .
Let
N b a d : = ∣ S ∖ G ∣ = ∑ S ∈ S 1 { S ∉ G } . N_{\mathrm{bad}} := |\mathcal{S} \setminus\mathcal{G}| = \sum_{S \in\mathcal{S}} 1_{\{S \notin\mathcal{G}\}}. N bad := ∣ S ∖ G ∣ = S ∈ S ∑ 1 { S ∈ / G } .
By linearity of expectation,
E N b a d = ∑ S ∈ S P { S ∉ G } ≤ L C m 2 e − c m . \mathbb{E}N_{\mathrm{bad}} = \sum_{S \in\mathcal{S}} \mathbb{P}\{S \notin\mathcal{G}\} \leq L C m^{2} e^{-c m}. E N bad = S ∈ S ∑ P { S ∈ / G } ≤ L C m 2 e − c m .
Since ∣ G ∣ < L / 2 |\mathcal{G}| < L/2 ∣ G ∣ < L /2 implies N b a d > L / 2 N_{\mathrm{bad}} > L/2 N bad > L /2 , Markov’s inequality yields
P { ∣ G ∣ < L / 2 } ≤ 2 E N b a d L ≤ 2 C m 2 e − c m . \mathbb{P}\{|\mathcal{G}| < L/2\} \leq\frac{2\mathbb{E}N_{\mathrm{bad}}}{L} \leq2 C m^{2} e^{-c m}. P { ∣ G ∣ < L /2 } ≤ L 2 E N bad ≤ 2 C m 2 e − c m .
Absorbing the factor 2 into C C C proves the claim.
We next control the geometry of pairs. The following entropy estimate shows that pairs of row sets with very large overlap form an exponentially negligible fraction.
Lemma 4.3 (Count high-overlap pairs). Suppose n m / m → β > 1 n_m/m \to\beta> 1 n m / m → β > 1 and let
L m : = ( n m m − 1 ) . L_m := \binom{n_m}{m-1}. L m := ( m − 1 n m ) . Then
1 m log L m ⟶ h ( β ) . (15) \frac{1}{m}\log L_m \longrightarrow h(\beta). \tag*{(15)} m 1 log L m ⟶ h ( β ) . (15) Moreover, for every λ < h ( β ) \lambda< h(\beta) λ < h ( β ) there are constants δ 0 , κ > 0 \delta_0,\kappa> 0 δ 0 , κ > 0 such that, for all sufficiently large m m m ,
1 L m ∑ 1 ≤ k ≤ ⌊ δ 0 m ⌋ ( m − 1 k ) ( n m − m + 1 k ) ≤ e − ( λ + 4 κ ) m . (16) \frac{1}{L_m}\sum_{1 \leq k \leq\lfloor\delta_0 m \rfloor}
\binom{m-1}{k}\binom{n_m-m+1}{k}
\leq e^{-(\lambda+4\kappa)m}. \tag*{(16)} L m 1 1 ≤ k ≤ ⌊ δ 0 m ⌋ ∑ ( k m − 1 ) ( k n m − m + 1 ) ≤ e − ( λ + 4 κ ) m . (16)
Proof. Write β m : = n m / m \beta_m := n_m/m β m := n m / m , so β m → β \beta_m \to\beta β m → β . Stirling’s formula gives
1 m log L m = 1 m ( log ( n m ! ) − log ( ( m − 1 ) ! ) − log ( ( n m − m + 1 ) ! ) ) = β m log β m − ( β m − 1 ) log ( β m − 1 ) + o ( 1 ) , \frac{1}{m}\log L_m = \frac{1}{m}\left(\log(n_m!) - \log((m-1)!) - \log((n_m-m+1)!)\right)
= \beta_m \log\beta_m - (\beta_m-1)\log(\beta_m-1) + o(1), m 1 log L m = m 1 ( log ( n m !) − log (( m − 1 )!) − log (( n m − m + 1 )!) ) = β m log β m − ( β m − 1 ) log ( β m − 1 ) + o ( 1 ) ,
which proves (15) .
Fix λ < h ( β ) \lambda< h(\beta) λ < h ( β ) and choose κ > 0 \kappa> 0 κ > 0 so small that λ + 7 κ < h ( β ) \lambda+ 7\kappa< h(\beta) λ + 7 κ < h ( β ) . By (15) , for all sufficiently large m m m ,
L m ≥ e ( h ( β ) − κ ) m . L_m \geq e^{(h(\beta)-\kappa)m}. L m ≥ e ( h ( β ) − κ ) m .
Since n m / m → β n_m/m \to\beta n m / m → β , there is A > 0 A > 0 A > 0 such that n m − m + 1 ≤ A m n_m-m+1 \leq A m n m − m + 1 ≤ A m for all sufficiently large m m m . Using ( p k ) ≤ ( e p / k ) k \binom{p}{k} \leq(ep/k)^k ( k p ) ≤ ( e p / k ) k , we obtain, for 1 ≤ k ≤ δ 0 m 1 \leq k \leq\delta_0m 1 ≤ k ≤ δ 0 m and x : = k / m x := k/m x := k / m ,
1 m log [ ( m − 1 k ) ( n m − m + 1 k ) ] ≤ x log ( A e 2 x 2 ) . (17) \frac{1}{m}\log\left[\binom{m-1}{k}\binom{n_m-m+1}{k}\right] \leq x\log\left(\frac{A e^{2}}{x^{2}}\right). \tag*{(17)} m 1 log [ ( k m − 1 ) ( k n m − m + 1 ) ] ≤ x log ( x 2 A e 2 ) . (17)
The right-hand side tends to zero as x ↓ 0 x \downarrow0 x ↓ 0 . Choose δ 0 > 0 \delta_0 > 0 δ 0 > 0 sufficiently small that δ 0 < 1 2 min { 1 , β − 1 } \delta_0 < \frac{1}{2}\min\{1,\beta-1\} δ 0 < 2 1 min { 1 , β − 1 } and
x log ( A e 2 x 2 ) ≤ κ 2 ( 0 < x ≤ δ 0 ) . x\log\left(\frac{Ae^2}{x^2}\right) \le\frac{\kappa}{2} \qquad(0 < x \le\delta_0). x log ( x 2 A e 2 ) ≤ 2 κ ( 0 < x ≤ δ 0 ) .
Then every summand in (16) is at most e κ m / 2 e^{\kappa m/2} e κm /2 , and the sum contains at most m m m terms. Hence, for all sufficiently large m m m ,
∑ 1 ≤ k ≤ ⌊ δ 0 m ⌋ ( m − 1 k ) ( n m − m + 1 k ) ≤ m e κ m / 2 ≤ e κ m . \sum_{1\le k\le\lfloor\delta_0m\rfloor}\binom{m-1}{k}\binom{n_m-m+1}{k}\le me^{\kappa m/2}\le e^{\kappa m}. 1 ≤ k ≤ ⌊ δ 0 m ⌋ ∑ ( k m − 1 ) ( k n m − m + 1 ) ≤ m e κm /2 ≤ e κm .
Dividing by the lower bound for L m L_m L m gives
1 L m ∑ 1 ≤ k ≤ ⌊ δ 0 m ⌋ ( m − 1 k ) ( n m − m + 1 k ) ≤ e − ( h ( β ) − 2 κ ) m . \frac{1}{L_m}\sum_{1\le k\le\lfloor\delta_0m\rfloor}\binom{m-1}{k}\binom{n_m-m+1}{k}\le e^{-(h(\beta)-2\kappa)m}. L m 1 1 ≤ k ≤ ⌊ δ 0 m ⌋ ∑ ( k m − 1 ) ( k n m − m + 1 ) ≤ e − ( h ( β ) − 2 κ ) m .
Since h ( β ) − 2 κ > λ + 4 κ h(\beta)-2\kappa>\lambda+4\kappa h ( β ) − 2 κ > λ + 4 κ , this proves (16) .
Lemma 4.3 shows that pairs ( S , T ) (S,T) ( S , T ) with very large overlap, equivalently with ∣ T ∖ S ∣ |T\setminus S| ∣ T ∖ S ∣ small, form only a very small proportion of all pairs. It remains to consider pairs for which T ∖ S T\setminus S T ∖ S contains at least δ 0 m \delta_0m δ 0 m rows. Fix such a pair and condition on the rows indexed by S S S . Then u S u_S u S is fixed, while the rows indexed by T ∖ S T\setminus S T ∖ S remain independent. If u T u_T u T is close to u S u_S u S up to a change of sign, then, because the rows indexed by T T T are orthogonal to u T u_T u T , the rows in T ∖ S T\setminus S T ∖ S must have small inner products with u S u_S u S , unless the matrix formed by these rows has an unusually large operator norm. The following Lemma 4.4 rules out the latter possibility with exponentially high probability. Then Lemma 4.5 combines this operator-norm bound with the bounded-density estimate for the projections of the rows indexed by T ∖ S T\setminus S T ∖ S onto u S u_S u S , showing that only an exponentially small proportion of the remaining pairs can have close normal vectors.
Lemma 4.4 (Operator-norm tail). For every H > 0 H>0 H > 0 there is a constant R = R ( H , ξ ) > 0 R=R(H,\xi)>0 R = R ( H , ξ ) > 0 such that, for every 1 ≤ q ≤ m 1\le q\le m 1 ≤ q ≤ m and every q × m q\times m q × m matrix B B B with i.i.d. entries distributed as ξ \xi ξ ,
P { ∥ B ∥ o p > R m } ≤ e − H m . (18) \mathbb{P}\{\|B\|_{\mathrm{op}}>R\sqrt{m}\}\le e^{-Hm}. \tag*{(18)} P { ∥ B ∥ op > R m } ≤ e − H m . (18)
Proof. The subgaussian operator-norm estimate [13 Theorem 4.4.5] gives a constant C ξ C_\xi C ξ such that
P { ∥ B ∥ o p > C ξ ( q + m + u ) } ≤ 2 e − u 2 , u ≥ 0. \mathbb{P}\{\|B\|_{\mathrm{op}}>C_\xi(\sqrt{q}+\sqrt{m}+u)\}\le2e^{-u^2}, \qquad u\ge0. P { ∥ B ∥ op > C ξ ( q + m + u )} ≤ 2 e − u 2 , u ≥ 0.
Take u = H + 1 m u=\sqrt{H}+1\sqrt{m} u = H + 1 m . Since q ≤ m q\le m q ≤ m , one may choose R = C ξ ( 2 + H + 1 ) R=C_\xi(2+\sqrt{H}+1) R = C ξ ( 2 + H + 1 ) , and 2 e − ( H + 1 ) m ≤ e − H m 2e^{-(H+1)m}\le e^{-Hm} 2 e − ( H + 1 ) m ≤ e − H m for m ≥ 1 m\ge1 m ≥ 1 .
:::
Lemma 4.5 (Few nearly parallel pairs). Suppose n m / m → β > 1 n_m/m\to\beta>1 n m / m → β > 1 . With the notation above, fix λ < h ( β ) \lambda<h(\beta) λ < h ( β ) . There are constants δ 0 , a , κ , c ∗ > 0 \delta_0,a,\kappa,c_*>0 δ 0 , a , κ , c ∗ > 0 such that, with probability at least 1 − e − c ∗ m 1-e^{-c_*m} 1 − e − c ∗ m for all sufficiently large m m m , the number of ordered distinct pairs ( S , T ) ∈ S 2 (S,T)\in\mathcal{S}^2 ( S , T ) ∈ S 2 satisfying at least one of
∣ T ∖ S ∣ ≤ δ 0 m , or d p r ( u S , u T ) < a , (19) |T\setminus S|\le\delta_0m, \qquad\text{or} \qquad d_{\mathrm{pr}}(u_S,u_T)<a, \tag*{(19)} ∣ T ∖ S ∣ ≤ δ 0 m , or d pr ( u S , u T ) < a , (19) is at most
2 L m 2 e − ( λ + 4 κ ) m . 2L_m^2e^{-(\lambda+4\kappa)m}. 2 L m 2 e − ( λ + 4 κ ) m .
Proof. Fix λ < h ( β ) \lambda< h(\beta) λ < h ( β ) and choose δ 0 , κ > 0 \delta_0, \kappa> 0 δ 0 , κ > 0 from Lemma 4.3. For each fixed S ∈ S S \in\mathcal{S} S ∈ S , the number of T ∈ S T \in\mathcal{S} T ∈ S with ∣ T ∖ S ∣ = q |T \setminus S| = q ∣ T ∖ S ∣ = q is ( m − 1 q ) ( n m − m + 1 q ) \binom{m-1}{q}\binom{n_m-m+1}{q} ( q m − 1 ) ( q n m − m + 1 ) . Hence the number of ordered distinct pairs with ∣ T ∖ S ∣ ≤ δ 0 m |T \setminus S| \le\delta_0m ∣ T ∖ S ∣ ≤ δ 0 m is at most
L m 2 e − ( λ + 4 κ ) m . L_m^2 e^{-(\lambda+4\kappa)m}. L m 2 e − ( λ + 4 κ ) m .
This estimate is deterministic.
Choose H > max { 0 , λ + 4 κ } + 2 H > \max\{0,\lambda+4\kappa\}+2 H > max { 0 , λ + 4 κ } + 2 , and then choose R = R ( H , ξ ) R=R(H,\xi) R = R ( H , ξ ) from Lemma 4.4 . Fix an ordered pair ( S , T ) (S,T) ( S , T ) with q : = ∣ T ∖ S ∣ > δ 0 m q := |T \setminus S| > \delta_0m q := ∣ T ∖ S ∣ > δ 0 m , and condition on the rows indexed by S S S . Put u = u S u=u_S u = u S and J = T ∖ S J=T \setminus S J = T ∖ S , and let B J B_J B J have the rows indexed by J J J . These q q q rows are independent of the conditioning and of one another.
If d p r ( u S , u T ) < a d_{\mathrm{pr}}(u_S,u_T)<a d pr ( u S , u T ) < a , choose v ∈ { u T , − u T } v \in\{u_T,-u_T\} v ∈ { u T , − u T } with ∥ u − v ∥ 2 < a \|u-v\|_2<a ∥ u − v ∥ 2 < a . Since B J v = 0 B_Jv=0 B J v = 0 , on { ∥ B J ∥ o p ≤ R m } \{\|B_J\|_{\mathrm{op}}\le R\sqrt{m}\} { ∥ B J ∥ op ≤ R m } one has
∥ B J u ∥ 2 = ∥ B J ( u − v ) ∥ 2 < R a m . \|B_Ju\|_2=\|B_J(u-v)\|_2<Ra\sqrt{m}. ∥ B J u ∥ 2 = ∥ B J ( u − v ) ∥ 2 < R a m .
With τ a : = R a 2 / δ 0 \tau_a:=Ra\sqrt{2/\delta_0} τ a := R a 2/ δ 0 , this implies
# { i ∈ J : ∣ ⟨ R i , u ⟩ ∣ ≤ τ a } ≥ q / 2. \#\{i\in J:|\langle R_i,u\rangle|\le\tau_a\}\ge q/2. # { i ∈ J : ∣ ⟨ R i , u ⟩ ∣ ≤ τ a } ≥ q /2.
Otherwise more than q / 2 q/2 q /2 terms in ∥ B J u ∥ 2 2 \|B_Ju\|_2^2 ∥ B J u ∥ 2 2 would exceed τ a 2 \tau_a^2 τ a 2 , contradicting q > δ 0 m q>\delta_0m q > δ 0 m and ∥ B J u ∥ 2 2 < R 2 a 2 m \|B_Ju\|_2^2<R^2a^2m ∥ B J u ∥ 2 2 < R 2 a 2 m .
By Lemma 2.2, each of these small-ball events has conditional probability at most p a : = 2 2 K τ a p_a:=2\sqrt{2}K\tau_a p a := 2 2 K τ a . Choose a > 0 a>0 a > 0 sufficiently small that p a ≤ 1 p_a\le1 p a ≤ 1 and 2 p a ≤ exp [ − ( H + 1 ) / δ 0 ] 2\sqrt{p_a}\le\exp[-(H+1)/\delta_0] 2 p a ≤ exp [ − ( H + 1 ) / δ 0 ] . Conditional independence and a union bound over subsets of rows give
P { # { i ∈ J : ∣ ⟨ R i , u ⟩ ∣ ≤ τ a } ≥ q / 2 ∣ ( R i ) i ∈ S } ≤ 2 q p a q / 2 ≤ e − ( H + 1 ) m . \mathbb{P}\left\{\#\{i\in J:|\langle R_i,u\rangle|\le\tau_a\}\ge q/2\mid(R_i)_{i\in S}\right\}\le2^q p_a^{q/2}\le e^{-(H+1)m}. P { # { i ∈ J : ∣ ⟨ R i , u ⟩ ∣ ≤ τ a } ≥ q /2 ∣ ( R i ) i ∈ S } ≤ 2 q p a q /2 ≤ e − ( H + 1 ) m .
Since q ≤ m − 1 q\le m-1 q ≤ m − 1 , Lemma 4.4 applies to B J B_J B J . Thus, uniformly for these ordered pairs,
P { d p r ( u S , u T ) < a } ≤ 2 e − H m . \mathbb{P}\{d_{\mathrm{pr}}(u_S,u_T)<a\}\le2e^{-Hm}. P { d pr ( u S , u T ) < a } ≤ 2 e − H m .
Let F m F_m F m count such low-overlap pairs with d p r ( u S , u T ) < a d_{\mathrm{pr}}(u_S,u_T)<a d pr ( u S , u T ) < a . Then E F m ≤ 2 L m 2 e − H m \mathbb{E}F_m\le2L_m^2e^{-Hm} E F m ≤ 2 L m 2 e − H m , so Markov’s inequality yields
P { F m > L m 2 e − ( λ + 4 κ ) m } ≤ 2 e − ( H − λ − 4 κ ) m ≤ e − c ∗ m \mathbb{P}\{F_m>L_m^2e^{-(\lambda+4\kappa)m}\}\le2e^{-(H-\lambda-4\kappa)m}\le e^{-c_*m} P { F m > L m 2 e − ( λ + 4 κ ) m } ≤ 2 e − ( H − λ − 4 κ ) m ≤ e − c ∗ m
for all sufficiently large m m m , with c ∗ = ( H − λ − 4 κ ) / 2 > 0 c_*=(H-\lambda-4\kappa)/2>0 c ∗ = ( H − λ − 4 κ ) /2 > 0 . Combining this with the deterministic high-overlap count proves the lemma. □
The upper estimate also relies on estimation of some small ball probabilities. The following two corollaries give the results in the subgaussian setting.
Corollary 4.6 (One-slab estimate for marked rows). Let X 1 , … , X k ∈ R m X_1,\ldots,X_k\in\mathbb{R}^m X 1 , … , X k ∈ R m be independent rows with i.i.d. coordinates distributed as ξ \xi ξ , and let the unit vectors below be deterministic. Define the following small ball probability
p u , k ( t ) : = P { ∑ j = 1 k ∣ ⟨ X j , u ⟩ ∣ 2 ≤ t 2 } . p_{u,k}(t):=\mathbb{P}\left\{\sum_{j=1}^{k}|\langle X_j,u\rangle|^2\le t^2\right\}. p u , k ( t ) := P { j = 1 ∑ k ∣ ⟨ X j , u ⟩ ∣ 2 ≤ t 2 } .
There are constants c 1 , C 1 > 0 c_1,C_1>0 c 1 , C 1 > 0 such that for every k ≥ 1 k\ge1 k ≥ 1 , every 0 < t ≤ 1 0<t\le1 0 < t ≤ 1 , and every unit vector u u u with ∥ u ∥ ∞ ≤ η \|u\|_\infty\le\eta ∥ u ∥ ∞ ≤ η ,
c 1 k v q t k ≤ p u , k ( t ) ≤ C 1 k v q t k , (20) c_1^k v_q t^k\le p_{u,k}(t)\le C_1^k v_q t^k, \tag*{(20)} c 1 k v q t k ≤ p u , k ( t ) ≤ C 1 k v q t k , (20)
where v q v_q v q is the volume of the Euclidean unit ball in R q \mathbb{R}^q R q .
Proof. By Lemma 2.4 and independence, the joint density of ( ⟨ X 1 , u ⟩ , … , ⟨ X k , u ⟩ ) (\langle X_1,u\rangle,\ldots,\langle X_k,u\rangle) (⟨ X 1 , u ⟩ , … , ⟨ X k , u ⟩) is at least c 0 k c_0^k c 0 k on the unit ball in R k \mathbb{R}^k R k , integration over the ball of radius t t t gives the lower bound. The upper bound follows similarly from (6) .
Corollary 4.7 (Two-slab estimate for marked rows). Let X 1 , … , X k ∈ R m X_1,\ldots,X_k\in\mathbb{R}^m X 1 , … , X k ∈ R m be independent rows with i.i.d. coordinates distributed as ξ \xi ξ , and let the unit vectors below be deterministic. Define
q u , v , k ( t ) : = P { ∑ j = 1 k ∣ ⟨ X j , u ⟩ ∣ 2 ≤ t 2 , ∑ j = 1 k ∣ ⟨ X j , v ⟩ ∣ 2 ≤ t 2 } q_{u,v,k}(t):=\mathbb{P}\left\{\sum_{j=1}^{k}\lvert\langle X_j,u\rangle\rvert^2\le t^2,\sum_{j=1}^{k}\lvert\langle X_j,v\rangle\rvert^2\le t^2\right\} q u , v , k ( t ) := P { j = 1 ∑ k ∣⟨ X j , u ⟩ ∣ 2 ≤ t 2 , j = 1 ∑ k ∣⟨ X j , v ⟩ ∣ 2 ≤ t 2 } For arbitrary unit vectors u , v u,v u , v with ∥ u ∥ ∞ , ∥ v ∥ ∞ ≤ η \lVert u\rVert_\infty,\lVert v\rVert_\infty\le\eta ∥ u ∥ ∞ , ∥ v ∥ ∞ ≤ η , and any 0 < t ≤ 1 0<t\le1 0 < t ≤ 1 ,
q u , v , k ( t ) ≤ C 1 k v k t k . (21) q_{u,v,k}(t)\le C_1^k v_k t^k. \tag*{(21)} q u , v , k ( t ) ≤ C 1 k v k t k . (21) Furthermore, assume the above u , v u,v u , v also satisfies d p r ( u , v ) ≥ a > 0 d_{\mathrm{pr}}(u,v)\ge a>0 d pr ( u , v ) ≥ a > 0 , then
q u , v , k ( t ) ≤ C a k v k 2 t 2 k . (22) q_{u,v,k}(t)\le C_a^k v_k^2t^{2k}. \tag*{(22)} q u , v , k ( t ) ≤ C a k v k 2 t 2 k . (22) where C a C_a C a is a constant which only depends on a , C R V , K a,C_{\mathrm{RV}},K a , C RV , K .
Proof. The crude bound (21) follows by discarding one event and the right-hand side of (20) . For the sharper bound, note that if ρ = ∣ ⟨ u , v ⟩ ∣ \rho=\lvert\langle u,v\rangle\rvert ρ = ∣⟨ u , v ⟩∣ , then
d p r 2 ( u , v ) = 2 ( 1 − ρ ) d_{\mathrm{pr}}^2(u,v)=2(1-\rho) d pr 2 ( u , v ) = 2 ( 1 − ρ )
Hence if d p r ( u , v ) ≥ a d_{\mathrm{pr}}(u,v)\ge a d pr ( u , v ) ≥ a , then
1 − ρ 2 = ( 1 − ρ ) ( 1 + ρ ) ≥ 1 − ρ ≥ a 2 / 2 1-\rho^2=(1-\rho)(1+\rho)\ge1-\rho\ge a^2/2 1 − ρ 2 = ( 1 − ρ ) ( 1 + ρ ) ≥ 1 − ρ ≥ a 2 /2
Thus, by (7) , we have for every j j j ,
∥ dens ( ⟨ X j , u ⟩ , ⟨ X j , v ⟩ ) ∥ ∞ ≤ C R V 2 K 2 1 − ρ 2 ≤ 2 C R V 2 K 2 a = : C a \left\lVert\operatorname{dens}(\langle X_j,u\rangle,\langle X_j,v\rangle)\right\rVert_\infty
\le\frac{C_{\mathrm{RV}}^2K^2}{\sqrt{1-\rho^2}}
\le\frac{\sqrt{2}C_{\mathrm{RV}}^2K^2}{a}
=:C_a ∥ dens (⟨ X j , u ⟩ , ⟨ X j , v ⟩) ∥ ∞ ≤ 1 − ρ 2 C RV 2 K 2 ≤ a 2 C RV 2 K 2 =: C a
Thus similarly a integration over ball of radius t t t gives the desired result.
Sequential marked rows and the upper estimate
We now prove the upper estimate. As in the usual marked-row construction, an ( m − 1 ) (m-1) ( m − 1 ) -tuple of base rows determines a candidate hyperplane, and one seeks marked rows that are almost orthogonal to its normal. The difference is that the k k k marked constraints are imposed one at a time. A one-row second-moment estimate has a success probability bounded away from zero, and the candidate family is then restricted successively using k k k independent groups of reserved rows.
Proof map.
Reserve k b ≍ m kb \asymp m k b ≍ m rows and split them into k k k groups of size b ≍ m / k b \asymp m/k b ≍ m / k . The remaining rows generate exponentially many candidate hyperplanes. After selecting j j j marked rows, retain those candidates whose normal has scalar product at most s = t / k s = t/\sqrt{k} s = t / k with each selected row. Lemma 5.3 shows that a fresh row has a fixed positive probability of retaining a proportion at least c 1 s c_1s c 1 s of the current candidates while leaving at most A 0 s A_0s A 0 s times the current number of exceptional pairs. Lemma 5.4 verifies that the required bounds persist through all k k k stages. Independence within each reserved group then gives a suitable row with probability at least 1 − e − c b 1-e^{-c b} 1 − e − c b .
Sequential filtering of candidate hyperplanes
Let b 1 , … , b n ∈ R m b_1,\ldots,b_n \in\mathbb{R}^m b 1 , … , b n ∈ R m be the base rows, and let x 1 , … , x k ∈ R m x_1,\ldots,x_k \in\mathbb{R}^m x 1 , … , x k ∈ R m be distinct marked rows chosen outside this base family. In the probabilistic construction below, these marked rows will be selected from k k k disjoint reserved groups; the other reserved rows are not part of the base family. Set
S : = { S ⊂ [ n ] : ∣ S ∣ = m − 1 } , \mathcal{S} := \{S \subset[n] : |S| = m-1\}, S := { S ⊂ [ n ] : ∣ S ∣ = m − 1 } ,
and let u S u_S u S be a unit normal to the base rows indexed by S S S . For I ⊂ S \mathcal{I} \subset\mathcal{S} I ⊂ S , x ∈ R m x \in\mathbb{R}^m x ∈ R m , and s > 0 s > 0 s > 0 , define
I ( x ; s ) : = { S ∈ I : ∣ ⟨ x , u S ⟩ ∣ ≤ s } . (23) \mathcal{I}(x;s) := \{S \in\mathcal{I} : |\langle x,u_S\rangle| \le s\}. \tag*{(23)} I ( x ; s ) := { S ∈ I : ∣ ⟨ x , u S ⟩ ∣ ≤ s } . (23)
Starting from I 0 : = I \mathcal{I}_0 := \mathcal{I} I 0 := I , define
I j : = I j − 1 ( x j ; s ) , 1 ≤ j ≤ k . (24) \mathcal{I}_j := \mathcal{I}_{j-1}(x_j;s), \qquad1 \le j \le k. \tag*{(24)} I j := I j − 1 ( x j ; s ) , 1 ≤ j ≤ k . (24)
Hence at the last iteration, if I k \mathcal{I}_k I k is nonempty, there is a set S ∗ S^* S ∗ , such that for every j = 1 , 2 , … , k j=1,2,\ldots,k j = 1 , 2 , … , k , ∣ ⟨ x j , u S ∗ ⟩ ∣ ≤ s |\langle x_j,u_{S^*}\rangle| \le s ∣ ⟨ x j , u S ∗ ⟩ ∣ ≤ s .
Lemma 5.1 (Sequential marked rows imply a bad submatrix). Let x 1 , … , x k x_1,\ldots,x_k x 1 , … , x k be the k k k marked rows, let t > 0 t>0 t > 0 , and set s = t / k s=t/\sqrt{k} s = t / k . If the family I k \mathcal{I}_k I k in (24) is nonempty, then the union of the m − 1 m-1 m − 1 base rows indexed by S ∗ S^* S ∗ and the k k k marked rows consists of an ( m + k − 1 ) × m (m+k-1)\times m ( m + k − 1 ) × m row submatrix B B B satisfying σ m ( B ) ≤ t \sigma_m(B)\le t σ m ( B ) ≤ t and thus
M m , k − 1 ( A m ) ≤ t . M_{m,k-1}(A_m) \le t. M m , k − 1 ( A m ) ≤ t .
Proof. Since the base rows are orthogonal to u S ∗ u_{S^*} u S ∗ and
∣ ⟨ x j , u S ∗ ⟩ ∣ ≤ s , 1 ≤ j ≤ k . |\langle x_j,u_{S^*}\rangle| \le s, \qquad1 \le j \le k. ∣ ⟨ x j , u S ∗ ⟩ ∣ ≤ s , 1 ≤ j ≤ k .
We have
∥ B u S ∗ ∥ 2 2 = ∑ i ∈ S ∗ ∣ ⟨ b i , u S ∗ ⟩ ∣ 2 + ∑ j = 1 k ∣ ⟨ x j , u S ∗ ⟩ ∣ 2 ≤ k s 2 = t 2 . \|Bu_{S^*}\|_2^2 = \sum_{i\in S^*} |\langle b_i,u_{S^*}\rangle|^2 + \sum_{j=1}^{k} |\langle x_j,u_{S^*}\rangle|^2 \le ks^2 = t^2. ∥ B u S ∗ ∥ 2 2 = i ∈ S ∗ ∑ ∣ ⟨ b i , u S ∗ ⟩ ∣ 2 + j = 1 ∑ k ∣ ⟨ x j , u S ∗ ⟩ ∣ 2 ≤ k s 2 = t 2 .
The variational characterization of the least singular value yields σ m ( B ) ≤ t \sigma_m(B) \le t σ m ( B ) ≤ t and thus M m , k − 1 ( A m ) ≤ t M_{m,k-1}(A_m) \le t M m , k − 1 ( A m ) ≤ t .
Lemma 5.2 (Paley–Zygmund inequality). For every nonnegative random variable Z Z Z with 0 < E Z 2 < ∞ 0 < \mathbb{E}Z^2 < \infty 0 < E Z 2 < ∞ and every ρ ∈ ( 0 , 1 ) \rho\in(0,1) ρ ∈ ( 0 , 1 ) ,
P { Z ≥ ρ E Z } ≥ ( 1 − ρ ) 2 ( E Z ) 2 E Z 2 . \mathbb{P}\{Z \ge\rho\mathbb{E}Z\} \ge(1-\rho)^2 \frac{(\mathbb{E}Z)^2}{\mathbb{E}Z^2}. P { Z ≥ ρ E Z } ≥ ( 1 − ρ ) 2 E Z 2 ( E Z ) 2 .
Lemma 5.3 (One marked-row stage). Let F ⊂ S \mathcal{F} \subset\mathcal{S} F ⊂ S be finite, with ∥ u S ∥ ∞ ≤ η \|u_S\|_\infty\le\eta ∥ u S ∥ ∞ ≤ η for every S ∈ F S \in\mathcal{F} S ∈ F .
Let
E ⊂ { ( S , T ) ∈ F 2 : S ≠ T } \mathcal{E} \subset\{(S,T) \in\mathcal{F}^2:S \ne T\} E ⊂ {( S , T ) ∈ F 2 : S = T } contain every distinct pair for which d p r ( u S , u T ) < a d_{\mathrm{pr}}(u_S,u_T)<a d pr ( u S , u T ) < a . Write M = ∣ F ∣ M=|\mathcal{F}| M = ∣ F ∣ , and assume
s M ≥ 1 , ∣ E ∣ ≤ s M 2 , 0 < s ≤ 1. (25) sM \ge1,\qquad|\mathcal{E}| \le sM^2,\qquad0<s\le1. \tag*{(25)} s M ≥ 1 , ∣ E ∣ ≤ s M 2 , 0 < s ≤ 1. (25) Let X X X have i.i.d. coordinates distributed as ξ \xi ξ , independently of the family and its normals. Define
Z ( X ) : = ∑ S ∈ F 1 { ∣ ⟨ X , u S ⟩ ∣ ≤ s } , W ( X ) : = ∑ ( S , T ) ∈ E 1 { ∣ ⟨ X , u S ⟩ ∣ ≤ s , ∣ ⟨ X , u T ⟩ ∣ ≤ s } . Z(X):=\sum_{S\in\mathcal{F}}\mathbf{1}_{\{|\langle X,u_S\rangle|\le s\}},\qquad
W(X):=\sum_{(S,T)\in\mathcal{E}}\mathbf{1}_{\{|\langle X,u_S\rangle|\le s,\ |\langle X,u_T\rangle|\le s\}}. Z ( X ) := S ∈ F ∑ 1 { ∣ ⟨ X , u S ⟩ ∣ ≤ s } , W ( X ) := ( S , T ) ∈ E ∑ 1 { ∣ ⟨ X , u S ⟩ ∣ ≤ s , ∣ ⟨ X , u T ⟩ ∣ ≤ s } . There are constants c 1 ∈ ( 0 , 1 ) c_1\in(0,1) c 1 ∈ ( 0 , 1 ) , p 0 > 0 p_0>0 p 0 > 0 , and A 0 > 1 A_0>1 A 0 > 1 , depending only on a a a and the law of ξ \xi ξ , such that, conditionally on the family and its normals,
P { Z ( X ) ≥ c 1 s M , W ( X ) ≤ A 0 s ∣ E ∣ } ≥ p 0 . \mathbb{P}\{Z(X)\ge c_1sM,\ W(X)\le A_0s|\mathcal{E}|\}\ge p_0. P { Z ( X ) ≥ c 1 s M , W ( X ) ≤ A 0 s ∣ E ∣ } ≥ p 0 . Proof. Condition on the family and its normals. The one-row cases of Corollaries 4.6 and 4.7 give
E Z ≥ c s M , E Z 2 ≤ C s M + C a s 2 M 2 + C s ∣ E ∣ ≤ C ′ s 2 M 2 . \mathbb{E}Z\ge csM,\qquad
\mathbb{E}Z^2\le CsM+C_as^2M^2+Cs|\mathcal{E}|\le C's^2M^2. E Z ≥ cs M , E Z 2 ≤ C s M + C a s 2 M 2 + C s ∣ E ∣ ≤ C ′ s 2 M 2 . The three terms in the second-moment estimate correspond to diagonal pairs, distinct pairs outside E \mathcal{E} E , and pairs in E \mathcal{E} E . The final inequality uses (25) . Paley–Zygmund therefore gives
P { Z ≥ 1 2 E Z } ≥ c 2 4 C ′ = : p 1 > 0. \mathbb{P}\{Z\ge\tfrac{1}{2}\mathbb{E}Z\}\ge\frac{c^2}{4C'}=:p_1>0. P { Z ≥ 2 1 E Z } ≥ 4 C ′ c 2 =: p 1 > 0. Choose c 1 = min { c / 2 , 1 / 2 } c_1=\min\{c/2,1/2\} c 1 = min { c /2 , 1/2 } . Then P { Z ≥ c 1 s M } ≥ p 1 \mathbb{P}\{Z\ge c_1sM\}\ge p_1 P { Z ≥ c 1 s M } ≥ p 1 .
The crude one-vector bound gives E W ≤ C s ∣ E ∣ \mathbb{E}W\le Cs|\mathcal{E}| E W ≤ C s ∣ E ∣ . If E = ∅ \mathcal{E}=\varnothing E = ∅ , then W = 0 W=0 W = 0 identically. Otherwise Markov’s inequality, with A 0 > 1 A_0>1 A 0 > 1 chosen so that C / A 0 ≤ p 1 / 2 C/A_0\le p_1/2 C / A 0 ≤ p 1 /2 , gives
P { W > A 0 s ∣ E ∣ } ≤ p 1 / 2. \mathbb{P}\{W>A_0s|\mathcal{E}|\}\le p_1/2. P { W > A 0 s ∣ E ∣ } ≤ p 1 /2. In either case the simultaneous event has probability at least p 0 : = p 1 / 2 p_0:=p_1/2 p 0 := p 1 /2 .
Iteration estimates
Fix ε ∈ ( 0 , h ( γ ) ) \varepsilon\in(0,h(\gamma)) ε ∈ ( 0 , h ( γ )) and, throughout the remainder of the section, write
k : = k m , λ : = h ( γ ) − ε , t : = exp ( − λ m k ) , s : = t k . (26) k:=k_m,\qquad\lambda:=h(\gamma)-\varepsilon,\qquad
t:=\exp\left(-\lambda\frac{m}{k}\right),\qquad
s:=\frac{t}{\sqrt{k}}. \tag*{(26)} k := k m , λ := h ( γ ) − ε , t := exp ( − λ k m ) , s := k t . (26)
Since h ( ⋅ ) h(\cdot) h ( ⋅ ) is increasing, we can choose a small enough δ ∈ ( 0 , γ − 1 ) \delta\in(0,\gamma-1) δ ∈ ( 0 , γ − 1 ) such that, with β : = γ − δ \beta:=\gamma-\delta β := γ − δ ,
Δ : = h ( β ) − λ = h ( γ − δ ) − h ( γ ) + ε > 0. (27) \Delta:=h(\beta)-\lambda=h(\gamma-\delta)-h(\gamma)+\varepsilon>0. \tag*{(27)} Δ := h ( β ) − λ = h ( γ − δ ) − h ( γ ) + ε > 0. (27)
Now set b : = ⌊ δ m k ⌋ b:=\left\lfloor\frac{\delta m}{k}\right\rfloor b := ⌊ k δ m ⌋ and choose k b kb k b rows and split them into k k k disjoint groups { R 1 , … , R k } \{\mathcal{R}_1,\ldots,\mathcal{R}_k\} { R 1 , … , R k } , where
R j = { Y j , 1 , … , Y j , b } , 1 ≤ j ≤ k . \mathcal{R}_j=\{Y_{j,1},\ldots,Y_{j,b}\},\qquad1\le j\le k. R j = { Y j , 1 , … , Y j , b } , 1 ≤ j ≤ k .
The remaining n : = N m − k b n:=N_m-kb n := N m − k b rows are the base rows. Since k b = δ m + O ( k ) kb=\delta m+O(k) k b = δ m + O ( k ) and k = o ( m ) k=o(m) k = o ( m ) , one has n / m → β > 1 n/m\to\beta>1 n / m → β > 1 .
Now let
S = { S ⊂ [ n ] : ∣ S ∣ = m − 1 } , L : = ∣ S ∣ = ( n m − 1 ) . \mathcal{S}=\{S\subset[n]:|S|=m-1\},\qquad L:=|\mathcal{S}|=\binom{n}{m-1}. S = { S ⊂ [ n ] : ∣ S ∣ = m − 1 } , L := ∣ S ∣ = ( m − 1 n ) .
Since λ < h ( β ) \lambda<h(\beta) λ < h ( β ) , Lemma 4.2 and Lemma 4.5 implies there are constants a , κ , c > 0 a,\kappa,c>0 a , κ , c > 0 and a event Ω b a s e \Omega_{\mathrm{base}} Ω base such that
P ( Ω b a s e c ) ≤ C e − c m , (28) \mathbb{P}(\Omega_{\mathrm{base}}^{c})\le Ce^{-cm}, \tag*{(28)} P ( Ω base c ) ≤ C e − c m , (28)
and, on Ω b a s e \Omega_{\mathrm{base}} Ω base , there is a subset G ⊂ S \mathcal{G}\subset\mathcal{S} G ⊂ S and a set of ordered distinct pairs
E = { ( S , T ) ∈ G 2 : S ≠ T , ∣ T ∖ S ∣ ≤ δ 0 m or d p r ( u S , u T ) < a } \mathcal{E}=\{(S,T)\in\mathcal{G}^{2}:S\ne T,\ |T\setminus S|\le\delta_{0}m\text{ or }d_{\mathrm{pr}}(u_{S},u_{T})<a\} E = {( S , T ) ∈ G 2 : S = T , ∣ T ∖ S ∣ ≤ δ 0 m or d pr ( u S , u T ) < a }
satisfying
∣ G ∣ ≥ L 2 , ∣ E ∣ ≤ 2 L 2 e − ( λ + 4 κ ) m , (29) |\mathcal{G}|\ge\frac{L}{2},\qquad|\mathcal{E}|\le2L^{2}e^{-(\lambda+4\kappa)m}, \tag*{(29)} ∣ G ∣ ≥ 2 L , ∣ E ∣ ≤ 2 L 2 e − ( λ + 4 κ ) m , (29)
while every distinct pair outside E \mathcal{E} E has projective distance d p r ( u S , u T ) d_{\mathrm{pr}}(u_{S},u_{T}) d pr ( u S , u T ) at least a a a .
Starting from I 0 : = G \mathcal{I}_{0}:=\mathcal{G} I 0 := G , suppose marked row x j x_{j} x j have been chosen successively and define
I j : = I j − 1 ( x j ; s ) , M j : = ∣ I j ∣ , Q j : = ∣ E ∩ ( I j × I j ) ∣ . \mathcal{I}_{j}:=\mathcal{I}_{j-1}(x_{j};s),\qquad M_{j}:=|\mathcal{I}_{j}|,\qquad Q_{j}:=|\mathcal{E}\cap(\mathcal{I}_{j}\times\mathcal{I}_{j})|. I j := I j − 1 ( x j ; s ) , M j := ∣ I j ∣ , Q j := ∣ E ∩ ( I j × I j ) ∣.
Here M j M_{j} M j measures the number of candidate hyperplanes that survive after the first j j j -th round. And Q j Q_{j} Q j measures the number of surviving pairs whose normal vectors may be too strongly correlated. Controlling Q j Q_{j} Q j ensures that such pairs remain sufficiently sparse for the second-moment argument at the next stage.
Lemma 5.4 (Stability of the iteration). Assume k log m = o ( m ) k\log m=o(m) k log m = o ( m ) and that Ω b a s e \Omega_{\mathrm{base}} Ω base holds. Use the constants c 1 , A 0 c_{1},A_{0} c 1 , A 0 from Lemma 5.3 . Suppose that the first j j j selected marked rows satisfy
M i ≥ c 1 s M i − 1 , Q i ≤ A 0 s Q i − 1 , 1 ≤ i ≤ j . (30) M_{i}\ge c_{1}sM_{i-1},\qquad Q_{i}\le A_{0}sQ_{i-1},\qquad1\le i\le j. \tag*{(30)} M i ≥ c 1 s M i − 1 , Q i ≤ A 0 s Q i − 1 , 1 ≤ i ≤ j . (30) Then
M j ≥ L 2 ( c 1 s ) j , Q j ≤ 2 L 2 e − ( λ + 4 κ ) m ( A 0 s ) j . (31) M_{j}\ge\frac{L}{2}(c_{1}s)^{j},\qquad Q_{j}\le2L^{2}e^{-(\lambda+4\kappa)m}(A_{0}s)^{j}. \tag*{(31)} M j ≥ 2 L ( c 1 s ) j , Q j ≤ 2 L 2 e − ( λ + 4 κ ) m ( A 0 s ) j . (31) Uniformly for 0 ≤ j < k 0\le j<k 0 ≤ j < k , these bounds imply s M j ≥ 1 sM_{j}\ge1 s M j ≥ 1 and Q j ≤ s M j 2 Q_{j}\le sM_{j}^{2} Q j ≤ s M j 2 for all sufficiently large m m m . If all k k k stages succeed, then M k ≥ 1 M_{k}\ge1 M k ≥ 1 .
Proof. Iteration of (30) , starting from (29) , gives (31) . Also,
log L = h ( β ) m + o ( m ) . (32) \log L=h(\beta)m+o(m). \tag*{(32)} log L = h ( β ) m + o ( m ) . (32)
Recall that Δ = h ( β ) − λ > 0 \Delta=h(\beta)-\lambda>0 Δ = h ( β ) − λ > 0 , log s = − λ m / k − 1 2 log k \log s=-\lambda m/k-\frac{1}{2}\log k log s = − λm / k − 2 1 log k , and 0 < c 1 < 1 0<c_{1}<1 0 < c 1 < 1 . For 0 ≤ j < k 0\le j<k 0 ≤ j < k ,
log ( s M j ) ≥ log ( L / 2 ) + ( j + 1 ) log s + j log c 1 ≥ Δ m − k 2 log k − O ( k ) + o ( m ) ⟶ + ∞ . (33) \begin{aligned}
\log(sM_{j})\ge\log(L/2)+(j+1)\log s+j\log c_{1} \\
&\ge\Delta m-\frac{k}{2}\log k-O(k)+o(m)\longrightarrow+\infty. \tag*{(33)}
\end{aligned} log ( s M j ) ≥ log ( L /2 ) + ( j + 1 ) log s + j log c 1 ≥ Δ m − 2 k log k − O ( k ) + o ( m ) ⟶ + ∞. (33)
The lower bound is uniform in j j j . Similarly, since A 0 > 1 A_{0}>1 A 0 > 1 ,
Q j s M j 2 ≤ 8 e − ( λ + 4 κ ) m ( A 0 c 1 2 ) j s − j − 1 ≤ exp { − 4 κ m + k 2 log k + O ( k ) } ⟶ 0 , (34) \begin{aligned}
\frac{Q_{j}}{sM_{j}^{2}}\le8e^{-(\lambda+4\kappa)m}\left(\frac{A_{0}}{c_{1}^{2}}\right)^{j}s^{-j-1} \\
&\le\exp\left\{-4\kappa m+\frac{k}{2}\log k+O(k)\right\}\longrightarrow0, \tag*{(34)}
\end{aligned} s M j 2 Q j ≤ 8 e − ( λ + 4 κ ) m ( c 1 2 A 0 ) j s − j − 1 ≤ exp { − 4 κm + 2 k log k + O ( k ) } ⟶ 0 , (34)
uniformly for j < k j<k j < k , using s − k = e λ m k / 2 s^{-k}=e^{\lambda_m k/2} s − k = e λ m k /2 . These limits follow from k log m = o ( m ) k\log m=o(m) k log m = o ( m ) and imply the stage hypotheses. Finally,
log M k ≥ log ( L / 2 ) + k log s + k log c 1 ≥ Δ m − k 2 log k − O ( k ) + o ( m ) ⟶ + ∞ . \log M_k\ge\log(L/2)+k\log s+k\log c_1\ge\Delta m-\frac{k}{2}\log k-O(k)+o(m)\longrightarrow+\infty. log M k ≥ log ( L /2 ) + k log s + k log c 1 ≥ Δ m − 2 k log k − O ( k ) + o ( m ) ⟶ + ∞.
Thus M k ≥ 1 M_k\ge1 M k ≥ 1 when all stages succeed.
Completion of the upper estimate
Proposition 5.5 (Upper estimate). Under the assumptions of Theorem 1.3 , for every fixed ε > 0 \varepsilon>0 ε > 0 , there are constants c , C > 0 c,C>0 c , C > 0 such that, with
t m : = exp [ − ( h ( γ ) − ε ) m k m ] , t_m:=\exp\left[-(h(\gamma)-\varepsilon)\frac{m}{k_m}\right], t m := exp [ − ( h ( γ ) − ε ) k m m ] , one has, for all sufficiently large m m m ,
P { M m , r m ( A m ) > t m } ≤ C e − c m + k m exp ( − c m k m ) . (35) \mathbb{P}\{M_{m,r_m}(A_m)>t_m\}\le Ce^{-cm}+k_m\exp\left(-c\frac{m}{k_m}\right). \tag*{(35)} P { M m , r m ( A m ) > t m } ≤ C e − c m + k m exp ( − c k m m ) . (35) In particular, the probability on the left tends to zero.
Proof. Without loss of generality, we assume ε ∈ ( 0 , h ( γ ) ) \varepsilon\in(0,h(\gamma)) ε ∈ ( 0 , h ( γ )) . Use the notation and row decomposition introduced above, and condition first on the base rows. On Ω b a s e \Omega_{\mathrm{base}} Ω base , set I 0 = G \mathcal{I}_0=\mathcal{G} I 0 = G . We choose one row from each group inductively.
Suppose that rows x 1 , … , x j − 1 x_1,\ldots,x_{j-1} x 1 , … , x j − 1 have already been chosen and that the first j − 1 j-1 j − 1 thinnings satisfy (30) . The family I j − 1 \mathcal{I}_{j-1} I j − 1 is determined by the base rows and the first j − 1 j-1 j − 1 groups, whereas the rows in the j j j th group R j \mathcal{R}_j R j are independent of this information. By Lemma 5.4, I j − 1 \mathcal{I}_{j-1} I j − 1 satisfies (25) . Lemma 5.3 therefore shows that each row in R j \mathcal{R}_j R j , conditionally on F j − 1 = σ ( base rows , R 1 , … , R j − 1 ) \mathcal{F}_{j-1}=\sigma(\text{base rows},\mathcal{R}_1,\ldots,\mathcal{R}_{j-1}) F j − 1 = σ ( base rows , R 1 , … , R j − 1 ) , satisfies (30) with probability at least p 0 p_0 p 0 . Since the b b b rows in this group are conditionally independent,
P { R j contains no suitable row ∣ F j − 1 } ≤ ( 1 − p 0 ) b ≤ e − p 0 b . (36) \mathbb{P}\{\mathcal{R}_j\text{ contains no suitable row}\mid\mathcal{F}_{j-1}\}\le(1-p_0)^b\le e^{-p_0b}. \tag*{(36)} P { R j contains no suitable row ∣ F j − 1 } ≤ ( 1 − p 0 ) b ≤ e − p 0 b . (36)
Whenever a suitable row exists, choose the first one in the fixed ordering of R j \mathcal{R}_j R j and continue the construction.
A union bound over the k k k groups gives
P { the construction stops before round k ∣ Ω b a s e } ≤ k e − p 0 b . (37) \mathbb{P}\{\text{the construction stops before round }k\mid\Omega_{\mathrm{base}}\}\le ke^{-p_0b}. \tag*{(37)} P { the construction stops before round k ∣ Ω base } ≤ k e − p 0 b . (37)
If the construction reaches round k k k , Lemma 5.4 gives I k ≠ ∅ \mathcal{I}_k\ne\varnothing I k = ∅ , and Lemma 5.1 then yields M m , r m ( A m ) ≤ t m M_{m,r_m}(A_m)\le t_m M m , r m ( A m ) ≤ t m .
Because b = ⌊ δ m / k ⌋ b=\lfloor\delta m/k\rfloor b = ⌊ δ m / k ⌋ and m / k → ∞ m/k\to\infty m / k → ∞ , one has b ≥ δ m / ( 2 k ) b\ge\delta m/(2k) b ≥ δ m / ( 2 k ) for all sufficiently large m m m . Combining (28) and (37) therefore gives
P { M m , r m ( A m ) > t m } ≤ C e − c m + k exp ( − c m k ) . \mathbb{P}\{M_{m,r_m}(A_m)>t_m\}\le Ce^{-cm}+k\exp\left(-c\frac{m}{k}\right). P { M m , r m ( A m ) > t m } ≤ C e − c m + k exp ( − c k m ) .
Finally, k log m = o ( m ) k\log m=o(m) k log m = o ( m ) implies log k = o ( m / k ) \log k=o(m/k) log k = o ( m / k ) , so the second term tends to zero.
Proof of Theorem 1.3 . Proposition 3.3 gives the lower deviation (12) , and Proposition 5.5 gives the upper deviation (35) . For every fixed ε ∈ ( 0 , h ( γ ) ) \varepsilon\in(0,h(\gamma)) ε ∈ ( 0 , h ( γ )) , their combination yields
P { ∣ k m m log M m , r m ( A m ) + h ( γ ) ∣ > ε } ⟶ 0. \mathbb{P}\left\{\left|\frac{k_m}{m}\log M_{m,r_m}(A_m)+h(\gamma)\right|>\varepsilon\right\}\longrightarrow0. P { m k m log M m , r m ( A m ) + h ( γ ) > ε } ⟶ 0.
This proves (4) .
Proof of Theorem 1.1 . Take k m = r + 1 k_m=r+1 k m = r + 1 fixed in Theorem 1.3 and divide the limit by r + 1 r+1 r + 1 . This gives (3) . For each fixed deviation tolerance, (12) and (35) also give exponentially small failure probabilities.
Phase retrieval
We now apply the row-submatrix estimates to the stability of real phase retrieval. As explained in the Introduction, the loss of sign information makes this stability depend on the least singular values of complementary row blocks. For a full-spark matrix with N = 2 m − 1 + r N=2m-1+r N = 2 m − 1 + r rows, the obstruction ω ( A ) \omega(A) ω ( A ) introduced below is exactly the row minimum M m , r ( A ) M_{m,r}(A) M m , r ( A ) . At the critical count r = 0 r=0 r = 0 , this also equals the optimal lower Lipschitz constant L A L_A L A . When r > 0 r>0 r > 0 , partitions with two full-rank blocks require an additional estimate. We combine the row-minimum theorem with small-ball estimates for these complementary blocks to determine the logarithmic decay rate of L A L_A L A and the corresponding growth rate of the phase-retrieval condition number.
Recall that, for A ∈ R N × m A\in\mathbb{R}^{N\times m} A ∈ R N × m , the real amplitude map is
Φ A : R m / { ± 1 } ⟶ R N , Φ A ( x ) = ∣ A x ∣ , \Phi_A:\mathbb{R}^m/\{\pm1\}\longrightarrow\mathbb{R}^N,\qquad\Phi_A(x)=|Ax|, Φ A : R m / { ± 1 } ⟶ R N , Φ A ( x ) = ∣ A x ∣ ,
where the absolute value is taken coordinatewise. Equip the domain with the quotient distance
d ± ( x , y ) : = min { ∥ x − y ∥ 2 , ∥ x + y ∥ 2 } . d_{\pm}(x,y):=\min\{\|x-y\|_2,\|x+y\|_2\}. d ± ( x , y ) := min { ∥ x − y ∥ 2 , ∥ x + y ∥ 2 } .
The optimal lower and upper Lipschitz constants are
L A : = inf x ≠ ± y ∥ Φ A ( x ) − Φ A ( y ) ∥ 2 d ± ( x , y ) , U A : = sup x ≠ ± y ∥ Φ A ( x ) − Φ A ( y ) ∥ 2 d ± ( x , y ) . (38) L_A:=\inf_{x\ne\pm y}\frac{\|\Phi_A(x)-\Phi_A(y)\|_2}{d_{\pm}(x,y)},\qquad U_A:=\sup_{x\ne\pm y}\frac{\|\Phi_A(x)-\Phi_A(y)\|_2}{d_{\pm}(x,y)}. \tag*{(38)} L A := x = ± y inf d ± ( x , y ) ∥ Φ A ( x ) − Φ A ( y ) ∥ 2 , U A := x = ± y sup d ± ( x , y ) ∥ Φ A ( x ) − Φ A ( y ) ∥ 2 . (38)
Define also the rank-deficient-side obstruction
ω ( A ) : = min J ⊂ [ N ] rank ( A J ) < m σ m ( A J c ) . (39) \omega(A):=\min_{\substack{J\subset[N]\\ \operatorname{rank}(A_J)<m}}\sigma_m(A_{J^c}). \tag*{(39)} ω ( A ) := J ⊂ [ N ] rank ( A J ) < m min σ m ( A J c ) . (39)
Here J c = [ N ] ∖ J J^c=[N]\setminus J J c = [ N ] ∖ J , and the variational convention for σ m \sigma_m σ m in Section 1 includes empty and rank-deficient blocks. When L A > 0 L_A>0 L A > 0 , the amplitude-map condition number is
κ p h ( A ) : = U A L A = ∥ A ∥ o p L A . (40) \kappa_{\mathrm{ph}}(A):=\frac{U_A}{L_A}=\frac{\|A\|_{\mathrm{op}}}{L_A}. \tag*{(40)} κ ph ( A ) := L A U A = L A ∥ A ∥ op . (40)
Proposition 6.1 (Partition formula). *For every real N × m N\times m N × m matrix A A A ,
L A = min J ⊂ [ N ] ( σ m ( A J ) 2 + σ m ( A J c ) 2 ) 1 / 2 , U A = ∥ A ∥ o p . (41) L_A=\min_{J\subset[N]}\left(\sigma_m(A_J)^2+\sigma_m(A_{J^c})^2\right)^{1/2},\qquad U_A=\|A\|_{\mathrm{op}}. \tag*{(41)} L A = J ⊂ [ N ] min ( σ m ( A J ) 2 + σ m ( A J c ) 2 ) 1/2 , U A = ∥ A ∥ op . (41)
Consequently L A ≤ ω ( A ) L_A\le\omega(A) L A ≤ ω ( A ) . If N = 2 m − 1 N=2m-1 N = 2 m − 1 , then L A = ω ( A ) L_A=\omega(A) L A = ω ( A ) .
:::
Proof. The first identity is the real amplitude-map formula of [2 equations (4.3)–(4.5) and Theorem 4.3] ; we give a direct verification in row-matrix notation. For real a , b a,b a , b ,
∣ ∣ a ∣ − ∣ b ∣ ∣ 2 = min { ∣ a − b ∣ 2 , ∣ a + b ∣ 2 } . \lvert\lvert a\rvert-\lvert b\rvert\rvert^2=\min\{\lvert a-b\rvert^2,\lvert a+b\rvert^2\}. ∣∣ a ∣ − ∣ b ∣ ∣ 2 = min {∣ a − b ∣ 2 , ∣ a + b ∣ 2 } .
Writing u = x − y u=x-y u = x − y and v = x + y v=x+y v = x + y therefore gives
∥ Φ A ( x ) − Φ A ( y ) ∥ 2 2 = ∑ i = 1 N min { ∣ ⟨ a i , u ⟩ ∣ 2 , ∣ ⟨ a i , v ⟩ ∣ 2 } = min J ⊂ [ N ] ( ∥ A J u ∥ 2 2 + ∥ A J c v ∥ 2 2 ) . \lVert\Phi_A(x)-\Phi_A(y)\rVert_2^2=\sum_{i=1}^{N}\min\{\lvert\langle a_i,u\rangle\rvert^2,\lvert\langle a_i,v\rangle\rvert^2\}=\min_{J\subset[N]}\left(\lVert A_Ju\rVert_2^2+\lVert A_{J^c}v\rVert_2^2\right). ∥ Φ A ( x ) − Φ A ( y ) ∥ 2 2 = i = 1 ∑ N min {∣⟨ a i , u ⟩ ∣ 2 , ∣⟨ a i , v ⟩ ∣ 2 } = J ⊂ [ N ] min ( ∥ A J u ∥ 2 2 + ∥ A J c v ∥ 2 2 ) .
where a i a_i a i is the i i i th row of A A A . Let Λ \Lambda Λ denote the minimum of σ m ( A J ) 2 + σ m ( A J c ) 2 \sigma_m(A_J)^2+\sigma_m(A_{J^c})^2 σ m ( A J ) 2 + σ m ( A J c ) 2 over J J J . Every term in the last minimum is at least Λ min { ∥ u ∥ 2 2 , ∥ v ∥ 2 2 } \Lambda\min\{\lVert u\rVert_2^2,\lVert v\rVert_2^2\} Λ min {∥ u ∥ 2 2 , ∥ v ∥ 2 2 } , so L A 2 ≥ Λ L_A^2\ge\Lambda L A 2 ≥ Λ .
Conversely, fix J J J and choose unit vectors u , v u,v u , v attaining σ m ( A J ) \sigma_m(A_J) σ m ( A J ) and σ m ( A J c ) \sigma_m(A_{J^c}) σ m ( A J c ) , respectively. Set x = ( u + v ) / 2 x=(u+v)/2 x = ( u + v ) /2 and y = ( v − u ) / 2 y=(v-u)/2 y = ( v − u ) /2 . Then d ± ( x , y ) = 1 d_{\pm}(x,y)=1 d ± ( x , y ) = 1 and x ≠ ± y x\ne\pm y x = ± y , so the same identity gives L A 2 ≤ σ m ( A J ) 2 + σ m ( A J c ) 2 L_A^2\le\sigma_m(A_J)^2+\sigma_m(A_{J^c})^2 L A 2 ≤ σ m ( A J ) 2 + σ m ( A J c ) 2 . Minimizing over J J J proves the first formula. The bound U A ≤ ∥ A ∥ o p U_A\le\lVert A\rVert_{\mathrm{op}} U A ≤ ∥ A ∥ op follows from the reverse triangle inequality, applied with both y y y and − y -y − y ; equality follows by taking y = 0 y=0 y = 0 and a unit vector x x x attaining ∥ A ∥ o p \lVert A\rVert_{\mathrm{op}} ∥ A ∥ op .
Restricting the partition minimum to rank ( A J ) < m \operatorname{rank}(A_J)<m rank ( A J ) < m gives L A ≤ ω ( A ) L_A\le\omega(A) L A ≤ ω ( A ) . When N = 2 m − 1 N=2m-1 N = 2 m − 1 , every partition has a side with at most m − 1 m-1 m − 1 rows. That side has rank less than m m m , so, after exchanging the sides if necessary, every value in the partition minimum occurs in (39) . Hence equality holds.
For N ≥ 2 m N\ge2m N ≥ 2 m , a partition can have two full-rank sides, so equality with ω ( A ) \omega(A) ω ( A ) no longer follows. The next theorem identifies the rate of ω ( A ) \omega(A) ω ( A ) ; Corollary 6.5 then establishes the matching rate for L A L_A L A in the moderate-surplus regime.
Definition 6.2 (Full spark). A real N × m N\times m N × m matrix is full spark if every m m m rows are linearly independent.
Lemma 6.3 (Reduction of ω \omega ω to the redundant row minimum). Let r ≥ 0 r\ge0 r ≥ 0 be an integer, and let A ∈ R ( 2 m − 1 + r ) × m A\in\mathbb{R}^{(2m-1+r)\times m} A ∈ R ( 2 m − 1 + r ) × m be full spark. Then
ω ( A ) = M m , r ( A ) . (42) \omega(A)=M_{m,r}(A). \tag*{(42)} ω ( A ) = M m , r ( A ) . (42) Moreover, L A > 0 L_A>0 L A > 0 .
Proof. Full spark implies rank ( A J ) < m \operatorname{rank}(A_J)<m rank ( A J ) < m exactly when ∣ J ∣ ≤ m − 1 \lvert J\rvert\le m-1 ∣ J ∣ ≤ m − 1 . If J 1 ⊂ J 2 J_1\subset J_2 J 1 ⊂ J 2 , deleting rows gives σ m ( A J 2 c ) ≤ σ m ( A J 1 c ) \sigma_m(A_{J_2^c})\le\sigma_m(A_{J_1^c}) σ m ( A J 2 c ) ≤ σ m ( A J 1 c ) . Thus the minimum in (39) is attained among the sets with ∣ J ∣ = m − 1 \lvert J\rvert=m-1 ∣ J ∣ = m − 1 , whose complements have m + r m+r m + r rows. This proves (42) . Every partition of 2 m − 1 + r 2m-1+r 2 m − 1 + r rows has at least one side with at least m m m rows; full spark makes its least singular value positive. The finite minimum in (41) is therefore positive.
Theorem 6.4 (Phase-retrieval obstruction rate). Let r m ≥ 0 r_m\ge0 r m ≥ 0 be integers, put k m = r m + 1 k_m=r_m+1 k m = r m + 1 and N m = 2 m − 1 + r m N_m=2m-1+r_m N m = 2 m − 1 + r m , and assume k m log m = o ( m ) k_m\log m=o(m) k m log m = o ( m ) . Let A m ∈ R N m × m A_m\in\mathbb{R}^{N_m\times m} A m ∈ R N m × m have i.i.d. entries distributed as ξ \xi ξ under the standing assumptions. Then A m A_m A m is full spark almost surely, and
k m m log ω ( A m ) → P − log 4. (43) \frac{k_m}{m}\log\omega(A_m)\xrightarrow{\mathbb{P}}-\log4. \tag*{(43)} m k m log ω ( A m ) P − log 4. (43) Proof. Absolute continuity gives full spark almost surely. Lemma 6.3 yields ω ( A m ) = M m , r m ( A m ) \omega(A_m)=M_{m,r_m}(A_m) ω ( A m ) = M m , r m ( A m ) . Since N m = 2 m + k m − 2 N_m=2m+k_m-2 N m = 2 m + k m − 2 and k m = o ( m ) k_m=o(m) k m = o ( m ) , one has N m / m → 2 N_m/m\to2 N m / m → 2 . Theorem 1.3 , together with h ( 2 ) = log 4 h(2)=\log4 h ( 2 ) = log 4 , proves (43) .
Corollary 6.5 (Optimal lower Lipschitz rate with redundant rows). Under the assumptions of Theorem 6.4 ,
k m m log L A m → P − log 4. (44) \frac{k_m}{m}\log L_{A_m} \xrightarrow{\mathbb{P}} -\log4. \tag*{(44)} m k m log L A m P − log 4. (44) More precisely, with D D D from Lemma 3.2 , for every t > 0 t>0 t > 0 ,
P { L A m ≤ t } ≤ 2 N m m 2 ( D m t ) k m . (45) \mathbb{P}\{L_{A_m}\le t\}\le2^{N_m}m^2(D\sqrt{m}t)^{k_m}. \tag*{(45)} P { L A m ≤ t } ≤ 2 N m m 2 ( D m t ) k m . (45) In particular, for every fixed ε > 0 \varepsilon>0 ε > 0 ,
P { L A m ≤ exp [ − ( log 4 + ε ) m k m ] } ≤ exp { − ε m + O ( k m log m ) } ⟶ 0. (46) \mathbb{P}\left\{L_{A_m}\le\exp\left[-(\log4+\varepsilon)\frac{m}{k_m}\right]\right\}\le\exp\{-\varepsilon m+O(k_m\log m)\}\longrightarrow0. \tag*{(46)} P { L A m ≤ exp [ − ( log 4 + ε ) k m m ] } ≤ exp { − ε m + O ( k m log m )} ⟶ 0. (46) For fixed r m = r r_m=r r m = r , this gives m − 1 log L A m → P − log 4 / ( r + 1 ) m^{-1}\log L_{A_m}\xrightarrow{\mathbb{P}}-\log4/(r+1) m − 1 log L A m P − log 4/ ( r + 1 ) .
Proof. Fix m m m and abbreviate N = N m N=N_m N = N m , k = k m k=k_m k = k m , and A = A m A=A_m A = A m . For a deterministic J ⊂ [ N ] J\subset[N] J ⊂ [ N ] , let
F J ( t ) : = { σ m ( A J ) 2 + σ m ( A J c ) 2 ≤ t 2 } . F_J(t):=\{\sigma_m(A_J)^2+\sigma_m(A_{J^c})^2\le t^2\}. F J ( t ) := { σ m ( A J ) 2 + σ m ( A J c ) 2 ≤ t 2 } .
By (41) , { L A ≤ t } = ⋃ J ⊂ [ N ] F J ( t ) \{L_A\le t\}=\bigcup_{J\subset[N]}F_J(t) { L A ≤ t } = ⋃ J ⊂ [ N ] F J ( t ) . We bound the probability for each fixed partition.
Suppose first that ∣ J ∣ ≥ m |J|\ge m ∣ J ∣ ≥ m and ∣ J c ∣ ≥ m |J^c|\ge m ∣ J c ∣ ≥ m . Set
d 1 : = ∣ J ∣ − m + 1 , d 2 : = ∣ J c ∣ − m + 1. d_1:=|J|-m+1,\qquad d_2:=|J^c|-m+1. d 1 := ∣ J ∣ − m + 1 , d 2 := ∣ J c ∣ − m + 1.
Then d 1 , d 2 ≥ 1 d_1,d_2\ge1 d 1 , d 2 ≥ 1 and, crucially,
d 1 + d 2 = N − 2 m + 2 = k . d_1+d_2=N-2m+2=k. d 1 + d 2 = N − 2 m + 2 = k .
The event F J ( t ) F_J(t) F J ( t ) requires both σ m ( A J ) ≤ t \sigma_m(A_J)\le t σ m ( A J ) ≤ t and σ m ( A J c ) ≤ t \sigma_m(A_{J^c})\le t σ m ( A J c ) ≤ t . The two row blocks are independent because J J J is deterministic and the entries of A A A are independent. Applying Lemma 3.2 separately gives
P ( F J ( t ) ) ≤ P { σ m ( A J ) ≤ t } P { σ m ( A J c ) ≤ t } ≤ m 2 ( D m t ) d 1 + d 2 = m 2 ( D m t ) k . \mathbb{P}(F_J(t))\le\mathbb{P}\{\sigma_m(A_J)\le t\}\mathbb{P}\{\sigma_m(A_{J^c})\le t\}
\le m^2(D\sqrt{m}t)^{d_1+d_2}=m^2(D\sqrt{m}t)^k. P ( F J ( t )) ≤ P { σ m ( A J ) ≤ t } P { σ m ( A J c ) ≤ t } ≤ m 2 ( D m t ) d 1 + d 2 = m 2 ( D m t ) k .
Suppose instead that ∣ J ∣ < m |J|<m ∣ J ∣ < m . Then σ m ( A J ) = 0 \sigma_m(A_J)=0 σ m ( A J ) = 0 and ∣ J c ∣ ≥ m + k − 1 |J^c|\ge m+k-1 ∣ J c ∣ ≥ m + k − 1 . Choose a deterministic subset T J ⊂ J c T_J\subset J^c T J ⊂ J c of size m + k − 1 m+k-1 m + k − 1 . Adding rows cannot decrease the least singular value, so σ m ( A J c ) ≥ σ m ( A T J ) \sigma_m(A_{J^c})\ge\sigma_m(A_{T_J}) σ m ( A J c ) ≥ σ m ( A T J ) . Hence
P ( F J ( t ) ) ≤ P { σ m ( A T J ) ≤ t } ≤ m ( D m t ) k ≤ m 2 ( D m t ) k . \mathbb{P}(F_J(t))\le\mathbb{P}\{\sigma_m(A_{T_J})\le t\}\le m(D\sqrt{m}t)^k\le m^2(D\sqrt{m}t)^k. P ( F J ( t )) ≤ P { σ m ( A T J ) ≤ t } ≤ m ( D m t ) k ≤ m 2 ( D m t ) k .
The case ∣ J c ∣ < m |J^c|<m ∣ J c ∣ < m is identical after interchanging the sides. These cases exhaust all partitions since N ≥ 2 m − 1 N\ge2m-1 N ≥ 2 m − 1 . In particular, when k = 1 k=1 k = 1 there are no partitions with both sides of size at least m m m .
A union bound over the 2 N 2^N 2 N subsets J J J proves (45) ; no independence between different partitions is needed. For t = exp [ − ( log 4 + ε ) m / k ] t=\exp[-(\log4+\varepsilon)m/k] t = exp [ − ( log 4 + ε ) m / k ] , the logarithm of its right-hand side is
N log 2 + 2 log m + k log D + k 2 log m − ( log 4 + ε ) m = − ε m + ( k − 2 ) log 2 + 2 log m N\log2+2\log m+k\log D+\frac{k}{2}\log m-(\log4+\varepsilon)m
=-\varepsilon m+(k-2)\log2+2\log m N log 2 + 2 log m + k log D + 2 k log m − ( log 4 + ε ) m = − ε m + ( k − 2 ) log 2 + 2 log m
+ k log D + k 2 log m = − ε m + O ( k log m ) . \qquad{}+k\log D+\frac{k}{2}\log m
=-\varepsilon m+O(k\log m). + k log D + 2 k log m = − ε m + O ( k log m ) .
The assumption k log m = o ( m ) k\log m=o(m) k log m = o ( m ) proves (46) .
For the opposite deviation, use L A m ≤ ω ( A ) L_{A_m}\leq\omega(A) L A m ≤ ω ( A ) and Theorem 6.4 . More quantitatively, full spark and Proposition 5.5 , with γ = 2 \gamma=2 γ = 2 , give, for each fixed ε ∈ ( 0 , log 4 ) \varepsilon\in(0,\log4) ε ∈ ( 0 , log 4 ) ,
P { L A m > exp [ − ( log 4 − ε ) m k m ] } ≤ C e − c m + k m exp ( − c m k m ) ⟶ 0. (47) \mathbb{P}\left\{L_{A_m}>\exp\left[-(\log4-\varepsilon)\frac{m}{k_m}\right]\right\}\leq Ce^{-cm}+k_m\exp\left(-c\frac{m}{k_m}\right)\longrightarrow0. \tag*{(47)} P { L A m > exp [ − ( log 4 − ε ) k m m ] } ≤ C e − c m + k m exp ( − c k m m ) ⟶ 0. (47)
Combining the two deviations proves (44) .
Remark 6.6 (Scope of the rate conclusion). Theorem 6.4 and Corollary 6.5 identify the same logarithmic rate for ω ( A m ) \omega(A_m) ω ( A m ) and L A m L_{A_m} L A m . They do not assert equality of these quantities for redundant matrices, convergence of their ratio to one, or a sharp multiplicative prefactor. The conclusion is restricted to k m log m = o ( m ) k_m\log m=o(m) k m log m = o ( m ) .
Corollary 6.7 (Almost-sure logarithmic laws). Assume the matrices A m A_m A m in Theorem 1.3 are defined on a common probability space. No independence across dimensions is required. Then
k m m log M m , r m ( A m ) ⟶ − h ( γ ) almost surely. \frac{k_m}{m}\log M_{m,r_m}(A_m)\longrightarrow-h(\gamma)\qquad\text{almost surely.} m k m log M m , r m ( A m ) ⟶ − h ( γ ) almost surely. In particular, for fixed r m = r r_m=r r m = r , the limit in Theorem 1.1 holds almost surely. Under the phase-retrieval specialization N m = 2 m − 1 + r m N_m=2m-1+r_m N m = 2 m − 1 + r m ,
k m m log ω ( A m ) ⟶ − log 4 , k m m log L A m ⟶ − log 4 almost surely. \frac{k_m}{m}\log\omega(A_m)\longrightarrow-\log4,\qquad\frac{k_m}{m}\log L_{A_m}\longrightarrow-\log4\qquad\text{almost surely.} m k m log ω ( A m ) ⟶ − log 4 , m k m log L A m ⟶ − log 4 almost surely. These statements apply to each prescribed sequence satisfying the stated assumptions.
Proof. Fix ε ∈ ( 0 , h ( γ ) ) \varepsilon\in(0,h(\gamma)) ε ∈ ( 0 , h ( γ )) . By (12) , the lower-deviation probability is at most exp { − ε m + o ( m ) } \exp\{-\varepsilon m+o(m)\} exp { − ε m + o ( m )} and is therefore summable. By (35) , the upper-deviation probability is at most
C e − c m + k m exp ( − c m / k m ) , Ce^{-cm}+k_m\exp(-cm/k_m), C e − c m + k m exp ( − c m / k m ) ,
where c , C > 0 c,C>0 c , C > 0 may depend on the fixed ε \varepsilon ε and γ \gamma γ , but not on m m m . Since k m log m = o ( m ) k_m\log m=o(m) k m log m = o ( m ) , eventually k m ≤ m k_m\leq m k m ≤ m and c m / k m ≥ 4 log m cm/k_m\geq4\log m c m / k m ≥ 4 log m . Hence
k m exp ( − c m / k m ) ≤ m − 3 k_m\exp(-cm/k_m)\leq m^{-3} k m exp ( − c m / k m ) ≤ m − 3
for all sufficiently large m m m , so the upper-deviation probabilities are summable as well. The first Borel–Cantelli lemma, applied for a countable sequence of positive ε \varepsilon ε tending to zero, proves the row-minimum limit. Taking k m = r + 1 k_m=r+1 k m = r + 1 gives the fixed-surplus assertion. Absolute continuity gives the required full-rank events simultaneously for all m m m by a countable intersection.
For ω ( A m ) \omega(A_m) ω ( A m ) , use (42) and h ( 2 ) = log 4 h(2)=\log4 h ( 2 ) = log 4 . For L A m L_{A_m} L A m , the lower-deviation bound (46) is summable because k m log m = o ( m ) k_m\log m=o(m) k m log m = o ( m ) , and the upper-deviation bound (47) is summable by the same argument. Applying Borel–Cantelli again proves the remaining limit. None of these applications requires independence across dimensions.
Corollary 6.8 (Phase-retrieval condition number). Under the assumptions of Theorem 6.4 ,
k m m log κ p h ( A m ) ⟶ log 4. (48) \frac{k_m}{m}\log\kappa_{\mathrm{ph}}(A_m)\longrightarrow\log4. \tag*{(48)} m k m log κ ph ( A m ) ⟶ log 4. (48) If the matrices are defined on a common probability space, this convergence holds almost surely, without requiring independence across dimensions. Moreover, κ p h ( A m / m ) = κ p h ( A m ) \kappa_{\mathrm{ph}}(A_m/\sqrt{m})=\kappa_{\mathrm{ph}}(A_m) κ ph ( A m / m ) = κ ph ( A m ) .
Proof. Since N m / m → 2 N_m/m \to2 N m / m → 2 , the subgaussian operator-norm estimate [13 Theorem 4.4.5] , with deviation parameter u = m u=\sqrt{m} u = m , gives constants c , C > 0 c,C>0 c , C > 0 such that
P { ∥ A m ∥ o p > C m } ≤ 2 e − c m \mathbb{P}\{\lVert A_m\rVert_{\mathrm{op}}>C\sqrt{m}\}\le2e^{-cm} P {∥ A m ∥ op > C m } ≤ 2 e − c m
for all sufficiently large m m m . For a lower bound, ∥ A m ∥ o p ≥ ∥ A m e 1 ∥ 2 \lVert A_m\rVert_{\mathrm{op}}\ge\lVert A_m e_1\rVert_2 ∥ A m ∥ op ≥ ∥ A m e 1 ∥ 2 . Because E ξ 2 = 1 \mathbb{E}\xi^2=1 E ξ 2 = 1 , there is a fixed θ > 0 \theta>0 θ > 0 such that
E e − θ ξ 2 ≤ e − 3 θ / 4 . \mathbb{E}e^{-\theta\xi^2}\le e^{-3\theta/4}. E e − θ ξ 2 ≤ e − 3 θ /4 .
Indeed, both sides equal one at θ = 0 \theta=0 θ = 0 , and their right derivatives there are − 1 -1 − 1 and − 3 / 4 -3/4 − 3/4 , respectively. Independence of the entries in the first column and Markov’s inequality give
P { ∥ A m e 1 ∥ 2 2 ≤ N m / 2 } ≤ e θ N m / 2 ( E e − θ ξ 2 ) N m ≤ e − θ N m / 4 . \mathbb{P}\{\lVert A_m e_1\rVert_2^2\le N_m/2\}\le e^{\theta N_m/2}\bigl(\mathbb{E}e^{-\theta\xi^2}\bigr)^{N_m}\le e^{-\theta N_m/4}. P {∥ A m e 1 ∥ 2 2 ≤ N m /2 } ≤ e θ N m /2 ( E e − θ ξ 2 ) N m ≤ e − θ N m /4 .
Thus log ∥ A m ∥ o p = 1 2 log m + O P ( 1 ) \log\lVert A_m\rVert_{\mathrm{op}}=\frac{1}{2}\log m+O_{\mathbb{P}}(1) log ∥ A m ∥ op = 2 1 log m + O P ( 1 ) , and
k m m log ∥ A m ∥ o p → P 0 \frac{k_m}{m}\log\lVert A_m\rVert_{\mathrm{op}}\xrightarrow{\mathbb{P}}0 m k m log ∥ A m ∥ op P 0
by k m log m = o ( m ) k_m\log m=o(m) k m log m = o ( m ) . Combining this with (40) and Corollary 6.5 proves (48) .
On a common probability space, the two norm-deviation bounds are summable. Borel–Cantelli therefore gives c 0 m ≤ ∥ A m ∥ o p ≤ C m c_0\sqrt{m}\le\lVert A_m\rVert_{\mathrm{op}}\le C\sqrt{m} c 0 m ≤ ∥ A m ∥ op ≤ C m eventually almost surely for a deterministic c 0 > 0 c_0>0 c 0 > 0 . The scaled logarithm of the norm then converges almost surely to zero, and Corollary 6.7 supplies the almost-sure limit for L A m L_{A_m} L A m . Finally, multiplication of A A A by a positive scalar multiplies both U A U_A U A and L A L_A L A by that scalar, leaving their ratio unchanged. □
References