betaFeedback

WorksMathematics

Universality of smallest singular values of random row submatrices and phase retrieval problems

Abstract

We establish universal logarithmic laws for extreme least singular values of random row submatrices and for the global stability of real phase retrieval near its injectivity threshold. Let Am∈RNm×mA_m\in\mathbb{R}^{N_m\times m} have i.i.d. entries distributed as a centered, variance-one real subgaussian random variable with a bounded Lebesgue density, and suppose Nm/m→γ>1N_m/m\toγ>1. For integers 0≤rm≤Nm−m0\le r_m\le N_m-m, let Mm,rm(Am)M_{m,r_m}(A_m) be the minimum least singular value over all row submatrices of AmA_m with m+rmm+r_m rows. Writing km=rm+1k_m=r_m+1, we prove that whenever kmlog⁡m=o(m)k_m\log m=o(m), (km/m)log⁡Mm,rm(Am)(k_m/m)\log M_{m,r_m}(A_m) converges in probability to −h(γ)-h(γ), where h(γ)=γlog⁡γ−(γ−1)log⁡(γ−1)h(γ)=γ\logγ-(γ-1)\log(γ-1). This covers both fixed and moderately growing surplus. The limiting rate is universal within the stated class of entry distributions. For real phase retrieval from Nm=2m−1+rmN_m=2m-1+r_m amplitude measurements, let LAmL_{A_m} denote the optimal lower Lipschitz constant of the map x↦∣Amx∣x\mapsto|A_mx|, with signals identified up to sign, and let κph(Am)=∥Am∥op/LAmκ_{\mathrm{ph}}(A_m)=\|A_m\|_{\mathrm{op}}/L_{A_m} be its scale-invariant global condition number. In the same surplus regime, (km/m)log⁡LAm(k_m/m)\log L_{A_m} and (km/m)log⁡κph(Am)(k_m/m)\logκ_{\mathrm{ph}}(A_m) converge in probability to −log⁡4-\log 4 and log⁡4\log 4, respectively. Although these measurements determine every signal up to sign almost surely, the condition number grows exponentially in dimension for fixed surplus and exceeds every fixed power of mm throughout the stated regime, with probability tending to one. These conclusions quantify the distinction between uniqueness and uniform stability under measurement noise. All stated limits also hold almost surely on any common probability space, without requiring independence across dimensions.

Introduction and main results

Let A∈RN×mA \in\mathbb{R}^{N \times m}, with N≥mN \ge m. For an integer 0≤r≤N−m0 \le r \le N-m, define

Mm,r(A):=min⁡T⊂[N]∣T∣=m+rσm(AT),Mm(A):=Mm,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)}

where ATA_T is the row submatrix indexed by TT. For any matrix BB with mm columns, we use the convention

σm(B):=inf⁡∥x∥2=1∥Bx∥2\sigma_m(B) := \inf_{\lVert x\rVert_2=1} \lVert Bx\rVert_2

to denote it’s least singular value. In particular, σm(B)=0\sigma_m(B)=0 when BB has rank less than mm, including when it has fewer than mm rows. The quantity Mm,r(A)M_{m,r}(A) measures the smallest least singular value among the (m+r)×m(m+r) \times m row submatrices; the square case is r=0r=0.

For background on least singular values of i.i.d. random matrices, see [7, 12]. Even when the entries of AA 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, set

h(γ):=γlog⁡γ−(γ−1)log⁡(γ−1).(2)h(\gamma) := \gamma\log\gamma- (\gamma- 1)\log(\gamma- 1). \tag*{(2)}

If Nm/m→γN_m/m \to\gamma, then

(Nmm)=exp⁡{h(γ)m+o(m)}.\binom{N_m}{m} = \exp\{h(\gamma)m + o(m)\}.

Shmalo [10] established the square-row law for real standard Gaussian entries,

1mlog⁡Mm(Am)→P−h(γ),\frac{1}{m}\log M_m(A_m) \xrightarrow{\mathbb{P}} -h(\gamma),

