Online dictionary learning for sparse coding

Julien MairalFrancis BachJean PonceGuillermo Sapiro

article2009ICML2,475 citationsTest of Time Award

Develops an online dictionary learning algorithm based on stochastic approximations that efficiently scales to millions of training samples without requiring learning rate tuning, backed by convergence proofs and demonstrated on large-scale image restoration tasks.

Listen

The article addresses the challenge of learning dictionaries for sparse coding, a technique that represents signals as sparse combinations of basis elements and has proven effective for image and audio processing tasks. Traditional batch methods struggle with the massive training sets common in these domains, often involving millions of samples, leading to high computational costs and memory demands that limit practical use.

The article set out to develop and validate an online algorithm that learns dictionaries by processing data sequentially, minimizing the expected reconstruction cost rather than just fitting a finite set exactly. It casts dictionary learning as optimizing a non-convex objective over a convex constraint set and solves it through stochastic approximations that update a quadratic surrogate function at each step.

The approach alternates sparse coding of incoming samples with efficient block-coordinate dictionary updates that reuse prior computations, avoiding explicit learning-rate tuning. Experiments drew on over a million patches from the Berkeley segmentation dataset across three sizes and applied the method to inpainting a 12-megapixel image; convergence was proven under standard assumptions on data support and solution uniqueness.

The online method reached lower objective values faster than batch alternatives on every tested dataset size, often by orders of magnitude on a log-time scale, and matched or exceeded carefully tuned stochastic gradient descent without parameter search. It produced usable dictionaries for large-scale inpainting in roughly eight minutes on modest hardware and scaled gracefully beyond the reach of prior second-order batch procedures.

These results indicate that online dictionary learning can make state-of-the-art sparse representations practical for video streams and other dynamic, high-volume data while lowering barriers to real-time or large-image applications. The gains matter most where training time or memory currently constrain adoption in restoration, classification, or compression pipelines.

The article recommends deploying the algorithm for video restoration and extending it to discriminative losses and matrix factorizations such as sparse PCA. Further work should include broader empirical comparisons on standard restoration benchmarks and handling of time-varying data streams.

The analysis assumes bounded data density and conditions that guarantee unique sparse codes after a few iterations; results may be sensitive to poor initial dictionaries, and the full convergence proof covers only the basic version. Confidence is high for the reported image-patch tasks but should be tempered when extrapolating to domains that violate the stated assumptions.

Ecole Normale Supérieure INRIA University of Minnesota coding scheme sparse approximations online dictionary learning sparse coding sparse representations

getspams/spams-devel Mairal et al (2009).pdf

Paper: Efficient sparse coding algorithms, Honglak Lee et al. (2006). Introduces efficient alternating optimization algorithms for L1-regularized sparse coding and basis learning, establishing the computational framework that online dictionary learning speeds up.
Paper: Emergence of simple-cell receptive field properties by learning a sparse code for natural images, Bruno A. Olshausen et al. (1996). Pioneers the unsupervised learning of sparse linear codes for natural image patches, providing the foundational formulation underlying dictionary learning.
Paper: Non-negative Matrix Factorization with Sparseness Constraints, Patrik O. Hoyer (2004). Formulates matrix factorization under explicit sparseness constraints, serving as key background for constrained dictionary optimization.
Paper: Online Passive-Aggressive Algorithms, K. Crammer et al. (2003). Presents core online learning principles and sequential update strategies that motivate streaming stochastic approximations for large-scale datasets.

Paper: Online Learning for Matrix Factorization and Sparse Coding, Julien Mairal et al. (2010). Expands the online dictionary learning framework to general matrix factorizations, including non-negative matrix factorization and sparse PCA with convergence proofs.
Paper: Learning Fast Approximations of Sparse Coding, Karol Gregor et al. (2010). Directly tackles the per-sample sparse coding bottleneck of dictionary learning by training feed-forward neural networks like LISTA to approximate sparse codes rapidly.
Paper: Locality-constrained Linear Coding for image classification, Jinjun Wang et al. (2010). Extends standard sparse coding dictionary formulations by incorporating locality constraints to improve computational efficiency and performance in image classification.
Paper: Sparse Subspace Clustering: Algorithm, Theory, and Applications, Ehsan Elhamifar et al. (2012). Applies sparse representation and self-expressiveness optimization principles to the problem of clustering high-dimensional data lying across multiple subspaces.
Paper: Image Super-Resolution Using Deep Convolutional Networks, Chao Dong et al. (2014). Reformulates classical sparse-coding-based image super-resolution and restoration pipelines into end-to-end trained deep convolutional neural networks.

