Pith. sign in

REVIEW 8 minor 58 references

Four-plus-delta moments suffice for low-rank matrix recovery

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · glm-5.2

2026-07-10 03:14 UTC pith:CSGXIG5J

load-bearing objection Extends optimal O(rn) low-rank matrix recovery from sub-Gaussian to finite 4+δ-moment sampling via decoupling and heavy-tailed covariance estimation

arxiv 2607.08671 v1 pith:CSGXIG5J submitted 2026-07-09 math.ST cs.ITmath.ITstat.TH

Low-Rank Matrix Recovery via Heavy-Tailed Quadratic Sampling

Gao Huang , Song Li This is my paper
classification math.ST cs.ITmath.ITstat.TH MSC 62H1294A1215B5260B20
keywords low-rank matrix recoveryheavy-tailed distributionsquadratic samplingphase retrievalnuclear norm minimizationsemidefinite programmingsmall ball methoddecoupling inequality
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proves that a rank-r Hermitian matrix can be recovered from m = O(rn) quadratic measurements of the form y_k = a_k* M a_k using standard convex programs (nuclear norm minimization or semidefinite-constrained empirical risk minimization), without any Gaussian or sub-Gaussian assumption on the sampling vectors. The only distributional requirement is that the entries of each sampling vector are independent, mean-zero, variance-one, and possess finite (4+δ)-th moments for some δ > 0, plus two identifiability conditions excluding degenerate cases like Bernoulli ±1 entries. Two technical tools make this possible: a decoupling-based moment bound for quadratic forms that replaces the usual Hanson-Wright inequality (which needs sub-Gaussian tails), and a covariance-estimation argument for heavy-tailed random matrices that controls the empirical process term in Mendelson's small ball method. As byproducts, the paper removes a logarithmic factor from the sample complexity of complex projective 4-design sampling and establishes stability of the phaseless operator under the same weak moment conditions.

Core claim

The central mechanism is that the rank null space property for the quadratic sampling operator can be established using only fourth-moment information (plus a δ-th moment for uniform high-probability control), by combining a decoupling argument for the quadratic form a*aMa with heavy-tailed covariance estimation of the matrix (1/m) Σ ε_k a_k a_k*. The decoupling step replaces sub-Gaussian concentration: it splits the diagonal and off-diagonal parts of the quadratic form, uses Rosenthal's inequality on each, and yields E|a*aMa|^p ≤ C_p(|Tr M|^p + α_{2p} ||M||_F^p) under only finite 2p-th moments. The covariance estimation step replaces covering-number arguments that fail for heavy tails, by a

What carries the argument

Decoupling inequality for quadratic forms (Theorem de la Peña) + Rosenthal's inequality for sums of independent heavy-tailed random variables + Paley-Zygmund lower bound on small ball function + heavy-tailed covariance matrix estimation (Tikhomirov / Jirak-Minsker-Shen-Wahl) + Rosenthal-type inequality for random matrices (Jirak-Minsker-Shen-Wahl) + Mendelson's small ball method + rank null space property framework (Kabanava-Kueng-Rauhut-Terstiege)

Load-bearing premise

The sampling vector entries must satisfy β = min_i E[|a_i|^4] > 1 and |E[a_i^2]| < 1, which excludes distributions where |a| is constant (like Bernoulli ±1), because in that case different rank-one basis matrices produce identical measurements and become indistinguishable.

What would settle it

Construct a distribution with finite (4+δ)-th moments satisfying the stated conditions but for which the empirical process term W_m or the small ball function Q_{2ξ} fails to achieve the required bounds at m = O(rn), causing the rank NSP to break down. Alternatively, find a heavy-tailed ensemble satisfying all assumptions where numerical experiments show a phase transition strictly above the predicted O(rn) threshold.

Watch this falsifier — get emailed when new claim-graph text bears on it.

