Separable Simplex-structured Matrix Factorization: Robustness of Combinatorial Approaches

Abstract

In this paper, we consider the following low-rank matrix approximation problem, referred to as separable simplex-structured matrix factorization: given an input matrix X, find W and H such that X ≈ WH where the columns of W are chosen among the columns of X and where the entries of each column of H are nonnegative and sum to at most one. This problem has been studied extensively in the literature and is a generalization of separable nonnegative matrix factorization, with applications for example in hyperspectral unmixing and document analysis. Many methods have been proposed to tackle this problem; the three main classes are greedy algorithms, convex relaxations and combinatorial approaches. For the first two classes, robustness to noise of several algorithms have been characterized precisely. As far as we know, no such result exist for combinatorial formulations. This paper fills in this gap: we provide a tight robustness analysis of an exact combinatorial formulation of the problem. Although such formulations are difficult to optimize, we show that they lead to stronger robustness to noise than greedy algorithms and convex relaxations.