Cover for Online dictionary learning for sparse coding

Abstract

Sparse coding—that is, modelling data vectors as sparse linear combinations of basis elements—is widely used in machine learning, neuroscience, signal processing, and statistics. This paper focuses on learning the basis set, also called dictionary, to adapt it to specific data, an approach that has recently proven to be very effective for signal reconstruction and classification in the audio and image processing domains. This paper proposes a new online optimization algorithm for dictionary learning, based on stochastic approximations, which scales up gracefully to large datasets with millions of training samples. A proof of convergence is presented, along with experiments with natural images demonstrating that it leads to faster performance and better dictionaries than classical batch algorithms for both small and large datasets. like decompositions based on principal component analysis and its variants, these models do not impose that the basis vectors be orthogonal, allowing more flexibility to adapt the representation to the data. While learning the dictionary has proven to be critical to achieve (or improve upon) state-of-the-art results, effectively solving the corresponding optimization problem is a significant computational challenge, particularly in the context of the large-scale datasets involved in image processing tasks, that may include millions of training samples. Addressing this challenge is the topic of this paper. Concretely, consider a signal x in R^m. We say that it admits a sparse approximation over a dictionary D in R^{m×k}, with k columns referred to as atoms, when one can find a linear combination of a “few” atoms from D that is “close” to the signal x. Experiments have shown that modelling a signal with such a sparse decomposition (sparse coding) is very effective in many signal processing applications (Chen et al., 1999). For natural images, predefined dictionaries based on various types of wavelets (Mallat, 1999) have been used for this task. However, learning the dictionary instead of using off-the-shelf bases has been shown to dramatically improve signal reconstruction (Elad & Aharon, 2006). Although some of the learned dictionary elements may sometimes “look like” wavelets (or Gabor filters), they are tuned to the input images or signals, leading to much better results in practice. Most recent algorithms for dictionary learning (Olshausen & Field, 1997; Aharon et al., 2006; Lee et al., 2007) are second-order iterative batch procedures, accessing the whole training set at each iteration in order to minimize a cost function under some constraints. Although they have shown experimentally to be much faster than first-order gradient descent methods (Lee et al., 2007), they cannot effectively handle very large training sets (Bottou & Bousquet, 2008), or dynamic training data changing over time,

Topics

coding scheme sparse approximations

Keywords

online dictionary learning sparse coding sparse representations overcomplete dictionaries basis pursuit stochastic approximations matrix factorization soft thresholding image restoration signal reconstruction

1. Introduction
1.1. Contributions
2. Problem Statement
3. Online Dictionary Learning
3.1. Algorithm Outline
3.2. Sparse Coding
3.3. Dictionary Update
3.4. Optimizing the Algorithm
4. Convergence Analysis
4.1. Assumptions
4.2. Main Results and Proof Sketches
5. Experimental Validation
5.1. Performance evaluation
5.2. Application to Inpainting
6. Discussion
Acknowledgments
References

Knowls

Knowl 1 — Formulation of Sparse Coding and Dictionary Learning
model/method
Dictionary learning models a signal $x \in \mathbb{R}^m$ as a sparse linear combination of atoms from a dictionary matrix $D = [d_1, \dots, d_k] \in \mathbb{R}^{m \times k}$ . For a given signal $x$ and dictionary $D$ , the loss function $l(x, D)$ is defined as the optimal value of the $\ell_1$ -sparse coding problem:

$l(x, D) \triangleq \min_{\alpha \in \mathbb{R}^k} \frac{1}{2} \|x - D\alpha\|_2^2 + \lambda \|\alpha\|_1$

where $\lambda \in \mathbb{R}$ is a positive regularization parameter and $\alpha \in \mathbb{R}^k$ is the sparse decomposition vector. To prevent $D$ from becoming arbitrarily large (which would artificially diminish $\alpha$ ), each column $d_j$ of $D$ is constrained to have an $\ell_2$ -norm less than or equal to one. The constraint set is the convex set:

$\mathcal{C} \triangleq \left\{ D \in \mathbb{R}^{m \times k} \text{ s.t. } \forall j = 1, \dots, k, \; d_j^T d_j \le 1 \right\}$

Given signals drawn from a probability distribution $p(x)$ , the goal of dictionary learning is to minimize the expected cost function:

