Pith. sign in

REVIEW 2 major objections 4 minor 61 references

Efficient Over-parameterized Matrix Sensing from Noisy Measurements via Alternating Preconditioned Gradient Descent

T0 review · 2 major / 4 minor · reviewed 2026-08-09 · deepseek-v4-flash

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

Pith's one-line read By alternating updates of the two factor matrices, APGD removes the damping parameter from preconditioned gradient descent and reaches near-optimal error at a linear rate in noisy over-parameterized matrix sensing.

desk verdict APGD is a nice damping-free alternating preconditioned method, but Theorem 2's noise floor is off by a factor of m and Theorem 3's algebra fails, so the theory needs major revision. read the letter →

arxiv 2502.00463 v3 pith:CKMNSB2P submitted 2025-02-01 cs.LG math.OCstat.ML

Zhiyu Liu , Zhi Han , Yandong Tang , Shaojie Tang , Yao Wang This is my paper · ORCID
classification cs.LGmath.OCstat.ML
keywords matrixsensingover-parameterizationpreconditionedgradientdescentalternatingminimizationlow-rankrecoverynoisymeasurementslinearconvergencerestrictedisometryproperty
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

The paper tackles noisy matrix sensing in the over-parameterized regime, where the estimated rank exceeds the true rank and the target is recovered through an asymmetric factorization $X = LR^\top$. It claims that updating $L$ and $R$ alternately, each with a Moore-Penrose preconditioner $(R^\top R)^\dagger$ or $(L^\top L)^\dagger$, eliminates the damping parameter $\lambda$ that all previous preconditioned methods needed, while still converging linearly to near-optimal error $O(\nu^2 r n \log n / m)$. If correct, this removes the need for careful $\lambda$-tuning in ill-conditioned, over-parameterized low-rank recovery and allows step sizes up to $1/(1+\delta_{2r+1})$, independent of the condition number. The same alternating template is shown to give linear convergence for any loss that is rank-$2r$ restricted smooth and strongly convex, covering weighted PCA, 1-bit matrix completion, and matrix completion.

What carries the argument

The object carrying the argument is the alternating preconditioned update: $L_{t+1} = L_t - \eta \nabla_L f(L_t,R_t)(R_t^\top R_t)^\dagger$, followed by $R_{t+1} = R_t - \eta \nabla_R f(L_{t+1}, R_t)(L_{t+1}^\top L_{t+1})^\dagger$. The key step is Lemma 1: for the noiseless case, because the second factor is frozen during each subproblem, the per-subproblem Lipschitz constant is $1+\delta_{2r+1}$ rather than an expression depending on a damping parameter $\lambda$; the $DD^\top$ term that made the Lipschitz constant blow up in simultaneous updates is avoided. The proof then works in the local norms induced by $P_{R_t}=R_t^\top R_t$ and $P_{L_t}=L_t^\top L_t$ (that is, $\|A\|_{R_t} = \|A P_{R_t}^{1/2}\|_F$ and its dual), uses an angle lower bound between the error matrix and the current factor's column space to get a Polyak-\L{}ojasiewicz-type gradient lower bound (Lemma 3), and splits the noisy dynamics into cases where the gradient dominates the noise (linear contraction) and where the noise dominates (error already near the floor $E_{\mathrm{opt}}$).

What would settle it

On a Gaussian matrix sensing instance with $n_1=n_2=50$, true rank $r_\star=5$, estimated rank $r=10$, $m=10nr$ measurements, condition number $\kappa=100$, and noise variance chosen so that $E_{\mathrm{opt}}$ is well below the initialization error, run APGD with the spectral initialization and step size $\eta=0.99/(1+\delta_{2r+1})$. If the relative error does not decrease linearly toward $O(\nu^2 r n \log n/m)$ within roughly 100 iterations, Theorem 2's guarantee fails on the regime it claims to cover.

Watch

Extended reading notes

Core claim

The central result is Theorem 2: under Gaussian measurements, RIP constant $\delta_{2r+1} \le \rho/(8\kappa\sqrt{r_\star+r})$ with $\rho \le 1/2$, sample complexity $m \gtrsim \nu^2 r n \log n / (\sigma_{r_\star}(X_\star)\rho^2\delta_{2r+1}^2)$, and step size $\eta \le 1/(1+\delta_{2r+1})$, APGD initialized by spectral initialization satisfies $\|L_t R_t^\top - X_\star\|_F^2 \le \max\{C_\delta Q_f^{2t}\|L_0 R_0^\top - X_\star\|_F^2, C_3 E_{\mathrm{opt}}\}$ with high probability, where $E_{\mathrm{opt}} = C_e \nu^2 r n \log n / m$ and $Q_f<1$ is an explicit contraction factor. That is, the iterates converge linearly until they reach a near-optimal statistical error floor, and the error floor is independent of the condition number. The mechanism is the alternating update: because each factor is updated while the other is held fixed, the problematic quadratic term in the gradient that forced the damping parameter in ScaledGD($\lambda$), PrecGD, and NoisyPrecGD simply disappears. The paper also establishes a general template (Theorem 3) in which any loss satisfying rank-$2r$ restricted smoothness and strong convexity inherits linear convergence under APGD.