and the complex Gaussian exponent −h(γ)/2-h(\gamma)/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. Write

K:=∥fξ∥∞<∞.K := \lVert f_\xi\rVert_\infty< \infty.

All matrix entries are independent copies of ξ\xi. No smoothness of fξf_\xi is assumed.

Theorem 1.1 (Fixed-surplus law). Let r≥0r \ge0 be a fixed integer, and let Am∈RNm×mA_m \in\mathbb{R}^{N_m \times m} have independent entries distributed as ξ\xi. Assume Nm/m→γ>1N_m/m \to\gamma> 1 and Nm≥m+rN_m \ge m + r for all large mm. Then

1mlog⁡Mm,r(Am)→P−h(γ)r+1(3)\frac{1}{m}\log M_{m,r}(A_m) \xrightarrow{\mathbb{P}} -\frac{h(\gamma)}{r+1} \tag*{(3)}

Remark 1.2. Note that the normalization Var⁡(ξ)=1\operatorname{Var}(\xi) = 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, since ξ\xi is subgaussian and has a Lebesgue density, 0<σ<∞0 < \sigma< \infty. Define ξ~=ξ/σ\widetilde{\xi} = \xi/\sigma, A~m=Am/σ\widetilde{A}_m = A_m/\sigma. Then ξ~\widetilde{\xi} is centered, variance one, subgaussian, and has density fξ~(x)=σfξ(σx)f_{\widetilde{\xi}}(x) = \sigma f_\xi(\sigma x), so that ∥fξ~∥∞≤σK\lVert f_{\widetilde{\xi}}\rVert_\infty\le\sigma K. Moreover, Mm,r(Am)=σMm,r(A~m)M_{m,r}(A_m) = \sigma M_{m,r}(\widetilde{A}_m). We have

1mlog⁡Mm,r(Am)=log⁡σm+1mlog⁡Mm,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).

Now since for every fixed ε∈(0,h(γ))\varepsilon\in(0,h(\gamma)), ∣log⁡σ∣/m≤ε/2\lvert\log\sigma\rvert/m \le\varepsilon/2 for sufficiently large mm,

P{∣1mlog⁡Mm,r(Am)+h(γ)r+1∣>ε}=P{∣log⁡σm+1mlog⁡Mm,r(A~m)+h(γ)r+1∣>ε}≤P{∣1mlog⁡Mm,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\}.

Thus, it is enough to establish the desired estimate for the normalized matrix A~m\widetilde{A}_m, i.e., under the assumption Var⁡(ξ)=1\operatorname{Var}(\xi) = 1. For the remainder of the proof we impose this normalization.

If rr is not fixed, we have the following moderate-surplus form.

Theorem 1.3 (Moderate-surplus law). Let NmN_m and rmr_m be integer-valued sequences, and let Am∈RNm×mA_m \in\mathbb{R}^{N_m \times m} have i.i.d. entries distributed as ξ\xi. Suppose

Nmm⟶γ>1,km=rm+1∈N,kmlog⁡m=o(m),0≤rm≤Nm−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

for all large mm. Then

kmmlog⁡Mm,rm(Am)→P−h(γ).(4)\frac{k_m}{m}\log M_{m,r_m}(A_m) \xrightarrow{\mathbb{P}} -h(\gamma). \tag*{(4)}

