# Subgradient Descent Learns Orthogonal Dictionaries

arXiv: https://arxiv.org/abs/1810.10702 · HTML: https://mlsanity.com/paper/1810.10702/

## Key facts

- Cited by 17 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 Oct 2018.

## Built on by (most cited first, 17 of 17)

- [The Power of Preconditioning in Overparameterized Low-Rank Matrix Sensing](https://mlsanity.com/paper/2302.01186/) (2023)
- [Scaling and Scalability: Provable Nonconvex Low-Rank Tensor Estimation from Incomplete Measurements](https://mlsanity.com/paper/2104.14526/) (2021)
- [Sign-RIP: A Robust Restricted Isometry Property for Low-rank Matrix Recovery](https://mlsanity.com/paper/2102.02969/) (2021)
- [NCVX: A General-Purpose Optimization Solver for Constrained Machine and Deep Learning](https://mlsanity.com/paper/2210.00973/) (2022)
- [Simple Alternating Minimization Provably Solves Complete Dictionary Learning](https://mlsanity.com/paper/2210.12816/) (2022)
- [NCVX: A User-Friendly and Scalable Package for Nonconvex Optimization in Machine Learning](https://mlsanity.com/paper/2111.13984/) (2021)
- [Closed-Loop Transcription via Convolutional Sparse Coding](https://mlsanity.com/paper/2302.09347/) (2023)
- [Riemannian Perspective on Matrix Factorization](https://mlsanity.com/paper/2102.00937/) (2021)
- [On the Uniform Convergence of Subdifferentials in Stochastic Optimization and Learning](https://mlsanity.com/paper/2405.10289/) (2024)
- [SPEAR++: Scaling Gradient Inversion via Sparsely-Used Dictionary Learning](https://mlsanity.com/paper/2510.24200/) (2025)
- [Efficient Sparse Coding using Hierarchical Riemannian Pursuit](https://mlsanity.com/paper/2104.10314/) (2021)
- [Convex Sparse Blind Deconvolution](https://mlsanity.com/paper/2106.07053/) (2021)
- [Optimal vintage factor analysis with deflation varimax](https://mlsanity.com/paper/2310.10545/) (2023)
- [Online Orthogonal Dictionary Learning Based on Frank-Wolfe Method](https://mlsanity.com/paper/2103.01484/) (2021)
- [Implicit Bias of Projected Subgradient Method Gives Provable Robust Recovery of Subspaces of Unknown Codimension](https://mlsanity.com/paper/2201.09079/) (2022)
- [Decentralized Complete Dictionary Learning via ℓ4-Norm Maximization](https://mlsanity.com/paper/2211.03628/) (2022)
- [Recovering Imbalanced Clusters via Gradient-Based Projection Pursuit](https://mlsanity.com/paper/2502.02668/) (2025)

## Abstract (arXiv)

This paper concerns dictionary learning, i.e., sparse coding, a fundamental representation learning problem. We show that a subgradient descent algorithm, with random initialization, can provably recover orthogonal dictionaries on a natural nonsmooth, nonconvex ℓ1 minimization formulation of the problem, under mild statistical assumptions on the data. This is in contrast to previous provable methods that require either expensive computation or delicate initialization schemes. Our analysis develops several tools for characterizing landscapes of nonsmooth functions, which might be of independent interest for provable training of deep networks with nonsmooth activations (e.g., ReLU), among numerous other applications. Preliminary experiments corroborate our analysis and show that our algorithm works well empirically in recovering orthogonal dictionaries.