OP-00060 Solution claimed

The value of ω(A) for Gaussian matrices in real phase retrieval

For $A \in \mathbb{R}^{N \times M}$ with rows $A_1, \dots, A_N$ let $$\omega(A) = \min_{S \subseteq [N]:\ \operatorname{rank}(A_{S^c}) < M} \sigma_M(A_S),$$ where $A_S$ is the submatrix of the rows indexed by $S$ and $\sigma_M$ is its $M$-th singular value. Real phase retrieval with $A$ is injective exactly when $\omega(A) > 0$, which requires $N \ge 2M - 1$, and its stability is governed by $1/\omega(A)$. Balan and Wang conjectured that there are universal constants $C > 0$ and $0 < \beta < 1$ such that $\omega(A) \le C \max_k \|A_k\|\, \beta^M$ for every $M > 1$ and every $A \in \mathbb{R}^{(2M-1) \times M}$ in which any $M$ rows span $\mathbb{R}^M$.

Problem. For $A \in \mathbb{R}^{(2M-1) \times M}$ with i.i.d. standard Gaussian entries, what is the value of $\omega(A)$? Does it satisfy the Balan–Wang bound? If so, what is $\beta$?

Source: Bandeira, Open Problem 21 of Randomstrasse101, in “Injectivity and Stability of Phase Retrieval” (2025); Entry 10 of arXiv:2603.29571.

The statement is adapted from randomstrasse101.math.ethz.ch, whose text is available under CC BY 4.0.

Classification

Primary: PR — Probability
Secondary: FA
Keywords: phase retrieval, random matrices, Randomstrasse101, stability
Literature checked: Oct. 2, 2026 by clemens-admin

References

@misc{randomstrasse2025,
  author = {Bandeira, Afonso S. and Dmitriev, Daniil and Lucca, Kevin and Nizi{\'c}-Nikolac, Petar and R{\"o}dder, Almut},
  title = {{Randomstrasse101}: Open Problems of 2025},
  year = {2026},
  eprint = {2603.29571},
  archivePrefix = {arXiv}
}

@article{balan2015invertibility,
  author = {Balan, Radu and Wang, Yang},
  title = {Invertibility and robustness of phaseless reconstruction},
  journal = {Applied and Computational Harmonic Analysis},
  volume = {38},
  number = {3},
  pages = {469--488},
  year = {2015},
  doi = {10.1016/j.acha.2014.07.003},
  eprint = {1308.4718},
  archivePrefix = {arXiv}
}

Resolution claims

Extreme least singular values of Gaussian row submatrices and a phase retrieval stability problem v1 arXiv ↗ AI-Verified

Yitzchak Shmalo

Let $\mathbb F\in\{\mathbb R,\mathbb C\}$ and $d_{\mathbb F}=\dim_{\mathbb R}\mathbb F$. If $A_m\in\mathbb F^{N_m\times m}$ has independent standard Gaussian entries and $N_m/m\toγ>1$, then \[ \min_{\substack{T\subset[N_m]\\ |T|=m}} σ_{\min}(A_{m,T}) = \left(\frac{γ^γ}{(γ-1)^{γ-1}}\right)^{-m/d_{\mathbb F}+o_P(m)} . \] If $N_m=γm+O(1)$, the convergence of $m^{-1}\log M_m^{\mathbb F}$ has probability error $O(m^{-1})$. In particular, at the real phase-retrieval threshold $N=2m-1$, \[ ω(A_m)=4^{-m+o_P(m)}, \] so the Gaussian Balan--Wang critical exponential …

Full resolution · not verified · fidelity not established · posted on arXiv 7 Jul 2026

Status history

When	Change	By	Reason
2026-10-04	Open → Solution claimed	The registry's curators	Extreme least singular values of Gaussian row submatrices and a phase retrieval stability problem v1 recorded from arXiv:2607.06249v1.

Citing this problem

This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.

OP-00060, "The value of ω(A) for Gaussian matrices in real phase retrieval", clopen.solutions.