Learning nonnegative matrix factorizations from compressed data
This paper proposes a theoretical and practical framework for performing nonnegative matrix factorization (NMF) from compressed measurements. The authors address the computational and memory challenges of standard NMF through a sketch-and-solve approach, using randomized sketches that are either data-oblivious or data-adapted. The resulting optimization problems depend only on the compressed data and require at most one or two passes over the original matrix. The method is motivated in part by randomized sketching techniques developed in related work, including by [\textit{C.A. Haselby} et al., Appl. Comput. Harmon. Anal. 66, 161--192 (2023; Zbl 07714159)], while building on earlier approaches to compressed NMF.\N\NThe main contribution is a careful connection between the optimal solutions of the compressed problems and those of the original NMF problem. The authors consider two-sided row and column sketching, as well as one-sided orthogonal and approximately orthogonal sketching, and develop memory-efficient multiplicative-update algorithms for the resulting objectives. A technical challenge is that random sketches may destroy the nonnegativity needed by standard MU updates; this is addressed through suitable regularization/shift terms. Numerical experiments on synthetic, image and text datasets demonstrate comparable factorization performance using only about 5\% of the original data, while the paper also discusses limitations of the current theoretical results, particularly for two-sided compression.
- A fast randomized algorithm for the approximation of matrices
- A statistical perspective on randomized sketching for ordinary least-squares
- Algorithms for nonnegative matrix factorization with the -divergence
- Block majorization-minimization with diminishing radius for constrained nonsmooth nonconvex optimization
- Compressed Nonnegative Matrix Factorization Is Fast and Accurate
- Fast Nonnegative Matrix/Tensor Factorization Based on Low-Rank Approximation
- Faster least squares approximation
- Finding structure with randomness: probabilistic algorithms for constructing approximate matrix decompositions
- Frequent directions: simple and deterministic matrix sketching
- Improved approximation algorithms for large matrices via random projections
- Learning the parts of objects by non-negative matrix factorization
- Lower bounds on nonnegative rank via nonnegative nuclear norms
- Lower Memory Oblivious (Tensor) Subspace Embeddings with Fewer Random Bits: Modewise Methods for Least Squares
- Modewise operators, the tensor restricted isometry property, and low-rank tensor recovery
- Non-negative matrix factorization with sparseness constraints
- Nonnegative matrix factorization
- On the complexity of nonnegative matrix factorization
- Practical sketching algorithms for low-rank matrix approximation
- Randomized Algorithms for Matrices and Data
- Randomized algorithms for symmetric nonnegative matrix factorization
- Randomized low-rank approximations beyond Gaussian random matrices
- Sketching as a tool for numerical linear algebra
- Turnstile streaming algorithms might as well be linear sketches
This page was built for publication: Learning nonnegative matrix factorizations from compressed data
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7299120)
