Pith. sign in

REVIEW 3 major objections 4 minor 77 references

A High-Dimensional Statistical Theory for Convex and Nonconvex Matrix Sensing

T0 review · 3 major / 4 minor · reviewed 2026-08-06 · deepseek-v4-flash

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

Pith's one-line read The paper proves that in high-dimensional Gaussian matrix sensing, every local minimum of the nonconvex factorized estimator concentrates like hard-thresholding the singular values of a denoised observation matrix, while the convex…

desk verdict First precise asymptotic equivalence between convex/nonconvex matrix sensing and soft/hard thresholding; substantial and probably right, but the written proof has a fixable gap in the debiasing step and a sign typo in the main probability bounds. read the letter →

arxiv 2506.20659 v1 pith:IJPQSAGH submitted 2025-06-25 math.ST math.OCstat.TH

Joshua Agterberg , René Vidal This is my paper · ORCID
classification math.STmath.OCstat.TH MSC 62F1262J0760B2090C26
keywords matrixsensingtraceregressionnonconvexfactorizationnuclearnormregularizationconvexGaussianmin-maxtheoremdenoisinghardthresholdingsoft
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

This paper asks a sharp question: in matrix sensing, where a low-rank matrix is recovered from noisy linear measurements, which estimator is actually better, the convex nuclear-norm regularized one or the nonconvex factorized one? It proves that in a high-dimensional Gaussian model with the rank known and the signal strong enough, the answer separates cleanly: the convex estimator behaves asymptotically like soft-thresholding the singular values of M + σH, while the nonconvex estimator behaves like hard-thresholding, i.e., best rank-r truncation, of the same denoised matrix. Because known-rank hard thresholding has smaller mean-squared error than soft thresholding in this regime, the nonconvex estimator uniformly dominates the convex one. The equivalence is stated as concentration of every 1-Lipschitz function, so it is a distributional statement rather than only an error-rate bound.

What carries the argument

The argument runs through four linked equivalences. First, a deterministic theorem shows that on a high-probability 'good event' (bounded noise operator, restricted isometry), any local minimum of the regularized nonconvex problem equals the convex minimizer, U(λ)U(λ)⊤ = Z(λ). Second, a new Matrix CGMT (a matrix-ensemble generalization of the Convex Gaussian Min-Max Theorem) translates the convex program into a scalar fixed-point system whose solution (τ*, ζ*) is nearly (σ, 1), yielding concentration of Z(λ) around the soft-thresholding estimator Z_ST(λ/ζ*)(τ*). Third, 'debiased' versions of both estimators, which add λ back to the top singular values, concentrate around hard thresholding. Fourth, and only requiring n ≫ dr², the debiased estimator is shown to be close to the unregularized local minimum U(0). The key technical insight is that the CGMT-reduced objective, though not strongly convex on the positive semidefinite cone, becomes strongly convex when restricted to rank-r matrices.

What would settle it

Run GOE matrix sensing with d = 200, r = 2, n = Cdr² and a strong signal (λ_r/σ = 4√r), compare the normalized mean-squared error of U(0)U(0)⊤ against the rank-r truncation of M + σH, and compute the MSE ratio of Corollary 1; if the gap exceeds the theorem's stated rate Cσr√(d/n) by a divergent factor, or if the asymptotic MSE ratio falls below one, the claim fails. A scan across weaker signals (λ_r/σ = 2, 1, 0.5) can locate the regime where the dominance reverses.

Watch

Extended reading notes

Core claim

The central discovery is that the convex/nonconvex choice in matrix sensing mirrors the soft/hard thresholding choice in matrix denoising. For the nonconvex factorized estimator with known rank and no regularization, U(0)U(0)⊤/√(dr) concentrates, for every 1-Lipschitz function φ, around E_H φ(Z_HT/√(dr)), where Z_HT is the best rank-r approximation of M + σH; for the convex estimator Z(λ), the same concentration holds around the soft-thresholding estimator Z_ST(λ) of M + σH, with explicit vanishing tail bounds. A corollary concludes that the nonconvex estimator has asymptotically no larger squared error than the convex one, with strict inequality for generic signal spectra, which makes the convex estimator inadmissible in this regime.

Load-bearing premise

The comparison rests on the structural model: known rank r, signal strong enough that the smallest eigenvalue satisfies λ_r/σ ≥ C√r, and sample size n ≥ Cdr², and the paper itself notes that the final equivalence step essentially requires n ≫ dr²; if the signal is weak, the rank is misspecified, or the sample size is only of order dr, the uniform dominance conclusion does not follow.

Editorial extensions

If this is right

  • The nonconvex factorized estimator with known rank matches the asymptotic distribution of the best rank-r approximation of M + σH, so it can be used for entrywise statistical inference without debiasing; the convex estimator requires explicit debiasing.
  • In the regime d ≪ n ≪ d² with rank fixed, the convex nuclear-norm estimator is asymptotically inadmissible relative to the nonconvex estimator under squared error.
  • The soft/hard thresholding dichotomy transfers from matrix denoising to matrix sensing: both estimators' asymptotics are read off from the fixed-point system (τ*, ζ*) ≈ (σ, 1).
  • Since the equivalence holds for every 1-Lipschitz function, it implies convergence in distribution, which opens the door to confidence intervals and tests inherited from matrix denoising.
  • The dominance result presupposes the true rank is known; overestimating r is not covered by the theory.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • If the reduction to denoising is exact, then the known phase-transition results for optimal hard thresholds in matrix denoising likely transfer to sensing, meaning the truncation level or regularization strength could be tuned from the denoising surrogate alone without new sensing-specific analysis.
  • The paper's simulations show the convex estimator wins when the signal-to-noise ratio is below one; a natural extension is to locate the precise SNR phase transition where dominance flips and to test whether it coincides with the optimal-hard-threshold boundary in denoising.
  • The equivalence suggests a route to adaptive rank selection for the nonconvex estimator: rank could be chosen by thresholding singular values of the data matrix, since the estimator is claimed to behave like a pure denoising truncation.
  • A finite-sample test of the theory is to measure the gap between U(0)U(0)⊤ and Z_HT across n, d, r and check whether it tracks the theorem's stated rate Cσr√(d/n).
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

