Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
Open accessThe DOI matches its Crossref record; 267 of the 279 references it cites were found in a registry or an index.
Abstract
Substantial progress has been made recently on developing provably accurate and efficient algorithms for low-rank matrix factorization via nonconvex optimization. While conventional wisdom often takes a dim view of nonconvex optimization algorithms due to their susceptibility to spurious local minima, simple iterative methods such as gradient descent have been remarkably successful in practice. The theoretical footings, however, had been largely lacking until recently. In this tutorial-style overview, we highlight the important role of statistical models in enabling efficient nonconvex optimization with performance guarantees. We review two contrasting approaches: (1) two-stage algorithms, which consist of a tailored initialization step followed by successive refinement; and (2) global landscape analysis and initialization-free algorithms. Several canonical matrix factorization problems are discussed, including but not limited to matrix sensing, phase retrieval, matrix completion, blind deconvolution, and robust principal component analysis. Special care is taken to illustrate the key technical insights underlying their analyses. This article serves as a testament that the integrated consideration of optimization and statistics leads to fruitful research findings.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Figures
![Fig. 1 An example of f ( · ) taken from [21]. Here, f ( x ) = x 2 if x ∈ [ -6 , 6] and f ( x ) = x 2 +1 . 5 | x | (cos( | x | -6) -1) if | x | > 6 . It satisfies RC ( μ, λ , ζ ) with some μ, λ > 0 and ζ = ∞ , but is clearly nonconvex.](https://figures.cochat.ai/paper-figures/efaa47591b5349acbef65a17306cdcb7/nonconvex-optimization-meets-low-rank-matrix-factorization-an-overview-figure-1.png)
![Fig. 2 Illustration of the function f ( x ) = 1 4 ‖ xx ⊤ -M ‖ 2 F , where x = [ x 1 , x 2 ] ⊤ and M =[ 1 -0 . 5 -0 . 5 1 ] .](https://figures.cochat.ai/paper-figures/a0e28a4860794cd1847da664546e9c3b/nonconvex-optimization-meets-low-rank-matrix-factorization-an-overview-figure-2.png)

![Fig. 4 Comparisons of 3 designs of the preprocessing function for estimating a 64 × 64 cameraman image from phaseless measurements under Poisson noise. (Red curve) the subset scheme in (119), where the parameter γ has been optimized for each fixed α ; (Green curve) the function T ∗ α ( · ) defined in [129]; (Blue curve) the uniformly optimal design T ∗ ( · ) in [130].](https://figures.cochat.ai/paper-figures/e8c537207c1141a888de05d5b42b9ec8/nonconvex-optimization-meets-low-rank-matrix-factorization-an-overview-figure-4.png)
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
In the citing paper
“Fortunately, under the high-dimensional statistical setting, the local strong convexity and smoothness of the nonconvex loss functions can be exploited to tame the nonconvexity for various learning models, e.g., blind demixing [189], phase retrieval [254], and shallow neural networks [255].”
From Edge artificial intelligence for 6g: vision, enabling technologies, and applications (2022) · cites this paper as [254]
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Matrix Factorization Techniques for Recommender Systems
Koren, Y., Bell, R., & Volinsky, C. (2009) · Computer · doi:10.1109/mc.2009.263 · Cited by 11,673 · cited 1×
“However, despite its wide use and remarkable performance in practice [15], [16], the foundational understanding of generic nonconvex optimization is far from mature.”
BackgroundA Stochastic Approximation Method
Robbins, H., & Monro, S. (1951) · The Annals of Mathematical Statistics · doi:10.1214/aoms/1177729586 · Cited by 9,643
Robust principal component analysis?
Candès, E. J., Li, X., Ma, Y., & Wright, J. (2011) · Journal of the ACM · doi:10.1145/1970392.1970395 · Cited by 6,921 · cited 2×
“Examples include low-rank matrix completion [1]–[3], phase retrieval [4], blind deconvolution and self-calibration [5], [6], robust principal component analysis [7], [8], synchronization and alignment [9]–[11], to name just a few.”
BackgroundA method for solving the convex programming problem with convergence rate O(1/k^2)
Nesterov, Y. E. (1983) · Доклады Академии наук · Cited by 6,318
Phase retrieval algorithms: a comparison
Fienup, J. R. (1982) · Applied Optics · doi:10.1364/ao.21.002758 · Cited by 5,596 · cited 3×
“This is exactly the Error Reduction (ER) algorithm proposed by Gerchberg and Saxton [43, 112] in the 1970s.”
BackgroundMethodExact Matrix Completion via Convex Optimization
Candès, E. J., & Recht, B. (2009) · Foundations of Computational Mathematics · doi:10.1007/s10208-009-9045-5 · Cited by 4,877
A practical algorithm for the determination of phase from image and diffraction plane pictures
Gerchberg, R. W. (1972) · Optik · Cited by 4,519
Halko, N., Martinsson, P. G., & Tropp, J. A. (2011) · SIAM Review · doi:10.1137/090771806 · Cited by 4,002
The restricted isometry property and its implications for compressed sensing
Candès, E. J. (2008) · Comptes Rendus. Mathématique · doi:10.1016/j.crma.2008.03.014 · Cited by 3,686 · cited 2×
“Lemma 3 ([43]): If an operator A satisfies the 2r-RIP with RIP constant δ2r < 1, then ∣ ∣ 〈 A(X),A(Y ) 〉 − 〈X,Y 〉 ∣ ∣ ≤ δ2r‖X‖F‖Y ‖F (23)”
BackgroundIntroductory Lectures on Convex Optimization: A Basic Course
Nesterov, Y. E. (2014) · Medical Entomology and Zoology · Cited by 3,557
Research works printed but not linked: 6
- Y. Chi, Y. M. Lu, and Y. Chen, "Nonconvex optimization meets low-rank matrix factorization: An overview," arXiv:1809.09573, 2018. · arXiv
- Q. Qu, Y. Zhang, Y. Eldar, and J. Wright, "Convolutional phase retrieval," in Proc. Neural Inf. Process. Syst., 2017, pp. 6086-6096.
- Z. Allen-Zhu, "Recent advances in stochastic convex and non-convex optimization," ICML Tut., 2017. [Online]. Available: http://people.csail.mit.edu/zeyuan/topics/icml-2017.htm
- M. Soltanolkotabi, "Algorithms and theory for clustering and nonconvex quadratic programming," Ph.D. dissertation, Stanford Univ., Stanford, U.K., 2014.
- J. Duchi, S. Shalev-Shwartz, Y. Singer, and T. Chandra, "Efficient pro- jections onto the ℓ 1 -ball for learning in high dimensions," in Proc. Int. Conf. Mach. Learn., 2008, pp. 272-279.
- T. Zhao, Z. Wang, and H. Liu, "Nonconvex low rank matrix factorization via inexact first order oracle," in Proc. Adv. Neural Inf. Process. Syst., 2015, pp. 559-567.
Cited by
Items 201–300 of 390
Temporal Autoregressive Matrix Factorization for High-Dimensional Time Series Prediction of OSS
Chen, L., Yang, Y., & Wang, W. (2023) · IEEE Transactions on Neural Networks and Learning Systems · doi:10.1109/tnnls.2023.3271327 · Cited by 7
Hyperparameter tuning via trajectory predictions: stochastic prox-linear methods in matrix sensing
Lou, M., Chandrasekher, K. A., & Pananjady, A. (2025) · Mathematical Programming · doi:10.1007/s10107-025-02279-0 · Cited by 7
Implicit regularization makes overparameterized asymmetric matrix sensing robust to perturbations
Wind, J. S. (2026) · Philosophical Transactions of the Royal Society A Mathematical Physical and Engineering Sciences · doi:10.1098/rsta.2025.0120 · Cited by 8
“For an overview, see Chi et al. [2019].”
Real Color Image Denoising Using t-Product- Based Weighted Tensor Nuclear Norm Minimization
Liu, M., Zhang, X., & Tang, L. (2019) · IEEE Access · doi:10.1109/access.2019.2960078 · Cited by 7
“Low-rank matrix representation in [2], [10], [37]–[39] has drawn a lot of attention due to the rapid progress in convex and non-convex optimization during the past decades.”
BackgroundExact matrix completion based on low rank Hankel structure in the Fourier domain
Chen, J., Gao, W., & Wei, K. (2021) · Applied and Computational Harmonic Analysis · doi:10.1016/j.acha.2021.05.002 · Cited by 7
Low rank matrix recovery with adversarial sparse noise*
Xu, H., Li, S., & Lin, J. (2021) · Inverse Problems · doi:10.1088/1361-6420/ac44dc · Cited by 7
“We refer the interested readers to [17, 19, 21] for recent overviews and limit our discussions to the most relevant literature in what follows.”
Sun, J. F., Wang, G., Giannakis, G. B., Yang, Q., & Yang, Z. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1911.00934 · Cited by 7
Sparse GCA and Thresholded Gradient DescentPreprint
Gao, S., & Ma, Z. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2107.00371 · Cited by 7
“The following lemma is adapted from Lemma 4 in [10] and it is an extension of the gradient descent condition from vectors to rank r matrices.”
BackgroundMethodInfluentialBraun, G., Tyagi, H., & Biernacki, C. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2112.10467 · Cited by 7
“Iterative refinement methods can also be derived naturally from the Power Method (Wang et al., 2021b; Ndaoud et al., 2019) or alternative optimization methods (Chi et al., 2019a).”
MethodPhase Retrieval and Matrix Sensing via Benign and Overparametrized Nonconvex Optimization
McRae, A. D. (2026) · IEEE Transactions on Information Theory · doi:10.1109/tit.2026.3684748 · Cited by 6
“See those papers and the older but more comprehensive survey [39]for further discussion and references.”
The Geometry of Equality-constrained Global Consensus Problems
Li, Q., Zhu, Z., Tang, G., & Wakin, M. B. (2019) · IEEE International Conference on Acoustics Speech and Signal Processing · doi:10.1109/icassp.2019.8682568 · Cited by 8
Luo, Y., Li, X., & Zhang, A. R. (2023) · Mathematics of Operations Research · doi:10.1287/moor.2023.1377 · Cited by 6
Stochastic nested primal-dual method for nonconvex constrained composition optimization
Jin, L., & Wang, X. (2024) · Mathematics of Computation · doi:10.1090/mcom/3965 · Cited by 6
“With slight modifications on objective function, [8] and [21] consider (6.4) with different S .”
BackgroundInfluentialShi, Q., & Han, J. (2020) · Digital Signal Processing · doi:10.1016/j.dsp.2020.102947 · Cited by 6
Reconstruction of low-rank aggregation kernels in univariate population balance equations
Ahrens, R., & Borne, S. L. (2021) · Advances in Computational Mathematics · doi:10.1007/s10444-021-09871-w · Cited by 6
Low-Rank Online Dynamic Assortment with Dual Contextual Information
Lee, S. J., Sun, W. W., & Liu, Y. (2025) · Journal of the American Statistical Association · doi:10.1080/01621459.2025.2597043 · Cited by 8
Ma, Z., Bi, Y., Lavaei, J., & Sojoudi, S. (2022) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v36i7.20734 · Cited by 6
Zhang, P., Luo, X., Ma, Y., Wang, C., Wang, W., & Xu, Q. (2022) · Remote Sensing · doi:10.3390/rs14030573 · Cited by 6
Luo, Y., Li, X., & Zhang, A. R. (2024) · INFORMS Journal on Optimization · doi:10.1287/ijoo.2022.0030 · Cited by 6
He, H., & Zhang, Z. (2024) · Journal of Scientific Computing · doi:10.1007/s10915-024-02715-x · Cited by 6
“, see some surveys [25, 29, 31, 34, 69, 78] and the most recent monograph [33] on nonconvex topics.”
Learning Latent Features With Pairwise Penalties in Low-Rank Matrix Completion
Ji, K., Tan, J. R., Xu, J., & Chi, Y. (2020) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2020.3008050 · Cited by 6
“LOW-RANK matrix completion [1], [2] has been widely used in many real-world data applications, e.”
BackgroundMethodSelf-citationThe nonsmooth landscape of blind deconvolutionPreprint
Díaz, M. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1911.08526 · Cited by 6
“This thread of ideas has proven very successful, and we refer the reader to [16] for a survey.”
BackgroundVariational Optimization on Lie Groups, with Examples of Leading (Generalized) Eigenvalue ProblemsPreprint
Tao, M., & Ohsawa, T. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2001.10006 · Cited by 6
“is not restricted to convex optimization. In fact, the proposed methods will be demonstrated on an example of (leading) (Generalized) EigenValues (GEV) problems, which is known to be nonconvex (e.g., Chi et al. (2019) and its references therein). GEV is a classical linear algebra problem behind tasks including Linear…”
MethodInfluentialDistributed Stochastic Non-Convex Optimization: Momentum-Based Variance ReductionPreprint
Khanduri, P., Sharma, P., Kafle, S., Bulusu, S., Rajawat, K., & Varshney, P. K. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2005.00224 · Cited by 6
“vex stochastic optimization problems of the form given in (1) cover a myriad of machine learning applications [2]. Such problems often arise in training of deep neural networks [3], matrix completion [4], principal component analysis [5], [6], tensor decomposition [7], inference in graphical models [8] and maximum lik…”
BackgroundHow Many Samples is a Good Initial Point Worth in Low-rank Matrix Recovery?Preprint
Zhang, G., & Zhang, R. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2006.06915 · Cited by 6
“This notion of a global guarantee—one that is valid starting from any initial point—is considerably stronger than what is needed for empirical success to be observed [8].”
BackgroundSharp Global Guarantees for Nonconvex Low-Rank Matrix Recovery in the Overparameterized Regime.Preprint
Zhang, R. Y. (2021) · arXiv (Cornell University) · Cited by 6
Subquadratic Overparameterization for Shallow Neural NetworksPreprint
Song, C., Ramezani-Kebrya, A., Pethick, T., Eftekhari, A., & Cevher, V. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2111.01875 · Cited by 17
“The idea of initializing a nonconvex problem close to a global minimum has a long history in nonconvex optimization, particularly in matrix factorization; see [6] and references therein.”
BackgroundEscaping Saddle Points in Ill-Conditioned Matrix Completion with a Scalable Second Order MethodPreprint
Kümmerle, C., & Verdun, C. M. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2009.02905 · Cited by 6
“To overcome these drawbacks, a variety of alternative approaches have been proposed and studied, many of which optimize an empirical loss defined for a matrix factorization model, or which optimize the empirical loss using Riemannian manifold structures, see (Chi et al., 2019) for a recent survey.”
BackgroundMethodInfluentialLearning Transition Operators From Sparse Space-Time Samples
Kümmerle, C., Maggioni, M., & Tang, S. (2024) · IEEE Transactions on Information Theory · doi:10.1109/tit.2024.3413534 · Cited by 8
Kaushik, P., Vaidya, A., Chaudhari, S., & Yuille, A. (2025) · IEEE/CVF Conference on Computer Vision and Pattern Recognition Workshops (CVPRW) · doi:10.1109/cvprw67362.2025.00070 · Cited by 10
“This is a well-established line of research starting from Burer-Monteiro factorization [7], with a recent resurgence by Hu et al. [18] (LoRA), who used it as a technique to finetune LLMs; and other re-lated variants [9, 27, 34].”
In-memory analog computing for non-negative matrix factorization
Wang, S., Luo, Y., Zuo, P., Li, Y. B., Pan, L., Ielmini, D., & Sun, Z. (2026) · Nature Communications · doi:10.1038/s41467-026-68609-8 · Cited by 7
“Decomposition, however, represents a higher-order inverse problem, in which a knownmatrix R isfactorizedintotwounknownmatrices, U and V (e.g., R = U (cid:1) V T ), making it fundamentally a non-convex optimization problem 34 .”
InfluentialMa, Z., Bi, Y., Lavaei, J., & Sojoudi, S. (2023) · INFORMS Journal on Optimization · doi:10.1287/ijoo.2023.0090 · Cited by 5
“Many notable problems such as matrix completion [1, 2], phase synchronization/retrieval [3–5], robust PCA [6], collaborative learning and multi-class clustering [7, 8], and and several others [9, 10] can be viewed as special cases of the problem (1).”
BackgroundMultilinear Kernel Regression and Imputation via Manifold Learning
Nguyen, D. T., & Slavakis, K. (2024) · IEEE Open Journal of Signal Processing · doi:10.1109/ojsp.2024.3444707 · Cited by 9
“…from the data themselves, and incorporating that information into MultiL-KRIM’s inverse problem, differs from “blind” decomposition methods, e.g., [9], [10], [11], [12], [53], [54], [55], [56] (see also Section I), where no geometric information from the data is infused into their data models.”
MethodSpectral Neural Networks: Approximation Theory and Optimization Landscape
Cheng-hui, L., Sonthalia, R., & Trillos, N. G. (2026) · Journal of Machine Learning · doi:10.4208/jml.240322 · Cited by 5
A Unified Framework for Estimation of High-Dimensional Conditional Factor Models
Chen, Q. (2025) · Journal of the American Statistical Association · doi:10.1080/01621459.2025.2591269 · Cited by 5
“One potential approach to address the second challenge is alternating least squares; however, it may suffer from non-convergence issues due to the nonconvexity of (12) (Golub and Van Loan 2013; Chi, Lu, and Chen 2019).”
Analysis of Asymptotic Escape of Strict Saddle Sets in Manifold Optimization
Hou, T. Y., Li, Z., & Zhang, Z. (2020) · SIAM Journal on Mathematics of Data Science · doi:10.1137/19m129437x · Cited by 7
Efficient Sparse Coding Using Hierarchical Riemannian Pursuit
Xue, Y., Lau, V. K. N., & Cai, S. (2021) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2021.3093769 · Cited by 6
Minimax optimal clustering of bipartite graphs with a generalized power method
Braun, G., & Tyagi, H. (2023) · Information and Inference A Journal of the IMA · doi:10.1093/imaiai/iaad006 · Cited by 5
“, group synchronization (Boumal, 2016), joint alignment from pairwise difference (Chen and Candès, 2018), graph matching (Onaran and Villar, 2017), low rank matrix recovery (Chi et al., 2019) and SBM (Wang et al.”
BackgroundGradient flow on extensive-rank positive semi-definite matrix denoising
Bodin, A., & Macris, N. (2023) · IEEE Information Theory Workshop (ITW) · doi:10.1109/itw55543.2023.10161669 · Cited by 13
Asymptotic dynamics of alternating minimization for bilinear regression
Okajima, K., & Takahashi, T. (2025) · Journal of Statistical Mechanics Theory and Experiment · doi:10.1088/1742-5468/add1ce · Cited by 5
“Moreover, while the initialization setup given in (6) is purely conventional, we stress that the analysis in our work is extendable to more realistic spectral initializations [14, 58, 59].”
A super-resolution framework for tensor decomposition
Li, Q., Prater, A., Shen, L., & Tang, G. (2022) · Information and Inference A Journal of the IMA · doi:10.1093/imaiai/iaac002 · Cited by 5
Rank-one matrix estimation: analytic time evolution of gradient descent dynamicsPreprint
Bodin, A., & Macris, N. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2105.12257 · Cited by 5
Seeded graph matching for the correlated Gaussian Wigner model via the projected power methodPreprint
Araya, E., Braun, G., & Tyagi, H. (2022) · HAL · doi:10.48550/arxiv.2204.04099 · Cited by 5
“…for various tasks including clustering SBM (Wang et al., 2021), group synchronization (Boumal, 2016; Gao and Zhang, 2022b), joint alignment from pairwise difference (Chen and Cand`es, 2016), low rank-matrix recovery (Chi et al., 2019) and the generalized orthogonal Procrustes problem (Ling, 2021).”
MethodStatistical Inference for Linear Functions of Eigenvectors with Small EigengapsPreprint
Agterberg, J. (2023) · arXiv (Cornell University) · doi:10.48550/arxiv.2308.02480 · Cited by 5
Learning single index model with gradient descent: spectral initialization and precise asymptoticsPreprint
Chen, Y., & Shen, Y. (2025) · arXiv (Cornell University) · doi:10.48550/arxiv.2509.23527 · Cited by 5
Self-citationGiampouras, P. V., Cai, H., & Vidal, R. (2024) · arXiv (Cornell University) · doi:10.48550/arxiv.2410.16826 · Cited by 5
“To address this, matrix factorization-based approaches have been proposed, Chi et al. (2019); Park et al. (2016), which, given r ≥ rank( X ⋆ ), use matrices L ∈ R m r and R ∈ R n r such that X = LR ⊤ .”
BackgroundMethodInfluentialNonsmooth rank-one matrix factorization landscape
Josz, C., & Lai, L. (2021) · Optimization Letters · doi:10.1007/s11590-021-01819-9 · Cited by 9
“The number of survey papers [28, 10, 12, 11, 20, 26] on the subject in the last three years is a testament to the amount of research it has spawned.”
BackgroundJoint contrastive learning of structural and semantic for graph collaborative filtering
Dai, J., Li, Q., Nong, T., Bi, Q., & Chu, H. (2024) · Neurocomputing · doi:10.1016/j.neucom.2024.127547 · Cited by 4
Beyond vintage rotation: bias-free sparse representation learning with oracle inference
Cui, C., Chen, Y., Ouyang, J., & Xu, G. (2026) · Journal of the Royal Statistical Society Series B (Statistical Methodology) · doi:10.1093/jrsssb/qkag133 · Cited by 5
“Similar loss-based formulations are also common in the low-rank factorisation literature (Srebro et al. 2004, Chen & Wainwright 2015, Chi et al. 2019).”
Self-citationFast automatic step size selection for zeroth-order nonconvex stochastic optimization
Yang, Z. (2021) · Expert Systems with Applications · doi:10.1016/j.eswa.2021.114749 · Cited by 4
Smoothed amplitude flow-based phase retrieval algorithm
Xiao, Z., Wang, Y., & Gui, G. (2021) · Journal of the Franklin Institute · doi:10.1016/j.jfranklin.2021.06.021 · Cited by 4
Correlating Time Series With Interpretable Convolutional Kernels
Chen, X., Cai, H., Liu, F., & Zhao, J. (2025) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2025.3550877 · Cited by 7
“Each subproblem can be resolved by the conjugate gradient method effi-ciently [34].”
Beyond Procrustes: Balancing-free Gradient Descent for Asymmetric Low-Rank Matrix Sensing
Ma, C., Li, Y., & Chi, Y. (2019) · Asilomar Conference on Signals, Systems and Computers (ACSSC) · doi:10.1109/ieeeconf44664.2019.9048714 · Cited by 4
“The readers are referred to the recent overview [27] for additional references.”
BackgroundSelf-citationPreference-Tree-Based Real-Time Recommendation System
Kang, S., & Chung, K. (2022) · Entropy · doi:10.3390/e24040503 · Cited by 5
“[10] trained a regression model with a recommendation system based on matrix factorization (MF) to predict unknown preferences between users and content.”
MethodLow-rank matrix factorization with nonconvex regularization and bilinear decomposition
Wang, S., Xia, K., Li, W., Yin, Z., He, Z., Zhang, J., & Aslam, N. (2022) · Signal Processing · doi:10.1016/j.sigpro.2022.108694 · Cited by 6
Certifying the Absence of Spurious Local Minima at Infinity
Josz, C., & Li, X. (2023) · SIAM Journal on Optimization · doi:10.1137/22m1479531 · Cited by 4
“3 Matrix sensing Matrix sensing is a widely used model in computer vision and statistics; see for instance [10, 39].”
MethodA new complexity metric for nonconvex rank-one generalized matrix completion
Zhang, H., Yalçın, B., Lavaei, J., & Sojoudi, S. (2023) · Mathematical Programming · doi:10.1007/s10107-023-02008-5 · Cited by 7
“1) has attracted a lot of attention in recent years; see the review papers [18,22].”
Low-Rank Univariate Sum of Squares Has No Spurious Local Minima
Legat, B., Yuan, C., & Parrilo, P. A. (2023) · SIAM Journal on Optimization · doi:10.1137/22m1516208 · Cited by 4
“See [11] for a survey of these problems.”
BackgroundLow-rank Matrix Sensing With Dithered One-Bit Quantization
Yeganegi, F., Eamaz, A., & Soltanalian, M. (2024) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit57864.2024.10619615 · Cited by 4
“In low-rank matrix sensing, the linear operator A ( X ) is obtained as [7], where A j ∈ R n 1 × n 2 is the j -th sensing matrix.”
BackgroundMethodQuick Unsupervised Hyperspectral Dimensionality Reduction for Earth Observation: A Comparison
Lupu, D., Garrett, J. L., Johansen, T. A., Orlandić, M., & Necoara, I. (2025) · IEEE Transactions on Computational Imaging · doi:10.1109/tci.2025.3555137 · Cited by 4
“There are many iterative algorithms in the literature to solve this nonconvex optimization problem, see e.g., [22], [23], [34].”
No Spurious Solutions in Non-convex Matrix Sensing: Structure Compensates for Isometry
Molybog, I., Sojoudi, S., & Lavaei, J. (2021) · Proceedings of the ... American Control Conference/Proceedings of the American Control Conference · doi:10.23919/acc50511.2021.9483256 · Cited by 4
“Particularly, significant progress has been made towards understanding different variants of low-rank matrix recovery, although explanations of the simplest version called matrix sensing are still under active development [20], [21], [22], [18], [23], [24].”
BackgroundDiminishing Regret for Online Nonconvex Optimization
Park, S., Mulvaney-Kemp, J., Jin, M., & Lavaei, J. (2021) · Proceedings of the ... American Control Conference/Proceedings of the American Control Conference · doi:10.23919/acc50511.2021.9482986 · Cited by 4
“Existing works often assume that there exists a reasonably large region of attraction around the global optimum in order to guarantee the successful convergence of the iterative methods like gradient descent [36].”
BackgroundInfluentialNoisy Gradient Descent Converges to Flat Minima for Nonconvex Matrix FactorizationPreprint
Liu, T., Li, Y., Wei, S., Zhou, E., & Zhao, T. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2102.12430 · Cited by 4
“The optimization landscape of (2) has been well studied in the previous literature (Ge et al., 2016, 2017; Chi et al., 2019; Li et al., 2019a).”
BackgroundMethodInfluentialZhang, Q., He, L., Wang, Y., Deng, L.-J., & Liu, J. (2023) · SSRN Electronic Journal · doi:10.2139/ssrn.4619184 · Cited by 4
A theory of optimal convex regularization for low-dimensional recovery
Traonmilin, Y., Gribonval, R., & Vaiter, S. (2024) · Information and Inference A Journal of the IMA · doi:10.1093/imaiai/iaae013 · Cited by 3
Qiu, D., Ng, M. K., & Zhang, X. (2023) · Journal of Computational Mathematics · doi:10.4208/jcm.2309-m2023-0041 · Cited by 3
A Unified Diffusion Framework for Traffic Imputation and Prediction With Physical Priors
Liu, P., Zhu, Y., Yang, Y., Wang, C., & Jie, J. (2025) · IEEE Transactions on Mobile Computing · doi:10.1109/tmc.2025.3591423 · Cited by 3
“Although effective in capturing latent structures [33], [34], [35] these methods often overlook the underlying topological relationships within traffic networks and face scalability issues due to data sparsity and the high computational cost of matrix decomposition.”
On Variational Inference in Biclustering Models
Fang, G., & Li, P. (2021) · International Conference on Machine Learning · Cited by 3
The Local Landscape of Phase Retrieval Under Limited Samples
Liu, K., Wang, Z., & Wu, L. (2024) · IEEE Transactions on Information Theory · doi:10.1109/tit.2024.3481269 · Cited by 3
Spectrum and pseudspectrum of D -stable matrices of economy models
Rehman, M.-U., Alshabhi, S. H., Mustafa, A. O., Mohammed, M. M., Aljohani, S., Mahgoub, H. S., Bashir, R. A. A., & Bakery, A. A. (2024) · Journal of Mathematics and Computer Science · doi:10.22436/jmcs.038.03.02 · Cited by 3
Separable Joint Blind Deconvolution and Demixing
Weitzner, D., & Giryes, R. (2021) · IEEE Journal of Selected Topics in Signal Processing · doi:10.1109/jstsp.2021.3057238 · Cited by 3
“A thorough review of nonconvex algorithms in a broader context of general matrix completion problems can be found in [25].”
BackgroundSketched Learning for Image Denoising
Shi, H., Traonmilin, Y., & Aujol, J. (2021) · Lecture notes in computer science · doi:10.1007/978-3-030-75549-2_23 · Cited by 6
Escaping Saddle Points for Successive Convex Approximation
Bedi, A. S., Rajawat, K., Aggarwal, V., & Koppel, A. (2021) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2021.3138242 · Cited by 7
Kernel-Based Multilayer Graph Signal Recovery via Median Truncation of Gradient Descent
Khonglah, J. R., & Mukherjee, A. (2023) · IEEE Transactions on Signal and Information Processing over Networks · doi:10.1109/tsipn.2023.3268128 · Cited by 3
“Generally, both the proofs follow the same regime and require that the median truncated gradients meet the regularity condition (RC) [35] using the concentration properties of the sample median.”
MethodGradient-Based Spectral Embeddings of Random Dot Product Graphs
Fiori, M., Marenco, B., Larroca, F., Bermolen, P., & Mateos, G. (2023) · IEEE Transactions on Signal and Information Processing over Networks · doi:10.1109/tsipn.2023.3343607 · Cited by 3
“There have been several noteworthy advances in the study of GD’s convergence (including rates) for this non-convex setting, as well as accelerated variants [10], [11], [26]–[29].”
BackgroundInfluentialStrong Convexity of Affine Phase Retrieval
Huang, M., & Xu, Z. (2024) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2024.3371170 · Cited by 3
“We refer the reader to survey papers [12], [24] for accounts of recent developments in the theory, algorithms and applications of phase retrieval.”
MethodMulti-Linear Kernel Regression and Imputation VIA Manifold Learning: the Dynamic MRI Case
Nguyen, D. T., & Slavakis, K. (2024) · IEEE International Conference on Acoustics Speech and Signal Processing · doi:10.1109/icassp48485.2024.10446236 · Cited by 4
“Numerous data-modeling approaches have been proposed for the imputation-by-regression problem: compressed sensing [5], low-rank modeling [6–9], and learning strategies based on dictionaries [5, 10], manifolds [11–17], kernels [18–20], and tensors [19, 21– 24].”
BackgroundMethodSimpler Gradient Methods for Blind Super-Resolution With Lower Iteration Complexity
Li, J., Cui, W., & Zhang, X. (2024) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2024.3470071 · Cited by 3
“In this paper, we focus on the fast nonconvex gradient methods based on low-rank factorization, which have received great interest in recent years [31].”
MethodSupervised factor modeling for high-dimensional linear time series
Huang, F., Lu, K., Zheng, Y., & Li, G. (2025) · Journal of Econometrics · doi:10.1016/j.jeconom.2025.105995 · Cited by 3
Low solution rank of the matrix LASSO under RIP with consequences for rank-constrained algorithms
McRae, A. D. (2025) · Mathematical Programming · doi:10.1007/s10107-025-02236-x · Cited by 3
“We do not attempt to cover the full body of such results (as they have a fundamentally different character than ours), but see the survey [27] as well as more recent papers such as [19, 28, 21, 29] for further references.”
Advancing Decoding Strategies: Enhancements in Locally Typical Sampling for LLMs
Sen, J., Sengupta, S., & Dasgupta, S. (2026) · Intelligent systems reference library · doi:10.1007/978-3-032-13497-4_17 · Cited by 4
“Exploring model pruning techniques [84-85], approximate nearest neighbor search for semantic alignment [86-88], or low-rank matrix factorization meth-ods [89-90] could help reduce computational costs.”
Non-convex exact community recovery in stochastic block model
Wang, P., Zhou, Z., & So, A. M. (2021) · Mathematical Programming · doi:10.1007/s10107-021-01715-1 · Cited by 3
“These include deep neural networks [32,33], low-rank matrix recovery [12,23], phase retrieval [27,35], source localization [24,31], and synchronization [25,39].”
BackgroundLocal and Global Convergence of General Burer-Monteiro Tensor Optimizations
Li, S., & Li, Q. (2022) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v36i9.21267 · Cited by 3
Market Equilibrium Models in Large-Scale Internet Markets
Kroer, C., & Stier‐Moses, N. E. (2021) · Springer series in supply chain management · doi:10.1007/978-3-030-81945-3_7 · Cited by 6
Algorithmic Advances for the Adjacency Spectral Embedding
Fiori, M., Marenco, B., Larroca, F., Bermolen, P., & Mateos, G. (2022) · European Signal Processing Conference (EUSIPCO) · doi:10.23919/eusipco55093.2022.9909610 · Cited by 3
“See [11] and references therein for a similar version of this proposition.”
BackgroundYalçın, B., Zhang, H., Lavaei, J., & Sojoudi, S. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2110.10279 · Cited by 3
“We refer the reader to Chi et al. (2019) for a review of the low-rank matrix optimization problem.”
The radius of statistical efficiency
Cutler, J., Díaz, M., & Drusvyatskiy, D. (2026) · Foundations of Computational Mathematics · doi:10.1007/s10208-026-09743-z · Cited by 2
“See, for example, [14, 17, 24, 74] for an overview.”
Solving Quadratic Systems With Full-Rank Matrices Using Sparse or Generative Priors
Chen, J., Ng, M. K., & Liu, Z. (2025) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2024.3522179 · Cited by 2
Low-Rank Covariance Matrix Recovery From Rank-One Measurements: An Analytical Solution
Wang, P., Fang, J., Ma, B., Wang, B., & Leus, G. J. T. (2025) · IEEE Signal Processing Letters · doi:10.1109/lsp.2025.3584252 · Cited by 2
“Previousworksonlow-rankPSDmatrixrecoverycanbe broadlycategorizedintotwogroups[8]:convexrelaxation methodsandnon-convexoptimizationmethods.”
InfluentialNear-Quadratic Convergence of the Gauss–Newton Method for Complex Phase Retrieval
Huang, M. (2025) · IEEE Transactions on Information Theory · doi:10.1109/tit.2025.3633715 · Cited by 2
“Additional non-convex phase retrieval algorithms with provable guarantees are discussed in [5], [6], [7], [9], [17], [20], [25], [34], [48], [50], [52], [55], [58], [59].”
Near-Optimal Reconfigurable Intelligent Surface Configuration: Blind Beamforming With Sensing
Dinh‐Van, S., Tran, N. P., & Higgins, M. D. (2026) · IEEE Transactions on Wireless Communications · doi:10.1109/twc.2026.3726665 · Cited by 2
“Before presenting the main result, we first state and explain the assumptions required for the success of the algorithm.”
Smooth Optimization Using Global and Local Low-Rank Regularizers
Lobos, R. A., Cavazos, J. S., Nadakuditi, R. R., & Fessler, J. A. (2026) · SIAM Journal on Imaging Sciences · doi:10.1137/25m175891x · Cited by 2
“…function that measures data consistency; ∥·∥ ∗ denotes the nuclear norm; and β is a regularization parameter. include Example applications robust PCA [5], matrix completion [11, 18], parallel MRI [29, 73, 74], low-rank + sparse models for dynamic MRI [53], among many others [10,12,23,28,66,68,71].”
The Geometric Effects of Distributing Constrained Nonconvex Optimization Problems
Li, Q., Yang, X., Zhu, Z., Tang, G., & Wakin, M. B. (2019) · IEEE International Workshop on Computational Advances in Multi-Sensor Adaptive Processing · doi:10.1109/camsap45676.2019.9022447 · Cited by 3
“A variety of nonconvex machine learning problems have recently been shown to have benign geometric landscapes, in which there are no spurious local minima and all saddle points are strict saddles at which the Hessian has at least one negative eigenvalue [1]–[11].”
BackgroundLow-Rank Matrix Estimation from Rank-One Projections by Unlifted Convex Optimization
Bahmani, S., & Lee, K. (2021) · SIAM Journal on Matrix Analysis and Applications · doi:10.1137/20m1330099 · Cited by 2
No Statistical-Computational Gap in Spiked Matrix Models with Generative Network Priors
Cocola, J., Hand, P., & Voroninski, V. (2021) · Entropy · doi:10.3390/e23010115 · Cited by 2
“The above bounds imply in particular that for all x ∈ B(x?, γ‖x?‖(2)) the gradient of f̌ satisfies the regularity condition (see [63]):”
BackgroundHuang, H., & Zoubir, A. M. (2021) · IEEE International Conference on Acoustics Speech and Signal Processing · doi:10.1109/icassp39728.2021.9413843 · Cited by 2
“Based on this fact, we propose the following LRSD problem min Z,V ‖Y − Z−V‖2F + λ1‖V‖2,0 + λ2Rank(Z), (5) where ‖·‖F and ‖·‖2,0 denote the Frobenius norm and theL2,0 mixed norm of a matrix, respectively, Rank(·) is the rank of a matrix, and λ1 and λ2 are tuning parameters for balancing the three terms in the objective…”
MethodInfluentialLi, Z., Li, H., Li, K., Wu, F., Chen, L. Y., & Li, K. (2021) · ACM/IMS Transactions on Data Science · doi:10.1145/3497749 · Cited by 3
“Due to the entanglement of the parameters, the optimization objective (2) is nonconvex, and alternative minimization is adopted [8] [17] [54] [47], which can”
BackgroundMethodRobust estimation of highly corrupted low‐rank matrix via alternating direction method of multiplier
Yimamu, T., & Eisaka, T. (2022) · IET Signal Processing · doi:10.1049/sil2.12168 · Cited by 2
A Newton-CG based barrier-augmented Lagrangian method for general nonconvex conic optimization
He, C., Huang, H., & Lu, Z. (2024) · Computational Optimization and Applications · doi:10.1007/s10589-024-00603-6 · Cited by 2
“In this subsection we consider a low-rank matrix recovery problem (e.g., see [9, 29, 59]) where A : R n × n → R m is a linear operator and · F is the Frobenius norm.”
BackgroundLow-Rank Tensors for Multi-Dimensional Markov Models
Navarro, M., Rozada, S., Marques, A. G., & Segarra, S. (2025) · IEEE International Conference on Acoustics Speech and Signal Processing · doi:10.1109/icassp49660.2025.10889291 · Cited by 2
“In this work, we rely on two assumptions: Markovianity, where future behavior relies only on the current state of the system, and low-rankness [6], where the system dynamics can be represented by a small set of hidden variables [7].”
Metadata
- Authors
- Chi, Y., Lu, Y. M., & Chen, Y.
- Affiliations
- Carnegie Mellon University (US)
- Harvard University (US)
- Princeton University (US)
- Venue
- IEEE Transactions on Signal Processing
- Published
- 2019-10-15
- Volume
- 67
- Issue
- 20
- Pages
- 5239-5269
- ISSN
- 1053-587X (ISSN-L)
- 1941-0476
- OpenAlex
- W2969215180
- Cited by
- 360
- References
- 279
- Citations by year
- 2026: 20 · 2025: 33 · 2024: 36 · 2023: 50 · 2022: 40 · 2021: 80 · 2020: 65 · 2019: 32
- FWCI
- 37.03
- Type
- journal article
- Language
- en
- Open access
- hybrid
- doi.org
- Licence
- Locations
- IEEE Transactions on Signal Processing (publishedVersion, cc-by)
- arXiv (Cornell University) (submittedVersion)
- arXiv (Cornell University)
- Funders
- Office of Naval Research (N00014-18-1-2142, N00014-19-1-2404)
- Army Research Office (W911NF-18-1-0303)
- Air Force Office of Scientific Research (FA9550-15-1-0205)
- National Science Foundation (CCF-1901199, CCF-1806154, ECCS-1818571, CCF-1718698, CCF-1910410, CCF-1907661, IIS-1900140)
- Harvard Dean's Competitive Fund for Promising Research
- AFOSR (YIP FA9550-19-1-0030)
- ARO (W911NF-18-1-0303)
- ONR (N00014-19-1-2120)
- Topics
- Physical Sciences › Computer Science › Signal Processing › Sparse and Compressive Sensing Techniques
- Physical Sciences › Computer Science › Artificial Intelligence › Stochastic Gradient Optimization Techniques
- Physical Sciences › Mathematics › Numerical Analysis › Advanced Optimization Algorithms Research
- Keywords
- non-convex optimization, low-rank factorization, statistical models, spurious local minima, two-stage algorithm, matrix sensing, phase retrieval, matrix completion, blind deconvolution, robust principal component analysis, performance guarantees
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.