$f(D) \triangleq \mathbb{E}_x[l(x, D)] = \lim_{n \to \infty} \frac{1}{n} \sum_{i=1}^n l(x_i, D) \quad \text{almost surely}$

over the constraint set $\mathcal{C}$ .
Knowl 2 — Online Dictionary Learning Algorithm
algorithm
The online dictionary learning algorithm iteratively processes training signals one by one (or in mini-batches), alternating between sparse coding of the current sample and updating the dictionary using accumulated summary matrices. At iteration $t$ , the algorithm computes the sparse representation $\alpha_t$ of signal $x_t \in \mathbb{R}^m$ using the dictionary $D_{t-1} \in \mathcal{C} \subset \mathbb{R}^{m \times k}$ from the previous step via the LARS algorithm, accumulates the outer products into statistics matrices $A_t \in \mathbb{R}^{k \times k}$ and $B_t \in \mathbb{R}^{m \times k}$ , and updates $D_t$ by minimizing the aggregate quadratic surrogate function $\hat{f}_t(D) \triangleq \frac{1}{t} \sum_{i=1}^t (\frac{1}{2}\|x_i - D\alpha_i\|_2^2 + \lambda \|\alpha_i\|_1) = \frac{1}{t}(\frac{1}{2}\text{Tr}(D^T D A_t) - \text{Tr}(D^T B_t)) + \text{const}$ with warm restart $D_{t-1}$ .
Input: Distribution $p(x)$ or streaming data $x \in \mathbb{R}^m$ , regularization parameter $\lambda \in \mathbb{R}$ , initial dictionary $D_0 \in \mathbb{R}^{m \times k}$ , number of iterations $T$ .
Output: Learned dictionary $D_T \in \mathbb{R}^{m \times k}$ .
Initialize $A_0 \leftarrow 0 \in \mathbb{R}^{k \times k}$ , $B_0 \leftarrow 0 \in \mathbb{R}^{m \times k}$
for $t = 1$ to $T$ do
    Draw sample $x_t \sim p(x)$
    Compute sparse code via LARS:
         $\alpha_t \leftarrow \arg\min_{\alpha \in \mathbb{R}^k} \frac{1}{2} \|x_t - D_{t-1}\alpha\|_2^2 + \lambda \|\alpha\|_1$
    Update statistics matrices:
         $A_t \leftarrow A_{t-1} + \alpha_t \alpha_t^T$
         $B_t \leftarrow B_{t-1} + x_t \alpha_t^T$
    Compute dictionary $D_t$ by column-wise block-coordinate descent using $D_{t-1}$ as warm restart:
         $D_t \leftarrow \arg\min_{D \in \mathcal{C}} \frac{1}{t} \left( \frac{1}{2} \text{Tr}(D^T D A_t) - \text{Tr}(D^T B_t) \right)$
end for
return $D_T$
Knowl 3 — Block-Coordinate Descent for Dictionary Column Updates
algorithm
The dictionary update step minimizes the quadratic surrogate cost $\frac{1}{2} \text{Tr}(D^T D A) - \text{Tr}(D^T B)$ over the convex set $\mathcal{C} = \{D = [d_1, \dots, d_k] \in \mathbb{R}^{m \times k} \mid d_j^T d_j \le 1, \forall j\}$ using block-coordinate descent. It updates each column $d_j$ sequentially while keeping all other columns fixed, guaranteeing convergence to a global optimum because the constraints are separable across columns. In practice, a single sweep over all columns $j = 1, \dots, k$ suffices when using the previous dictionary estimate as a warm restart.
Input: Current dictionary $D = [d_1, \dots, d_k] \in \mathbb{R}^{m \times k}$ , matrix $A = [a_1, \dots, a_k] \in \mathbb{R}^{k \times k}$ , matrix $B = [b_1, \dots, b_k] \in \mathbb{R}^{m \times k}$ .
Output: Updated dictionary $D \in \mathbb{R}^{m \times k}$ .
repeat
    for $j = 1$ to $k$ do
        Compute gradient update vector:
             $u_j \leftarrow \frac{1}{A_{jj}} (b_j - D a_j) + d_j$
        Project onto unit $\ell_2$ ball:
             $d_j \leftarrow \frac{1}{\max(\|u_j\|_2, 1)} u_j$
    end for
