Improved matrix algorithms via the subsampled randomized Hadamard transform
From MaRDI portal
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".
Several recent randomized linear algebra algorithms rely upon fast dimension reduction methods. A popular choice is the subsampled randomized Hadamard transform (SRHT). The authors address the efficacy of an SRHT-based low-rank matrix approximation technique introduced by \textit{F. Woolfe} et al. [Appl. Comput. Harmon. Anal. 25, No. 3, 335--366 (2008; Zbl 1155.65035)]. Some sharper approximation bounds are proved. They also discuss two approaches to least squares regression involving SRHT dimensionality reduction.
Recommendations
- Improved analysis of the subsampled randomized Hadamard transform
- A Fast Hadamard Transform for Signals With Sublinear Sparsity in the Transform Domain
- Improved bounds for the RIP of subsampled circulant matrices
- Uniform approximations for Randomized Hadamard Transforms with applications
- Decomposition of binary matrices and fast Hadamard transforms
- Approximating subadditive Hadamard functions on implicit matrices
- A Fast Random Sampling Algorithm for Sparsifying Matrices
- A fast randomized algorithm for the approximation of matrices
- Matrix decompositions using sub-Gaussian random matrices
- Subspace Iteration Randomization and Singular Value Problems
Cited in
(44)- Random projections for Bayesian regression
- Randomized LU decomposition
- Randomized block Krylov subspace methods for trace and log-determinant estimators
- An efficient randomized algorithm for computing the approximate Tucker decomposition
- An efficient algorithm for computing the approximate t-URV and its applications
- Adaptive iterative Hessian sketch via A-optimal subsampling
- The complexity of computing (almost) orthogonal matrices with \(\varepsilon\)-copies of the Fourier transform
- Sublinear update time randomized algorithms for dynamic graph regression
- On spectral and numerical properties of random butterfly matrices
- Randomized linear algebra for model reduction. I. Galerkin methods and error estimation
- Far-field compression for fast kernel summation methods in high dimensions
- Paved with good intentions: analysis of a randomized block Kaczmarz method
- Interpolation of inverse operators for preconditioning parameter-dependent equations
- Improved analysis of the subsampled randomized Hadamard transform
- Practical sketching algorithms for low-rank matrix approximation
- A bootstrap method for error estimation in randomized matrix multiplication
- Scalable semidefinite programming
- RidgeSketch: a fast sketching based solver for large scale ridge regression
- Singular values of dual quaternion matrices and their low-rank approximations
- scientific article; zbMATH DE number 7164768 (Why is no real title available?)
- Streaming low-rank matrix approximation with an application to scientific simulation
- Randomized approximation of the Gram matrix: exact computation and probabilistic bounds
- Randomized numerical linear algebra: Foundations and algorithms
- Simpler is better: a comparative study of randomized pivoting algorithms for CUR and interpolative decompositions
- Robust Recovery of Low-Rank Matrices and Low-Tubal-Rank Tensors from Noisy Sketches
- Randomized Low-Rank Approximation for Symmetric Indefinite Matrices
- An Improved Analysis and Unified Perspective on Deterministic and Randomized Low-Rank Matrix Approximation
- Fast randomized numerical rank estimation for numerically low-rank matrices
- A fast randomized algorithm for computing an approximate null space
- Learning to Forecast Dynamical Systems from Streaming Data
- Fixed-precision randomized low-rank approximation methods for nonlinear model order reduction of large systems
- Randomized low-rank approximation methods for projection-based model order reduction of large nonlinear dynamical problems
- A multilinear Nyström algorithm for low-rank approximation of tensors in Tucker format
- Efficient bounds and estimates for canonical angles in randomized subspace approximations
- Efficient randomized algorithms for computing an approximation of the tensor train decomposition
- Matrix perturbation analysis of methods for extracting singular values from approximate singular subspaces
- CholeskyQR with randomization and pivoting for tall matrices (CQRRPT)
- Low-rank approximation of parameter-dependent matrices via CUR decomposition
- Surrogate-based autotuning for randomized sketching algorithms in regression problems
- Efficient randomized algorithms for fixed precision problem of approximate Tucker decomposition
- Capacity analysis of vector symbolic architectures
- Subspace embeddings with the rerandomized SRHT
- High-dimensional model recovery from random sketched data by exploring intrinsic sparsity
- Hilbert space methods for reduced-rank Gaussian process regression
This page was built for publication: Improved matrix algorithms via the subsampled randomized Hadamard transform
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2866237)
