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 101–200 of 390
Estimating Higher-Order Mixed Memberships via the l2,∞ Tensor Perturbation Bound
Agterberg, J., & Zhang, A. R. (2024) · Journal of the American Statistical Association · doi:10.1080/01621459.2024.2404265 · Cited by 19
“Tensor data analysis techniques are closely tied to spectral methods, which have myriad applications in high-dimensional statistics (Chen et al. 2021), including in principal component analysis, spectral clustering, and as initializations for nonconvex algorithms (Chi et al. 2019).”
Provable Low Rank Phase Retrieval
Nayer, S. S., Narayanamurthy, P. K., & Vaswani, N. (2020) · IEEE Transactions on Information Theory · doi:10.1109/tit.2020.2984478 · Cited by 19
“It is well known that, when studying iterative (non-convex) solutions to problems, the global measurements’ setting is easier to study, and one can obtain better sample complexity guarantees for it, as compared to its non-global counterpart [27].”
BackgroundXiong, H., Chi, Y., Hu, B., & Zhang, W. (2019) · Automatica · doi:10.1016/j.automatica.2019.108715 · Cited by 19
“This nonconvex loss function was also discussed in [19, 18].”
BackgroundSelf-citationFast and provable tensor robust principal component analysis via scaled gradient descent
Dong, H., Tong, T., Ma, C., & Chi, Y. (2023) · Information and Inference A Journal of the IMA · doi:10.1093/imaiai/iaad019 · Cited by 18
Self-citationPhase retrieval via smoothed amplitude flow
Luo, Q., Wang, H., & Lin, S. (2020) · Signal Processing · doi:10.1016/j.sigpro.2020.107719 · Cited by 18
Bayesian Uncertainty Quantification for Low-Rank Matrix Completion
Yuchi, H. S., Mak, S., & Xie, Y. (2022) · Bayesian Analysis · doi:10.1214/22-ba1317 · Cited by 25
“There is now a rich body of work on matrix completion; recent overviews include Davenport and Romberg (2016) and Chi et al. (2019).”
BackgroundFattahi, S., & Sojoudi, S. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1812.11466 · Cited by 21
“…([13, 14, 15, 29]), phase retrieval ([30]), and dictionary recovery ([31]) have benign global landscape , i.e., every local solution is also global and every saddle point has a direction with a strictly negative curvature (see [32] for a comprehensive survey on the related problems).”
BackgroundRobust Recovery via Implicit Bias of Discrepant Learning Rates for Double Over-parameterizationPreprint
You, C., Zhu, Z., Qu, Q., & Ma, Y. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2006.08857 · Cited by 44
“The computational challenge has been addressed by recent development of matrix factorization (MF) methods [18, 22].”
Implicit Regularization in Tensor FactorizationPreprint
Razin, N., Maman, A., & Cohen, N. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2102.09972 · Cited by 21
“The literature on matrix factorization for rank minimization is far too broad to cover here — we refer to Chi et al. (2019) for a recent review.”
BackgroundHou, T. Y., Li, Z., & Zhang, Z. (2020) · CaltechAUTHORS (California Institute of Technology) · doi:10.48550/arxiv.2012.15467 · Cited by 18
“We refer the reader to the excellent survey papers [17, 26, 28, 40] on low-rank matrix recovery.”
BackgroundBayesian Hyperspectral Image Super-Resolution in the Presence of Spectral Variability
Ye, F., Wu, Z., Xu, Y., Liu, H., & Wei, Z. (2022) · IEEE Transactions on Geoscience and Remote Sensing · doi:10.1109/tgrs.2022.3228313 · Cited by 18
“Motivated by the advances in modern optimization theory [5], [6], model optimization has become one of the most commonly applied HSI–MSI fusion techniques.”
MethodHaddad, A., & Najafizadeh, L. (2023) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2023.3238281 · Cited by 17
“Matrix factorization is an algebraic analysis approach that involves decomposing a matrix into the product of two, or more, matrices, with the aim of representing or approximating the contents of the original matrix in terms of latent components that possess certain features [8], [9].”
BackgroundMaRLI: Attack on the Discrete-Phase WISL Minimization Problem
Eamaz, A., Yeganegi, F., & Soltanalian, M. (2023) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2023.3339398 · Cited by 17
“It is noteworthy that the convergence analysis of cyclic algorithms continues to be an actively studied realm within the literature, and under reasonably moderate conditions, the propensity for convergence towards a stationary point can be demonstrated [48].”
BackgroundProvable Near-Optimal Low-Multilinear-Rank Tensor RecoveryPreprint
Cai, J., Miao, L., Wang, Y., & Xian, Y. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2007.08904 · Cited by 17
“Surprisingly, it has been shown that these non-convex low-rank matrix recovery approaches are guaranteed to converge to the global minimum [3, 6, 9, 21, 39, 42, 43], and there is no spurious local minima of many non-convex functions for low-rank matrix recovery [14, 28, 38, 46].”
BackgroundSurrogate-assisted global transfer optimization based on adaptive sampling strategy
Chen, W., Dong, H., Wang, P., & Wang, X. (2023) · Advanced Engineering Informatics · doi:10.1016/j.aei.2023.101914 · Cited by 16
Wang, Z.-Y., So, H. C., & Liu, Z. (2022) · Signal Processing · doi:10.1016/j.sigpro.2022.108580 · Cited by 16
Approximate message passing from random initialization with applications to Z 2 synchronization
Li, G., Fan, W., & Wei, Y. (2023) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.2302930120 · Cited by 16
“For this reason, prior AMP theory falls short of describing how AMP behaves after a growing number of iterations, which stands in contrast to other optimization-based procedures that often come with non-asymptotic analysis accommodating a large number of iterations (Chen and Wainwright, 2015; Chi et al., 2019; Keshava…”
BackgroundResultEamaz, A., Yeganegi, F., Needell, D. M., & Soltanalian, M. (2024) · IEEE Transactions on Information Theory · doi:10.1109/tit.2024.3422918 · Cited by 16
“The original signal representing the signal to be recovered is shown by yellow. storage requirements, and lower per-iteration computational cost [48].”
BackgroundSoltanolkotabi, M., Stöger, D., & Xie, C. (2025) · IEEE Transactions on Information Theory · doi:10.1109/tit.2025.3530335 · Cited by 25
Luo, Y., & Zhang, A. R. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2104.12031 · Cited by 16
“The readers are referred to a recent survey in Chi et al. (2019).”
BackgroundKamali, P. J., & Urbani, P. (2023) · arXiv (Cornell University) · doi:10.48550/arxiv.2309.04788 · Cited by 16
“04788v1 [ c s .”
Downlink CSI Recovery in Massive MIMO Systems by Proactive Sensing
Li, L., Zhu, M., Xia, S., & Chang, T. (2022) · IEEE Wireless Communications Letters · doi:10.1109/lwc.2022.3228244 · Cited by 15
“Note that although f1(g) is nonconvex, the gradient descent method has been verified to achieve good performance for the conventional PR problem (without the regularizer) when the initial point is set properly [13].”
MethodDynamical reversibility and a new theory of causal emergence based on SVD
Zhang, J., Tao, R., Leong, K. H., Yang, M., & Yuan, B. (2025) · npj Complexity · doi:10.1038/s44260-025-00028-0 · Cited by 21
Benign Nonconvex Landscapes in Optimal and Robust Control, Part I: Global Optimality
Zheng, Y., Pai, C.-F. R., & Tang, Y. (2026) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2026.3675544 · Cited by 15
“…optimization results have recently emerged in machine learning literature, where the underlying geometrical properties (such as rotational [53] and discrete [54] symmetries) enable identifying the local curvature of stationary points and thus contribute to global optimality of…”
Compressive Learning for Patch-Based Image Denoising
Shi, H., Traonmilin, Y., & Aujol, J. (2022) · SIAM Journal on Imaging Sciences · doi:10.1137/21m1459812 · Cited by 16
Chandrasekher, K. A., Lou, M., & Pananjady, A. (2024) · Information and Inference A Journal of the IMA · doi:10.1093/imaiai/iaae025 · Cited by 20
Optimization landscape of Tucker decomposition
Frandsen, A., & Ge, R. (2020) · Mathematical Programming · doi:10.1007/s10107-020-01531-z · Cited by 22
Cost-Efficient RIS-Aided Channel Estimation via Rank-One Matrix Factorization
Zhang, W., & Tay, W. P. (2021) · IEEE Wireless Communications Letters · doi:10.1109/lwc.2021.3107547 · Cited by 15
Luo, Y., Huang, W. T., Li, X., & Zhang, A. R. (2023) · Operations Research · doi:10.1287/opre.2023.2445 · Cited by 15
Complete Dictionary Learning via $\ell^4$-Norm Maximization over the Orthogonal GroupPreprint
Zhai, Y., Yang, Z., Liao, Z., Wright, J. N., & Ma, Y. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1906.02435 · Cited by 15
Towards a Better Global Loss Landscape of GANsPreprint
Sun, R., Fang, T., & Schwing, A. G. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2011.04926 · Cited by 25
“[91], Sun [81]), and has received great attention in matrix factorization [31, 14, 19] and supervised learning [38, 47, 2, 92, 27].”
BackgroundManifold Gradient Descent Solves Multi-Channel Sparse Blind Deconvolution Provably and Efficiently
Shi, L., & Chi, Y. (2020) · IEEE International Conference on Acoustics Speech and Signal Processing · doi:10.1109/icassp40776.2020.9054356 · Cited by 15
“Our work belongs to the recent line of activities on designing provable nonconvex procedures for high-dimensional statistical estimation, see [12] for an overview.”
BackgroundSelf-citationZhang, L., Chao, X., Qian, Q., & Jing, F. (2022) · Technological Forecasting and Social Change · doi:10.1016/j.techfore.2022.121902 · Cited by 15
Nearly optimal bounds for the global geometric landscape of phase retrieval
Cai, J., Huang, M., Li, D., & Wang, Y. (2023) · Inverse Problems · doi:10.1088/1361-6420/acdab7 · Cited by 21
“We refer the reader to survey papers [1, 10, 21, 31] for accounts of recent developments in the theory, algorithms and applications of phase retrieval.”
MethodManifold Gradient Descent Solves Multi-Channel Sparse Blind Deconvolution Provably and Efficiently
Shi, L., & Chi, Y. (2021) · IEEE Transactions on Information Theory · doi:10.1109/tit.2021.3075148 · Cited by 17
Self-citationInformation-Guided Sampling for Low-Rank Matrix CompletionPreprint
Mak, S., Yushi, H. S., & Xie, Y. (2017) · arXiv (Cornell University) · doi:10.48550/arxiv.1706.08037 · Cited by 15
“There is now a rich body of work on matrix completion with various convex and non-convex optimization algorithms; recent overviews include Davenport & Romberg (2016) and Chi et al. (2019).”
BackgroundDistributed Low-rank Matrix Factorization With Exact Consensus
Zhu, Z., Li, Q., Yang, X., Tang, G., & Wakin, M. B. (2019) · neural information processing systems · Cited by 23
Bohannon, A., Lawhern, V. J., Waytowich, N. R., & Balan, R. V. (2020) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2020.3012946 · Cited by 13
“[29] Y. Chi, Y. M. Lu, and Y. Chen, “Nonconvex optimization meets low-rank matrix factorization: An overview,” IEEE Trans.”
BackgroundGNMR: A Provable One-Line Algorithm for Low Rank Matrix Recovery
Zilber, P., & Nadler, B. (2022) · SIAM Journal on Mathematics of Data Science · doi:10.1137/21m1433812 · Cited by 13
A Nonlinear Matrix Decomposition for Mining the Zeros of Sparse Data
Saul, L. K. (2022) · SIAM Journal on Mathematics of Data Science · doi:10.1137/21m1405769 · Cited by 24
“, bidiagonalization and column pivoting [22, 38], alternating least-squares [46], other nonconvex optimizations [19, 57], randomized methods [34, 44, 80, 116, 117]), but in this framework the choice becomes a lower-level operational decision that can be based on the specific problem instance.”
BackgroundLin, K., Lei, J., & Roeder, K. (2021) · Journal of the American Statistical Association · doi:10.1080/01621459.2021.1886106 · Cited by 19
“For example, to accommodate the constraints in Assumption 3.1, Wang, Zhang, and Gu (2017), Yu, Gupta, and Kolar (2020), and Chi, Lu, and Chen (2019) adapted the theoretical framework to study slightly different estimators based on alternating projected gradient descent.”
BackgroundInfluentialSpurious Valleys, NP-Hardness, and Tractability of Sparse Matrix Factorization with Fixed Support
Le, Q.-T., Riccietti, E., & Gribonval, R. (2023) · SIAM Journal on Matrix Analysis and Applications · doi:10.1137/22m1496657 · Cited by 17
“…many existing results of matrix decomposition problems that are proved to hold with high probability under certain random models [3, 30, 41, 15, 14, 8, 9]), our result deterministically ensures the benign landscape for each matrix A , under certain conditions on the support constraints ( I, J ) .”
BackgroundConvolutional Geometric Matrix CompletionPreprint
Yao, K.-L., Li, W.-J., Yang, J., & Lu, X. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1803.00754 · Cited by 13
Limitations of Implicit Bias in Matrix Sensing: Initialization Rank MattersPreprint
Eftekhari, A., & Zygalakis, K. C. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2008.12091 · Cited by 14
“Lastly, the simpler under-parametrized regime of m > pd is not of interest here and we refer the reader to the survey [12].”
BackgroundWang, H., Chen, J., & Wei, K. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2108.07899 · Cited by 13
Rahimi, M., Ghaderi, S., Moreau, Y., & Ahookhosh, M. (2026) · Journal of Global Optimization · doi:10.1007/s10898-026-01642-5 · Cited by 13
“Representative examples include image deblurring [45], image inpainting [80], compressed sensing [14], sparse recovery [75], matrix factorization [16], nonnegative matrix factorization [27], matrix completion [68], tensor factorization [74], phase retrieval [23], and deep neural networks [33].”
Modern optimization theory and applications
Ye, Y., Jiang, B., Li, X., Jianjun, G., Qi, D., Chaolin, Y., Ge, D., Wang, Z., & He, S. (2020) · Scientia Sinica Mathematica · doi:10.1360/ssm-2020-0035 · Cited by 13
Discovering Dynamic Patterns from Spatiotemporal Data with Time-Varying Low-Rank Autoregression
Chen, X., Zhang, C., Chen, X., Saunier, N., & Sun, L. (2023) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2023.3294440 · Cited by 27
“The conjugate gradient method allows one to search for the approximated solution to a system of linear equations with a relatively small number of iterations (e.g., 5 or 10) [24], showing convergence guarantee for solving subproblems of matrix/tensor factorization [31].”
MethodSu, X., Wang, Y., Chu, H., Jiang, L., Yan, Y., Qiao, X., Yu, J., Guo, K., Zong, Y., & Wan, M. (2024) · Ultrasonics · doi:10.1016/j.ultras.2024.107379 · Cited by 12
Adaptive Rank-One Matrix Completion Using Sum of Outer Products
Wang, Z.-Y., Li, X. P., So, H. C., & Zoubir, A. M. (2023) · IEEE Transactions on Circuits and Systems for Video Technology · doi:10.1109/tcsvt.2023.3250651 · Cited by 12
“Lemma 1 means that MMM is the unique optimal solution of the following optimization problem Another lemma is the latest theorem for global optimality in low-rank optimization [55]–[62].”
BackgroundSolving Complex Quadratic Systems With Full-Rank Random Matrices
Huang, S., Gupta, S., & Dokmanić, I. (2020) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2020.3011016 · Cited by 12
“[57].”
Bauch, J., Nadler, B., & Zilber, P. (2021) · SIAM Journal on Mathematics of Data Science · doi:10.1137/20m1315294 · Cited by 12
Qin, Z., & Zhu, Z. (2025) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2025.3593840 · Cited by 11
“…encompasses various special tensor regression models, including scalar-on-tensor regression (where the response is a scalar) [18], [19], [20], tensor-on-vector regression (where N = 1 ) [21], [22], [23], and scalar-on-matrix regression (i.e., the matrix sensing problem) [24], [25], [26], [27].”
Lu, S., Hong, M., & Wang, Z. (2019) · Iowa State University Digital Repository (Iowa State University) · Cited by 11
Tong, T., Ma, C., & Chi, Y. (2021) · IEEE Data Science Workshop (DSW) · doi:10.1109/dslw51110.2021.9523407 · Cited by 12
“Low-rank matrix recovery has been a target of intense interest in the last decade; we invite the readers to check out [10], [11], [1] for recent overviews, and limit our discussions to the most relevant literature in the sequel.”
BackgroundSelf-citationSparsity-driven high-resolution fast electromagnetic vortex imaging based on two-dimensional NCALM
Qu, H., Cheng, D., Chen, C., & Chen, W. (2020) · IEEE International Conference on Computer and Communications (ICCC) · doi:10.1109/iccc51575.2020.9345020 · Cited by 11
Randomly Initialized Alternating Least Squares: Fast Convergence for Matrix Sensing
Lee, K., & Stöger, D. (2023) · SIAM Journal on Mathematics of Data Science · doi:10.1137/22m1506456 · Cited by 11
Communication-Efficient Distributed Eigenspace Estimation
Charisopoulos, V., Benson, A. R., & Damle, A. (2021) · SIAM Journal on Mathematics of Data Science · doi:10.1137/20m1364862 · Cited by 15
Constrained Channel Decomposition-Based Hybrid Beamforming for mmWave Massive MIMO Systems
Zilli, G. M., & Zhu, W. (2020) · IEEE Open Journal of the Communications Society · doi:10.1109/ojcoms.2020.3035118 · Cited by 12
“The solution to problem (14) is obtained with the projected block coordinate descent method [38], [39], by cyclically seeking the block coordinate descent solution with respect to each block variable (e.g., w k , i or f k , i ), while keeping the other block variable fixed.”
MethodRole of sparsity and structure in the optimization landscape of non-convex matrix sensing
Molybog, I., Sojoudi, S., & Lavaei, J. (2020) · Mathematical Programming · doi:10.1007/s10107-020-01590-2 · Cited by 11
Blind Super-Resolution of Point Sources via Projected Gradient Descent
Mao, S., & Chen, J. (2022) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2022.3209006 · Cited by 13
“where M = [ L R ]H ∈ C12, and the last term penalizes the mismatch between L and R, which is widely used in rectangular low rank matrix recovery [28, 33, 12].”
BackgroundMethodLearning Mixtures of Low-Rank Models
Chen, Y., Ma, C., Poor, H. V., & Chen, Y. (2021) · IEEE Transactions on Information Theory · doi:10.1109/tit.2021.3065700 · Cited by 11
Self-citationSorkhi, A. G., Abbasi, Z., Mobarakeh, M. I., & Pirgazi, J. (2021) · BMC Bioinformatics · doi:10.1186/s12859-021-04464-2 · Cited by 10
Gradient descent with adaptive stepsize converges (nearly) linearly under fourth-order growth
Davis, D., Drusvyatskiy, D., & Jiang, L. (2025) · Mathematical Programming · doi:10.1007/s10107-025-02290-5 · Cited by 10
Hyperspectral image denoising based on low-rank coefficients and orthonormal dictionary
Zhang, F., Yang, G., & Xue, J. (2020) · Signal Processing · doi:10.1016/j.sigpro.2020.107738 · Cited by 10
“One approach to solving (3) is by concatenating E and Z as a single variable and then directly applying standard iterative algorithms like gradient descent (or its variants); see [38, 39] for an overview.”
BackgroundTraonmilin, Y., Aujol, J., & Leclaire, A. (2022) · Information and Inference A Journal of the IMA · doi:10.1093/imaiai/iaac011 · Cited by 10
Complete Dictionary Learning via $\ell_p$-norm MaximizationPreprint
Shen, Y., Xue, Y., Zhang, J., Letaief, K. B., & Lau, V. K. N. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2002.10043 · Cited by 12
“If a benign landscape exists, a sophisticated saddle-point escaping scheme can find a global optimums in polynomial time [8].”
BackgroundHessian Eigenspectra of More Realistic Nonlinear ModelsPreprint
Liao, Z., & Mahoney, M. W. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2103.01519 · Cited by 13
“For non-convex problems, the properties of the local loss “landscape” around a given point w in the parameter space is of central significance [20, 26, 51, 56, 95–97].”
Forecasting Urban Traffic States with Sparse Data Using Hankel Temporal Matrix Factorization
Chen, X., Zhao, X.-L., & Cheng, C. (2024) · INFORMS journal on computing · doi:10.1287/ijoc.2022.0197 · Cited by 9
Ma, C., Xu, X., Tong, T., & Chi, Y. (2024) · Applied and numerical harmonic analysis · doi:10.1007/978-3-031-66497-7_7 · Cited by 10
Self-citationLow-Rank Contextual Reinforcement Learning from Heterogeneous Human Feedback
Lee, S. J., Sun, W. W., & Liu, Y. (2026) · Journal of the American Statistical Association · doi:10.1080/01621459.2026.2674413 · Cited by 9
“This assumption is standard in low-rank matrix estimation problems (Jain, Netrapalli, and Sanghavi 2013; Chi, Lu, and Chen 2019; Xia and Yuan 2021) and is commonly referred to as the “basin of attraction” condition, ensuring that the algorithm converges to the desired target.”
Matrix completion with nonconvex regularization: spectral operators and scalable algorithms
Mazumder, R., Saldana, D. F., & Weng, H. (2020) · Statistics and Computing · doi:10.1007/s11222-020-09939-5 · Cited by 9
Group-Sparse Matrix Factorization for Transfer Learning of Word Embeddings
Xu, K., Zhao, X., Bastani, H., & Bastani, O. (2026) · Management Science · doi:10.1287/mnsc.2022.01740 · Cited by 14
“We obtain tighter bounds under the following concept of smoothness from Chi et al. (2019): Definition 6.”
MethodLocal Geometry of Nonconvex Spike Deconvolution From Low-Pass Measurements
Costa, M. F. D., & Chi, Y. (2023) · IEEE Journal on Selected Areas in Information Theory · doi:10.1109/jsait.2023.3262689 · Cited by 12
“Our work can be viewed as falling into a growing line of research on developing provably efficient nonconvex methods—especially first-order methods—for high-dimensional signal estimation, examples including phase retrieval [26], low-rank matrix estimation [27, 19], blind deconvolution [28], dictionary learning [29], m…”
MethodSelf-citationMultiway Spherical Clustering Via Degree-Corrected Tensor Block Models
Hu, J., & Wang, M. (2023) · IEEE Transactions on Information Theory · doi:10.1109/tit.2023.3239521 · Cited by 9
“Our methods generalize the recent global-to-local strategy for matrix learning (Gao et al., 2018; Chi et al., 2019; Yun and Proutiere, 2016) to tensors (Han et al.”
MethodMatrix Completion from One-Bit Dither Samples
Eamaz, A., Yeganegi, F., & Soltanalian, M. (2024) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2024.3445289 · Cited by 9
“The convergence behavior of algorithms based on low-rank matrix factorization remains an active topic of study [2].”
Asynchronous Parallel Nonconvex Optimization Under the Polyak-Łojasiewicz Condition
Yazdani, K., & Hale, M. (2021) · IEEE Control Systems Letters · doi:10.1109/lcsys.2021.3082800 · Cited by 9
Enhanced sparse ISAR imaging by jointly using sparsity and low-rank properties
Lv, M., Chen, W., Ma, J., Cheng, Q., Yang, J. A., & Ma, X. (2021) · Digital Signal Processing · doi:10.1016/j.dsp.2021.103242 · Cited by 9
Depth Descent Synchronization in $${{\,\mathrm{\text {SO}}\,}}(D)$$
Maunu, T., & Lerman, G. (2023) · International Journal of Computer Vision · doi:10.1007/s11263-022-01686-6 · Cited by 12
“For many nonconvex methods, good initialization is quite important [Li et al., 2019, Maunu et al., 2019, Qu et al., 2019, Chi et al., 2019, Qu et al., 2020].”
MethodDistributed Stochastic Gradient Descent and Convergence to Local MinimaPreprint
Swenson, B., Murray, R., Kar, S., & Poor, H. V. (2020) · arXiv (Cornell University) · Cited by 9
Restoration Guarantee of Image Inpainting via Low Rank Patch Matrix Completion
Cai, J., Choi, J. K., Li, J., & Yin, G. (2024) · SIAM Journal on Imaging Sciences · doi:10.1137/23m1614456 · Cited by 11
Zhang, M., Ke, W., He, Y., Zhu, Q., & Xu, Y. (2024) · IEEE Sensors Journal · doi:10.1109/jsen.2024.3519357 · Cited by 8
An accelerated stochastic variance-reduced method for machine learning problems
Yang, Z., Chen, Z., & Wang, C. (2020) · Knowledge-Based Systems · doi:10.1016/j.knosys.2020.105941 · Cited by 9
On the Convergence of Non-Convex Phase Retrieval With Denoising Priors
Xue, D., Zheng, Z., Dai, W., Li, C., Zou, J., & Xiong, H. (2022) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2022.3203228 · Cited by 8
“…framework can be further generalized to solve the class of non-convex problems with denoising priors, e.g. , matrix sensing, matrix completion, and blind deconvolution as suggested in [45], as well as provide a well-developed tool for convergence analysis under denoisers without closed form.”
BackgroundNoncovANM: Gridless DOA Estimation for LPDF System
Zhao, Y., Chen, P., Cao, Z., & Wang, X. (2023) · IEEE Transactions on Vehicular Technology · doi:10.1109/tvt.2023.3293189 · Cited by 8
“In [31], two-stage and saddle-point escaping algorithms are given to escape undesired saddle points and find a local minimum efficiently, where the complexity of finding a saddle point is given in [32].”
BackgroundOne-Bit Matrix Completion With Time-Varying Sampling Thresholds
Eamaz, A., Yeganegi, F., & Soltanalian, M. (2023) · International Conference on Sampling Theory and Applications · doi:10.1109/sampta59647.2023.10301389 · Cited by 8
“As a special case of low-rank matrix sensing, matrix completion poses unique challenges due to the sampling matrices potentially not satisfying the matrix restricted isometry property (RIP) conditions [4, 5].”
BackgroundSensor Network Localization via Riemannian Conjugate Gradient and Rank Reduction
Li, Y., & Sun, X. (2024) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2024.3378378 · Cited by 8
“M , R n × d ∗ and S n + denote the general Riemannian manifold, the set of full column rank n × d matrices and the set of n × n PSD matrices, respectively.”
BackgroundOptimal Tuning-Free Convex Relaxation for Noisy Matrix Completion
Yang, Y., & Ma, C. (2023) · IEEE Transactions on Information Theory · doi:10.1109/tit.2023.3284341 · Cited by 8
Median-Truncated Gradient Descent: A Robust and Scalable Nonconvex Approach for Signal Estimation
Chi, Y., Li, Y., Zhang, H., & Liang, Y. (2019) · Applied and numerical harmonic analysis · doi:10.1007/978-3-319-73074-5_8 · Cited by 11
Self-citationNonconvex Low-Rank Symmetric Tensor Completion from Noisy DataPreprint
Cai, C., Li, G., Poor, H. V., & Chen, Y. (2019) · arXiv (Cornell University) · Cited by 8
Self-citationGeneral Low-rank Matrix Optimization: Geometric Analysis and Sharper BoundsPreprint
Zhang, H., Bi, Y., & Lavaei, J. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2104.10356 · Cited by 8
“Please see the survey paper by Chi et al. (2019) for more examples.”
BackgroundMicrobiome data integration via shared dictionary learning
Yuan, B., & Wang, S. (2025) · Nature Communications · doi:10.1038/s41467-025-63425-y · Cited by 8
“The matrix factorization employed in shared dictionary learning can aid in recovering these missing values (Chi et al., 2019).”
Hu, Q., Wu, H., & Luo, X. (2025) · IEEE/CAA Journal of Automatica Sinica · doi:10.1109/jas.2025.125774 · Cited by 20
Bénard, P.-J., Traonmilin, Y., Aujol, J., & Soubies, E. (2024) · Inverse Problems · doi:10.1088/1361-6420/ad33e4 · Cited by 7
Sensing and Deep CNN-Assisted Semi-Blind Detection for Multi-User Massive MIMO Communications
Han, F., Zeng, J., Zheng, L., Zhang, H., & Wang, J. (2024) · Remote Sensing · doi:10.3390/rs16020247 · Cited by 7
Atom-constrained Gridless DOA Refinement with Wirtinger Gradients
Park, Y., Gerstoft, P., & Mecklenbräuker, C. F. (2024) · IEEE Open Journal of Signal Processing · doi:10.1109/ojsp.2024.3496815 · Cited by 7
Can Learning Be Explained by Local Optimality in Robust Low-Rank Matrix Recovery?
Ma, J., & Fattahi, S. (2025) · Mathematics of Operations Research · doi:10.1287/moor.2023.0371 · Cited by 7
“These methods have demonstrated remarkable success in learning the true model across a range of modern ML tasks, from low-rank matrix recovery to training deep neural networks; see recent surveys [CC18, CLC19, ZQW20, Sun20, Sun19].”
Sensor network localization has a benign landscape after low-dimensional relaxation
Criscitiello, C., McRae, A. D., Rebjock, Q., & Boumal, N. (2026) · Mathematical Programming · doi:10.1007/s10107-026-02380-y · Cited by 7
“Problem (SNL–complete) is an instance of low-rank matrix sensing (Chi et al., 2019) with sensing operator ∆ given by (EDM–map).”
Xie, F., & Zhang, Y. (2025) · The Annals of Statistics · doi:10.1214/25-aos2520 · Cited by 7
On the geometric analysis of a quartic–quadratic optimization problem under a spherical constraint
Zhang, H., Milzarek, A., Wen, Z., & Yin, W. (2021) · Mathematical Programming · doi:10.1007/s10107-021-01702-6 · Cited by 10
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.