until convergence (or single iteration when warm restarted)
return $D$
Knowl 4 — Mini-Batch Extension and Statistics Rescaling
model/method
To improve convergence speed and computational efficiency, the online dictionary learning algorithm can draw mini-batches of $\eta > 1$ signals at each iteration $t$ , denoted $x_{t,1}, \dots, x_{t,\eta} \in \mathbb{R}^m$ , with corresponding sparse representations $\alpha_{t,1}, \dots, \alpha_{t,\eta} \in \mathbb{R}^k$ . The sufficient statistics matrices $A_t \in \mathbb{R}^{k \times k}$ and $B_t \in \mathbb{R}^{m \times k}$ are updated with a scaling factor $\beta$ :

$A_t \leftarrow \beta A_{t-1} + \sum_{i=1}^\eta \alpha_{t,i} \alpha_{t,i}^T$

$B_t \leftarrow \beta B_{t-1} + \sum_{i=1}^\eta x_{t,i} \alpha_{t,i}^T$

where $\beta \triangleq \frac{\theta + 1 - \eta}{\theta + 1}$ and $\theta$ is defined as:

$\theta \triangleq \begin{cases} t\eta & \text{if } t < \eta \\ \eta^2 + t - \eta & \text{if } t \ge \eta \end{cases}$

This weighting maintains asymptotic consistency with the convergence analysis while allowing empirical speedups of a factor of 10 or more (with typical values $\eta \in \{128, 256, 512\}$ ).
Knowl 5 — Assumptions for Convergence Analysis of Online Dictionary Learning
assumption
The convergence analysis of the online dictionary learning algorithm rests on three assumptions:
1. Assumption (A) - Compact Support: The data distribution admits a bounded probability density $p(x)$ with compact support $K \subset \mathbb{R}^m$ .
2. Assumption (B) - Lower-Bounded Hessians: The surrogate quadratic functions $\hat{f}_t$ are strictly convex with lower-bounded Hessians. Specifically, the smallest eigenvalue of the positive semi-definite matrix $\frac{1}{t} A_t$ is bounded below by a constant $\kappa_1 > 0$ for all $t$ , ensuring $A_t$ is invertible.
3. Assumption (C) - Uniqueness of Sparse Coding Solution: For all $x \in K$ and all dictionaries $D$ in the subset $\mathcal{S} \subset \mathcal{C}$ considered by the algorithm, if $\Lambda \triangleq \{j \in \{1,\dots,k\} \mid |d_j^T(x - D\alpha^\star)| = \lambda\}$ is the active set for the optimal sparse code $\alpha^\star$ , the smallest eigenvalue of $D_\Lambda^T D_\Lambda$ is greater than or equal to a constant $\kappa_2 > 0$ . This ensures $D_\Lambda^T D_\Lambda$ is invertible, guaranteeing uniqueness of the Lasso solution $\alpha^\star$ .
Knowl 6 — Almost Sure Convergence of the Objective and Surrogate Functions
theoretical result
Let $\hat{f}_t(D) \triangleq \frac{1}{t} \sum_{i=1}^t (\frac{1}{2} \|x_i - D\alpha_i\|_2^2 + \lambda \|\alpha_i\|_1)$ be the empirical surrogate function and $f(D) \triangleq \mathbb{E}_x[l(x, D)]$ be the expected cost. Under assumptions (A), (B), and (C):
1. The sequence of surrogate values $\hat{f}_t(D_t)$ converges almost surely.
2. The difference between the expected cost and the surrogate cost evaluated at $D_t$ satisfies:
$f(D_t) - \hat{f}_t(D_t) \xrightarrow{a.s.} 0$
1. The sequence of expected costs $f(D_t)$ converges almost surely.
Knowl 7 — Asymptotic Convergence to Stationary Points
theoretical result
Under assumptions (A), (B), and (C), the sequence of dictionaries $D_t$ produced by the online dictionary learning algorithm is asymptotically close to the set of stationary points of the dictionary learning objective function $f(D) = \mathbb{E}_x[l(x, D)]$ with probability one. Specifically, any accumulation point $D_\infty$ of the sequence $D_t$ satisfies the first-order optimality condition $- \nabla f(D_\infty) \in \mathcal{N}_\mathcal{C}(D_\infty)$ , where $\mathcal{N}_\mathcal{C}(D_\infty)$ is the normal cone of the convex set $\mathcal{C}$ at $D_\infty$ .

Knowl 8 — Experimental Evaluation on Natural Image Patch Datasets

experimental setup

The algorithm was evaluated on natural image patches sampled from the Berkeley segmentation dataset, using $10^6$ patches for training and $2.5 \times 10^5$ patches for testing across three configurations:

