Efficient preconditioning for noisy separable nonnegative matrix factorization problems by successive projection based low-rank approximations

DOI10.1007/S10994-017-5673-1zbMATH Open1459.65039arXiv1710.00387OpenAlexW2766826645MaRDI QIDQ1640558FDOQ1640558

Authors: Tomohiko Mizutani, Mirai Tanaka 

Publication date: 14 June 2018

Published in: Machine Learning (Search for Journal in Brave)

Abstract: The successive projection algorithm (SPA) can quickly solve a nonnegative matrix factorization problem under a separability assumption. Even if noise is added to the problem, SPA is robust as long as the perturbations caused by the noise are small. In particular, robustness against noise should be high when handling the problems arising from real applications. The preconditioner proposed by Gillis and Vavasis (2015) makes it possible to enhance the noise robustness of SPA. Meanwhile, an additional computational cost is required. The construction of the preconditioner contains a step to compute the top-$k$ truncated singular value decomposition of an input matrix. It is known that the decomposition provides the best rank-$k$ approximation to the input matrix; in other words, a matrix with the smallest approximation error among all matrices of rank less than $k$. This step is an obstacle to an efficient implementation of the preconditioned SPA. To address the cost issue, we propose a modification of the algorithm for constructing the preconditioner. Although the original algorithm uses the best rank-$k$ approximation, instead of it, our modification uses an alternative. Ideally, this alternative should have high approximation accuracy and low computational cost. To ensure this, our modification employs a rank-$k$ approximation produced by an SPA based algorithm. We analyze the accuracy of the approximation and evaluate the computational cost of the algorithm. We then present an empirical study revealing the actual performance of the SPA based rank-$k$ approximation algorithm and the modified preconditioned SPA.

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

Recommendations

• Robustness analysis of preconditioned successive projection algorithm for general form of separable NMF problem
• Semidefinite programming based preconditioning for more robust near-separable nonnegative matrix factorization
• Successive nonnegative projection algorithm for robust nonnegative blind source separation
• Sparse and unique nonnegative matrix factorization through data preprocessing
• Refinement of Hottopixx method for nonnegative matrix factorization under noisy separability

zbMATH Keywords

robustnesssingular value decompositionlow-rank approximationhyperspectral unmixingsuccessive projectionseparable nonnegative matrix factorization

Mathematics Subject Classification ID

Factorization of matrices (15A23) Preconditioners for iterative methods (65F08) Numerical methods for low-rank matrix approximation; matrix compression (65F55)

Cites Work

• SDPT3 — A Matlab software package for semidefinite programming, Version 1.3
• Matrix completion from noisy entries
• Title not available (Why is that?)
• Title not available (Why is that?)
• Finding structure with randomness: probabilistic algorithms for constructing approximate matrix decompositions
• Latent semantic indexing: A probabilistic analysis
• On the complexity of nonnegative matrix factorization
• Computing a nonnegative matrix factorization -- provably
• Introduction to Information Retrieval
• Handbook series linear algebra. Linear least squares solutions by Householder transformations
• Robustness analysis of preconditioned successive projection algorithm for general form of separable NMF problem
• Ellipsoidal rounding for nonnegative matrix factorization under noisy separability
• Enhancing pure-pixel identification performance via preconditioning
• Semidefinite programming based preconditioning for more robust near-separable nonnegative matrix factorization
• Computation of Minimum-Volume Covering Ellipsoids
• Title not available (Why is that?)
• On selecting a maximum volume sub-matrix of a matrix and related problems
• A randomized algorithm for principal component analysis
• Linear convergence of a modified Frank–Wolfe algorithm for computing minimum-volume enclosing ellipsoids
• On a decomposition lemma for positive semi-definite block-matrices
• Spectral Unmixing via Data-Guided Sparsity
• Sketching as a tool for numerical linear algebra
• Subspace Iteration Randomization and Singular Value Problems
• Robust Hyperspectral Unmixing With Correntropy-Based Metric
• Compressed Nonnegative Matrix Factorization Is Fast and Accurate

Cited In (4)

• Robustness analysis of preconditioned successive projection algorithm for general form of separable NMF problem
• Enhancing pure-pixel identification performance via preconditioning
• Semidefinite programming based preconditioning for more robust near-separable nonnegative matrix factorization
• CMD: controllable matrix decomposition with global optimization for deep neural network compression

Uses Software

• SDPT3

This page was built for publication: Efficient preconditioning for noisy separable nonnegative matrix factorization problems by successive projection based low-rank approximations

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