Improved analysis of the subsampled randomized Hadamard transform
From MaRDI portal
(Redirected from 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
(94)- Fast spatial Gaussian process maximum likelihood estimation via skeletonization factorizations
- CholeskyQR with randomization and pivoting for tall matrices (CQRRPT)
- 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
- Randomized low-rank approximations beyond Gaussian random matrices
- Asymptotically liberating sequences of random unitary matrices
- Random sampling of bandlimited signals on graphs
- On data preconditioning for regularized loss minimization
- Construction of hierarchically semiseparable matrix representation using adaptive Johnson-Lindenstrauss sketching
- 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 _p regression with randomized preconditioning
- A sublinear-time randomized algorithm for column and row subset selection based on strong rank-revealing QR factorizations
- 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
- Sketched and truncated polynomial Krylov subspace methods: matrix Sylvester equations
- Distribution of the number of pivots needed using Gaussian elimination with partial pivoting on random matrices
- Detecting interactions in high-dimensional data using cross leverage scores
- Complete pivoting growth of butterfly matrices and butterfly Hadamard 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
- Randomized block Gram-Schmidt process for the solution of linear systems and eigenvalue problems
- 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
- Training (overparametrized) neural networks in near-linear time
- Randomized linear algebra for model reduction. I. Galerkin methods and error estimation
- Generalized subsampled Newton method for large-scale linear inequalities with Tikhonov regularization
- Randomized approximation of the Gram matrix: exact computation and probabilistic bounds
- Practical sketching algorithms for low-rank matrix approximation
- Randomized approach to matrix completion: applications in recommendation systems and image inpainting
- 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
- Matrix perturbation analysis of methods for extracting singular values from approximate singular subspaces
- 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
- High-precision randomized preconditioned iterative methods for the random feature method
- Randomized Householder QR
- A Computationally Efficient Projection-Based Approach for Spatial Generalized Linear Mixed Models
- \(S^{\top}S\)-SVD via sketching and the nearest \(S^{\top}S\)-orthogonal matrix
- 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
- Randomized Kaczmarz methods with beyond-Krylov convergence
- Hadamard transforms and analysis on Cayley-Dickson algebras
- Fine-grained analysis and faster algorithms for iteratively solving linear systems
- High-dimensional model recovery from random sketched data by exploring intrinsic sparsity
- Randomized LU decomposition
- Dictionary-based model reduction for state estimation
- 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
- Block Kaczmarz method with inequalities
- Randomized flexible GMRES with deflated restarting
- Paved with good intentions: analysis of a randomized block Kaczmarz method
- Faster algorithms for Schatten-p low rank approximation
- 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
- RTSMS: randomized Tucker with single-mode sketching
- Preserving privacy between features in distributed estimation
- Randomized Block Davidson Eigensolvers for Plane-Wave Density-Functional Theory
- Randomized iterative methods for generalized absolute value equations: solvability and error bounds
- Low-rank approximation of parameter-dependent matrices via CUR decomposition
- 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)