Patches are normalized to unit $\ell_2$ -norm, and the regularization parameter is fixed to $\lambda = 1.2 / \sqrt{m}$ , which empirically yields sparse representations with approximately 10 non-zero coefficients per patch. The mini-batch parameter was evaluated for powers of 2, with $\eta = 256$ selected as optimal.

Knowl 9 — Empirical Superiority of Online Dictionary Learning over Batch and SGD Methods
empirical result
Across all tested datasets (A, B, and C with $10^6$ training samples):
1. Online vs. Batch: The online dictionary learning algorithm systematically reaches lower test objective values in substantially less wall-clock computation time than batch coordinate descent methods run on subsets of sizes $n = 10^4, 10^5,$ or the full dataset $n = 10^6$ . The speedup is up to multiple orders of magnitude for a given objective precision.
2. Online vs. Stochastic Gradient Descent (SGD): Projected first-order SGD requires joint tuning of mini-batch size $\eta$ and learning rate $\rho$ (with optimal values $\rho = 10^4, \eta = 512$ ). In contrast, the proposed online algorithm is parameter-free regarding step size, converges as fast or faster than optimally-tuned SGD, and achieves lower asymptotic objective values on larger dictionary configurations (such as Dataset C).
Knowl 10 — Large-Scale 12-Megapixel Color Image Inpainting
empirical result
The online dictionary learning algorithm scaled directly to inpainting text overlaid on a 12-Megapixel color photograph. A dictionary of $k = 256$ atoms was trained on approximately $7 \times 10^6$ undamaged $12 \times 12$ RGB patches ( $m = 432$ ) in two epochs (around 500 seconds on an 8-core 2.4 GHz machine). Sparse coding over the learned dictionary successfully reconstructed the missing pixels under the overlaid text, demonstrating that the online algorithm can learn dictionaries from multi-million patch datasets directly on full-resolution imagery without memory bottlenecks.

Coverage note — Proof sketches and intermediate convergence lemmas were omitted in accordance with the rules, and heuristic tricks for handling fixed-size datasets and purging unused atoms were condensed into the core algorithmic knowls.

References

1.Aharon, M., & Elad, M. (2008). Sparse and redundant modeling of image content using an image-signature-dictionary. SIAM Imaging Sciences, 1, 228–247.
2.Aharon, M., Elad, M., & Bruckstein, A. M. (2006). The K-SVD: An algorithm for designing of overcomplete dictionaries for sparse representations. IEEE Transactions Signal Processing, 54, 4311-4322
3.Bertsekas, D. (1999). Nonlinear programming. Athena Scientific Belmont, Mass.
4.Bickel, P., Ritov, Y., & Tsybakov, A. (2007). Simultaneous analysis of Lasso and Dantzig selector. preprint.
5.Bonnans, J., & Shapiro, A. (1998). Optimization problems with perturbation: A guided tour. SIAM Review, 40, 202–227.
6.Borwein, J., & Lewis, A. (2006). Convex analysis and nonlinear optimization: theory and examples. Springer.
7.Bottou, L. (1998). Online algorithms and stochastic approximations. In D. Saad (Ed.), Online learning and neural networks.
8.Bottou, L., & Bousquet, O. (2008). The tradeoffs of large scale learning. Advances in Neural Information Processing Systems, 20, 161–168.
9.Chen, S., Donoho, D., & Saunders, M. (1999). Atomic decomposition by basis pursuit. SIAM Journal on Scientific Computing, 20, 33–61.
10.Efron, B., Hastie, T., Johnstone, I., & Tibshirani, R. (2004). Least angle regression. Annals of Statistics, 32, 407–499.
11.Elad, M., & Aharon, M. (2006). Image denoising via sparse and redundant representations over learned dictionaries. IEEE Transactions Image Processing, 54, 3736–3745.
12.Fisk, D. (1965). Quasi-martingale. Transactions of the American Mathematical Society, 359–388.
13.Friedman, J., Hastie, T., Hölfling, H., & Tibshirani, R. (2007). Pathwise coordinate optimization. Annals of Statistics, 1, 302–332.
14.Fu, W. (1998). Penalized Regressions: The Bridge Versus the Lasso. Journal of computational and graphical statistics, 7, 397–416.
15.Fuchs, J. (2005). Recovery of exact sparse representations in the presence of bounded noise. IEEE Transactions Information Theory, 51, 3601–3608.
16.Lee, H., Battle, A., Raina, R., & Ng, A. Y. (2007). Efficient sparse coding algorithms. Advances in Neural Information Processing Systems, 19, 801–808.
17.Mairal, J., Elad, M., & Sapiro, G. (2008). Sparse representation for color image restoration. IEEE Transactions Image Processing, 17, 53–69.
18.Mairal, J., Bach, F., Ponce, J., Sapiro, G., & Zisserman, A. (2009). Supervised dictionary learning. Advances in Neural Information Processing Systems, 21, 1033–1040.
19.Mallat, S. (1999). A wavelet tour of signal processing, second edition. Academic Press, New York.
20.Olshausen, B. A., & Field, D. J. (1997). Sparse coding with an overcomplete basis set: A strategy employed by V1? Vision Research, 37, 3311–3325.
21.Osborne, M., Presnell, B., & Turlach, B. (2000). A new approach to variable selection in least squares problems. IMA Journal of Numerical Analysis, 20, 389–403.
22.Protter, M., & Elad, M. (2009). Image sequence denoising via sparse and redundant representations. IEEE Transactions Image Processing, 18, 27–36.
23.Raina, R., Battle, A., Lee, H., Packer, B., & Ng, A. Y. (2007). Self-taught learning: transfer learning from unlabeled data. Proceedings of the 26th International Conference on Machine Learning, 759–766.
24.Tibshirani, R. (1996). Regression shrinkage and selection via the Lasso. Journal of the Royal Statistical Society Series B, 67, 267–288.
25.Van der Vaart, A. (1998). Asymptotic Statistics. Cambridge University Press.
26.Zou, H., & Hastie, T. (2005). Regularization and variable selection via the elastic net. Journal of the Royal Statistical Society Series B, 67, 301–320.

