Near-Optimal Column-Based Matrix Reconstruction

Abstract

We consider low-rank reconstruction of a matrix using its columns and we present asymptotically optimal algorithms for both spectral norm and Frobenius norm reconstruction. The main tools we introduce to obtain our r esults are: (i) the use of fast approximate SVD-like decompositions for column reconstruction, and (ii) two deter ministic algorithms for selecting rows from matrices with orthonormal columns, building upon the sparse represen tation theorem for decompositions of the identity that appeared in \cite{BSS09}.

SIAM Journal on Computing (SICOMP), invited to special issue of FOCS 2011

References in corpus (1)

• Faster Subset Selection for Matrices and Applications

Cited by in corpus (22)

• Fast approximation of matrix coherence and statistical leverage
• Greedy Column Subset Selection: New Bounds and Distributed Algorithms
• Randomized Dimensionality Reduction for k-means Clustering
• CUR Algorithm for Partially Observed Matrices
• On the Power of Adaptivity in Matrix Completion and Approximation
• A Scalable CUR Matrix Decomposition Algorithm: Lower Time Complexity and Tighter Bound
• Frequent Directions : Simple and Deterministic Matrix Sketching
• An Explicit Sampling Dependent Spectral Error Bound for Column Subset Selection
• An Efficient Algorithm for Unweighted Spectral Graph Sparsification
• Efficient Algorithms and Error Analysis for the Modified Nystrom Method
• Improved matrix algorithms via the Subsampled Randomized Hadamard Transform
• Simple and Deterministic Matrix Sketching
• A Fast Greedy Algorithm for Generalized Column Subset Selection
• Ridge Regression and Provable Deterministic Ridge Leverage Score Sampling
• Faster Subset Selection for Matrices and Applications
• Greedy Column Subset Selection for Large-scale Data Sets
• Efficient Frequent Directions Algorithm for Sparse Matrices
• Adjusting Leverage Scores by Row Weighting: A Practical Approach to Coherent Matrix Completion
• On Truncated-SVD-like Sparse Solutions to Least-Squares Problems of Arbitrary Dimensions
• A note on sparse least-squares regression
• Optimal ${\ell }_1$ Column Subset Selection and a Fast PTAS for Low Rank Approximation
• Improved Low-rank Matrix Decompositions via the Subsampled Randomized Hadamard Transform