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

to appear in SIAM Journal on Matrix Analysis and Applications

References in corpus (5)

• Fast approximation of matrix coherence and statistical leverage
• Near-optimal Coresets For Least-Squares Regression
• The spectral norm error of the naive Nystrom extension
• Low Rank Approximation and Regression in Input Sparsity Time
• The Effect of Coherence on Sampling from Matrices with Orthonormal Columns, and Preconditioned Least Squares Problems

Cited by in corpus (5)

• Paved with Good Intentions: Analysis of a Randomized Block Kaczmarz Method
• Fast and Robust Least Squares Estimation in Corrupted Linear Models
• Stochastic Newton and Quasi-Newton Methods for Large Linear Least-squares Problems
• DUAL-LOCO: Distributing Statistical Estimation Using Random Projections
• An Empirical Evaluation of Sketched SVD and its Application to Leverage Score Ordering