Online Learning for Matrix Factorization and Sparse Coding

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.

• Publication year

  2009

• Venue

  Journal of machine learning research

• Publication date

  2009-08-01

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.5555/1756006.1756008arXiv 0908.0050
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Matrix Computations

  2011cited by this paper
• Joint covariate selection and joint subspace selection for multiple classification problems

  2010cited by this paper
• Nonlinear Programming

  2010influential reference
• Fast Inference in Sparse Coding Algorithms with Applications to Object Recognition

  2010cited by this paper
• Matrix Factorization Techniques for Recommender Systems

  2009cited by this paper
• Non-local sparse models for image restoration

  2009cited by this paper
• Nonnegative Matrix Factorization with the Itakura-Saito Divergence: With Application to Music Analysis

  2009cited by this paper
• Structured Variable Selection with Sparsity-Inducing Norms

  2009cited by this paper
• Linear spatial pyramid matching using sparse coding for image classification

  2009cited by this paper
• 双対平坦空間におけるLeast Angle Regressionと情報量規準

  2009influential reference
• A penalized matrix decomposition, with applications to sparse principal components and canonical correlation analysis.

  2009cited by this paper
• Group lasso with overlap and graph lasso

  2009influential reference
• Online dictionary learning for sparse coding

  2009cited by this paper
• Stochastic Convex Optimization

  2009cited by this paper
• Sparse Modeling of Textures

  2009cited by this paper
• Image Sequence Denoising via Sparse and Redundant Representations

  2009cited by this paper
• Structured Sparse Principal Component Analysis

  2009influential reference
• Union support recovery in high-dimensional multivariate regression

  2008cited by this paper
• SIMULTANEOUS ANALYSIS OF LASSO AND DANTZIG SELECTOR

  2008cited by this paper
• Supervised Dictionary Learning

  2008influential reference
• Efficient projections onto the l1-ball for learning in high dimensions

  2008cited by this paper
• The Group-Lasso for generalized linear models: uniqueness of solutions and efficient algorithms

  2008cited by this paper
• Convex Sparse Matrix Factorizations

  2008cited by this paper
• Variable selection for the multicategory SVM via adaptive sup-norm regularization

  2008cited by this paper
• Learning Multiscale Sparse Representations for Image and Video Restoration

  2008cited by this paper
• Coordinate descent algorithms for lasso penalized regression

  2008cited by this paper
• Sparse Representation for Color Image Restoration

  2008influential reference
• Sparse coding

  2008cited by this paper
• Differentiable Sparse Coding

  2008cited by this paper
• Spatial smoothing and hot spot detection for CGH data using the fused lasso.

  2008cited by this paper
• Discriminative learned dictionaries for local image analysis

  2008cited by this paper
• Sparse and Redundant Modeling of Image Content Using an Image-Signature-Dictionary

  2008cited by this paper
• Consistency of the group Lasso and multiple kernel learning

  2007influential reference
• Molecular Cancer Class Discovery Using Non-negative Matrix Factorization with Sparseness Constraint

  2007cited by this paper
• Projected Gradient Methods for Nonnegative Matrix Factorization

  2007influential reference
• Optimal Solutions for Sparse Principal Component Analysis

  2007cited by this paper
• Self-taught learning: transfer learning from unlabeled data

  2007influential reference
• The Tradeoffs of Large Scale Learning

  2007influential reference
• Catching Change-points with Lasso

  2007cited by this paper
• Gradient methods for minimizing composite objective function

  2007cited by this paper
• PATHWISE COORDINATE OPTIMIZATION

  2007influential reference
• Model selection and estimation in regression with grouped variables

  2006cited by this paper
• Sparse Principal Component Analysis

  2006influential reference
• Méthodes à noyaux pour la détection de piétons. (Kernel Machines for Pedestrian Detection)

  2006cited by this paper
• Algorithms for simultaneous sparse approximation. Part I: Greedy pursuit

  2006cited by this paper
• $rm K$-SVD: An Algorithm for Designing Overcomplete Dictionaries for Sparse Representation

  2006influential reference
• Algorithms for simultaneous sparse approximation. Part II: Convex relaxation

  2006cited by this paper
• Efficient sparse coding algorithms

  2006cited by this paper
• Nonnegative Sparse PCA

  2006cited by this paper
• Image Denoising Via Sparse and Redundant Representations Over Learned Dictionaries

  2006influential reference
• The PASCAL Visual Object Classes Challenge

  2006influential reference
• Genomic and transcriptional aberrations linked to breast cancer pathophysiologies.

  2006cited by this paper
• Sparse solutions to linear inverse problems with multiple measurement vectors

  2005cited by this paper
• K-SVD : An Algorithm for Designing of Overcomplete Dictionaries for Sparse Representation

  2005influential reference
