Adaptive Sampling and Fast Low-Rank Matrix Approximation

DOI10.1007/11830924_28zbMath1155.68575MaRDI 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

68W25: Approximation algorithms

68W20: Randomized algorithms

15A03: Vector spaces, linear dependence, rank, lineability

Related Items

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