Load-bearing premise

The whole convergence proof rests on the spectral initialization getting within distance $\|X_0 - X_\star\|_F \le \rho\,\sigma_{r_\star}(X_\star)$ with $\rho \le 1/2$, and guaranteeing that closeness forces the number of measurements to grow with the square of the condition number; if the initialization is not that close, the linear rate is not established.

Editorial extensions

If this is right

  • Noisy over-parameterized matrix sensing can be solved at a linear rate with no damping parameter to tune, removing the main practical obstacle in ScaledGD($\lambda$), PrecGD, and NoisyPrecGD.
  • The allowed step size $\eta \le 1/(1+\delta_{2r+1})$ is bounded only by the RIP constant, so APGD can take large steps even for ill-conditioned targets, where vanilla GD and small-initialization GD require steps of order $1/(\kappa^2 \sigma_1)$.
  • The recovery error $O(\nu^2 r n \log n / m)$ does not grow with the condition number, unlike the $\kappa^2$ factor in small-initialization GD.
  • Because the factorization is asymmetric and no PSD constraint is imposed, the method applies to general rectangular low-rank matrices, not only symmetric positive semidefinite ones.
  • Any low-rank estimation task whose loss is rank-$2r$ restricted smooth and strongly convex inherits linear convergence under the same alternating-preconditioning template, including weighted PCA, matrix completion, and 1-bit matrix completion.

Reading between the lines

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

  • If the damping-free property is really due to the alternating structure, the same idea should transfer to other bilinear factorizations (for instance, tensor or coupled-matrix decompositions) where simultaneous preconditioned updates also suffer from quadratic gradient terms; testing this would separate the principle from the specific low-rank sensing setting.
  • The linear-rate guarantee currently needs spectral initialization that improves with the condition number through $\delta_{2r+1} \le \rho/(8\kappa\sqrt{r_\star+r})$. A testable extension is to replace that initialization by, say, a few iterations of vanilla GD or a non-spectral warm start and check whether the contraction still holds numerically, which would widen the regime the theorem covers.
  • In the matrix completion experiments the paper initializes APGD randomly even though the theory assumes spectral initialization; quantifying the basin of linear convergence for random starts would turn a practical convenience into a provable property.
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

2 major / 4 minor

Summary. The paper proposes Alternating Preconditioned Gradient Descent (APGD) for noisy, over-parameterized, asymmetric matrix sensing. Unlike prior preconditioned methods such as PrecGD and NoisyPrecGD, APGD removes the damping parameter from the right preconditioners by alternating the L- and R-updates. The main theoretical result, Theorem 2, claims that APGD converges linearly to a near-optimal error floor E_opt = O(ν² r n log n / m) under RIP, sub-Gaussian noise, spectral initialization, and a step-size condition η ≤ 1/(1+δ). The paper also gives a general contraction result, Theorem 3, for rank-2r restricted smooth and strongly convex losses, and reports experiments on noisy matrix sensing, weighted PCA, 1-bit matrix completion, and matrix completion.

Significance. The damping-free alternating preconditioning idea is attractive and is a genuine departure from the λ-dependent preconditioners in prior work. If the main guarantee were correct, APGD would be the first damping-free preconditioned method with a linear-rate guarantee for noisy asymmetric over-parameterized matrix sensing; the experiments also cover a broad range of low-rank estimation tasks and the code is publicly available. However, the advertised near-optimal statistical error rests on a concentration step that has the wrong scaling under the stated measurement model, and the general contraction claimed for Lg/μ ≤ 9801 is not supported by the algebra in Lemma 9. The algorithmic framework remains potentially valuable, but the central statistical claim is not established as stated.

major comments (2)
  1. [Appendix A, Lemma 4; Theorem 2] The concentration inequality used to control the noise term is not valid under the model stated in Theorem 2. Conditional on the noise vector s, the matrix M = ∑_{i=1}^m s_i A_i has iid entries with variance (∑_i s_i²)/m ≈ ν², so the standard spectral-norm bound for iid sub-Gaussian matrices gives ‖M‖₂² = Θ(ν² n) with high probability, not O(ν² n log n / m). The step marked (b) in the proof of Lemma 4 is the only source of the claimed floor E_opt = C_e ν² r n log n / m, so Theorem 2's near-optimal error bound is unsupported; with the usual scaling m ≍ r n, the asserted bound is smaller by a factor of m than the natural concentration scale of the noise term. Please state the precise version of Lemma 16 of [16] being invoked, including its normalization assumptions, or correct the noise model and the theorem accordingly.
  2. [Appendix E, Lemma 9 and Eq. (7)] The claimed range Lg/μ ≤ 9801 does not follow from the displayed formulas. For ρ = 0.1, Cρ = sqrt((1−3ρ²)/(1−ρ²)) = sqrt(0.97/0.99) < 1, so ζ = ((Cρ−1)Lg + (Cρ+1)μ)/√(2Lg) becomes negative as soon as Lg/μ > (1+Cρ)/(1−Cρ) ≈ 197.99. A negative ζ cannot be used as the lower-bound constant in Lemma 9; the subsequent derivation of Qg = (1 − 0.198 μ/Lg)² for Lg/μ ≤ 9801 is therefore invalid. This affects Theorem 3, the comparison in Table II, and the claim in Remark 4; the condition needs to be corrected or a different argument is required.
