Fast and Robust Recursive Algorithms for Separable Nonnegative Matrix Factorization

Abstract

In this paper, we study the nonnegative matrix factorization problem under the separability assumption (that is, there exists a cone spanned by a small subset of the columns of the input nonnegative data matrix containing all columns), which is equivalent to the hyperspectral unmixing problem under the linear mixing model and the pure-pixel assumption. We present a family of fast recursive algorithms, and prove they are robust under any small perturbations of the input data matrix. This family generalizes several existing hyperspectral unmixing algorithms and hence provides for the first time a theoretical justification of their better practical performance.

30 pages, 2 figures, 7 tables. Main change: Improvement of the bound of the main theorem (Th. 3), replacing r with sqrt(r)

References in corpus (4)

• Factoring nonnegative matrices with linear programs
• Sparse and Unique Nonnegative Matrix Factorization Through Data Preprocessing
• Robustness Analysis of Hottopixx, a Linear Programming Model for Factoring Nonnegative Matrices
• Computing a Nonnegative Matrix Factorization -- Provably

Cited by in corpus (74)

• Nonnegative Matrix Factorization for Signal and Data Analytics: Identifiability, Algorithms, and Applications
• Linked Component Analysis from Matrices to High Order Tensors: Applications to Biomedical Data
• Fast Conical Hull Algorithms for Near-separable Non-negative Matrix Factorization
• Identifiability of the Simplex Volume Minimization Criterion for Blind Hyperspectral Unmixing: The No Pure-Pixel Case
• Hierarchical Clustering of Hyperspectral Images using Rank-Two Nonnegative Matrix Factorization
• Efficient Nonnegative Tucker Decompositions: Algorithms and Uniqueness
• Robust Volume Minimization-Based Matrix Factorization for Remote Sensing and Document Clustering
• Sparse and Unique Nonnegative Matrix Factorization Through Data Preprocessing
• Deep Spectrum Cartography: Completing Radio Map Tensors Using Learned Neural Models
• Deep matrix factorizations
• Successive Nonnegative Projection Algorithm for Robust Nonnegative Blind Source Separation
• On Identifiability of Nonnegative Matrix Factorization
• Robust Near-Separable Nonnegative Matrix Factorization Using Linear Optimization
• Self-Dictionary Sparse Regression for Hyperspectral Unmixing: Greedy Pursuit and Pure Pixel Search are Related
• A Nonlinear Orthogonal Non-Negative Matrix Factorization Approach to Subspace Clustering
• Unsupervised Classification in Hyperspectral Imagery with Nonlocal Total Variation and Primal-Dual Hybrid Gradient Algorithm
• Semidefinite Programming Based Preconditioning for More Robust Near-Separable Nonnegative Matrix Factorization
• Algorithms and Comparisons of Non-negative Matrix Factorization with Volume Regularization for Hyperspectral Unmixing
• A Nonconvex Splitting Method for Symmetric Nonnegative Matrix Factorization: Convergence Analysis and Optimality
• Detecting Overlapping Communities in Networks Using Spectral Methods
• An Empirical-Bayes Approach to Recovering Linearly Constrained Non-Negative Sparse Signals
• Compressed Nonnegative Matrix Factorization is Fast and Accurate
• Mixed Membership Estimation for Social Networks
• Generalized Separable Nonnegative Matrix Factorization
• Introduction to Nonnegative Matrix Factorization
• Nonparametric Detection of Nonlinearly Mixed Pixels and Endmember Estimation in Hyperspectral Images
• Sparse and Non-Negative BSS for Noisy Data
• A Fast Gradient Method for Nonnegative Sparse Regression with Self Dictionary
• Using separable non-negative matrix factorization techniques for the analysis of time-resolved Raman spectra
• Dictionary-based Tensor Canonical Polyadic Decomposition
• Ellipsoidal Rounding for Nonnegative Matrix Factorization Under Noisy Separability
• Simplex-Structured Matrix Factorization: Sparsity-based Identifiability and Provably Correct Algorithms
• Scalable methods for nonnegative matrix factorizations of near-separable tall-and-skinny matrices
• Recovering Joint Probability of Discrete Random Variables from Pairwise Marginals
• Estimating Mixed Memberships with Sharp Eigenvector Deviations
• Consistent Estimation of Mixed Memberships with Successive Projections
• Beyond Alternating Updates for Matrix Factorization with Inertial Bregman Proximal Gradient Algorithms
• Probabilistic Simplex Component Analysis
• Block Alternating Bregman Majorization Minimization with Extrapolation
• Intersecting Faces: Non-negative Matrix Factorization With New Guarantees
• Recent Advances in Text Analysis
• Rank-One NMF-Based Initialization for NMF and Relative Error Bounds under a Geometric Assumption
• Memory-Efficient Convex Optimization for Self-Dictionary Separable Nonnegative Matrix Factorization: A Frank-Wolfe Approach
• Learning Nonlinear Mixtures: Identifiability and Algorithm
• Multi-block Bregman proximal alternating linearized minimization and its application to orthogonal nonnegative matrix factorization
• Enhancing Pure-Pixel Identification Performance via Preconditioning
• Robustness Analysis of Preconditioned Successive Projection Algorithm for General Form of Separable NMF Problem
• Divide-and-Conquer Learning by Anchoring a Conical Hull
• Maximum Volume Inscribed Ellipsoid: A New Simplex-Structured Matrix Factorization Framework via Facet Enumeration and Convex Optimization
• Identifiability-Guaranteed Simplex-Structured Post-Nonlinear Mixture Learning via Autoencoder
• Mixed Membership Graph Clustering via Systematic Edge Query
• Relative Pairwise Relationship Constrained Non-negative Matrix Factorisation
• Hierarchically Regularized Deep Forecasting
• A Spectral Method for Identifiable Grade of Membership Analysis with Binary Responses
• Smoothed Separable Nonnegative Matrix Factorization
• Provably robust blind source separation of linear-quadratic near-separable mixtures
• Penalized matrix decomposition for denoising, compression, and improved demixing of functional imaging data
• Convex Programming Based Spectral Clustering
• Provable Overlapping Community Detection in Weighted Graphs
• Refinement of Hottopixx Method for Nonnegative Matrix Factorization Under Noisy Separability
• Necessary and Sufficient Conditions and a Provably Efficient Algorithm for Separable Topic Discovery
• Deep NMF Topic Modeling
• How to Fake Multiply by a Gaussian Matrix
• Spectral Clustering by Ellipsoid and Its Connection to Separable Nonnegative Matrix Factorization
• Endmember Extraction from Hyperspectral Images Using Self-Dictionary Approach with Linear Programming
• On the Robustness of the Successive Projection Algorithm
• Near-separable Non-negative Matrix Factorization with ${\ell }_1$- and Bregman Loss Functions
• Recovery of Joint Probability Distribution from one-way marginals: Low rank Tensors and Random Projections
• Dirichlet Simplex Nest and Geometric Inference
• Tangent Space Based Alternating Projections for Nonnegative Low Rank Matrix Approximation
• Deep topic modeling by multilayer bootstrap network and lasso
• Nonnegative Low Rank Tensor Approximation and its Application to Multi-dimensional Images
• Techniques for clustering interaction data as a collection of graphs
• Consistency of regularized spectral clustering in degree-corrected mixed membership model