Improved analysis of the subsampled randomized Hadamard transform
From MaRDI portal
Publication:3101550
Abstract: This paper presents an improved analysis of a structured dimension-reduction map called the subsampled randomized Hadamard transform. This argument demonstrates that the map preserves the Euclidean geometry of an entire subspace of vectors. The new proof is much simpler than previous approaches, and it offers---for the first time---optimal constants in the estimate on the number of dimensions required for the embedding.
Recommendations
- Improved matrix algorithms via the subsampled randomized Hadamard transform
- Randomized large distortion dimension reduction
- New and Improved Johnson–Lindenstrauss Embeddings via the Restricted Isometry Property
- Fast, deterministic and sparse dimensionality reduction
- Dimensionality reduction with subgaussian matrices: a unified theory
Cites work
- A fast randomized algorithm for the approximation of matrices
- Extensions of Lipschitz mappings into a Hilbert space
- Finding structure with randomness: probabilistic algorithms for constructing approximate matrix decompositions
- On Talagrand's deviation inequalities for product measures
- On the conditioning of random subdictionaries
- The concentration of measure phenomenon
Cited in
(70)- Improved matrix algorithms via the subsampled randomized Hadamard transform
- On randomized sketching algorithms and the Tracy-Widom law
- Universality laws for randomized dimension reduction, with applications
- Randomized block Krylov subspace methods for trace and log-determinant estimators
- Perturbations of CUR Decompositions
- Faster randomized block Kaczmarz algorithms
- Sharper bounds for regularized data fitting
- A Computationally Efficient Projection-Based Approach for Spatial Generalized Linear Mixed Models
- On data preconditioning for regularized loss minimization
- High-dimensional model recovery from random sketched data by exploring intrinsic sparsity
- Randomized LU decomposition
- Adaptive iterative Hessian sketch via \(A\)-optimal subsampling
- The expected norm of a sum of independent random matrices: an elementary approach
- On greedy randomized average block Kaczmarz method for solving large linear systems
- Estimating Leverage Scores via Rank Revealing Methods and Randomization
- Perturbations of the \textsc{Tcur} decomposition for tensor valued data in the Tucker format
- Faster randomized block sparse Kaczmarz by averaging
- Scalable kernel \(k\)-means clustering with Nyström approximation: relative-error bounds
- Far-field compression for fast kernel summation methods in high dimensions
- Randomized algorithms in numerical linear algebra
- On spectral and numerical properties of random butterfly matrices
- Randomized Dynamic Mode Decomposition
- On expected error of randomized Nyström kernel regression
- On principal components regression, random projections, and column subsampling
- Asymptotically liberating sequences of random unitary matrices
- Interpolation of inverse operators for preconditioning parameter-dependent equations
- Streaming low-rank matrix approximation with an application to scientific simulation
- Fast spatial Gaussian process maximum likelihood estimation via skeletonization factorizations
- Sketched ridge regression: optimization perspective, statistical perspective, and model averaging
- RidgeSketch: a fast sketching based solver for large scale ridge regression
- Randomized approximation of the Gram matrix: exact computation and probabilistic bounds
- Numerically safe Gaussian elimination with no pivoting
- Randomized numerical linear algebra: Foundations and algorithms
- Robust CUR Decomposition: Theory and Imaging Applications
- Randomized linear algebra for model reduction. I. Galerkin methods and error estimation
- Paved with good intentions: analysis of a randomized block Kaczmarz method
- Mode-wise tensor decompositions: multi-dimensional generalizations of CUR decompositions
- Random sampling of bandlimited signals on graphs
- Weighted SGD for \(\ell_p\) regression with randomized preconditioning
- Tensor-structured sketching for constrained least squares
- Block Kaczmarz method with inequalities
- Randomized Low-Rank Approximation for Symmetric Indefinite Matrices
- New studies of randomized augmentation and additive preprocessing
- Sub-sampled Newton methods
- A fast randomized algorithm for computing an approximate null space
- Randomized LU decomposition using sparse projections
- Practical sketching algorithms for low-rank matrix approximation
- Sublinear Cost Low Rank Approximation via Subspace Sampling
- Structural Convergence Results for Approximation of Dominant Subspaces from Block Krylov Spaces
- Stochastic block projection algorithms with extrapolation for convex feasibility problems
- Randomized matrix-free trace and log-determinant estimators
- Random multipliers numerically stabilize Gaussian and block Gaussian elimination: proofs and an extension to low-rank approximation
- A multilinear Nyström algorithm for low-rank approximation of tensors in Tucker format
- 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
- Growth Factors of Random Butterfly Matrices and the Stability of Avoiding Pivoting
- Dictionary-based model reduction for state estimation
- \texttt{pylspack}: parallel algorithms and data structures for sketching, column subset selection, regression, and leverage scores
- Sharp Analysis of Sketch-and-Project Methods via a Connection to Randomized Singular Value Decomposition
- Hadamard transforms and analysis on Cayley-Dickson algebras
- Average block column action methods for solving least squares problems
- Distribution of the number of pivots needed using Gaussian elimination with partial pivoting on random matrices
- Simpler is better: a comparative study of randomized pivoting algorithms for CUR and interpolative decompositions
- Preserving privacy between features in distributed estimation
- Speeding Up Krylov Subspace Methods for Computing \(\boldsymbol{{f}(A){b}}\) via Randomization
- Sketch-based multiplicative updating algorithms for symmetric nonnegative tensor factorizations with applications to face image clustering
- Efficient bounds and estimates for canonical angles in randomized subspace approximations
- Fast randomized numerical rank estimation for numerically low-rank matrices
- Fast and accurate randomized algorithms for linear systems and eigenvalue problems
- Randomized flexible GMRES with deflated restarting
This page was built for publication: Improved analysis of the subsampled randomized Hadamard transform
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3101550)