minor comments (4)
  1. [Section III-B, Theorem 2] The step-size condition in Theorem 2 is written as η ≤ 1/(1+δ_{2r+1}), but at the endpoint η = 1/(1+δ_{2r+1}) the coefficient C2 = η − (η/3)(1 + 2η(1+δ_{2r+1})) equals zero, so no contraction is obtained. The theorem should state the strict inequality η < 1/(1+δ_{2r+1}), matching the discussion in the text.
  2. [Appendix B, proof of Lemma 2] In the expression for Z2, the first line writes ∇_L f(L_{t+1}, R_t), but the subsequent computation uses ∇_L f(L_t, R_t); the notation should be made consistent.
  3. [Appendix C, proof of Lemma 3] The final RIP step writes the lower bound in terms of f_c(L_{t+1}, R_t), while f_c(L_t, R_t) appears to be intended. The inequality is repairable, but as written it is confusing.
  4. [Appendix A, Lemma 4 proof] The equality ∥R_t(R_t^T R_t)^{†/2}∥_F² = r holds only when R_t has rank r; for a rank-deficient iterate the right-hand side should be rank(R_t) ≤ r. This is harmless for the proof but should be stated.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: APGD's guarantee is derived from standard RIP/sub-Gaussian assumptions and external concentration/initialization lemmas, with no self-referential reduction to its own inputs.

full rationale

I walked the derivation chain of Theorem 2 and Theorem 3 and found no circular step that reduces a prediction to an input by construction. The recovery error bound in Theorem 2 is proved in Appendix D by combining Lemma 2 (a Lipschitz-like inequality, proved in Appendix B), Lemma 3 (a gradient lower bound, proved in Appendix C), and Lemma 4 (a concentration/initialization lemma). Lemma 4 imports three ingredients: RIP from [7], the noise concentration bound from Lemma 16 of [16], and the spectral-initialization closeness bound from Proposition 23 of [16]. These are genuine external results: none of the cited works share authors with the present paper, and none of the cited statements assert the paper's target conclusion that alternating preconditioned updates converge linearly to near-optimal error without a damping term. The paper's distinctive claim, that alternating updates remove the need for lambda, is supported by its own algebra in Lemma 1 and Lemma 2 rather than by definitional equivalence or by citing its own conclusion. There is no fitted parameter that is later renamed a prediction: Theorem 2 contains no data-fitting step, and the constants C_delta, C_e, Q_f are explicit functions of the RIP constant, noise variance, rank, and dimension rather than fitted values. Even the skeptical concern about Lemma 4's concentration scale (whether the stated nu^2 n log n / m bound is correct under N(0,1/m) sensing matrices) is a correctness question about an external concentration lemma, not a circularity: an erroneous imported bound would make the theorem false or unsupported, but it would not make the derivation equivalent to its inputs. Theorem 3 similarly uses restricted smoothness/strong convexity assumptions and two imported lemmas from [17] and [20], then combines them with the paper's own Lipschitz-like and angle lower-bound lemmas; this is a standard modular proof, not a renaming of a known result. The step-size robustness claim follows from the paper's own Lemma 1 with eta <= 1/(1+delta), which is a derived sufficient condition rather than an assumption identical to the conclusion. Accordingly, none of the seven circularity patterns are present, and the correct finding is no significant circularity (score 0).

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

The central theorem rests on standard RIP and sub-Gaussian assumptions plus a local initialization condition. No free physical parameters are fit; the step size is a hyperparameter. The general extension relies on RSC/RSM and an external subspace lemma from [16] whose quoted form appears doubtful. No invented entities are introduced.

free parameters (1)
  • step size eta = 1 for APGD in sensing, 0.9 for weighted PCA, 4 for 1-bit matrix completion; baseline-specific values in experiments
    Chosen by hand to give fastest convergence in experiments. The theorem only requires eta < 1/(1+delta), so this is a hyperparameter, not a fitted scientific parameter.
