Accession Number:

ADA625637

Title:

A DEIM Induced CUR Factorization

Descriptive Note:

Corporate Author:

RICE UNIV HOUSTON TX DEPT OF COMPUTATIONAL AND APPLIED MATHEMATICS

Personal Author(s):

Report Date:

2015-09-18

Pagination or Media Count:

31.0

Abstract:

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 nearly equal 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 nearly equal 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.

Subject Categories:

  • Numerical Mathematics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE