Separable Simplex-structured Matrix Factorization: Robustness of Combinatorial Approaches
Separable Simplex-structured Matrix Factorization: Robustness of Combinatorial Approaches
复制标题
可分离单纯形结构矩阵分解：组合方法的鲁棒性
DOI：
10.1109/icassp.2019.8682644
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Nicolas Gillis
中科院分区：
文献类型：
--
作者：
Nicolas Gillis
本文考虑了以下低秩矩阵逼近问题，称为可分单纯形结构矩阵分解：给定一个输入矩阵X，求W和H，使得X <$WH其中W的列是从X的列中选择的，且H的每一列的元素是非负的且和至多为1.这个问题已经在文献中被广泛研究，并且是可分离非负矩阵分解的推广，例如在高光谱解混和文档分析中的应用。已经提出了许多方法来解决这个问题;三个主要类别是贪婪算法，凸松弛和组合方法。对于前两类，几种算法对噪声的鲁棒性已经被精确地表征。据我们所知，对于组合公式，不存在这样的结果。本文填补了这一空白：我们提供了一个严格的鲁棒性分析的问题的精确组合制定。虽然这样的配方是很难优化，我们表明，它们导致更强的鲁棒性比贪婪算法和凸松弛噪声。
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.