Stochastic Subsampling for Factorizing Huge Matrices
arXiv:1701.05363 · doi:10.1109/TSP.2017.2752697
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.
arXiv commentIEEE Transactions on Signal Processing, Institute of Electrical and Electronics Engineers, A Paraître
References in corpus (8)
- Scikit-learn: Machine Learning in Python
- Pathwise coordinate optimization
- Subspace Learning and Imputation for Streaming Big Data Matrices and Tensors
- Optimization with First-Order Surrogate Functions
- Stochastic Majorization-Minimization Algorithms for Large-Scale Optimization
- Dictionary Learning for Massive Matrix Factorization
- Iterative Hessian sketch: Fast and accurate solution approximation for constrained least-squares
- A randomized algorithm for principal component analysis
Cited by in corpus (4)
- Online matrix factorization for Markovian data and applications to Network Dictionary Learning
- Joint Majorization-Minimization for Nonnegative Matrix Factorization with the -divergence
- Sparse Quantized Spectral Clustering
- Extracting representations of cognition across neuroimaging studies improves brain decoding