Universality of smallest singular values of random row submatrices and phase retrieval problems
math.PR
Submitted: 2026-11-04
Updated: 2026-11-04
Comments: 28 pages
License: http://creativecommons.org/licenses/by/4.0/
The gist: 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.
Terminology
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 A m in 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 N m/m toγ>1. For integers 0 at most r m at most N m-m, let M m,r m(A m) be the minimum least singular value over all row submatrices of A m with m+r m rows. Writing k m=r m+1, we prove that whenever k m m=o(m), (k m/m) M m,r m(A m) converges in probability to-h(γ), where h(γ)=γ γ-(γ-1) (γ-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 N m=2m-1+r m amplitude measurements, let L A m denote the optimal lower Lipschitz constant of the map x A mx, with signals identified up to sign, and let κ ph(A m)=|A m| op/L A m be its scale-invariant global condition number. In the same surplus regime, (k m/m) L A m and (k m/m) κ ph(A m) converge in probability to - 4 and 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 m 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.
Sources
- Normal vector of a random hyperplane
- Extreme least singular values of Gaussian row submatrices and a phase retrieval stability problem
Related papers
- Rank-One HCIZ Integrals and Multiplicative Convolutions
- Repeated averaging on random d-regular graphs
- Precise cover times for branching random walks on Hamming graphs: (iterated) logarithmic corrections
- Markov Chain CLTs: Resolving Open Problems
- Marked stable L'evy processes in Brownian local time
- A Sharp Refinement of Samuels' Inequality via Cap Moves