The deviation estimates proved below are summable. Consequently, if the matrices AmA_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 ω(Am)\omega(A_m) and the optimal lower Lipschitz constant LAmL_{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=km=rm+1k=k_m=r_m+1. There are exp⁡{h(γ)m+o(m)}\exp\{h(\gamma)m+o(m)\} candidate row sets. An (m−1)(m-1)-row base set determines a unit normal uu, and adjoining kk rows whose scalar products with uu have absolute value at most t/kt/\sqrt{k} produces an (m+k−1)×m(m+k-1)\times m matrix with least singular value at most tt. For a delocalized normal, each independent constraint has probability comparable to t/kt/\sqrt{k}. Their combined cost is therefore tkexp⁡{O(klog⁡(k+1))}t^k\exp\{O(k\log(k+1))\}. Since klog⁡m=o(m)k\log m=o(m), balancing this cost against the number of candidates suggests klog⁡t∼−h(γ)mk\log t\sim-h(\gamma)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∈RN×mA\in\mathbb{R}^{N\times m}, the amplitude map is

ΦA:Rm/{±1}⟶RNΦA(x)=∣Ax∣\Phi_A:\mathbb{R}^m/\{\pm1\}\longrightarrow\mathbb{R}^N\qquad\Phi_A(x)=|Ax|

with the absolute value taken coordinatewise. The quotient accounts for the unavoidable ambiguity between xx and −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 xx and yy 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 JJ, on which AJ(x−y)A_J(x-y) is small, and its complement, on which AJc(x+y)A_{J^c}(x+y) is small. If the signals are separated up to sign, both x−yx-y and x+yx+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], either the rows of AJA_J or those of AJcA_{J^c} span Rm\mathbb{R}^m. Consequently, 2m−12m-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 mm rows are linearly independent. This holds almost surely under our absolute-continuity assumption.

References

  1. [1]R. Balan, P. G. Casazza, and D. Edidin, On signal reconstruction without phase, Appl. Comput. Harmon. Anal. 20 (2006), no. 3, 345–356.DOI
  2. [2]R. Balan and Y. Wang, Invertibility and robustness of phaseless reconstruction, Appl. Comput. Harmon. Anal. 38 (2015), no. 3, 469–488.arxiv.org/abs/1308.4718
  3. [3]A. S. Bandeira, J. Cahill, D. G. Mixon, and A. A. Nelson, Saving phase: injectivity and stability for phase retrieval, Appl. Comput. Harmon. Anal. 37 (2014), no. 1, 106–125.arxiv.org/abs/1302.4618
  4. [4]S. G. Bobkov and F. Götze, Berry–Esseen bounds in the local limit theorems, Lithuanian Math. J. 65 (2025), no. 1, 50–66, doi:10.1007/s10986-025-09659-1.
  5. [6]H. H. Nguyen and V. H. Vu, Normal vector of a random hyperplane, Int. Math. Res. Not. IMRN (2018), no. 6, 1754–1778; arXiv:1604.04897.arxiv.org/abs/1604.04897
  6. [7]M. Rudelson and R. Vershynin, The smallest singular value of a random rectangular matrix, Comm. Pure Appl. Math. 62 (2009), no. 12, 1707–1739.arxiv.org/abs/0802.3956
  7. [8]M. Rudelson and R. Vershynin, Small ball probabilities for linear images of high-dimensional distributions, Int. Math. Res. Not. IMRN (2015), no. 19, 9594–9617.
  8. [9]L. Rademacher and C. Shu, The smoothed complexity of Frank–Wolfe methods via conditioning of random matrices and polytopes, Math. Stat. Learn. 5 (2022), no. 3/4, 273–310, doi:10.4171/MSL/35.DOI
  9. [10]Y. Shmalo, Extreme least singular values of Gaussian row submatrices and a phase retrieval stability problem, arXiv:2607.06249 (2026).arxiv.org/abs/2607.06249
  10. [11]Y. Shmalo, Extreme least singular values with redundancy, radial ensembles, and quantitative stability of phase retrieval, unpublished manuscript, June 28, 2026, privately communicated.
  11. [12]T. Tao and V. Vu, Random matrices: the distribution of the smallest singular values, Geom. Funct. Anal. 20 (2010), no. 1, 260–297.arxiv.org/abs/0903.0614
  12. [13]R. Vershynin, High-Dimensional Probability: An Introduction with Applications in Data Science, Cambridge Series in Statistical and Probabilistic Mathematics, Cambridge University Press, Cambridge, 2018.
  13. [14]C. E. Häggblom, Gaussian Critical-Threshold Instability in Real Phase Retrieval, arXiv:2609.28198 (2026).arxiv.org/abs/2609.28198

Paper details

vlnc:W_8s5vxsdq
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 10

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents