PaperlayerView exact revision on arXiv

Source-linked AI summary

Improved matrix algorithms via the Subsampled Randomized Hadamard Transform

Christos Boutsidis, Alex Gittens

arXiv:1204.0062v4cs.DSmath.NA

TL;DR

The paper studies whether SRHT-based low-rank approximation can provide accurate Frobenius- and spectral-norm results while retaining fast dimension reduction. It develops sharper analyses and supporting SRHT matrix-operation results, including approximate multiplication. The conclusions support using these methods when computational efficiency matters more than highly accurate approximations, subject to transform and sampling trade-offs.

  • Problem

    The paper examines the efficacy of an SRHT-based low-rank approximation method in Frobenius and spectral norms, where structured transforms trade isotropic randomness for faster computation and potentially looser bounds.

  • Method

    The paper analyzes SRHT low-rank approximation and develops supporting results on singular-value preservation, column equalization, and high-probability approximate matrix multiplication.

  • Results

    The analysis provides sharper approximation bounds, while experiments report comparable SRHT and Gaussian residual errors except for a notable SRHT disadvantage on a highly coherent dataset.

  • Takeaways & Limitations

    The methods are appropriate when users are willing to trade some accuracy for computational efficiency, rather than when highly accurate low-rank approximations are required.

  • Takeaways & Limitations

    SRHT matrices are defined only for power-of-two dimensions, and their structured randomness can require more samples and logarithmic factors than Gaussian or subgaussian alternatives.

Abstract

from arXiv · show

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

1. Introduction.

Randomized dimension reduction addresses the prohibitive cost of deterministic matrix computations by shrinking matrices before applying standard procedures. This introduction presents SRHTs as a structured option for fast low-rank approximation and related numerical linear algebra tasks.

  • Motivation: O(m^3) arithmetic operations can be prohibitive for matrices with millions or billions of entries, motivating dimension reduction before deterministic procedures.For matrix multiplication, forming YY^T instead of AA^T can require o(m^3) operations when the reduction matrix preserves sufficient information.
  • Randomized numerical linear algebra: Randomized dimension-reduction matrices support approximate low-rank approximation, least-squares regression, and k-means clustering in o(m^3) arithmetic operations.The literature includes random signs, Gaussian entries, leverage-based sampling, uniform sampling, and structured transforms as choices for Ω.
  • SRHT motivation: SRHTs are attractive because their structure reduces the cost of computing Y = AΩ from O(m^2r) to O(m^2 log^2 r).The paper analyzes an SRHT-based randomized low-rank approximation algorithm and claims sharper approximation bounds than prior analyses.
  • SRHT construction: An SRHT combines random sign diagonalization, a normalized Walsh–Hadamard transform, and uniformly sampled rows of the identity matrix.The transform is defined for n = 2^p and uses r < n sampled rows.
  • Scope and extensions: The SRHT restriction to power-of-two dimensions can be avoided by extending the analysis to structured orthonormal transforms such as the DCT or DHT.The paper states that its results extend unchanged because the relevant orthogonal-transform lemma remains valid.
  • Paper scope: SRHT-based low-rank approximation is analyzed through theoretical guarantees in both spectral and Frobenius norms.The paper’s main result, Theorem 2.1, concerns the accuracy of approximations constructed with an SRHT matrix.

2. Low-rank matrix approximation using SRHTs.

The paper analyzes SRHT-based low-rank approximation through residual and forward error bounds in Frobenius and spectral norms, comparing them with prior guarantees. Its spectral-norm bounds are especially useful when singular values decay, while SRHT’s speed introduces logarithmic sampling factors and stronger sample requirements.

  • Main result: Theorem 2.1 supplies simultaneous Frobenius- and spectral-norm bounds with explicit high-probability guarantees.The Frobenius bounds hold with probability at least 1−δC^2 ln(k/δ)/4−7δ, while the spectral bounds hold with probability at least 1−5δ.
  • Computational cost: The reduced matrix Y can be formed in 2mn log_2(r + 1) arithmetic operations, followed by additional costs for forming YY†A and Ã_k.This structured computation is the main computational advantage emphasized for SRHT-based approximation.
  • Main result: Theorem 2.1 analyzes an SRHT approximation Y = AΘT and constructs both a rank-at-most-r residual approximation YY†A and a rank-at-most-k approximation Ã_k.The analysis uses an orthonormal basis Q for the range of Y and computes Ã_k from the SVD of Q^TA.
  • Comparison with prior work: The first two Frobenius residual-error bounds are slightly stronger than prior bounds, while the spectral residual-error bounds are significantly sharper.The authors do not claim optimality, and constants such as 22 and 6 are not optimized.
  • Spectral-norm behavior: When singular values decay sufficiently fast, the second spectral bound gives ∥A−Ã_k∥_2 ≤ O(1)·∥A−A_k∥_2 with probability at least 1−8δ.Fast decay can make ∥A−A_k∥_F = Θ(1)·∥A−A_k∥_2, explaining observed relative-error spectral behavior under power-law decay.
  • Comparison of sampling schemes: Compared with Gaussian and random-sign schemes, SRHT bounds require logarithmic factors and r > k ln(ρ/δ), reflecting a trade-off between fast structured computation and isotropic randomness.SRHT computes the reduced matrix faster, but the resulting guarantees can require more samples.

3. Least squares regression.

This section analyzes SRHT-based least-squares regression methods that reduce the problem before solving it, either directly or through preconditioning. The paper gives an improved sample-complexity analysis and relates SRHT sampling choices to conditioning and runtime.

  • Direct least-squares via the SRHT: SRHT regression premultiplies A and b by Θ, then solves the smaller least-squares problem using (ΘA)†Θb.This approach reduces the dimensions before applying a direct solver.
  • Direct least-squares via the SRHT: The algorithm runs in O(mn log^2 r + rn^2) time, combining fast SRHT multiplication with the smaller regression solve.The first term is the cost of multiplying by the SRHT, and the second is the cost of solving the reduced problem.
  • Direct least-squares via the SRHT: The paper’s new analysis shows that asymptotically fewer samples r are needed and that failure probability has logarithmic dependence.The reduced sample requirement immediately improves the algorithm’s running time.
  • SRHT preconditioning: For iterative regression, Blendenpik uses an SRHT-based QR factorization to construct a preconditioner for LSQR.The number of LSQR iterations is proportional to the resulting two-norm condition number.
  • SRHT preconditioning: The analysis distinguishes uniform sampling without replacement from Blendenpik’s with-replacement sampling and from Bernoulli sampling analyzed elsewhere.The paper also connects the conditioning analysis to singular-value bounds for U^TΘ^T.

4. Matrix Computations with SRHT matrices.

The paper motivates its low-rank approximation analysis by identifying the effect of SRHT postmultiplication on singular values as a central issue. Understanding this perturbation is key to controlling approximation error.

  • Matrix computations with SRHT matrices: Analyzing SRHT low-rank approximation requires understanding how postmultiplication changes the singular values of a matrix.The section focuses particularly on the perturbation of singular values of orthonormal matrices.

4.1. SRHTs applied to orthonormal matrices.

This section develops the geometric foundation for SRHT analysis: randomized Hadamard mixing equalizes row norms, after which uniform sampling approximately preserves singular values of orthonormal matrices.

  • Geometric preservation: SRHT-based low-rank approximation controls residual error through the norms of perturbed orthonormal matrices.Those norms are small when the perturbed matrices retain singular values close to the originals.
  • Geometric preservation: Tropp’s result shows that sufficiently large SRHTs preserve the singular values of short-fat orthonormal-row matrices up to a small multiplicative factor.The paper includes a full proof of the restated result.
  • Row equalization and sampling: Uniform sampling without replacement preserves the singular values of V^TΘ^T with high probability when r satisfies the lemma’s sampling condition.The result holds simultaneously for all i in [k] with probability at least 1−3δ.
  • Row equalization and sampling: Premultiplication by HD equalizes the row norms of an orthonormal matrix, making uniform sampling suitable for preserving its geometry.The row-norm bound is stated for randomized signs, a normalized Hadamard matrix, and failure probability δ.
  • Sampling with replacement: The same geometric-preservation framework is extended to uniform sampling with replacement through an analogous SRHT lemma.The paper presents the corresponding setup and high-probability singular-value conclusion.
  • Role in low-rank approximation: The structural and geometric lemmas are sufficient to recover earlier SRHT low-rank approximation results, while the paper later exploits singular-value decay for sharper bounds.This section supplies the geometric component used by that later analysis.

