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.”
Conn, A. R., Gould, N. I. M., & Toint, P. L. (2000) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9780898719857 · Cited by 2,981
The Geometry of Algorithms with Orthogonality Constraints
Edelman, A., Arias, T. A., & Smith, S. T. (1998) · SIAM Journal on Matrix Analysis and Applications · doi:10.1137/s0895479895290954 · Cited by 2,685 · cited 1×
“This will require additional nontrivial technical work, but likely feasible thanks to the relatively complete knowledge of the orthogonal group [50], [119].”
BackgroundA Mathematical Introduction to Compressive Sensing
Foucart, S., & Rauhut, H. (2013) · Applied and Numerical Harmonic Analysis · doi:10.1007/978-0-8176-4948-7 · Cited by 2,548 · cited 1×
“A.7 (Moments of the ˜RV). If X˘˜(n), then it holds for all integer p1 that E[Xp] = 2p=2 ( p=2 + n=2) ( n=2) p!np=2: Lemma A.8 (Moment-Control Bernstein’s Inequality for Scalar RVs, Theorem 2.10 of [122]). Let X 1;:::;X p be i.i.d. real-valued random variables. Suppose that there exist some positive numbers Rand ˙2 suc…”
BackgroundInfluentialReal Analysis: Modern Techniques and Their Applications
Folland, G. B. (1984) · Cited by 2,496
Convergence of a Block Coordinate Descent Method for Nondifferentiable Minimization
Tseng, P. (2001) · Journal of Optimization Theory and Applications · doi:10.1023/a:1017501703105 · Cited by 1,989 · cited 1×
“, [34], [35] for classic results and [36], [37] for several interesting recent developments.”
BackgroundSparse and Redundant Representations: From Theory to Applications in Signal and Image Processing
Elad, M. (2010) · doi:10.1007/978-1-4419-7011-4 · Cited by 1,897 · cited 3×
“far too ambitious to include here a comprehensive review of the exciting developments of DL algorithms and applications after the pioneer work [10]. We refer the reader to Chapter 12 - 15 of the book [12] and the survey paper [13] for summaries of relevant developments in image analysis and visual recognition. In the…”
BackgroundResultInfluentialOptimization Algorithms on Matrix Manifolds
Absil, P.-A., Mahony, R., & Sepulchre, R. (2008) · Princeton University Press eBooks · doi:10.1515/9781400830244 · Cited by 1,840
Concentration Inequalities: A Nonasymptotic Theory of Independence
Boucheron, S., Lugosi, G., & Massart, P. (2013) · doi:10.1093/acprof:oso/9780199535255.001.0001 · Cited by 1,768 · cited 1×
“Moreover, for any z, z (cid:48) ∈ R , we have Lemma A.2 (Harris’ Inequality, [120], see also Theorem 2.15 of [121]) .”
BackgroundInfluentialProximal alternating linearized minimization for nonconvex and nonsmooth problems
Bolte, J., Sabach, S., & Teboulle, M. (2014) · Mathematical Programming · doi:10.1007/s10107-013-0701-9 · Cited by 1,688 · cited 3×
“To characterize the function landscape of f ( q ; X 0 ) over S n − 1 , we mostly work with the function induced by the reparametrization In particular, we focus our attention to the smaller set because q (Γ) contains all points q ∈ S n − 1 with n ∈ arg max i ∈± [ n ] q ∗ e i and we can similarly…”
MethodMoré, J. J., & Sorensen, D. C. (1983) · SIAM Journal on Scientific and Statistical Computing · doi:10.1137/0904038 · Cited by 1,411 · cited 1×
“t to min k˘k fb(U q(k)˘;q (k)); (I.17) where the objective is quadratic in ˘. This is the classical trust region problem (with ‘2 norm ball constraint) that admits very efficient numerical algorithms [55], [56]. Once we obtain the minimizer ˘ ?, we set ?= U˘ ?, which solves (I.16). One additional issue as compared to t…”
BackgroundNeural networks and principal component analysis: Learning from examples without local minima
Baldi, P., & Hornik, K. (1989) · Neural Networks · doi:10.1016/0893-6080(89)90014-2 · Cited by 1,383 · cited 1×
“e) Nonconvex problems with similar geometric structure: Besides ICA discussed above, it turns out that a handful of other practical problems arising in signal processing and machine learning induce the “no spurious minimizers, all saddles are second-order” structure under natural setting, including the eigenvalue prob…”
BackgroundPhaseLift: Exact and Stable Signal Recovery from Magnitude Measurements via Convex Programming
Candès, E. J., Strohmer, T., & Voroninski, V. (2013) · Communications on Pure and Applied Mathematics · doi:10.1002/cpa.21432 · Cited by 1,197
Parallel and distributed computation
Bertsekas, D. P., Tsitsiklis, J. N., & Sennikov, A. N. (1989) · Cited by 1,187
Attouch, H., Bolte, J., Redont, P., & Soubeyran, A. (2010) · Mathematics of Operations Research · doi:10.1287/moor.1100.0449 · Cited by 1,172 · cited 3×
“To characterize the function landscape of f ( q ; X 0 ) over S n − 1 , we mostly work with the function induced by the reparametrization In particular, we focus our attention to the smaller set because q (Γ) contains all points q ∈ S n − 1 with n ∈ arg max i ∈± [ n ] q ∗ e i and we can similarly…”
MethodPhase Retrieval via Wirtinger Flow: Theory and Algorithms
Candès, E. J., Li, X., & Soltanolkotabi, M. (2015) · IEEE Transactions on Information Theory · doi:10.1109/tit.2015.2399924 · Cited by 1,049
1 USER-FRIENDLY TAIL BOUNDS FOR SUMS OF RANDOM MATRICES
Tropp, J. A. (2010) · Cited by 1,018
Matrix Completion From a Few Entries
Keshavan, R. H., Montanari, A., & Oh, S. (2010) · IEEE Transactions on Information Theory · doi:10.1109/tit.2010.2046205 · Cited by 974
The Convex Geometry of Linear Inverse Problems
Chandrasekaran, V., Recht, B., Parrilo, P. A., & Willsky, A. S. (2010) · Cited by 921
The Convex Geometry of Linear Inverse Problems
Chandrasekaran, V., Recht, B., Parrilo, P. A., & Willsky, A. S. (2012) · Foundations of Computational Mathematics · doi:10.1007/s10208-012-9135-7 · Cited by 886
DeVore, R. A. (1998) · Acta Numerica · doi:10.1017/s0962492900002816 · Cited by 877 · cited 1×
“Let A ∞ denote the value of A at convergence (we set the maximally allowable number of ADM iterations to be 10 4 and λ = 2 ).”
BackgroundLow-rank matrix completion using alternating minimization
Jain, P., Netrapalli, P., & Sanghavi, S. (2013) · Proceedings of the forty-fifth annual ACM symposium on Theory of Computing · doi:10.1145/2488608.2488693 · Cited by 817
Blind Source Separation by Sparse Decomposition in a Signal Dictionary
Zibulevsky, M., & Pearlmutter, B. A. (2001) · Neural Computation · doi:10.1162/089976601300014385 · Cited by 766
Optimization and Dynamical Systems
Helmke, U., & Moore, J. B. (1994) · Communications and Control Engineering · doi:10.1007/978-1-4471-3467-1 · Cited by 724
User-Friendly Tail Bounds for Sums of Random Matrices
Tropp, J. A. (2012) · Foundations of Computational Mathematics · doi:10.1007/s10208-011-9099-z · Cited by 718 · cited 1×
“all integers m2: Let S : = 1 p P p k=1 X k, then for all t>0, it holds that P[jS E[S]jt] 2exp pt2 2˙2 + 2Rt : Lemma A.9 (Moment-Control Bernstein’s Inequality for Matrix RVs, Theorem 6.2 of [123]). Let X 1;:::;X p2R d be i.i.d. random, symmetric matrices. Suppose there exist some positive number Rand ˙2 such that E…”
BackgroundInfluentialMatrix completion from a few entries
Keshavan, R. H., Oh, S., & Montanari, A. (2009) · 2009 IEEE International Symposium on Information Theory · doi:10.1109/isit.2009.5205567 · Cited by 650
Deep learning without poor local minima
Kawaguchi, K. (2016) · arXiv · doi:10.48550/arxiv.1605.07110 · Cited by 592
A lower bound for the critical probability in a certain percolation process
Harris, T. E. (1960) · Mathematical Proceedings of the Cambridge Philosophical Society · doi:10.1017/s0305004100034241 · Cited by 589 · cited 2×
“Lemma 30 (Harris’ Inequality, [121], See Also [122, Th.”
InfluentialPhase Retrieval Using Alternating Minimization
Netrapalli, P., Jain, P., & Sanghavi, S. (2015) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2015.2448516 · Cited by 535 · 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.”
MethodHigh-dimensional regression with noisy and missing data: Provable guarantees with nonconvexity
Loh, P.-L., & Wainwright, M. J. (2012) · The Annals of Statistics · doi:10.1214/12-aos1018 · Cited by 529 · cited 1×
“s with another popular contrast function, the fourth-order cumulants, however, indeed overlap 21This is a body of recent work studying nonconvex recovery up to statistical precision, including, e.g., [65]–[72]. 22The powerful framework [40], [41] to establish local convergence of ADM algorithms to critical points appl…”
BackgroundConvex Functions and Optimization Methods on Riemannian Manifolds
Udrişte, C. (1994) · Springer eBooks · doi:10.1007/978-94-015-8390-9 · Cited by 491 · cited 1×
“ust-region algorithm on the sphere builds on the extensive research efforts to generalize Euclidean numerical algorithms to (Riemannian) manifold settings. We refer the reader to the monographs [52], [99], [100] for survey of developments in this field. In particular, [101] developed Newton and conjugate-gradient metho…”
MethodSolving Random Quadratic Systems of Equations Is Nearly as Easy as Solving Linear Systems
Chen, Y., & Candès, E. J. (2017) · Communications on Pure and Applied Mathematics · doi:10.1002/cpa.21638 · Cited by 477
Ma, J., & Plonka, G. (2010) · IEEE Signal Processing Magazine · doi:10.1109/msp.2009.935453 · Cited by 464 · cited 1×
“Let A ∞ denote the value of A at convergence (we set the maximally allowable number of ADM iterations to be 10 4 and λ = 2 ).”
BackgroundTrust-Region Methods on Riemannian Manifolds
Absil, P.-A., Baker, C. G., & Gallivan, K. A. (2007) · Foundations of Computational Mathematics · doi:10.1007/s10208-005-0179-9 · Cited by 461 · cited 1×
“2) Proof of Proposition II.6: Proof: By similar consideration as proof of the above proposition, the following is justified:”
BackgroundDonoho, D., & Tanner, J. (2009) · Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences · doi:10.1098/rsta.2009.0152 · Cited by 436 · cited 1×
“In this paper, we provide a nonconvex formulation for the DR problem, and characterize the geometric structure of the formulation that allows development of efficient algorithms for optimization.”
MethodData compression and harmonic analysis
Donoho, D. L., Vetterli, M., DeVore, R. A., & Daubechies, I. (1998) · IEEE Transactions on Information Theory · doi:10.1109/18.720544 · Cited by 432 · cited 1×
“Manuscript received xxx; revised xxx. 1 As Donoho et al [9] put it, “...in effect, uncovering the optimal codebook structure of naturally occurring data involves more challenging empirical questions than any that have ever been solved in empirical work in the mathematical sciences.” a r X i v :…”
BackgroundLiving on the edge: phase transitions in convex programs with random data
Amelunxen, D., Lotz, M., McCoy, M. B., & Tropp, J. A. (2014) · Information and Inference · doi:10.1093/imaiai/iau005 · Cited by 413
Blind Deconvolution Using Convex Programming
Ahmed, A., Recht, B., & Romberg, J. (2014) · IEEE Transactions on Information Theory · doi:10.1109/tit.2013.2294644 · Cited by 387 · cited 1×
“Known relaxations [42], [48] fix the scale by setting (cid:107) q ∗ Y ∞ = 1 and use (cid:107)·(cid:107) 1 as a surrogate to (cid:107)·(cid:107) 0 , where (cid:107)·(cid:107) ∞ is the elementwise ∞ norm, leading to the optimization problem The constraint means at least one coordinate of q ∗ Y has…”
BackgroundStatistical guarantees for the EM algorithm: From population to sample-based analysis
Balakrishnan, S., Wainwright, M. J., & Yu, B. (2017) · The Annals of Statistics · doi:10.1214/16-aos1435 · Cited by 384
Sparse Modeling for Image and Vision Processing
Ponce, J., Mairal, J., Bach, F., Image, S. M., Processing, V., Hal, H. I., & Supérieure, E. N. (2014) · Cited by 335
Sparse Modeling for Image and Vision Processing
Mairal, J. (2014) · now publishers, Inc. eBooks · doi:10.1561/9781680830095 · Cited by 322
Nonlinear Methods of Approximation
Temlyakov, V. N. (2003) · Foundations of Computational Mathematics · doi:10.1007/s102080010029 · Cited by 309
Guaranteed Matrix Completion via Non-Convex Factorization
Sun, R., & Luo, Z.-Q. (2016) · IEEE Transactions on Information Theory · doi:10.1109/tit.2016.2598574 · Cited by 309
The non-convex Burer-Monteiro approach works on smooth semidefinite programsPreprint
Boumal, N., Voroninski, V., & Bandeira, A. S. (2016) · arXiv (Cornell University) · doi:10.48550/arxiv.1606.04970 · Cited by 288 · cited 1×
“e) Nonconvex problems with similar geometric structure: Besides ICA discussed above, it turns out that a handful of other practical problems arising in signal processing and machine learning induce the “no spurious minimizers, all saddles are second-order” structure under natural setting, including the eigenvalue prob…”
BackgroundComputing a nonnegative matrix factorization -- provably
Arora, S., Ge, R., Kannan, R., & Moitra, A. (2012) · Proceedings of the forty-fourth annual ACM symposium on Theory of computing · doi:10.1145/2213977.2213994 · Cited by 280 · 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.”
MethodSparse Modeling for Image and Vision Processing
Mairal, J., Bach, F., & Ponce, J. (2014) · Foundations and Trends® in Computer Graphics and Vision · doi:10.1561/0600000058 · Cited by 267 · cited 2×
“Is there any hope to obtain global solutions to the DL problem?”
BackgroundRegularized M-estimators with nonconvexity: Statistical and algorithmic theory for local optima
Loh, P., & Wainwright, M. J. (2013) · ScholarlyCommons (University of Pennsylvania) · Cited by 254
On the Computational Efficiency of Training Neural Networks
Livni, R., Shalev‐Shwartz, S., & Shamir, O. (2014) · arXiv (Cornell University) · doi:10.48550/arxiv.1410.1141 · Cited by 245 · 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.”
MethodProvable Bounds for Learning Some Deep Representations
Arora, S., Bhaskara, A., Ge, R., & Ma, T. (2013) · arXiv (Cornell University) · doi:10.48550/arxiv.1310.6343 · Cited by 240
Non-convex Robust PCAPreprint
Netrapalli, P., Niranjan, U. N., Sanghavi, S., Anandkumar, A., & Jain, P. (2014) · CaltechAUTHORS (California Institute of Technology) · doi:10.48550/arxiv.1410.7660 · Cited by 240
Global Optimality of Local Search for Low Rank Matrix Recovery
Bhojanapalli, S., Neyshabur, B., & Srebro, N. (2016) · arXiv (Cornell University) · doi:10.48550/arxiv.1605.07221 · Cited by 218 · cited 1×
“e) Nonconvex problems with similar geometric structure: Besides ICA discussed above, it turns out that a handful of other practical problems arising in signal processing and machine learning induce the “no spurious minimizers, all saddles are second-order” structure under natural setting, including the eigenvalue prob…”
BackgroundUnderstanding Alternating Minimization for Matrix Completion
Hardt, M. (2014) · 2014 IEEE 55th Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2014.75 · Cited by 216
Exact Recovery of Sparsely-Used DictionariesPreprint
Spielman, D. A., Wang, H., & Wright, J. N. (2012) · arXiv (Cornell University) · doi:10.48550/arxiv.1206.5882 · Cited by 216 · cited 5×
“that the phenomenon has been observed on real images7. One may imagine only random data typically have “favorable” structures; in fact, almost all existing theories for DL pertain only to random data [42]–[47]. C. Dictionary Recovery and Our Results In this paper, we take a step towards explaining the surprising effec…”
BackgroundMethodInfluentialSelf-citationSquare Deal: Lower Bounds and Improved Relaxations for Tensor Recovery
Mu, C., Huang, B., Wright, J. N., & Goldfarb, D. (2013) · arXiv (Cornell University) · doi:10.48550/arxiv.1307.5870 · Cited by 203
Self-citationDictionary Learning and Tensor Decomposition via the Sum-of-Squares Method
Barak, B., Kelner, J. A., & Steurer, D. (2015) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/2746539.2746605 · Cited by 202 · cited 3×
“The improvement is based on a refinement to the rounding procedure for the SOS proposed in [57].”
BackgroundMethodOn the uniqueness of overcomplete dictionaries, and a practical way to retrieve them
Aharon, M., Elad, M., & Bruckstein, A. M. (2006) · Linear Algebra and its Applications · doi:10.1016/j.laa.2005.06.035 · Cited by 194
Dictionary Identification—Sparse Matrix-Factorization via $\ell_1$-Minimization
Gribonval, R., & Schnass, K. (2010) · IEEE Transactions on Information Theory · doi:10.1109/tit.2010.2048466 · Cited by 191
Nonconvex Phase Synchronization
Boumal, N. (2016) · SIAM Journal on Optimization · doi:10.1137/16m105808x · Cited by 191
Simple, Efficient, and Neural Algorithms for Sparse CodingPreprint
Arora, S., Ge, R., Ma, T., & Moitra, A. (2015) · arXiv (Cornell University) · doi:10.48550/arxiv.1503.00778 · Cited by 190 · cited 5×
“[39], [41] and [40], [43] gave efficient algorithms that provably recover overcomplete (m ≥ n), incoherent dictionaries, based on a”
BackgroundInfluentialA Geometric Analysis of Phase Retrieval
Sun, J., Qu, Q., & Wright, J. (2018) · Foundations of Computational Mathematics · doi:10.1007/s10208-017-9365-9 · Cited by 189
Self-citationChen, Y., & Wainwright, M. J. (2015) · arXiv (Cornell University) · doi:10.48550/arxiv.1509.03025 · Cited by 187
Low-rank Solutions of Linear Matrix Equations via Procrustes FlowPreprint
Tu, S., Boczar, R., Simchowitz, M., Soltanolkotabi, M., & Recht, B. (2015) · arXiv (Cornell University) · doi:10.48550/arxiv.1507.03566 · Cited by 180
Provable Tensor Factorization with Missing DataPreprint
Jain, P., & Oh, S. (2014) · arXiv (Cornell University) · doi:10.48550/arxiv.1406.2784 · Cited by 178 · 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.”
MethodNew Algorithms for Learning Incoherent and Overcomplete DictionariesPreprint
Arora, S., Ge, R., & Moitra, A. (2013) · arXiv (Cornell University) · doi:10.48550/arxiv.1308.6273 · Cited by 174 · cited 1×
“[39], [41] and [40], [43] gave efficient algorithms that provably recover overcomplete (m ≥ n), incoherent dictionaries, based on a”
BackgroundEscaping From Saddle Points --- Online Stochastic Gradient for Tensor Decomposition
Ge, R., Huang, F., Jin, C., & Yang, Y. (2015) · arXiv (Cornell University) · doi:10.48550/arxiv.1503.02101 · Cited by 173 · cited 1×
“2) Proof of Proposition II.6: Proof: By similar consideration as proof of the above proposition, the following is justified:”
BackgroundRegularized M-estimators with nonconvexity: Statistical and algorithmic theory for local optima
Loh, P., & Wainwright, M. J. (2013) · arXiv (Cornell University) · doi:10.48550/arxiv.1305.2436 · Cited by 169
Matrix Completion has No Spurious Local Minimum
Ge, R., Lee, J. D., & Ma, T. (2016) · arXiv (Cornell University) · doi:10.48550/arxiv.1605.07272 · Cited by 168
When Are Nonconvex Problems Not Scary?Preprint
Sun, J., Qu, Q., & Wright, J. N. (2015) · arXiv (Cornell University) · doi:10.48550/arxiv.1510.06096 · Cited by 166
Self-citationStatistical consistency and asymptotic normality for high-dimensional robust $M$-estimators
Loh, P.-L. (2017) · The Annals of Statistics · doi:10.1214/16-aos1471 · Cited by 166
Low-rank solutions of linear matrix equations via procrustes flow
Tu, S., Boczar, R., Simchowitz, M., Soltanolkotabi, M., & Recht, B. (2016) · Cited by 165
Learning Sparsely Used Overcomplete Dictionaries via Alternating Minimization
Agarwal, A., Anandkumar, A., Jain, P., & Netrapalli, P. (2016) · SIAM Journal on Optimization · doi:10.1137/140979861 · Cited by 162
Support recovery without incoherence: A case for nonconvex regularization
Loh, P.-L., & Wainwright, M. J. (2017) · The Annals of Statistics · doi:10.1214/16-aos1530 · Cited by 161
Learning Unions of Orthonormal Bases with Thresholded Singular Value Decomposition
Lesage, S., Gribonval, R., Bimbot, F., & Benaroya, L. (2006) · IEEE International Conference on Acoustics Speech and Signal Processing · doi:10.1109/icassp.2005.1416298 · Cited by 155
Sparse and Spurious: Dictionary Learning With Noise and Outliers
Gribonval, R., Jenatton, R., & Bach, F. (2015) · IEEE Transactions on Information Theory · doi:10.1109/tit.2015.2472522 · Cited by 147
Guaranteed Non-Orthogonal Tensor Decomposition via Alternating Rank-$1$ UpdatesPreprint
Anandkumar, A., Ge, R., & Janzamin, M. (2014) · arXiv (Cornell University) · doi:10.48550/arxiv.1402.5180 · Cited by 141
Polynomial-Time Tensor Decompositions with Sum-of-Squares
Ma, T., Jonathan Jingsheng, S. H. I., & Steurer, D. (2016) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2016.54 · Cited by 140 · cited 1×
“After our initial submission, the very recent work [58] assumed the same model as in [57] and provided the first polynomial-time algorithm that guarantees to recover overcomplete dictionaries when the coefficients have up to near sparsity.”
MethodA geometric analysis of phase retrieval
Sun, J., Qu, Q., & Wright, J. N. (2016) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit.2016.7541725 · Cited by 140
Self-citationNo bad local minima: Data independent training error guarantees for multilayer neural networks
Soudry, D., & Carmon, Y. (2016) · arXiv (Cornell University) · doi:10.48550/arxiv.1605.08361 · Cited by 133
Zheng, Q., & Lafferty, J. (2015) · arXiv (Cornell University) · doi:10.48550/arxiv.1506.06081 · Cited by 130
Finding a Sparse Vector in a Subspace: Linear Sparsity Using Alternating Directions
Qu, Q., Sun, J., & Wright, J. (2016) · IEEE Transactions on Information Theory · doi:10.1109/tit.2016.2601599 · Cited by 120 · cited 2×
“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.”
BackgroundMethodSelf-citationProvable Sparse Tensor Decomposition
Sun, W. W., Lu, J., Liu, H., & Cheng, G. (2016) · Journal of the Royal Statistical Society Series B (Statistical Methodology) · doi:10.1111/rssb.12190 · Cited by 119
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 · cited 3×
“These challenges are coupled, as function classes with known “good” analytic bases are rare.”
BackgroundMethodInfluentialSelf-citationWang, Z., Gu, Q., Ning, Y., & Liu, H. (2014) · PubMed · doi:10.48550/arxiv.1412.8729 · Cited by 105
Fast Exact Matrix Completion with Finite SamplesPreprint
Jain, P., & Netrapalli, P. (2014) · arXiv (Cornell University) · doi:10.48550/arxiv.1411.1087 · Cited by 104 · cited 1×
“In the surge of theoretical understanding of nonconvex heuristics [39]–[41], [43], [46], [74]–[79], [84], [85], [88], [89], [92], [93], [93], the initialization plus local refinement strategy mostly differs from practice, whereby random initializations seem to work well, and the analytic techniques developed in that l…”
BackgroundGuaranteed Matrix Completion via Nonconvex Factorization
Sun, R., & Luo, Z.-Q. T. (2015) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2015.25 · Cited by 102
Sample Complexity of Dictionary Learning and Other Matrix Factorizations
Gribonval, R., Jenatton, R., Bach, F., Kleinsteuber, M., & Seibert, M. (2015) · IEEE Transactions on Information Theory · doi:10.1109/tit.2015.2424238 · Cited by 98
Lee, K., Wu, Y., & Bresler, Y. (2017) · IEEE Transactions on Information Theory · doi:10.1109/tit.2017.2784479 · Cited by 98
Fast Sparsity-Based Orthogonal Dictionary Learning for Image Restoration
Bao, C., Cai, J., & Ji, H. (2013) · IEEE/CVF International Conference on Computer Vision (ICCV) · doi:10.1109/iccv.2013.420 · Cited by 96 · cited 2×
“For norms, (cid:107)·(cid:107) is the usual 2 norm for a vector and the operator norm (i.e., 2 → 2 ) for a matrix; all other norms will be indexed by subscript, for example the Frobenius norm (cid:107)·(cid:107) F for matrices and the element-wise max-norm (cid:107)·(cid:107) ∞ .”
BackgroundMethod$K$-Dimensional Coding Schemes in Hilbert Spaces
Maurer, A., & Pontil, M. (2010) · IEEE Transactions on Information Theory · doi:10.1109/tit.2010.2069250 · Cited by 92 · cited 1×
“Is there any hope to obtain global solutions to the DL problem?”
BackgroundThe Sample Complexity of Dictionary LearningPreprint
Vainsencher, D., Mannor, S., & Bruckstein, A. M. (2010) · arXiv (Cornell University) · doi:10.48550/arxiv.1011.5395 · Cited by 92
New Null Space Results and Recovery Thresholds for Matrix Rank MinimizationPreprint
Oymak, S., & Hassibi, B. (2010) · arXiv (Cornell University) · doi:10.48550/arxiv.1011.6326 · Cited by 91
Sharp Recovery Bounds for Convex Demixing, with Applications
McCoy, M. B., & Tropp, J. A. (2014) · Foundations of Computational Mathematics · doi:10.1007/s10208-014-9191-2 · Cited by 87
Complete 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-citationBandeira, A. S., Boumal, N., & Voroninski, V. (2016) · arXiv (Cornell University) · doi:10.48550/arxiv.1602.04426 · Cited by 82
L0 Norm Based Dictionary Learning by Proximal Methods with Global Convergence
Bao, C., Ji, H., Quan, Y., & Shen, Z. (2014) · IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings - IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings · doi:10.1109/cvpr.2014.493 · Cited by 81 · cited 1×
“very up to statistical precision, including, e.g., [66]–[73]. 21The powerful framework [38], [39] to establish local convergence of ADM algorithms to critical points applies to DL/DR also, see, e.g., [96]–[98]. However, these results do not guarantee to produce global optima. IEEE TRANSACTION ON INFORMATION THEORY, VO…”
BackgroundCurvilinear path steplength algorithms for minimization which use directions of negative curvature
Goldfarb, D. (1980) · Mathematical Programming · doi:10.1007/bf01588294 · Cited by 78
Provable ICA with Unknown Gaussian Noise, and Implications for Gaussian Mixtures and Autoencoders
Arora, S., Ge, R., Moitra, A., & Sachdeva, S. (2015) · Algorithmica · doi:10.1007/s00453-015-9972-2 · Cited by 72 · cited 3×
“unction in ICA that has not been thoroughly analyzed [112], and algorithm and analysis with another popular contrast function, the fourth-order cumulants, indeed overlap with ours considerably [110], [111]22. While this interesting connection potentially helps port our analysis to ICA, it is a fundamental question to…”
BackgroundMethodInfluentialA 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 · cited 2×
“[39], [41] and [40], [43] gave efficient algorithms that provably recover overcomplete (m ≥ n), incoherent dictionaries, based on a”
BackgroundLearning linear transformations
FRIEZE, A. M., Jerrum, M., & Kannan, R. (2002) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1996.548495 · Cited by 67 · 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.”
MethodAlternating Minimization for Mixed Linear Regression
Yi, X., Caramanis, C., & Sanghavi, S. (2013) · arXiv (Cornell University) · doi:10.48550/arxiv.1310.3745 · Cited by 66 · cited 2×
“In the surge of theoretical understanding of nonconvex heuristics [39]–[41], [43], [46], [74]–[79], [84], [85], [88], [89], [92], [93], [93], the initialization plus local refinement strategy mostly differs from practice, whereby random initializations seem to work well, and the analytic techniques developed in that l…”
BackgroundTensor vs Matrix Methods: Robust Tensor Decomposition under Block Sparse PerturbationsPreprint
Anandkumar, A., Jain, P., Shi, Y., & Niranjan, U. N. (2015) · arXiv (Cornell University) · doi:10.48550/arxiv.1510.04747 · Cited by 65
On the identifiability of overcomplete dictionaries via the minimisation principle underlying K-SVD
Schnass, K. (2014) · Applied and Computational Harmonic Analysis · doi:10.1016/j.acha.2014.01.005 · Cited by 59
Donoho, D. L., Gavish, M., & Montanari, A. (2013) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.1306110110 · Cited by 57
When Can Dictionary Learning Uniquely Recover Sparse Data From Subsamples?
Hillar, C. J., & Sommer, F. T. (2015) · IEEE Transactions on Information Theory · doi:10.1109/tit.2015.2460238 · Cited by 57 · cited 2×
“Aside from efficient recovery, other theoretical work on DL includes results on identifiability [52], [53], [59], generalization bounds [60]–[63], and noise stability [64].”
BackgroundProvable Methods for Training Neural Networks with Sparse ConnectivityPreprint
Sedghi, H., & Anandkumar, A. (2014) · arXiv (Cornell University) · doi:10.48550/arxiv.1412.2693 · Cited by 57
Approximating the little Grothendieck problem over the orthogonal and unitary groups
Bandeira, A. S., Kennedy, C., & Singer, A. (2016) · Mathematical Programming · doi:10.1007/s10107-016-0993-7 · Cited by 55
Dropping Convexity for Faster Semi-definite OptimizationPreprint
Bhojanapalli, S., Kyrillidis, A., & Sanghavi, S. (2015) · arXiv (Cornell University) · doi:10.48550/arxiv.1509.03917 · Cited by 53
Kech, M., & Krahmer, F. (2017) · SIAM Journal on Applied Algebra and Geometry · doi:10.1137/16m1067469 · Cited by 53
More Algorithms for Provable Dictionary LearningPreprint
Arora, S., Bhaskara, A., Ge, R., & Ma, T. (2014) · arXiv (Cornell University) · doi:10.48550/arxiv.1401.0579 · Cited by 49
Fast matrix completion without the condition number
Hardt, M., & Wootters, M. K. (2014) · arXiv (Cornell University) · doi:10.48550/arxiv.1407.4070 · Cited by 49
Identifiability Scaling Laws in Bilinear Inverse ProblemsPreprint
Choudhary, S., & Mitra, U. (2014) · arXiv (Cornell University) · doi:10.48550/arxiv.1402.2637 · Cited by 47 · cited 2×
“, [17]–[19] and the identification issue in blind deconvolution [20], [21].”
BackgroundOn the local correctness of ℓ1-minimization for dictionary learning
Geng, Q., & Wright, J. N. (2014) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit.2014.6875421 · Cited by 45
Self-citationAnalyzing Tensor Power Method Dynamics in Overcomplete RegimePreprint
Anandkumar, A., Ge, R., & Janzamin, M. (2014) · Journal of Machine Learning Research · doi:10.48550/arxiv.1411.1488 · Cited by 42
Scaling law for recovering the sparsest element in a subspace
Demanet, L., & Hand, P. (2014) · Information and Inference A Journal of the IMA · doi:10.1093/imaiai/iau007 · Cited by 40 · cited 3×
“A substantial leap forward would be to extend the methodology to recovery of structured overcomplete dictionaries, such as tight frames.”
BackgroundMethodComplete Dictionary Recovery over the SpherePreprint
Sun, J., Qu, Q., & Wright, J. N. (2015) · arXiv (Cornell University) · doi:10.48550/arxiv.1504.06785 · Cited by 38
Self-citationConvergence radius and sample complexity of ITKM algorithms for dictionary learning
Schnass, K. (2016) · Applied and Computational Harmonic Analysis · doi:10.1016/j.acha.2016.08.002 · Cited by 38
Statistical guarantees for the EM algorithm: From population to sample-based analysisPreprint
Balakrishnan, S., Wainwright, M. J., & Yu, B. (2014) · arXiv (Cornell University) · doi:10.48550/arxiv.1408.2156 · Cited by 36
Convergence analysis for iterative data-driven tight frame construction scheme
Bao, C., Ji, H., & Shen, Z. (2014) · Applied and Computational Harmonic Analysis · doi:10.1016/j.acha.2014.06.007 · Cited by 36 · cited 1×
“up to statistical precision, including, e.g., [66]–[73]. 21The powerful framework [38], [39] to establish local convergence of ADM algorithms to critical points applies to DL/DR also, see, e.g., [96]–[98]. However, these results do not guarantee to produce global optima. IEEE TRANSACTION ON INFORMATION THEORY, VOL. XX…”
BackgroundNear Optimal Compressed Sensing of Sparse Rank-One Matrices via Sparse Power Factorization.Preprint
Lee, K., Wu, Y., & Bresler, Y. (2013) · arXiv (Cornell University) · Cited by 35
Identifiability and Stability in Blind Deconvolution Under Minimal Assumptions
Li, Y., Lee, K., & Bresler, Y. (2017) · IEEE Transactions on Information Theory · doi:10.1109/tit.2017.2689779 · Cited by 34 · cited 1×
“, [17]–[19] and the identification issue in blind deconvolution [20], [21].”
BackgroundNonconvex Statistical Optimization: Minimax-Optimal Sparse PCA in Polynomial TimePreprint
Wang, Z., Lu, H., & Liu, H. (2014) · arXiv (Cornell University) · doi:10.48550/arxiv.1408.5352 · Cited by 32
The local convexity of solving systems of quadratic equationsPreprint
White, C. D., Sanghavi, S., & Ward, R. (2015) · arXiv (Cornell University) · doi:10.48550/arxiv.1506.07868 · Cited by 32 · cited 1×
“c) Nonconvex optimization problems: For other nonconvex optimization problems of recovery of structured signals,21 including low-rank matrix completion/recovery [74]–[83], phase retreival [84]–[87], tensor recovery [88]–[91], mixed regression [92], [93], structured element pursuit [46], and recovery of simultaneously…”
BackgroundSparse Matrix FactorizationPreprint
Neyshabur, B., & Panigrahy, R. (2013) · arXiv (Cornell University) · doi:10.48550/arxiv.1311.3315 · Cited by 31
Local Identification of Overcomplete DictionariesPreprint
SchnassKarin (2014) · arXiv (Cornell University) · doi:10.48550/arxiv.1401.6354 · Cited by 31 · cited 1×
“Subsequent work [14], [15], [54]–[56] studied when the target dictionary is a local optimizer of natural recovery criteria.”
BackgroundComplete Dictionary Recovery Using Nonconvex Optimization
Sun, J., Qu, Q., & Wright, J. N. (2015) · Cited by 31
Self-citationSparsity-Based Generalization Bounds for Predictive Sparse Coding
Mehta, N. A., & Gray, A. (2013) · Cited by 29
Nonlinear approximation and its applications
DeVore, R. (2009) · Springer eBooks · doi:10.1007/978-3-642-03413-8_6 · Cited by 29
A Convergent Incoherent Dictionary Learning Algorithm for Sparse Coding
Bao, C., Quan, Y., & Ji, H. (2014) · Lecture notes in computer science · doi:10.1007/978-3-319-10599-4_20 · Cited by 29
Finding a sparse vector in a subspace: Linear sparsity using alternating directionsPreprint
Qu, Q., Sun, J., & Wright, J. N. (2014) · arXiv (Cornell University) · doi:10.48550/arxiv.1412.4659 · Cited by 29 · cited 2×
“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.”
BackgroundMethodSelf-citationA Clustering Approach to Learn Sparsely-Used Overcomplete DictionariesPreprint
Agarwal, A., Anandkumar, A., & Netrapalli, P. (2013) · arXiv (Cornell University) · doi:10.48550/arxiv.1309.1952 · Cited by 25 · cited 1×
“[41], [43] and [42], [45] gave efficient algorithms that provably recover overcomplete (m ≥ n) and incoherent dictionaries, based on a combination of {clustering or spectral initialization} and local refinement.”
MethodMatrix Sparsification and the Sparse Null Space Problem
Gottlieb, L.-A. J., & Neylon, T. (2010) · Lecture notes in computer science · doi:10.1007/978-3-642-15369-3_16 · Cited by 20
Computing Matrix Squareroot via Non Convex Local SearchPreprint
Jain, P., Jin, C., Kakade, S. M., & Netrapalli, P. (2015) · arXiv (Cornell University) · Cited by 20
Tight Hardness of the Non-commutative Grothendieck Problem
Briët, J., Regev, O., & Saket, R. (2017) · Theory of Computing · doi:10.4086/toc.2017.v013a015 · Cited by 18 · cited 1×
“, [17]–[19] and the identification issue in blind deconvolution [20], [21].”
BackgroundTight Hardness of the Non-commutative Grothendieck Problem
Briot, J., Regev, O., & Saket, R. (2015) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2015.72 · Cited by 16
Provable Tensor Methods for Learning Mixtures of Generalized Linear\n Models
Sedghi, H., Janzamin, M., & Anandkumar, A. (2017) · eScholarship (California Digital Library) · Cited by 15
Wu, S., & Yu, B. (2018) · Journal of Machine Learning Research · Cited by 13
Provable Tensor Methods for Learning Mixtures of Generalized Linear ModelsPreprint
Sedghi, H., Janzamin, M., & Anandkumar, A. (2014) · arXiv (Cornell University) · doi:10.48550/arxiv.1412.3046 · Cited by 11
Approximating the Little Grothendieck Problem over the Orthogonal and Unitary GroupsPreprint
Bandeira, A. S., Kennedy, C., & Singer, A. (2013) · arXiv (Cornell University) · doi:10.48550/arxiv.1308.5207 · Cited by 10
The Local Convexity of Solving Quadratic EquationsPreprint
White, C. D., Ward, R., & Sanghavi, S. (2015) · arXiv (Cornell University) · Cited by 10
Wu, S., & Yu, B. (2015) · arXiv (Cornell University) · doi:10.48550/arxiv.1505.04363 · Cited by 7
Sample Complexity of Dictionary Learning and other Matrix FactorizationsPreprint
Gribonval, R., Jenatton, R., Bach, F., et al. (2013) · arXiv (Cornell University) · doi:10.48550/arxiv.1312.3790 · Cited by 6
New Ties between Computational Harmonic Analysis and Approximation Theory
Candès, E. J. (n.d.) · Cited by 6
Dictionary Learning and Tensor Decomposition via the Sum-of-Squares MethodPreprint
Barak, B., Kelner, J. A., & Steurer, D. (2014) · arXiv (Cornell University) · doi:10.48550/arxiv.1407.1543 · Cited by 5 · cited 3×
“The improvement is based on a refinement to the rounding procedure for the SOS proposed in [57].”
BackgroundMethodProvable Sparse Tensor DecompositionPreprint
Sun, W. W., Lu, J., Liu, H., et al. (2015) · arXiv (Cornell University) · doi:10.48550/arxiv.1502.01425 · Cited by 4
Sparse and spurious: dictionary learning with noise and outliersPreprint
Gribonval, R., Jenatton, R., & Bach, F. (2014) · arXiv (Cornell University) · doi:10.48550/arxiv.1407.5155 · Cited by 4
Tight Hardness of the Non-commutative Grothendieck Problem
Briët, J., Regev, O., & Saket, R. (2014) · Centrum Wiskunde & Informatica (CWI), the national research institute for mathematics and computer science in the Netherlands · doi:10.48550/arxiv.1412.4413 · Cited by 4 · cited 1×
“, [17]–[19] and the identification issue in blind deconvolution [20], [21].”
BackgroundIdentifiability in Blind Deconvolution under Minimal Assumptions.Preprint
Li, Y., Lee, K., & Bresler, Y. (2015) · arXiv (Cornell University) · Cited by 3
Analyzing Tensor Power Method Dynamics in Overcomplete Regime - eScholarship
Anandkumar, A., Ge, R., & Janzamin, M. (2017) · Cited by 3
Provable Tensor Methods for Learning Mixtures of Generalized Linear Models - eScholarship
Sedghi, H., Janzamin, M., & Anandkumar, A. (2017) · Cited by 2
Approximating the Little Grothendieck Problem over the Unitary and Orthogonal GroupsPreprint
Bandeira, A. S., Kennedy, C., & Singer, A. (2013) · arXiv (Cornell University) · Cited by 2
Global Convergence of Non-Convex Gradient Descent for Computing Matrix SquarerootPreprint
Jain, P., Jin, C., Kakade, S. M., et al. (2015) · arXiv (Cornell University) · doi:10.48550/arxiv.1507.05854
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
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.