1407.5516

Total: 1

#1 A DEIM Induced CUR Factorization [PDF] [Copy] [Kimi] [REL]

Authors: D. C. Sorensen, M. Embree

We derive a CUR 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 ACUR, 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 AVSWT, 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 large-scale problems, V and W can be approximated using an incremental QR algorithm that makes one pass through A. Numerical examples illustrate the favorable performance of the DEIM-CUR method, compared to CUR approximations based on leverage scores.

Subject: Numerical Analysis

Publish: 2014-07-21 14:48:27 UTC