pith. sign in

arxiv: 2404.12828 · v2 · submitted 2024-04-19 · 🧮 math.OC · math.ST· stat.TH

Low solution rank of the matrix LASSO under RIP with consequences for rank-constrained algorithms

Andrew D. McRae This is my paper

Pith reviewed 2026-05-24 02:31 UTC · model grok-4.3

classification 🧮 math.OC math.STstat.TH
keywords matrix LASSOnuclear norm penaltyrestricted isometry propertylow-rank recoveryBurer-Monteiro factorizationproximal gradient descentrank-constrained optimizationconvex relaxation
0
0 comments X

The pith

The matrix LASSO yields a unique solution whose rank is bounded by the ground truth rank when the measurement operator satisfies RIP and noise is sufficiently small relative to the penalty.

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

The paper shows that the nuclear-norm penalized least-squares problem produces low-rank solutions under the same RIP assumptions used for error bounds in matrix sensing. A sympathetic reader would care because this supplies the missing justification for why the convex relaxation actually returns low-rank matrices outside narrow cases, and it transfers guarantees to nonconvex methods. If the ground truth is low-rank, the operator obeys matrix RIP, and measurement error stays small enough compared to the penalty parameter, the LASSO solution is unique and its rank is controlled by the ground truth rank. The same conditions then imply linear convergence of a rank-projected proximal gradient method from any starting point and that every second-order critical point of the Burer-Monteiro factorization is globally optimal and recovers the LASSO solution.

Core claim

If the ground truth matrix has low rank, the linear measurement operator satisfies the matrix restricted isometry property, and the measurement error is small enough relative to the nuclear norm penalty, then the unique LASSO solution has rank approximately bounded by that of the ground truth. From this bound it follows that a low-rank-projected proximal gradient descent algorithm converges linearly to the LASSO solution from arbitrary initialization and that the factored Burer-Monteiro formulation has a benign landscape in which every second-order critical point is globally optimal.

What carries the argument

The matrix restricted isometry property of the linear measurement operator, which controls how the operator distorts the nuclear norm and Frobenius norm of low-rank matrices and thereby transfers the rank bound from ground truth to the penalized solution.

If this is right

  • Low-rank projected proximal gradient descent converges linearly to the LASSO solution from any initialization.
  • All second-order critical points of the Burer-Monteiro factored formulation are globally optimal and equal the LASSO solution.
  • The rank bound on the LASSO solution holds under the same RIP assumptions already used for classical low-rank matrix sensing error bounds.
  • The nuclear-norm penalty succeeds in promoting low solution rank outside the very specific circumstances previously analyzed.

Where Pith is reading between the lines

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

  • The result supplies a theoretical route to certify that a computed low-rank matrix is the unique LASSO solution without solving the convex program directly.
  • Similar rank-control arguments may apply to other convex relaxations whose penalties are not strictly rank-promoting in finite dimensions.
  • The benign-landscape claim for the factored problem could be tested numerically on random RIP operators of moderate size to check the predicted absence of spurious critical points.

Load-bearing premise

The linear measurement operator must satisfy the matrix restricted isometry property with constants strong enough for the rank bound to hold.

What would settle it

A concrete counter-example consisting of a low-rank ground truth, an operator obeying RIP with the required constants, and measurement error small relative to the penalty, yet the computed LASSO solution has rank strictly larger than the ground truth rank.

read the original abstract

