Improved matrix algorithms via the Subsampled Randomized Hadamard\n Transform

2012/03/30 by Christos Boutsidis, Boutsidis, Christos, Alex Gittens +1 · 5 citations
Engineering · Computer Science · #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques #Matrix Theory and Algorithms

paper · pdf · doi:10.48550/arxiv.1204.0062

Abstract

Several recent randomized linear algebra algorithms rely upon fast dimension\nreduction methods. A popular choice is the Subsampled Randomized Hadamard\nTransform (SRHT). In this article, we address the efficacy, in the Frobenius\nand spectral norms, of an SRHT-based low-rank matrix approximation technique\nintroduced by Woolfe, Liberty, Rohklin, and Tygert. We establish a slightly\nbetter Frobenius norm error bound than currently available, and a much sharper\nspectral norm error bound (in the presence of reasonable decay of the singular\nvalues). Along the way, we produce several results on matrix operations with\nSRHTs (such as approximate matrix multiplication) that may be of independent\ninterest. Our approach builds upon Tropp's in "Improved analysis of the\nSubsampled Randomized Hadamard Transform".\n

Citations

• Note on sampling without replacing from a finite collection of matrices
• Finding Structure with Randomness: Probabilistic Algorithms for Constructing Approximate Matrix Decompositions

Cited by

• How many integrals should be evaluated at least in two-dimensional hyperinterpolation?
• A Unified Zeroth-Order Optimization Framework via Oblivious Randomized Sketching
• Accelerating Randomized Algorithms for Low-Rank Matrix Approximation
• Fast and Robust Least Squares Estimation in Corrupted Linear Models
• GPU-Parallelizable Randomized Sketch-and-Precondition for Linear Regression using Sparse Sign Sketches

Related

• Improved Low-rank Matrix Decompositions via the Subsampled Randomized Hadamard Transform
• An improved analysis and unified perspective on deterministic and randomized low rank matrix approximations
• Randomized algorithms for low-rank matrix approximation: Design, analysis, and applications
• Randomized algorithms for low-rank matrix factorizations: sharp\n performance bounds
• Optimal approximate matrix product in terms of stable rank