A note on element-wise matrix sparsification via a matrix-valued Bernstein inequality

DOI10.1016/j.ipl.2011.01.010zbMath1260.68454arXiv1006.0407OpenAlexW1984492644MaRDI QIDQ1944905

Anastasios Zouzias, Petros Drineas

Publication date: 28 March 2013

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1006.0407

zbMATH Keywords

algorithmsmatrix sparsificationmatrix-valued Bernstein bounds

Mathematics Subject Classification ID

Computational methods for sparse matrices (65F50) Numerical computation of matrix norms, conditioning, scaling (65F35) Approximation algorithms (68W25) Randomized algorithms (68W20)

Related Items

Comparison of matrix norm sparsification, Detection thresholds in very sparse matrix completion, Tensor sparsification via a bound on the spectral norm of random tensors: Algorithm 1., Convergence analysis of iterated best response for a trusted computation game, Frequent Directions: Simple and Deterministic Matrix Sketching, Recovering PCA from Hybrid-$(\ell_1,\ell_2)$ Sparse Sampling of Data Elements, Low-Rank Matrix Approximations Do Not Need a Singular Value Gap, Unnamed Item

Cites Work

• Unnamed Item
• Exact matrix completion via convex optimization
• Fast computation of low-rank matrix approximations
• A Fast Random Sampling Algorithm for Sparsifying Matrices
• Fast computation of low rank matrix approximations
• The Power of Convex Relaxation: Near-Optimal Matrix Completion
• Fast Monte Carlo Algorithms for Matrices I: Approximating Matrix Multiplication