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 201–290 of 290
Optimization Foundations of Reinforcement Learning
Bhandari, J. (2020) · doi:10.7916/d8-adga-w360 · Cited by 4
Stochastic Approximation for Online Tensorial Independent Component AnalysisPreprint
Li, C. J., & Jordan, M. I. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2012.14415 · Cited by 4
PGDOT -- Perturbed Gradient Descent Adapted with Occupation TimePreprint
Guo, X., Han, J., Tajrobehkar, M., & Tang, W. (2020) · arXiv (Cornell University) · Cited by 4
Learning Polynomial TransformationsPreprint
Chen, S., Li, J. Z., Li, Y., & Zhang, A. R. (2022) · arXiv (Cornell University) · doi:10.48550/arxiv.2204.04209 · Cited by 4
Enhancing Performance of Explainable AI Models with Constrained Concept RefinementPreprint
Liang, G., Michielssen, S., & Fattahi, S. (2025) · arXiv (Cornell University) · doi:10.48550/arxiv.2502.06775 · Cited by 4
“Indeed, (Arora et al., 2015) asserts that sparsity levels beyond k = Ω n log n rarely succeed in practice, even though several approaches have been proposed to handle cases where k = Ω ( n ) (Sun et al., 2016; Liang et al., 2022).”
The Geometric Effects of Distributing Constrained Nonconvex Optimization Problems
Li, Q., Yang, X., Zhu, Z., Tang, G., & Wakin, M. B. (2019) · IEEE International Workshop on Computational Advances in Multi-Sensor Adaptive Processing · doi:10.1109/camsap45676.2019.9022447 · Cited by 3
Bilinear inverse problems with sparsity: Optimal identifiability conditions and efficient recovery
Li, Y. (2018) · Illinois Digital Environment for Access to Learning and Scholarship (University of Illinois at Urbana-Champaign) · Cited by 3
A Sufficient Condition for Local Optima to be Globally Optimal
Zhou, F., & Low, S. H. (2020) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc42340.2020.9303868 · Cited by 3
Online Orthogonal Dictionary Learning Based on Frank–Wolfe Method
Xue, Y., & Lau, V. K. N. (2021) · IEEE Transactions on Neural Networks and Learning Systems · doi:10.1109/tnnls.2021.3131181 · Cited by 3
“Another method is to restrict the dictionary over the orthogonal group O(N, R) and solve the following optimization problem only for the dictionary [6]–[8]”
MethodResultData clustering based on the modified relaxation Cheeger cut model
Yang, Y.-F., Zhou, H., & Zhou, B. (2022) · Computational and Applied Mathematics · doi:10.1007/s40314-022-01757-x · Cited by 3
“Recently, it was extended to solve the eigenfunction of the nonlinear functions in Feld et al. (2019), Lellmann et al. (2013) and Sun et al. (2017), where this problem was solved through employing some gradient flow methods.”
MethodAdaptive Trust-Region Method on Riemannian Manifold
Zhao, S., Yan, T., Wang, K., & Zhu, Y. (2023) · Journal of Scientific Computing · doi:10.1007/s10915-023-02288-1 · Cited by 3
“spaces, and it can be applied in many different fields, such as low-rank matrix completion [1, 2], phase retrieval [3–5], phase synchronization [6, 7], blind deconvolution [8], and dictionary learning [9, 10] and so on.”
BackgroundData‐driven methods for quantitative imaging
Dong, G., Flaschel, M., Hintermüller, M., Papafitsoros, K., Sirotenko, C., & Tabelow, K. (2024) · GAMM-Mitteilungen · doi:10.1002/gamm.202470014 · Cited by 3
“In [194, 195] the structure of minimizers and stationary points is studied.”
Robust Second-Order Nonconvex Optimization and Its Application to Low Rank Matrix Sensing
Li, S., Cheng, Y., Diakonikolas, I., Diakonikolas, J., Ge, R., & Wright, S. J. (2023) · neural information processing systems · doi:10.52202/075280-2369 · Cited by 3
Analysis of Fast Alternating Minimization for Structured Dictionary Learning
Ravishankar, S., Ma, A., & Needell, D. M. (2018) · Information Theory and Applications Workshop (ITA) · doi:10.1109/ita.2018.8503246 · Cited by 3
Recovering Structured Low-rank Operators Using Nuclear Norms
Bruer, J. J. (2017) · CaltechTHESIS (California Institute of Technology) · doi:10.7907/z9f18wqs · Cited by 3
Machine Learning: Why Do Simple Algorithms Work So Well?
Jin, C. (2019) · UC Berkeley · Cited by 3
A Line-Search Descent Algorithm for Strict Saddle Functions with Complexity GuaranteesPreprint
O’Neill, M. J., & Wright, S. J. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2006.07925 · Cited by 3
Lecture notes on non-convex algorithms for low-rank matrix recoveryPreprint
Waldspurger, I. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2105.10318 · Cited by 3
IB-AdCSCNet:Adaptive Convolutional Sparse Coding Network Driven by Information BottleneckPreprint
Zou, H., Qin, M., Song, Y., & Yang, X. (2024) · arXiv (Cornell University) · doi:10.48550/arxiv.2405.14192 · Cited by 3
“CSC model based on sparse representation theory[6, 7, 8, 9, 10], It is assumed that the input signal can be represented by a small number of atoms in the dictionary, leading to excellent performance in data compression and representation.”
MethodUnderstanding the Implicit Regularization of Gradient Descent in Over-parameterized ModelsPreprint
Ma, J., Liang, G., & Fattahi, S. (2025) · arXiv (Cornell University) · doi:10.48550/arxiv.2505.17304 · Cited by 3
On the Complexity of Optimization: Curved Spaces and Benign Landscapes
Criscitiello, C. (2025) · Infoscience (Ecole Polytechnique Fédérale de Lausanne) · doi:10.5075/epfl-thesis-11173 · Cited by 3
Primal-Dual Methods for Nonsmooth Nonconvex Optimization with Orthogonality ConstraintsPreprint
Zhu, L., Ding, W., Liu, S., & So, A. M. (2026) · arXiv (Cornell University) · doi:10.48550/arxiv.2604.04130 · Cited by 3
“…applications across scientific and engineering domains, including principal component analysis [JC16, JNRS10, WLS23], low-rank matrix completion [KMO10, Van13], group synchronization [Lin22, LYS23, ZLS23], dictionary learning [SQW16, CS16], and deep learning [SMG14, ASB16, KD18], among others.”
Qiu, J., Ma, B., Milzarek, A., & Zhang, J. (2026) · arXiv (Cornell University) · doi:10.48550/arxiv.2608.03001 · Cited by 3
“This property appears in many structured nonconvex landscapes, including the eigenvector problem and PCA [71], orthogonal tensor decomposition [27], dictionary learning [73], phase retrieval [72], and low-rank matrix recovery [13].”
Multichannel Sparse Blind Deconvolution on the Sphere
Li, Y., & Bresler, Y. (2019) · IEEE International Conference on Acoustics Speech and Signal Processing · doi:10.1109/icassp.2019.8683334 · Cited by 2
Gradient Descent Converges to Minimizers: Optimal and Adaptive Step-Size Rules
Shi, B., & Iyengar, S. S. (2019) · Springer eBooks · doi:10.1007/978-3-030-17076-9_7 · Cited by 2
Shen, C., Mi, L., & Zhang, L. (2021) · Optimization · doi:10.1080/02331934.2021.1958809 · Cited by 2
“In this paper, we focus on the problem (1) which has a role in the applications in, for example, sparse null space problems [16], sparse principal component analysis [17–19], complete dictionary recovery [20,21], signal processing [22], motion and structure recovery [23,24].”
BackgroundShi, B., & Iyengar, S. S. (2019) · Springer eBooks · doi:10.1007/978-3-030-17076-9_3 · Cited by 2
Perturbed gradient descent with occupation time.Preprint
Guo, X., Han, J., & Tang, W. (2020) · arXiv (Cornell University) · Cited by 2
Convex Sparse Blind DeconvolutionPreprint
Sun, Q., & Donoho, D. L. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2106.07053 · Cited by 2
Personalized Federated Learning via Maximizing Correlation with Sparse and Hierarchical ExtensionsPreprint
YinchuanLi, XiaofengLiu, XuZhang, YunfengShao, QingWang, & YanhuiGeng (2021) · arXiv (Cornell University) · Cited by 2
Achour, E. M., Malgouyres, F., & Gerchinovitz, S. (2021) · HAL · Cited by 2
Leader Stochastic Gradient Descent for Distributed Training of Deep Learning Models: ExtensionPreprint
Teng, Y., Gao, W., Chalus, F., Choromanska, A., Goldfarb, D., & Weller, A. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1905.10395 · Cited by 2
Decentralized Complete Dictionary Learning via $\ell^{4}$-Norm MaximizationPreprint
Lu, Q., & Lian, L. (2022) · arXiv (Cornell University) · doi:10.48550/arxiv.2211.03628 · Cited by 2
Gradient descent in matrix factorization: Understanding large initializationPreprint
Chen, H., Chen, X., Elmasri, M., & Sun, Q. (2023) · arXiv (Cornell University) · doi:10.48550/arxiv.2305.19206 · Cited by 2
“Previous studies have approached this issue through various angles, including examing the optimization landscape [Sun et al., 2016, 2018, Zhu et al., 2021] and directly conducting convergence analyses [Ma et al., 2018, Chen et al., 2019, Stöger and Soltanolkotabi, 2021].”
BackgroundLocal Minima in Mixture Problems and their Algorithmic Implications
Qian, W. (2020) · eCommons (Cornell University) · doi:10.7298/jjj2-wa43 · Cited by 2
Principles and Practice of Deep Representation Learning: or a Mathematical Theory of MemoryPreprint
Buchanan, S., Pai, D., Wang, P., & Ma, Y. (2026) · arXiv (Cornell University) · doi:10.48550/arxiv.2606.06624 · Cited by 2
Encoder Blind Combinatorial Compressed Sensing
Murray, M., & Tanner, J. (2022) · IEEE Transactions on Information Theory · doi:10.1109/tit.2022.3189278 · Cited by 1
Frank, N. B., Pughe-Sanford, J. L., & Grauer, S. J. (2026) · Journal of Computational Physics · doi:10.1016/j.jcp.2026.115114 · Cited by 1
“However, in many high dimensional problems, such as dictionary learning [57], tensor decomposition [58], matrix completion [59], and training certain (restrictive) classes of neural networks [60], all minima are global minima with the same loss.”
CSCCap: Plugging Sparse Coding in Zero-Shot Image Captioning
Song, Y. G., Yang, X., Huang, R., Haifeng, B., & Yang, L. (2024) · ACM International Conference on Multimedia in Asia (MMAsia) · doi:10.1145/3696409.3700286 · Cited by 1
“They serve as powerful tools for analyzing natural images, offering good theoretical interpretability and biological plausibility [21].”
Signal Recovery with Non-Expansive Generative Network Priors
Cocola, J. (2022) · neural information processing systems · doi:10.52202/068431-1674 · Cited by 1
Implicit regularization and solution uniqueness in over-parameterized matrix sensingPreprint
Geyer, K., Kyrillidis, A., & Kalev, A. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1806.02046 · Cited by 1
“ient descent does not introduce spurious local minima in matrix completion [19] and matrix sensing [20, 21], and all local minima are global in some tensor decompositions [22] and dictionary learning [23]; see [24, 25] for a complete overview of these results. Further, there is literature that characterizes the landsc…”
Hitting Time of Stochastic Gradient Langevin Dynamics to Stationary Points: A Direct Analysis.Preprint
Chen, X., Du, S. S., & Tong, X. T. (2019) · arXiv (Cornell University) · Cited by 1
Non-Convex Compressed Sensing with Training DataPreprint
Welper, G. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2101.08310 · Cited by 1
“These include optimization over spheres by trust-region methods [51, 52], (cid:96) 4 -norm maximization [60], combinations of clustering and alternating minimization [1], [9, 5, 8] and tensor decompositions [10].”
MethodDictionary and prior learning with unrolled algorithms for unsupervised inverse problemsPreprint
Malézieux, B., Moreau, T., & Kowalski, M. (2021) · HAL · Cited by 1
Personalized Federated Learning via Maximizing Correlation with Sparse and Hierarchical Extensions.Preprint
Li, Y., Liu, X., Zhang, X., Shao, Y., Wang, Q., & Geng, Y. (2021) · arXiv (Cornell University) · Cited by 1
Escaping From Saddle Points Using Asynchronous Coordinate Gradient DescentPreprint
Bornstein, M., Liu, J.-P., Li, J., & Huang, F. (2022) · arXiv (Cornell University) · doi:10.48550/arxiv.2211.09908 · Cited by 1
Malézieux, B. (2023) · theses.fr (ABES) · doi:10.70675/a70b21f1zb6a6z44e2z86f0z4b89290dcb97 · Cited by 1
Noise is All You Need: Private Second-Order Convergence of Noisy SGDPreprint
Avdiukhin, D., Dinitz, M., Fan, C., & Yaroslavtsev, G. (2024) · arXiv (Cornell University) · doi:10.48550/arxiv.2410.06878 · Cited by 1
“In many cases, local minima are global minima (see e.g. Sun et al. [2017], Ge et al. [2016], Kawaguchi [2016]), and hence DP-SGD is capable of finding high-quality solutions while preserving privacy.”
BackgroundAboussalah, A. M., & Abbahaddou, Y. (2024) · arXiv (Cornell University) · doi:10.48550/arxiv.2412.11292 · Cited by 1
Perspectives on Geometry and Optimization: from Measures to Neural Networks
Colmenares, F. S. (2023) · DSpace@MIT (Massachusetts Institute of Technology) · Cited by 1
Improved Global Landscape Guarantees for Low-rank Factorization in SynchronizationPreprint
Ling, S. (2026) · arXiv (Cornell University) · doi:10.48550/arxiv.2601.20292 · Cited by 1
“Most of these aforementioned works such as [43, 19, 42, 34] focus on understanding how the landscape depends on the data sample size, and aim to derive a near-optimal bound on the sample size to guarantee a benign landscape that is similar to its population counterpart.”
A Gaussian smoothing-based zeroth-order method for Goldstein second-order stationarityPreprint
Lei, M., Pong, T. K., Yue, M., Zeng, L., & Zhang, H. (2026) · arXiv (Cornell University) · doi:10.48550/arxiv.2607.21258 · Cited by 1
“…for many smooth nonconvex problems arising in modern applications, such as phase retrieval [30, 48], low-rank matrix recovery [4, 15, 51] and dictionary learning [47], it has been shown that all second-order stationary points are global minimizers, while first-order stationary points need not be.”
When is sparse dictionary learning well-posed?Preprint
Garfinkle, C. J., & Hillar, C. J. (2016) · arXiv (Cornell University)
First Order Methods for Nonconvex Optimization via Symmetric Factorization
Zheng, Q. (2017) · Knowledge@UChicago (University of Chicago) · doi:10.6082/m1319t0f
Blind Signal Detection for Sparse Massive MIMO: Degrees of Freedom and Achievable Rates
Zhang, J., Yuan, X., & Zhang, Y. A. (2017) · Globecom · doi:10.1109/glocom.2017.8254877
One-dimensional system arising in stochastic gradient descent
Karatapanis, K. (2021) · Advances in Applied Probability · doi:10.1017/apr.2020.10
Dictionary Learning and Sparse Coding on Statistical ManifoldsPreprint
Chakraborty, R., Banerjee, M., & Vemuri, B. C. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1805.02505
“For further discussion on this topic and the problem of complete dictionary recovery over a sphere, we refer the readers to [47], where authors provide a provably convergent algorithm.”
BackgroundNon-convex methods for spectrally sparse signal reconstruction via low-rank Hankel matrix completion
Wang, T., Zhu, X., Stewart, D. E., Cai, J., Xu, W., & Han, W. (2018) · doi:10.17077/etd.mgxvcx2i
A Mathematical Framework on Machine Learning: Theory and Application
Shi, B. (2018) · FIU - Digital Commons (Florida International University) · doi:10.25148/etd.fidc007030
The Local Geometry of Orthogonal Dictionary Learning using L1 Minimization
Li, Q., Zhu, Z., Wakin, M. B., & Tang, G. (2019) · Asilomar Conference on Signals, Systems and Computers (ACSSC) · doi:10.1109/ieeeconf44664.2019.9049030
“− Another line of work [6], [8], [12] recover the columns of the ground-truth dictionary one by one from the unit spheres.”
BackgroundThe Permuted Striped Block Model and its Factorization - Algorithms with Recovery Guarantees.Preprint
Murray, M., & Tanner, J. (2020) · arXiv (Cornell University)
Operator Splitting Methods for Convex and Nonconvex Optimization
Liu, Y. (2020) · eScholarship (California Digital Library)
Computational and Statistical Aspects of High-Dimensional Structured Estimation
Chen, S. (2018) · University of Minnesota Digital Conservancy (University of Minnesota)
Fattahi, S. (2020) · eScholarship (California Digital Library)
Provable and Efficient Algorithms for Federated, Batch and Reinforcement Learning
Ghosh, A. (2021) · eScholarship (California Digital Library)
Dictionary Learning for the Almost-Linear Sparsity RegimePreprint
Novikov, A., & White, S. (2022) · arXiv (Cornell University) · doi:10.48550/arxiv.2210.10855
“…have not been widely employed in subsequent attempts to solve dictionary learning in the linear ( s ∼ M ) sparsity regime, with practitioners instead turning to more technical machinery such as the sum-of-squares hierarchy [Barak et al., 2015] or Riemannian trust-regions [Sun et al., 2017a,b].”
BackgroundLearning Trees of $\ell_0$-Minimization ProblemsPreprint
Welper, G. (2023) · arXiv (Cornell University) · doi:10.48550/arxiv.2302.02548
“Given that Y contains sufficiently many independent samples form the class C<t, sparse factorization algorithms [2, 23, 41, 1, 6, 4, 35, 5, 8, 38, 42, 43, 36, 55] can recover the matrices X and Z up to scaling Γ and permutation P .”
BackgroundData-driven methods for quantitative imagingPreprint
Dong, G., Flaschel, M., Hintermüller, M., Papafitsoros, K., Sirotenko, C., & Tabelow, K. (2024) · arXiv (Cornell University) · doi:10.34657/33658
Efficient Matrix Factorization Via Householder ReflectionsPreprint
Dash, A., & Siripuram, A. (2024) · arXiv (Cornell University) · doi:10.48550/arxiv.2405.07649
DIST-CURE: A Robust Distributed Learning Algorithm with Cubic Regularized Newton
Ghosh, A., Maity, R. K., & Mazumdar, A. (2024) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit57864.2024.10619481
“In fact, in many problems of interest, all local minima are global minima (e.g., dictionary learning [17], phase retrieval [14], matrix sensing and completion [11], [16], and some of neural nets [12]).”
BackgroundManifold Quadratic Penalty Alternating Minimization for Sparse Principal Component AnalysisPreprint
Adam, T. (2024) · arXiv (Cornell University) · doi:10.48550/arxiv.2411.06654
“Problems of the form (1) arise in many applications such as unsupervised feature selection [3], [4], dictionary learning [5], [6], sparse blind deconvolution [7], compressed modes [8], and sparse principal component analysis [9]–[11].”
BackgroundImplicit Regularization of Gradient Descent in Realistic Settings
Ma, J. (2025) · Deep Blue (University of Michigan) · doi:10.7302/25524
Qi, A., Huang, J., Yang, L., & Huang, C. (2025) · arXiv (Cornell University) · doi:10.48550/arxiv.2510.19408
“Moreover, in tasks like dictionary learning and robust subspace recovery, one often encounters the need to minimize a positively homogeneous convex function over ℓ 2 or ℓ ∞ spheres, e.g., see [1, 36, 40, 45] and the references therein.”
Sharper Convergence Rates for Nonconvex Optimisation via Reduction Mappings
Markou, E., Ajanthan, T., & Gould, S. J. (2025) · neural information processing systems · doi:10.52202/085713-2995
From matrix factorisation to signal propagation in deep learning: algorithms and guarantees
Murray, M. (2021) · Oxford University Research Archive (ORA) (University of Oxford) · doi:10.5287/ora-2axq7xj2y
Advances in Optimization on Riemannian Manifolds
Li, J. (2023) · eScholarship (California Digital Library)
Provably Efficient Algorithms for Non-convex Optimization with Benign Structures
Zhang, H. (2024) · eScholarship (California Digital Library)
Topics in non-convex optimization and learning
Zhang, H. (2019) · DSpace@MIT (Massachusetts Institute of Technology)
Safe Online Decision-Making for Non-Stationary Systems
Ding, Y. (2023) · eScholarship (California Digital Library)
Sparsified Calibration: Ensuring Channel Sparsity in Massive MIMO Systems
Yang, F., Cai, C., Xue, Z., Wang, Y., Zhu, H., & Gao, X. (2026) · IEEE Transactions on Vehicular Technology · doi:10.1109/tvt.2026.3669604
“Firstly, due to the bilinear mapping: ( Φ , b u ) (cid:10)→ Φ b u , the problem in (16) is typically non-convex [54].”
Accelerated gradient dynamics on Riemannian manifolds: faster rate and trajectory convergence
Natu, T., Castera, C., Fadili, J. M., & Ochs, P. (2026) · Optimization · doi:10.1080/02331934.2026.2642342
“…Karcher-mean problem (Bini and Iannazzo, 2013), semidefinite programming (Burer and Mon-teiro, 2005), Gaussian Mixture Models (Hosseini and Sra, 2015), dictionary learning (Sun et al., 2016), matrix completion (Vandereycken, 2013) and statistical shape analysis (Ring and Wirth, 2012) among others.”
Achour, E. M. (2022) · theses.fr (ABES) · doi:10.70675/844f7ddaz4abbz4c26z83d3z9a3ce9519a42
Model Order Reduction of Switched Systems on Riemannian Manifold
Jiang, Y., Wang, W., & Miao, Z. (2026) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2026.3689328
“The key branch of manifold optimization, Riemannian manifold optimization, has gained much attention due to applications in low-rank matrix completion, phase retrieval, and phase synchronization [30], [31].”
He, C., Zhang, X., & Shin, F. C. P. (2026) · arXiv (Cornell University) · doi:10.48550/arxiv.2607.10764
“Riemannian optimization on the unit torus has become a standard approach for constant-modulus beam synthesis [26], [27], but its performance relative to unconstrained beamforming in sparse near-field satellite arrays is not yet well understood.”
Jointly Sparse Blind Deconvolution via Riemannian OptimizationPreprint
Wang, W., Guo, B., Yang, Z., Chen, S., & Shi, J. (2026) · arXiv (Cornell University) · doi:10.48550/arxiv.2608.04465
Over-parameterized low-rank matrix estimation: Theory, algorithms, applications
Zhang, J. (2025) · Illinois Digital Environment for Access to Learning and Scholarship (University of Illinois at Urbana-Champaign)
Recursive Gradient Retraction Methods for Stochastic Nonconvex Optimization on Stiefel ManifoldsPreprint
Yuan, Z., Sun, L., & Yuan, G. (2026) · arXiv (Cornell University) · doi:10.48550/arxiv.2610.19944
“In dictionary learning, spherical and orthogonal-group formulations are used to identify complete dictionaries from sparsely generated observations [47,55].”
Díaz, M., Trillos, N. G., López-Castaño, D., & Yang, C. (2026) · arXiv (Cornell University) · doi:10.48550/arxiv.2610.36581
Yuan, J., & Yan, T. (2026) · Mathematics · doi:10.3390/math14214098
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.