Incremental singular value decomposition (SVD) was proposed by Brand to efficiently compute the SVD of a matrix. The algorithm needs to compute thousands or millions of orthogonal matrices and to multiply them together. However, the multiplications may corrode the orthogonality. Hence many reorthogonalizations are needed in practice. In [Linear Algebra and its Applications 415 (2006) 20-30], Brand asked "It is an open question how often this is necessary to guarantee a certain overall level of numerical precision; it does not change the overall complexity." In this paper, we answer this question and the answer is we can avoid computing the large amount of those orthogonal matrices and hence the reorthogonalizations are not necessary by modifying his algorithm. We prove that the modification does not change the outcomes of the algorithm. Numerical experiments are presented to illustrate the performance of our modification.
翻译:Brand提出递增单值分解法(SVD)是为了有效地计算矩阵的SVD。算法需要计算千或百万个正方形矩阵,并把它们相乘。 但是, 乘法可能会腐蚀正方形。 因此, 在实践中需要许多再解剖法。 在[ Linear Algebra 及其应用 415(2006 20-30 ) 中, Brand 问道 : “ 这是一个尚未解决的问题, 保证总的数字精确度需要多久才能保证一次总的数字精确度; 它不会改变整体复杂性。 ” 在本文中, 我们回答这个问题, 答案是, 我们可以避免计算这些正方形矩阵的大量数据, 因此通过修改他的算法是没有必要再解算法。 我们证明修改不会改变算法的结果。 数字实验是用来说明我们修改过程的绩效的。