Improved matrix algorithms via the Subsampled Randomized Hadamard Transform

Details Improved matrix algorithms via the Subsampled Randomized Hadamard Transform Improved matrix algorithms via the Subsampled Randomized Hadamard Transform

2012-03-31

arxiv.org/abs/1204.0062v1

Computer Science

Data Structures and Algorithms

25 pages, improves upon http://arxiv.org/abs/1105.0464

Scientific paper

The SRHT low-rank matrix approximation algorithm, which is based upon randomized dimension reduction via the Subsampled Randomized Hadamard Transform, is the fastest known low-rank matrix approximation technique. Novel Frobenius and spectral norm error bounds are provided which improve upon previous efforts to provide quality-of-approximation guarantees for this method. In particular, a much sharpened spectral norm error bound is obtained. Similarly, the SRHT least-squares algorithm solves regressions problems quickly via dimension reduction and the Subsampled Randomized Hadamard Transform. We also provide a novel analysis of this approximation algorithm and show improved quality-of-approximation guarantees. Our main theorems are a consequence of results on approximate matrix computations involving SRHT matrices that may themselves be of independent interest.

Affiliated with

Also associated with

No associations

Rating

Improved matrix algorithms via the Subsampled Randomized Hadamard Transform 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 Improved matrix algorithms via the Subsampled Randomized Hadamard Transform, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Improved matrix algorithms via the Subsampled Randomized Hadamard Transform will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-655218