期刊
ELECTRONIC JOURNAL OF LINEAR ALGEBRA
卷 22, 期 -, 页码 1031-1048出版社
INT LINEAR ALGEBRA SOC
DOI: 10.13001/1081-3810.1489
关键词
Singular value decomposition; CUR decomposition; Rank k approximation; Least squares; Tucker decomposition
类别
资金
- Berlin Mathematical School, Berlin, Germany
- Deutsche Forschungsgemeinschaft through DFG Research Center Matheon Mathematics for Key Technologies in Berlin
- DFG Research Center MATHEON
In many applications such as data compression, imaging or genomic data analysis, it is important to approximate a given m x n matrix A by a matrix B of rank at most k which is much smaller than m and n. The best rank k approximation can be determined via the singular value decomposition which, however, has prohibitively high computational complexity and storage requirements for very large m and n. We present an optimal least squares algorithm for computing a rank k approximation to an m x n matrix A by reading only a limited number of rows and columns of A. The algorithm has complexity O(k(2) max(m, n)) and allows to iteratively improve given rank k approximations by reading additional rows and columns of A. We also show how this approach can be extended to tensors and present numerical results.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据