Stochastic Subsampling for Factorizing Huge Matrices

DOI10.1109/TSP.2017.2752697MaRDI QIDQ4621521zbMATH OpenOpenAlexFDO

Authors Arthur Mensch, Julien Mairal, Bertrand Thirion, Gaël Varoquaux

Publication date 12 February 2019

Published in IEEE Transactions on Signal Processing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1701.05363

Mathematics Subject Classification ID

Signal theory (characterization, reconstruction, filtering, etc.) (94A12) Sampling theory in information and communication theory (94A20)

Abstract: We present a matrix-factorization algorithm that scales to input matrices with both huge number of rows and columns. Learned factors may be sparse or dense and/or non-negative, which makes our algorithm suitable for dictionary learning, sparse component analysis, and non-negative matrix factorization. Our algorithm streams matrix columns while subsampling them to iteratively learn the matrix factors. At each iteration, the row dimension of a new sample is reduced by subsampling, resulting in lower time complexity compared to a simple streaming algorithm. Our method comes with convergence guarantees to reach a stationary point of the matrix-factorization problem. We demonstrate its efficiency on massive functional Magnetic Resonance Imaging data (2 TB), and on patches extracted from hyperspectral images (103 GB). For both problems, which involve different penalties on rows and columns, we obtain significant speed-ups compared to state-of-the-art algorithms.

Cited in

(3)

• Compressed dictionary learning
• Online matrix factorization for Markovian data and applications to network dictionary learning
• Minimization by incremental stochastic surrogate optimization for large scale nonconvex problems

This page was built for publication: Stochastic Subsampling for Factorizing Huge Matrices

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4621521)