We show that solutions to the popular convex matrix LASSO problem (nuclear-norm--penalized linear least-squares) have low rank under similar assumptions as required by classical low-rank matrix sensing error bounds. Although the purpose of the nuclear norm penalty is to promote low solution rank, a proof has not yet (to our knowledge) been provided outside very specific circumstances. Furthermore, we show that this result has significant theoretical consequences for nonconvex rank-constrained optimization approaches. Specifically, we show that if (a) the ground truth matrix has low rank, (b) the (linear) measurement operator has the matrix restricted isometry property (RIP), and (c) the measurement error is small enough relative to the nuclear norm penalty, then the (unique) LASSO solution has rank (approximately) bounded by that of the ground truth. From this, we show (a) that a low-rank--projected proximal gradient descent algorithm will converge linearly to the LASSO solution from any initialization, and (b) that the nonconvex landscape of the low-rank Burer-Monteiro--factored problem formulation is benign in the sense that all second-order critical points are globally optimal and yield the LASSO solution.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper claims that under the matrix restricted isometry property (RIP) with suitable constants, a low-rank ground-truth matrix, and sufficiently small measurement noise relative to the nuclear-norm penalty parameter, any solution to the matrix LASSO (nuclear-norm penalized least squares) has rank approximately bounded by that of the ground truth. It further claims that this low-rank property implies linear convergence of a low-rank projected proximal gradient algorithm to the LASSO solution from arbitrary initialization and that the Burer-Monteiro factored formulation has a benign landscape in which all second-order critical points are globally optimal and recover the LASSO solution.

Significance. If the central low-rank claim holds with the stated uniqueness, the result supplies a previously missing general proof that the nuclear-norm penalty indeed produces low-rank solutions under the same RIP conditions used for recovery error bounds. The algorithmic consequences would then provide a rigorous link between the convex LASSO and practical non-convex rank-constrained methods, including explicit linear convergence rates and a landscape guarantee for the factored formulation.

major comments (2)
  1. [Abstract, §1] Abstract and opening paragraph of §1: the claim that the LASSO solution is 'unique' (and therefore that 'the' solution has low rank) is not justified by the matrix RIP assumption alone. Matrix RIP with constant δ_{2r} controls the operator only on matrices of rank at most 2r and does not imply injectivity of A over the full space of n×n matrices; consequently the quadratic term ½‖A(X)−y‖² is not strictly convex and the composite objective can admit multiple minimizers with identical nuclear norms even when conditions (a)–(c) hold. A separate null-space or strict-convexity argument stronger than RIP is required for uniqueness but is not supplied by the stated hypotheses.
  2. [§3] §3 (or the section containing the main rank bound): the low-rank conclusion is stated for 'the (unique) LASSO solution,' so the rank bound itself is conditional on uniqueness. If multiple minimizers exist, the bound may hold for some but not all of them, which would weaken the subsequent claims about projected proximal gradient convergence and the Burer-Monteiro landscape.
minor comments (2)
  1. [Theorem 1] Notation for the RIP constants and the precise dependence of the rank bound on δ_{2r} and λ should be stated explicitly in the main theorem statement rather than only in the proof.
  2. [Abstract] The abstract states 'approximately bounded'; the precise additive or multiplicative factor in the rank bound should be written out in the theorem.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful and insightful comments. We agree that uniqueness of the LASSO solution is not implied by the stated RIP conditions alone. Our rank bound in fact applies to every minimizer, and we will revise the manuscript to remove the uniqueness claim while preserving the main results and algorithmic consequences. We address each major comment below.

read point-by-point responses

  1. Referee: [Abstract, §1] Abstract and opening paragraph of §1: the claim that the LASSO solution is 'unique' (and therefore that 'the' solution has low rank) is not justified by the matrix RIP assumption alone. Matrix RIP with constant δ_{2r} controls the operator only on matrices of rank at most 2r and does not imply injectivity of A over the full space of n×n matrices; consequently the quadratic term ½‖A(X)−y‖² is not strictly convex and the composite objective can admit multiple minimizers with identical nuclear norms even when conditions (a)–(c) hold. A separate null-space or strict-convexity argument stronger than RIP is required for uniqueness but is not supplied by the stated hypotheses.

    Authors: We agree that matrix RIP does not imply uniqueness or strict convexity over the full matrix space. The proof of the approximate rank bound applies verbatim to every global minimizer of the LASSO objective under assumptions (a)–(c). We will revise the abstract and §1 to state that every LASSO solution (rather than the unique solution) has rank approximately bounded by that of the ground truth. This makes the claims accurate without altering the technical content. revision: yes

  2. Referee: [§3] §3 (or the section containing the main rank bound): the low-rank conclusion is stated for 'the (unique) LASSO solution,' so the rank bound itself is conditional on uniqueness. If multiple minimizers exist, the bound may hold for some but not all of them, which would weaken the subsequent claims about projected proximal gradient convergence and the Burer-Monteiro landscape.

    Authors: We will update §3 and the algorithmic sections to state the rank bound for every minimizer. The linear convergence of low-rank projected proximal gradient then holds when the target is any LASSO minimizer (the proof uses only the low-rank property of that target). For the Burer-Monteiro landscape, all second-order critical points remain globally optimal and recover some LASSO solution; we will add a clarifying sentence that the benign-landscape guarantee is with respect to the (possibly non-unique) set of LASSO solutions. revision: yes

