Improved analysis of the subsampled randomized Hadamard transform
From MaRDI portal
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
(97)- On principal components regression, random projections, and column subsampling
- Randomized LU decomposition
- Random sampling of bandlimited signals on graphs
- Sub-sampled Newton methods
- Randomized LU decomposition using sparse projections
- Randomized block Krylov subspace methods for trace and log-determinant estimators
- On greedy randomized average block Kaczmarz method for solving large linear systems
- Perturbations of the \textsc{Tcur} decomposition for tensor valued data in the Tucker format
- Adaptive iterative Hessian sketch via A-optimal subsampling
- On spectral and numerical properties of random butterfly matrices
- Randomized linear algebra for model reduction. I. Galerkin methods and error estimation
- Random multipliers numerically stabilize Gaussian and block Gaussian elimination: proofs and an extension to low-rank approximation
- Numerically safe Gaussian elimination with no pivoting
- Far-field compression for fast kernel summation methods in high dimensions
- Randomized matrix-free trace and log-determinant estimators
- Paved with good intentions: analysis of a randomized block Kaczmarz method
- Asymptotically liberating sequences of random unitary matrices
- Interpolation of inverse operators for preconditioning parameter-dependent equations
- On data preconditioning for regularized loss minimization
- Improved matrix algorithms via the subsampled randomized Hadamard transform
- The expected norm of a sum of independent random matrices: an elementary approach
- New studies of randomized augmentation and additive preprocessing
- A Computationally Efficient Projection-Based Approach for Spatial Generalized Linear Mixed Models
- Weighted SGD for _p regression with randomized preconditioning
- Sketched ridge regression: optimization perspective, statistical perspective, and model averaging
- Randomized algorithms in numerical linear algebra
- Practical sketching algorithms for low-rank matrix approximation
- Fast spatial Gaussian process maximum likelihood estimation via skeletonization factorizations
- Scalable kernel \(k\)-means clustering with Nyström approximation: relative-error bounds
- Sharper bounds for regularized data fitting
- Estimating Leverage Scores via Rank Revealing Methods and Randomization
- Sublinear Cost Low Rank Approximation via Subspace Sampling
- Tensor-structured sketching for constrained least squares
- Stochastic block projection algorithms with extrapolation for convex feasibility problems
- On expected error of randomized Nyström kernel regression
- RidgeSketch: a fast sketching based solver for large scale ridge regression
- Mode-wise tensor decompositions: multi-dimensional generalizations of CUR decompositions
- Faster randomized block Kaczmarz algorithms
- Randomized Dynamic Mode Decomposition
- Streaming low-rank matrix approximation with an application to scientific simulation
- Universality laws for randomized dimension reduction, with applications
- Randomized approximation of the Gram matrix: exact computation and probabilistic bounds
- Structural Convergence Results for Approximation of Dominant Subspaces from Block Krylov Spaces
- Perturbations of CUR Decompositions
- Robust CUR Decomposition: Theory and Imaging Applications
- Randomized numerical linear algebra: Foundations and algorithms
- Simpler is better: a comparative study of randomized pivoting algorithms for CUR and interpolative decompositions
- Randomized Low-Rank Approximation for Symmetric Indefinite Matrices
- Faster randomized block sparse Kaczmarz by averaging
- Growth Factors of Random Butterfly Matrices and the Stability of Avoiding Pivoting
- Fast randomized numerical rank estimation for numerically low-rank matrices
- A fast randomized algorithm for computing an approximate null space
- On randomized sketching algorithms and the Tracy-Widom law
- Speeding Up Krylov Subspace Methods for Computing \(\boldsymbol{{f}(A){b}}\) via Randomization
- Sharp Analysis of Sketch-and-Project Methods via a Connection to Randomized Singular Value Decomposition
- Hadamard transforms and analysis on Cayley-Dickson algebras
- Dictionary-based model reduction for state estimation
- Preserving privacy between features in distributed estimation
- 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
- Fast and accurate randomized algorithms for linear systems and eigenvalue problems
- 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
- Sketch-based multiplicative updating algorithms for symmetric nonnegative tensor factorizations with applications to face image clustering
- \texttt{pylspack}: parallel algorithms and data structures for sketching, column subset selection, regression, and leverage scores
- 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
- Randomized flexible GMRES with deflated restarting
- Randomized approach to matrix completion: applications in recommendation systems and image inpainting
- High-precision randomized preconditioned iterative methods for the random feature method
- \(S^{\top}S\)-SVD via sketching and the nearest \(S^{\top}S\)-orthogonal matrix
- Matrix perturbation analysis of methods for extracting singular values from approximate singular subspaces
- Randomized Kaczmarz methods with beyond-Krylov convergence
- Fine-grained analysis and faster algorithms for iteratively solving linear systems
- An efficient greedy quasi block coordinate descent method for solving linear least-squares problems
- Error analysis of randomized symplectic model order reduction for Hamiltonian systems
- Faster algorithms for Schatten-p low rank approximation
- RTSMS: randomized Tucker with single-mode sketching
- Randomized iterative methods for generalized absolute value equations: solvability and error bounds
- CholeskyQR with randomization and pivoting for tall matrices (CQRRPT)
- Low-rank approximation of parameter-dependent matrices via CUR decomposition
- Construction of hierarchically semiseparable matrix representation using adaptive Johnson-Lindenstrauss sketching
- Sketched and truncated polynomial Krylov subspace methods: matrix Sylvester equations
- Detecting interactions in high-dimensional data using cross leverage scores
- Randomized block Gram-Schmidt process for the solution of linear systems and eigenvalue problems
- Randomized low-rank approximations beyond Gaussian random matrices
- A sublinear-time randomized algorithm for column and row subset selection based on strong rank-revealing QR factorizations
- Training (overparametrized) neural networks in near-linear time
- Generalized subsampled Newton method for large-scale linear inequalities with Tikhonov regularization
- Complete pivoting growth of butterfly matrices and butterfly Hadamard matrices
- Randomized Householder QR
- Randomized structured total-least-squares-based higher-order extended dynamic mode decomposition
- Subspace Langevin Monte Carlo
- Subspace embeddings with the rerandomized SRHT
- Optimal oblivious subspace embeddings with near-optimal sparsity
- High-dimensional model recovery from random sketched data by exploring intrinsic sparsity
- Block Kaczmarz method with inequalities
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)
