Fetching the paper…
Reading the bibliography…
The CUR decomposition of an $m \times n$ matrix $A$ finds an $m \times c$ matrix $C$ with a subset of $c < n$ columns of $A,$ together with an $r \times n$ matrix $R$ with a subset of $r < m$ rows of $A,$ as well as a $c \times r$ low-rank matrix $U$ such that the matrix $C U R$ approximates the matrix $A,$ that is, $ || A - CUR ||_F^2 \le (1+\epsilon) || A - A_k||_F^2$, where $||.||_F$ denotes the Frobenius norm and $A_k$ is the best $m \times n$ matrix of rank $k$ constructed via the SVD.
Universal classes of hash functions
L. Carter and M. N. Wegman · 1979
Earlier work this paper cites.
Mosaic-skeleton approximations
E. Tyrtyshnikov · 1996
Earlier work this paper cites.
A theory of pseudoskeleton approximations
S. Goreinov, E. Tyrtyshnikov, and N. Zamarashkin · 1997
Earlier work this paper cites.
Pseudo-skeleton approximations by matrices of maximal volume
S. Goreinov, N. Zamarashkin, and E. Tyrtyshnikov · 1997
Earlier work this paper cites.
Improved bound for rank revealing LU factorizations
T. Hwang, W. Lin, and D. Pierce · 1997
Earlier work this paper cites.
Fast Monte-Carlo algorithms for finding low-rank approximations
A. Frieze, R. Kannan, and S. Vempala · 1998
Earlier work this paper cites.
Four algorithms for the efficient computation of truncated QR approximations to a sparse matrix
G. Stewart · 1999
Earlier work this paper cites.
On the existence and computation of rank-revealing LU factorizations
C. Pan · 2000
Earlier work this paper cites.
Incomplete cross approximation in the mosaic-skeleton method
E. Tyrtyshnikov · 2000
Earlier work this paper cites.
Fast Monte-Carlo algorithms for approximate matrix multiplication
P. Drineas and R. Kannan · 2001
Earlier work this paper cites.
Database-friendly random projections: Johnson-lindenstrauss with binary coins
D. Achlioptas · 2003
Earlier work this paper cites.
Pass efficient algorithms for approximating large matrices
P. Drineas and R. Kannan · 2003
Earlier work this paper cites.
Strong rank revealing LU factorizations
L. Miranian and M. Gu · 2003
Earlier work this paper cites.
Strong rank revealing Cholesky factorization
M. Gu and L. Miranian · 2004
Earlier work this paper cites.
Algorithm 844: Computing sparse reduced-rank approximations to sparse matrices
M. W. Berry, S. A. Pulatova, and G. Stewart · 2005
Earlier work this paper cites.
On the nyström method for approximating a gram matrix for improved kernel-based learning
P. Drineas and M. W. Mahoney · 2005
Earlier work this paper cites.
Matrix approximation and projective clustering via volume sampling
A. Deshpande, L. Rademacher, S. Vempala, and G. Wang · 2006
Earlier work this paper cites.
Adaptive sampling and fast low-rank matrix approximation
A. Deshpande and S. Vempala · 2006
Cited alongside, same era.
Fast Monte Carlo algorithms for matrices I: Approximating matrix multiplication
P. Drineas, R. Kannan, and M. Mahoney · 2006
Cited alongside, same era.
Fast Monte Carlo algorithms for matrices II: Computing a low-rank approximation to a matrix
P. Drineas, R. Kannan, and M. Mahoney · 2006
Cited alongside, same era.
Fast Monte Carlo algorithms for matrices III: Computing a compressed approximate matrix decomposition
P. Drineas, R. Kannan, and M. Mahoney · 2006
Cited alongside, same era.
Polynomial time algorithm for column-row based relative-error low-rank matrix approximation
P. Drineas, M. Mahoney, and S. Muthukrishnan · 2006
Cited alongside, same era.
Open problems in data streams and related topics
Efficient volume sampling for row/column subset selection
A. Deshpande and L. Rademacher · 2010
Later among the works it cites.
Row Sampling for Matrix Algorithms via a Non-Commutative Bernstein Bound
M. Magdon-Ismail · 2010
Later among the works it cites.
Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions
N. Halko, P. Martinsson, and J. Tropp · 2011
Later among the works it cites.
Optimal column-based low-rank matrix reconstruction
V. Guruswami and A. K. Sinop · 2012
Later among the works it cites.
On generalized matrix approximation problem in the spectral norm
K. C. Sou and A. Ranzer · 2012
Later among the works it cites.
Near optimal column based matrix reconstruction
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
A. McGregor · 2006
Cited alongside, same era.
Improved approximation algorithms for large matrices via random projections
T. Sarlos · 2006
Cited alongside, same era.
Generalized rank-constrained matrix approximations
S. Friedland and A. Torokhti · 2007
Cited alongside, same era.
Sampling from large matrices: An approach through geometric functional analysis
M. Rudelson and R. Vershynin · 2007
Cited alongside, same era.
Relative-error cur matrix decompositions
P. Drineas, M. W. Mahoney, and S. Muthukrishnan · 2008
Cited alongside, same era.
A fast randomized algorithm for overdetermined linear least-squares regression
V. Rokhlin and M. Tygert · 2008
Cited alongside, same era.
Twice-ramanujan sparsifiers
J. Batson, D. Spielman, and N. Srivastava · 2009
Cited alongside, same era.
C. Boutsidis, P. Drineas, and M. Magdon-Ismail · 2013
Later among the works it cites.
Improved matrix algorithms via the subsampled randomized hadamard transform
C. Boutsidis and A. Gittens · 2013
Later among the works it cites.
Low rank approximation and regression in input sparsity time
K. L. Clarkson and D. P. Woodruff · 2013
Later among the works it cites.
Low rank approximation and regression in input sparsity time
K. L. Clarkson and D. P. Woodruff · 2013
Later among the works it cites.
Relative errors for deterministic low-rank matrix approximations
M. Ghashami and J. Phillips · 2013
Later among the works it cites.
Revisiting the nystrom method for improved large-scale machine learning
A. Gittens and M. W. Mahoney · 2013
Later among the works it cites.
Nimble algorithms for cloud computing
R. Kannan, S. Vempala, and D. P. Woodruff · 2013
Later among the works it cites.
Low-distortion subspace embeddings in input-sparsity time and applications to robust linear regression
X. Meng and M. W. Mahoney · 2013
Later among the works it cites.
Osnap: Faster numerical linear algebra algorithms via sparser subspace embeddings
J. Nelson and H. L. Nguyên · 2013
Later among the works it cites.
Improving cur matrix decomposition and the nystrom approximation via adaptive sampling
S. Wang and Z. Zhang · 2013
Later among the works it cites.
Randomized extended kaczmarz for solving least-squares
A. Zouzias and N. Freris · 2013
Later among the works it cites.