Circularity Check

0 steps flagged

No circularity; derivation conditioned on external RIP assumption

full rationale

The paper conditions its low-rank bound and algorithmic consequences on the standard external matrix RIP assumption (plus small noise relative to the nuclear-norm penalty). No step in the provided abstract or claim reduces the claimed rank bound or uniqueness to a quantity defined by the result itself, to a fitted parameter renamed as prediction, or to a self-citation chain. The derivation therefore remains self-contained against external benchmarks and receives the default non-circularity finding.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on the matrix RIP as a domain assumption from prior literature; no free parameters or invented entities are introduced.

axioms (1)
  • domain assumption The linear measurement operator satisfies the matrix restricted isometry property (RIP)
    Invoked explicitly as condition (b) for the low-rank bound and all downstream claims.

pith-pipeline@v0.9.0 · 5751 in / 1294 out tokens · 41426 ms · 2026-05-24T02:31:59.030894+00:00 · methodology

discussion (0)

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

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

58 extracted references · 58 canonical work pages

  1. [1]

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

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

    work page 2011

  2. [2]

    Estimation of (near) l ow-rank matrices with noise and high-dimensional scaling,

    S. Negahban and M. J. Wainwright, “Estimation of (near) l ow-rank matrices with noise and high-dimensional scaling,” Ann. Stat. , vol. 39, no. 2, 2011

    work page 2011

  3. [3]

    Estimation of high-dimensi onal low-rank matrices,

    A. Rohde and A. B. Tsybakov, “Estimation of high-dimensi onal low-rank matrices,” Ann. Stat., vol. 39, no. 2, 2011

    work page 2011

  4. [4]

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

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

    work page 2010

  5. [5]

    ROP: Matrix recovery via rank-one projections,

    T. T. Cai and A. Zhang, “ROP: Matrix recovery via rank-one projections,” Ann. Stat. , vol. 43, no. 1, pp. 102–138, 2015

    work page 2015

  6. [6]

    A fast iterative shrinkage-thr esholding algorithm for linear inverse problems,

    A. Beck and M. Teboulle, “A fast iterative shrinkage-thr esholding algorithm for linear inverse problems,” SIAM J. Imaging. Sci. , vol. 2, no. 1, pp. 183–202, 2009

    work page 2009

  7. [7]

    Fast randomized singular value thresholding for low-rank optimization,

    T.-H. Oh, Y. Matsushita, Y.-W. Tai, and I. S. Kweon, “Fast randomized singular value thresholding for low-rank optimization,” IEEE Trans. Pattern Anal. Mach. Intell. , vol. 40, no. 2, pp. 376–391, 2018

    work page 2018

  8. [8]

    General low-rank matrix o ptimization: Geometric analysis and sharper bounds,

    H. Zhang, Y. Bi, and J. Lavaei, “General low-rank matrix o ptimization: Geometric analysis and sharper bounds,” in Proc. Conf. Neural Inf. Process. Syst. (NeurIPS) , (Virtual confer- ence), pp. 27369–27380, Dec. 2021

    work page 2021

  9. [9]

    An equivalence between cr itical points for rank constraints versus low-rank factorizations,

    W. Ha, H. Liu, and R. F. Barber, “An equivalence between cr itical points for rank constraints versus low-rank factorizations,” SIAM J. Optim. , vol. 30, no. 4, pp. 2927–2955, 2020

    work page 2020

  10. [10]

    The non-convex geometry of lo w-rank matrix optimization,

    Q. Li, Z. Zhu, and G. Tang, “The non-convex geometry of lo w-rank matrix optimization,” Inform. Inference., vol. 8, no. 1, pp. 51–96, 2019

    work page 2019

  11. [11]

    Complexity bo unds for second-order optimality in unconstrained optimization,

    C. Cartis, N. I. M. Gould, and P. L. Toint, “Complexity bo unds for second-order optimality in unconstrained optimization,” J. Complexity , vol. 28, no. 1, pp. 93–108, 2012

    work page 2012

  12. [12]

    Gradient descent only co nverges to minimizers: Non-isolated critical points and invariant regions,

    I. Panageas and G. Piliouras, “Gradient descent only co nverges to minimizers: Non-isolated critical points and invariant regions,” in Proc. Innovations Theor. Comput. Sci. (ITCS) , (Berkeley, California), Jan. 2017

    work page 2017

  13. [13]

    An overview of low-rank matrix recovery from incomplete observations,

    M. A. Davenport and J. Romberg, “An overview of low-rank matrix recovery from incomplete observations,” IEEE J. Sel. Topics Signal Process. , vol. 10, no. 4, pp. 608–622, 2016. 16

    work page 2016

  14. [14]

    Low-rank matrix compl etion: A contemporary survey,

    L. T. Nguyen, J. Kim, and B. Shim, “Low-rank matrix compl etion: A contemporary survey,” IEEE Access, vol. 7, pp. 94215–94237, 2019

    work page 2019

  15. [15]

    Robust princi pal component analysis?,

    E. J. Cand` es, X. Li, Y. Ma, and J. Wright, “Robust princi pal component analysis?,” J. ACM, vol. 58, no. 3, pp. 1–37, 2011

    work page 2011

  16. [16]

    Low-rank positive semidefinit e matrix recovery from corrupted rank-one measurements,

    Y. Li, Y. Sun, and Y. Chi, “Low-rank positive semidefinit e matrix recovery from corrupted rank-one measurements,” IEEE Trans. Signal Process. , vol. 65, no. 2, pp. 397–408, 2017

    work page 2017

  17. [17]

    No spurious local minima in n onconvex low rank problems: A unified geometric analysis,

    R. Ge, C. Jin, and Y. Zheng, “No spurious local minima in n onconvex low rank problems: A unified geometric analysis,” in Proc. Int. Conf. Mach. Learn. (ICML) , (Sydney, Australia), pp. 1233–1242, Aug. 2017

    work page 2017

  18. [18]

    Exact guarantees on the abse nce of spurious local minima for non-negative rank-1 robust principal component analysis,

    S. Fattahi and S. Sojoudi, “Exact guarantees on the abse nce of spurious local minima for non-negative rank-1 robust principal component analysis, ” J. Mach. Learn. Res. , vol. 21, no. 59, pp. 1–51, 2020

    work page 2020

  19. [19]

    Nonconvex rob ust low-rank matrix recovery,

    X. Li, Z. Zhu, A. Man-Cho So, and R. Vidal, “Nonconvex rob ust low-rank matrix recovery,” SIAM J. Optim. , vol. 30, no. 1, pp. 660–686, 2020

    work page 2020

  20. [20]

    Global convergence of sub-gradie nt method for robust matrix recovery: Small initialization, noisy measurements, and over-param eterization,

    J. Ma and S. Fattahi, “Global convergence of sub-gradie nt method for robust matrix recovery: Small initialization, noisy measurements, and over-param eterization,” J. Mach. Learn. Res. , vol. 24, no. 96, pp. 1–84, 2023

    work page 2023

  21. [21]

    Rank oversp ecified robust matrix recovery: Subgradient method and exact recovery,

    L. Ding, L. Jiang, Y. Chen, Q. Qu, and Z. Zhu, “Rank oversp ecified robust matrix recovery: Subgradient method and exact recovery,” in Proc. Conf. Neural Inf. Process. Syst. (NeurIPS) , (Virtual conference), pp. 26767–26778, Dec. 2021

    work page 2021

  22. [22]

    Nuclear -norm penalization and optimal rates for noisy low-rank matrix completion,

    V. Koltchinskii, K. Lounici, and A. Tsybakov, “Nuclear -norm penalization and optimal rates for noisy low-rank matrix completion,” Ann. Stat. , vol. 39, no. 5, pp. 2302–2329, 2011

    work page 2011

  23. [23]

    Rank penalized estimators for high-dimensi onal matrices,

    O. Klopp, “Rank penalized estimators for high-dimensi onal matrices,” Electron. J. Stat. , vol. 5, pp. 1161–1183, 2011

    work page 2011

  24. [24]

    Optimal selection o f reduced rank estimators of high-dimensional matrices,

    F. Bunea, Y. She, and M. H. Wegkamp, “Optimal selection o f reduced rank estimators of high-dimensional matrices,” Ann. Stat. , vol. 39, no. 2, 2011

    work page 2011

  25. [25]

    Reduced rank regressi on via adaptive nuclear norm penalization,

    K. Chen, H. Dong, and K.-S. Chan, “Reduced rank regressi on via adaptive nuclear norm penalization,” Biometrika, vol. 100, no. 4, pp. 901–920, 2013

    work page 2013

  26. [26]

    Hastie, R

    T. Hastie, R. Tibshirani, and M. Wainwright, Statistical Learning with Sparsity . New York: CRC Press, 2015

    work page 2015

  27. [27]

    Nonconvex optimization me ets low-rank matrix factoriza- tion: An overview,

    Y. Chi, Y. M. Lu, and Y. Chen, “Nonconvex optimization me ets low-rank matrix factoriza- tion: An overview,” IEEE Trans. Signal Process. , vol. 67, no. 20, pp. 5239–5269, 2019

    work page 2019

  28. [28]

    A deterministic theory for exac t non-convex phase retrieval,

    B. Yonel and B. Yazici, “A deterministic theory for exac t non-convex phase retrieval,” IEEE Trans. Signal Process., vol. 68, pp. 4612–4626, 2020

    work page 2020

  29. [29]

    Convex and nonconve x optimization are both minimax-optimal for noisy blind deconvolution under rando m designs,

    Y. Chen, J. Fan, B. Wang, and Y. Yan, “Convex and nonconve x optimization are both minimax-optimal for noisy blind deconvolution under rando m designs,” J. Amer. Stat. Assoc. , vol. 118, no. 542, pp. 858–868, 2023

    work page 2023

  30. [30]

    A unified computational and statistical framework for nonconvex low-rank matrix estimation,

    L. Wang, X. Zhang, and Q. Gu, “A unified computational and statistical framework for nonconvex low-rank matrix estimation,” in Proc. Int. Conf. Artif. Intell. Statist. (AISTATS) , (Ft. Lauderdale, FL, USA), pp. 981–990, Apr. 2017

    work page 2017

  31. [31]

    From symmetry to geometr y: Tractable nonconvex prob- lems,

    Y. Zhang, Q. Qu, and J. Wright, “From symmetry to geometr y: Tractable nonconvex prob- lems,” 2020

    work page 2020

  32. [32]

    Matrix completion has no spur ious local minimum,

    R. Ge, J. D. Lee, and T. Ma, “Matrix completion has no spur ious local minimum,” in Proc. Conf. Neural Inf. Process. Syst. (NeurIPS) , vol. 29, (Barcelona, Spain), 2016

    work page 2016

  33. [33]

    Symmetry, saddle points, and global optimization landscape of nonconvex matrix fact orization,

    X. Li, J. Lu, R. Arora, J. Haupt, H. Liu, Z. Wang, and T. Zha o, “Symmetry, saddle points, and global optimization landscape of nonconvex matrix fact orization,” IEEE Trans. Inf. Theory, vol. 65, no. 6, pp. 3489–3514, 2019

    work page 2019

  34. [34]

    How much restricted isometry is needed in nonconvex matrix recovery?,

    R. Y. Zhang, C. Josz, S. Sojoudi, and J. Lavaei, “How much restricted isometry is needed in nonconvex matrix recovery?,” in Proc. Conf. Neural Inf. Process. Syst. (NeurIPS) , (Montreal, Canada), pp. 5586–5597, Dec. 2018. 17

    work page 2018

  35. [35]

    Sharp restricte d isometry bounds for the inexistence of spurious local minima in nonconvex matrix recovery,

    R. Y. Zhang, S. Sojoudi, and J. Lavaei, “Sharp restricte d isometry bounds for the inexistence of spurious local minima in nonconvex matrix recovery,” J. Mach. Learn. Res. , vol. 20, no. 114, 2019

    work page 2019

  36. [36]

    A geometric analysis of pha se retrieval,

    J. Sun, Q. Qu, and J. Wright, “A geometric analysis of pha se retrieval,” Found. Comput. Math., vol. 18, no. 5, pp. 1131–1198, 2018

    work page 2018

  37. [37]

    Sharp global guarantees for nonconvex low -rank matrix recovery in the over- parameterized regime,

    R. Y. Zhang, “Sharp global guarantees for nonconvex low -rank matrix recovery in the over- parameterized regime,” Apr. 2021

    work page 2021

  38. [38]

    Inductive matrix completion: No bad local minima and a fast algorithm,

    P. Zilber and B. Nadler, “Inductive matrix completion: No bad local minima and a fast algorithm,” in Proc. Int. Conf. Mach. Learn. (ICML) , (Baltimore, Maryland), pp. 27671– 27692, July 2022

    work page 2022

  39. [39]

    A new co mplexity metric for nonconvex rank-one generalized matrix completion,

    H. Zhang, B. Yal¸ cın, J. Lavaei, and S. Sojoudi, “A new co mplexity metric for nonconvex rank-one generalized matrix completion,” Math. Program., 2023

    work page 2023

  40. [40]

    On critical points o f quadratic low-rank matrix opti- mization problems,

    A. Uschmajew and B. Vandereycken, “On critical points o f quadratic low-rank matrix opti- mization problems,” IMA J. Numer. Anal. , vol. 40, no. 4, pp. 2626–2651, 2020

    work page 2020

  41. [41]

    Can learning be explained by local optimality in low-rank matrix recovery?,

    J. Ma and S. Fattahi, “Can learning be explained by local optimality in low-rank matrix recovery?,” Feb. 2023

    work page 2023

  42. [42]

    Global optimalit y in low-rank matrix optimiza- tion,

    Z. Zhu, Q. Li, G. Tang, and M. B. Wakin, “Global optimalit y in low-rank matrix optimiza- tion,” IEEE Trans. Signal Process. , vol. 66, no. 13, pp. 3614–3628, 2018

    work page 2018

  43. [43]

    The global optimi zation geometry of low-rank matrix optimization,

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

    work page 2021

  44. [44]

    On the absence of spurious local min ima in nonlinear low-rank matrix recovery problems,

    Y. Bi and J. Lavaei, “On the absence of spurious local min ima in nonlinear low-rank matrix recovery problems,” in Proc. Int. Conf. Artif. Intell. Statist. (AISTATS) , (Virtual confer- ence), pp. 379–387, Apr. 2021

    work page 2021

  45. [45]

    Local and global linear c onvergence of general low-rank matrix recovery problems,

    Y. Bi, H. Zhang, and J. Lavaei, “Local and global linear c onvergence of general low-rank matrix recovery problems,” in Proc. AAAI Conf. Artif. Intell. (AAAI) , vol. 36, (Virtual conference), pp. 10129–10137, Feb. 2022

    work page 2022

  46. [46]

    Global o ptimality of local search for low rank matrix recovery,

    S. Bhojanapalli, B. Neyshabur, and N. Srebro, “Global o ptimality of local search for low rank matrix recovery,” in Proc. Conf. Neural Inf. Process. Syst. (NeurIPS) , (Barcelona, Spain), pp. 3873–3881, Dec. 2016

    work page 2016

  47. [47]

    N on-square matrix sensing without spurious local minima via the Burer-Monteiro approach,

    D. Park, A. Kyrillidis, C. Carmanis, and S. Sanghavi, “N on-square matrix sensing without spurious local minima via the Burer-Monteiro approach,” in Proc. Int. Conf. Artif. Intell. Statist. (AISTATS), (Fort Lauderdale, FL, USA), pp. 65–74, 2017

    work page 2017

  48. [48]

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

    X. Zhang, L. Wang, Y. Yu, and Q. Gu, “A primal-dual analys is of global optimality in nonconvex low-rank matrix recovery,” in Proc. Int. Conf. Mach. Learn. (ICML) , (Stockholm, Sweden), pp. 5862–5871, July 2018

    work page 2018

  49. [49]

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

    Z. Ma, Y. Bi, J. Lavaei, and S. Sojoudi, “Sharp restricte d isometry property bounds for low- rank matrix recovery problems with corrupted measurements ,” in Proc. AAAI Conf. Artif. Intell. (AAAI) , vol. 36, (Virtual conference), pp. 7672–7681, Feb. 2022

    work page 2022

  50. [50]

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

    Z. Ma and S. Sojoudi, “Noisy low-rank matrix optimizati on: Geometry of local minima and convergence rate,” in Proc. Int. Conf. Artif. Intell. Statist. (AISTATS) , (Valencia, Spain), pp. 3125–3150, 2023

    work page 2023

  51. [51]

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

    Z. Ma, Y. Bi, J. Lavaei, and S. Sojoudi, “Geometric analy sis of noisy low-rank matrix recovery in the exact parametrized and the overparametrized regimes ,” INFORMS J. Opt. , vol. 5, no. 4, pp. 356–375, 2023

    work page 2023

  52. [52]

    Improved global guarantees for the noncon vex Burer-Monteiro factorization via rank overparameterization,

    R. Y. Zhang, “Improved global guarantees for the noncon vex Burer-Monteiro factorization via rank overparameterization,” Math. Program., 2024

    work page 2024

  53. [53]

    Nonconvex matrix factorizati on is geodesically convex: Global landscape analysis for fixed-rank matrix optimization from a Riemannian perspective,

    Y. Luo and N. G. Trillos, “Nonconvex matrix factorizati on is geodesically convex: Global landscape analysis for fixed-rank matrix optimization from a Riemannian perspective,” Sept. 2022. 18

    work page 2022

  54. [54]

    R. A. Horn and C. R. Johnson, Matrix Analysis . Cambridge, United Kingdom: Cambridge University Press, 2 ed., 2013

    work page 2013

  55. [55]

    Bhatia, Matrix Analysis

    R. Bhatia, Matrix Analysis . New York: Springer, 1997

    work page 1997

  56. [56]

    Foucart and H

    S. Foucart and H. Rauhut, A Mathematical Introduction to Compressive Sensing . New York: Birkh¨ auser, 2013

    work page 2013

  57. [57]

    Exact wor st-case convergence rates of the proximal gradient method for composite convex minimiza tion,

    A. B. Taylor, J. M. Hendrickx, and F. Glineur, “Exact wor st-case convergence rates of the proximal gradient method for composite convex minimiza tion,” J. Opt. Theory Appl. , vol. 178, pp. 455–476, 2018

    work page 2018

  58. [58]

    The usual smooth lift of the nu clear norm regularizer enjoys 2 ⇒ 1,

    N. Boumal and A. D. McRae, “The usual smooth lift of the nu clear norm regularizer enjoys 2 ⇒ 1,” Oct. 2024. 19

    work page 2024