assumptions (5)
  • domain assumption The linear measurement operator A satisfies rank-(2r+1) RIP with constant delta_{2r+1}.
    Definition 1 and Lemma 4; requires m approximately greater than (2r+1)n/delta^2 and is the main structural assumption for the sensing theorem.
  • domain assumption Noise entries s_i are independent sub-Gaussian with variance proxy nu^2.
    Assumed in the problem statement of Section I and used via Lemma 4 and concentration arguments for A*(s).
  • domain assumption Initialization satisfies ||X0 - X*||_F <= rho sigma_{r*}(X*) with rho <= 1/2.
    Imported from Proposition 23 in [16] via spectral initialization; not proved in this paper and drives Lemma 6.
  • domain assumption For the general extension, g is rank-2r restricted Lg-smooth and mu-strongly convex.
    Definition 2/3 and Theorem 3; standard in this literature, but the paper's arithmetic on the allowed Lg/mu range is flawed.
  • standard math Lemma 13 of [16] as quoted in Lemma 6.
    Used to bound the angle between subspaces; the quoted statement appears inconsistent in the small-D limit and would need the original source checked.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Efficient Over-parameterized Matrix Sensing from Noisy Measurements via Alternating Preconditioned Gradient Descent." pith.science (2026). https://pith.science/paper/CKMNSB2P

@misc{pith2026250200463,
  author       = {Pith},
  title        = {Pith review of: Efficient Over-parameterized Matrix Sensing from Noisy Measurements via Alternating Preconditioned Gradient Descent},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/CKMNSB2P}},
  note         = {Machine review of arXiv:2502.00463}
}
abstract

We consider the noisy matrix sensing problem in the over-parameterization setting, where the estimated rank $r$ is larger than the true rank $r_\star$ of the target matrix $X_\star$. Specifically, our main objective is to recover a matrix $ X_\star \in \mathbb{R}^{n_1 \times n_2} $ with rank $ r_\star $ from noisy measurements using an over-parameterized factorization $ LR^\top $, where $ L \in \mathbb{R}^{n_1 \times r}, \, R \in \mathbb{R}^{n_2 \times r} $ and $ \min\{n_1, n_2\} \ge r > r_\star $, with $ r_\star $ being unknown. Recently, preconditioning methods have been proposed to accelerate the convergence of matrix sensing problem compared to vanilla gradient descent, incorporating preconditioning terms $ (L^\top L + \lambda I)^{-1} $ and $ (R^\top R + \lambda I)^{-1} $ into the original gradient. However, these methods require careful tuning of the damping parameter $\lambda$ and are sensitive to step size. To address these limitations, we propose the alternating preconditioned gradient descent (APGD) algorithm, which alternately updates the two factor matrices, eliminating the need for the damping parameter $\lambda$ and enabling faster convergence with larger step sizes. We theoretically prove that APGD convergences to a near-optimal error at a linear rate. We further show that APGD can be extended to deal with other low-rank matrix estimation tasks, also with a theoretical guarantee of linear convergence. To validate the effectiveness and scalability of the proposed APGD, we conduct simulated and real-world experiments on a wide range of low-rank estimation problems, including noisy matrix sensing, weighted PCA, 1-bit matrix completion, and matrix completion. The extensive results demonstrate that APGD consistently achieves the fastest convergence and the lowest computation time compared to the existing alternatives.

Figures

Figures reproduced from arXiv: 2502.00463 by the authors.

