On the Wiberg Algorithm for Matrix Factorization in the Presence of Missing Components
On the Wiberg Algorithm for Matrix Factorization in the Presence of Missing Components
复制标题
DOI：
10.1007/s11263-006-9785-5
复制
发表时间：
2007-05
影响因子：
19.5
通讯作者：
Takayuki Okatani;K. Deguchi
中科院分区：
文献类型：
--
作者：
Takayuki Okatani;K. Deguchi
本文考虑将一个缺失成分矩阵分解为两个较小矩阵的乘积的问题，也称为缺失数据主成分分析（PCAMD）。Wiberg算法是应用数学界为解决这一问题而开发的一种数值算法。我们认为该算法在计算机视觉界还没有得到正确的理解。虽然在我们的社区有很多研究，几乎每一个都涉及到Wiberg的研究，但据我们所知，还没有文献对Wiberg算法的性能进行研究，也没有文献对算法的细节进行介绍。在本文中，我们提出了该算法的推导以及在其实现中需要仔细考虑的问题，然后检查其性能。实验结果表明，Wiberg算法表现出相当好的性能，这应该与我们社区的传统观点相矛盾，即基于最小化的算法往往不能相对频繁地收敛到全局最小值。Wiberg算法的性能是这样的，即使从随机初始值开始，它在大多数情况下收敛到一个正确的解决方案，即使矩阵有许多缺失的组件和数据被非常强的噪声污染。我们的结论是，Wiberg算法也可以作为计算机视觉问题的标准算法。
This paper considers the problem of factorizing a matrix with missing components into a product of two smaller matrices, also known as principal component analysis with missing data (PCAMD). The Wiberg algorithm is a numerical algorithm developed for the problem in the community of applied mathematics. We argue that the algorithm has not been correctly understood in the computer vision community. Although there are many studies in our community, almost every one of which refers to the Wiberg study, as far as we know, there is no literature in which the performance of the Wiberg algorithm is investigated or the detail of the algorithm is presented. In this paper, we present derivation of the algorithm along with a problem in its implementation that needs to be carefully considered, and then examine its performance. The experimental results demonstrate that the Wiberg algorithm shows a considerably good performance, which should contradict the conventional view in our community, namely that minimization-based algorithms tend to fail to converge to a global minimum relatively frequently. The performance of the Wiberg algorithm is such that even starting with random initial values, it converges in most cases to a correct solution, even when the matrix has many missing components and the data are contaminated with very strong noise. Our conclusion is that the Wiberg algorithm can also be used as a standard algorithm for the problems of computer vision.