Semidefinite Programming Based Preconditioning for More Robust Near-Separable Nonnegative Matrix Factorization
Authors:
- Nicolas GillisNGNicolas Gillis
- Stephen A. VavasisSVStephen A. Vavasis
- 1 January 2015
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Optimization
- Vol. 25 (1) , 677-698
Abstract
Nonnegative matrix factorization (NMF) under the separability assumption can provably be solved efficiently, even in the presence of noise, and has been shown to be a powerful technique in document classification and hyperspectral unmixing. This problem is referred to as near-separable NMF and requires that there exists a cone spanned by a small subset of the columns of the input nonnegative matrix approximately containing all columns. In this paper, we propose a preconditioning based on the minimum volume ellipsoid and semidefinite programming making the input matrix well-conditioned. This in turn can improve significantly the performance of near-separable NMF algorithms which is illustrated on the popular successive projection algorithm (SPA). The new preconditioned SPA is provably more robust to noise, and outperforms SPA on several synthetic data sets. We also show how an active-set method allows us to apply the preconditioning on large-scale real-world hyperspectral images.Keywords
All Related Versions
This publication has 19 references indexed in Scilit:
- Fast and Robust Recursive Algorithmsfor Separable Nonnegative Matrix FactorizationIEEE Transactions on Pattern Analysis and Machine Intelligence, 2014
- Robustness Analysis of Hottopixx, a Linear Programming Model for Factoring Nonnegative MatricesSIAM Journal on Matrix Analysis and Applications, 2013
- Hyperspectral Data Geometry-Based Estimation of Number of Endmembers Using p-Norm-Based Pure Pixel Identification AlgorithmIEEE Transactions on Geoscience and Remote Sensing, 2012
- Tissue-Specific Compartmental Analysis for Dynamic Contrast-Enhanced MR Imaging of Complex TumorsIEEE Transactions on Medical Imaging, 2011
- A Convex Analysis Framework for Blind Separation of Non-Negative SourcesIEEE Transactions on Signal Processing, 2008
- Linear convergence of a modified Frank–Wolfe algorithm for computing minimum-volume enclosing ellipsoidsOptimization Methods and Software, 2008
- Minimum-Volume Enclosing Ellipsoids and Core SetsJournal of Optimization Theory and Applications, 2005
- The successive projections algorithm for variable selection in spectroscopic multicomponent analysisChemometrics and Intelligent Laboratory Systems, 2001
- Rounding of Polytopes in the Real Number Model of ComputationMathematics of Operations Research, 1996
- On the complexity of approximating the maximal inscribed ellipsoid for a polytopeMathematical Programming, 1993