Complete Dictionary Recovery Over the Sphere I: Overview and the Geometric Picture
Open accessThe DOI matches its Crossref record; 160 of the 174 references it cites were found in a registry or an index.
Abstract
We consider the problem of recovering a complete (i.e., square and invertible) matrix A0, from Y ∈ Rn×pwith Y = A0X0, provided X0is sufficiently sparse. This recovery problem is central to theoretical understanding of dictionary learning, which seeks a sparse representation for a collection of input signals and finds numerous applications in modern signal processing and machine learning. We give the first efficient algorithm that provably recovers A0when X0has O (n) nonzeros per column, under suitable probability model for X0. In contrast, prior results based on efficient algorithms either only guarantee recovery when X0has O(√n) zeros per column, or require multiple rounds of semidefinite programming relaxation to work when X0has O(n) nonzeros per column. Our algorithmic pipeline centers around solving a certain nonconvex optimization problem with a spherical constraint. In this paper, we provide a geometric characterization of the objective landscape. In particular, we show that the problem is highly structured with high probability: 1) there are no “spurious” local minimizers and 2) around all saddle points the objective has a negative directional curvature. This distinctive structure makes the problem amenable to efficient optimization algorithms. In a companion paper, we design a second-order trust-region algorithm over the sphere that provably converges to a local minimizer from arbitrary initializations, despite the presence of saddle points.
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
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
“Besides, with high-dimensional datasets, the nonconvex loss functions of certain statistical learning models, including over-parameterized neural networks [180] and dictionary learning [256], can enjoy benign global geometric landscape such that all the local minima are global minima, and all the saddle points can be escaped efficiently using the algorithms including trust region method and pertur”
From Edge artificial intelligence for 6g: vision, enabling technologies, and applications (2022) · cites this paper as [256]
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
(2021) · A First Course in Statistical Programming with R · doi:10.1017/9781108993456.011 · Cited by 13,724
Independent component analysis: algorithms and applications
Hyvärinen, A., & Oja, E. (2000) · Neural Networks · doi:10.1016/s0893-6080(00)00026-5 · Cited by 8,705 · cited 1×
“Putting together the above estimates for the case w (cid:54) = 0 , we obtain Hence for all w , we can take the 1 5 √ 2 π as the lower bound, completing the proof.”
MethodIndependent component analysis, A new concept?
Comon, P. (1994) · Signal Processing · doi:10.1016/0165-1684(94)90029-9 · Cited by 8,205
Independent Component Analysis
(2004) · Independent Component Analysis · doi:10.7551/mitpress/3717.003.0014 · Cited by 7,903
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
Self-citationFast and robust fixed-point algorithms for independent component analysis
Hyvarinen, A. (1999) · IEEE Transactions on Neural Networks · doi:10.1109/72.761722 · Cited by 6,246 · cited 1×
“Putting together the above estimates for the case w (cid:54) = 0 , we obtain Hence for all w , we can take the 1 5 √ 2 π as the lower bound, completing the proof.”
MethodEmergence of simple-cell receptive field properties by learning a sparse code for natural images
Olshausen, B. A., & Field, D. J. (1996) · Nature · doi:10.1038/381607a0 · Cited by 5,694 · cited 2×
“We have Collecting the above estimates, we have where at the second line we have used the assumption that (cid:107) w (cid:107) ≥ µ/ (4 √ 2) and also the fact that √ 2) .”
BackgroundMethodParallel and Distributed Computation: Numerical Methods
Bertsekas, D. P., & Tsitsiklis, J. N. (1989) · DSpace@MIT (Massachusetts Institute of Technology) · Cited by 5,293
Independent Component Analysis
Hyvärinen, A., Karhunen, J., & Oja, E. (2001) · Wiley eBooks · doi:10.1002/0471221317 · Cited by 5,007
Sparse coding with an overcomplete basis set: A strategy employed by V1?
Olshausen, B. A., & Field, D. J. (1997) · Vision Research · doi:10.1016/s0042-6989(97)00169-7 · Cited by 3,642 · cited 1×
“For any θ ∈ (0 , 1 / 2) , if µ ≤ c min θn − 1 , n − 5 / 4 , it holds for all w with 1 / 20 Here c > 0 is a constant.”
Research works printed but not linked: 1
- candès, 2014, Mathematics of sparsity (and a few other things), Proc Int Congr Math, 1
Cited by
Items 101–200 of 290
Finding a low-rank basis in a matrix subspace
Nakatsukasa, Y., Soma, T., & Uschmajew, A. (2016) · Mathematical Programming · doi:10.1007/s10107-016-1042-2 · Cited by 22
“The recent work [60,61] is an extensive theoretical and practical approach to the very similar problem of sparse dictionary learning.”
BackgroundEvolutionary Gradient Descent for Non-convex Optimization
Xue, K., Qian, C., Xu, L., & Fei, X. (2021) · International Joint Conference on Artificial Intelligence · doi:10.24963/ijcai.2021/443 · Cited by 21
“…optimization, it often requires to escape the saddle points and find a second-order stationary point, which can approximate the global optimum well in many cases, e.g., matrix factorization [ Li et al. , 2016 ] , matrix completion [ Ge et al. , 2016 ] and dictionary learning [ Sun et al. , 2016 ] .”
BackgroundNearly 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
“matrix sensing [2, 29], tensor decomposition [15], dictionary learning [33] and matrix completion [16].”
BackgroundOn 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
“Such remarkable properties have been rigorously proven under suitable assumptions for different low-rank optimization problems like matrix sensing [4, 23], matrix completion [34, 14], general convex functions on M≤k [18, 41], SDPs [6, 7], and also for some other problems in the context of compressed sensing like phase…”
BackgroundMultichannel Sparse Blind Deconvolution on the Sphere
Li, Y., & Bresler, Y. (2019) · IEEE Transactions on Information Theory · doi:10.1109/tit.2019.2928576 · Cited by 21
“Similar geometric analysis has been conducted for dictionary learning [40], phase retrieval [41], and single channel sparse blind deconvolution [13].”
MethodKuai, X., Yuan, X., Yan, W., Liu, H., & Zhang, Y. A. (2020) · IEEE Transactions on Communications · doi:10.1109/tcomm.2020.2969905 · Cited by 21
Fattahi, S., & Sojoudi, S. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1812.11466 · Cited by 21
“, 2018), and dictionary recovery (Sun et al., 2017) have benign global landscape, i.”
BackgroundUnique Sharp Local Minimum in $\ell_1$-minimization Complete Dictionary LearningPreprint
Wang, Y., Wu, S., & Yu, B. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1902.08380 · Cited by 21
Ma, J., & Fattahi, S. (2022) · arXiv (Cornell University) · doi:10.48550/arxiv.2202.08788 · Cited by 21
An Envelope for Davis–Yin Splitting and Strict Saddle-Point Avoidance
Liu, Y., & Yin, W. (2019) · Journal of Optimization Theory and Applications · doi:10.1007/s10957-019-01477-z · Cited by 20
Data-Driven Discovery of Block-Oriented Nonlinear Models Using Sparse Null-Subspace Methods
Li, J., Li, X., Zhang, H., Chen, G., & Yuan, Y. (2020) · IEEE Transactions on Cybernetics · doi:10.1109/tcyb.2020.3015705 · Cited by 19
Improved Learning of One-hidden-layer Convolutional Neural Networks with OverlapsPreprint
Du, S. S., & Goel, S. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1805.07798 · Cited by 18
“] finds a global minimum in polynomial time. Many problems in machine learning admit these benign geometric properties, including including tensor decomposition [Ge et al., 2015], dictionary learning [Sun et al., 2017], matrix sensing [Bhojanapalli et al., 2016, Park et al., 2017], matrix completion [Ge et al., 2017a,…”
BackgroundGradient Descent Provably Escapes Saddle Points in the Training of Shallow ReLU Networks
Cheridito, P., Jentzen, A., & Rossmannek, F. (2024) · Journal of Optimization Theory and Applications · doi:10.1007/s10957-024-02513-3 · Cited by 17
“While empirical evidence suggests that many saddle points are strict (see [12]), this is proved only in some special cases; for example, for shallow quadratic networks [ 16, 41] and for deep linear networks [3, 28].”
A Convex Variational Model for Learning Convolutional Image Atoms from Incomplete Data
Chambolle, A., Holler, M., & Pock, T. (2019) · Journal of Mathematical Imaging and Vision · doi:10.1007/s10851-019-00919-7 · Cited by 17
Manifold 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
Riemannian Perspective on Matrix FactorizationPreprint
Ahn, K., & Suarez, F. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2102.00937 · Cited by 17
“Apart from matrix completion, over the last few years, there have been many works understanding Riemannian landscape for other problems, including dictionary learning (Sun et al., 2016; Bai et al., 2018; Zhu et al., 2019; Li et al., 2019), (robust) subspace recovery (Maunu et al.”
BackgroundUnderstanding approximate and unrolled dictionary learning for pattern recoveryPreprint
Malézieux, B., Moreau, T., & Kowalski, M. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2106.06338 · Cited by 17
“Theoretical elements on identifiability and local convergence have been proven in several studies (Gribonval et al., 2015; Haeffele & Vidal, 2015; Agarwal et al., 2016; Sun et al., 2016).”
BackgroundA Global Geometric Analysis of Maximal Coding Rate ReductionPreprint
Wang, P., Liu, H., Pai, D., Yu, Y., Zhu, Z., Qu, Q., & Ma, Y. (2024) · arXiv (Cornell University) · doi:10.48550/arxiv.2406.01909 · Cited by 17
“These include low-rank matrix factorization [12, 46, 5, 60], community detection [50, 52], dictionary learning [45, 39], and deep neural networks [47, 55, 61, 62, 18, 27].”
Self-citationGradient-Based Algorithms for Zeroth-Order Optimization
Prashanth, L. A., & Bhatnagar, S. (2025) · Foundations and Trends® in Optimization · doi:10.1561/2400000047 · Cited by 16
Blind Data Detection in Massive MIMO via ℓ₃-Norm Maximization Over the Stiefel Manifold
Xue, Y., Shen, Y., Lau, V. K. N., Zhang, J., & Letaief, K. B. (2020) · IEEE Transactions on Wireless Communications · doi:10.1109/twc.2020.3033699 · Cited by 16
“To recover the k -th column of X H , we solve the following problem : where However, this method requires that the dictionary X must be a square matrix (complete) [30].”
MethodSimchowitz, M., Alaoui, A. E., & Recht, B. (2017) · arXiv (Cornell University) · doi:10.48550/arxiv.1704.04548 · Cited by 16
“As mentioned in the introduction, there has been a flurry of recent work establishing the efficacy and correctness of local search algorithms in numerous non-convex problems, including Dictionary Learning [11, 80], Matrix Factorization [15, 82, 85], Matrix Completion [40, 16], Phase Retrieval [18, 79, 22], and training n…”
BackgroundInfluentialThe loss landscape of deep linear neural networks: a second-order analysisPreprint
Achour, E. M., Malgouyres, F., & Gerchinovitz, S. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2107.13289 · Cited by 16
Quantization avoids saddle points in distributed optimization
Bo, Y., & Wang, Y. (2024) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.2319625121 · Cited by 15
Matrix Completion and Related Problems via Strong Duality
Balcan, M.-F., Liang, Y., Woodruff, D. P., & Zhang, H. (2017) · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · doi:10.4230/lipics.itcs.2018.5 · Cited by 15
Dictionary learning—from local towards global and adaptive
Pali, M., & Schnass, K. (2023) · Information and Inference A Journal of the IMA · doi:10.1093/imaiai/iaad008 · Cited by 15
On Collaborative Compressive Sensing Systems: The Framework, Design, and Algorithm
Zhu, Z., Li, G., Ding, J., Li, Q., & He, X. (2018) · SIAM Journal on Imaging Sciences · doi:10.1137/17m1148426 · Cited by 15
Manifold 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
“Compared to the sample complexityO(n(9)) required for learning complete dictionaries in [10], our result demonstrates the benefit of exploiting convolutional structures, which has a much lower sample complexity of O(n).”
BackgroundMethodInfluentialOnline ICA: Understanding Global Dynamics of Nonconvex Optimization via Diffusion ProcessesPreprint
Li, C. J., Wang, Z., & Liu, H. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1808.09642 · Cited by 15
Diffusion Approximations for Online Principal Component Estimation and Global ConvergencePreprint
Li, C. J., Wang, M., Liu, H., & Zhang, T. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1808.09645 · Cited by 15
Alternating minimization for dictionary learning: Local Convergence GuaranteesPreprint
Chatterji, N. S., & Bartlett, P. L. (2017) · arXiv (Cornell University) · doi:10.48550/arxiv.1711.03634 · Cited by 15
“[33] provide a Riemannian trust region method that can tolerate sparsity s = O(d), while earlier work by Spielman et al.”
On the Uniqueness and Stability of Dictionaries for Sparse Representation of Noisy Signals
Garfinkle, C. J., & Hillar, C. J. (2019) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2019.2935914 · Cited by 14
Time-Variation in Online Nonconvex Optimization Enables Escaping From Spurious Local Minima
Ding, Y., Lavaei, J., & Arcak, M. (2021) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2021.3135361 · Cited by 14
“Furthermore, it has been shown that nearly-isotropic classes of problems in matrix completion/sensing [30]–[32], robust principle component analysis [33], [34], and dictionary recovery [35] have benign landscape, implying that they are free of spurious local minima.”
BackgroundLuo, Y., & Trillos, N. G. (2026) · Mathematical Programming · doi:10.1007/s10107-026-02400-x · Cited by 14
Analysis of the Optimization Landscapes for Overcomplete Representation LearningPreprint
Qu, Q., Zhai, Y., Li, X., Zhang, Y., & Zhu, Z. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1912.02427 · Cited by 14
Self-citationOptimal Regularization for a Data Source
Leong, O., Reilly, E. O., Soh, Y. S., & Chandrasekaran, V. (2025) · Foundations of Computational Mathematics · doi:10.1007/s10208-025-09693-y · Cited by 13
“…learning, most prior work and performance guarantees analyze convergence guarantees of learning a synthetically generated, planted basis [1, 80, 81, 21], but these works do not consider the question of studying why a polyhedral regularizer is the “best choice” as a regularizer for a given…”
Local Geometry Determines Global Landscape in Low-Rank Factorization for Synchronization
Ling, S. (2025) · Foundations of Computational Mathematics · doi:10.1007/s10208-025-09707-9 · Cited by 13
“However, the solution is typically not equal to the ground truth [9, 66, 34], as shown in the examples such as angular synchronization [9, 66], orthogonal group synchronization [34], and generalized orthogonal Procrustes problem [35].”
Simple Alternating Minimization Provably Solves Complete Dictionary Learning
Liang, G., Zhang, G., Fattahi, S., & Zhang, R. Y. (2025) · SIAM Journal on Mathematics of Data Science · doi:10.1137/23m1568120 · Cited by 13
Chen, S., Deng, Z., Ma, S., & So, A. M. (2019) · Asilomar Conference on Signals, Systems and Computers (ACSSC) · doi:10.1109/ieeeconf44664.2019.9048840 · Cited by 13
“[11] suggested to replace the absolute value function |t| by hμ(t) = μ log(cosh(t/μ)), where μ > 0 is a smooth parameter, and then solve the smoothed problem by either Riemannian trustregion method [6], [7] or Riemannian gradient descent method [11].”
Leader Stochastic Gradient Descent for Distributed Training of Deep Learning ModelsPreprint
Teng, Y., Gao, W., Chalus, F., Choromanska, A., Goldfarb, D., & Weller, A. (2019) · arXiv (Cornell University) · Cited by 13
Zhang, G., Fattahi, S., & Zhang, R. Y. (2022) · arXiv (Cornell University) · doi:10.48550/arxiv.2206.03345 · Cited by 13
Riemannian trust-region methods for strict saddle functions with complexity guarantees
Goyens, F., & Royer, C. W. (2024) · Mathematical Programming · doi:10.1007/s10107-024-02156-2 · Cited by 12
“In this work, we consider a subset of problems with benign nonconvexity (see Definition 2.4), which focuses on problems with isolated minimizers.”
InfluentialLocal 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
Analysis of fast structured dictionary learning
Ravishankar, S., Ma, A., & Needell, D. M. (2019) · Information and Inference A Journal of the IMA · doi:10.1093/imaiai/iaz028 · Cited by 12
Nouiehed, M., & Razaviyayn, M. (2020) · SIAM Journal on Optimization · doi:10.1137/19m1256415 · Cited by 12
“Therefore, when applied to problems with “ nice ” geometrical properties, the set of second order stationary points could even coincide with the set of global optima – see [2, 3, 7, 33, 36, 20, 37, 38] for examples of such objective functions.”
BackgroundEscaping Spurious Local Minimum Trajectories in Online Time-varying Nonconvex Optimization
Ding, Y., Lavaei, J., & Arcak, M. (2021) · Proceedings of the ... American Control Conference/Proceedings of the American Control Conference · doi:10.23919/acc50511.2021.9483303 · Cited by 12
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
“Second, the complete dictionary learning problem can be converted into the orthogonal case through a simple preconditioning [21].”
BackgroundMethodInfluentialExtending the Step-Size Restriction for Gradient Descent to Avoid Strict Saddle Points
Schaeffer, H., & McCalla, S. G. (2020) · SIAM Journal on Mathematics of Data Science · doi:10.1137/19m129509x · Cited by 11
Identifiability of Complete Dictionary Learning
Cohen, J. E., & Gillis, N. (2019) · SIAM Journal on Mathematics of Data Science · doi:10.1137/18m1233339 · Cited by 11
“overy, and propose an efficient dictionary learning algorithm, referred to as Exact Recovery of Sparsely-Used Dictionaries (ER-SpUD). Other examples include a Riemannian trust-region method proposed in [34,35] which assumes Oprq zeros per column of B, a model based on tensor Tucker decompositions [4] which requires stru…”
MethodPersonalized Dictionary Learning for Heterogeneous Datasets
Liang, G., Shi, N., Kontar, R. A., & Fattahi, S. (2023) · neural information processing systems · doi:10.52202/075280-2213 · Cited by 11
Dictionary Learning With BLOTLESS Update
Yu, Q. J., Dai, W., Cvetković, Z., & Zhu, J. (2020) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2020.2971948 · Cited by 11
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
On the Complexity of Decentralized Smooth Nonconvex Finite-Sum OptimizationPreprint
Luo, L., Bai, Y., Chen, L., Liu, Y., & Ye, H. (2022) · arXiv (Cornell University) · doi:10.48550/arxiv.2210.13931 · Cited by 11
Differentially Private Linearized ADMM Algorithm for Decentralized Nonconvex Optimization
Yue, X.-Y., Xiao, J., Liu, X., & Wang, Y. (2025) · IEEE Transactions on Information Forensics and Security · doi:10.1109/tifs.2025.3550808 · Cited by 10
“This is demonstrated by results involving tensor decomposition [17], dictionary learning [44], smooth semidefinite programs [45], and robust principal component analysis [46].”
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
Escaping saddle points efficiently with occupation-time-adapted perturbations
Guo, X., Han, J., Tajrobehkar, M., & Tang, W. (2024) · Journal of Computational Mathematics and Data Science · doi:10.1016/j.jcmds.2024.100090 · Cited by 10
“…et al., 2015; 2018; Ge & Ma, 2017; Sanjabi et al., 2019), semidefinite programming (Bandeira et al., 2016; Mei et al., 2017), dictionary learning (Sun et al., 2017), phase retrieval (Sun et al., 2018), robust regression (Mei et al., 2018), low-rank matrix factorization (Bhojanapalli et al.,…”
BackgroundGeneralized Orthogonal Procrustes Problem under Arbitrary Adversaries
Ling, S. (2025) · SIAM Journal on Matrix Analysis and Applications · doi:10.1137/24m1631122 · Cited by 10
“…of the nonconvex objective function is benign under nearly identical conditions that enable the success of the SDR. Examples include phase retrieval [54], phase synchronization and community detection [35], orthogonal group synchronization [37], matrix completion [25] and dictionary learning [53].”
Non-Convex Matrix Completion and Related Problems via Strong Duality
Balcan, M.-F., Liang, Y., Song, Z., Woodruff, D. P., & Zhang, H. (2019) · Journal of Machine Learning Research · Cited by 10
Exact and Efficient Multi-Channel Sparse Blind Deconvolution — A Nonconvex Approach
Qu, Q., Li, X., & Zhu, Z. (2019) · Asilomar Conference on Signals, Systems and Computers (ACSSC) · doi:10.1109/ieeeconf44664.2019.9049053 · Cited by 10
“To alleviate this effect, we introduce a preconditioning matrix [7], [12], [13], defined as follows 8 P “ ˜ θnp ¸ which refines the function landscapes by orthogonalizing the circulant matrix C a : Next, we develop efficient first-order methods and provide guarantees for exact recovery.”
MethodSelf-citationDual Principal Component PursuitPreprint
Tsakiris, M. C., & Vidal, R. (2015) · arXiv (Cornell University) · doi:10.48550/arxiv.1510.04390 · Cited by 10
Preconditioned Gradient Descent for Over-Parameterized Nonconvex Matrix FactorizationPreprint
Zhang, G., Fattahi, S., & Zhang, R. Y. (2025) · arXiv (Cornell University) · doi:10.48550/arxiv.2504.09708 · Cited by 10
The Global Landscape of Phase Retrieval II: Quotient Intensity Models
Cai, J., Huang, M., Li, D., & Wang, Y. (2022) · Annals of Applied Mathematics · doi:10.4208/aam.oa-2021-0010 · Cited by 9
Multilinear 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.”
BackgroundMethodBilinear Dictionary Update via Linear Least Squares
Yu, Q. J., Dai, W., Cvetković, Z., & Zhu, J. (2019) · IEEE International Conference on Acoustics Speech and Signal Processing · doi:10.1109/icassp.2019.8682302 · Cited by 9
Hu, X., & Liu, X. (2020) · Sensors · doi:10.3390/s20113041 · Cited by 9
“There are also some approaches using smoothing techniques to approximate the `1-norm term such as Logcosh [8,33], Huber loss [34], pseudo-Huber [5], etc.”
MethodInfluentialNonnegative Bounded Convolutional Sparse Learning Method for Envelope Feature Deconvolution
Du, Z., Chen, X., Zhang, H., & Yang, Y. (2020) · IEEE Transactions on Instrumentation and Measurement · doi:10.1109/tim.2020.2998564 · Cited by 9
“Fortunately, for dictionary learning model (NBconvSLM is its one special instance), there are no spurious local minimizers and all local minimizers are the permutations of the optimal solutions [45], which makes the proposed model amenable to ADMM optimization framework.”
BackgroundLearning Polynomial Transformations via Generalized Tensor Decompositions
Chen, S., Li, J. Z., Li, Y., & Zhang, A. R. (2023) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/3564246.3585209 · Cited by 9
Learning Semidefinite Regularizers
Soh, Y. S., & Chandrasekaran, V. (2018) · Foundations of Computational Mathematics · doi:10.1007/s10208-018-9386-z · Cited by 9
“To build support for this idea, several researchers have proven that random initialization succeeds with high probability in recovering a desired factorization under suitable conditions in a number of problems [29,58], including in a restricted form of dictionary learning [59,60] in which the polyhedral regularizer is…”
BackgroundOn the Absence of Spurious Local Trajectories in Time-Varying Nonconvex Optimization
Fattahi, S., Josz, C., Ding, Y., Mohammadi-Ghazi, R., Lavaei, J., & Sojoudi, S. (2021) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2021.3137147 · Cited by 9
“Inparticular,ithasbeenshownthatnearlyisotropic classesofproblemsinmatrixcompletion/sensing[9],[10],[17], robustprinciplecomponentanalysis[12],[18],anddictionary recovery[19]havebenignlandscape,implyingthattheyarefree ofspuriouslocalminima.”
Adaptive-Size Dictionary Learning Using Information Theoretic Criteria
Dumitrescu, B., & Giurcăneanu, C. D. (2019) · Algorithms · doi:10.3390/a12090178 · Cited by 9
Escaping Saddle Points for Nonsmooth Weakly Convex Functions via Perturbed Proximal AlgorithmsPreprint
Huang, M., & Zhu, W. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2102.02837 · Cited by 9
Identifiable Shared Component Analysis of Unpaired Multimodal Mixtures
Timilsina, S., Shrestha, S., & Fu, X. (2024) · neural information processing systems · doi:10.52202/079017-4058 · Cited by 8
The Global Landscape of Phase Retrieval I: Perturbed Amplitude Models
Cai, J., Huang, M., Li, D., & Wang, Y. (2021) · Annals of Applied Mathematics · doi:10.4208/aam.oa-2021-0009 · Cited by 8
Three Proofs of the Benedetto–Fickus Theorem
Mixon, D. G., Needham, T., Shonkwiler, C., & Villar, S. (2023) · Applied and numerical harmonic analysis · doi:10.1007/978-3-031-41130-4_14 · Cited by 8
“…last decade of research has centered around analyzing non-convex landscapes for optimization in various settings, such as orthogonal tensor decomposition [15], the Burer–Monteiro method [6], dictionary learning [31], matrix completion [16], phase retrieval [32], and neural network training [23].”
Escaping Saddle Points for Zeroth-order Non-convex Optimization using Estimated Gradient Descent
Bai, Q., Agarwal, M., & Aggarwal, V. (2020) · Conference on Information Sciences and Systems · doi:10.1109/ciss48834.2020.1570627382 · Cited by 8
Absence of Spurious Local Trajectories in Time-Varying Optimization: A Control-Theoretic Perspective
Fattahi, S., Josz, C., Mohammadi-Ghazi, R., Lavaei, J., & Sojoudi, S. (2020) · IEEE Conference on Control Technology and Applications (CCTA) · doi:10.1109/ccta41146.2020.9206163 · Cited by 8
Absence of spurious local trajectories in time-varying optimizationPreprint
Fattahi, S., Josz, C., Mohammadi-Ghazi, R., Lavaei, J., & Sojoudi, S. (2019) · arXiv (Cornell University) · Cited by 8
Unique Sparse Decomposition of Low Rank Matrices
Jin, D., Bing, X., & Zhang, Y. (2022) · IEEE Transactions on Information Theory · doi:10.1109/tit.2022.3223230 · Cited by 7
A Randomized Algorithm for Nonconvex Minimization With Inexact Evaluations and Complexity Guarantees
Li, S., & Wright, S. J. (2025) · Journal of Optimization Theory and Applications · doi:10.1007/s10957-025-02817-y · Cited by 7
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
A 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
“More generally, under the strict-saddle property, a number of saddle-escaping algorithms [5, 14, 33] converge to the global solution in polynomial time; see e.g., [6, 7, 16, 25, 26, 40, 47, 48, 59, 62, 64].”
Compressed Dictionary Learning
Schnass, K., & Teixeira, F. C. A. (2020) · Journal of Fourier Analysis and Applications · doi:10.1007/s00041-020-09738-6 · Cited by 7
“Since the seminal paper by Olshausen and Field, [11], a plethora of dictionary learning algorithms have emerged, see [3], [10], [21], [23], [25], [36], [24], [26], and also theory on the problem has become available, [15], [38], [7], [2], [32], [33], [14], [8], [6], [35], [39], [40].”
BackgroundA Comprehensive Study on Optimization Strategies for Gradient Descent In Deep LearningPreprint
Yadav, K. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2101.02397 · Cited by 7
“Fortunately, we can sort of rule out local minima as they give quite satisfactory results, this was proved for many cases including dictionary learning [12], matrix completion [13], tensor decomposition [14], and some cases of deep learning [15].”
Last-Iterate Convergence of Adaptive Riemannian Gradient Descent for Equilibrium ComputationPreprint
Cai, Y., Jordan, M. I., Lin, T., Oikonomou, A., & Vlatakis-Gkaragkounis, E.-V. (2023) · arXiv (Cornell University) · doi:10.48550/arxiv.2306.16617 · Cited by 7
“…serves as an abstraction for many machine learning applications, including principal component analysis [Boumal and Absil, 2011], dictionary learning [Sun et al., 2016a,b], deep neural networks [Huang et al., 2018], and low-rank matrix learning [Vandereycken, 2013, Jawanpuria and Mishra, 2018].”
Wu, S., & Yu, B. (2015) · arXiv (Cornell University) · doi:10.48550/arxiv.1505.04363 · Cited by 7
Complete dictionary learning via ℓp-norm maximization
Shen, Y., Xue, Y., Zhang, J., Letaief, K. B., & Lau, V. K. N. (2020) · Rare & Special e-Zone (The Hong Kong University of Science and Technology) · Cited by 6
On the Global Geometry of Sphere-Constrained Sparse Blind Deconvolution
Zhang, Y., Lau, Y., Kuo, H.-W., Cheung, S. C., Pasupathy, A. N., & Wright, J. N. (2019) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2019.2939237 · Cited by 6
“This is motivated in part by [23], which demonstrates that a certain formulation of the dictionary learning problem over the sphere has no spurious local minimizers, even for relatively dense target representations.”
BackgroundInfluentialSelf-citationEfficient 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
Zeroth-order Optimization on Riemannian Manifolds
Li, J., Balasubramanian, K., & Ma, S. (2020) · Cited by 6
Ghosh, A., Maity, R. K., Mazumdar, A., & Ramchandran, K. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2103.09424 · Cited by 6
“In fact, in many problems of interest, all local minima are global minima (e.g., dictionary learning Sun et al. (2017), phase retrieval Sun et al. (2016), matrix sensing and completion Bhojanapalli et al. (2016); Ge et al. (2017), and some of neural nets Kawaguchi (2016)).”
A Complete Loss Landscape Analysis of Regularized Deep Matrix Factorization
Chen, P., Jiang, R., & Wang, P. (2026) · SIAM Journal on Optimization · doi:10.1137/25m1777578 · Cited by 5
Optimal vintage factor analysis with deflation varimax
Bing, X., He, X., Jin, D., & Zhang, Y. (2025) · The Annals of Statistics · doi:10.1214/25-aos2518 · Cited by 5
A Geometric Approach to $k$k-Means Clustering
Hong, J., Qian, W., Chen, Y., & Zhang, Y. (2025) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2025.3616858 · Cited by 5
“Onthe theory side, recent years have witnessed exciting progress on demystifying the structure of local solutions in certain nonconvex problems [11], [12], [13], [14], [15], [16], [17], [18], including k -means and related clustering problems.”
Spectral 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
Conditions for Exact Convex Relaxation and No Spurious Local Optima
Zhou, F., & Low, S. H. (2021) · IEEE Transactions on Control of Network Systems · doi:10.1109/tcns.2021.3112758 · Cited by 5
“This technique or idea were also used in [16] for dictionary recovery problem and [17] for phase synchronization.”
MethodBehind the Scenes of Gradient Descent: A Trajectory Analysis via Basis Function DecompositionPreprint
Ma, J., Guo, L., & Fattahi, S. (2022) · arXiv (Cornell University) · doi:10.48550/arxiv.2210.00346 · Cited by 5
Smooth Quasar-Convex Optimization with ConstraintsPreprint
Martínez-Rubio, D. (2025) · arXiv (Cornell University) · doi:10.48550/arxiv.2510.01943 · Cited by 5
“Besides, it has been shown that all local minimizers are global in a number of machine learning tasks such as problems in phase retrieval (Sun, Qu, and Wright, 2018), tensor decomposition (Ge, Huang, et al., 2015), dictionary learning (Sun, Qu, and Wright, 2017), matrix sensing (Bhojanapalli,…”
A New Inexact Manifold Proximal Linear Algorithm with Adaptive Stopping CriteriaPreprint
Zheng, Z., Yu, X., Ma, S., & Xue, L. (2025) · arXiv (Cornell University) · doi:10.48550/arxiv.2508.19234 · Cited by 5
“Examples include sparse principal component analysis (SPCA) [1–3], fair PCA [4–6], sparse canonical correlation analysis (SCCA) [7–9], sparse spectral clustering (SSC) [10–12], orthogonal dictionary learning [13–17], and beamforming design [18].”
SPEAR++: Scaling Gradient Inversion via Sparsely-Used Dictionary LearningPreprint
Bakarsky, A., Dimitrov, D. I., Baader, M., & Vechev, M. (2025) · arXiv (Cornell University) · doi:10.48550/arxiv.2510.24200 · Cited by 5
“We lean on the insights of Sun et al. [20] that the problem is amenable to efficient non-convex optimization via loss relaxation and leverage first-order optimization procedures to recover the sparse columns of the matrix ∂ L ∂Z .”
Convergence Regions of Alternating Minimization Algorithms for Dictionary Learning
Ruetz, S., & Schnass, K. (2026) · SIAM Journal on Optimization · doi:10.1137/23m1575469 · Cited by 4
Asymptotic Proximal Point Methods for Global Optimization
Luo, X., Xu, X., & Rabitz, H. (2025) · Journal of Scientific Computing · doi:10.1007/s10915-025-03119-1 · Cited by 4
“The trust region techniques [35, 36] can also avoid saddle points and are not limited to strict saddle points, but generally, the perturbed gradient method is more efficient in practice.”
Metadata
- Authors
- Sun, J., Qu, Q., & Wright, J.
- Affiliations
- Columbia University (US)
- Venue
- IEEE Transactions on Information Theory
- Published
- 2017-02
- Volume
- 63
- Issue
- 2
- Pages
- 853-884
- ISSN
- 0018-9448 (ISSN-L)
- 1557-9654
- OpenAlex
- W2601846890
- Cited by
- 213
- References
- 174
- Citations by year
- 2026: 4 · 2025: 9 · 2024: 12 · 2023: 12 · 2022: 9 · 2021: 37 · 2020: 39 · 2019: 54 · 2018: 19 · 2017: 12
- FWCI
- 25.96
- Type
- journal article
- Language
- en
- Open access
- green
- arxiv.org
- Licence
- Locations
- IEEE Transactions on Information Theory (publishedVersion)
- arXiv (Cornell University) (submittedVersion)
- arXiv (Cornell University)
- Funders
- ONR (N00014-13-1-0492)
- NSF (1343282, CCF 1527809, IIS 1546411)
- Moore and Sloan Foundations
- Topics
- Physical Sciences › Computer Science › Signal Processing › Sparse and Compressive Sensing Techniques
- Physical Sciences › Mathematics › Statistics and Probability › Statistical Methods and Inference
- Physical Sciences › Computer Science › Computer Vision and Pattern Recognition › Image and Signal Denoising Methods
- Keywords
- dictionary learning, sparse representation, matrix recovery, spherical constraint, non-convex optimization, saddle points, directional curvature, trust region method
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.