• Addendum: Regularization and variable selection via the elastic net

  2005cited by this paper
• Recovery of exact sparse representations in the presence of bounded noise

  2005cited by this paper
• Simultaneous Variable Selection

  2005influential reference
• Acquiring linear subspaces for face recognition under variable lighting

  2005cited by this paper
• Sparsity and smoothness via the fused lasso

  2005cited by this paper
• A Direct Formulation for Sparse PCA Using Semidefinite Programming

  2004cited by this paper
• Non-negative Matrix Factorization with Sparseness Constraints

  2004cited by this paper
• Stochastic Approximation and Recursive Algorithms and Applications

  2003cited by this paper
• Convex Analysis and Nonlinear Optimization: Theory and Examples. Jonathan M. Borwein and Adrian S. Lewis, Springer, New York, 2000

  2003cited by this paper
• A Modified Principal Component Technique Based on the LASSO

  2003cited by this paper
• Non-negative sparse coding

  2002influential reference
• From Few to Many: Illumination Cone Models for Face Recognition under Variable Lighting and Pose

  2001cited by this paper
• Blind source separation by sparse decomposition

  2001cited by this paper
• Ððòò Ëóùö Ëëôôööøøóò Ý Ëôôö×× Óñôó××øøóò Ò Ëëëòòð Øøóòòöý

  2000cited by this paper
• Learning Overcomplete Representations

  2000cited by this paper
• A new approach to variable selection in least squares problems

  2000cited by this paper
• Algorithms for Non-negative Matrix Factorization

  2000influential reference
• Frame based signal compression using method of optimal directions (MOD)

  1999cited by this paper
• Matrix Differential Calculus with Applications in Statistics and Econometrics (Revised Edition)

  1999cited by this paper
• A wavelet tour of signal processing

  1998cited by this paper
• Optimization Problems with Perturbations: A Guided Tour

  1998cited by this paper
• Atomic Decomposition by Basis Pursuit

  1998cited by this paper
• A View of the Em Algorithm that Justifies Incremental, Sparse, and other Variants

  1998cited by this paper
• Penalized Regressions: The Bridge versus the Lasso

  1998cited by this paper
• Sparse coding with an overcomplete basis set: a strategy employed by V1?

  1997cited by this paper
• Regression Shrinkage and Selection via the Lasso

  1996influential reference
• Learning and example selection for object and pattern detection

  1996cited by this paper
• Be more precise.

  1992cited by this paper
• Adaptive Algorithms and Stochastic Approximations

  1990cited by this paper
• A linear-time median-finding algorithm for projecting a vector on the simplex of Rn

  1989cited by this paper
• Matrix Differential Calculus with Applications

  1988cited by this paper
• The Theory of Max-Min and its Application to Weapons Allocation Problems

  1967cited by this paper
• Relations Between Two Sets of Variates

  1936cited by this paper

• Hierarchical Concept Embedding&Pursuit for Interpretable Image Classification

  2026cites this paper
• Anchor-to-Graph Structural Co-regularization for Scalable Multi-view Clustering

  2026cites this paper
• Sensor-Driven Strain Detection and Deep Learning Evaluation of Passive Exoskeletons in Industrial Tasks

  2026cites this paper
• From physics to machine learning and back: Part I - Learning with inductive biases in prognostics and health management (PHM)

  2026cites this paper
• Federated sparse representation-based anomaly detection

  2026cites this paper
• Variable Projected Augmented Lagrangian Methods for Generalized Lasso Problems

  2025cites this paper
• Discriminative latent representation harmonization of multicenter medical data

  2025cites this paper
• Deep sparse representation driven network for compressive imaging

  2025cites this paper
• Improved Bounds For Online Convex Optimization

  2025cites this paper
• Online multidimensional dictionary learning

  2025cites this paper
• Dual-level information fusion-boosted Fisher embedding discriminative dictionary learning for few-shot recognition

  2025cites this paper
• Structured Augmented Sparse Dictionary Learning for Incipient Fault Detection and Isolation

  2025cites this paper
• Non-Negative Matrix Factorization in Recommender Models: Concept, Survey, and Future Direction

  2025cites this paper
• Ambient noise-based passive reconstruction of dispersion curve in a thin-plate with complex boundary interferences using sparse learning

  2025cites this paper
• Generalized nonnegative structured Kruskal tensor regression

  2025cites this paper
• Dictionary Learning-Enabled Privacy Preserving Semantic Communication System

  2025cites this paper
• Rapid Learning for Efficient Audio Acquisition in Constrained Environment

  2025cites this paper
• Parsimonious Gaussian mixture models with piecewise-constant eigenvalue profiles

  2025cites this paper
