Online Learning for Matrix Factorization and Sparse Coding

Julien MairalFrancis BachJean PonceGuillermo Sapiro

article2010JMLR2,704 citations

Introduces an online stochastic algorithm for sparse coding and dictionary learning that scales efficiently to millions of training samples with provable convergence guarantees across diverse matrix factorization tasks.

Listen

The article addresses the challenge of learning dictionaries for sparse coding on very large datasets, such as millions of image patches or genomic measurements, where classical batch matrix factorization methods become impractical due to memory and computation limits.

It sets out to develop and analyze an online algorithm, based on stochastic approximations, that solves dictionary learning and related matrix factorization problems by processing one sample or a small mini-batch at a time while guaranteeing almost-sure convergence to a stationary point.

The method alternates sparse coding steps solved by LARS with dictionary updates that minimize a quadratic surrogate function built from a few running sufficient statistics; the approach extends directly to non-negative matrix factorization, sparse PCA with elastic-net or fused-lasso constraints, and simultaneous sparse coding by changing only the projection or regularization steps.

On image-patch and face datasets ranging from thousands to a million samples, the algorithm reaches lower objective values faster than both batch coordinate-descent methods and carefully tuned stochastic gradient descent; it produces visually localized, interpretable atoms and scales to a 12-megapixel inpainting task in minutes. On breast-cancer CGH data it recovers biologically plausible sparse factors with correlation performance comparable to specialized penalized matrix decomposition.

These results show that online second-order information can be exploited without manual learning-rate schedules, making dictionary learning practical for dynamic or massive data streams while preserving theoretical guarantees under standard compactness and restricted-eigenvalue assumptions.

The main limitations are the lack of global optimality guarantees (common to all non-convex dictionary-learning formulations) and reliance on the data having bounded support and the surrogate Hessians remaining well-conditioned after a few iterations; users should therefore monitor atom usage and consider warm-start or continuation strategies when regularization is strong.

Next steps suggested by the work include applying the framework to video restoration with time-varying dictionaries and extending the loss to discriminative tasks such as classification, where overfitting risk is higher and larger-scale experiments will be needed to confirm generalization.

Ecole Normale Supérieure INRIA University of Minnesota matrix factorizations non-negative matrix factorization online learning matrix factorization sparse coding online learning

arXiv: 0908.0050 getspams/spams-devel

Paper: Online dictionary learning for sparse coding, J. Mairal et al. (2009). It provides the direct conference precursor and foundational stochastic surrogate framework that this extended journal article builds upon and generalizes.
Paper: Efficient sparse coding algorithms, Honglak Lee et al. (2006). It introduces standard alternating optimization formulations and active-set techniques for sparse coding that the source adapts into an online stochastic setting.
Paper: Online Convex Programming and Generalized Infinitesimal Gradient Ascent, Martin A. Zinkevich (2003). It establishes fundamental convergence principles and projection mechanisms for online convex programming that underpin stochastic optimization algorithms.
Paper: Non-negative Matrix Factorization with Sparseness Constraints, Patrik O. Hoyer (2004). It formulates matrix factorization subject to explicit sparsity and non-negativity constraints, which the source directly extends with online updating.
Paper: Algorithms for Non-negative Matrix Factorization, Daniel D. Lee et al. (2000). It defines classic batch non-negative matrix factorization and auxiliary function techniques that motivate the source's online surrogate updates.
Paper: Full regularization path for sparse principal component analysis, Alexandre d'Aspremont et al. (2007). It details sparse principal component analysis formulations whose regularized variants are adopted and made online in the source.

Paper: Learning Fast Approximations of Sparse Coding, Karol Gregor et al. (2010). It addresses the computational bottleneck of iterative sparse coding by training feed-forward neural networks to rapidly approximate sparse inference.
Paper: Locality-constrained Linear Coding for image classification, Jinjun Wang et al. (2010). It builds on dictionary coding representations by introducing locality constraints to enable fast analytical feature encoding for image classification.
Paper: Adaptive Subgradient Methods for Online Learning and Stochastic Optimization, John Duchi et al. (2011). It generalizes adaptive step-size schedules in online and stochastic optimization for sparse feature settings.
Paper: Sparse Subspace Clustering: Algorithm, Theory, and Applications, Ehsan Elhamifar et al. (2012). It uses sparse representation principles to construct self-expressive similarity graphs for clustering data in unions of subspaces.
Paper: Accelerating Stochastic Gradient Descent using Predictive Variance Reduction, Rie Johnson et al. (2013). It develops explicit variance reduction techniques that advance stochastic gradient convergence beyond basic online approximations.
Paper: Optimization Methods for Large-Scale Machine Learning, Léon Bottou et al. (2016). It provides a comprehensive theoretical survey of stochastic and second-order optimization methods for large-scale machine learning.

Cover for Online Learning for Matrix Factorization and 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 the large-scale matrix factorization problem that consists of learning the basis set, adapting it to specific data. Variations of this problem include dictionary learning in signal processing, non-negative matrix factorization and sparse principal component analysis. In this paper, we propose to address these tasks with a new online optimization algorithm, based on stochastic approximations, which scales up gracefully to large datasets with millions of training samples, and extends naturally to various matrix factorization formulations, making it suitable for a wide range of learning problems. A proof of convergence is presented, along with experiments with natural images and genomic data demonstrating that it leads to state-of-the-art performance in terms of speed and optimization for both small and large datasets.

1 Introduction
1.1 Contributions
1.2 Notation
2 Problem Statement
3 Online Dictionary Learning
3.1 Algorithm Outline
3.2 Sparse Coding
3.3 Dictionary Update
3.4 Optimizing the Algorithm
3.4.1 Handling Fixed-Size Data Sets
3.4.2 Scaling the “Past” Data
3.4.3 Mini-Batch Extension
3.4.4 Slowing Down the First Iterations
3.4.5 Purging the Dictionary from Unused Atoms
3.5 Link with Second-order Stochastic Gradient Descent
4 Convergence Analysis
4.1 Assumptions
4.2 Main Results
5 Extensions to Matrix Factorization
5.1 Using Different Regularizers for 𝜶{\boldsymbol{\alpha}}
5.2 Using Different Constraint Sets for 𝐃{\mathbf{D}}
5.3 Non Negative Matrix Factorization
5.4 Sparse Principal Component Analysis
5.5 Constrained Sparse Coding
5.6 Simultaneous Sparse Coding
6 Experimental Validation
6.1 Performance Evaluation for Dictionary Learning
6.1.1 Online vs. Batch
6.1.2 Comparison with Stochastic Gradient Descent
6.2 Non Negative Matrix Factorization and Non Negative Sparse Coding
6.3 Sparse Principal Component Analysis
6.3.1 Faces and Natural Patches
6.3.2 Genomic Data
6.4 Application to Large-Scale Image Processing
7 Conclusion
A Theorems and Useful Lemmas
B Efficient Projections Algorithms
B.1 A Linear-time Projection on the Elastic-Net Constraint
B.2 A Homotopy Method for Solving the Fused Lasso Signal Approximation
References

