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
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
“…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…”
BackgroundHow to escape saddle points efficiently
Jin, C., Ge, R., Netrapalli, P., Kakade, S. M., & Jordan, M. I. (2017) · International Conference on Machine Learning · Cited by 750
First-order methods almost always avoid strict saddle points
Lee, J. D., Panageas, I., Piliouras, G., Simchowitz, M., Jordan, M. I., & Recht, B. (2019) · Mathematical Programming · doi:10.1007/s10107-019-01374-3 · Cited by 377
Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
Chi, Y., Lu, Y. M., & Chen, Y. (2019) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2019.2937282 · Cited by 360
Global Optimality Guarantees for Policy Gradient Methods
Bhandari, J., & Russo, D. (2024) · Operations Research · doi:10.1287/opre.2021.0014 · Cited by 305
An Analysis of the t-SNE Algorithm for Data VisualizationPreprint
Arora, S., Hu, W. P., & Kothari, P. K. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1803.01768 · Cited by 289
“Researchers have managed to rigorously analyze non-convex optimization algorithms in a host of settings (Dasgupta, 1999; Arora et al., 2012, 2014; Bhojanapalli et al., 2016; Ge et al., 2015a; Sun et al., 2017; Ge et al., 2017, 2016; Park et al., 2017).”
BackgroundGradient Descent Can Take Exponential Time to Escape Saddle PointsPreprint
Du, S. S., Jin, C., Lee, J. D., Jordan, M. I., Póczos, B., & Singh, A. (2017) · arXiv (Cornell University) · doi:10.48550/arxiv.1705.10412 · Cited by 267
“These properties hold for a variety of machine learning problems, including tensor decomposition [Ge et al., 2015], dictionary learning [Sun et al., 2017], phase retrieval [Sun et al., 2016], matrix sensing [Bhojanapalli et al., 2016, Park et al., 2017], matrix completion [Ge et al., 2016, 2017],…”
BackgroundOn Nonconvex Optimization for Machine Learning: Gradients, Stochasticity, and Saddle Points
Jin, C., Netrapalli, P., Ge, R., Kakade, S. M., & Jordan, M. I. (2021) · Journal of the ACM · doi:10.1145/3418526 · Cited by 260
“underlying global geometry that these problems have in common. Problems for which second-order stationary points are global minima include tensor decomposition [Ge et al.,2015], dictionary learning [Sun et al., 2016a], phase retrieval [Sun et al., 2016b], synchronization and MaxCut [Bandeira et al., 2016, Mei et al.,…”
BackgroundOptimistic mirror descent in saddle-point problems: Going the extra (gradient) milePreprint
Mertikopoulos, P., Lecouat, B., Zenati, H., Foo, C.-S., Chandrasekhar, V., & Piliouras, G. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1807.02629 · Cited by 236
“…property was shown to hold in a wide range of salient objective functions ranging from low-rank matrix factorization (Bhojanapalli et al., ; Ge et al., , ) and dictionary learning (Sun et al., ,b), to principal component analysis (Ge et al., ), phase retrieval (Sun et al., ), and many other models.”
BackgroundA Geometric Analysis of Neural Collapse with Unconstrained FeaturesPreprint
Zhu, Z., Ding, T., Zhou, J., Li, X., You, C., Sulam, J., & Qu, Q. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2105.02375 · Cited by 229
“These problems include, but are not limited to, phase retrieval [86,87], low-rank matrix recovery [78,82,85,88,90], dictionary learning [80,83,84,91,96], and sparse blind deconvolution [92–95].”
BackgroundSelf-citationHow to Escape Saddle Points Efficiently
Jin, C., Ge, R., Netrapalli, P., Kakade, S. M., & Jordan, M. I. (2017) · arXiv (Cornell University) · doi:10.48550/arxiv.1703.00887 · Cited by 205
“On the other hand, saddle points (and local maxima) can correspond to highly suboptimal solutions in many problems [see, e.g., Jain et al., 2015, Sun et al., 2016b].”
BackgroundInfluentialProximal Gradient Method for Nonsmooth Optimization over the Stiefel Manifold
Chen, S., Ma, S., So, A. M., & Zhang, T. (2020) · SIAM Journal on Optimization · doi:10.1137/18m122457x · Cited by 205
Ma, C., Wang, K., Chi, Y., & Chen, Y. (2020) · Foundations of Computational Mathematics · doi:10.1007/s10208-019-09429-9 · Cited by 204
No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysis
Ge, R., Jin, C., & Zheng, Y. (2017) · arXiv (Cornell University) · doi:10.48550/arxiv.1704.00708 · Cited by 199
Gradient Descent Converges to Minimizers
Lee, J. D., Simchowitz, M., Jordan, M. I., & Recht, B. (2016) · arXiv (Cornell University) · doi:10.48550/arxiv.1602.04915 · Cited by 103
Gradient Descent Learns One-hidden-layer CNN: Don't be Afraid of Spurious Local MinimaPreprint
Du, S. S., Lee, J. D., Tian, Y., Póczos, B., & Singh, A. (2017) · arXiv (Cornell University) · doi:10.48550/arxiv.1712.00779 · Cited by 195
“…analyses, these algorithmic results have shown a large number problems, including tensor decomposition [Ge et al., 2015], dictionary learning [Sun et al., 2017], phase retrieval [Sun et al., 2016], matrix sensing [Bhojanapalli et al., 2016, Park et al., 2017], matrix completion [Ge et al.,…”
BackgroundGlobal Optimality in Low-Rank Matrix Optimization
Zhu, Z., Li, Q., Tang, G., & Wakin, M. B. (2018) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2018.2835403 · Cited by 174
Non-square matrix sensing without spurious local minima via the Burer-Monteiro approachPreprint
Park, D., Kyrillidis, A., Caramanis, C., & Sanghavi, S. (2016) · arXiv (Cornell University) · doi:10.48550/arxiv.1609.03240 · Cited by 173
Adaptive Interference Removal for Uncoordinated Radar/Communication Coexistence
Zheng, L., Lops, M., & Wang, X. (2017) · IEEE Journal of Selected Topics in Signal Processing · doi:10.1109/jstsp.2017.2785783 · Cited by 155
Stochastic Cubic Regularization for Fast Nonconvex OptimizationPreprint
Tripuraneni, N., Stern, M., Jin, C., Regier, J., & Jordan, M. I. (2017) · arXiv (Cornell University) · doi:10.48550/arxiv.1711.02838 · Cited by 155
Complete Dictionary Recovery Over the Sphere II: Recovery by Riemannian Trust-Region Method
Sun, J., Qu, Q., & Wright, J. (2017) · IEEE Transactions on Information Theory · doi:10.1109/tit.2016.2632149 · Cited by 112
Self-citationSharp Analysis for Nonconvex SGD Escaping from Saddle PointsPreprint
Fang, C., Lin, Z., & Zhang, T. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1902.00247 · Cited by 115
“…such as principal component analysis (Li et al., 2018a; Jain & Kar, 2017), matrix completion (Jain et al., 2013; Ge et al., 2016; Sun & Luo, 2016), dictionary learning (Sun et al., 2015, 2017) as well as linear and nonlinear neural networks (Zhong et al., 2017; Li & Yuan, 2017; Li et al., 2018b).”
BackgroundMethodWeakly Convex Optimization over Stiefel Manifold Using Riemannian Subgradient-Type Methods
Li, X., Chen, S., Deng, Z., Qu, Q., Zhu, Z., & So, A. M. (2021) · SIAM Journal on Optimization · doi:10.1137/20m1321000 · Cited by 110
“, square and invertible) dictionaries via preconditioning [54,66].”
BackgroundSelf-citationThe Global Optimization Geometry of Low-Rank Matrix Optimization
Zhu, Z., Li, Q., Tang, G., & Wakin, M. B. (2021) · IEEE Transactions on Information Theory · doi:10.1109/tit.2021.3049171 · Cited by 101
Dynamics of Deep Neural Networks and Neural Tangent HierarchyPreprint
Huang, J., & Yau, H. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1909.08156 · Cited by 99
“A line of recent results show that, in many optimization problems of interest [7, 15, 16, 33, 40, 41], loss landscapes are in such class.”
ResultOn the Landscape of Synchronization Networks: A Perspective from Nonconvex Optimization
Ling, S., Xu, R., & Bandeira, A. S. (2019) · SIAM Journal on Optimization · doi:10.1137/18m1217644 · Cited by 97
“Nonconvex optimization plays a crucial role in the mathematics of signal processing [7, 13, 29, 42, 43, 44, 50], statistics [12, 33], and machine learning [14, 20, 21, 39, 45], and has attracted substantial attention in the past few years.”
BackgroundGao, X., Gürbüzbalaban, M., & Zhu, L. (2021) · Operations Research · doi:10.1287/opre.2021.2162 · Cited by 96
Blind Signal Detection in Massive MIMO: Exploiting the Channel Sparsity
Zhang, J., Yuan, X., & Zhang, Y. A. (2017) · IEEE Transactions on Communications · doi:10.1109/tcomm.2017.2761384 · Cited by 95
Multi-Target Position and Velocity Estimation Using OFDM Communication Signals
Li, Y., Wang, X., & Ding, Z. (2019) · IEEE Transactions on Communications · doi:10.1109/tcomm.2019.2956928 · Cited by 94
“m=1 ρ 2 T(P(Um))−Um (2)F , and approximate the 1-norm by a twice continuously differentiable function [44] e 1 ≈ φ (e)”
BackgroundComplete dictionary recovery over the sphere
Sun, J., Qu, Q., & Wright, J. N. (2015) · International Conference on Sampling Theory and Applications · doi:10.1109/sampta.2015.7148922 · Cited by 86
Self-citationLi, J., So, A. M., & Ma, W. (2020) · IEEE Signal Processing Magazine · doi:10.1109/msp.2020.3003845 · Cited by 82
“There are many other applications whose natural optimization formulations are non-convex yet highly structured, such as dictionary learning [14], [15], non-negative matrix factorization [16], [17], and phase retrieval [18], [19].”
BackgroundLiu, H., So, A. M., & Wu, W. (2018) · Mathematical Programming · doi:10.1007/s10107-018-1285-1 · Cited by 79
“This approach has been employed to study a wide variety of structured non-convex optimization problems, including dictionary learning [5,49,50], matrix completion and sensing [16,51,60], phase retrieval [10,34,48], phase synchronization [26,61], and tensor decomposition and factorization [18,52].”
MethodAn Unconstrained Layer-Peeled Perspective on Neural CollapsePreprint
Ji, W., Lu, Y., Zhang, Y., Deng, Z., & Su, W. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2110.02796 · Cited by 79
“Examples include phase retrieval (Sun et al., 2018), low-rank matrix recovery (Ge et al., 2016; 2015), dictionary learning (Sun et al., 2016; Qu et al., 2019; Laurent & Brecht, 2018) and blind deconvolution (Lau et al., 2019).”
BackgroundSpectral Compressed Sensing via Projected Gradient Descent
Cai, J., Wang, T., & Wei, K. (2018) · SIAM Journal on Optimization · doi:10.1137/17m1141394 · Cited by 74
“Recently, a line of research work has been devoted to the geometric analysis of non-convex optimization problems including dictionary learning [39], phase retrieval [40], low rank matrix sensing and matrix completion [1, 35, 24, 23], tensor completion [22] and robust PCA [23].”
BackgroundCardinality Minimization, Constraints, and Regularization: A Survey
Tillmann, A. M., Bienstock, D., Lodi, A., & Schwartz, A. (2024) · SIAM Review · doi:10.1137/21m142770x · Cited by 73
Provable Representation Learning for Imitation Learning via Bi-level OptimizationPreprint
Arora, S., Du, S. S., Kakade, S. M., Luo, Y., & Saunshi, N. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2002.10544 · Cited by 73
“Imitation learning can help with sample efficiency of many problems (Ross & Bagnell, 2010; Sun et al., 2017; Daumé et al., 2009; Chang et al., 2015; Pan et al., 2018).”
BackgroundA Clustering Approach to Learning Sparsely Used Overcomplete Dictionaries
Agarwal, A., Anandkumar, A., & Netrapalli, P. (2016) · IEEE Transactions on Information Theory · doi:10.1109/tit.2016.2614684 · Cited by 72
Neural Collapse with Normalized Features: A Geometric Analysis Over the Riemannian Manifold
Yaras, C., Wang, P., Zhu, Z., Balzano, L., & Qu, Q. (2022) · neural information processing systems · doi:10.52202/068431-0839 · Cited by 70
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 67
Self-citationAlternating Minimizations Converge to Second-Order Optimal Solutions
Li, Q., Zhu, Z., & Tang, G. (2019) · International Conference on Machine Learning · Cited by 66
ADMM for multiaffine constrained optimization
Gao, W., Goldfarb, D., & Curtis, F. E. (2019) · Optimization methods & software · doi:10.1080/10556788.2019.1683553 · Cited by 64
“For more information on dictionary learning, see [18, 50, 51, 43, 56].”
BackgroundFirst-order methods almost always avoid saddle points: the case of vanishing step-sizesPreprint
Panageas, I., Piliouras, G., & Wang, X. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1906.07772 · Cited by 64
A Newton-Based Method for Nonconvex Optimization with Fast Evasion of Saddle Points
Paternain, S., Mokhtari, A., & Ribeiro, A. (2019) · SIAM Journal on Optimization · doi:10.1137/17m1150116 · Cited by 62
“an be reduced to the minimization of nonconvex functions [25]. Despite this general complexity, some recent results have shown that for a large class of nonconvex problems such as dictionary learning [30], tensor decomposition [12], matrix completion [13], and training of some specific forms of neural networks [17], al…”
BackgroundEfficiently escaping saddle points on manifoldsPreprint
Criscitiello, C., & Boumal, N. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1906.04321 · Cited by 62
“See [14] and [25] for examples of the strict saddle property on manifolds.”
BackgroundRegularized gradient descent: a non-convex recipe for fast joint blind deconvolution and demixing
Ling, S., & Strohmer, T. (2019) · Information and Inference: A Journal of the IMA · doi:10.1093/imaiai/iax022 · Cited by 47
Towards Riemannian Accelerated Gradient MethodsPreprint
Zhang, H., & Sra, S. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1806.02812 · Cited by 60
DYNAMICAL, SYMPLECTIC AND STOCHASTIC PERSPECTIVES ON GRADIENT-BASED OPTIMIZATION
Jordan, M. I. (2019) · International Congress of Mathematicians (ICM) · doi:10.1142/9789813272880_0022 · Cited by 58
Stochastic Zeroth-Order Riemannian Derivative Estimation and Optimization
Li, J., Balasubramanian, K., & Ma, S. (2022) · Mathematics of Operations Research · doi:10.1287/moor.2022.1302 · Cited by 57
Scalable Solvers of Random Quadratic Equations via Stochastic Truncated Amplitude Flow
Wang, G., Giannakis, G. B., & Chen, J. (2017) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2017.2652392 · Cited by 55
Zhou, J., Li, X., Ding, T., You, C., Qu, Q., & Zhu, Z. (2022) · arXiv (Cornell University) · doi:10.48550/arxiv.2203.01238 · Cited by 55
Self-citationRobust PCA by Manifold OptimizationPreprint
Zhang, T., & Yang, Y. (2017) · arXiv (Cornell University) · doi:10.48550/arxiv.1708.00257 · Cited by 54
A Riemannian Alternating Direction Method of Multipliers
Li, J., Ma, S., & Srivastava, T. (2024) · Mathematics of Operations Research · doi:10.1287/moor.2023.0068 · Cited by 51
Super-Resolution mmWave Channel Estimation for Generalized Spatial Modulation Systems
Chu, H., Zheng, L., & Wang, X. (2019) · IEEE Journal of Selected Topics in Signal Processing · doi:10.1109/jstsp.2019.2918481 · Cited by 51
“Moreover, since ‖ · ‖1 in the objective function is non-smooth, we approximate it with [49]”
BackgroundEscaping Saddle Points in Constrained OptimizationPreprint
Mokhtari, A., Ozdaglar, A., & Jadbabaie, A. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1809.02162 · Cited by 51
“act that for certain nonconvex problems, all local minimizers are global. These include, for example, matrix completion (Ge et al., 2016), phase retrieval (Sun et al., 2016), and dictionary learning (Sun et al., 2017). For such problems, finding the global minimum of (1) reduces to the problem of finding one of its loca…”
BackgroundScaling 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
Revisiting Sparse Convolutional Model for Visual Recognition
Dai, X., Li, M., Zhai, P., Tong, S., Gao, X., Huang, S., Zhu, Z., You, C., & Ma, Y. (2022) · neural information processing systems · doi:10.52202/068431-0762 · Cited by 46
The Global Optimization Geometry of Shallow Linear Neural Networks
Zhu, Z., Soudry, D., Eldar, Y. C., & Wakin, M. B. (2019) · Journal of Mathematical Imaging and Vision · doi:10.1007/s10851-019-00889-w · Cited by 45
Chen, S., Ma, S., Xue, L., & Zou, H. (2020) · INFORMS Journal on Optimization · doi:10.1287/ijoo.2019.0032 · Cited by 44
Ling, S. (2022) · Mathematical Programming · doi:10.1007/s10107-022-01896-3 · Cited by 42
Opinion Dynamics Optimization by Varying Susceptibility to Persuasion via Non-Convex Local Search
Abebe, R., Chan, T.-H. H., Kleinberg, J. M., Liang, Z., Parkes, D. C., Sozio, M., & Tsourakakis, C. E. (2021) · ACM Transactions on Knowledge Discovery from Data · doi:10.1145/3466617 · Cited by 42
Fast and Guaranteed Blind Multichannel Deconvolution Under a Bilinear System Model
Lee, K., Tian, N., & Romberg, J. (2018) · IEEE Transactions on Information Theory · doi:10.1109/tit.2018.2840711 · Cited by 41
“Dictionary learning is another bilinear problem arising in numerous applications; convergence of a Riemannian trust-region method for this problem has been studied with a thorough geometric analysis in [42] and [43].”
MethodDecentralized nonconvex optimization with guaranteed privacy and accuracy
Wang, Y., & Başar, T. (2023) · Automatica · doi:10.1016/j.automatica.2023.110858 · Cited by 40
Convolutional Phase Retrieval via Gradient Descent
Qu, Q., Zhang, Y., Eldar, Y. C., & Wright, J. N. (2019) · IEEE Transactions on Information Theory · doi:10.1109/tit.2019.2950717 · Cited by 40
Self-citationConvergence to Second-Order Stationarity for Constrained Non-Convex OptimizationPreprint
Nouiehed, M., Lee, J. D., & Razaviyayn, M. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1810.02024 · Cited by 40
“This property is satisfied in many practical objective functions; see [18, 25, 38, 39, 40].”
BackgroundUnderstanding Deep Representation Learning via Layerwise Feature Compression and DiscriminationPreprint
Wang, P., Xiao, L., Yaras, C. B., Zhu, Z., Balzano, L., Hu, W., & Qu, Q. (2023) · arXiv (Cornell University) · doi:10.48550/arxiv.2311.02960 · Cited by 39
Self-citationSolving phase retrieval with random initial guess is nearly as good as by spectral initialization
Cai, J., Huang, M., Li, D., & Wang, Y. (2022) · Applied and Computational Harmonic Analysis · doi:10.1016/j.acha.2022.01.002 · Cited by 38
Fu, X., Vervliet, N., Lathauwer, L. D., Huang, K., & Gillis, N. (2020) · IEEE Signal Processing Magazine · doi:10.1109/msp.2020.3003544 · Cited by 38
“Consequently, a globally optimal solution can be attained via nonconvex optimization methods [66].”
BackgroundNonconvex Demixing From Bilinear Measurements
Dong, J., & Shi, Y. (2018) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2018.2864660 · Cited by 37
“The successful examples include matrix sensing [17], matrix completion [18], dictionary learning [19], tensor decomposition [20], synchronization problem [21] and learning shallow neural networks [22].”
Geometric Analysis of Nonconvex Optimization Landscapes for Overcomplete Learning
Qu, Q., Zhai, Y., Xiao, L., Zhang, Y., & Zhu, Z. (2020) · International Conference on Learning Representations · Cited by 35
Self-citationJana, D., & Nagarajaiah, S. (2022) · Engineering Structures · doi:10.1016/j.engstruct.2022.115280 · Cited by 35
Sparse Personalized Federated Learning
Liu, X., Li, Y., Wang, Q., Zhang, X., Shao, Y., & Geng, Y. (2023) · IEEE Transactions on Neural Networks and Learning Systems · doi:10.1109/tnnls.2023.3250658 · Cited by 35
“To start with, we use a twice continuously differentiable approximation to replace the ℓ 1 -norm used in FedMac , i.e., replacing ∥ x ∥ 1 by [33] x n ρ where x n is the n th element in x and ρ is a weight parameter, which controls the smoothing level.”
MethodFinding Second-Order Stationary Points in Nonconvex-Strongly-Concave Minimax Optimization
Luo, L., Li, Y., & Chen, C. (2022) · neural information processing systems · doi:10.52202/068431-2657 · Cited by 35
“Under mild strict saddle condition [3, 10, 11, 34, 35], the approximate SSP of P ( x ) implies an approximate local minimax point of f ( x , y ) defined by Jin et al. [17], which successfully characterizes the local optimality for problem (1).”
BackgroundMethodSPEAR: Exact Gradient Inversion of Batches in Federated Learning
Dimitrov, D. I., Baader, M., Müller, M. N., & Vechev, M. (2024) · neural information processing systems · doi:10.52202/079017-3390 · Cited by 34
Hitting Time of Stochastic Gradient Langevin Dynamics to Stationary Points: A Direct AnalysisPreprint
Chen, X., Du, S., & Tong, X. T. (2019) · arXiv.org · doi:10.48550/arxiv.1904.13016 · Cited by 2
“Examples include matrix factorization, neural networks, dictionary learning, e.t.c. (Hardt and Ma, 2016; Ge et al., 2015; Sun et al., 2017; Ge et al., 2017; Park et al., 2017; Bhojanapalli et al., 2016; Du and Lee, 2018; Du et al., 2018a; Ge et al., 2018; Du et al., 2018b; Mei et al., 2017).”
BackgroundLikelihood landscape and maximum likelihood estimation for the discrete orbit recovery model
Fan, Z., Sun, Y. J., Wang, T., & Wu, Y. (2021) · Communications on Pure and Applied Mathematics · doi:10.1002/cpa.22032 · Cited by 31
Exact 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
Self-citationHeavy-ball Algorithms Always Escape Saddle Points
Sun, T., Li, D., Quan, Z., Jiang, H., Li, S., & Dou, Y. (2019) · International Joint Conference on Artificial Intelligence · doi:10.24963/ijcai.2019/488 · Cited by 31
From the simplex to the sphere: faster constrained optimization using the Hadamard parametrization
Li, Q., McKenzie, D. H., & Yin, W. (2023) · Information and Inference A Journal of the IMA · doi:10.1093/imaiai/iaad017 · Cited by 29
Rayleigh quotient minimization for absolutely one-homogeneous functionals
Feld, T., Aujol, J., Gilboa, G., & Papadakis, N. (2019) · Inverse Problems · doi:10.1088/1361-6420/ab0cb2 · Cited by 29
Blind Gain and Phase Calibration via Sparse Spectral Methods
Li, Y., Lee, K., & Bresler, Y. (2018) · IEEE Transactions on Information Theory · doi:10.1109/tit.2018.2883623 · Cited by 29
Short-and-Sparse Deconvolution -- A Geometric ApproachPreprint
Lau, Y., Qu, Q., Kuo, H.-W., Zhou, P., Zhang, Y., & Wright, J. N. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1908.10959 · Cited by 29
Self-citationWang, Z., Liu, B., Chen, S., Ma, S., Xue, L., & Zhao, H. (2021) · INFORMS Journal on Optimization · doi:10.1287/ijoo.2021.0064 · Cited by 28
Alternating minimization for dictionary learning with random initializationPreprint
Chatterji, N. S., & Bartlett, P. L. (2017) · arXiv (Cornell University) · Cited by 28
Sparse Federated Learning With Hierarchical Personalization Models
Liu, X., Wang, Q., Shao, Y., & Li, Y. (2023) · IEEE Internet of Things Journal · doi:10.1109/jiot.2023.3318647 · Cited by 27
“Theorem 1: Proof: We first prove some interesting character of φ ρ ( x ) in (4), which is convex smooth approximation to (cid:5) x (cid:5) 1 [33] and”
BackgroundZhu, Z., Ding, T., Robinson, D. P., Tsakiris, M. C., & Vidal, R. (2019) · neural information processing systems · Cited by 27
Time Series Forecasting via Learning Convolutionally Low-Rank Models
Liu, G. (2022) · IEEE Transactions on Information Theory · doi:10.1109/tit.2022.3144605 · Cited by 27
“The latter is closely related to the problem of learning a possibly overcomplete dictionary B T ∈ R m × q that expresses each sample as a linear combination of few dictionary atoms, i.e., the well-known sparsely-used dictionary learning [9], [10], [11], [12].”
BackgroundEfficient Dictionary Learning with Gradient DescentPreprint
Gilboa, D., Buchanan, S., & Wright, J. N. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1809.10313 · Cited by 27
“Strictly speaking, fDL is Morse with high probability, due to results of (Sun et al., 2017).”
BackgroundInfluentialSelf-citationLinearized ADMM Converges to Second-Order Stationary Points for Non-Convex Problems
Lu, S., Lee, J. D., Razaviyayn, M., & Hong, M. (2021) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2021.3100976 · Cited by 26
Zhang, C., Chen, X., & Ma, S. (2023) · Mathematics of Operations Research · doi:10.1287/moor.2022.0286 · Cited by 25
Chen, S., Ma, S., So, A. M., & Zhang, T. (2024) · SIAM Review · doi:10.1137/24m1628578 · Cited by 25
First-Order Algorithms for Min-Max Optimization in Geodesic Metric Spaces
Jordan, M. I., Lin, T., & Vlatakis-Gkaragkounis, E.-V. (2022) · neural information processing systems · doi:10.52202/068431-0475 · Cited by 25
Sparse Coding and Autoencoders
Rangamani, A., Mukherjee, A., Basu, A., Arora, A., Ganapathi, T., Chin, S., & Tran, T. D. (2018) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit.2018.8437533 · Cited by 25
Li, Z., Cai, J., & Wei, K. (2019) · IEEE Transactions on Information Theory · doi:10.1109/tit.2019.2956922 · Cited by 25
Chen, S., Deng, Z., Ma, S., & So, A. M. (2021) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2021.3099643 · Cited by 25
“They then solve the resulting smoothed problems by either the Riemannian trust-region method [26, 27] or the Riemannian gradient descent method [11, 20].”
Mirror descent in saddle-point problems: Going the extra (gradient) mile.Preprint
Mertikopoulos, P., Zenati, H., Lecouat, B., Foo, C.-S., Chandrasekhar, V., & Piliouras, G. (2018) · arXiv (Cornell University) · Cited by 25
Finding 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
“If one sparse row vector of X can be found, one may resort to deflation [47] or repeating random trials [46, 70] to recover X and A up to a signed permutation SP( n ) ambiguity.”
BackgroundMethodInfluentialSelf-citationRevisiting Opinion Dynamics with Varying Susceptibility to Persuasion via Non-Convex Local Search
Chan, T.-H. H., Liang, Z., & Sozio, M. (2019) · International World Wide Web Conference (WWW) · doi:10.1145/3308558.3313509 · Cited by 23
“[14], who also gave examples of problems where all local optima are also global optima; some examples are tensor decomposition [9], dictionary learning [22], phase retrieval [21], matrix sensing [3, 20] and matrix completion [10].”
BackgroundSensor calibration for off-the-grid spectral estimation
Eldar, Y. C., Liao, W., & Tang, S. (2018) · Applied and Computational Harmonic Analysis · doi:10.1016/j.acha.2018.08.003 · Cited by 23
A Newton-MR algorithm with complexity guarantees for nonconvex smooth unconstrained optimizationPreprint
Liu, Y., & Roosta, F. (2022) · arXiv (Cornell University) · doi:10.48550/arxiv.2208.07095 · Cited by 23
“, online tensor decomposition [71], dictionary recovery problems [72], the (generalized) phase retrieval problems [73], and the phase synchronization and community detection problems [3,12].”
BackgroundOptimization landscape of Tucker decomposition
Frandsen, A., & Ge, R. (2020) · Mathematical Programming · doi:10.1007/s10107-020-01531-z · Cited by 22
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.