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

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

2011-03-28

arxiv.org/abs/1103.5453v1

Computer Science

Data Structures and Algorithms

Working paper

Scientific paper

We focus on \emph{row sampling} based approximations for matrix algorithms, in particular matrix multipication, sparse matrix reconstruction, and \math{\ell_2} regression. For \math{\matA\in\R^{m\times d}} (\math{m} points in \math{d\ll m} dimensions), and appropriate row-sampling probabilities, which typically depend on the norms of the rows of the \math{m\times d} left singular matrix of \math{\matA} (the \emph{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

Affiliated with

Also associated with

No associations

Rating

Using a Non-Commutative Bernstein Bound to Approximate Some Matrix Algorithms in the Spectral Norm does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Using a Non-Commutative Bernstein Bound to Approximate Some Matrix Algorithms in the Spectral Norm, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Using a Non-Commutative Bernstein Bound to Approximate Some Matrix Algorithms in the Spectral Norm will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-708074