Improved analysis of the subsampled randomized Hadamard transform
From MaRDI portal
Publication:3101550
DOI10.1142/S1793536911000787zbMATH Open1232.15029arXiv1011.1595OpenAlexW2963455674MaRDI QIDQ3101550FDOQ3101550
Authors: Joel A. Tropp 
Publication date: 29 November 2011
Published in: Advances in Adaptive Data Analysis (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1011.1595
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
Random matrices (algebraic aspects) (15B52) Boolean and Hadamard matrices (15B34) Linear transformations, semilinear transformations (15A04)
Cites Work
- Extensions of Lipschitz mappings into a Hilbert space
- Finding structure with randomness: probabilistic algorithms for constructing approximate matrix decompositions
- The concentration of measure phenomenon
- On the conditioning of random subdictionaries
- On Talagrand's deviation inequalities for product measures
- A fast randomized algorithm for the approximation of matrices
Cited In (72)
- 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
- Fast randomized numerical rank estimation for numerically low-rank matrices
- 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
- Simpler is better: a comparative study of randomized pivoting algorithms for CUR and interpolative decompositions
- A multilinear Nyström algorithm for low-rank approximation of tensors in Tucker format
- 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
- Efficient bounds and estimates for canonical angles in randomized subspace approximations
- Hadamard transforms and analysis on Cayley-Dickson algebras
- Dictionary-based model reduction for state estimation
- Randomized flexible GMRES with deflated restarting
- Growth Factors of Random Butterfly Matrices and the Stability of Avoiding Pivoting
- Preserving privacy between features in distributed estimation
- Random multipliers numerically stabilize Gaussian and block Gaussian elimination: proofs and an extension to low-rank approximation
- 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
- Interpolation of inverse operators for preconditioning parameter-dependent equations
- On greedy randomized average block Kaczmarz method for solving large linear systems
- Far-field compression for fast kernel summation methods in high dimensions
- Title not available (Why is that?)
- 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
- Randomized numerical linear algebra: Foundations and algorithms
- Random sampling of bandlimited signals on graphs
- Sublinear Cost Low Rank Approximation via Subspace Sampling
- On data preconditioning for regularized loss minimization
- Sketched ridge regression: optimization perspective, statistical perspective, and model averaging
- Weighted SGD for \(\ell_p\) regression with randomized preconditioning
- Randomized LU decomposition using sparse projections
- Randomized matrix-free trace and log-determinant estimators
- Perturbations of CUR Decompositions
- Sharper bounds for regularized data fitting
- Scalable kernel \(k\)-means clustering with Nyström approximation: relative-error bounds
- Randomized Low-Rank Approximation for Symmetric Indefinite Matrices
- A fast randomized algorithm for computing an approximate null space
- Improved matrix algorithms via the subsampled randomized Hadamard transform
- Robust CUR Decomposition: Theory and Imaging Applications
- Numerically safe Gaussian elimination with no pivoting
- The fast Cauchy transform and faster robust linear regression
- Randomized approximation of the Gram matrix: exact computation and probabilistic bounds
- Randomized linear algebra for model reduction. I. Galerkin methods and error estimation
- Practical sketching algorithms for low-rank matrix approximation
- Faster randomized block Kaczmarz algorithms
- On randomized sketching algorithms and the Tracy-Widom law
- Randomized block Krylov subspace methods for trace and log-determinant estimators
- Randomized Dynamic Mode Decomposition
- On spectral and numerical properties of random butterfly matrices
- New studies of randomized augmentation and additive preprocessing
- Stochastic block projection algorithms with extrapolation for convex feasibility problems
- A Computationally Efficient Projection-Based Approach for Spatial Generalized Linear Mixed Models
- Universality laws for randomized dimension reduction, with applications
- Toward a unified theory of sparse dimensionality reduction in Euclidean space
- High-dimensional model recovery from random sketched data by exploring intrinsic sparsity
- Randomized LU decomposition
- Block Kaczmarz method with inequalities
- Paved with good intentions: analysis of a randomized block Kaczmarz method
- Adaptive iterative Hessian sketch via \(A\)-optimal subsampling
- 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
- 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
- Fast spatial Gaussian process maximum likelihood estimation via skeletonization factorizations
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)