• Viral particle prediction in wastewater treatment plants using nonlinear lifelong learning models

  2025cites this paper
• Learning-based super-resolution for remote sensing images via adaptive reconstruction regularization

  2025cites this paper
• Learning missing instances in intact and projection spaces for incomplete multi-view unsupervised feature selection

  2025cites this paper
• Decentralized Byzantine‐Resilient Dictionary Learning

  2025cites this paper
• Multiscale modes of functional brain connectivity

  2025cites this paper
• A Multipath AoA/AoD-Based Shared Dictionary Learning Framework for FDD Massive MIMO Channel Estimation

  2025cites this paper
• Deep class-weighted and class-shared dictionary learning for image classification

  2025cites this paper
• Enforcing Orderedness to Improve Feature Consistency

  2025cites this paper
• Bipartite graph regularized robust low-rank matrix factorization for fast semi-supervised image clustering

  2025cites this paper
• Low-Rank Equilibrium Propagation: An Online Incremental Learning Architecture for Analog-Based Hardware Accelerators

  2025cites this paper
• Online Learning With Non-convex Losses: New Condition To Achieve Small Dynamic Regret

  2025cites this paper
• RoseCDL: Robust and Scalable Convolutional Dictionary Learning for Rare-event Detection

  2025cites this paper
• A Scene Recognition Algorithm Using Features of Hybrid Scene Concepts

  2025cites this paper
• HAMD-RSISR: Hybrid Attention and Multidictionary for Remote Sensing Super-Resolution

  2025cites this paper
• Deep linear matrix approximate reconstruction with integrated BOLD signal denoising reveals reproducible hierarchical brain connectivity networks from multiband multi-echo fMRI.

  2025cites this paper
• Lattice: Learning to Efficiently Compress the Memory

  2025cites this paper
• Beyond FACS: Data-driven Facial Expression Dictionaries, with Application to Predicting Autism

  2025influential citation
• From Pixels and Words to Waves: A Unified Framework for Spectral Dictionary vLLMs

  2025cites this paper
• Sparse decomposition-based adaptive kurtogram analysis for bearing compound fault diagnosis

  2025cites this paper
• Structured Pattern Discovery Using Dictionary Learning for Incipient Fault Detection and Isolation

  2025cites this paper
• Real-time detection and classification of active regions from solar images using sector-based hashing

  2025cites this paper
• Are Sparse Autoencoders Useful for Java Function Bug Detection?

  2025cites this paper
• Free Lunch to Meet the Gap: Intermediate Domain Reconstruction for Cross-Domain Few-Shot Learning

  2025cites this paper
• Confident local similarity graphs for unsupervised feature selection on incomplete multi-view data

  2025cites this paper
• Joint Learning of Commonality and Specificity Dictionaries for Identifying Flow Regime in Oil–Gas–Water Three-Phase Flow

  2025cites this paper
• Sparse Latent Factor Forecaster (SLFF) with Iterative Inference for Transparent Multi-Horizon Commodity Futures Prediction

  2025cites this paper
• Effective sparse tracking with convolution-based discriminative sparse appearance model

  2025cites this paper
• Collaborative Group-Aware Hashing for Fast Recommender Systems

  2025cites this paper
• Discrete Facial Encoding: : A Framework for Data-driven Facial Display Discovery

  2025cites this paper
• Online Simplex-Structured Matrix Factorization

  2025cites this paper
• Color Normalization in Breast Cancer Immunohistochemistry Images Based on Sparse Stain Separation and Self-Sparse Fuzzy Clustering

  2025influential citation
• COSPADI: Compressing LLMs via Calibration-Guided Sparse Dictionary Learning

  2025cites this paper
• Tuberculosis Detection from Cough Recordings Using Bag-of-Words Classifiers

  2025cites this paper
• Learning of Patch-Based Smooth-Plus-Sparse Models for Image Reconstruction

  2024cites this paper
• A Zero-Shot Physics-Informed Dictionary Learning Approach for Sound Field Reconstruction

  2024cites this paper
• Online Dictionary Learning Method for Cone-beam X-ray Luminescence Computed Tomography Reconstruction: A Preliminary Simulation Study

  2024cites this paper
• Structured Joint Sparse Discriminative Dictionary Learning for Image Classification

  2024cites this paper
• Analysis and Synthesis Denoisers for Forward-Backward Plug-and-Play Algorithms

  2024influential citation
• Beyond Adapter Retrieval: Latent Geometry-Preserving Composition via Sparse Task Projection

  2024cites this paper
• Efficient and provable online reduced rank regression via online gradient descent

  2024cites this paper
• mmPalm: Unlocking Ubiquitous User Authentication through Palm Recognition with mmWave Signals

  2024cites this paper
