Show simple item record

dc.contributor.authorSorensen, D.C.
Embree, Mark
dc.date.accessioned 2017-05-15T21:11:38Z
dc.date.available 2017-05-15T21:11:38Z
dc.date.issued 2016
dc.identifier.citation 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.
dc.identifier.urihttps://hdl.handle.net/1911/94281
dc.description.abstract 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.
dc.language.iso eng
dc.publisher SIAM
dc.rights 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.
dc.title A DEIM Induced CUR Factorization
dc.type Journal article
dc.citation.journalTitle SIAM Journal on Scientific Computing
dc.subject.keyworddiscrete empirical interpolation method
CUR factorization
pseudoskeleton de-composition
low-rank approximation
one-pass QR decomposition
dc.citation.volumeNumber 38
dc.citation.issueNumber 3
dc.type.dcmi Text
dc.identifier.doihttp://dx.doi.org/10.1137/140978430
dc.type.publication publisher version
dc.citation.firstpage A1454
dc.citation.lastpage A1482


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record