If this is right

  • Phase retrieval (rank-one case) via PhaseLift is guaranteed under heavy-tailed sampling with only 4+δ moments, extending the theory to practical imaging modalities where illumination patterns may not be Gaussian.
  • Complex projective 4-design sampling achieves optimal O(rn) sample complexity for low-rank matrix recovery, removing the previous O(rn log n) barrier and improving derandomization guarantees for quantum state tomography.
  • The stability of the phaseless operator F_Ω holds under the same weak moment assumptions, providing Lipschitz-type lower bounds for the measurement map that are useful for analyzing nonconvex phase retrieval algorithms.
  • The decoupling-based moment bound for quadratic forms is a standalone tool that could be applied to other problems involving quadratic measurements of heavy-tailed random vectors, such as covariance sketching or blind deconvolution.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The 4+δ threshold appears to be a genuine barrier for this framework: the small ball analysis involves fourth moments of the entries through second-moment estimates of a*Ma, and the δ provides integrability for uniform control. Whether recovery is possible with exactly four moments (δ=0) or fewer remains open and would likely require a fundamentally different approach.
  • The constants in the sample complexity depend on α_{4+δ} through the factor α_{4+δ}^{32+12δ/((4+δ)δ)}, which grows rapidly as the (4+δ)-th moment increases. This suggests that while the O(rn) scaling is optimal, the practical sample size for very heavy-tailed distributions (e.g., α_{4+δ} large) could be substantially worse than the Gaussian benchmark, a gap not visible in the order notation.
  • The identifiability conditions β > 1 and |γ| < 1 exclude Bernoulli ±1 sampling, which is a standard ensemble in compressed sensing. Whether an alternative convex formulation or sampling model could bypass this identifiability obstruction for Bernoulli-type measurements is a natural question.
  • The extension to approximate complex projective t-designs (mentioned but not carried out) would require generalizing the covariance estimation lemma beyond the isotropic case, potentially connecting to effective-rank-based bounds.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

0 major / 8 minor

Summary. This paper studies the recovery of an (approximately) low-rank Hermitian matrix $M_0$ from $m$ quadratic measurements of the form $y_k = a_k^* M_0 a_k + noise$, using two convex programs: nuclear norm minimization (NNM, Eq. 4) and semidefinite-constrained empirical risk minimization (PSD-ERM, Eq. 5). The main contribution is proving that both methods achieve uniform, stable, and robust recovery with the optimal sample complexity $m = O(rn)$ under the assumption that the sampling vectors have independent, mean-zero, variance-one entries with only finite $(4+delta)$-th moments. This substantially weakens the Gaussian/sub-Gaussian assumptions prevalent in prior work. The proof combines the rank null space property (rank NSP) framework with Mendelson's small ball method, using two key technical ingredients: (1) a decoupling-based moment bound for quadratic forms (Proposition 4), and (2) a complex-valued covariance estimation result for heavy-tailed distributions (Theorem 3). As byproducts, the authors establish optimal sample complexity for complex projective 4-design sampling (Theorem 4, removing a log factor from prior work) and stability guarantees for phase retrieval under weak moment assumptions (Theorem 5).

Significance. The paper addresses a well-motivated gap in the low-rank matrix recovery and phase retrieval literature: most existing guarantees require Gaussian or sub-Gaussian sampling, while practical ensembles (e.g., in ghost imaging) may exhibit heavy tails. Achieving the information-theoretically optimal $O(rn)$ sample complexity under only finite $(4+delta)$-th moment assumptions is a meaningful advance. The two technical ingredients are well-chosen and potentially reusable: Proposition 4 provides a Hanson-Wright-type moment bound without sub-Gaussianity via decoupling and Rosenthal's inequality, and Theorem 3 adapts recent heavy-tailed covariance estimation results (Tikhomirov, Jirak-Minsker-Shen-Wahl) to the complex-valued, symmetrized setting. The improvement of the 4-design sample complexity from $O(rn log n)$ to $O(rn)$ is a clean corollary. The numerical experiments in Section 6, while basic, corroborate the theoretical predictions regarding phase transitions and noise robustness for a Student-$t_5$ ensemble. The proofs are modular and verifiable, with the main line of argument (small ball lower bound via Paley-Zygmund + Proposition 4; empirical process upper bound via Theorem 3; NSP

