Smoothed Separable Nonnegative Matrix Factorization
arXiv:2110.05528 · doi:10.1016/j.laa.2023.07.013
Abstract
Given a set of data points belonging to the convex hull of a set of vertices, a key problem in linear algebra, signal processing, data analysis and machine learning is to estimate these vertices in the presence of noise. Many algorithms have been developed under the assumption that there is at least one nearby data point to each vertex; two of the most widely used ones are vertex component analysis (VCA) and the successive projection algorithm (SPA). This assumption is known as the pure-pixel assumption in blind hyperspectral unmixing, and as the separability assumption in nonnegative matrix factorization. More recently, Bhattacharyya and Kannan (ACM-SIAM Symposium on Discrete Algorithms, 2020) proposed an algorithm for learning a latent simplex (ALLS) that relies on the assumption that there is more than one nearby data point to each vertex. In that scenario, ALLS is probalistically more robust to noise than algorithms based on the separability assumption. In this paper, inspired by ALLS, we propose smoothed VCA (SVCA) and smoothed SPA (SSPA) that generalize VCA and SPA by assuming the presence of several nearby data points to each vertex. We illustrate the effectiveness of SVCA and SSPA over VCA, SPA and ALLS on synthetic data sets, on the unmixing of hyperspectral images, and on feature extraction on facial images data sets. In addition, our study highlights new theoretical results for VCA.
arXiv comment31 pages + 10 pages of supplementary. Many clarifications have been brought to the paper, and we have added numerical experiments on facial images
References in corpus (11)
- Fast and Robust Recursive Algorithms for Separable Nonnegative Matrix Factorization
- Accelerated Multiplicative Updates and Hierarchical ALS Algorithms for Nonnegative Matrix Factorization
- Identifiability of the Simplex Volume Minimization Criterion for Blind Hyperspectral Unmixing: The No Pure-Pixel Case
- Successive Nonnegative Projection Algorithm for Robust Nonnegative Blind Source Separation
- Robust Near-Separable Nonnegative Matrix Factorization Using Linear Optimization
- A Fast Hyperplane-Based Minimum-Volume Enclosing Simplex Algorithm for Blind Hyperspectral Unmixing
- Robustness Analysis of Hottopixx, a Linear Programming Model for Factoring Nonnegative Matrices
- Simplex-Structured Matrix Factorization: Sparsity-based Identifiability and Provably Correct Algorithms
- Probabilistic Simplex Component Analysis
- Intersecting Faces: Non-negative Matrix Factorization With New Guarantees
- Learning a Latent Simplex in Input-Sparsity Time