期刊
SIAM JOURNAL ON SCIENTIFIC COMPUTING
卷 38, 期 3, 页码 A1454-A1482出版社
SIAM PUBLICATIONS
DOI: 10.1137/140978430
关键词
discrete empirical interpolation method; CUR factorization; pseudoskeleton decomposition; low-rank approximation; one-pass QR decomposition
资金
- AFOSR [FA9550-12-1-0155]
- NSF [CCF-1320866]
- Direct For Computer & Info Scie & Enginr
- Division of Computing and Communication Foundations [1320866] Funding Source: National Science Foundation
We derive a CUR approximate matrix factorization based on the discrete empirical interpolation method (DEIM). For a given matrix A, such a factorization provides a low-rank approximate decomposition of the form A approximate to CUR, where C and R are subsets of the columns and rows of A, and U is constructed to make CUR a good approximation. Given a low-rank singular value decomposition A approximate to VSWT, the DEIM procedure uses V and W to select the columns and rows of A that form C and R. Through an error analysis applicable to a general class of CUR factorizations, we show that the accuracy tracks the optimal approximation error within a factor that depends on the conditioning of submatrices of V and W. For very large problems, V and W can be approximated well using an incremental QR algorithm that makes only one pass through A. Numerical examples illustrate the favorable performance of the DEIM-CUR method compared to CUR approximations based on leverage scores.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据