4.2. SRHTs applied to general matrices.

The paper extends SRHT analysis from orthonormal matrices to general matrices and derives bounds for spectral and Frobenius norms, column-norm equalization, and approximate matrix multiplication.

  • General matrices: The analysis extends SRHT perturbation results to general matrices by controlling the singular values of Σ_{ρ−k}V^TΘ^T.A key tool bounds the maximum column norm after SRHT application using the root mean-squared average of the original column norms.
  • Column-norm equalization: Lemma 4.6 shows that randomized Hadamard mixing equalizes column norms: every transformed column is unlikely to exceed its average scale by much.The proof uses concentration for convex Lipschitz functions of Rademacher variables.
  • Spectral and singular-value control: The column-norm result implies that SRHTs essentially preserve singular values of general rectangular matrices at the same aspect ratio.The section also notes that the SRHT does not substantially increase spectral norm when the aspect ratio is larger.
  • Spectral and Frobenius control: For spectral-norm analysis, the paper conditions on bounded transformed column norms and applies a matrix Chernoff bound to the sampled Gram matrix.The randomness from Hadamard signs is handled through the conditioning event, while row sampling remains for the Chernoff argument.
  • Spectral and Frobenius control: The SRHT is unlikely to substantially increase a matrix’s Frobenius norm, and the corresponding theorem gives a high-probability bound for arbitrary η≥0.The proof combines column-norm control with sampling without replacement.
  • Approximate matrix multiplication: Lemma 4.11 provides a high-probability Frobenius-error bound for approximate matrix multiplication using SRHT-based sampling.The result is obtained from a vector Bernstein inequality for sampling without replacement.
  • Approximate matrix multiplication: The relative approximation error is controlled by the multiplication condition number, the stable rank of one factor, and the number of sampled columns, with the roles of the factors interchangeable.A generic uniform-sampling result underlies the SRHT-specific bound.

5. Proofs of our main Theorems.

The proofs begin by introducing restricted low-rank matrix approximation within a prescribed column subspace.

  • Theorem 2.1 is preceded by background on restricted low-rank matrix approximation.The approximation is considered within a subspace rather than over all rank-k matrices.
  • The setup uses A ∈ R^{m×n}, an integer k < n, and Y ∈ R^{m×r} with r > k.
  • When m = r, the problem becomes the standard unrestricted low-rank approximation problem addressed via the SVD.

5.1. Preliminaries.

The preliminaries define subspace-restricted approximations, establish their computational procedure and error identities, and introduce projection-based bounds used later for low-rank approximation and regression.

  • Restricted low-rank approximation: The restricted approximation Π^ξ_{Y,k}(A) is the best rank-k approximation to A within the column space of Y under ξ ∈ {2,F}.
  • Restricted low-rank approximation: The procedure constructs an orthonormal basis Q for range(Y), computes a rank-k approximation to Q^T A, and returns QX_opt.The returned matrix has rank at most k and lies in the column span of Y.
  • Restricted low-rank approximation: The procedure costs O(mnℓ + mrℓ) time and computes the same matrix independently of whether the spectral or Frobenius norm defines the restricted problem.
  • Projection bounds: Projection-based approximation bounds apply when Y = AΩ and V_k^TΩ has full row rank, covering both spectral and Frobenius norms.
  • Projection bounds: A new lemma is introduced for forward error, complementing the existing residual-error bound for projection-based low-rank approximation.
  • Least-squares projection bounds: The preliminaries also state projection-based residual and forward-error frameworks for least-squares regression under rank and embedding assumptions.

