Checking the Sufficiently Scattered Condition using a Global Non-Convex Optimization Software
This work provides a practical tool for verifying identifiability in matrix factorization problems, which is incremental but useful for researchers in fields like hyperspectral imaging and data analysis.
The paper tackles the NP-hard problem of checking the sufficiently scattered condition (SSC) for matrix factorization identifiability by formulating it as a non-convex quadratic optimization problem and solving it with Gurobi software, demonstrating feasibility in realistic scenarios with moderate factorization ranks on synthetic and real-world data.
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.