Knowls

Knowl 1 — Online Dictionary Learning Algorithm
algorithm
Online dictionary learning optimizes a dictionary $D \in \mathbb{R}^{m \times k}$ to represent data vectors $x \in \mathbb{R}^m$ drawn from a probability distribution $p(x)$ as sparse linear combinations of $k$ dictionary atoms (columns $d_1, \dots, d_k$ ). The algorithm alternates between sparse coding incoming signals over the current dictionary and updating the dictionary by minimizing a quadratic surrogate function using incrementally accumulated sufficient statistics.

Given a regularization parameter $\lambda \in \mathbb{R}$ , an initial dictionary $D_0 \in \mathcal{C} = \{D \in \mathbb{R}^{m \times k} \mid \forall j=1,\dots,k, d_j^T d_j \le 1\}$ , and iteration count $T$ :
1. A sample $x_t \in \mathbb{R}^m$ is drawn from $p(x)$ .
2. Sparse coding computes the code vector $\alpha_t \in \mathbb{R}^k$ via LARS-Lasso: $\alpha_t \triangleq \arg\min_{\alpha \in \mathbb{R}^k} \frac{1}{2} \|x_t - D_{t-1}\alpha\|_2^2 + \lambda \|\alpha\|_1$
3. Sufficient statistics matrices $A_t \in \mathbb{R}^{k \times k}$ and $B_t \in \mathbb{R}^{m \times k}$ are updated: $A_t \leftarrow A_{t-1} + \alpha_t \alpha_t^T, \quad B_t \leftarrow B_{t-1} + x_t \alpha_t^T$ with $A_0 = 0$ and $B_0 = 0$ .
4. The dictionary $D_t$ is updated via block coordinate descent warm-restarted at $D_{t-1}$ to minimize the quadratic surrogate: $\hat{f}_t(D) \triangleq \frac{1}{t} \left( \frac{1}{2} \text{Tr}(D^T D A_t) - \text{Tr}(D^T B_t) \right)$ over $D \in \mathcal{C}$ . Each column $j \in \{1,\dots,k\}$ is updated sequentially: $u_j \leftarrow \frac{1}{A_t[j, j]} (B_t[:, j] - D A_t[:, j]) + d_j, \quad d_j \leftarrow \frac{u_j}{\max(\|u_j\|_2, 1)}$ In practice, a single pass over columns $j = 1, \dots, k$ per iteration is sufficient.
Input: Data distribution $p(x)$ , parameter $\lambda \in \mathbb{R}$ , initial dictionary $D_0 \in \mathbb{R}^{m \times k}$ , iterations $T$
Output: Learned dictionary $D_T \in \mathbb{R}^{m \times k}
$A_0 \leftarrow 0$
$B_0 \leftarrow 0$
for $t = 1$ to $T$ do
    Draw $x_t$ from $p(x)$
    Compute $\alpha_t \leftarrow \arg\min_{\alpha \in \mathbb{R}^k} \frac{1}{2} \|x_t - D_{t-1}\alpha\|_2^2 + \lambda \|\alpha\|_1$ using LARS
     $A_t \leftarrow A_{t-1} + \alpha_t \alpha_t^T$
     $B_t \leftarrow B_{t-1} + x_t \alpha_t^T$
     $D \leftarrow D_{t-1}$
    repeat
        for $j = 1$ to $k$ do
             $u_j \leftarrow \frac{1}{A_t[j, j]} (B_t[:, j] - D A_t[:, j]) + D[:, j]$
             $D[:, j] \leftarrow \frac{u_j}{\max(\|u_j\|_2, 1)}$
        end for
    until convergence of column updates
     $D_t \leftarrow D$
end for
return $D_T$
Knowl 2 — Asymptotic Convergence of Online Dictionary Learning to Stationary Points
theoretical result
Let $x \in \mathbb{R}^m$ be drawn from a probability distribution $p(x)$ on a compact support $K \subset \mathbb{R}^m$ . Consider the dictionary learning expected cost: $f(D) \triangleq \mathbb{E}_x [\ell(x, D)], \quad \text{where } \ell(x, D) \triangleq \min_{\alpha \in \mathbb{R}^k} \frac{1}{2} \|x - D\alpha\|_2^2 + \lambda \|\alpha\|_1$ over the convex constraint set $\mathcal{C} \triangleq \{D \in \mathbb{R}^{m \times k} \mid \forall j=1,\dots,k, \|d_j\|_2 \le 1\}$ .

Assume the following conditions:
1. Compact support: The data distribution $p(x)$ has compact support $K$ .
2. Strict convexity of surrogates: The smallest eigenvalue of $\frac{1}{t} A_t = \frac{1}{t} \sum_{i=1}^t \alpha_i \alpha_i^T$ is bounded below by a constant $\kappa_1 > 0$ for all $t$ .
3. Uniqueness of sparse codes: There exists $\kappa_2 > 0$ such that for all $x \in K$ and feasible $D \in \mathcal{C}$ , the Gram submatrix $D_\Lambda^T D_\Lambda$ restricted to the active set $\Lambda = \{j \mid |d_j^T(x - D\alpha^*(x, D))| = \lambda\}$ has smallest eigenvalue at least $\kappa_2$ .
Under these conditions:
- Asymptotic variations: The iterate increments satisfy $\|D_{t+1} - D_t\|_F = O(1/t)$ almost surely.
- Regularity of expected loss: The expected loss $f$ is continuously differentiable on $\mathcal{C}$ with $\nabla f(D) = \mathbb{E}_x [-(x - D\alpha^*(x, D))\alpha^*(x, D)^T]$ , and $\nabla f$ is Lipschitz continuous on $\mathcal{C}$ .
- Surrogate convergence: The surrogate sequence $\hat{f}_t(D_t) = \frac{1}{t} \sum_{i=1}^t (\frac{1}{2} \|x_i - D_t \alpha_i\|_2^2 + \lambda \|\alpha_i\|_1)$ converges almost surely, $f(D_t) - \hat{f}_t(D_t) \to 0$ almost surely, and $f(D_t)$ converges almost surely.
- Stationary point convergence: The distance between $D_t$ and the set of first-order stationary points of $f$ on $\mathcal{C}$ converges almost surely to $0$ as $t \to \infty$ .
Knowl 3 — Expected Cost and Quadratic Surrogate Formulation for Sparse Dictionary Learning
model/method
In sparse dictionary learning, a finite set of $n$ observations $X = [x_1, \dots, x_n] \in \mathbb{R}^{m \times n}$ is traditionally used to minimize the empirical cost: $f_n(D) \triangleq \frac{1}{n} \sum_{i=1}^n \ell(x_i, D), \quad \text{with } \ell(x, D) \triangleq \min_{\alpha \in \mathbb{R}^k} \frac{1}{2} \|x - D\alpha\|_2^2 + \lambda \|\alpha\|_1$ over the convex constraint set $\mathcal{C} = \{D \in \mathbb{R}^{m \times k} \mid \forall j=1,\dots,k, \|d_j\|_2 \le 1\}$ .

