IMPROVED ANALYSIS OF THE SUBSAMPLED RANDOMIZED HADAMARD TRANSFORM
From MaRDI portal
Publication:3101550
DOI10.1142/S1793536911000787zbMath1232.15029arXiv1011.1595OpenAlexW2963455674MaRDI QIDQ3101550
Publication date: 29 November 2011
Published in: Advances in Adaptive Data Analysis (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1011.1595
Random matrices (algebraic aspects) (15B52) Linear transformations, semilinear transformations (15A04) Boolean and Hadamard matrices (15B34)
Related Items
Numerically safe Gaussian elimination with no pivoting, On principal components regression, random projections, and column subsampling, Randomized numerical linear algebra: Foundations and algorithms, On data preconditioning for regularized loss minimization, Stochastic block projection algorithms with extrapolation for convex feasibility problems, On greedy randomized average block Kaczmarz method for solving large linear systems, New studies of randomized augmentation and additive preprocessing, Perturbations of the \textsc{Tcur} decomposition for tensor valued data in the Tucker format, Far-field compression for fast kernel summation methods in high dimensions, On expected error of randomized Nyström kernel regression, Sharper Bounds for Regularized Data Fitting, Randomized matrix-free trace and log-determinant estimators, RidgeSketch: A Fast Sketching Based Solver for Large Scale Ridge Regression, Block Kaczmarz method with inequalities, Simpler is better: a comparative study of randomized pivoting algorithms for CUR and interpolative decompositions, The Expected Norm of a Sum of Independent Random Matrices: An Elementary Approach, Randomized algorithms in numerical linear algebra, Randomized Low-Rank Approximation for Symmetric Indefinite Matrices, Randomized LU decomposition, Random sampling of bandlimited signals on graphs, Faster randomized block sparse Kaczmarz by averaging, Growth Factors of Random Butterfly Matrices and the Stability of Avoiding Pivoting, Practical Sketching Algorithms for Low-Rank Matrix Approximation, Adaptive iterative Hessian sketch via \(A\)-optimal subsampling, 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, Fast Spatial Gaussian Process Maximum Likelihood Estimation via Skeletonization Factorizations, 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, Paved with good intentions: analysis of a randomized block Kaczmarz method, Structural Convergence Results for Approximation of Dominant Subspaces from Block Krylov Spaces, Asymptotically liberating sequences of random unitary matrices, Sub-sampled Newton methods, Toward a unified theory of sparse dimensionality reduction in Euclidean space, Randomized LU decomposition using sparse projections, Unnamed Item, Unnamed Item, On spectral and numerical properties of random butterfly matrices, Faster Randomized Block Kaczmarz Algorithms, Interpolation of Inverse Operators for Preconditioning Parameter-Dependent Equations, Randomized Dynamic Mode Decomposition, Randomized block Krylov subspace methods for trace and log-determinant estimators, The Fast Cauchy Transform and Faster Robust Linear Regression, Randomized linear algebra for model reduction. I. Galerkin methods and error estimation, A Computationally Efficient Projection-Based Approach for Spatial Generalized Linear Mixed Models, Streaming Low-Rank Matrix Approximation with an Application to Scientific Simulation, High-dimensional model recovery from random sketched data by exploring intrinsic sparsity, Randomized Approximation of the Gram Matrix: Exact Computation and Probabilistic Bounds, Estimating Leverage Scores via Rank Revealing Methods and Randomization, Unnamed Item, Unnamed Item, Perturbations of CUR Decompositions, Robust CUR Decomposition: Theory and Imaging Applications, Sublinear Cost Low Rank Approximation via Subspace Sampling, Tensor-Structured Sketching for Constrained Least Squares, Random multipliers numerically stabilize Gaussian and block Gaussian elimination: proofs and an extension to low-rank approximation
Cites Work
- Unnamed Item
- Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions
- On the conditioning of random subdictionaries
- A fast randomized algorithm for the approximation of matrices
- On Talagrand's deviation inequalities for product measures
- Extensions of Lipschitz mappings into a Hilbert space
