Fetching the paper…
Reading the bibliography…
We study subset selection for matrices defined as follows: given a matrix $\matX \in \R^{n \times m}$ ($m > n$) and an oversampling parameter $k$ ($n \le k \le m$), select a subset of $k$ columns from $\matX$ such that the pseudo-inverse of the subsampled matrix has as smallest norm as possible.
Matrix Analysis
R. Horn and C. Johnson · 1985
Earlier work this paper cites.
Invertibility of large submatrices with applications to the geometry of banach spaces and harmonic analysis
J. Bourgain and L. Tzafriri · 1987
Earlier work this paper cites.
The truncated svd as a method for regularization
P. Hansen · 1987
Earlier work this paper cites.
Some applications of the rank revealing QR factorization
T. Chan and P. Hansen · 1992
Earlier work this paper cites.
Some applications of the rank revealing QR factorization
T. F. Chan and P. C. Hansen · 1992
Earlier work this paper cites.
Rank-revealing QR factorizations and the singular value decomposition
Y. P. Hong and C. T. Pan · 1992
Earlier work this paper cites.
Low-rank revealing QR factorizations
T. F. Chan and P. C. Hansen · 1994
Earlier work this paper cites.
A graph-theoretic game and its application to the k-server problem
N. Alon, R. M. Karp, D. Peleg, and D. West · 1995
Earlier work this paper cites.
Relative perturbation techniques for singular value problems
S. Eisenstat and I. Ipsen · 1995
Earlier work this paper cites.
Downdating the singular value decomposition
M. Gu and S. Eisenstat · 1995
Earlier work this paper cites.
Matrix Computations
G. Golub and C. V. 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.
Generating random spanning trees more quickly than the cover time
D. B. Wilson · 1996
Earlier work this paper cites.
A theory of pseudoskeleton approximations
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.
Distributed computing: a locality-sensitive approach
D. Peleg · 2000
Earlier work this paper cites.
On spanning tree preconditioners
E. G. Boman and B. Hendrickson · 2001
Earlier work this paper cites.
Np - hardness of largest contained and smallest containing simplices for v- and h-polytopes
A. Packer · 2002
Earlier work this paper cites.
Strong rank revealing Cholesky factorization
M. Gu and L. Miranian · 2004
Earlier work this paper cites.
Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems
D. A. Spielman and S.-H. Teng · 2004
Cited alongside, same era.
Matrix Mathematics: Theory, Facts, and Formulas with Applications to Linear Systems Theory
D. S. Bernstein · 2005
Cited alongside, same era.
Lower-stretch spanning trees
M. Elkin, Y. Emerk, D. Spielman, and S. Teng · 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.
Fast Monte Carlo algorithms for matrices I: Approximating matrix multiplication
P. Drineas, R. Kannan, and M. Mahoney · 2006
Cited alongside, same era.
Algorithm 853: An efficient algorithm for solving rank-deficient least squares problems
L. Foster and R. Kommu · 2006
Blendenpik: Supercharging LAPACK’s least-squares solver
H. Avron, P. Maymounkov, and S. Toledo · 2010
Later among the works it cites.
Subset selection algorithms: Randomized vs. deterministic
M. Broadbent, M. Brown, K. Penner, I. Ipsen, and R. Rehman · 2010
Later among the works it cites.
Efficient volume sampling for row/column subset selection
A. Deshpande and L. Rademacher · 2010
Later among the works it cites.
A note on sums of independent random matrices after ahlswede-winter
R. Vershynin · 2010
Later among the works it cites.
Topics in matrix sampling algorithms
C. Boutsidis · 2011
Closest in time.
Near optimal column based matrix reconstruction
C. Boutsidis, P. Drineas, and M. Magdon-Ismail · 2011
Closest in time.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Cited alongside, same era.
Parameterized complexity and improved inapproximability for computing the largest j-simplex in a v-polytope
I. Koutis · 2006
Cited alongside, same era.
Improved approximation algorithms for large matrices via random projections
T. Sarlos · 2006
Cited alongside, same era.
Subset selection for matrices
F. de Hoog and R. Mattheij · 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.
Nearly tight low stretch spanning trees
I. Abraham, Y. Bartal, and O. Neiman · 2008
Cited alongside, same era.
Graph sparsifications by effective resistances
N. Srivastava and D. Spielman · 2008
Cited alongside, same era.
Deterministic feature selection for k k -means clustering
C. Boutsidis and M. Magdon-Ismail · 2011
Closest in time.
Stochastic dimensionality reduction for k k -means clustering
C. Boutsidis, A. Zouzias, M. W. Mahoney, and P. Drineas · 2011
Closest in time.
A note on subset selection for matrices
F. de Hoog and R. Mattheij · 2011
Closest in time.
Faster least squares approximation
P. Drineas, M. W. Mahoney, S. Muthukrishnan, and T. Sarlos · 2011
Closest in time.
The spectral norm error of the naive nystrom extension
A. Gittens · 2011
Closest in time.
Rank-deficient nonlinear least squares problems and subset selection
I. Ipsen, C. T. Kelley, and S. R. Pope · 2011
Closest in time.
Solving SDD linear systems in time O ~ ( m log n log ( 1 / ϵ ) ) \tilde{O}(m\log{n}\log(1/\epsilon))
I. Koutis, G. L. Miller, and R. Peng · 2011
Closest in time.
A randomized algorithm for the decomposition of matrices
P. Martinsson, V. Rokhlin, and M. Tygert · 2011
Closest in time.
Improved analysis of the subsampled randomized hadamard transform
J. Tropp · 2011
Closest in time.
A Matrix Hyperbolic Cosine Algorithm and Applications
A. Zouzias · 2011
Closest in time.
Fast approximation of matrix coherence and statistical leverage
P. Drineas, M. Magdon-Ismail, M. W. Mahoney, and D. P. Woodruff · 2012
Closest in time.
Optimal column-based low-rank matrix reconstruction
V. Guruswami and A. K. Sinop · 2012
Closest in time.