Online Learning for Matrix Factorization and Sparse Coding

By Julien Mairal, Francis R. Bach, Jean Ponce, Guillermo Sapiro. 2009

2,696 citations recorded by the source corpus.

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 in order to adapt 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 data sets 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 data sets.

Subfields: Electrical and Electronic Engineering, Optimization & Training, Signal Processing

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Electrical and Electronic Engineering

In Optimization & Training

In Signal Processing

Citations in the corpus

Feature Purification: How Adversarial Training Performs Robust Deep Learning (2020, methodology): “We use a data model called sparse coding, which is a popular model to model image, text and speech data [11, 12, 69, 77, 78, 100, 105, 106].”
Example Selection For Dictionary Learning (2014, methodology): “We use the Orthogonal Matching Pursuit (OMP) algorithm Mallat and Zhang (1993), also implemented by the SPAMS package, for this problem.”
Stochastic variational inference (2012, background): “Many stochastic optimization algorithms beneﬁt from “minibatches,” i.e., several examples at a time (Bottou and Bousquet, 2008; Liang et al., 2009; Mairal et al., 2010).”
EDUCE: Explaining model Decisions through Unsupervised Concepts Extraction (2019, background): “arsity constraint on the number of concepts present in the inputs enforces semantic consistency, as sparse coding has been shown to induce useful, interpretable representations (Bengio et al., 2013a; Mairal et al., 2010). We experimentally demonstrate that a sparsity constraint is not sufﬁcient, and”
Deep Image Prior (2017, methodology): “Also in this group are methods based on fitting dictionaries to the patches of the corrupted image [23, 32] as well as methods based on convolutional sparse coding [31], which can also fit statistical models similar to shallow ConvNets to the reconstructed image [25].”
Learning a Text-Video Embedding from Incomplete and Heterogeneous Data (2018, methodology): “Several approaches such as: Low rank matrix factorization [41], Generative Adversarial Network [42] have successfully addressed the problem.”
Incremental Majorization-Minimization Optimization with Application to Large-Scale Machine Learning (2014, methodology): “Majorizing surrogates have also been used successfully in the signal processing literature about sparse estimation [11, 16, 26], linear inverse problems in image processing [1, 23], and matrix factorization [37, 40].”
Optimization with Sparsity-Inducing Penalties (2011, background): “Sparsity-inducing regularizations built upon such group structures have resulted in good performances for background subtraction [62, 86, 88], topographic dictionary learning [72, 88], wavelet-based denoising [111], and for face recognition with corruption by occlusions [70].”
The Utility of Sparse Representations for Control in Reinforcement Learning (2018, background): “…to learning sparse representations incrementally, particularly through factorization approaches for dictionary learning (Mairal et al. 2009; Mairal et al. 2010; Le, Kumaraswamy, and White 2017) or for general sparse distributions (Ol-shausen and Field 1997; Olshausen 2002; Teh et al. 2003;…”
Learning with Submodular Functions: A Convex Optimization Perspective (2011, neutral): “, [90, 199, 139, 38] and references therein).”
Personal object discovery in first-person videos (2015, neutral): “In what follows, we address these challenges.”
Multi-view low-rank sparse subspace clustering (2017, background): “Learning representation matrix in SSC can be interpreted as sparse coding [22, 23, 24, 25, 26, 27].”
Deep learning for visual understanding (2017, neutral): “To address this issue, an online approach [127, 128] was proposed for learning dictionaries that process one element (or a small subset) of the training set at a time.”
Reborn Filters: Pruning Convolutional Neural Networks with Limited Data (2020, background): “(11) is a group fused lasso problem (Simon et al. 2013), which can be solved by many off-the-shelf convex toolboxes, such as CVX (Grant and Boyd 2014) and SPAMS (Mairal et al. 2010).”
Robust Joint Graph Sparse Coding for Unsupervised Spectral Feature Selection (2017, methodology): “We then used the package SPAMS [25] to obtain the bases.”
Beyond spatial pyramids: Receptive field learning for pooled image features (2012, background): “Dictionary learning algorithms have been discussed to find a set of basis that reconstructs local image patches or descriptors well [23, 9], and several encoding methods have been proposed to map the original data to a high-dimensional space that emphasizes certain properties, such as sparsity [24, ”
Learning Word Representations with Hierarchical Sparse Coding (2014, methodology): “We analyze the convergence of Algorithm 1 for the basic setting where we uniformly sample elements of the input matrix X. Similar to Mairal et al. (2010), we can rewrite our optimization problem as: arg minA ∑T t=1 L t(A)+λΩ(A), where Lt(A) = ‖X − DtA‖2F + τ ∑ m ‖dtm‖22, and Dt = Dt−1 + 2ηt((X −…”
Learning Semantic Image Representations at a Large Scale (2014, background): “Dictionary learning algorithms have been discussed to find a set of basis that reconstructs local image patches or descriptors well [80, 20], and several encoding methods have been proposed to map the original data to a high-dimensional space that emphasizes certain properties, such as sparsity [85,”
Laplacian Sparse Coding, Hypergraph Laplacian Sparse Coding, and Applications (2013, methodology): “Recently, this problem was trivially solved by Mairal by using an online learning method [39].”