Improved matrix algorithms via the Subsampled Randomized Hadamard Transform

Christos Boutsidis, Alex Gittens

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

Introduction

In the era of Big Data, traditional "gold standard" algorithms for matrix computations—such as Gaussian elimination or the Singular Value Decomposition (SVD)—are increasingly hitting a computational wall. When processing matrices with millions of rows and columns, the $O(n^3)$ runtime of these deterministic methods is not merely slow; it is often impossible.

To address this, researchers have turned to Randomized Numerical Linear Algebra (RandNLA). In their paper, "Improved matrix algorithms via the Subsampled Randomized Hadamard Transform," Christos Boutsidis and Alex Gittens provide a rigorous theoretical upgrade to one of the most promising tools in this field: the SRHT. By closing the gap between theoretical guarantees and empirical performance, they demonstrate that randomized "sketching" is far more accurate than previously believed.

The Subsampled Randomized Hadamard Transform (SRHT)

Many core tasks, such as low-rank approximation (PCA) and least-squares regression, require processing massive matrices. To solve this, researchers use dimension reduction: they multiply a giant matrix $A$ by a smaller random matrix $\Omega$ to create a "sketch" $Y$ that captures the essential information of $A$.

While Gaussian random matrices are highly accurate for this purpose, they are computationally expensive. The SRHT is a structured random matrix designed to be faster, defined as $\Theta = \sqrt{n/r} \cdot RHD$. It consists of three components:

  1. $D$ (Random Signs): A diagonal matrix that randomly flips the signs of the input.
  2. $H$ (Walsh-Hadamard): A structured matrix that "spreads out" the energy of the input vectors.
  3. $R$ (Subsampling): A matrix that randomly picks $r$ rows from the result.

The "magic" of the Hadamard transform is that it can be computed in $O(n \log n)$ time using a Fast Fourier-like algorithm. This allows the SRHT to compress data significantly faster than dense Gaussian matrices.

Theoretical Contributions: Sharper Error Bounds

The authors' primary contribution is a novel mathematical analysis using Matrix Chernoff bounds to provide tighter error estimates for low-rank approximations.

The "Decay" Advantage

Previous bounds for SRHT were often pessimistic because they did not account for the structure of singular values in real-world data. Boutsidis and Gittens show that if a matrix has a "heavy head" and "thin tail" (a few dominant singular values), the spectral norm error is much lower. They improved the spectral norm error bound from a factor involving the matrix dimension $\sqrt{n/r}$ to a much smaller factor involving the rank $\sqrt{\log \rho / r}$.

Coherence Neutralization

A significant challenge in random sampling is "coherence," where information is concentrated in just a few rows. The $HD$ part of the SRHT acts as a preconditioner, smearing that information across all rows. This makes uniform random sampling ($R$) highly effective, regardless of the original matrix structure.

Experimental Validation

The authors evaluated their theoretical bounds using three types of synthetic test matrices:

  • Matrix A: Approximately rank-1 with a flat residual spectrum to challenge spectral norm bounds.
  • Matrix B: A diagonal matrix with slowly decaying singular values and "coherent" (concentrated) singular vectors.
  • Matrix C: The same singular values as Matrix B, but with "incoherent" (spread out) singular vectors.

Experiments confirmed that SRHT-based approximations are nearly as accurate as Gaussian-based ones, even on difficult coherent matrices, while benefiting from the $O(mn \log r)$ computational speedup. Furthermore, they demonstrated that the number of samples $r$ needed for a good least-squares solution depends only logarithmically on the failure probability, making the algorithm exceptionally robust.

Limitations and Future Work

Despite the improvements, some constraints remain. The standard Walsh-Hadamard transform requires the matrix dimension $n$ to be a power of two. Additionally, the constants in the theoretical proofs (e.g., a factor of 528 in one bound) remain much larger than what is observed in practice.

The authors suggest that their results explain why SRHT works so well on matrices with power-law decay—an observation that was previously only empirical. Refining these bounds to match the "optimistic" constants seen in experiments remains an open challenge for the field.

Summary updated

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".
BibTeX
@article{boutsidis2013improved,
  author = {Christos Boutsidis and Alex Gittens},
  title = {{Improved matrix algorithms via the Subsampled Randomized Hadamard Transform}},
  journal = {SIAM J. Matrix Anal. Appl.},
  year = {2013},
  doi = {10.1137/120874540},
}
Figure