Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published September 12, 2013 | Submitted + Published
Journal Article Open

Improved matrix algorithms via the Subsampled Randomized Hadamard Transform

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].

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.

Attached Files

Published - 120874540.pdf

Submitted - 1204.0062v4.pdf

Files

120874540.pdf
Files (1.4 MB)
Name Size Download all
md5:054dc8512bb11edf51edc1419fac2dbc
538.7 kB Preview Download
md5:6dc88406d110f2df481338f9732c207f
907.7 kB Preview Download

Additional details

Created:
August 19, 2023
Modified:
October 25, 2023