Fetching the paper…
Reading the bibliography…
We give efficient algorithms for volume sampling, i.e., for picking $k$-subsets of the rows of any given matrix with probabilities proportional to the squared volumes of the simplices defined by them and the origin (or the squared volumes of the parallelepipeds defined by these subsets of rows).
Matrix Computations
G. Golub and C. van Loan · 1996
Earlier work this paper cites.
Efficient algorithms for computing a strong rank-revealing QR factorization
M. Gu and S. Eisenstat · 1996
Earlier work this paper cites.
Algebraic complexity theory
P. Bürgisser, M. Clausen, and M. A. Shokrollahi · 1997
Earlier work this paper cites.
Pseudo-skeleton approximations by matrices of maximal volume
S. Goreinov, E. Tyrtyshnikov, and N. Zamarashkin · 1997
Earlier work this paper cites.
On the existence and computation of rank-revealing LU factorizations
C.-T. Pan · 2000
Earlier work this paper cites.
The maximum-volume concept in approximation by low-rank matrices
S. Goreinov and E. Tyrtyshnikov · 2001
Earlier work this paper cites.
Determinantal probability measures
R. Lyons · 2003
Earlier work this paper cites.
Fast monte-carlo algorithms for finding low-rank approximations
A. Frieze, R. Kannan, and S. Vempala · 2004
Cited alongside, same era.
Essentially optimal computation of the inverses of generic polynomial matrices
C. Jeannerod and G. Villard · 2005
Cited alongside, same era.
Matrix approximation and projective clustering via volume sampling
A. Deshpande, L. Rademacher, S. Vempala, and G. Wang · 2006
Cited alongside, same era.
Adaptive sampling and fast low-rank matrix approximation
A. Deshpande and S. Vempala · 2006
Cited alongside, same era.
Determinantal processes and independence
J. Hough, M. Krishnapur, Y. Peres, and B. Virág · 2006
Cited alongside, same era.
Relative-error cur matrix decompositions
P. Drineas, M. Mahoney, and S. Muthukrishnan · 2008
Cited alongside, same era.
Near optimal dimensionality reductions that preserve volumes
A. Magen and A. Zouzias · 2008
Later among the works it cites.
An improved approximation algorithm for the column subset selection problem
C. Boutsidis, P. Drineas, and M. Mahoney · 2009
Later among the works it cites.
On selecting the maximum volume submatrix of a matrix and related problems
A. Çivril and M. Magdon-Ismail · 2009
Later among the works it cites.
Spectral algorithms
R. Kannan and S. Vempala · 2009
Later among the works it cites.
CUR matrix decompositions for improved data analysis
M. Mahoney and P. Drineas · 2009
Later among the works it cites.
Exponential inapproximability of selecting a maximum volume submatrix
A. Çivril and M. Magdon-Ismail · 2010
Closest in time.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…