Using a Non-Commutative Bernstein Bound to Approximate Some Matrix Algorithms in the Spectral Norm

2011/03/28 by Malik Magdon-Ismail, Magdon-Ismail, Malik
Computer Science · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #cs.DS

paper · pdf · doi:10.48550/arxiv.1103.5453

Working paper

arxiv created 2011/03/28 · arxiv updated 2011/03/29

Abstract

We focus on row sampling based approximations for matrix algorithms, in particular matrix multipication, sparse matrix reconstruction, and \mathℓ₂ regression. For \math\matA∈\R^{m× d} (\mathm points in \mathd≪ m dimensions), and appropriate row-sampling probabilities, which typically depend on the norms of the rows of the \mathm× d left singular matrix of \math\matA (the leverage scores), we give row-sampling algorithms with linear (up to polylog factors) dependence on the stable rank of \math\matA. This result is achieved through the application of non-commutative Bernstein bounds. Keywords: row-sampling; matrix multiplication; matrix reconstruction; estimating spectral norm; linear regression; randomized

Related

• Row Sampling for Matrix Algorithms via a Non-Commutative Bernstein Bound
• A Note On Estimating the Spectral Norm of A Matrix Efficiently
• Weighted sampling of outer products
• An Explicit Sampling Dependent Spectral Error Bound for Column Subset Selection
• ℓ_p Row Sampling by Lewis Weights