minor comments (8)
  1. In the proof of Theorem 3 (Section 3.3.1), Step 5 bounds the maximum terms $E max_k ||a_k||^2$ and $(E max_k ||a_k||^4)^{1/2}$ using a union bound over $m$ terms, yielding $n + sqrt(alpha_4 m n)$. This is then absorbed into the final bound $alpha_p^{2/p} sqrt(n/m) + n/m$. The absorption requires $m gtrsim alpha_4 n$, which is weaker than the stated $m gtrsim n$ but should be made explicit for the reader to verify the final simplification.
  2. The constants $f$, $g$, $h$ in equation (7) are quite involved (e.g., $f = alpha_{4+delta}^{32+12delta} (4+delta)^{delta/(4+delta)} / zeta^{3+8/delta}$). While Remark 1 acknowledges that optimality with respect to these constants is unknown, a brief comment on their scaling behavior (e.g., how they blow up as $delta to 0$ or as $alpha_{4+delta} to infty$) would help the reader assess practical applicability.
  3. In Section 6, the experimental setup uses $a = sqrt(3/10)(X + iY)$ with $X, Y sim t_5$. This ensemble has finite moments only up to order $q < 5$, so $delta < 1$ in the theory. It would be worth verifying and stating explicitly that conditions (6) on $beta$ and $gamma$ are satisfied for this distribution, to confirm that the experiments fall within the scope of the theorems.
  4. Remark 2 explains the necessity of $beta > 1$ and $gamma < 1$ by showing that Bernoulli $pm 1$ entries lead to indistinguishable rank-one basis matrices. This is a clear and important point. It might be worth adding a sentence noting that these conditions are satisfied by standard heavy-tailed distributions (e.g., Student-$t$ with appropriate normalization), so the reader understands the restrictions are not vacuous beyond heavy-tailedness.
  5. In equation (39) of Section 3.5, the eigenvalue bounds on $W$ are stated as holding with probability at least $1 - e^{-2n} - 1/(10 m^{delta/4}) - tilde{c}(delta)/m$. The term $1/(10 m^{delta/4})$ comes from Fact 2, but the exponent $delta/4$ appears without explicit derivation in the main text (it is in Appendix C). A forward reference to Appendix C at equation (39) would improve readability.
  6. The notation $M_{r,c} := M - M_r$ for the residual part is introduced in the notation paragraph after the main results, but it appears earlier in Theorem 1. Consider defining it at first use.
  7. Reference [2] is listed as 'In preparation, 2026.' Since this work is cited in Remark 10 regarding related stability results for the amplitude model, the authors should ensure the reference is available or replace it with a more stable citation if possible.
  8. In the proof of Lemma 7 (Section 4), the step applying Lemma 6 with $p = 6$ notes that $a$ is not centered but the random phase construction handles this. A one-sentence justification of why the random phase $e^{i theta} a$ preserves the sampling matrix $a a^*$ (namely $e^{i theta} a (e^{i theta} a)^* = a a^*$) would make this step self-contained.

Circularity Check

0 steps flagged

No circularity found; derivation chain is self-contained against external benchmarks

full rationale

The paper's central theorems (Theorems 1 and 2) are parameter-free recovery guarantees with stated assumptions (finite (4+δ)-th moments, β>1, γ<1) that do not include the target result. The proof chain proceeds through: (1) rank NSP framework from [30] (external, Kabanava–Kueng–Rauhut–Terstiege), (2) Mendelson's small ball method from [34, 57] (external), (3) lower bound on Q_{2ξ} via Paley–Zygmund from [48] (external) + Lemma 3 from [37] (external, Krahmer–Stöger) + Proposition 4 (new, proven in-paper via decoupling from [58]), (4) upper bound on W_m via Theorem 3 (new, proven in-paper using covariance estimation from [56, 29] and Rosenthal-type matrix inequality from [29]). Each link is logically independent. The two novel ingredients—Proposition 4 (decoupling-based moment bound) and Theorem 3 (complex covariance estimation)—are fully proven within the paper using external tools. Self-citations [26, 27, 28] are not load-bearing: [26] appears only in contextual reference lists, [27] provides an alternative citation (alongside external [17]) for a standard distance inequality in the byproduct Theorem 5, and [28] is cited for context in the introduction. No step reduces to its own inputs by construction, and no self-citation chain carries the central argument.

Axiom & Free-Parameter Ledger

3 free parameters · 7 axioms · 0 invented entities

The paper introduces no new mathematical entities, particles, or postulated objects. All objects (sampling vectors, measurement matrices, Hermitian matrices, Rademacher sequences) are standard. The constants f, g, h in (7) are derived quantities, not postulated. The proof combines existing tools (decoupling, Rosenthal, small ball method, covariance estimation) in a new way.

free parameters (3)
  • δ = any positive real
    Controls the moment order 4+δ; smaller δ means weaker assumptions but larger constants. Not fitted to data but a free parameter of the theorem.
  • q = ≥1
    The ℓ_q norm parameter for the noise bound; chosen by the user, not derived.
  • ρ = 1/2 (chosen in proofs)
    Rank NSP constant; set to 1/2 at the end of the proof but any value in (0,1) works with adjusted constants.
