Simplex-Structured Matrix Factorization: Sparsity-based Identifiability and Provably Correct Algorithms

Abstract

In this paper, we provide novel algorithms with identifiability guarantees for simplex-structured matrix factorization (SSMF), a generalization of nonnegative matrix factorization. Current state-of-the-art algorithms that provide identifiability results for SSMF rely on the sufficiently scattered condition (SSC) which requires the data points to be well spread within the convex hull of the basis vectors. The conditions under which our proposed algorithms recover the unique decomposition is in most cases much weaker than the SSC. We only require to have $d$ points on each facet of the convex hull of the basis vectors whose dimension is $d-1$. The key idea is based on extracting facets containing the largest number of points. We illustrate the effectiveness of our approach on synthetic data sets and hyperspectral images, showing that it outperforms state-of-the-art SSMF algorithms as it is able to handle higher noise levels, rank deficient matrices, outliers, and input data that highly violates the SSC.

arXiv comment38 pages

References in corpus (13)

• Fast and Robust Recursive Algorithms for Separable Nonnegative Matrix Factorization
• Nonnegative Matrix Factorization for Signal and Data Analytics: Identifiability, Algorithms, and Applications
• Identifiability of the Simplex Volume Minimization Criterion for Blind Hyperspectral Unmixing: The No Pure-Pixel Case
• Robust Volume Minimization-Based Matrix Factorization for Remote Sensing and Document Clustering
• Successive Nonnegative Projection Algorithm for Robust Nonnegative Blind Source Separation
• On Identifiability of Nonnegative Matrix Factorization
• Blind Audio Source Separation with Minimum-Volume Beta-Divergence NMF
• A Fast Hyperplane-Based Minimum-Volume Enclosing Simplex Algorithm for Blind Hyperspectral Unmixing
• Self-Dictionary Sparse Regression for Hyperspectral Unmixing: Greedy Pursuit and Pure Pixel Search are Related
• Algorithms and Comparisons of Non-negative Matrix Factorization with Volume Regularization for Hyperspectral Unmixing
• Exact and Heuristic Algorithms for Semi-Nonnegative Matrix Factorization
• Computing Large-Scale Matrix and Tensor Decomposition with Structured Factors: A Unified Nonconvex Optimization Perspective
• Identifiability of Complete Dictionary Learning

Cited by in corpus (9)

• A consistent and flexible framework for deep matrix factorizations
• Multiplicative Updates for NMF with $\beta$-Divergences under Disjoint Equality Constraints
• Partial Identifiability for Nonnegative Matrix Factorization
• Deep Nonnegative Matrix Factorization with Beta Divergences
• Smoothed Separable Nonnegative Matrix Factorization
• Bounded Simplex-Structured Matrix Factorization: Algorithms, Identifiability and Applications
• Checking the Sufficiently Scattered Condition using a Global Non-Convex Optimization Software
• Dual Simplex Volume Maximization for Simplex-Structured Matrix Factorization
• On the Robustness of the Successive Projection Algorithm