# Efficient Sparse Coding using Hierarchical Riemannian Pursuit

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 47 references that are in the map.
- First posted on arXiv 21 Apr 2021.

## Builds on (most cited first, 15 of 15)

- [Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview](https://mlsanity.com/paper/1809.09573/) (2018)
- [Matrix Completion has No Spurious Local Minimum](https://mlsanity.com/paper/1605.07272/) (2016)
- [Gradient Descent with Random Initialization: Fast Global Convergence for Nonconvex Phase Retrieval](https://mlsanity.com/paper/1803.07726/) (2018)
- [Complete Dictionary Recovery over the Sphere II: Recovery by Riemannian Trust-region Method](https://mlsanity.com/paper/1511.04777/) (2015)
- [Guaranteed Recovery of One-Hidden-Layer Neural Networks via Cross Entropy](https://mlsanity.com/paper/1802.06463/) (2018)
- [Complete Dictionary Recovery over the Sphere](https://mlsanity.com/paper/1504.06785/) (2015)
- [Subgradient Descent Learns Orthogonal Dictionaries](https://mlsanity.com/paper/1810.10702/) (2018)
- [Structured Local Optima in Sparse Blind Deconvolution](https://mlsanity.com/paper/1806.00338/) (2018)
- [Fast and robust tensor decomposition with applications to dictionary learning](https://mlsanity.com/paper/1706.08672/) (2017)
- [Nonconvex Low-Rank Matrix Recovery with Arbitrary Outliers via Median-Truncated Gradient Descent](https://mlsanity.com/paper/1709.08114/) (2017)
- [Efficient Dictionary Learning with Gradient Descent](https://mlsanity.com/paper/1809.10313/) (2018)
- [Manifold Gradient Descent Solves Multi-Channel Sparse Blind Deconvolution Provably and Efficiently](https://mlsanity.com/paper/1911.11167/) (2019)
- [Complete Dictionary Learning via ℓp-norm Maximization](https://mlsanity.com/paper/2002.10043/) (2020)
- [A Nonconvex Approach for Exact and Efficient Multichannel Sparse Blind Deconvolution](https://mlsanity.com/paper/1908.10776/) (2019)
- [Blind Data Detection in Massive MIMO via ℓ3-norm Maximization over the Stiefel Manifold](https://mlsanity.com/paper/2004.12301/) (2020)

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

- [Unique sparse decomposition of low rank matrices](https://mlsanity.com/paper/2106.07736/) (2021)
- [Optimal vintage factor analysis with deflation varimax](https://mlsanity.com/paper/2310.10545/) (2023)

## Abstract (arXiv)

Sparse coding is a class of unsupervised methods for learning a sparse representation of the input data in the form of a linear combination of a dictionary and a sparse code. This learning framework has led to state-of-the-art results in various image and video processing tasks. However, classical methods learn the dictionary and the sparse code based on alternating optimizations, usually without theoretical guarantees for either optimality or convergence due to non-convexity of the problem. Recent works on sparse coding with a complete dictionary provide strong theoretical guarantees thanks to the development of the non-convex optimization. However, initial non-convex approaches learn the dictionary in the sparse coding problem sequentially in an atom-by-atom manner, which leads to a long execution time. More recent works seek to directly learn the entire dictionary at once, which substantially reduces the execution time. However, the associated recovery performance is degraded with a finite number of data samples. In this paper, we propose an efficient sparse coding scheme with a two-stage optimization. The proposed scheme leverages the global and local Riemannian geometry of the two-stage optimization problem and facilitates fast implementation for superb dictionary recovery performance by a finite number of samples without atom-by-atom calculation. We further prove that, with high probability, the proposed scheme can exactly recover any atom in the target dictionary with a finite number of samples if it is adopted to recover one atom of the dictionary. An application on wireless sensor data compression is also proposed. Experiments on both synthetic and real-world data verify the efficiency and effectiveness of the proposed scheme.