Checking the Sufficiently Scattered Condition using a Global Non-Convex Optimization Software

Abstract

The sufficiently scattered condition (SSC) is a key condition in the study of identifiability of various matrix factorization problems, including nonnegative, minimum-volume, symmetric, simplex-structured, and polytopic matrix factorizations. The SSC allows one to guarantee that the computed matrix factorization is unique/identifiable, up to trivial ambiguities. However, this condition is NP-hard to check in general. In this paper, we show that it can however be checked in a reasonable amount of time in realistic scenarios, when the factorization rank is not too large. This is achieved by formulating the problem as a non-convex quadratic optimization problem over a bounded set. We use the global non-convex optimization software Gurobi, and showcase the usefulness of this code on synthetic data sets and on real-world hyperspectral images.

arXiv comment14 pages, code available from https://gitlab.com/ngillis/check-ssc

References in corpus (11)

• 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
• On Identifiability of Nonnegative Matrix Factorization
• Hyperspectral Unmixing: Ground Truth Labeling, Datasets, Benchmark Performances and Survey
• Blind Audio Source Separation with Minimum-Volume Beta-Divergence NMF
• Algorithms and Comparisons of Non-negative Matrix Factorization with Volume Regularization for Hyperspectral Unmixing
• Simplex-Structured Matrix Factorization: Sparsity-based Identifiability and Provably Correct Algorithms
• Recovering Joint Probability of Discrete Random Variables from Pairwise Marginals
• Polytopic Matrix Factorization: Determinant Maximization Based Criterion and Identifiability
• Bounded Simplex-Structured Matrix Factorization: Algorithms, Identifiability and Applications