Adaptive Sampling and Fast Low-Rank Matrix Approximation

DOI10.1007/11830924_28zbMath1155.68575OpenAlexW2044610104MaRDI QIDQ3595389

Amit Deshpande, Santosh Vempala

Publication date: 28 August 2007

Published in: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/11830924_28

Mathematics Subject Classification ID

Approximation algorithms (68W25) Randomized algorithms (68W20) Vector spaces, linear dependence, rank, lineability (15A03)

Related Items

A fast block low-rank dense solver with applications to finite-element matrices, Column subset selection problem is UG-hard, Proportional Volume Sampling and Approximation Algorithms for A-Optimal Design, A Local Search Framework for Experimental Design, One-pass additive-error subset selection for \(\ell_p\) subspace approximation and \((k, p)\)-clustering, A fast, memory efficient and robust sparse preconditioner based on a multifrontal approach with applications to finite‐element matrices, Randomized algorithms in numerical linear algebra, Exponential inapproximability of selecting a maximum volume sub-matrix, Lower bounds for column matrix approximations, Unnamed Item, Literature survey on low rank approximation of matrices, Optimal CUR Matrix Decompositions, Unnamed Item, Sampling-based dimension reduction for subspace approximation with outliers, Sampling based succinct matrix approximation, Efficient subspace approximation algorithms, Effective implementation to reduce execution time of a low-rank matrix approximation problem, Turning Big Data Into Tiny Data: Constant-Size Coresets for $k$-Means, PCA, and Projective Clustering, Matrix recipes for hard thresholding methods, Unnamed Item, Fast randomized matrix and tensor interpolative decomposition using countsketch, Learning big (image) data via coresets for dictionaries, On the accuracy of cross and column low-rank maxvol approximations in average, A note on linear function approximation using random projections, Frequent Directions: Simple and Deterministic Matrix Sketching, ASKIT: An Efficient, Parallel Library for High-Dimensional Kernel Summations, Column subset selection via sparse approximation of SVD, On selecting a maximum volume sub-matrix of a matrix and related problems, Optimal Column-Based Low-Rank Matrix Reconstruction, LEAST SQUARES APPROXIMATIONS OF MEASURES VIA GEOMETRIC CONDITION NUMBERS, Unnamed Item, Estimating Leverage Scores via Rank Revealing Methods and Randomization, Perfect $L_p$ Sampling in a Data Stream, Fast and Accurate Proper Orthogonal Decomposition using Efficient Sampling and Iterative Techniques for Singular Value Decomposition