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)- Fast spatial Gaussian process maximum likelihood estimation via skeletonization factorizations
- 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
- Random multipliers numerically stabilize Gaussian and block Gaussian elimination: proofs and an extension to low-rank approximation
- Perturbations of the \textsc{Tcur} decomposition for tensor valued data in the Tucker format
- Estimating Leverage Scores via Rank Revealing Methods and Randomization
- Fast and accurate randomized algorithms for linear systems and eigenvalue problems
- Interpolation of inverse operators for preconditioning parameter-dependent equations
- Faster randomized block sparse Kaczmarz by averaging
- On greedy randomized average block Kaczmarz method for solving large linear systems
- Far-field compression for fast kernel summation methods in high dimensions
- On principal components regression, random projections, and column subsampling
- Sub-sampled Newton methods
- Structural Convergence Results for Approximation of Dominant Subspaces from Block Krylov Spaces
- Asymptotically liberating sequences of random unitary matrices
- Random sampling of bandlimited signals on graphs
- On data preconditioning for regularized loss minimization
- Randomized numerical linear algebra: Foundations and algorithms
- Sublinear Cost Low Rank Approximation via Subspace Sampling
- Randomized LU decomposition using sparse projections
- Randomized matrix-free trace and log-determinant estimators
- Sketched ridge regression: optimization perspective, statistical perspective, and model averaging
- Average block column action methods for solving least squares problems
- Weighted SGD for \(\ell_p\) regression with randomized preconditioning
- Fast randomized numerical rank estimation for numerically low-rank matrices
- Sharper bounds for regularized data fitting
- Perturbations of CUR Decompositions
- Scalable kernel \(k\)-means clustering with Nyström approximation: relative-error bounds
- Distribution of the number of pivots needed using Gaussian elimination with partial pivoting on random matrices
- Improved matrix algorithms via the subsampled randomized Hadamard transform
- Sketch-based multiplicative updating algorithms for symmetric nonnegative tensor factorizations with applications to face image clustering
- Randomized Low-Rank Approximation for Symmetric Indefinite Matrices
- A fast randomized algorithm for computing an approximate null space
- Robust CUR Decomposition: Theory and Imaging Applications
- Numerically safe Gaussian elimination with no pivoting
- \texttt{pylspack}: parallel algorithms and data structures for sketching, column subset selection, regression, and leverage scores
- Simpler is better: a comparative study of randomized pivoting algorithms for CUR and interpolative decompositions
- Randomized linear algebra for model reduction. I. Galerkin methods and error estimation
- Randomized approximation of the Gram matrix: exact computation and probabilistic bounds
- Practical sketching algorithms for low-rank matrix approximation
- Faster randomized block Kaczmarz algorithms
- Randomized block Krylov subspace methods for trace and log-determinant estimators
- Mode-wise tensor decompositions: multi-dimensional generalizations of CUR decompositions
- On randomized sketching algorithms and the Tracy-Widom law
- A multilinear Nyström algorithm for low-rank approximation of tensors in Tucker format
- New studies of randomized augmentation and additive preprocessing
- On spectral and numerical properties of random butterfly matrices
- Randomized Dynamic Mode Decomposition
- Speeding Up Krylov Subspace Methods for Computing \(\boldsymbol{{f}(A){b}}\) via Randomization
- Stochastic block projection algorithms with extrapolation for convex feasibility problems
- A Computationally Efficient Projection-Based Approach for Spatial Generalized Linear Mixed Models
- Sharp Analysis of Sketch-and-Project Methods via a Connection to Randomized Singular Value Decomposition
- Efficient bounds and estimates for canonical angles in randomized subspace approximations
- Universality laws for randomized dimension reduction, with applications
- Hadamard transforms and analysis on Cayley-Dickson algebras
- High-dimensional model recovery from random sketched data by exploring intrinsic sparsity
- Randomized LU decomposition
- Dictionary-based model reduction for state estimation
- Block Kaczmarz method with inequalities
- Randomized flexible GMRES with deflated restarting
- Paved with good intentions: analysis of a randomized block Kaczmarz method
- Adaptive iterative Hessian sketch via A-optimal subsampling
- Growth Factors of Random Butterfly Matrices and the Stability of Avoiding Pivoting
- Streaming low-rank matrix approximation with an application to scientific simulation
- RidgeSketch: a fast sketching based solver for large scale ridge regression
- Tensor-structured sketching for constrained least squares
- Preserving privacy between features in distributed estimation
- Randomized algorithms in numerical linear algebra
- On expected error of randomized Nyström kernel regression
- The expected norm of a sum of independent random matrices: an elementary approach
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)
