Semidefinite Programming Based Preconditioning for More Robust Near-Separable Nonnegative Matrix Factorization

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 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 allow us to apply the preconditioning on large-scale real-world hyperspectral images.

25 pages, 6 figures, 4 tables. New numerical experiments, additional remarks and comments

References in corpus (8)

• Fast and Robust Recursive Algorithms for Separable Nonnegative Matrix Factorization
• A Practical Algorithm for Topic Modeling with Provable Guarantees
• Fast Conical Hull Algorithms for Near-separable Non-negative Matrix Factorization
• Sparse and Unique Nonnegative Matrix Factorization Through Data Preprocessing
• Robust Near-Separable Nonnegative Matrix Factorization Using Linear Optimization
• Robustness Analysis of Hottopixx, a Linear Programming Model for Factoring Nonnegative Matrices
• Ellipsoidal Rounding for Nonnegative Matrix Factorization Under Noisy Separability
• Faster Subset Selection for Matrices and Applications

Cited by in corpus (21)

• Nonnegative Matrix Factorization for Signal and Data Analytics: Identifiability, Algorithms, and Applications
• Successive Nonnegative Projection Algorithm for Robust Nonnegative Blind Source Separation
• Mixed Membership Estimation for Social Networks
• Heuristics for Exact Nonnegative Matrix Factorization
• Introduction to Nonnegative Matrix Factorization
• Consistent Estimation of Mixed Memberships with Successive Projections
• Enhancing Pure-Pixel Identification Performance via Preconditioning
• Robustness Analysis of Preconditioned Successive Projection Algorithm for General Form of Separable NMF Problem
• Maximum Volume Inscribed Ellipsoid: A New Simplex-Structured Matrix Factorization Framework via Facet Enumeration and Convex Optimization
• A useful criterion on studying consistent estimation in community detection
• Finding mixed memberships in categorical data
• Directed mixed membership stochastic blockmodel
• On Restricted Nonnegative Matrix Factorization
• Majorization-minimization Bregman proximal gradient algorithms for NMF with the Kullback--Leibler divergence
• Endmember Extraction from Hyperspectral Images Using Self-Dictionary Approach with Linear Programming
• Spectral Clustering by Ellipsoid and Its Connection to Separable Nonnegative Matrix Factorization
• On the Robustness of the Successive Projection Algorithm
• Impact of regularization on spectral clustering under the mixed membership stochastic block model
• Mixed membership estimation for categorical data with weighted responses
• Fixed Point Algorithm for Solving Nonmonotone Variational Inequalities in Nonnegative Matrix Factorization
• Overlapping and nonoverlapping models