3 major / 4 minor

Summary. This paper develops a high-dimensional asymptotic theory for symmetric matrix sensing under Gaussian measurements and noise. The main result, Theorem 1, states that for an appropriate scaling, every local minimum of the nonconvex factorized estimator behaves like matrix hard thresholding of a denoising problem, while the convex nuclear-norm estimator behaves like matrix soft thresholding of the same denoising problem; a corollary concludes that the nonconvex estimator has asymptotically no larger mean-squared error. The proof strategy combines a new matrix generalization of the Convex Gaussian Min-Max Theorem, a deterministic equivalence between convex and nonconvex regularized estimators on a 'good' event, a fixed-point characterization of soft-thresholding parameters, and a debiasing argument that connects the unregularized nonconvex estimator to hard-thresholding. The paper is largely self-contained, with detailed appendices for the CGMT proof, the fixed-point analysis, and the debiasing steps.

Significance. If the results are correct, this is a substantial contribution: it provides the first precise statistical comparison between convex and nonconvex matrix sensing estimators in a high-dimensional regime, establishes a distributional equivalence to classical matrix denoising procedures, and proves a uniform MSE dominance of the known-rank nonconvex estimator over the convex estimator. The matrix CGMT (Theorem 3) and the deterministic local-minima equivalence (Theorem 2) are likely to be of independent interest. The paper is also unusually candid about limitations, including the requirement n >> dr^2 for the final debiasing step, the restriction to known rank, the symmetric PSD model, and the failure of nonconvex dominance in weak-signal regimes. However, as discussed below, several theorem statements in the current draft contain significant local gaps that must be repaired before the main claims can be accepted.

major comments (3)
  1. [Theorem 6, Section 4.2, Eqs. (75) and (87)-(90)] The proof of Theorem 6 applies Theorem 4 to eφ = φ∘eη, but the expectation on the right-hand side is then E eφ(Z_ST^{(λ/ζ*)}(τ*)/√(dr)) = E φ(eη(Z_ST^{(λ/ζ*)}(τ*)/√(dr))), not E φ(Z_HT^{(λ)}/√(dr)). For positive singular values s_i of M + τ*H, the matrix eη(Z_ST^{(λ/ζ*)}(τ*)/√(dr)) has singular values (s_i − λ/ζ* + λ)/√(dr) = s_i/√(dr) + λ(1 − 1/ζ*)/√(dr), whereas Z_HT^{(λ)}/√(dr) has singular values s_i/√(dr). This is a deterministic mismatch whose Frobenius norm is λ|1 − 1/ζ*|/√d = O(σ dr^{3/2}/n) by Lemma 6. Since the fixed-point equations of Lemma 6 do not force ζ* = 1, Theorem 6 as stated cannot hold for fixed ε in regimes where this mismatch is not negligible. The proof is missing an explicit additive bias term and a triangle-inequality step; the mismatch can be absorbed into Theorem 1's tolerance only when n >> dr^2, not under Assumptions 1-3 alone. A related issue is that the replacement eη = η on the soft-thresholding matrix requires Z_ST^{(λ/ζ*)}(τ*) to lie in the set S of Eq. (79), which is only known on the high-probability rank event of Lemma 11; this event is not incorporated in the displayed chain.
  2. [Theorem 4 Eq. (52), Theorem 6 Eq. (76), Lemma 9] The probability bounds contain minus signs before the final exponential term: Theorem 4 states O(exp(−cd) + exp(−cdr) + exp(−cn) + ε^{-2} exp(−cdrε^4) − exp(−(dr)^2/n ε^4)), and the same minus sign appears in Theorem 6 and in the proof line (90); Lemma 9 similarly states a probability of at least 1 − O(exp(−cdr) − exp(−cn)). As written, an expression O(A − B) is not a valid upper tail bound because it can be negative, and 1 − O(A − B) can exceed one. These should be plus signs throughout. This is a typographical error, but it occurs inside the main theorem statements and must be corrected.
  3. [Theorem 6 proof, application of Lemma 11] Even after correcting the ζ* mismatch, the proof of Theorem 6 needs to explicitly handle the event that Z_ST^{(λ/ζ*)}(τ*) is not in the set S of Eq. (79). Lemma 11 guarantees rank ≤ r and spectral-norm bounds only with probability 1 − C exp(−cd), and outside this event the Lipschitz extension eη need not coincide with η. The displayed chain (87)-(90) does not include this event, so the final bound is missing a term of order exp(−cd) unless the proof is modified to incorporate Lemma 11 and control the expectation of φ(eη(Z_ST)) on the complement.
minor comments (4)
  1. [Theorem 7 proof, Eq. (117)] The display after rearrangement should read ∥U_deb^{(λ)} − U(0)∥_F ≤ (80κ/λmax(M)) ∥∇f_ncvx^{(0)}(U_deb^{(λ)})∥_F, not (80 κ λmax(M)) times the gradient; the subsequent algebra indicates that the division by λmax(M) is what is intended.
  2. [Section 1.6, final bullet] The sentence 'one of our major results shows that the nonconvex formulation with correctly specified rank dominates the nonconvex formulation' should say 'dominates the convex formulation.'
  3. [Throughout] There are several typos that should be cleaned up, including 'Lipchitz' in the abstract, 'veector' in Section 1.1, and inconsistent spacing in displayed equations such as Eq. (11) and Eq. (12).
  4. [Theorem 4 remark, after Eq. (52)] The remark that the C√r/γn error term in Theorem 1 can be eliminated by using Z_ST^{(λ/ζ*)}(τ*) is helpful, but it would be clearer to state explicitly that this replacement requires Lemma 7 and that the O(σ dr^{3/2}/n) bias of Lemma 7 is what produces the final tolerance in Theorem 1.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the soft/hard-thresholding targets are derived from deterministic fixed-point equations via the Matrix CGMT, not fitted or imposed.

full rationale