When samples are drawn from an underlying continuous distribution $p(x)$ , the target objective is the expected cost: $f(D) \triangleq \mathbb{E}_x [\ell(x, D)] = \lim_{n \to \infty} f_n(D) \quad \text{a.s.}$

To optimize $f(D)$ online without re-evaluating historical data points, the online dictionary learning framework minimizes at step $t$ an empirical quadratic surrogate function: $\hat{f}_t(D) \triangleq \frac{1}{t} \sum_{i=1}^t \left( \frac{1}{2} \|x_i - D\alpha_i\|_2^2 + \lambda \|\alpha_i\|_1 \right)$ where each code vector $\alpha_i$ was computed at step $i$ using $D_{i-1}$ and kept fixed thereafter. The function $\hat{f}_t(D)$ upperbounds the empirical cost $f_t(D_t)$ and depends only on two aggregated matrices: $A_t \triangleq \sum_{i=1}^t \alpha_i \alpha_i^T \in \mathbb{R}^{k \times k}, \quad B_t \triangleq \sum_{i=1}^t x_i \alpha_i^T \in \mathbb{R}^{m \times k}$ which allows $\hat{f}_t(D)$ to be written up to constant terms as: $\hat{f}_t(D) = \frac{1}{t} \left( \frac{1}{2} \text{Tr}(D^T D A_t) - \text{Tr}(D^T B_t) \right) + \text{const}$ This surrogate can be minimized over $\mathcal{C}$ with $O(k^2 + mk)$ memory footprint.
Knowl 4 — Algorithmic Refinements for Online Dictionary Learning
model/method
Four practical refinements improve convergence speed, computational throughput, and numerical stability in online dictionary learning:
1. Mini-batch drawing: Drawing a mini-batch of $\eta > 1$ samples $x_{t, 1}, \dots, x_{t, \eta}$ at iteration $t$ enables precomputation of the Gram matrix $D_{t-1}^T D_{t-1}$ . For LARS-Lasso sparse coding, decomposing 1 sample costs $O(k m s + k s^2)$ , where $s$ is the number of non-zero coefficients. Decomposing $\eta$ samples with a precomputed Gram matrix costs $O(k^2 m + \eta(k m + k s^2))$ , resulting in substantial computational speedups per signal when $\eta \gg 1$ and $s \ll k$ . Sufficient statistics update via: $A_t \leftarrow A_{t-1} + \frac{1}{\eta} \sum_{i=1}^\eta \alpha_{t, i} \alpha_{t, i}^T, \quad B_t \leftarrow B_{t-1} + \frac{1}{\eta} \sum_{i=1}^\eta x_{t, i} \alpha_{t, i}^T$
2. Past data scaling (exponential forgetting): To weight newer coefficients more heavily, historical statistics are scaled at iteration $t$ by $\beta_t = (1 - 1/t)^\rho$ for parameter $\rho \ge 0$ : $A_t \leftarrow \beta_t A_{t-1} + \alpha_t \alpha_t^T, \quad B_t \leftarrow \beta_t B_{t-1} + x_t \alpha_t^T$ This modifies the surrogate to $\sum_{i=1}^t (i/t)^\rho \ell(x_i, D, \alpha_i)$ , speeding up convergence on large datasets ( $n \ge 10^5$ ).
3. Auxiliary matrix cycling on finite datasets: On fixed-size datasets iterated over multiple epochs, maintaining auxiliary matrices $A'_t, B'_t$ reset each epoch and setting $A_t \leftarrow A'_t, B_t \leftarrow B'_t$ at epoch boundaries ensures no coefficients older than two epochs remain in the statistics.
4. Initial stabilization: Initializing $A_0 = t_0 I$ and $B_0 = t_0 D_0$ with $t_0 \ge 0$ prevents large erratic steps in early iterations, though $t_0 = 0$ is typically sufficient.
Knowl 5 — Linear-Time Orthogonal Projection onto the Elastic-Net Constraint
algorithm
Given a vector $b \in \mathbb{R}^m$ , a parameter $\gamma \ge 0$ , and a radius $\tau > 0$ , the orthogonal projection of $b$ onto the elastic-net constraint set is formulated as: $\min_{u \in \mathbb{R}^m} \frac{1}{2} \|b - u\|_2^2 \quad \text{s.t.} \quad \|u\|_1 + \frac{\gamma}{2} \|u\|_2^2 \le \tau$

If $\|b\|_1 + \frac{\gamma}{2}\|b\|_2^2 \le \tau$ , $u^* = b$ . Otherwise, the optimal solution is given by: $u^*(\lambda)[j] = \frac{\text{sign}(b[j])(|b[j]| - \lambda)^+}{1 + \lambda \gamma}, \quad j = 1, \dots, m$ where $\lambda > 0$ is the unique dual root of $\sum_{j \in S(\lambda)} \frac{1}{(1+\lambda\gamma)^2} (|b[j]| + \frac{\gamma}{2} |b[j]|^2 - \lambda(1 + \frac{\gamma\lambda}{2})) = \tau$ , and $S(\lambda) = \{j \mid |b[j]| \ge \lambda\}$ .

The algorithm determines $S(\lambda)$ in average $O(m)$ time using randomized partitioning, and computes $\lambda$ via the quadratic formula:
Input: Vector $b \in \mathbb{R}^m$ , parameter $\gamma \in \mathbb{R}$ , radius $\tau > 0$
Output: Projected vector $u \in \mathbb{R}^m$
if $\|b\|_1 + \frac{\gamma}{2}\|b\|_2^2 \le \tau$ then
    return $u \leftarrow b$