• SIBS: A sparse encoder utilizing self-inspired bases for efficient image representation

  2024cites this paper
• Autoencoder Reconstruction Model for Long-Horizon Exploration

  2024cites this paper
• Ensemble Sparse Approach to Smart Meter Forecasting from Different Horizons

  2024cites this paper
• Multiday Personal Identification and Authentication Using Electromyogram Signals and Bag-of-Words Classification Models

  2024cites this paper
• Vortex rope identification in Francis turbine based on cyclostationary extended dictionary learning

  2024cites this paper
• Convergence and Complexity Guarantee for Inexact First-order Riemannian Optimization Algorithms

  2024cites this paper
• ICe: interior cevian initialization for enhanced reconstruction methods

  2024influential citation
• Dual-level feature assessment for unsupervised multi-view feature selection with latent space learning

  2024cites this paper
• Sparsity in transformers: A systematic literature review

  2024cites this paper
• Learning a Convex Patch-Based Synthesis Model via Deep Equilibrium

  2024cites this paper
• Locality regularized reconstruction: structured sparsity and Delaunay triangulations

  2024cites this paper
• On-the-fly spectral unmixing based on Kalman filtering

  2024influential citation
• Evaluation of sparsity metrics and evolutionary algorithms applied for normalization of H&E histological images

  2024cites this paper
• Near-Optimal Convex Simple Bilevel Optimization with a Bisection Method

  2024cites this paper
• Transcending the Limit of Local Window: Advanced Super-Resolution Transformer with Adaptive Token Dictionary

  2024cites this paper
• Dual Sparse Structured Subspaces and Graph Regularisation for Particle Swarm Optimisation-Based Multi-Label Feature Selection

  2024cites this paper
• Sparse linear dictionary reconstruction for removing microphonic noise from nuclear spectrometry measurements

  2024cites this paper
• Learning Spatiotemporal Brain Dynamics in Adolescents via Multimodal MEG and fMRI Data Fusion Using Joint Tensor/Matrix Decomposition

  2024cites this paper
• A METHOD FOR DETECTING SPATIOTEMPORAL PATTERNS OF CANCER BIOMARKERS-EVOKED ACTIVITY USING RADIAL BASIS FUNCTION NETWORK EXTRACTED TIME-DOMAIN FEATURES FROM CALCIUM IMAGING DATA.

  2024cites this paper
• Stochastic optimization with arbitrary recurrent data sampling

  2024cites this paper
• Structured collaborative sparse dictionary learning for monitoring of multimode processes

  2024cites this paper
• Comprehensive Study on Zeroing Neural Network With High-Order Evolutionary Formula, Nonlinear Functions, and Variable Parameter for Time-Changing Matrix Cholesky Decomposition

  2024cites this paper
• Image Deraining via Self-supervised Reinforcement Learning

  2024cites this paper
• Spatial resolution enhancement method for hyperspectral image based on spatial-spectral feature fusion

  2024cites this paper
• Joint Cauchy dictionary learning and graph learning for unsupervised feature selection

  2024cites this paper
• Online Tensor Max-Norm Regularization via Stochastic Optimization

  2024cites this paper
• Toward Real-Time Solar Content-Based Image Retrieval

  2024cites this paper
• Improved Dictionary Learning for FMRI Data Analysis Capturing Common and Individual Activation Maps

  2024cites this paper
• Quantum Algorithm for Sparse Online Learning with Truncated Gradient Descent

  2024cites this paper
• Anderson acceleration for iteratively reweighted 𝓁1 algorithm

  2024cites this paper
• SODL-IR-FISTA: sparse online dictionary learning with iterative reduction FISTA for cone-beam X-ray luminescence computed tomography

  2024cites this paper
• On-the-Fly Spectral Unmixing for Real-Time Hyperspectral Data Analysis

  2024cites this paper
• Uncovering student profiles. An explainable cluster analysis approach to PISA 2022

  2024cites this paper
• A Framework for Compressed Weighted Nonnegative Matrix Factorization

  2024cites this paper
• Kernel-Based Sparse Representation Learning With Global and Local Low-Rank Label Constraint

  2024cites this paper
• COVID-19 Detection Using ECG Signals and Bag-of-Words Classifier

  2023cites this paper
• Sun Magnetograms Retrieval from Vast Collections Through Small Hash Codes

  2023cites this paper
• Kernel recursive least squares dictionary learning algorithm

  2023cites this paper
• Convergent Regularization in Inverse Problems and Linear Plug-and-Play Denoisers

  2023cites this paper
• Matrix Factorization Techniques in Machine Learning, Signal Processing, and Statistics

  2023cites this paper
• Occlusion recovery face recognition based on information reconstruction

  2023cites this paper