Efficient preconditioning for noisy separable nonnegative matrix factorization problems by successive projection based low-rank approximations
Efficient preconditioning for noisy separable nonnegative matrix factorization problems by successive projection based low-rank approximations
复制标题
DOI：
10.1007/s10994-017-5673-1
复制
发表时间：
2018-04
期刊：
影响因子：
7.5
通讯作者：
Tomohiko Mizutani;Mirai Tanaka
中科院分区：
文献类型：
--
作者：
Tomohiko Mizutani;Mirai Tanaka
连续投影算法（SPA）可以快速求解在可分性假设下的非负矩阵分解问题。即使在问题中加入噪声，只要噪声引起的扰动较小，SPA也是鲁棒的。特别是，在处理实际应用中产生的问题时，对噪声的鲁棒性应该很高。Gillis和Vavasis提出的预调节器（SIAM J Optim 25(1): 677-698, 2015）使得增强SPA的噪声鲁棒性成为可能。同时，还需要额外的计算成本。预条件的构造包含了计算输入矩阵的顶截断奇异值分解的步骤。已知该分解提供了输入矩阵的最佳秩-k近似；换句话说，在所有秩次较少的矩阵中，近似误差最小的矩阵。这一步骤阻碍了预处理SPA的有效实施。为了解决成本问题，我们提出了一种构造预条件的改进算法。虽然原始算法使用了最佳rank-k近似，但我们的修改使用了另一种方法。理想情况下，这种替代方法应该具有较高的近似精度和较低的计算成本。为了确保这一点，我们的修改采用了由基于SPA的算法产生的秩近似。我们分析了近似的准确性，并评估了算法的计算成本。然后，我们提出了一个实证研究，揭示了基于SPA的秩-k近似算法和改进的预置SPA的实际性能。
The successive projection algorithm (SPA) can quickly solve a nonnegative matrix factorization problem under a separability assumption. Even if noise is added to the problem, SPA is robust as long as the perturbations caused by the noise are small. In particular, robustness against noise should be high when handling the problems arising from real applications. The preconditioner proposed by Gillis and Vavasis (SIAM J Optim 25(1):677–698, 2015) makes it possible to enhance the noise robustness of SPA. Meanwhile, an additional computational cost is required. The construction of the preconditioner contains a step to compute the top-ktruncated singular value decomposition of an input matrix. It is known that the decomposition provides the best rank-kapproximation to the input matrix; in other words, a matrix with the smallest approximation error among all matrices of rank less thank. This step is an obstacle to an efficient implementation of the preconditioned SPA. To address the cost issue, we propose a modification of the algorithm for constructing the preconditioner. Although the original algorithm uses the best rank-kapproximation, instead of it, our modification uses an alternative. Ideally, this alternative should have high approximation accuracy and low computational cost. To ensure this, our modification employs a rank-kapproximation produced by an SPA based algorithm. We analyze the accuracy of the approximation and evaluate the computational cost of the algorithm. We then present an empirical study revealing the actual performance of the SPA based rank-kapproximation algorithm and the modified preconditioned SPA.