else
     $U \leftarrow \{1, \dots, m\}$
     $s \leftarrow 0$
     $\rho \leftarrow 0$
    while $U \neq \emptyset$ do
        Pick $k \in U$ uniformly at random
         $G \leftarrow \{j \in U \mid |b[j]| \ge |b[k]|\}$
         $L \leftarrow \{j \in U \mid |b[j]| < |b[k]|\}$
         $\Delta \rho \leftarrow |G|$
         $\Delta s \leftarrow \sum_{j \in G} (|b[j]| + \frac{\gamma}{2}|b[j]|^2)$
        if $s + \Delta s - (\rho + \Delta \rho)(1 + \frac{\gamma}{2}|b[k]|)|b[k]| < \tau (1 + \gamma |b[k]|)^2$ then
             $s \leftarrow s + \Delta s$
             $\rho \leftarrow \rho + \Delta \rho$
             $U \leftarrow L$
        else
             $U \leftarrow G \setminus \{k\}$
        end if
    end while
     $a_{\text{quad}} \leftarrow \gamma^2 \tau + \frac{\gamma}{2} \rho$
     $b_{\text{quad}} \leftarrow 2 \gamma \tau + \rho$
     $c_{\text{quad}} \leftarrow \tau - s$
     $\lambda \leftarrow \frac{-b_{\text{quad}} + \sqrt{b_{\text{quad}}^2 - 4 a_{\text{quad}} c_{\text{quad}}}}{2 a_{\text{quad}}}$
    for $j = 1$ to $m$ do
         $u[j] \leftarrow \frac{\text{sign}(b[j]) \max(|b[j]| - \lambda, 0)}{1 + \lambda \gamma}$
    end for
    return $u$
end if
Knowl 6 — Online Sparse Principal Component Analysis
model/method
Sparse Principal Component Analysis (SPCA) is formulated as a sparse matrix factorization problem on $X = [x_1, \dots, x_n] \in \mathbb{R}^{m \times n}$ : $\min_{\substack{\alpha \in \mathbb{R}^{k \times n} \\ D \in \mathbb{R}^{m \times k}}} \sum_{i=1}^n \left( \frac{1}{2} \|x_i - D\alpha_i\|_2^2 + \lambda \|\alpha_i\|_1 \right) \quad \text{s.t.} \quad \forall j=1,\dots,k, \quad \|d_j\|_2^2 + \gamma \|d_j\|_1 \le 1$ where $\lambda$ controls representation sparsity in $\alpha_i$ , and $\gamma > 0$ controls the sparsity of the dictionary atoms $d_j$ .