Citation

MLA

Mairal, J., et al. “Online Dictionary Learning for Sparse Coding”. Proceedings of the 26th Annual International Conference on Machine Learning, 2009, pp. 689–96, https://doi.org/10.1145/1553374.1553463.

APA

Mairal, J., Bach, F., Ponce, J., & Sapiro, G. (2009). Online dictionary learning for sparse coding. Proceedings of the 26th Annual International Conference on Machine Learning, 689–696. https://doi.org/10.1145/1553374.1553463

Chicago

Mairal, J., F. Bach, J. Ponce, and G. Sapiro. 2009. “Online Dictionary Learning for Sparse Coding”. Proceedings of the 26th Annual International Conference on Machine Learning, 689–96. https://doi.org/10.1145/1553374.1553463.

Harvard

Mairal, J. et al. (2009) “Online dictionary learning for sparse coding”, Proceedings of the 26th Annual International Conference on Machine Learning. ACM, pp. 689–696. Available at: https://doi.org/10.1145/1553374.1553463.

Vancouver

1. Mairal J, Bach F, Ponce J, Sapiro G (2009) Online dictionary learning for sparse coding. In: Proceedings of the 26th Annual International Conference on Machine Learning. ACM, pp 689–696

BibTeX

@inproceedings{Mairal_2009, series={ICML ’09}, title={Online dictionary learning for sparse coding}, url={http://dx.doi.org/10.1145/1553374.1553463}, DOI={10.1145/1553374.1553463}, booktitle={Proceedings of the 26th Annual International Conference on Machine Learning}, publisher={ACM}, author={Mairal, Julien and Bach, Francis and Ponce, Jean and Sapiro, Guillermo}, year={2009}, month=June, pages={689–696}, collection={ICML ’09} }

Metadata:Crossref

Source Code

This paper has an official code repository available. Click below to access the source code.

View Repository

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

License: Authors

Dataset	Signal size $m$	Number of atoms $k$	Type
A	$8 \times 8 = 64$	256	bw
B	$12 \times 12 \times 3 = 432$	512	color
C	$16 \times 16 = 256$	1024	bw

Online dictionary learning for sparse coding

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — Formulation of Sparse Coding and Dictionary Learning

Knowl 2 — Online Dictionary Learning Algorithm

Knowl 3 — Block-Coordinate Descent for Dictionary Column Updates

Knowl 4 — Mini-Batch Extension and Statistics Rescaling

Knowl 5 — Assumptions for Convergence Analysis of Online Dictionary Learning

Knowl 6 — Almost Sure Convergence of the Objective and Surrogate Functions

Knowl 7 — Asymptotic Convergence to Stationary Points