5.2. Proof of Theorem 2.1.

The proof of Theorem 2.1 applies projection lemmas and SRHT concentration bounds to derive Frobenius- and spectral-norm guarantees, with failure probability controlled by a union bound.

  • Frobenius norm bounds: The Frobenius-norm proof applies the projection bound with Ω = Θ^T and uses SRHT estimates to establish the theorem’s Frobenius inequalities.
  • Frobenius norm bounds: The identity from Lemma 5.1 transfers the Frobenius guarantee from the restricted approximation Π^F_{Y,k}(A) to the computed approximation Ã_k.
  • Spectral norm bounds: The spectral-norm proof combines SRHT bounds, projection estimates, and square-root inequalities to derive the theorem’s residual and forward-error bounds.
  • Spectral norm bounds: The resulting spectral estimates include terms proportional to 3 ln(ρ/δ) / r and 6 ln(ρ/δ) / r times ∥A − A_k∥_F.
  • Probability and complexity: The four spectral error bounds hold with failure probability no more than 5δ.
  • Probability and complexity: Given Y, constructing Ã_k requires O(mnℓ + ℓ^2n) arithmetic operations after forming an orthonormal basis for its range.

5.3. Proof of Theorem 3.1.

The proof of Theorem 3.1 reuses projection-based least-squares lemmas, verifies their conditions through SRHT bounds, and derives the stated forward and residual guarantees; experiments assess tightness and compare SRHT with Gaussian approximation.

  • Residual error: The residual-error proof applies the least-squares projection lemma with Ω = Θ^T and uses an SRHT rank condition to obtain the theorem’s bound.
  • Probability: The theorem’s failure probability is obtained by a union bound over the probabilistic events used in the proof.
  • Forward error: The forward-error proof applies the second least-squares lemma with Ω = Θ^T and verifies its parameter conditions using α = 1 − √ε and β = 4ε.
  • Experiments: Experiments investigate the tightness of residual and forward-error bounds in both spectral and Frobenius norms.
  • Experiments: The experiments also test whether SRHT low-rank approximation is significantly less accurate than Gaussian low-rank approximation.

6. Experiments.

The experiments compare SRHT and Gaussian low-rank approximations on three matrices designed to test spectral structure and singular-space coherence. SRHT approximations generally achieve small residual and forward errors with r = ⌈2k ln n⌉ samples, while observed bounds remain conservative.

  • 6.1. Test Matrices: Matrices A, B, and C test large spectral gaps, slowly decaying spectra, and differences in singular-space coherence.A is approximately rank one with a flat residual spectrum; B and C share singular values but differ in coherence.
  • 6.2. Empirical comparison of the SRHT and Gaussian algorithms: SRHT spectral accuracy improves on less coherent datasets, while Gaussian approximations appear comparatively insensitive to coherence.The Frobenius-norm improvement with lower coherence is present but weaker; on B, Gaussian sampling gives a notable decrease while SRHT remains comparable to B_k.
  • 6.2. Empirical comparison of the SRHT and Gaussian algorithms: Both algorithms produce forward errors on the scale of ∥M_k∥, but rank restriction helps more clearly in Frobenius norm than in spectral norm.The rank-restricted approximation is not more spectrally accurate than the non-rank-restricted approximation, and is more accurate for highly coherent B than nearly minimally coherent C.
  • 6.3. Empirical evaluation of our error bounds: The empirical Frobenius residual results suggest that the required sample count can be linear in k, and non-rank-restricted approximations require fewer samples than rank-restricted ones.For small k, the required sample count can be smaller than k for all three datasets.
  • 6.3. Empirical evaluation of our error bounds: Theorem 2.1’s bounds appear pessimistic: observed spectral residual errors are smaller than its upper bounds, while the theory still improves substantially on prior efforts.The experiments indicate room for sharper understanding of SRHT low-rank approximation.
Loading 1204.0062v4…