A Fast Random Sampling Algorithm for Sparsifying Matrices

DOI10.1007/11830924_26zbMath1155.68567OpenAlexW1581656968MaRDI QIDQ3595390

Sanjeev Arora, Satyen Kale, Elad Hazan

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_26

Mathematics Subject Classification ID

Computational methods for sparse matrices (65F50) Approximation algorithms (68W25) Randomized algorithms (68W20)

Related Items (11)

ReliefE: feature ranking in high-dimensional spaces via manifold embeddings ⋮ Comparison of matrix norm sparsification ⋮ Faster least squares approximation ⋮ A note on element-wise matrix sparsification via a matrix-valued Bernstein inequality ⋮ Tensor sparsification via a bound on the spectral norm of random tensors: Algorithm 1. ⋮ Sampling based succinct matrix approximation ⋮ Toward a unified theory of sparse dimensionality reduction in Euclidean space ⋮ The Fast Cauchy Transform and Faster Robust Linear Regression ⋮ Frequent Directions: Simple and Deterministic Matrix Sketching ⋮ Recovering PCA from Hybrid-$(\ell_1,\ell_2)$ Sparse Sampling of Data Elements ⋮ Unnamed Item

This page was built for publication: A Fast Random Sampling Algorithm for Sparsifying Matrices