CaltechAUTHORS
  A Caltech Library Service

Improved matrix algorithms via the Subsampled Randomized Hadamard Transform

Boutsidis, Christos and Gittens, Alex (2013) Improved matrix algorithms via the Subsampled Randomized Hadamard Transform. SIAM Journal on Matrix Analysis and Applications, 34 (3). pp. 1301-1340. ISSN 0895-4798. doi:10.1137/120874540. https://resolver.caltech.edu/CaltechAUTHORS:20131025-105700204

[img]
Preview
PDF - Published Version
See Usage Policy.

538kB
[img]
Preview
PDF - Submitted Version
See Usage Policy.

907kB

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20131025-105700204

Abstract

Several recent randomized linear algebra algorithms rely upon fast dimension reduction methods. A popular choice is the subsampled randomized Hadamard transform (SRHT). In this article, we address the efficacy, in the Frobenius and spectral norms, of an SRHT-based low-rank matrix approximation technique introduced by Woolfe, Liberty, Rohklin, and Tygert. We establish a slightly better Frobenius norm error bound than is currently available, and a much sharper spectral norm error bound (in the presence of reasonable decay of the singular values). Along the way, we produce several results on matrix operations with SRHTs (such as approximate matrix multiplication) that may be of independent interest. Our approach builds upon Tropp's in “Improved Analysis of the Subsampled Randomized Hadamard Transform” [Adv. Adaptive Data Anal., 3 (2011), pp. 115--126].


Item Type:Article
Related URLs:
URLURL TypeDescription
http://dx.doi.org/10.1137/120874540DOIArticle
http://epubs.siam.org/doi/abs/10.1137/120874540PublisherArticle
http://arxiv.org/abs/1204.0062arXivDiscussion Paper
Additional Information:© 2013, Society for Industrial and Applied Mathematics. Received by the editors April 23, 2012; accepted for publication (in revised form) by I. C. F. Ipsen June 4, 2013; published electronically September 12, 2013. We would like to thank Joel Tropp and Mark Tygert for the initial suggestion that we attempt to sharpen the analysis of the SHRT low rank approximation algorithm and for fruitful conversations on our approach. We are also grateful to an anonymous reviewer for pointing out the value in interpreting Lemma 4.11 as a relative error bound, and to Malik Magdon-Ismail for providing the proof of Lemma 5.3.
Subject Keywords:low-rank approximation, least-squares regression, Hadamard transform, sampling, randomized algorithms
Issue or Number:3
Classification Code:AMS subject classifications: 15B52, 15A18, 11K45
DOI:10.1137/120874540
Record Number:CaltechAUTHORS:20131025-105700204
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20131025-105700204
Official Citation:Improved Matrix Algorithms via the Subsampled Randomized Hadamard Transform Boutsidis, C. and Gittens, A. SIAM Journal on Matrix Analysis and Applications 2013 34:3, 1301-1340
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:42071
Collection:CaltechAUTHORS
Deposited By: Ruth Sustaita
Deposited On:25 Oct 2013 18:19
Last Modified:10 Nov 2021 04:37

Repository Staff Only: item control page