Near Optimal Column-Based Matrix Reconstruction
- 1 October 2011
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 305-314
- https://doi.org/10.1109/focs.2011.21
Abstract
We consider low-rank reconstruction of a matrix using a subset of its columns and we present asymptotically optimal algorithms for both spectral norm and Frobenius norm reconstruction. The main tools we introduce to obtain our results are: (i) the use of fast approximate SVD-like decompositions for column-based matrix reconstruction, and (ii) two deterministic algorithms for selecting rows from matrices with orthonormal columns, building upon the sparse representation theorem for decompositions of the identity that appeared in [1].Keywords
All Related Versions
This publication has 16 references indexed in Scilit:
- Efficient Subspace Approximation AlgorithmsDiscrete & Computational Geometry, 2011
- Finding Structure with Randomness: Probabilistic Algorithms for Constructing Approximate Matrix DecompositionsSIAM Review, 2011
- Coresets and Sketches for High Dimensional Subspace Approximation ProblemsPublished by Society for Industrial & Applied Mathematics (SIAM) ,2010
- A Randomized Algorithm for Principal Component AnalysisSIAM Journal on Matrix Analysis and Applications, 2010
- CUR matrix decompositions for improved data analysisProceedings of the National Academy of Sciences, 2009
- Randomized algorithms for the low-rank approximation of matricesProceedings of the National Academy of Sciences, 2007
- Sampling-based dimension reduction for subspace approximationPublished by Association for Computing Machinery (ACM) ,2007
- Efficient Algorithms for Computing a Strong Rank-Revealing QR FactorizationSIAM Journal on Scientific Computing, 1996
- SOME APPLICATIONS OF THE RANK REVEALING QR FACTORIZATIONSIAM Journal on Scientific and Statistical Computing, 1992
- Numerical methods for solving linear least squares problemsNumerische Mathematik, 1965