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
Edge artificial intelligence for 6g: vision, enabling technologies, and applications
Letaief, K. B., Shi, Y., Lu, J., & Lu, J. (2022) · IEEE Journal on Selected Areas in Communications · doi:10.1109/jsac.2021.3126076 · Cited by 829
“, blind demixing [189], phase retrieval [254], and shallow neural networks [255].”
BackgroundExploiting Shared Representations for Personalized Federated LearningPreprint
Collins, L., Hassani, H., Mokhtari, A., & Shakkottai, S. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2102.07078 · Cited by 1,317
“Incoherence of the ground-truth matrices is a key property required for efficient matrix completion and other sensing problems with sparse measurements (Chi et al., 2019).”
BackgroundOptimization for deep learning: theory and algorithms
Sun, R. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1912.08957 · Cited by 125
“[40] for a survey), which emerged after 2010 in machine learning and signal processing areas 15.”
BackgroundMa, C., Wang, K., Chi, Y., & Chen, Y. (2020) · Foundations of Computational Mathematics · doi:10.1007/s10208-019-09429-9 · Cited by 204
Self-citationGradient descent with random initialization: fast global convergence for nonconvex phase retrieval
Chen, Y., Chi, Y., Fan, J., & Ma, C. (2019) · Mathematical Programming · doi:10.1007/s10107-019-01363-6 · Cited by 122
Self-citationOptimization for Deep Learning: An Overview
Sun, R.-Y. (2020) · Journal of the Operations Research Society of China · doi:10.1007/s40305-020-00309-6 · Cited by 181
“Non-convex Matrix/Tensor Factorization The most related subarea to GON is “non-convex optimization for matrix/tensor factorization” (see, e.g., Chi et al. [131] for a survey), which emerged after around year 2009 in machine learning and signal pro-10 cessing areas.”
BackgroundGridless DOA Estimation and Root-MUSIC for Non-Uniform Linear Arrays
Wagner, M., Park, Y., & Gerstoft, P. (2021) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2021.3068353 · Cited by 191
“Convergence of the AP Gridless algorithm falls into the branch of research known as low rank matrix approximation, which has been active for several decades [57], [60].”
Wen, F., Chu, L., Liu, P., & Qiu, R. C. (2018) · IEEE Access · doi:10.1109/access.2018.2880454 · Cited by 185
Simulated Annealing: a Review and a New Scheme
Guilmeau, T., Chouzenoux, E., & Elvira, V. (2021) · 2021 IEEE Statistical Signal Processing Workshop (SSP) · doi:10.1109/ssp49050.2021.9513782 · Cited by 160
“In those problems, nonconvexity can arise from sparsity penalty [1], low-rank prior [2], non-linear observation model [3], non-linear regressor [4], blind thus multi-linear problem structure [5], or discrete variables [6].”
BackgroundSpectral Methods for Data Science: A Statistical Perspective
Chen, Y., Chi, Y., Fan, J., & Ma, C. (2021) · Foundations and Trends® in Machine Learning · doi:10.1561/2200000079 · Cited by 359
“We will not elaborate on the nonconvex optimization aspect here but instead recommend the reader to the overview article Chi et al. (2019).”
BackgroundMethodSelf-citationImplicit Regularization in Deep Matrix FactorizationPreprint
Arora, S., Cohen, N., Hu, W., & Luo, Y. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1905.13655 · Cited by 629
“The literature on matrix factorization for low-rank matrix recovery is far too broad to cover here — we refer to [10] for a recent survey, while mentioning that the technique is oftentimes attributed to [8].”
BackgroundHarnessing Sparsity Over the Continuum: Atomic norm minimization for superresolution
Chi, Y., & Costa, M. F. D. (2020) · IEEE Signal Processing Magazine · doi:10.1109/msp.2019.2962209 · Cited by 190
“A popular heuristic to SDP with low-rank solutions is to apply low-rank matrix factorization and solve the corresponding nonconvex optimization problem [95], [96], with the premise of greatly reducing its computational cost.”
MethodSelf-citationInference and uncertainty quantification for noisy matrix completion
Chen, Y., Fan, J., Ma, C., & Yan, Y. (2019) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.1910053116 · Cited by 127
“micthenuclearnormkZk (see [SS05,MHT10]). A variety of optimization algorithms have been proposed to tackle the nonconvex program (3.4) or its variants [SL16,CW15,MWCC17]; the readers are referred to [CLC19] for a recent overview. Asaprominentexample,atwo-stagealgorithm—gradientdescentfollowingsuitableinitialization —…”
BackgroundInfluentialSelf-citationChen, Y., Chi, Y., Fan, J., Ma, C., & Yan, Y. (2020) · SIAM Journal on Optimization · doi:10.1137/19m1290000 · Cited by 194
Self-citationAn Experimental Survey of Missing Data Imputation Algorithms
Miao, X., Wu, Y., Chen, L., Gao, Y., & Yin, J. (2022) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2022.3186498 · Cited by 180
“Unlike other machine learning solutions, compression-based methods only build one data compression model [54], [55] for the whole incomplete dataset.”
MethodRecent Theoretical Advances in Non-Convex Optimization
Danilova, M., Dvurechensky, P. E., Gasnikov, A. V., Gorbunov, E., Guminov, S. V., Kamzolov, D., & Shibaev, I. (2022) · Springer optimization and its applications · doi:10.1007/978-3-031-00832-0_3 · Cited by 162
Low Rank Regularization: A review
Hu, Z., Nie, F., Wang, R., & Li, X. (2020) · Neural Networks · doi:10.1016/j.neunet.2020.09.021 · Cited by 116
Nonconvex Robust Low-Rank Matrix Recovery
Li, X., Zhu, Z., So, A. M., & Vidal, R. (2020) · SIAM Journal on Optimization · doi:10.1137/18m1224738 · Cited by 86
Implicit Regularization in Deep Learning May Not Be Explainable by NormsPreprint
Razin, N., & Cohen, N. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2005.06398 · Cited by 188
“[13] Yuejie Chi, Yue M Lu, and Yuxin Chen.”
BackgroundLi, Z., Luo, Y., & Lyu, K. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2012.09839 · Cited by 94
“Examples include matrix sensing, matrix completion, phase retrieval, robust principal component analysis, just to name a few (see Chi et al. 2019 for a survey).”
MethodNonconvex Low-Rank Tensor Completion from Noisy Data
Cai, C., Li, G., Poor, H. V., & Chen, Y. (2021) · Operations Research · doi:10.1287/opre.2021.2106 · Cited by 80
Self-citationAn optimal statistical and computational framework for generalized tensor estimation
Han, R., Willett, R. M., & Zhang, A. R. (2022) · The Annals of Statistics · doi:10.1214/21-aos2061 · Cited by 80
The Global Landscape of Neural Networks: An Overview
Sun, R., Li, D., Liang, S., Ding, T., & Srikant, R. (2020) · IEEE Signal Processing Magazine · doi:10.1109/msp.2020.3004124 · Cited by 134
“In this context, it has been established that the landscape is benign (e.g., every local minimum is a global minimum) for quite a few matrix problems, such as matrix completion and phase retrieval, under certain assumptions (see, e.g., [10] for a survey).”
BackgroundMethodZhang, Y., An, R., Liu, S., Cui, J., & Shang, X. (2021) · IEEE Transactions on Big Data · doi:10.1109/tbdata.2021.3125204 · Cited by 83
“Matrix factorization-based methods aim to approximate a matrix by the product of two feature matrices [18].”
MethodLow-Rank Matrix Recovery with Composite Optimization: Good Conditioning and Rapid Convergence
Charisopoulos, V., Chen, Y., Davis, D., Díaz, M., Ding, L., & Drusvyatskiy, D. (2021) · Foundations of Computational Mathematics · doi:10.1007/s10208-020-09490-9 · Cited by 116
Self-citationHigh-Dimensional Principal Component Analysis with Heterogeneous Missingness
Zhu, Z., Wang, T., & Samworth, R. J. (2022) · Journal of the Royal Statistical Society Series B (Statistical Methodology) · doi:10.1111/rssb.12550 · Cited by 83
“For comparison, we also studied the softImpute algorithm (Mazumder, Hastie and Tibshirani, 2010; Hastie et al., 2015), which is considered to be state-of-the-art for matrix completion (Chi, Lu and Chen, 2018).”
MethodBridging convex and nonconvex optimization in robust PCA: Noise, outliers and missing data
Chen, Y., Fan, J., Ma, C., & Yan, Y. (2021) · The Annals of Statistics · doi:10.1214/21-aos2066 · Cited by 92
Self-citationFrom Symmetry to Geometry: Tractable Nonconvex ProblemsPreprint
Zhang, Y., Qu, Q., & Wright, J. N. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2007.06753 · Cited by 66
“This class includes important model problems in phase recovery [3, 46] and low-rank estimation [11].”
BackgroundInfluentialAccelerating Ill-Conditioned Low-Rank Matrix Estimation via Scaled Gradient DescentPreprint
Tong, T., Ma, C., & Chi, Y. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2005.08898 · Cited by 67
“…iterates of the ScaledGD method in (8) satisfy Comparing to the rate of contraction (1 − 1 /κ ) of gradient descent for matrix factorization [MLC19, CLC19], Theorem 4 demonstrates that the pre-conditioners indeed allow better search directions in the local neighborhood of the ground truth, and…”
MethodSelf-citationSecond-Order Guarantees of Distributed Gradient Algorithms
Daneshmand, A., Scutari, G., & Kungurtsev, V. (2020) · SIAM Journal on Optimization · doi:10.1137/18m121784x · Cited by 68
Nonconvex Matrix Factorization From Rank-One Measurements
Li, Y., Ma, C., Chen, Y., & Chi, Y. (2021) · IEEE Transactions on Information Theory · doi:10.1109/tit.2021.3050427 · Cited by 54
“On the other hand, nonconvex approaches have drawn intense attention in the past decade due to their ability to achieve computational and statistical efficiency all at once [35].”
BackgroundSelf-citationInference for heteroskedastic PCA with missing data
Yan, Y., Chen, Y., & Fan, J. (2024) · The Annals of Statistics · doi:10.1214/24-aos2366 · Cited by 48
Self-citationTong, T., Ma, C., & Chi, Y. (2021) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2021.3071560 · Cited by 72
Self-citationUnderstanding the Generalization Benefit of Normalization Layers: Sharpness Reduction
Lyu, K., Li, Z., & Arora, S. (2022) · neural information processing systems · doi:10.52202/068431-2514 · Cited by 131
Bayesian optimization with Gaussian process surrogate model for source localization
Jenkins, W. F., Gerstoft, P., & Park, Y. (2023) · The Journal of the Acoustical Society of America · doi:10.1121/10.0020839 · Cited by 46
A Riemannian rank-adaptive method for low-rank matrix completion
Gao, B., & Absil, P.-A. (2021) · Computational Optimization and Applications · doi:10.1007/s10589-021-00328-w · Cited by 44
“This suggests that the proposed method might also perform well on other low-rank optimization problems, such as those mentioned in [12,19,4,16].”
MethodRobust Matrix Completion Based on Factorization and Truncated-Quadratic Loss Function
Wang, Z.-Y., Li, X. P., & So, H. C. (2022) · IEEE Transactions on Circuits and Systems for Video Technology · doi:10.1109/tcsvt.2022.3214583 · Cited by 47
Wu, X., Yang, Z., Stoica, P., & Xu, Z. (2022) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2022.3198863 · Cited by 42
“Several references on nonconvex approaches to low-rank matrix recovery with guaranteed global optimality [60], [61], [62] may prove useful in this direction.”
BackgroundAnalysis of the optimization landscape of Linear Quadratic Gaussian (LQG) control
Tang, Y., Zheng, Y., & Li, N. (2023) · Mathematical Programming · doi:10.1007/s10107-023-01938-4 · Cited by 59
“, in phase retrieval [21] and low-rank matrix factorization [22, 23]) and discrete symmetry (e.”
BackgroundShape Matters: Understanding the Implicit Bias of the Noise CovariancePreprint
HaoChen, J. Z., Wei, C., Lee, J. D., & Ma, T. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2006.08680 · Cited by 43
Subgradient Descent Learns Orthogonal DictionariesPreprint
Bai, Y. D., Jiang, Q., & Sun, J. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1810.10702 · Cited by 38
“By contrast, the recent progress in smooth nonconvex optimization has demonstrated that it is possible to separate the efforts of function landscape characterization and algorithm development (Sun et al., 2015b; Ge et al., 2015; Chi et al., 2018), so that on a class of benignly structured problems, global optimizers c…”
BackgroundSubspace Estimation from Unbalanced and Incomplete Data Matrices: 𝓁2, ∞ Statistical Guarantees
Cai, C., Li, G., Chi, Y., Poor, H. V., & Chen, Y. (2021) · The Annals of Statistics · doi:10.1214/20-aos1986 · Cited by 37
Self-citationPokala, P. K., Hemadri, R. V., & Seelamantula, C. S. (2021) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2021.3122259 · Cited by 37
Convergence of Random Reshuffling under the Kurdyka–Łojasiewicz Inequality
Xiao, L., Milzarek, A., & Qiu, J. (2023) · SIAM Journal on Optimization · doi:10.1137/21m1468048 · Cited by 37
Swenson, B., Murray, R., Poor, H. V., & Kar, S. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2003.02818 · Cited by 42
Asymmetry helps: Eigenvalue and eigenvector analyses of asymmetrically perturbed low-rank matrices
Chen, Y., Cheng, C., & Fan, J. (2021) · The Annals of Statistics · doi:10.1214/20-aos1963 · Cited by 36
Self-citationOn Low-Rank Directed Acyclic Graphs and Causal Structure Learning
Fang, Z., Zhu, S., Zhang, J., Liu, Y., Chen, Z., & He, Y. (2023) · IEEE Transactions on Neural Networks and Learning Systems · doi:10.1109/tnnls.2023.3273353 · Cited by 55
Guaranteed Recovery of One-Hidden-Layer Neural Networks via Cross Entropy
Fu, H., Chi, Y., & Liang, Y. (2020) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2020.2993153 · Cited by 49
“The parameter recovery viewpoint is relevant to the success of nonconvex learning in signal processing problems such as matrix completion, phase retrieval, blind deconvolution, dictionary learning and tensor decomposition [21]–[28], to name a few; see also the overview article [29].”
BackgroundSelf-citationA Robust Coevolutionary Neural-Based Optimization Algorithm for Constrained Nonconvex Optimization
Wei, L., Jin, L., & Luo, X. (2022) · IEEE Transactions on Neural Networks and Learning Systems · doi:10.1109/tnnls.2022.3220806 · Cited by 35
“For the previous studies on nonconvex optimization problems, a routine is to assume that there is no perturbation when executing the solution task [36], [37], [38].”
BackgroundFu, X., Vervliet, N., Lathauwer, L. D., Huang, K., & Gillis, N. (2020) · IEEE Signal Processing Magazine · doi:10.1109/msp.2020.3003544 · Cited by 38
“, compressed matrix recovery and matrix completion) are known to be solvable via nonconvex optimization methods, under certain conditions [65].”
BackgroundComposite optimization for robust rank one bilinear sensing
Charisopoulos, V., Davis, D., Díaz, M., & Drusvyatskiy, D. (2020) · Information and Inference A Journal of the IMA · doi:10.1093/imaiai/iaaa027 · Cited by 38
Zhang, Y., & Tang, M. (2023) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2023.3327631 · Cited by 38
“…local-minima, thereby making the theoretical analysis intractable unless we assume that the initial estimates for GD/SGD are sufficiently close to the global minima; see e.g., [43], [44] for some examples of results relating the closeness of the initial estimates and the convergence rate of GD/SGD.”
BackgroundResultSharp Global Guarantees for Nonconvex Low-Rank Recovery in the Noisy Overparameterized Regime
Zhang, R. Y. (2025) · SIAM Journal on Optimization · doi:10.1137/24m1697980 · Cited by 33
“Although low-rank matrix recovery under RIP is standard in the literature [4, 13, 9], a common critique is that it requires dense measurements, in the sense that A ( e i e Tj ) ̸ = 0 must hold for all i, j .”
Cai, C., Poor, H. V., & Chen, Y. (2022) · IEEE Transactions on Information Theory · doi:10.1109/tit.2022.3205781 · Cited by 32
Self-citationBeyond Procrustes: Balancing-Free Gradient Descent for Asymmetric Low-Rank Matrix Sensing
Ma, C., Li, Y., & Chi, Y. (2021) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2021.3051425 · Cited by 32
“The readers are referred to the recent overview [32] for additional references.”
BackgroundSelf-citationOn the computational and statistical complexity of over-parameterized matrix sensingPreprint
Zhuo, J., Kwon, J., Ho, N., & Caramanis, C. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2102.02756 · Cited by 32
“This computational overhead motivates the study of FGD method.”
MethodQuantum Neural Network Compression
Hu, Z., Dong, P., Wang, Z., Lin, Y., Wang, Y., & Jiang, W. (2022) · International Conference on Computer Aided Design · doi:10.1145/3508352.3549382 · Cited by 57
“To solve the aforementioned constrained non-convex optimization CQCP problem, there are two possible directions: (1) directly apply the existing mathematical programming techniques [9, 16], such as employing a stochastic path-integrated differential estimator; (2) transform the constrained non-convex problem to an unc…”
MethodEntrywise Estimation of Singular Vectors of Low-Rank Matrices With Heteroskedasticity and Dependence
Agterberg, J., Lubberts, Z., & Priebe, C. E. (2022) · IEEE Transactions on Information Theory · doi:10.1109/tit.2022.3159085 · Cited by 30
“In addition, eigenvectors or related quantities can be used as a “warm start” for optimization methods (Chen et al. (2019, 2021b); Chi et al. (2019); Lu and Li (2017); Ma et al. (2020); Xie and Xu (2020); Xie (2021)), yielding provable convergence to quantities of interest provided the…”
MethodXin, R., Das, S., Khan, U. A., & Kar, S. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2110.01594 · Cited by 30
“The above formulations are quite general and has found applications in, e.g., sparse non-convex linear models [2], principle component analysis [45], and matrix factorization [9].”
BackgroundNon-convex low-rank matrix recovery with arbitrary outliers via median-truncated gradient descent
Li, Y., Chi, Y., Zhang, H., & Liang, Y. (2019) · Information and Inference A Journal of the IMA · doi:10.1093/imaiai/iaz009 · Cited by 29
Self-citationSharp global convergence guarantees for iterative nonconvex optimization with random data
Chandrasekher, K. A., Pananjady, A., & Thrampoulidis, C. (2023) · The Annals of Statistics · doi:10.1214/22-aos2246 · Cited by 46
“At the same time, iterative algorithms run on nonconvex model-fitting problems with random data often exhibit several behaviors that are distinct from those observed in standard convex programming (see the monographs [43, 16, 18, 100] for examples).”
BackgroundExact Recovery of Multichannel Sparse Blind Deconvolution via Gradient Descent
Qu, Q., Li, X., & Zhu, Z. (2020) · SIAM Journal on Imaging Sciences · doi:10.1137/19m1291327 · Cited by 31
“648 [39] Yuejie Chi, Yue M Lu, and Yuxin Chen.”
BackgroundBoundary Defense Against Cyber Threat for Power System State Estimation
Jin, M., Lavaei, J., Sojoudi, S., & Baldick, R. (2020) · IEEE Transactions on Information Forensics and Security · doi:10.1109/tifs.2020.3043065 · Cited by 27
“Existing approaches to solve these problems include convex relaxation [23], [25], [26] and iterative algorithms [24].”
BackgroundFan, X., Liang, J., Zhao, X., Zhang, Y., & So, H. C. (2020) · IEEE Transactions on Antennas and Propagation · doi:10.1109/tap.2020.2992860 · Cited by 26
“On the other hand, the penalty and steepest method requires low computational and memory requirements, so it can be well suited for application to large-scale problems and is widely used in practice [16], [17], [20].”
BackgroundUniform RIP Conditions for Recovery of Sparse Signals by $\ell _p\,(0< p\leq 1)$ Minimization
Wan, A. (2020) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2020.3022822 · Cited by 28
“Much progress has been made on developing efficient algorithms for low-rank matrix completion via nonconvex optimization [18], [19].”
BackgroundHePPCAT: Probabilistic PCA for Data With Heteroscedastic Noise
Hong, D. K., Gilman, K., Balzano, L., & Fessler, J. A. (2021) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2021.3104979 · Cited by 34
“Three recent surveys summarize much of this progress [38, 39, 40] and thoroughly treat this related work.”
BackgroundProjected Gradient Descent for Non-Convex Sparse Spike Estimation
Traonmilin, Y., Aujol, J., & Leclaire, A. (2020) · IEEE Signal Processing Letters · doi:10.1109/lsp.2020.3003241 · Cited by 26
“Our method, following insights from the literature on nonconvex optimization for low-dimensional models [5], [7], [8], [19], [22], relies on two steps:”
MethodLi, H., Li, Z., Li, K., Rellermeyer, J. S., Chen, L. Y., & Li, K. (2020) · IEEE Transactions on Parallel and Distributed Systems · doi:10.1109/tpds.2020.3047460 · Cited by 36
“L-smooth function obviously [49], [50], [53].”
BackgroundMethodInfluentialAn Analysis of Constant Step Size SGD in the Non-convex Regime: Asymptotic Normality and BiasPreprint
Yu, L., Balasubramanian, K., Volgushev, S., & Erdogdu, M. A. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2006.07904 · Cited by 34
“From a statistical perspective, oftentimes these critical points or local minimizers have nice statistical properties [20, 3, 12, 21, 22, 5]; see also [23] for a counterexample.”
BackgroundTree-Based Real-Time Advertisement Recommendation System in Online Broadcasting
Kang, S., Jeong, C., & Chung, K. (2020) · IEEE Access · doi:10.1109/access.2020.3031925 · Cited by 25
“Among the model-based CF approaches, matrix factorization (MF) based on low dimensional (low rank) factor models is one of the most popular methods since it is known to generate the most accurate model [28].”
MethodProvable Bregman-divergence based Methods for Nonconvex and Non-Lipschitz ProblemsPreprint
Li, Q., Zhu, Z., Tang, G., & Wakin, M. B. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1904.09712 · Cited by 25
“Due to the requirement of the Lipschitz smoothness condition, the current theory for most traditional first-order (or even second-order) and alternating minimization algorithms cannot accommodate high-degree (larger than 2) polynomial objective functions, which sets demanding restrictions on the applications and conse…”
MethodScaling and Scalability: Provable Nonconvex Low-Rank Tensor Estimation from Incomplete MeasurementsPreprint
Tong, T., Ma, C., Prater-Bennette, A., Tripp, E. E., & Chi, Y. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2104.14526 · Cited by 47
Self-citationFinding the Sparsest Vectors in a Subspace: Theory, Algorithms, and ApplicationsPreprint
Qu, Q., Zhu, Z., Li, X., Tsakiris, M. C., Wright, J. N., & Vidal, R. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2001.06970 · Cited by 25
“…advances in phase retrieval [10–13], phase synchronization [14, 15], blind deconvolution [16, 17], dictionary learning [18, 19], matrix factorization [20–28], tensor decomposition [29], etc., reveal that the optimization landscapes of nonconvex problems often have benign geometric properties.”
BackgroundGeometry of Linear Convolutional Networks
Kohn, K., Merkh, T., Montúfar, G., & Trager, M. (2022) · SIAM Journal on Applied Algebra and Geometry · doi:10.1137/21m1441183 · Cited by 44
The power of preconditioning in overparameterized low-rank matrix sensing
Xu, X., Shen, Y., Chi, Y., & Ma, C. (2025) · Information and Inference A Journal of the IMA · doi:10.1093/imaiai/iaaf033 · Cited by 27
Self-citationNonconvex Structured Phase Retrieval: A Focus on Provably Correct Approaches
Vaswani, N. (2020) · IEEE Signal Processing Magazine · doi:10.1109/msp.2020.3003541 · Cited by 23
“Another important application of PR is in latent variable models, where the hidden variables are the missing signs of the linear projections of the unknown data vector/signal [1].”
BackgroundMethodInfluentialPCA reduced Gaussian mixture models with applications in superresolution
Hertrich, J., Nguyen, D.-P.-L., Aujol, J., Bernard, D., Berthoumieu, Y., Saadaldin, A., & Steidl, G. (2021) · Inverse Problems and Imaging · doi:10.3934/ipi.2021053 · Cited by 27
Structured Gradient Descent for Fast Robust Low-Rank Hankel Matrix Completion
Cai, H., Cai, J., & You, J. (2023) · SIAM Journal on Scientific Computing · doi:10.1137/22m1491009 · Cited by 31
“For a good initial guess, we modify the widely used spectral method [18, Section VIII].”
MethodAlgorithmic Regularization in Model-Free Overparametrized Asymmetric Matrix Factorization
Jiang, L., Chen, Y., & Ding, L. (2023) · SIAM Journal on Mathematics of Data Science · doi:10.1137/22m1519833 · Cited by 22
Self-citationZhang, Q., He, L., Wang, Y., Deng, L.-J., & Liu, J. (2024) · Signal Processing · doi:10.1016/j.sigpro.2024.109382 · Cited by 24
Exponential convergence of Sobolev gradient descent for a class of nonlinear eigenproblems
Zhang, Z. (2022) · Communications in Mathematical Sciences · doi:10.4310/cms.2022.v20.n2.a4 · Cited by 22
Rank Overspecified Robust Matrix Recovery: Subgradient Method and Exact RecoveryPreprint
Ding, L., Jiang, L., Chen, Y., Qu, Q., & Zhu, Z. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2109.11154 · Cited by 34
“2) [20–23]; in this case, the loss function has no spurious local minimum and is locally strongly convex [24, 25].”
BackgroundSelf-citationDeep dynamic imputation of clinical time series for mortality prediction
Shi, Z., Wang, S., Yue, L., Pang, L., Zuo, X., Zuo, W., & Li, X. (2021) · Information Sciences · doi:10.1016/j.ins.2021.08.016 · Cited by 21
Graph-guided Bayesian matrix completion for ocean sound speed field reconstruction
Li, S., Cheng, L., Zhang, T., Zhao, H., & Li, J. (2023) · The Journal of the Acoustical Society of America · doi:10.1121/10.0017064 · Cited by 21
Huang, C., Cui, J., Fu, Y., Huang, D., Zhao, M., & Li, L. (2023) · Neural Networks · doi:10.1016/j.neunet.2023.03.013 · Cited by 21
Robust Matrix Completion with Heavy-Tailed Noise
Wang, B. J., & Fan, J. (2024) · Journal of the American Statistical Association · doi:10.1080/01621459.2024.2375037 · Cited by 29
“This problem, usually termed as matrix completion , has attracted a lot of attention over a decade (Candes and Plan 2010; Keshavan, Montanari, and Oh 2010; Candes and Plan 2011; Ma et al. 2018; Chi, Lu, and Chen 2019; Chen, Liu, and Li 2020a; Chen et al. 2020b).”
Olikier, G., Gallivan, K., & Absil, P.-A. (2022) · Mathematics of Operations Research · doi:10.1287/moor.2024.0582 · Cited by 10
Robust Matrix Completion With Column Outliers
Nie, F., Li, Z., Hu, Z., Wang, R., & Li, X. (2021) · IEEE Transactions on Cybernetics · doi:10.1109/tcyb.2021.3072896 · Cited by 20
A novel fuzzy neural collaborative filtering for recommender systems
Deng, J., Chen, J., Wang, S., Ye, J., & Wang, Y. (2024) · Expert Systems with Applications · doi:10.1016/j.eswa.2024.125153 · Cited by 20
A Generalization of Wirtinger Flow for Exact Interferometric Inversion
Yonel, B., & Yazıcı, B. (2019) · SIAM Journal on Imaging Sciences · doi:10.1137/19m1238599 · Cited by 20
A Deterministic Theory for Exact Non-Convex Phase Retrieval
Yonel, B., & Yazıcı, B. (2020) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2020.3007967 · Cited by 20
Cheng, C., Wei, Y., & Chen, Y. (2021) · IEEE Transactions on Information Theory · doi:10.1109/tit.2021.3111828 · Cited by 20
Self-citationChen, Y., Fan, J., Wang, B., & Yan, Y. (2021) · Journal of the American Statistical Association · doi:10.1080/01621459.2021.1956501 · Cited by 20
“…that the model (1) might remind readers of the famous problem of phase retrieval (Candes, Strohmer, and Voroninski 2013; Shechtman et al. 2015; Chi, Lu, and Chen 2019), which is concerned with solving random quadratic systems of equations and clearly related to the problem of solving bilinear…”
BackgroundSelf-citationEltrass, A. S. (2022) · Biomedical Signal Processing and Control · doi:10.1016/j.bspc.2022.103750 · Cited by 22
Zhang, R. Y. (2024) · Mathematical Programming · doi:10.1007/s10107-024-02160-6 · Cited by 20
On critical points of quadratic low-rank matrix optimization problems
Uschmajew, A., & Vandereycken, B. (2020) · IMA Journal of Numerical Analysis · doi:10.1093/imanum/drz061 · Cited by 21
“, 2016), which are much less costly per iteration; see also Chi et al. (2019) for a recent overview.”
BackgroundEstimating differential latent variable graphical models with applications to brain connectivity
Na, S., Kolar, M., & Koyejo, S. (2020) · Biometrika · doi:10.1093/biomet/asaa066 · Cited by 28
The Global Geometry of Centralized and Distributed Low-rank Matrix Recovery Without Regularization
Li, S., Li, Q., Zhu, Z., Tang, G., & Wakin, M. B. (2020) · IEEE Signal Processing Letters · doi:10.1109/lsp.2020.3008876 · Cited by 20
Adversarial classification via distributional robustness with Wasserstein ambiguity
Ho-Nguyen, N., & Wright, S. J. (2022) · Mathematical Programming · doi:10.1007/s10107-022-01796-6 · Cited by 31
“[15]).”
Super-Resolution and Accurate Full-Field Displacement Measurement With Millimeter-Wave Radars
Liu, Z., Xiong, Y., Wu, G., Meng, G., & Peng, Z. (2023) · IEEE Transactions on Instrumentation and Measurement · doi:10.1109/tim.2023.3327467 · Cited by 19
“Many SR methods are proposed to solve this problem but almost all of them are essentially non-convex optimization, while the non-convexity does not allow for finding a global solution in a reasonable time [37].”
Method
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.