The Balan–Wang conjecture on the stability of 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$ (the complement property), and Balan and Wang showed that its stability is governed by $1/\omega(A)$. For $N = 2M - 1$, generic $A$ is injective.
Problem. Prove or disprove that there are universal constants $C > 0$ and $0 < \beta < 1$ such that for every $M > 1$ and every $A \in \mathbb{R}^{(2M-1) \times M}$ any $M$ rows of which span $\mathbb{R}^M$, $$\omega(A) \le C \max_k \|A_k\|\, \beta^M.$$
Source: Balan and Wang (2013), arXiv:1308.4718. Conjecture 20 of Randomstrasse101, in Bandeira's “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
- FA — Functional Analysis
- Secondary
- NA
- Keywords
- frames, phase retrieval, 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}
}
@article{bandeira2014saving,
author = {Bandeira, Afonso S. and Cahill, Jameson and Mixon, Dustin G. and Nelson, Aaron A.},
title = {Saving phase: Injectivity and stability for phase retrieval},
journal = {Applied and Computational Harmonic Analysis},
volume = {37},
pages = {106--125},
year = {2014}
}
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00037, "The Balan–Wang conjecture on the stability of real phase retrieval", clopen.solutions.