The paper's derivation chain is self-contained. Theorem 4 states concentration of Z(λ) (and U(λ)U(λ)^T) about Z_ST^{(λ/ζ*)}(τ*), where (τ*,ζ*) are defined as the solutions of the deterministic fixed-point system (46) depending only on model parameters and expectations over the GOE noise H; they are not fit to the observed estimator. Lemma 4 derives these equations from first-order conditions of ψ*, Lemma 5 proves existence and uniqueness, and Lemma 6 bounds τ*−σ and ζ*−1. Lemma 7 then controls replacement of Z_ST^{(λ/ζ*)}(τ*) by the standard soft-thresholding estimator Z_ST(λ), and Lemma 8 similarly controls Z_HT^{(λ)} versus Z_HT. Theorem 6 obtains concentration of the debiased estimator by applying Theorem 4 to a Lipschitz extension of the eigenvalue-shift map η; this is a derivation, not an assumption of the conclusion. Theorem 7 relates U(0) to the debiased estimator by gradient and Hessian estimates (Lemmas 9–10), with the n ≫ dr² requirement explicitly acknowledged. Corollary 1 uses the external, independently derived Gavish–Donoho asymptotic MSE formulas, which are not fitted to the paper's estimates. The paper's self-citations (e.g., Haeffele et al. 2014 in related-work discussion) are not load-bearing for the main theorems. The skeptic-flagged ζ*≠1 mismatch in Theorem 6 is a possible missing additive bias term, i.e., a proof correctness issue, not a circular reduction of the claimed conclusion to its inputs. No load-bearing step equates a fitted parameter with a prediction or defines a target in terms of the estimator itself.

Assumptions & free parameters 1 free parameters · 6 assumptions · 0 invented entities

The central claim is conditional on the Gaussian symmetric model, strong signal, known rank, and the sample-size regime. No new particles or forces are introduced; the debiased estimators Z_deb and U_deb are data-computable constructions rather than postulated latent quantities. The fixed-point parameters τ* and ζ* are deterministic functions of the model and the thresholding rule, not free parameters fitted to the data being predicted.

free parameters (1)
  • λ (regularization parameter) = C σ√d with a fixed C in [C4,C5] (not data-fitted)
    Tuning parameter of the convex and nonconvex estimators. Assumption 3 fixes its order; the theorems hold for any fixed λ in this range and the constants depend on C4,C5.
assumptions (6)
  • domain assumption Gaussian design and Gaussian noise: X_i ∼ GOE(d), ε_i ∼ N(0,σ²), with σ ≥ σ_min > 0
    The full model is specified in Equation (7); all results rely on Gaussianity and symmetry, as the authors acknowledge.
  • domain assumption M is symmetric PSD of known rank r with spectral structure satisfying Assumption 1 (λ_r/σ ∈ [C1√r, C2√r], κ=O(1))
    This strong-signal condition is needed for eigenspace identifiability, for the landscape arguments, and for the sign of the MSE comparison; the paper's own experiments show the ordering can reverse when it fails.
  • domain assumption Sample size n ≥ C3 d r² and n ≪ (dr)² (Assumption 2)
    Ensures the restricted-isometry event EGood with δ_{2r}=c√r and makes the error terms involving √(d/n) vanish; Theorem 7 is the step essentially requiring n ≫ dr².
  • standard math Restricted isometry property for the GOE measurement operator (Lemma 1) and standard RIP lemmas for low-rank matrices
    Used in Theorem 2 and in the Hessian computations; these follow from known random matrix results and are stated as lemmas with proofs.
  • standard math Geodesic convexity of the fixed-rank matrix manifold (Luo and Trillos 2022, cited theorems)
    Invoked in Lemma 10 to control the Hessian of the unregularized loss along the geodesic between U(0) and the debiased estimator.
  • standard math Gaussian comparison inequality (Theorem G.2 of Miolane and Montanari 2021) and Sion's minimax theorem
    They underpin the proof of the Matrix CGMT (Theorem 3, Appendix A.5), the paper's main technical engine.

how reviews work

0 comments
Cite this review

Pith. "Pith review of A High-Dimensional Statistical Theory for Convex and Nonconvex Matrix Sensing." pith.science (2026). https://pith.science/paper/IJPQSAGH

@misc{pith2026250620659,
  author       = {Pith},
  title        = {Pith review of: A High-Dimensional Statistical Theory for Convex and Nonconvex Matrix Sensing},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/IJPQSAGH}},
  note         = {Machine review of arXiv:2506.20659}
}
read the original abstract

The problem of matrix sensing, or trace regression, is a problem wherein one wishes to estimate a low-rank matrix from linear measurements perturbed with noise. A number of existing works have studied both convex and nonconvex approaches to this problem, establishing minimax error rates when the number of measurements is sufficiently large relative to the rank and dimension of the low-rank matrix, though a precise comparison of these procedures still remains unexplored. In this work we provide a high-dimensional statistical analysis for symmetric low-rank matrix sensing observed under Gaussian measurements and noise. Our main result describes a novel phenomenon: in this statistical model and in an appropriate asymptotic regime, the behavior of any local minimum of the nonconvex factorized approach (with known rank) is approximately equivalent to that of the matrix hard-thresholding of a corresponding matrix denoising problem, and the behavior of the convex nuclear-norm regularized least squares approach is approximately equivalent to that of matrix soft-thresholding of the same matrix denoising problem. Here "approximately equivalent" is understood in the sense of concentration of Lipchitz functions. As a consequence, the nonconvex procedure uniformly dominates the convex approach in mean squared error. Our arguments are based on a matrix operator generalization of the Convex Gaussian Min-Max Theorem (CGMT) together with studying the interplay between local minima of the convex and nonconvex formulations and their "debiased" counterparts, and several of these results may be of independent interest.

Figures

Figures reproduced from arXiv: 2506.20659 by the authors.