axioms (7)
  • domain assumption Sampling vector entries are independent, mean-zero, variance-one
    Invoked in Theorem 1, equation (6). Standard in the quadratic sampling literature but a structural assumption on the measurement model.
  • domain assumption β = min_i E[|a_i|^4] > 1 and γ = max_i |E[a_i^2]| < 1
    Equation (6), Theorem 1. Identifiability condition excluding Bernoulli ±1 and phase-degenerate ensembles (Remark 2). Load-bearing: without it, rank-one matrices are indistinguishable.
  • standard math Mendelson's small ball method (Proposition 3)
    Section 3.1.2. External result from [34, 57] providing the lower bound framework for the empirical process.
  • standard math Rosenthal's inequality (equation 17)
    Invoked in Proposition 4 Step 2 and Theorem 3 Step 3. Standard moment inequality for sums of independent random variables.
  • standard math Decoupling inequality for quadratic forms
    Proposition 4 Step 3, citing [58, Theorem 6.1.1]. Standard tool from probability theory.
  • standard math Heavy-tailed covariance estimation (Lemma 4, from [56, 29])
    Section 3.3. External result providing the high-probability operator norm bound for sample covariance matrices under finite p-th moments.
  • standard math Rank NSP framework (Propositions 1-2, from [30])
    Section 3.1.1. External results connecting the Frobenius-robust rank NSP to recovery guarantees for programs (4) and (5).

pith-pipeline@v1.1.0-glm · 29277 in / 3329 out tokens · 408230 ms · 2026-07-10T03:14:31.742661+00:00 · methodology

0 comments
read the original abstract

The problem of recovering an (approximately) low-rank Hermitian matrix $\pmb{M}_0 \in \mathbb{C}^{n \times n}$ of rank $r$ from quadratic sampling matrices of the form $\{\pmb{a}_k \pmb{a}_k^*\}_{k=1}^m$ arises in a variety of applications, including phase retrieval. To obtain rigorous recovery guarantees, the sampling vectors $\{\pmb{a}_k\}_{k=1}^m$ are typically modeled probabilistically. However, most existing theoretical results rely on Gaussian or sub-Gaussian assumptions, which may not accurately capture practical data models. In many applications, sampling vectors exhibit heavier tails, while theoretical understanding in such regimes remains scarce. In this paper, we bridge this gap. We show that two widely used convex approaches, nuclear norm minimization and semidefinite-constrained empirical risk minimization, achieve uniform, stable, and robust recovery under the mild assumption that the entries of the sampling vectors have only finite $4+\delta$ moments, with the optimal sample complexity $m = \mathcal{O}(rn)$ up to moment-dependent constants. The two main ingredients of our analysis are moment estimates for quadratic forms established via decoupling, together with recent advances in covariance estimation in heavy-tailed settings. As byproducts, we also establish the optimal sample complexity for low-rank matrix recovery under complex projective $4$-design sampling, thereby improving upon previous results, and obtain stability guarantees for phase retrieval under similarly weak moment assumptions.

Figures

Figures reproduced from arXiv: 2607.08671 by Gao Huang, Song Li.

Figure 1
Figure 1. Figure 1: Phase transition for the Student-t5 and Gaussian ensembles. normalized noise level. Both the NNM model (4) and the PSD model (5) are included in the comparison. The dotted reference line has slope one. The curves are approx￾imately parallel to this reference line, indicating that the reconstruction error grows nearly linearly with the noise level. Moreover, the Student-t5 ensemble exhibits robust￾ness comp… view at source ↗
Figure 2
Figure 2. Figure 2: Noise robustness under the Student-t5 and Gaussian ensembles. A Proof of Fact 1 For completeness, we include the proof; see also equation (9) in [48]. Let Z, s, q, θ be as in Fact 1, and define E := {Z ≥ θ ∥Z∥Ls }. Since Z s < θs ∥Z∥ s Ls on E c , we have ∥Z∥ s Ls = E(Z s1E ) + E (Z s1E c ) ≤ E(Z s1E ) + θ s ∥Z∥ s Ls . (46) 26 [PITH_FULL_IMAGE:figures/full_fig_p026_2.png] view at source ↗

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

