Adaptive Sampling and Fast Low-Rank Matrix Approximation
From MaRDI portal
Publication:3595389
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
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