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∈ℝNm× 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→γ>1. For integers 0≤ rm≤ Nm−m, let Mm,rm(Am) be the minimum least singular value over all row submatrices of Am with m+rm rows. Writing km=rm+1, we prove that whenever kmlog m=o(m), (km/m)log Mm,rm(Am) converges in probability to −h(γ), where 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+rm amplitude measurements, let LAm denote the optimal lower Lipschitz constant of the map x↦|Amx|, with signals identified up to sign, and let κph(Am)=|Am|op/LAm be its scale-invariant global condition number. In the same surplus regime, (km/m)log LAm and (km/m)logκph(Am) converge in probability to −log 4 and 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 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.
Related
- Smallest Singular Value Estimates for Nonuniform Fourier Matrices via Periodic Nonuniform Sampling
- An upper bound on the smallest singular value of dense signed random combinatorial matrices
- The smallest singular value of products of random combinatorial and deterministic matrices
- Multiple solutions of singular periodic problems
- Singular set estimates in quasilinear Alt-Caffarelli problems
BibTeX
@misc{wen2026universality,
title = {{Universality of smallest singular values of random row submatrices and phase retrieval problems}},
author = {Shu Wen and Christian E. Häggblom and Xiufan Yang},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.06736},
eprint = {2611.06736},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.06736},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Universality of smallest singular values of random row submatrices and phase retrieval problems
AU - Shu Wen
AU - Christian E. Häggblom
AU - Xiufan Yang
PY - 2026
DA - 2026/11/04
PB - arXiv
DO - 10.48550/arxiv.2611.06736
UR - https://arxiv.org/abs/2611.06736
AB - 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∈ℝ^N_m× 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→γ>1. For integers 0≤ r_m≤ 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_mlog m=o(m), (k_m/m)log M_m,r_m(A_m) converges in probability to −h(γ), where 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 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)log L_A_m and (k_m/m)logκ_ph(A_m) converge in probability to −log 4 and 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 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.
ER -