58 extracted references · 58 canonical work pages

  1. [1]

    Dictionary-sparse recovery from heavy- tailed measurements.Information and Inference: A Journal of the IMA, 11(4):1501–1526, 2022

    Pedro Abdalla and Christian K¨ ummerle. Dictionary-sparse recovery from heavy- tailed measurements.Information and Inference: A Journal of the IMA, 11(4):1501–1526, 2022

    work page 2022

  2. [2]

    Pedro Abdalla, Jo˜ ao P. G. Ramos, and Mitchell A. Taylor. In preparation, 2026

    work page 2026

  3. [3]

    Covariance estimation: Optimal dimension-free guarantees for adversarial corruption and heavy tails.Journal of the European Mathematical Society, 28(4):1809–1847, 2026

    Pedro Abdalla and Nikita Zhivotovskiy. Covariance estimation: Optimal dimension-free guarantees for adversarial corruption and heavy tails.Journal of the European Mathematical Society, 28(4):1809–1847, 2026

    work page 2026

  4. [4]

    Compressive multiplexing of correlated signals

    Ali Ahmed and Justin Romberg. Compressive multiplexing of correlated signals. IEEE Transactions on Information Theory, 61(1):479–498, 2014

    work page 2014

  5. [5]

    Chiang, Imants D

    Alaleh Aminzadeh, Lindon Roberts, Benjamin Young, Cheng I. Chiang, Imants D. Svalbe, David M. Paganin, and Andrew M. Kingston. Mask design, fabrication, and experimental ghost imaging applications for patterned X-ray illumination. Optics Express, 31(15):24328–24346, 2023

    work page 2023

  6. [6]

    Reconstruction of signals from magnitudes of redundant representa- tions: The complex case.Foundations of Computational Mathematics, 16(3):677– 721, 2016

    Radu Balan. Reconstruction of signals from magnitudes of redundant representa- tions: The complex case.Foundations of Computational Mathematics, 16(3):677– 721, 2016

    work page 2016

  7. [7]

    Painless reconstruction from magnitudes of frame coefficients.Journal of Fourier Analysis and Applications, 15(4):488–501, 2009

    Radu Balan, Bernhard G Bodmann, Peter G Casazza, and Dan Edidin. Painless reconstruction from magnitudes of frame coefficients.Journal of Fourier Analysis and Applications, 15(4):488–501, 2009

    work page 2009

  8. [8]

    Invertibility and robustness of phaseless reconstruc- tion.Applied and Computational Harmonic Analysis, 38(3):469–488, 2015

    Radu Balan and Yang Wang. Invertibility and robustness of phaseless reconstruc- tion.Applied and Computational Harmonic Analysis, 38(3):469–488, 2015

    work page 2015

  9. [9]

    Tony Cai and Anru Zhang

    T. Tony Cai and Anru Zhang. ROP: Matrix recovery via rank-one projections. The Annals of Statistics, 43(1):102–138, 2015

    work page 2015

  10. [10]

    Phase retrieval via matrix completion.SIAM Review, 57(2):225–251, 2015

    Emmanuel J Cand` es, Yonina C Eldar, Thomas Strohmer, and Vladislav Voronin- ski. Phase retrieval via matrix completion.SIAM Review, 57(2):225–251, 2015. 29

    work page 2015

  11. [11]

    Solving quadratic equations via PhaseLift when there are about as many equations as unknowns.Foundations of Computa- tional Mathematics, 14(5):1017–1026, 2014

    Emmanuel J Cand` es and Xiaodong Li. Solving quadratic equations via PhaseLift when there are about as many equations as unknowns.Foundations of Computa- tional Mathematics, 14(5):1017–1026, 2014

    work page 2014

  12. [12]

    Phase retrieval via Wirtinger flow: Theory and algorithms.IEEE Transactions on Information Theory, 61(4):1985–2007, 2015

    Emmanuel J Cand` es, Xiaodong Li, and Mahdi Soltanolkotabi. Phase retrieval via Wirtinger flow: Theory and algorithms.IEEE Transactions on Information Theory, 61(4):1985–2007, 2015

    work page 1985

  13. [13]

    PhaseLift: Exact and stable signal recovery from magnitude measurements via convex pro- gramming.Communications on Pure and Applied Mathematics, 66(8):1241–1274, 2013

    Emmanuel J Cand` es, Thomas Strohmer, and Vladislav Voroninski. PhaseLift: Exact and stable signal recovery from magnitude measurements via convex pro- gramming.Communications on Pure and Applied Mathematics, 66(8):1241–1274, 2013

    work page 2013

  14. [14]

    The convex geometry of linear inverse problems.Foundations of Computational Mathematics, 12(6):805–849, 2012

    Venkat Chandrasekaran, Benjamin Recht, Pablo A Parrilo, and Alan S Willsky. The convex geometry of linear inverse problems.Foundations of Computational Mathematics, 12(6):805–849, 2012

    work page 2012

  15. [15]

    Exact and stable covariance estimation from quadratic sampling via convex programming.IEEE Transactions on Information Theory, 61(7):4034–4059, 2015

    Yuxin Chen, Yuejie Chi, and Andrea J Goldsmith. Exact and stable covariance estimation from quadratic sampling via convex programming.IEEE Transactions on Information Theory, 61(7):4034–4059, 2015

    work page 2015

  16. [16]

    Stable optimizationless recovery from phaseless linear measurements.Journal of Fourier Analysis and Applications, 20(1):199–221, 2014

    Laurent Demanet and Paul Hand. Stable optimizationless recovery from phaseless linear measurements.Journal of Fourier Analysis and Applications, 20(1):199–221, 2014

    work page 2014

  17. [17]

    Solving (most) of a set of quadratic equalities: Composite optimization for robust phase retrieval.Information and Inference: A Journal of the IMA, 8(3):471–529, 2019

    John C Duchi and Feng Ruan. Solving (most) of a set of quadratic equalities: Composite optimization for robust phase retrieval.Information and Inference: A Journal of the IMA, 8(3):471–529, 2019

    work page 2019

  18. [18]

    Rieman- nian thresholding methods for row-sparse and low-rank matrix recovery.Numerical Algorithms, 93(2):669–693, 2023

    Henrik Eisenmann, Felix Krahmer, Max Pfeffer, and Andr´ e Uschmajew. Rieman- nian thresholding methods for row-sparse and low-rank matrix recovery.Numerical Algorithms, 93(2):669–693, 2023

    work page 2023

  19. [19]

    Phase retrieval: Stability and recovery guarantees.Applied and Computational Harmonic Analysis, 36(3):473–494, 2014

    Yonina C Eldar and Shahar Mendelson. Phase retrieval: Stability and recovery guarantees.Applied and Computational Harmonic Analysis, 36(3):473–494, 2014

    work page 2014

  20. [20]

    Quantum to- mography via compressed sensing: error bounds, sample complexity and efficient estimators.New Journal of Physics, 14(9):095022, 2012

    Steven T Flammia, David Gross, Yi-Kai Liu, and Jens Eisert. Quantum to- mography via compressed sensing: error bounds, sample complexity and efficient estimators.New Journal of Physics, 14(9):095022, 2012

    work page 2012

  21. [21]

    Iterative hard thresholding for low- rank recovery from rank-one projections.Linear Algebra and its Applications, 572:117–134, 2019

    Simon Foucart and Srinivas Subramanian. Iterative hard thresholding for low- rank recovery from rank-one projections.Linear Algebra and its Applications, 572:117–134, 2019

    work page 2019

  22. [22]

    Phase retrieval for sub-Gaussian mea- surements.Applied and Computational Harmonic Analysis, 53:95–115, 2021

    Bing Gao, Haixia Liu, and Yang Wang. Phase retrieval for sub-Gaussian mea- surements.Applied and Computational Harmonic Analysis, 53:95–115, 2021. 30

    work page 2021

  23. [23]

    Stable low-rank matrix recovery from 3-designs.Applied and Com- putational Harmonic Analysis, 84:101887, 2026

    Timm Gilles. Stable low-rank matrix recovery from 3-designs.Applied and Com- putational Harmonic Analysis, 84:101887, 2026

    work page 2026

  24. [24]

    A partial derandomization of PhaseLift using spherical designs.Journal of Fourier Analysis and Applications, 21(2):229–266, 2015

    David Gross, Felix Krahmer, and Richard Kueng. A partial derandomization of PhaseLift using spherical designs.Journal of Fourier Analysis and Applications, 21(2):229–266, 2015

    work page 2015

  25. [25]

    Quantum state tomography via compressed sensing.Physical Review Letters, 105(15):150401, 2010

    David Gross, Yi-Kai Liu, Steven T Flammia, Stephen Becker, and Jens Eisert. Quantum state tomography via compressed sensing.Physical Review Letters, 105(15):150401, 2010

    work page 2010

  26. [26]

    Low-rank Toeplitz matrix restoration: Descent cone anal- ysis and structured random matrix.IEEE Transactions on Information Theory, 71(5):3950–3956, 2025

    Gao Huang and Song Li. Low-rank Toeplitz matrix restoration: Descent cone anal- ysis and structured random matrix.IEEE Transactions on Information Theory, 71(5):3950–3956, 2025

    work page 2025

  27. [27]

    Stable phase retrieval: Optimal rates in Poisson and heavy-tailed models.arXiv preprint arXiv:2510.00551, 2025

    Gao Huang, Song Li, and Deanna Needell. Stable phase retrieval: Optimal rates in Poisson and heavy-tailed models.arXiv preprint arXiv:2510.00551, 2025

    work page arXiv 2025

  28. [28]

    Robust outlier bound condition to phase retrieval with adversarial sparse outliers.Applied and Computational Harmonic Analysis, 80:101819, 2026

    Gao Huang, Song Li, and Hang Xu. Robust outlier bound condition to phase retrieval with adversarial sparse outliers.Applied and Computational Harmonic Analysis, 80:101819, 2026

    work page 2026

  29. [29]

    Concentration and moment inequalities for sums of independent heavy-tailed random matrices

    Moritz Jirak, Stanislav Minsker, Yiqiu Shen, and Martin Wahl. Concentration and moment inequalities for sums of independent heavy-tailed random matrices. Probability Theory and Related Fields, 194:1917–1944, 2026

    work page 1917

  30. [30]

    Stable low-rank matrix recovery via null space properties.Information and Inference: A Journal of the IMA, 5(4):405–441, 2016

    Maryia Kabanava, Richard Kueng, Holger Rauhut, and Ulrich Terstiege. Stable low-rank matrix recovery via null space properties.Information and Inference: A Journal of the IMA, 5(4):405–441, 2016

    work page 2016

  31. [31]

    Cambridge University Press, 2 edition, 1985

    Jean-Pierre Kahane.Some Random Series of Functions, volume 5 ofCambridge Studies in Advanced Mathematics. Cambridge University Press, 2 edition, 1985

    work page 1985

  32. [32]

    Robust phase retrieval by alternating minimization

    Seonho Kim and Kiryung Lee. Robust phase retrieval by alternating minimization. IEEE Transactions on Signal Processing, 73:40–54, 2024

    work page 2024

  33. [33]

    Optimizing nonconfigurable, transversely displaced masks for illumination patterns in classical ghost imaging.Physical Re- view A, 107(2):023524, 2023

    Andrew M Kingston, Alaleh Aminzadeh, Lindon Roberts, Daniele Pelliccia, Imants D Svalbe, and David M Paganin. Optimizing nonconfigurable, transversely displaced masks for illumination patterns in classical ghost imaging.Physical Re- view A, 107(2):023524, 2023

    work page 2023

  34. [34]

    Bounding the smallest singular value of a random matrix without concentration.International Mathematics Re- search Notices, 2015(23):12991–13008, 2015

    Vladimir Koltchinskii and Shahar Mendelson. Bounding the smallest singular value of a random matrix without concentration.International Mathematics Re- search Notices, 2015(23):12991–13008, 2015

    work page 2015

  35. [35]

    Matrix factorization techniques for recommender systems.Computer, 42(8):30–37, 2009

    Yehuda Koren, Robert Bell, and Chris Volinsky. Matrix factorization techniques for recommender systems.Computer, 42(8):30–37, 2009. 31

    work page 2009

  36. [36]

    On the robustness of noise-blind low-rank recovery from rank-one measurements.Linear Algebra and its Applications, 652:37–81, 2022

    Felix Krahmer, Christian K¨ ummerle, and Oleh Melnyk. On the robustness of noise-blind low-rank recovery from rank-one measurements.Linear Algebra and its Applications, 652:37–81, 2022

    work page 2022

  37. [37]

    Complex phase retrieval from subgaussian measurements.Journal of Fourier Analysis and Applications, 26(6):89, 2020

    Felix Krahmer and Dominik St¨ oger. Complex phase retrieval from subgaussian measurements.Journal of Fourier Analysis and Applications, 26(6):89, 2020

    work page 2020

  38. [38]

    On the convex geometry of blind deconvolu- tion and matrix completion.Communications on Pure and Applied Mathematics, 74(4):790–832, 2021

    Felix Krahmer and Dominik St¨ oger. On the convex geometry of blind deconvolu- tion and matrix completion.Communications on Pure and Applied Mathematics, 74(4):790–832, 2021

    work page 2021

  39. [39]

    Low rank matrix recovery from rank one measurements.Applied and Computational Harmonic Analysis, 42(1):88–116, 2017

    Richard Kueng, Holger Rauhut, and Ulrich Terstiege. Low rank matrix recovery from rank one measurements.Applied and Computational Harmonic Analysis, 42(1):88–116, 2017

    work page 2017

  40. [40]

    Sparse recovery under weak moment assumptions.Journal of the European Mathematical Society, 19(3):881–904, 2017

    Guillaume Lecu´ e and Shahar Mendelson. Sparse recovery under weak moment assumptions.Journal of the European Mathematical Society, 19(3):881–904, 2017

    work page 2017

  41. [41]

    Truncated amplitude flow with coded diffraction patterns

    Huiping Li and Jiayi Li. Truncated amplitude flow with coded diffraction patterns. Inverse Problems, 41(1):015002, 2025

    work page 2025

  42. [42]

    Nonconvex matrix factor- ization from rank-one measurements.IEEE Transactions on Information Theory, 67(3):1928–1950, 2021

    Yuanxin Li, Cong Ma, Yuxin Chen, and Yuejie Chi. Nonconvex matrix factor- ization from rank-one measurements.IEEE Transactions on Information Theory, 67(3):1928–1950, 2021

    work page 1928

  43. [43]

    Interior-point method for nuclear norm approximation with application to system identification.SIAM Journal on Matrix Analysis and Applications, 31(3):1235–1256, 2010

    Zhang Liu and Lieven Vandenberghe. Interior-point method for nuclear norm approximation with application to system identification.SIAM Journal on Matrix Analysis and Applications, 31(3):1235–1256, 2010

    work page 2010

  44. [44]

    Acceleration and implicit regulariza- tion in Gaussian phase retrieval

    Tyler Maunu and Martin Molina-Fructuoso. Acceleration and implicit regulariza- tion in Gaussian phase retrieval. InProceedings of the 27th International Confer- ence on Artificial Intelligence and Statistics, volume 238 ofProceedings of Machine Learning Research, pages 4060–4068. PMLR, 2024

    work page 2024

  45. [45]

    Andrew D. McRae. Phase retrieval and matrix sensing via benign and over- parametrized nonconvex optimization.IEEE Transactions on Information The- ory, 72(6):4203–4220, 2026

    work page 2026

  46. [46]

    Learning without concentration.Journal of the ACM (JACM), 62(3):1–25, 2015

    Shahar Mendelson. Learning without concentration.Journal of the ACM (JACM), 62(3):1–25, 2015

    work page 2015

  47. [47]

    R. P. Millane. Phase retrieval in crystallography and optics.Journal of the Optical Society of America A, 7(3):394–411, 1990

    work page 1990

  48. [48]

    On lower bounds for tail probabilities.Journal of Statistical Planning and Inference, 137(8):2703–2705, 2007

    Valentin V Petrov. On lower bounds for tail probabilities.Journal of Statistical Planning and Inference, 137(8):2703–2705, 2007. 32

    work page 2007

  49. [49]

    A general algorithm for solving rank- one matrix sensing

    Lianke Qin, Zhao Song, and Ruizhe Zhang. A general algorithm for solving rank- one matrix sensing. InInternational Conference on Artificial Intelligence and Statistics, volume 238 ofProceedings of Machine Learning Research, pages 757–

    work page

  50. [50]

    Eldar, and John Wright

    Qing Qu, Yuqian Zhang, Yonina C. Eldar, and John Wright. Convolutional phase retrieval via gradient descent.IEEE Transactions on Information Theory, 66(3):1785–1821, 2020

    work page 2020

  51. [51]

    Low-rank matrix recovery via rank one tight frame measurements.Journal of Fourier Analysis and Applications, 25(2):588– 593, 2019

    Holger Rauhut and Ulrich Terstiege. Low-rank matrix recovery via rank one tight frame measurements.Journal of Fourier Analysis and Applications, 25(2):588– 593, 2019

    work page 2019

  52. [52]

    Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization.SIAM Review, 52(3):471–501, 2010

    Benjamin Recht, Maryam Fazel, and Pablo A Parrilo. Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization.SIAM Review, 52(3):471–501, 2010

    work page 2010

  53. [53]

    On the subspaces ofl p (p >2) spanned by sequences of independent random variables.Israel Journal of Mathematics, 8(3):273–303, 1970

    Haskell P Rosenthal. On the subspaces ofl p (p >2) spanned by sequences of independent random variables.Israel Journal of Mathematics, 8(3):273–303, 1970

    work page 1970

  54. [54]

    Hanson-Wright inequality and sub- Gaussian concentration.Electronic Communications in Probability, 18:1–9, 2013

    Mark Rudelson and Roman Vershynin. Hanson-Wright inequality and sub- Gaussian concentration.Electronic Communications in Probability, 18:1–9, 2013

    work page 2013

  55. [55]

    Phase retrieval with application to optical imaging: a contemporary overview.IEEE Signal Processing Magazine, 32(3):87–109, 2015

    Yoav Shechtman, Yonina C Eldar, Oren Cohen, Henry Nicholas Chapman, Jianwei Miao, and Mordechai Segev. Phase retrieval with application to optical imaging: a contemporary overview.IEEE Signal Processing Magazine, 32(3):87–109, 2015

    work page 2015

  56. [56]

    Sample covariance matrices of heavy-tailed distributions

    Konstantin Tikhomirov. Sample covariance matrices of heavy-tailed distributions. International Mathematics Research Notices, 2018(20):6254–6289, 2018

    work page 2018

  57. [57]

    Joel A. Tropp. Convex recovery of a structured signal from independent random linear measurements. InSampling Theory, a Renaissance: Compressive Sensing and Other Developments, pages 67–101. Birkh¨ auser, 2015

    work page 2015

  58. [58]

    Cambridge University Press, 2018

    Roman Vershynin.High-Dimensional Probability: An Introduction with Applica- tions in Data Science, volume 47. Cambridge University Press, 2018. 33

    work page 2018