In the online SPCA algorithm, sparse coding computes $\alpha_t$ via LARS-Lasso, sufficient statistics matrices $A_t = \sum_{i=1}^t \alpha_i \alpha_i^T$ and $B_t = \sum_{i=1}^t x_i \alpha_i^T$ accumulate past information, and dictionary updates solve decoupled column projections: $u_j \leftarrow \frac{1}{A_t[j, j]} (B_t[:, j] - D A_t[:, j]) + d_j$ $d_j \leftarrow \arg\min_{d \in \mathbb{R}^m} \|u_j - d\|_2^2 \quad \text{s.t.} \quad \|d\|_2^2 + \gamma \|d\|_1 \le 1$ Each column projection is executed in average $O(m)$ time using the randomized elastic-net projection algorithm. SPCA can also incorporate fused lasso constraints $\|d_j\|_2^2 + \gamma_1 \|d_j\|_1 + \gamma_2 \sum_{i=2}^m |d_j[i] - d_j[i-1]| \le 1$ to obtain piecewise-constant sparse components.
Knowl 7 — Online Non-Negative Matrix Factorization and Non-Negative Sparse Coding
model/method
Non-Negative Matrix Factorization (NMF) and Non-Negative Sparse Coding (NNSC) are formulated as constrained dictionary learning problems: $\min_{D \in \mathcal{C}', \alpha \in \mathbb{R}^{k \times n}} \sum_{i=1}^n \left( \frac{1}{2} \|x_i - D\alpha_i\|_2^2 + \lambda \sum_{j=1}^k \alpha_i[j] \right) \quad \text{s.t.} \quad D \ge 0, \quad \forall i, \alpha_i \ge 0$ where $\mathcal{C}' = \{D \in \mathbb{R}^{m \times k} \mid D \ge 0, \forall j=1,\dots,k, \|d_j\|_2 \le 1\}$ . Setting $\lambda = 0$ yields standard NMF, while $\lambda > 0$ yields NNSC.

Under the online optimization framework:
1. Non-negative sparse coding computes $\alpha_t \ge 0$ for signal $x_t \ge 0$ over $D_{t-1}$ using non-negative LARS-Lasso.
2. Matrices $A_t = \sum_{i=1}^t \alpha_i \alpha_i^T$ and $B_t = \sum_{i=1}^t x_i \alpha_i^T$ aggregate past information.
3. The dictionary update optimizes each column $d_j$ via block coordinate descent: $u_j \leftarrow \frac{1}{A_t[j, j]} (B_t[:, j] - D A_t[:, j]) + d_j$ $d_j \leftarrow \frac{\max(u_j, 0)}{\max(\|\max(u_j, 0)\|_2, 1)}$ where $\max(u_j, 0)$ is applied elementwise. The online algorithm converges almost surely to a stationary point and avoids the full dataset passes required by batch multiplicative update rules or projected gradient descent methods.
Knowl 8 — Homotopy Method for Fused Lasso Signal Approximation and Constraint Projection
algorithm
The fused lasso signal approximation problem seeks a vector $u \in \mathbb{R}^m$ minimizing: $\mathcal{P}(\gamma_1, \gamma_2, \gamma_3): \min_{u \in \mathbb{R}^m} \frac{1}{2} \|b - u\|_2^2 + \gamma_1 \|u\|_1 + \gamma_2 \sum_{i=2}^m |u[i] - u[i-1]| + \frac{\gamma_3}{2} \|u\|_2^2$ for a given vector $b \in \mathbb{R}^m$ .

The general solution $u^*(\gamma_1, \gamma_2, \gamma_3)$ is obtained from the pure total variation solution $u^*(0, \gamma_2, 0)$ via:
1. Soft-thresholding: $u^*(\gamma_1, \gamma_2, 0)[i] = \text{sign}(u^*(0, \gamma_2, 0)[i]) \max(|u^*(0, \gamma_2, 0)[i]| - \gamma_1, 0)$ .
2. Scaling: $u^*(\gamma_1, \gamma_2, \gamma_3) = \frac{1}{1 + \gamma_3} u^*(\gamma_1, \gamma_2, 0)$ .
To solve $\min_{u \in \mathbb{R}^m} \frac{1}{2}\|b - u\|_2^2 + \gamma_2 \sum_{i=2}^m |u[i] - u[i-1]|$ , the change of variable $v[1] = u[1]$ and $v[i] = u[i] - u[i-1]$ ( $i > 1$ ) recasts the problem as a weighted Lasso: $\min_{v \in \mathbb{R}^m} \frac{1}{2} \|b - \tilde{D}v\|_2^2 + \sum_{i=1}^m w_i |v[i]|$ where $w_1 = 0, w_i = \gamma_2$ ( $i > 1$ ), and $\tilde{D} \in \mathbb{R}^{m \times m}$ is lower-triangular with $\tilde{D}[i, j] = 1$ for $i \ge j$ and $0$ otherwise.

Because matrix-vector products $\tilde{D}w$ and $\tilde{D}^T w$ require $O(m)$ operations via recursive prefix sums, and for any active set $\Gamma = \{a_1, \dots, a_p\}$ ( $a_1 < \dots < a_p$ ) the Gram inverse $(\tilde{D}_\Gamma^T \tilde{D}_\Gamma)^{-1}$ is tridiagonal with closed form: $(\tilde{D}_\Gamma^T \tilde{D}_\Gamma)^{-1}_{i, i} = c_{i-1} + c_i, \quad (\tilde{D}_\Gamma^T \tilde{D}_\Gamma)^{-1}_{i, i+1} = -c_i, \quad c_i = \frac{1}{a_{i+1} - a_i}, \quad c_p = \frac{1}{m + 1 - a_p}$ the entire LARS homotopy path is computed in $O(ms)$ operations without matrix inversions or Cholesky factorizations, where $s$ is the number of piecewise-constant segments in the solution.
Knowl 9 — Online Simultaneous Sparse Coding
model/method
When signals arrive in groups $X_i = [x_{i, 1}, \dots, x_{i, q}] \in \mathbb{R}^{m \times q}$ that share a common sparsity pattern (active set of atoms), simultaneous sparse coding models the coefficient matrix $\alpha_i = [\alpha_{i, 1}, \dots, \alpha_{i, q}] \in \mathbb{R}^{k \times q}$ using an $\ell_{1,2}$ group-sparsity norm: $\ell'''(X_i, D) \triangleq \min_{\alpha_i \in \mathbb{R}^{k \times q}} \frac{1}{2} \|X_i - D\alpha_i\|_F^2 + \lambda \|\alpha_i\|_{1,2}, \quad \text{where } \|\alpha_i\|_{1,2} \triangleq \sum_{j=1}^k \|\alpha_i^j\|_2$ and $\alpha_i^j$ is the $j$ -th row of $\alpha_i$ .

The dictionary learning objective minimizes the expected loss: $\min_{D \in \mathcal{C}} \lim_{n \to \infty} \frac{1}{n} \sum_{i=1}^n \ell'''(X_i, D)$ In each iteration, given an observed group $X_t \in \mathbb{R}^{m \times q}$ , the coefficient matrix $\alpha_t \in \mathbb{R}^{k \times q}$ is computed via group block-coordinate descent or active set methods. The sufficient statistics matrices update as: $A_t \leftarrow A_{t-1} + \alpha_t \alpha_t^T, \quad B_t \leftarrow B_{t-1} + X_t \alpha_t^T$ and the dictionary update step proceeds identically to standard online dictionary learning.
Knowl 10 — Empirical Convergence Comparison of Online Dictionary Learning against Batch and SGD
empirical result
Online dictionary learning was compared against batch coordinate descent and first-order projected stochastic gradient descent (SGD) on $1.25 \times 10^6$ natural image patches from Pascal VOC 2006 ( $10^6$ training samples, $2.5 \times 10^5$ test samples) across three benchmark configurations:
- Set A: $8 \times 8$ grayscale patches ( $m = 64$ ), $k = 256$ atoms, $\lambda = 1.2/\sqrt{m} = 0.15$ .
- Set B: $12 \times 12$ RGB color patches ( $m = 432$ ), $k = 512$ atoms, $\lambda = 1.2/\sqrt{m} \approx 0.0577$ .
- Set C: $16 \times 16$ grayscale patches ( $m = 256$ ), $k = 1024$ atoms, $\lambda = 1.2/\sqrt{m} = 0.075$ .
All algorithms were implemented in C++ and evaluated on a single-core 2.66 GHz CPU with mini-batch size $\eta = 512$ .

Key experimental findings:
1. Online vs. Batch: The online algorithm consistently outperformed batch coordinate descent (evaluated on subsets of size $10^4, 10^5$ and full $10^6$ ) by orders of magnitude in training time. On Set A, the online method achieved a test cost of $0.285$ in approximately $2$ seconds, whereas batch learning on $10^6$ samples required over $1000$ seconds.
2. Online vs. SGD: Projected SGD with learning rate $\delta_t = a / (\eta t + b)$ (e.g., $a = 200,000, b = 400,000$ ) achieved asymptotic cost similar to the online algorithm, but was sensitive to $a$ and $b$ . In contrast, the online algorithm is step-size parameter-free, reaching low expected cost without requiring learning rate schedules.
3. Past data decay $\rho$ : Setting $\rho \in [10, 20]$ slightly accelerated convergence on the $10^6$ dataset, and setting initial stabilization $t_0 = 0$ produced results nearly identical to tuned $t_0$ .
Knowl 11 — Large-Scale Dictionary Learning for Natural Image Inpainting
empirical result
To evaluate scalability on large real-world problems, online dictionary learning was applied to inpaint a damaged 12-Megapixel photograph corrupted with overlaid text.

Experimental setup and results:
- Data volume: Approximately $7 \times 10^6$ undamaged $12 \times 12$ RGB patches ( $m = 432$ ) were extracted from the uncorrupted regions of the 12-Megapixel image.
- Training: A dictionary of $k = 256$ atoms was trained online over 2 epochs across the $7 \times 10^6$ patches.
- Computational speed: Running on a 2.4 GHz machine using 8 threads, the online dictionary learning completed in approximately 8 minutes.
- Inpainting performance: Using the learned dictionary within sparse coding inpainting reconstructed missing pixel values in the text regions, removing overlaid text while recovering fine image details and textures.
Knowl 12 — Empirical Performance of Online Non-Negative Matrix Factorization and Sparse Coding
empirical result
The online dictionary learning formulation for non-negative matrix factorization (NMF) and non-negative sparse coding (NNSC) was evaluated across three datasets:
- Set D: $n = 2,429$ face images from the MIT-CBCL database ( $m = 19 \times 19 = 361$ pixels, $k = 49$ components).
- Set E: $n = 2,414$ face images from the Extended Yale B database ( $m = 192 \times 168 = 32,256$ pixels, $k = 49$ components).
- Set F: $n = 100,000$ natural image patches from Pascal VOC 2006 ( $m = 16 \times 16 = 256$ pixels, $k = 64$ components).
Benchmarked against the multiplicative update algorithm of Lee and Seung (2001) for NMF and Hoyer's algorithm (2002) for NNSC:
1. Convergence speed: On all datasets, the online method reached lower objective values significantly faster than multiplicative and gradient baselines. On dataset D, the online method dropped the NMF objective below $0.02$ within $1$ second, while the baseline required over $100$ seconds. On dataset F ( $10^5$ samples), the online algorithm converged in under $10$ seconds versus thousands of seconds for the baseline.
2. Qualitative features: NMF and SPCA on face datasets D and E produced localized, part-based facial features (eyes, noses, mouths), whereas standard PCA produced holistic eigenfaces. On natural patches (Set F), SPCA with tunable $\gamma$ controlled dictionary sparsity ( $\tau = 70\%, 30\%, 10\%$ non-zero coefficients) while learning localized, oriented edge filters.

Coverage note — The secondary genomic data experiment applying SPCA with fused lasso to breast cancer CGH and gene expression correlation across 23 chromosomes (Section 6.3.2) was omitted as a standalone empirical knowl because it was an illustrative demonstration yielding results comparable to prior penalized matrix decomposition.

References

1.M. Aharon and M. Elad. Sparse and redundant modeling of image content using an image-signature-dictionary. SIAM Journal on Imaging Sciences, 1(3):228–247, July 2008.
2.M. Aharon, M. Elad, and A. M. Bruckstein. The K-SVD: An algorithm for designing of overcomplete dictionaries for sparse representations. IEEE Transactions on Signal Processing, 54(11):4311–4322, November 2006.
3.F. Bach. Consistency of the group Lasso and multiple kernel learning. Journal of Machine Learning Research, 9:1179–1224, 2008.
4.F. Bach, J. Mairal, and J. Ponce. Convex sparse matrix factorizations. Technical report, 2008. Preprint arXiv:0812.1869.
5.D. P. Bertsekas. Nonlinear Programming. Athena Scientific Belmont, 1999.
6.P. Bickel, Y. Ritov, and A. Tsybakov. Simultaneous analysis of Lasso and Dantzig selector. Annals of statistics, 37(4):1705–1732, 2009.
7.J. F. Bonnans and A. Shapiro. Optimization problems with perturbations: A guided tour. SIAM Review, 40(2):202–227, 1998.
8.J. F. Bonnans and A. Shapiro. Perturbation Analysis of Optimization Problems. Springer, 2000.
9.J. M. Borwein and A. S. Lewis. Convex Analysis and Nonlinear Optimization: Theory and Examples. Springer, 2006.
10.L. Bottou. Online algorithms and stochastic approximations. In David Saad, editor, Online Learning and Neural Networks. 1998.
11.L. Bottou and O. Bousquet. The trade-offs of large scale learning. In J.C. Platt, D. Koller, Y. Singer, and S. Roweis, editors, Advances in Neural Information Processing Systems, volume 20, pages 161–168. MIT Press, 2008.
12.D. M. Bradley and J. A. Bagnell. Differentiable sparse coding. In D. Koller, D. Schuurmans, Y. Bengio, and L. Bottou, editors, Advances in Neural Information Processing Systems, volume 21, pages 113–120. 2009.
13.S. S. Chen, D. L. Donoho, and M. A. Saunders. Atomic decomposition by basis pursuit. SIAM Journal on Scientific Computing, 20:33–61, 1999.
14.K. Chin, S. DeVries, J. Fridlyand, P.T. Spellman, R. Roydasgupta, W. L. Kuo, A. Lapuk, R. M. Neve, Z. Qian, T. Ryder, et al. Genomic and transcriptional aberrations linked to breast cancer pathophysiologies. Cancer Cell, 10(6):529–541, 2006.
15.S. F. Cotter, B. D. Rao, K. Engan, and K. Kreutz-Delgado. Sparse solutions to linear inverse problems with multiple measurement vectors. IEEE Transactions on Signal Processing, 53(7):2477–2488, 2005.
16.J. M. Danskin. The theory of max-min, and its application to weapons allocation problems. Ökonometrie und Unternehmensforschung, 1967.
17.A. d’Aspremont, L. El Ghaoui, M. I. Jordan, and G. R. G. Lanckriet. A direct formulation for sparse PCA using semidefinite programming. SIAM Review, 49(3):434–448, 2007.
18.A. d’Aspremont, F. Bach, and L. El Ghaoui. Optimal solutions for sparse principal component analysis. Journal of Machine Learning Research, 9:1269–1294, 2008.
19.J. Duchi, S. Shalev-Shwartz, Y. Singer, and T. Chandra. Efficient projections onto the ℓ1-ball for learning in high dimensions. In Proceedings of the International Conference on Machine Learning (ICML), 2008.
20.B. Efron, T. Hastie, I. Johnstone, and R. Tibshirani. Least angle regression. Annals of Statistics, 32(2):407–499, 2004.
21.M. Elad and M. Aharon. Image denoising via sparse and redundant representations over learned dictionaries. IEEE Transactions on Image Processing, 54(12):3736–3745, December 2006.
22.K. Engan, S. O. Aase, and J. H. Husoy. Frame based signal compression using method of optimal directions (MOD). In Proceedings of the 1999 IEEE International Symposium on Circuits Systems, volume 4, 1999.
23.M. Everingham, L. Van Gool, C. K. I. Williams, J. Winn, and A. Zisserman. The PASCAL Visual Object Classes Challenge 2006 (VOC2006) Results, 2006.
24.C. Févotte, N. Bertin, and J. L. Durrieu. Nonnegative matrix factorization with the itakura-saito divergence: With application to music analysis. Neural Computation, 21(3):793–830, 2009.
25.D. L. Fisk. Quasi-martingales. Transactions of the American Mathematical Society, 120(3): 359–388, 1965.
26.J. Friedman, T. Hastie, H. Höfling, and R. Tibshirani. Pathwise coordinate optimization. Annals of Applied Statistics, 1(2):302–332, 2007.
27.W. J. Fu. Penalized regressions: The bridge versus the Lasso. Journal of Computational and Graphical Statistics, 7:397–416, 1998.
28.J. J. Fuchs. Recovery of exact sparse representations in the presence of bounded noise. IEEE Transactions on Information Theory, 51(10):3601–3608, 2005.
29.A. S. Georghiades, P. N. Belhumeur, and D. J. Kriegman. From few to many: Illumination cone models for face recognition under variable lighting and pose. IEEE Transactions on Pattern Analysis and Machine Intelligence, 23(6):643–660, 2001.
30.G. H. Golub and C. F. Van Loan. Matrix computations. John Hopkins University Press, 1996.
31.R. Grosse, R. Raina, H. Kwong, and A. Y. Ng. Shift-invariant sparse coding for audio classification. In Proceedings of the Twenty-third Conference on Uncertainty in Artificial Intelligence (UAI), 2007.
32.Z. Harchaoui. Méthodes à Noyaux pour la Détection. PhD thesis, Télécom ParisTech, 2008.
33.Z. Harchaoui and C. Lévy-Leduc. Catching change-points with Lasso. In J.C. Platt, D. Koller, Y. Singer, and S. Roweis, editors, Advances in Neural Information Processing Systems, volume 20, pages 161–168. MIT Press, 2008.
34.H. Hotelling. Relations between two sets of variates. Biometrika, 28:321–377, 1936.
35.P. O. Hoyer. Non-negative sparse coding. In Proc. IEEE Workshop on Neural Networks for Signal Processing, 2002.
36.P. O. Hoyer. Non-negative matrix factorization with sparseness constraints. Journal of Machine Learning Research, 5:1457–1469, 2004.
37.L. Jacob, G. Obozinski, and J.-P. Vert. Group Lasso with overlap and graph Lasso. In Proceedings of the International Conference on Machine Learning (ICML), 2009.
38.R. Jenatton, J-Y. Audibert, and F. Bach. Structured variable selection with sparsity-inducing norms. Technical report, 2009a. Preprint arXiv:0904.3523v1.
39.R. Jenatton, G. Obozinski, and F. Bach. Structured sparse principal component analysis. Technical report, 2009b. Preprint arXiv:0909.1440v1.
40.I. T. Jolliffe, N. T. Trendafilov, and M. Uddin. A modified principal component technique based on the Lasso. Journal of Computational and Graphical Statistics, 12(3):531–547, 2003.
41.K. Kavukcuoglu, M. Ranzato, and Y. LeCun. Fast inference in sparse coding algorithms with applications to object recognition. Technical report, Computational and Biological Learning Lab, Courant Institute, NYU, 2008.
42.Y. Koren, R. Bell, and C. Volinsky. Matrix factorization techniques for recommender systems. IEEE Computer, 42(8):30–37, 2009.
43.H. J. Kushner and G. Yin. Stochastic Approximation and Recursive Algorithms and Applications. Springer, 2003.
44.D. D. Lee and H. S. Seung. Algorithms for non-negative matrix factorization. In Advances in Neural Information Processing Systems, pages 556–562, 2001.
45.H. Lee, A. Battle, R. Raina, and A. Y. Ng. Efficient sparse coding algorithms. In B. Schölkopf, J. Platt, and T. Hoffman, editors, Advances in Neural Information Processing Systems, volume 19, pages 801–808. MIT Press, 2007.
46.K. C. Lee, J. Ho, and D. Kriegman. Acquiring linear subspaces for face recognition under variable lighting. IEEE Transactions on Pattern Analysis and Machine Intelligence, 27 (5):684–698, 2005.
47.M. S. Lewicki and T. J. Sejnowski. Learning overcomplete representations. Neural Computation, 12(2):337–365, 2000.
48.C.J. Lin. Projected gradient methods for nonnegative matrix factorization. Neural Computation, 19(10):2756–2779, 2007.
49.N. Maculan and J. R. G. Galdino de Paula. A linear-time median-finding algorithm for projecting a vector on the simplex of Rn. Operations Research Letters, 8(4):219–222, 1989.
50.J. R. Magnus and H. Neudecker. Matrix Differential Calculus with Applications in Statistics and Econometrics, revised edition. John Wiley, Chichester, 1999.
51.J. Mairal, F. Bach, J. Ponce, G. Sapiro, and A. Zisserman. Discriminative learned dictionaries for local image analysis. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2008a.
52.J. Mairal, M. Elad, and G. Sapiro. Sparse representation for color image restoration. IEEE Transactions on Image Processing, 17(1):53–69, January 2008b.
53.J. Mairal, G. Sapiro, and M. Elad. Learning multiscale sparse representations for image and video restoration. SIAM Multiscale Modelling and Simulation, 7(1):214–241, April 2008c.
54.J. Mairal, F. Bach, J. Ponce, and G. Sapiro. Online dictionary learning for sparse coding. In Proceedings of the International Conference on Machine Learning (ICML), 2009a.
55.J. Mairal, F. Bach, J. Ponce, G. Sapiro, and A. Zisserman. Supervised dictionary learning. In D. Koller, D. Schuurmans, Y. Bengio, and L. Bottou, editors, Advances in Neural Information Processing Systems, volume 21, pages 1033–1040. MIT Press, 2009b.
56.J. Mairal, F. Bach, J. Ponce, G. Sapiro, and A. Zisserman. Non-local sparse models for image restoration. In Proceedings of the IEEE International Conference on Computer Vision (ICCV), 2009c.
57.S. Mallat. A Wavelet Tour of Signal Processing, Second Edition. Academic Press, New York, September 1999.
58.M. Métivier. Semi-martingales. Walter de Gruyter, 1983.
59.R. M. Neal and G. E. Hinton. A view of the EM algorithm that justifies incremental, sparse, and other variants. Learning in Graphical Models, 89:355–368, 1998.
60.Y. Nesterov. Gradient methods for minimizing composite objective function. Technical report, Center for Operations Research and Econometrics (CORE), Catholic University of Louvain, 2007.
61.G. Obozinski, M. J. Wainwright, and M. I. Jordan. Union support recovery in high-dimensional multivariate regression. UC Berkeley Technical Report 761, August 2008.
62.G. Obozinski, B. Taskar, and M. I. Jordan. Joint covariate selection and joint subspace selection for multiple classification problems. Statistics and Computing, 2009. Published online.
63.B. A. Olshausen and D. J. Field. Sparse coding with an overcomplete basis set: A strategy employed by V1? Vision Research, 37:3311–3325, 1997.
64.M. R. Osborne, B. Presnell, and B. A. Turlach. A new approach to variable selection in least squares problems. IMA Journal of Numerical Analysis, 20(3):389–403, 2000.
65.G. Peyré. Sparse modeling of textures. Journal of Mathematical Imaging and Vision, 34 (1):17–31, May 2009.
66.M. Protter and M. Elad. Image sequence denoising via sparse and redundant representations. IEEE Transactions on Image Processing, 18(1):27–36, 2009.
67.R. Raina, A. Battle, H. Lee, B. Packer, and A. Y. Ng. Self-taught learning: transfer learning from unlabeled data. In Proceedings of the International Conference on Machine Learning (ICML), 2007.
68.V. Roth and B. Fischer. The Group-Lasso for generalized linear models: uniqueness of solutions and efficient algorithms. In Proceedings of the International Conference on Machine Learning (ICML), 2008.
69.S. Shalev-Shwartz, O. Shamir, N. Srebro, and K. Sridharan. Stochastic convex optimization. In 22nd Annual Conference on Learning Theory (COLT), 2009.
70.K.-K. Sung. Learning and Example Selection for Object and Pattern Recognition. PhD thesis, MIT, Artificial Intelligence Laboratory and Center for Biological and Computational Learning, 1996.
71.R. Tibshirani. Regression shrinkage and selection via the Lasso. Journal of the Royal Statistical Society. Series B, 58(1):267–288, 1996.
72.R. Tibshirani and P. Wang. Spatial smoothing and hot spot detection for CGH data using the fused Lasso. Biostatistics, 9(1):18–29, 2008.
73.R. Tibshirani, M. Saunders, S. Rosset, J. Zhu, and K. Knight. Sparsity and smoothness via the fused lasso. Journal of the Royal Statistical Society Series B, 67(1):91–108, 2005.
74.J. A. Tropp. Algorithms for simultaneous sparse approximation. part ii: Convex relaxation. Signal Processing, Special Issue "Sparse Approximations in Signal and Image Processing", 86:589–602, April 2006.
75.J. A. Tropp, A. C. Gilbert, and M. J. Strauss. Algorithms for simultaneous sparse approximation. part i: Greedy pursuit. Signal Processing, Special Issue "Sparse Approximations in Signal and Image Processing", 86:572–588, April 2006.
76.B. A. Turlach, W. N. Venables, and S. J. Wright. Simultaneous variable selection. Technometrics, 47(3):349–363, 2005.
77.A. W. Van der Vaart. Asymptotic Statistics. Cambridge University Press, 1998.
78.D. M. Witten, R. Tibshirani, and T. Hastie. A penalized matrix decomposition, with applications to sparse principal components and canonical correlation analysis. Biostatistics, 10(3):515–534, 2009.
79.T. T. Wu and K. Lange. Coordinate descent algorithms for Lasso penalized regression. Annals of Applied Statistics, 2(1):224–244, 2008.
80.J. Yang, K. Yu, Y. Gong, and T. Huang. Linear spatial pyramid matching using sparse coding for image classification. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2009.
81.M. Yuan and Y. Lin. Model selection and estimation in regression with grouped variables. Journal of the Royal Statistical Society Series B, 68:49–67, 2006.
82.R. Zass and A. Shashua. Nonnegative sparse PCA. In B. Schölkopf, J. Platt, and T. Hoffman, editors, Advances in Neural Information Processing Systems, volume 19, pages 1561–1568. MIT Press, 2007.
83.H. H. Zhang, Y. Liu, Y. Wu, and J. Zhu. Selection for the multicategory svm via adaptive sup-norm regularization. Electronic Journal of Statistics, 2:149–167, 2008.
84.M. Zibulevsky and B. A. Pearlmutter. Blind source separation by sparse decomposition in a signal dictionary. Neural Computation, 13(4):863–882, 2001.
85.H. Zou and T. Hastie. Regularization and variable selection via the elastic net. Journal of the Royal Statistical Society Series B, 67(2):301–320, 2005.
86.H. Zou, T. Hastie, and R. Tibshirani. Sparse principal component analysis. Journal of Computational and Graphical Statistics, 15(2):265–286, 2006.

Citation

MLA

Mairal, J., et al. “Online Learning for Matrix Factorization and Sparse Coding”. HAL (Le Centre Pour La Communication Scientifique Directe), vol. 11, no. 1, 2010, pp. 19–60, http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.161.8345.

APA

Mairal, J., Bach, F., Ponce, J., & Sapiro, G. (2010). Online Learning for Matrix Factorization and Sparse Coding. HAL (Le Centre Pour La Communication Scientifique Directe), 11(1), 19–60. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.161.8345

Chicago

Mairal, J., F. Bach, J. Ponce, and G. Sapiro. 2010. “Online Learning for Matrix Factorization and Sparse Coding”. HAL (Le Centre Pour La Communication Scientifique Directe) 11 (1): 19–60. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.161.8345.

Harvard

Mairal, J. et al. (2010) “Online Learning for Matrix Factorization and Sparse Coding”, HAL (Le Centre pour la Communication Scientifique Directe), 11(1), pp. 19–60. Available at: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.161.8345.

Vancouver

1. Mairal J, Bach F, Ponce J, Sapiro G (2010) Online Learning for Matrix Factorization and Sparse Coding. HAL (Le Centre pour la Communication Scientifique Directe) 11:19–60

BibTeX

@article{mairal2010online,
  title = {Online Learning for Matrix Factorization and Sparse Coding},
  author = {Mairal, Julien and Bach, Francis and Ponce, Jean and Sapiro, Guillermo},
  year = {2010},
  journal = {HAL (Le Centre pour la Communication Scientifique Directe)},
  volume = {11},
  number = {1},
  pages = {19-60},
  url = {http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.161.8345}
}

Metadata:DOI registry

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: https://creativecommons.org/licenses/by/4.0/

Online Learning for Matrix Factorization and Sparse Coding

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — Online Dictionary Learning Algorithm

Knowl 2 — Asymptotic Convergence of Online Dictionary Learning to Stationary Points

Knowl 3 — Expected Cost and Quadratic Surrogate Formulation for Sparse Dictionary Learning

Knowl 4 — Algorithmic Refinements for Online Dictionary Learning

Knowl 5 — Linear-Time Orthogonal Projection onto the Elastic-Net Constraint

Knowl 6 — Online Sparse Principal Component Analysis

Knowl 7 — Online Non-Negative Matrix Factorization and Non-Negative Sparse Coding

Knowl 8 — Homotopy Method for Fused Lasso Signal Approximation and Constraint Projection

Knowl 9 — Online Simultaneous Sparse Coding

Knowl 10 — Empirical Convergence Comparison of Online Dictionary Learning against Batch and SGD

Knowl 11 — Large-Scale Dictionary Learning for Natural Image Inpainting

Knowl 12 — Empirical Performance of Online Non-Negative Matrix Factorization and Sparse Coding

References

Citation

BibTeX

Source Code

Access the Paper