Figure 1
Figure 1. Relative recovery error and computation time of NoisyPrecGD, GD, and APGD on the exact-rank noisy matrix sensing problem, where [PITH_FULL_IMAGE:figures/full_fig_p008_1.png] view at source ↗
Figure 2
Figure 2. Relative recovery error and computation time of NoisyPrecGD, GD, and APGD on the over-rank noisy matrix sensing problem, where [PITH_FULL_IMAGE:figures/full_fig_p008_2.png] view at source ↗
Figure 5
Figure 5. Experiments on the weighted PCA task with the following parameter [PITH_FULL_IMAGE:figures/full_fig_p009_5.png] view at source ↗
Figures from the paper (3 more)
Figure 4
Figure 4. Figure 4: Recovery error of APGD (with spectral initialization) and GD with [PITH_FULL_IMAGE:figures/full_fig_p009_4.png]
Figure 8
Figure 8. Figure 8: Compare the recovery performance of different algorithms under [PITH_FULL_IMAGE:figures/full_fig_p010_8.png]
Figure 7
Figure 7. Figure 7: Compare the recovery performance of different algorithms under [PITH_FULL_IMAGE:figures/full_fig_p010_7.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

61 extracted references · 51 canonical work pages

  1. [30]

    Preconditioning matters: Fast global convergence of non-convex matrix factorization via scaled gradient descent,

    X. Jia, H. Wang, J. Peng, X. Feng, and D. Meng, “Preconditioning matters: Fast global convergence of non-convex matrix factorization via scaled gradient descent,” Advances in Neural Information Processing Systems, vol. 36, 2024

    work page 2024

  2. [22]

    Accelerating gradient descent for over- parameterized asymmetric low-rank matrix sensing via preconditioning,

    C. Cheng and Z. Zhao, “Accelerating gradient descent for over- parameterized asymmetric low-rank matrix sensing via preconditioning,” in ICASSP 2024-2024 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP) . IEEE, 2024, pp. 7705–7709

    work page 2024

  3. [16]

    Preconditioned gradient descent for over-parameterized nonconvex matrix factorization,

    J. Zhang, S. Fattahi, and R. Y . Zhang, “Preconditioned gradient descent for over-parameterized nonconvex matrix factorization,” Advances in Neural Information Processing Systems , vol. 34, pp. 5985–5996, 2021

    work page 2021

  4. [1]

    Robust principal component analysis?

    E. J. Cand `es, X. Li, Y . Ma, and J. Wright, “Robust principal component analysis?” Journal of the ACM (JACM) , vol. 58, no. 3, pp. 1–37, 2011

    2011

  5. [2]

    Cloud removal in remote sensing images using nonnegative matrix factorization and error correction,

    X. Li, L. Wang, Q. Cheng, P. Wu, W. Gan, and L. Fang, “Cloud removal in remote sensing images using nonnegative matrix factorization and error correction,” ISPRS journal of photogrammetry and remote sensing, vol. 148, pp. 103–113, 2019

    work page 2019

  6. [3]

    Low-rank phase retrieval,

    N. Vaswani, S. Nayer, and Y . C. Eldar, “Low-rank phase retrieval,”IEEE Transactions on Signal Processing, vol. 65, no. 15, pp. 4059–4074, 2017

    work page 2017

  7. [4]

    Sample-efficient low rank phase retrieval,

    S. Nayer and N. Vaswani, “Sample-efficient low rank phase retrieval,” IEEE Transactions on Information Theory , vol. 67, no. 12, pp. 8190– 8206, 2021

    work page 2021

  8. [5]

    Robust and efficient high-dimensional quantum state tomography,

    M. Rambach, M. Qaryan, M. Kewming, C. Ferrie, A. G. White, and J. Romero, “Robust and efficient high-dimensional quantum state tomography,”Physical Review Letters, vol. 126, no. 10, p. 100402, 2021

    work page 2021

Show all 61 references
  1. [6]

    Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization,

    B. Recht, M. Fazel, and P. A. Parrilo, “Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization,” SIAM review, vol. 52, no. 3, pp. 471–501, 2010

    2010

  2. [7]

    Tight oracle inequalities for low-rank matrix recovery from a minimal number of noisy random measurements,

    E. J. Candes and Y . Plan, “Tight oracle inequalities for low-rank matrix recovery from a minimal number of noisy random measurements,” IEEE Transactions on Information Theory , vol. 57, no. 4, pp. 2342–2359, 2011

    2011

  3. [8]

    Exact matrix completion via convex opti- mization,

    E. Candes and B. Recht, “Exact matrix completion via convex opti- mization,” Communications of the ACM , vol. 55, no. 6, pp. 111–119, 2012

    2012

  4. [9]

    The power of convex relaxation: Near-optimal matrix completion,

    E. J. Cand `es and T. Tao, “The power of convex relaxation: Near-optimal matrix completion,” IEEE Transactions on Information Theory , vol. 56, no. 5, pp. 2053–2080, 2010

    2010

  5. [10]

    A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization,

    S. Burer and R. D. Monteiro, “A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization,” Mathematical Programming, vol. 95, no. 2, pp. 329–357, 2003. 11

    2003

  6. [11]

    Local minima and convergence in low-rank semidefinite pro- gramming,

    ——, “Local minima and convergence in low-rank semidefinite pro- gramming,” Mathematical programming, vol. 103, no. 3, pp. 427–444, 2005

    2005

  7. [12]

    Low-rank solutions of linear matrix equations via procrustes flow,

    S. Tu, R. Boczar, M. Simchowitz, M. Soltanolkotabi, and B. Recht, “Low-rank solutions of linear matrix equations via procrustes flow,” in International Conference on Machine Learning. PMLR, 2016, pp. 964– 973

    2016

  8. [13]

    On the computational and statistical complexity of over-parameterized matrix sensing,

    J. Zhuo, J. Kwon, N. Ho, and C. Caramanis, “On the computational and statistical complexity of over-parameterized matrix sensing,” Journal of Machine Learning Research , vol. 25, no. 169, pp. 1–47, 2024

    2024

  9. [14]

    Global optimality of local search for low rank matrix recovery,

    S. Bhojanapalli, B. Neyshabur, and N. Srebro, “Global optimality of local search for low rank matrix recovery,” Advances in Neural Information Processing Systems , vol. 29, 2016

    2016

  10. [15]

    Understanding incremental learning of gradient descent: A fine-grained analysis of matrix sensing,

    J. Jin, Z. Li, K. Lyu, S. S. Du, and J. D. Lee, “Understanding incremental learning of gradient descent: A fine-grained analysis of matrix sensing,” arXiv preprint arXiv:2301.11500 , 2023

    2023 arXiv

  11. [17]

    Preconditioned gradient descent for overparameterized nonconvex burer–monteiro factorization with global optimality certification,

    G. Zhang, S. Fattahi, and R. Y . Zhang, “Preconditioned gradient descent for overparameterized nonconvex burer–monteiro factorization with global optimality certification,” Journal of Machine Learning Research , vol. 24, no. 163, pp. 1–55, 2023

    2023

  12. [18]

    A convergent gradient descent algorithm for rank minimization and semidefinite programming from random linear measurements,

    Q. Zheng and J. Lafferty, “A convergent gradient descent algorithm for rank minimization and semidefinite programming from random linear measurements,” Advances in Neural Information Processing Systems , vol. 28, 2015

    2015

  13. [19]

    Solving 2d fredholm integral from incomplete measurements using compressive sensing,

    A. Cloninger, W. Czaja, R. Bai, and P. J. Basser, “Solving 2d fredholm integral from incomplete measurements using compressive sensing,” SIAM journal on imaging sciences , vol. 7, no. 3, pp. 1775–1798, 2014

    2014

  14. [20]

    Accelerating ill-conditioned low-rank matrix estimation via scaled gradient descent,

    T. Tong, C. Ma, and Y . Chi, “Accelerating ill-conditioned low-rank matrix estimation via scaled gradient descent,” Journal of Machine Learning Research, vol. 22, no. 150, pp. 1–63, 2021

    2021

  15. [21]

    The power of preconditioning in overparameterized low-rank matrix sensing,

    X. Xu, Y . Shen, Y . Chi, and C. Ma, “The power of preconditioning in overparameterized low-rank matrix sensing,” in International Confer- ence on Machine Learning . PMLR, 2023, pp. 38 611–38 654

    2023

  16. [23]

    Fast and accurate estimation of low-rank matrices from noisy measurements via preconditioned non- convex gradient descent,

    J. Zhang, R. Y . Zhang, and H.-M. Chiu, “Fast and accurate estimation of low-rank matrices from noisy measurements via preconditioned non- convex gradient descent,” in International Conference on Artificial Intelligence and Statistics . PMLR, 2024, pp. 3772–3780

    2024

  17. [24]

    A validation ap- proach to over-parameterized matrix and image recovery,

    L. Ding, Z. Qin, L. Jiang, J. Zhou, and Z. Zhu, “A validation ap- proach to over-parameterized matrix and image recovery,”arXiv preprint arXiv:2209.10675, 2022

    2022 arXiv

  18. [25]

    Low-rank matrix completion using alternating minimization,

    P. Jain, P. Netrapalli, and S. Sanghavi, “Low-rank matrix completion using alternating minimization,” in Proceedings of the forty-fifth annual ACM symposium on Theory of computing , 2013, pp. 665–674

    2013

  19. [26]

    Low rank matrix completion by alternating steep- est descent methods,

    J. Tanner and K. Wei, “Low rank matrix completion by alternating steep- est descent methods,” Applied and Computational Harmonic Analysis , vol. 40, no. 2, pp. 417–429, 2016

    2016

  20. [27]

    Randomly initialized alternating least squares: Fast convergence for matrix sensing,

    K. Lee and D. St ¨oger, “Randomly initialized alternating least squares: Fast convergence for matrix sensing,” SIAM Journal on Mathematics of Data Science, vol. 5, no. 3, pp. 774–799, 2023

    2023

  21. [28]

    Low rank matrix completion via robust alternating minimization in nearly linear time,

    Y . Gu, Z. Song, J. Yin, and L. Zhang, “Low rank matrix completion via robust alternating minimization in nearly linear time,” in The Twelfth International Conference on Learning Representations , 2024

    2024

  22. [29]

    Convergence of alternating gradient descent for matrix factorization,

    R. Ward and T. G. Kolda, “Convergence of alternating gradient descent for matrix factorization,” in Thirty-seventh Conference on Neural Infor- mation Processing Systems , 2023

    2023

  23. [31]

    Fast low-rank estimation by projected gradient descent: General statistical and algorithmic guarantees,

    Y . Chen and M. J. Wainwright, “Fast low-rank estimation by projected gradient descent: General statistical and algorithmic guarantees,” arXiv preprint arXiv:1509.03025, 2015

    2015 arXiv

  24. [32]

    Guaranteed matrix completion via non-convex factorization,

    R. Sun and Z.-Q. Luo, “Guaranteed matrix completion via non-convex factorization,” IEEE Transactions on Information Theory, vol. 62, no. 11, pp. 6535–6579, 2016

    2016

  25. [33]

    A riemannian geometry for low-rank matrix completion,

    B. Mishra, K. A. Apuroop, and R. Sepulchre, “A riemannian geometry for low-rank matrix completion,” arXiv preprint arXiv:1211.1550, 2012

    2012 arXiv

  26. [34]

    Guarantees of riemannian optimization for low rank matrix recovery,

    K. Wei, J.-F. Cai, T. F. Chan, and S. Leung, “Guarantees of riemannian optimization for low rank matrix recovery,” SIAM Journal on Matrix Analysis and Applications , vol. 37, no. 3, pp. 1198–1222, 2016

    2016

  27. [35]

    Riemannian preconditioning,

    B. Mishra and R. Sepulchre, “Riemannian preconditioning,” SIAM Journal on Optimization , vol. 26, no. 1, pp. 635–660, 2016

    2016

  28. [36]

    Accelerating sgd for highly ill- conditioned huge-scale online matrix completion,

    J. Zhang, H.-M. Chiu, and R. Y . Zhang, “Accelerating sgd for highly ill- conditioned huge-scale online matrix completion,” Advances in Neural Information Processing Systems , vol. 35, pp. 37 549–37 562, 2022

    2022

  29. [37]

    A preconditioned riemannian gra- dient descent algorithm for low-rank matrix recovery,

    F. Bian, J.-F. Cai, and R. Zhang, “A preconditioned riemannian gra- dient descent algorithm for low-rank matrix recovery,” arXiv preprint arXiv:2305.02543, 2023

    2023 arXiv

  30. [38]

    Globally q-linear gauss- newton method for overparameterized non-convex matrix sensing,

    X. Jia, F. FENG, D. Meng, and D. Sun, “Globally q-linear gauss- newton method for overparameterized non-convex matrix sensing,” in The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024

    2024

  31. [39]

    Learned robust pca: A scalable deep unfolding approach for high-dimensional outlier detection,

    H. Cai, J. Liu, and W. Yin, “Learned robust pca: A scalable deep unfolding approach for high-dimensional outlier detection,” Advances in Neural Information Processing Systems , vol. 34, pp. 16 977–16 989, 2021

    2021

  32. [40]

    Deeply learned robust matrix completion for large-scale low-rank data recovery,

    H. Cai, C. Kundu, J. Liu, and W. Yin, “Deeply learned robust matrix completion for large-scale low-rank data recovery,” arXiv preprint arXiv:2501.00677, 2024

    2024 arXiv

  33. [41]

    Low-rank matrix recovery with scaled subgradient methods: Fast and robust convergence without the condition number,

    T. Tong, C. Ma, and Y . Chi, “Low-rank matrix recovery with scaled subgradient methods: Fast and robust convergence without the condition number,” IEEE Transactions on Signal Processing , vol. 69, pp. 2396– 2409, 2021

    2021

  34. [42]

    Guarantees of a preconditioned subgradient algorithm for overparameterized asymmetric low-rank ma- trix recovery,

    P. Giampouras, H. Cai, and R. Vidal, “Guarantees of a preconditioned subgradient algorithm for overparameterized asymmetric low-rank ma- trix recovery,” arXiv preprint arXiv:2410.16826 , 2024

    2024 arXiv

  35. [43]

    Algorithmic regularization in over- parameterized matrix sensing and neural networks with quadratic ac- tivations,

    Y . Li, T. Ma, and H. Zhang, “Algorithmic regularization in over- parameterized matrix sensing and neural networks with quadratic ac- tivations,” in Conference On Learning Theory. PMLR, 2018, pp. 2–47

    2018

  36. [44]

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

    D. St ¨oger and M. Soltanolkotabi, “Small random initialization is akin to spectral learning: Optimization and generalization guarantees for overparameterized low-rank matrix reconstruction,” Advances in Neural Information Processing Systems , vol. 34, pp. 23 831–23 843, 2021

    2021

  37. [45]

    Implicit balancing and regularization: Generalization and convergence guarantees for overpa- rameterized asymmetric matrix sensing,

    M. Soltanolkotabi, D. St ¨oger, and C. Xie, “Implicit balancing and regularization: Generalization and convergence guarantees for overpa- rameterized asymmetric matrix sensing,” in The Thirty Sixth Annual Conference on Learning Theory . PMLR, 2023, pp. 5140–5142

    2023

  38. [46]

    Rank overspecified robust matrix recovery: Subgradient method and exact recovery,

    L. Ding, L. Jiang, Y . Chen, Q. Qu, and Z. Zhu, “Rank overspecified robust matrix recovery: Subgradient method and exact recovery,” Ad- vances in Neural Information Processing Systems 34 (NeurIPS 2021) , 2021

    2021

  39. [47]

    How over-parameterization slows down gradient descent in matrix sensing: The curses of symmetry and initialization,

    N. Xiong, L. Ding, and S. S. Du, “How over-parameterization slows down gradient descent in matrix sensing: The curses of symmetry and initialization,” in The Twelfth International Conference on Learning Representations, 2024

    2024

  40. [48]

    Global convergence of sub-gradient method for robust matrix recovery: Small initialization, noisy measurements, and over-parameterization,

    J. Ma and S. Fattahi, “Global convergence of sub-gradient method for robust matrix recovery: Small initialization, noisy measurements, and over-parameterization,” arXiv preprint arXiv:2202.08788 , 2022

    2022 arXiv

  41. [49]

    Projected gradient descent algorithm for low-rank matrix estimation,

    T. Zhang and X. Fan, “Projected gradient descent algorithm for low-rank matrix estimation,” arXiv preprint arXiv:2403.02704 , 2024

    2024 arXiv

  42. [50]

    Sharp restricted isometry property bounds for low-rank matrix recovery problems with corrupted measurements,

    Z. Ma, Y . Bi, J. Lavaei, and S. Sojoudi, “Sharp restricted isometry property bounds for low-rank matrix recovery problems with corrupted measurements,” in Proceedings of the AAAI Conference on Artificial Intelligence, vol. 36, no. 7, 2022, pp. 7672–7681

    2022

  43. [51]

    Noisy low-rank matrix optimization: Geometry of local minima and convergence rate,

    Z. Ma and S. Sojoudi, “Noisy low-rank matrix optimization: Geometry of local minima and convergence rate,” in International Conference on Artificial Intelligence and Statistics . PMLR, 2023, pp. 3125–3150

    2023

  44. [52]

    A primal-dual analysis of global optimality in nonconvex low-rank matrix recovery,

    X. Zhang, L. Wang, Y . Yu, and Q. Gu, “A primal-dual analysis of global optimality in nonconvex low-rank matrix recovery,” in International conference on machine learning . PMLR, 2018, pp. 5862–5871

    2018

  45. [53]

    Geometric analysis of noisy low-rank matrix recovery in the exact parametrized and the overparametrized regimes,

    Z. Ma, Y . Bi, J. Lavaei, and S. Sojoudi, “Geometric analysis of noisy low-rank matrix recovery in the exact parametrized and the overparametrized regimes,” INFORMS Journal on Optimization , 2023

    2023

  46. [54]

    The global optimization geometry of low-rank matrix optimization,

    Z. Zhu, Q. Li, G. Tang, and M. B. Wakin, “The global optimization geometry of low-rank matrix optimization,” IEEE Transactions on Information Theory, vol. 67, no. 2, pp. 1308–1331, 2021

    2021

  47. [55]

    The non-convex geometry of low-rank matrix optimization,

    Q. Li, Z. Zhu, and G. Tang, “The non-convex geometry of low-rank matrix optimization,” Information and Inference: A Journal of the IMA , vol. 8, no. 1, pp. 51–96, 2019

    2019

  48. [56]

    Global optimality in low-rank matrix optimization,

    Z. Zhu, Q. Li, G. Tang, and M. B. Wakin, “Global optimality in low-rank matrix optimization,” IEEE Transactions on Signal Processing , vol. 66, no. 13, pp. 3614–3628, 2018

    2018

  49. [57]

    Guaranteed rank minimization via singular value projection,

    P. Jain, R. Meka, and I. Dhillon, “Guaranteed rank minimization via singular value projection,” Advances in Neural Information Processing Systems, vol. 23, 2010. 12

    2010

  50. [58]

    Weighted low-rank approximations,

    N. Srebro and T. Jaakkola, “Weighted low-rank approximations,” in Proceedings of the 20th international conference on machine learning (ICML-03), 2003, pp. 720–727

    2003

  51. [59]

    1-bit matrix completion,

    M. A. Davenport, Y . Plan, E. Van Den Berg, and M. Wootters, “1-bit matrix completion,” Information and Inference: A Journal of the IMA , vol. 3, no. 3, pp. 189–223, 2014

    2014

  52. [60]

    Generalized Assorted Pixel Camera: Post-Capture Control of Resolution, Dynamic Range and Spectrum,

    F. Yasuma, T. Mitsunaga, D. Iso, and S. K. Nayar, “Generalized Assorted Pixel Camera: Post-Capture Control of Resolution, Dynamic Range and Spectrum,” Tech. Rep., Nov 2008. APPENDIX A. Preliminaries We begin by presenting a lemma that bridges the assump- tions of Theorem 2 wit...

    2008

  53. [61]

    Then with probability at least 1−3n−c1 −2e−c2mδ2r+1, the following states holds: (1) the linear map A(·) satisfies rank-(2r + 1) RIP with constant δ2r+1; (2) the noise terms ∥A∗(s)Rt∥2 P ∗ Rt ≤ Eopt, ∥A∗(s)L⊤ t ∥2 P ∗ Lt ≤ Eopt, where Eopt = Ce ν2rn log n m and n = max {n1, n2...

Pith tools

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