A Note on Element-wise Matrix Sparsification via a Matrix-valued Bernstein Inequality

Abstract

Given an n x n matrix A, we present a simple, element-wise sparsification algorithm that zeroes out all sufficiently small elements of A and then retains some of the remaining elements with probabilities proportional to the square of their magnitudes. We analyze the approximation accuracy of the proposed algorithm using a recent, elegant non-commutative Bernstein inequality, and compare our bounds with all existing (to the best of our knowledge) element-wise matrix sparsification algorithms.

8 pages

References in corpus (3)

• A Simpler Approach to Matrix Completion
• Error Bounds for Random Matrix Approximation Schemes
• Tensor sparsification via a bound on the spectral norm of random tensors

Cited by in corpus (11)

• Dimensionality Reduction of Massive Sparse Datasets Using Coresets
• Subadditivity of Matrix phi-Entropy and Concentration of Random Matrices
• A Matrix Hyperbolic Cosine Algorithm and Applications
• Concentration Inequalities for Sums of Markov Dependent Random Matrices
• Optimal Matrix Sketching over Sliding Windows
• Sampling-Based Methods for Multi-Block Optimization Problems over Transport Polytopes
• Global Capacity Measures for Deep ReLU Networks via Path Sampling
• Near-Optimal Entrywise Sampling of Numerically Sparse Matrices
• On Recovering the Best Rank-r Approximation from Few Entries
• Almost Optimal Sublinear Time Algorithm for Semidefinite Programming
• On Dimension-free Tail Inequalities for Sums of Random Matrices and Applications