Figure 1
Figure 1. For varying n ∈ {1000, 2000, 3000}, we generate M by first drawing a random matrix U of dimension n × r with entries N (0, 1) and setting Mf := UU ⊤. We then define M by setting the smallest nonzero singular value of Mf to be √ d. We control the SNR by varying σ ∈ {1/2, 1, 2} corresponding to an SNR of {2, 1, 1/2} respectively. We take λ = 0.5σ √ d in all simulations. To estimate U(0) we run gradient descent on f (0… view at source ↗
Figure 2
Figure 2. Diagram of Proof Dependencies well-behaved, which can be handled directly via techniques from random matrix theory. In addition, the other condition is that X ∗X behaves approximately as the identity operator on rank at most 2r matrices, which is known as the restricted isometry property in the literature. In particular, one formulation of the restricted isometry property is that X satisfies (1 − δ2r)∥A∥F ≤ ∥X ∗X (A… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

77 extracted references · 46 canonical work pages

  1. [1]

    Bandeira and Ramon van Handel

    Afonso S. Bandeira and Ramon van Handel. Sharp nonasymptotic bounds on the norm of random matrices with independent entries. The Annals of Probability, 44 0 (4): 0 2479--2506, July 2016. ISSN 0091-1798, 2168-894X. doi:10.1214/15-AOP1025

    doi:10.1214/15-aop1025 2016

  2. [2]

    The LASSO Risk for Gaussian Matrices

    Mohsen Bayati and Andrea Montanari. The LASSO Risk for Gaussian Matrices . IEEE Transactions on Information Theory, 58 0 (4): 0 1997--2017, April 2012. ISSN 1557-9654. doi:10.1109/TIT.2011.2174612

    work page arXiv 1997

  3. [3]

    Existence of solutions to the nonlinear equations characterizing the precise error of M-estimators

    Pierre C. Bellec and Takuya Koriyama. Existence of solutions to the nonlinear equations characterizing the precise error of M -estimators, October 2024. arXiv:2312.13254 [math]

    work page Pith review arXiv 2024

  4. [4]

    Bellec and Cun-Hui Zhang

    Pierre C. Bellec and Cun-Hui Zhang. Debiasing convex regularized estimators and interval estimation in linear models. The Annals of Statistics, 51 0 (2): 0 391--436, April 2023. ISSN 0090-5364, 2168-8966. doi:10.1214/22-AOS2243

    doi:10.1214/22-aos2243 2023

  5. [5]

    The eigenvalues and eigenvectors of finite, low rank perturbations of large random matrices

    Florent Benaych-Georges and Raj Rao Nadakuditi. The eigenvalues and eigenvectors of finite, low rank perturbations of large random matrices. Advances in Mathematics, 227 0 (1): 0 494--521, May 2011. ISSN 0001-8708. doi:10.1016/j.aim.2011.02.007

    doi:10.1016/j.aim.2011.02.007 2011

  6. [6]

    State evolution for approximate message passing with non-separable functions

    Raphaël Berthier, Andrea Montanari, and Phan-Minh Nguyen. State evolution for approximate message passing with non-separable functions. Information and Inference: A Journal of the IMA, 9 0 (1): 0 33--79, March 2020. ISSN 2049-8772. doi:10.1093/imaiai/iay021

    doi:10.1093/imaiai/iay021 2020

  7. [7]

    Global Optimality of Local Search for Low Rank Matrix Recovery

    Srinadh Bhojanapalli, Behnam Neyshabur, and Nati Srebro. Global Optimality of Local Search for Low Rank Matrix Recovery . In Advances in Neural Information Processing Systems , volume 29. Curran Associates, Inc., 2016

    work page 2016

  8. [8]

    Monteiro

    Samuel Burer and Renato D.C. Monteiro. A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization. Mathematical Programming, 95 0 (2): 0 329--357, February 2003. ISSN 1436-4646. doi:10.1007/s10107-002-0352-8

    doi:10.1007/s10107-002-0352-8 2003

Show all 77 references
  1. [9]

    Tony Cai and Anru Zhang

    T. Tony Cai and Anru Zhang. Rate-optimal perturbation bounds for singular subspaces with applications to high-dimensional statistics. The Annals of Statistics, 46 0 (1): 0 60--89, February 2018. ISSN 0090-5364, 2168-8966. doi:10.1214/17-AOS1541

    2018 doi

  2. [10]

    Tony Cai, Xiaodong Li, and Zongming Ma

    T. Tony Cai, Xiaodong Li, and Zongming Ma. Optimal rates of convergence for noisy sparse phase retrieval via thresholded Wirtinger flow. The Annals of Statistics, 44 0 (5): 0 2221--2251, October 2016 a . ISSN 0090-5364, 2168-8966. doi:10.1214/16-AOS1443

    2016 doi

  3. [11]

    Tony Cai, Tengyuan Liang, and Alexander Rakhlin

    T. Tony Cai, Tengyuan Liang, and Alexander Rakhlin. Geometric inference for general high-dimensional linear inverse problems. The Annals of Statistics, 44 0 (4): 0 1536--1563, August 2016 b . ISSN 0090-5364, 2168-8966. doi:10.1214/15-AOS1426

    2016 doi

  4. [12]

    Candès and Yaniv Plan

    Emmanuel J. Candès and Yaniv Plan. Tight Oracle Inequalities for Low - Rank Matrix Recovery From a Minimal Number of Noisy Random Measurements . IEEE Transactions on Information Theory, 57 0 (4): 0 2342--2359, April 2011. ISSN 1557-9654. doi:10.1109/TIT.2011.2111771

    2011

  5. [13]

    Candès, Xiaodong Li, and Mahdi Soltanolkotabi

    Emmanuel J. Candès, Xiaodong Li, and Mahdi Soltanolkotabi. Phase Retrieval via Wirtinger Flow : Theory and Algorithms . IEEE Transactions on Information Theory, 61 0 (4): 0 1985--2007, April 2015. ISSN 1557-9654. doi:10.1109/TIT.2015.2399924

    1985

  6. [14]

    The Lasso with general Gaussian designs with applications to hypothesis testing

    Michael Celentano, Andrea Montanari, and Yuting Wei. The Lasso with general Gaussian designs with applications to hypothesis testing. The Annals of Statistics, 51 0 (5), October 2023. ISSN 0090-5364. doi:10.1214/23-AOS2327

    2023 doi

  7. [15]

    Sharp global convergence guarantees for iterative nonconvex optimization with random data

    Kabir Aladin Chandrasekher, Ashwin Pananjady, and Christos Thrampoulidis. Sharp global convergence guarantees for iterative nonconvex optimization with random data. The Annals of Statistics, 51 0 (1): 0 179--210, February 2023. ISSN 0090-5364, 2168-8966. doi:10.1214/22-AOS2246

    2023 doi

  8. [16]

    Alternating minimization for generalized rank-1 matrix sensing: sharp predictions from a random initialization

    Kabir Aladin Chandrasekher, Mengqi Lou, and Ashwin Pananjady. Alternating minimization for generalized rank-1 matrix sensing: sharp predictions from a random initialization. Information and Inference: A Journal of the IMA, 13 0 (3): 0 iaae025, September 2024. ISSN 2049-8772. d...

    2024 doi

  9. [17]

    Low- Rank Matrix Recovery with Composite Optimization : Good Conditioning and Rapid Convergence

    Vasileios Charisopoulos, Yudong Chen, Damek Davis, Mateo Díaz, Lijun Ding, and Dmitriy Drusvyatskiy. Low- Rank Matrix Recovery with Composite Optimization : Good Conditioning and Rapid Convergence . Foundations of Computational Mathematics, 21 0 (6): 0 1505--1593, December 202...

    2021 doi

  10. [18]

    Hanson– Wright inequality in Hilbert spaces with application to \ K \ -means clustering for non- Euclidean data

    Xiaohui Chen and Yun Yang. Hanson– Wright inequality in Hilbert spaces with application to \ K \ -means clustering for non- Euclidean data. Bernoulli, 27 0 (1): 0 586--614, February 2021. ISSN 1350-7265. doi:10.3150/20-BEJ1251

    2021 doi

  11. [19]

    Gradient Descent with Random Initialization : Fast Global Convergence for Nonconvex Phase Retrieval

    Yuxin Chen, Yuejie Chi, Jianqing Fan, and Cong Ma. Gradient Descent with Random Initialization : Fast Global Convergence for Nonconvex Phase Retrieval . Mathematical Programming, 176 0 (1-2): 0 5--37, July 2019 a . ISSN 0025-5610, 1436-4646. doi:10.1007/s10107-019-01363-6

    2019 doi

  12. [20]

    Inference and Uncertainty Quantification for Noisy Matrix Completion

    Yuxin Chen, Jianqing Fan, Cong Ma, and Yuling Yan. Inference and Uncertainty Quantification for Noisy Matrix Completion . Proceedings of the National Academy of Sciences, 116 0 (46): 0 22931--22937, November 2019 b . ISSN 0027-8424, 1091-6490. doi:10.1073/pnas.1910053116

    2019 doi

  13. [21]

    Noisy Matrix Completion : Understanding Statistical Guarantees for Convex Relaxation via Nonconvex Optimization

    Yuxin Chen, Yuejie Chi, Jianqing Fan, Cong Ma, and Yuling Yan. Noisy Matrix Completion : Understanding Statistical Guarantees for Convex Relaxation via Nonconvex Optimization . SIAM Journal on Optimization, 30 0 (4): 0 3098--3121, January 2020. ISSN 1052-6234. doi:10.1137/19M1290000

    2020 doi

  14. [22]

    Spectral Methods for Data Science : A Statistical Perspective

    Yuxin Chen, Yuejie Chi, Jianqing Fan, and Cong Ma. Spectral Methods for Data Science : A Statistical Perspective . Foundations and Trends® in Machine Learning, 14 0 (5): 0 566--806, 2021 a . ISSN 1935-8237, 1935-8245. doi:10.1561/2200000079

    2021 doi

  15. [23]

    Bridging convex and nonconvex optimization in robust PCA : Noise , outliers and missing data

    Yuxin Chen, Jianqing Fan, Cong Ma, and Yuling Yan. Bridging convex and nonconvex optimization in robust PCA : Noise , outliers and missing data. The Annals of Statistics, 49 0 (5): 0 2948--2971, October 2021 b . ISSN 0090-5364, 2168-8966. doi:10.1214/21-AOS2066

    2021 doi

  16. [24]

    Convex and Nonconvex Optimization Are Both Minimax - Optimal for Noisy Blind Deconvolution Under Random Designs

    Yuxin Chen, Jianqing Fan, Bingyan Wang, and Yuling Yan. Convex and Nonconvex Optimization Are Both Minimax - Optimal for Noisy Blind Deconvolution Under Random Designs . Journal of the American Statistical Association, 0 0 (0): 0 1--11, July 2021 c . ISSN 0162-1459. doi:10.108...

    2021

  17. [25]

    Lu, and Yuxin Chen

    Yuejie Chi, Yue M. Lu, and Yuxin Chen. Nonconvex Optimization Meets Low - Rank Matrix Factorization : An Overview . IEEE Transactions on Signal Processing, 67 0 (20): 0 5239--5269, October 2019. ISSN 1053-587X, 1941-0476. doi:10.1109/TSP.2019.2937282

    2019

  18. [26]

    Fast rates for noisy interpolation require rethinking the effect of inductive bias

    Konstantin Donhauser, Nicolò Ruggeri, Stefan Stojanovic, and Fanny Yang. Fast rates for noisy interpolation require rethinking the effect of inductive bias. In Proceedings of the 39th International Conference on Machine Learning , pages 5397--5428. PMLR, June 2022. ISSN: 2640-3498

    2022

  19. [27]

    High dimensional robust M -estimation: asymptotic variance via approximate message passing

    David Donoho and Andrea Montanari. High dimensional robust M -estimation: asymptotic variance via approximate message passing. Probability Theory and Related Fields, 166 0 (3): 0 935--969, December 2016. ISSN 1432-2064. doi:10.1007/s00440-015-0675-z

    2016 doi

  20. [28]

    Lu, and Subhabrata Sen

    Rishabh Dudeja, Yue M. Lu, and Subhabrata Sen. Universality of approximate message passing with semirandom matrices. The Annals of Probability, 51 0 (5): 0 1616--1683, September 2023. ISSN 0091-1798, 2168-894X. doi:10.1214/23-AOP1628

    2023 doi

  21. [29]

    Rishabh Dudeja, Subhabrata Sen, and Yue M. Lu. Spectral Universality in Regularized Linear Regression With Nearly Deterministic Sensing Matrices . IEEE Transactions on Information Theory, 70 0 (11): 0 7923--7951, November 2024. ISSN 1557-9654. doi:10.1109/TIT.2024.3458953

    2024

  22. [30]

    Bickel, Chinghway Lim, and Bin Yu

    Noureddine El Karoui, Derek Bean, Peter J. Bickel, Chinghway Lim, and Bin Yu. On robust regression with high-dimensional predictors. Proceedings of the National Academy of Sciences, 110 0 (36): 0 14557--14562, September 2013. doi:10.1073/pnas.1307842110

    2013 doi

  23. [31]

    Matan Gavish and David L. Donoho. The Optimal Hard Threshold for Singular Values is 4/ sqrt 3. IEEE Transactions on Information Theory, 60 0 (8): 0 5040--5053, August 2014. ISSN 1557-9654. doi:10.1109/TIT.2014.2323359

    2014

  24. [32]

    No Spurious Local Minima in Nonconvex Low Rank Problems : A Unified Geometric Analysis

    Rong Ge, Chi Jin, and Yi Zheng. No Spurious Local Minima in Nonconvex Low Rank Problems : A Unified Geometric Analysis . In Proceedings of the 34th International Conference on Machine Learning , pages 1233--1242. PMLR, July 2017. ISSN: 2640-3498

    2017

  25. [33]

    Structured low-rank matrix factorization: Optimality, algorithm, and applications to image processing

    Benjamin Haeffele, Eric Young, and Rene Vidal. Structured low-rank matrix factorization: Optimality, algorithm, and applications to image processing. In International conference on machine learning, pages 2007--2015. PMLR, 2014

    2007

  26. [34]

    Noisy linear inverse problems under convex constraints: Exact risk asymptotics in high dimensions

    Qiyang Han. Noisy linear inverse problems under convex constraints: Exact risk asymptotics in high dimensions. The Annals of Statistics, 51 0 (4): 0 1611--1638, August 2023. ISSN 0090-5364, 2168-8966. doi:10.1214/23-AOS2301

    2023 doi

  27. [35]

    Entrywise dynamics and universality of general first order methods, June 2024

    Qiyang Han. Entrywise dynamics and universality of general first order methods, June 2024. arXiv:2406.19061 [cs, math, stat]

    2024 arXiv

  28. [36]

    Universality of regularized regression estimators in high dimensions

    Qiyang Han and Yandi Shen. Universality of regularized regression estimators in high dimensions. The Annals of Statistics, 51 0 (4): 0 1799--1823, August 2023. ISSN 0090-5364, 2168-8966. doi:10.1214/23-AOS2309

    2023 doi

  29. [37]

    The distribution of Ridgeless least squares interpolators, July 2023

    Qiyang Han and Xiaocong Xu. The distribution of Ridgeless least squares interpolators, July 2023. arXiv:2307.02044 [cs, math, stat]

    2023

  30. [38]

    Confidence Intervals and Hypothesis Testing for High - Dimensional Regression

    Adel Javanmard and Andrea Montanari. Confidence Intervals and Hypothesis Testing for High - Dimensional Regression . Journal of Machine Learning Research, 15 0 (82): 0 2869--2909, 2014 a . ISSN 1533-7928

    2014

  31. [39]

    Hypothesis Testing in High - Dimensional Regression Under the Gaussian Random Design Model : Asymptotic Theory

    Adel Javanmard and Andrea Montanari. Hypothesis Testing in High - Dimensional Regression Under the Gaussian Random Design Model : Asymptotic Theory . IEEE Transactions on Information Theory, 60 0 (10): 0 6522--6554, October 2014 b . ISSN 1557-9654. doi:10.1109/TIT.2014.2343629

    2014

  32. [40]

    Debiasing the lasso: Optimal sample size for Gaussian designs

    Adel Javanmard and Andrea Montanari. Debiasing the lasso: Optimal sample size for Gaussian designs. The Annals of Statistics, 46 0 (6A): 0 2593--2622, December 2018. ISSN 0090-5364, 2168-8966. doi:10.1214/17-AOS1630

    2018 doi

  33. [41]

    Precise statistical analysis of classification accuracies for adversarial training

    Adel Javanmard and Mahdi Soltanolkotabi. Precise statistical analysis of classification accuracies for adversarial training. The Annals of Statistics, 50 0 (4): 0 2127--2156, August 2022. ISSN 0090-5364, 2168-8966. doi:10.1214/22-AOS2180

    2022 doi

  34. [42]

    Precise Tradeoffs in Adversarial Training for Linear Regression

    Adel Javanmard, Mahdi Soltanolkotabi, and Hamed Hassani. Precise Tradeoffs in Adversarial Training for Linear Regression . In Proceedings of Thirty Third Conference on Learning Theory , pages 2034--2078. PMLR, July 2020. ISSN: 2640-3498

    2020

  35. [43]

    Takuya Koriyama and Pierre C. Bellec. Phase transitions for the existence of unregularized M -estimators in single index models, May 2025. arXiv:2501.03163 [math]

    2025 arXiv

  36. [44]

    Laurent and P

    B. Laurent and P. Massart. Adaptive estimation of a quadratic functional by model selection. The Annals of Statistics, 28 0 (5): 0 1302--1338, October 2000. ISSN 0090-5364, 2168-8966. doi:10.1214/aos/1015957395

  37. [45]

    Symmetry, Saddle Points , and Global Optimization Landscape of Nonconvex Matrix Factorization

    Xingguo Li, Junwei Lu, Raman Arora, Jarvis Haupt, Han Liu, Zhaoran Wang, and Tuo Zhao. Symmetry, Saddle Points , and Global Optimization Landscape of Nonconvex Matrix Factorization . IEEE Transactions on Information Theory, 65 0 (6): 0 3489--3514, June 2019. ISSN 1557-9654. do...

    2019

  38. [46]

    A precise high-dimensional asymptotic theory for boosting and minimum-ell\_1-norm interpolated classifiers

    Tengyuan Liang and Pragya Sur. A precise high-dimensional asymptotic theory for boosting and minimum-ell\_1-norm interpolated classifiers. The Annals of Statistics, 50 0 (3): 0 1669--1695, June 2022. ISSN 0090-5364, 2168-8966. doi:10.1214/22-AOS2170

    2022 doi

  39. [47]

    Learning curves of generic features maps for realistic datasets with a teacher-student model

    Bruno Loureiro, Cedric Gerbelot, Hugo Cui, Sebastian Goldt, Florent Krzakala, Marc Mezard, and Lenka Zdeborová. Learning curves of generic features maps for realistic datasets with a teacher-student model. In Advances in Neural Information Processing Systems , volume 34, pages...

    2021

  40. [48]

    Nonconvex Matrix Factorization is Geodesically Convex : Global Landscape Analysis for Fixed -rank Matrix Optimization From a Riemannian Perspective , November 2022

    Yuetian Luo and Nicolas Garcia Trillos. Nonconvex Matrix Factorization is Geodesically Convex : Global Landscape Analysis for Fixed -rank Matrix Optimization From a Riemannian Perspective , November 2022. arXiv:2209.15130 [math]

    2022 arXiv

  41. [49]

    Implicit Regularization in Nonconvex Statistical Estimation : Gradient Descent Converges Linearly for Phase Retrieval , Matrix Completion , and Blind Deconvolution

    Cong Ma, Kaizheng Wang, Yuejie Chi, and Yuxin Chen. Implicit Regularization in Nonconvex Statistical Estimation : Gradient Descent Converges Linearly for Phase Retrieval , Matrix Completion , and Blind Deconvolution . Foundations of Computational Mathematics, 20 0 (3): 0 451--...

    2020 doi

  42. [50]

    Beyond Procrustes : Balancing - Free Gradient Descent for Asymmetric Low - Rank Matrix Sensing

    Cong Ma, Yuanxin Li, and Yuejie Chi. Beyond Procrustes : Balancing - Free Gradient Descent for Asymmetric Low - Rank Matrix Sensing . IEEE Transactions on Signal Processing, 69: 0 867--877, 2021. ISSN 1941-0476. doi:10.1109/TSP.2021.3051425

    2021

  43. [51]

    On the Optimization Landscape of Burer - Monteiro Factorization : When do Global Solutions Correspond to Ground Truth ?, February 2023

    Jianhao Ma and Salar Fattahi. On the Optimization Landscape of Burer - Monteiro Factorization : When do Global Solutions Correspond to Ground Truth ?, February 2023. arXiv:2302.10963 [cs, math]

    2023 arXiv

  44. [52]

    Geometric Analysis of Noisy Low - Rank Matrix Recovery in the Exact Parametrized and the Overparametrized Regimes

    Ziye Ma, Yingjie Bi, Javad Lavaei, and Somayeh Sojoudi. Geometric Analysis of Noisy Low - Rank Matrix Recovery in the Exact Parametrized and the Overparametrized Regimes . INFORMS Journal on Optimization, April 2023. ISSN 2575-1484. doi:10.1287/ijoo.2023.0090

    2023

  45. [53]

    The distribution of the Lasso : Uniform control over sparse balls and adaptive parameter tuning

    Léo Miolane and Andrea Montanari. The distribution of the Lasso : Uniform control over sparse balls and adaptive parameter tuning. The Annals of Statistics, 49 0 (4): 0 2313--2335, August 2021. ISSN 0090-5364, 2168-8966. doi:10.1214/20-AOS2038

    2021 doi

  46. [54]

    Universality of max-margin classifiers, September 2023

    Andrea Montanari, Feng Ruan, Basil Saeed, and Youngtak Sohn. Universality of max-margin classifiers, September 2023. arXiv:2310.00176 [math, stat]

    2023 arXiv

  47. [55]

    The generalization error of max-margin linear classifiers: Benign overfitting and high dimensional asymptotics in the overparametrized regime

    Andrea Montanari, Feng Ruan, Youngtak Sohn, and Jun Yan. The generalization error of max-margin linear classifiers: Benign overfitting and high dimensional asymptotics in the overparametrized regime. The Annals of Statistics, 53 0 (2): 0 822--853, April 2025. ISSN 0090-5364, 2...

    2025 doi

  48. [56]

    Wainwright

    Sahand Negahban and Martin J. Wainwright. Estimation of (near) low-rank matrices with noise and high-dimensional scaling. Annals of Statistics, 39 0 (2): 0 1069--1097, April 2011. ISSN 0090-5364, 2168-8966. doi:10.1214/10-AOS850

    2011 doi

  49. [57]

    The Impact of Regularization on High -dimensional Logistic Regression

    Fariborz Salehi, Ehsan Abbasi, and Babak Hassibi. The Impact of Regularization on High -dimensional Logistic Regression . In Advances in Neural Information Processing Systems , volume 32. Curran Associates, Inc., 2019

    2019

  50. [58]

    Implicit Balancing and Regularization : Generalization and Convergence Guarantees for Overparameterized Asymmetric Matrix Sensing

    Mahdi Soltanolkotabi, Dominik Stöger, and Changzhi Xie. Implicit Balancing and Regularization : Generalization and Convergence Guarantees for Overparameterized Asymmetric Matrix Sensing . IEEE Transactions on Information Theory, 71 0 (4): 0 2991--3037, April 2025. ISSN 1557-96...

    2025

  51. [59]

    Tight bounds for maximum \ ell\_1\ -margin classifiers

    Stefan Stojanovic, Konstantin Donhauser, and Fanny Yang. Tight bounds for maximum \ ell\_1\ -margin classifiers. In Proceedings of The 35th International Conference on Algorithmic Learning Theory , pages 1055--1112. PMLR, March 2024. ISSN: 2640-3498

    2024

  52. [60]

    Small random initialization is akin to spectral learning: Optimization and generalization guarantees for overparameterized low-rank matrix reconstruction

    Dominik Stöger and Mahdi Soltanolkotabi. Small random initialization is akin to spectral learning: Optimization and generalization guarantees for overparameterized low-rank matrix reconstruction. In Advances in Neural Information Processing Systems , volume 34, pages 23831--23...

    2021

  53. [61]

    Sharp Asymptotics and Optimal Performance for Inference in Binary Models

    Hossein Taheri, Ramtin Pedarsani, and Christos Thrampoulidis. Sharp Asymptotics and Optimal Performance for Inference in Binary Models . In Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics , pages 3739--3749. PMLR, June 2020. I...

    2020

  54. [62]

    Fundamental Limits of Ridge - Regularized Empirical Risk Minimization in High Dimensions

    Hossein Taheri, Ramtin Pedarsani, and Christos Thrampoulidis. Fundamental Limits of Ridge - Regularized Empirical Risk Minimization in High Dimensions . In Proceedings of The 24th International Conference on Artificial Intelligence and Statistics , pages 2773--2781. PMLR, Marc...

    2021

  55. [63]

    The Gaussian min-max theorem in the Presence of Convexity , March 2015 a

    Christos Thrampoulidis, Samet Oymak, and Babak Hassibi. The Gaussian min-max theorem in the Presence of Convexity , March 2015 a . arXiv:1408.4837 [cs, math]

    2015 arXiv

  56. [64]

    Regularized Linear Regression : A Precise Analysis of the Estimation Error

    Christos Thrampoulidis, Samet Oymak, and Babak Hassibi. Regularized Linear Regression : A Precise Analysis of the Estimation Error . In Proceedings of The 28th Conference on Learning Theory , pages 1683--1709. PMLR, June 2015 b . ISSN: 1938-7228

    2015

  57. [65]

    Precise Error Analysis of Regularized M - Estimators in High Dimensions

    Christos Thrampoulidis, Ehsan Abbasi, and Babak Hassibi. Precise Error Analysis of Regularized M - Estimators in High Dimensions . IEEE Transactions on Information Theory, 64 0 (8): 0 5592--5628, August 2018. ISSN 1557-9654. doi:10.1109/TIT.2018.2840720

    2018

  58. [66]

    Low- Rank Matrix Recovery With Scaled Subgradient Methods : Fast and Robust Convergence Without the Condition Number

    Tian Tong, Cong Ma, and Yuejie Chi. Low- Rank Matrix Recovery With Scaled Subgradient Methods : Fast and Robust Convergence Without the Condition Number . IEEE Transactions on Signal Processing, 69: 0 2396--2409, 2021. ISSN 1941-0476. doi:10.1109/TSP.2021.3071560

    2021

  59. [67]

    Low-rank Solutions of Linear Matrix Equations via Procrustes Flow

    Stephen Tu, Ross Boczar, Max Simchowitz, Mahdi Soltanolkotabi, and Ben Recht. Low-rank Solutions of Linear Matrix Equations via Procrustes Flow . In Proceedings of The 33rd International Conference on Machine Learning , pages 964--973. PMLR, June 2016. ISSN: 1938-7228

    2016

  60. [68]

    Robust Matrix Completion with Heavy - Tailed Noise

    Bingyan Wang, , and Jianqing Fan. Robust Matrix Completion with Heavy - Tailed Noise . Journal of the American Statistical Association, 120 0 (550): 0 922--934, April 2025. ISSN 0162-1459. doi:10.1080/01621459.2024.2375037

    2025

  61. [69]

    Tight bounds for minimum \ ell\_1\ -norm interpolation of noisy data

    Guillaume Wang, Konstantin Donhauser, and Fanny Yang. Tight bounds for minimum \ ell\_1\ -norm interpolation of noisy data. In Proceedings of The 25th International Conference on Artificial Intelligence and Statistics , pages 10572--10602. PMLR, May 2022. ISSN: 2640-3498

    2022

  62. [70]

    Confidence Region of Singular Subspaces for Low - Rank Matrix Regression

    Dong Xia. Confidence Region of Singular Subspaces for Low - Rank Matrix Regression . IEEE Transactions on Information Theory, 65 0 (11): 0 7437--7459, November 2019. ISSN 1557-9654. doi:10.1109/TIT.2019.2924900

    2019

  63. [71]

    The Power of Preconditioning in Overparameterized Low - Rank Matrix Sensing

    Xingyu Xu, Yandi Shen, Yuejie Chi, and Cong Ma. The Power of Preconditioning in Overparameterized Low - Rank Matrix Sensing . In Proceedings of the 40th International Conference on Machine Learning , pages 38611--38654. PMLR, July 2023. ISSN: 2640-3498

    2023

  64. [72]

    Optimal Tuning - Free Convex Relaxation for Noisy Matrix Completion

    Yuepeng Yang and Cong Ma. Optimal Tuning - Free Convex Relaxation for Noisy Matrix Completion . IEEE Transactions on Information Theory, 69 0 (10): 0 6571--6585, October 2023. ISSN 1557-9654. doi:10.1109/TIT.2023.3284341

    2023

  65. [73]

    Cun-Hui Zhang and Stephanie S. Zhang. Confidence Intervals for Low Dimensional Parameters in High Dimensional Linear Models . Journal of the Royal Statistical Society Series B: Statistical Methodology, 76 0 (1): 0 217--242, January 2014. ISSN 1369-7412. doi:10.1111/rssb.12026

    2014 doi

  66. [74]

    Gavin Zhang, Hong-Ming Chiu, and Richard Y. Zhang. Fast and Minimax Optimal Estimation of Low - Rank Matrices via Non - Convex Gradient Descent , May 2023. arXiv:2305.17224 [cs, math, stat]

    2023 arXiv

  67. [75]

    Richard Y. Zhang. Sharp Global Guarantees for Nonconvex Low - Rank Matrix Recovery in the Overparameterized Regime , April 2021. arXiv:2104.10790 [math]

    2021 arXiv

  68. [76]

    A Convergent Gradient Descent Algorithm for Rank Minimization and Semidefinite Programming from Random Linear Measurements

    Qinqing Zheng and John Lafferty. A Convergent Gradient Descent Algorithm for Rank Minimization and Semidefinite Programming from Random Linear Measurements . In Advances in Neural Information Processing Systems , volume 28. Curran Associates, Inc., 2015

    2015

  69. [77]

    write newline

    " write newline "" before.all 'output.state := FUNCTION n.dashify 't := "" t empty not t #1 #1 substring "-" = t #1 #2 substring "--" = not "--" * t #2 global.max substring 't := t #1 #1 substring "-" = "-" * t #2 global.max substring 't := while if t #1 #1 substring * t #2 gl...

Pith tools

Reviewed August 6, 2026 · model on record in the stance chip above.