dc.contributor.author Sorensen, D.C.Embree, Mark 2017-05-15T21:11:38Z 2017-05-15T21:11:38Z 2016 Sorensen, D.C. and Embree, Mark. "A DEIM Induced CUR Factorization." SIAM Journal on Scientific Computing, 38, no. 3 (2016) SIAM: A1454-A1482. http://dx.doi.org/10.1137/140978430. https://hdl.handle.net/1911/94281 We derive a CUR approximate matrix factorization based on the discrete empirical interpolation method (DEIM). For a given matrix ${\bf A}$, such a factorization provides a low-rank approximate decomposition of the form ${\bf A} \approx \bf C \bf U \bf R$, where ${\bf C}$ and ${\bf R}$ are subsets of the columns and rows of ${\bf A}$, and ${\bf U}$ is constructed to make $\bf C\bf U \bf R$ a good approximation. Given a low-rank singular value decomposition ${\bf A} \approx \bf V \bf S \bf W^T$, the DEIM procedure uses ${\bf V}$ and ${\bf W}$ to select the columns and rows of ${\bf A}$ that form ${\bf C}$ and ${\bf 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 ${\bf V}$ and ${\bf W}$. For very large problems, ${\bf V}$ and ${\bf W}$ can be approximated well using an incremental QR algorithm that makes only one pass through ${\bf A}$. Numerical examples illustrate the favorable performance of the DEIM-CUR method compared to CUR approximations based on leverage scores. eng SIAM Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. A DEIM Induced CUR Factorization Journal article SIAM Journal on Scientific Computing discrete empirical interpolation methodCUR factorizationpseudoskeleton de-compositionlow-rank approximationone-pass QR decomposition 38 3 Text http://dx.doi.org/10.1137/140978430 publisher version A1454 A1482
﻿