Name
Abstract | ||
|---|---|---|
A skeleton decomposition of a matrix A is any factorization of the form A:(C)ZA(R):, where A:(C) comprises columns of A, and A(R): comprises rows of A. In this paper, we investigate the conditions under which random sampling of C and R results in accurate skeleton decompositions. When the singular vectors (or more generally the generating vectors) are incoherent, we show that a simple algorithm returns an accurate skeleton in sublinear O(l(3)) time from l similar or equal to k log n rows and columns drawn uniformly at random, with an approximation error of the form O(n/l sigma(k)) where sigma(k) is the kth singular value of A. We discuss the crucial role that regularization plays in forming the middle matrix U as a pseudoinverse of the restriction A(RC) of A to rows in R and columns in C. The proof methods enable the analysis of two alternative sublinear-time algorithms, based on the rank-revealing QR decomposition, which allows us to tighten the number of rows and/or columns to k with error bound proportional to sigma(k). |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1137/110852310 | SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS |
Keywords | DocType | Volume |
skeleton,column subset selection,low-rank approximations,CUR,interpolative decomposition,Nystrom method | Journal | 34 |
Issue | ISSN | Citations |
3 | 0895-4798 | 2 |
PageRank | References | Authors |
0.35 | 15 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Jiawei Chiu | 1 | 3 | 0.73 |
| Laurent Demanet | 2 | 750 | 57.81 |