Estimating Leverage Scores via Rank Revealing Methods and Randomization
From MaRDI portal
Publication:5006452
DOI10.1137/20M1314471zbMath1472.62082arXiv2105.11004OpenAlexW3189461746MaRDI QIDQ5006452
Aleksandros Sobczyk, Efstratios Gallopoulos
Publication date: 16 August 2021
Published in: SIAM Journal on Matrix Analysis and Applications (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2105.11004
Estimation in multivariate analysis (62H12) Random matrices (probabilistic aspects) (60B20) Randomized algorithms (68W20) Preconditioners for iterative methods (65F08)
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Toward a unified theory of sparse dimensionality reduction in Euclidean space
- Fast quantum algorithms for least squares regression and statistic leverage scores
- Faster least squares approximation
- Fast dimension reduction using Rademacher series on dual BCH codes
- Four algorithms for the the efficient computation of truncated pivoted QR approximations to a sparse matrix
- Accelerating data uncertainty quantification by solving linear systems with multiple right-hand sides
- Column subset selection is NP-complete
- An estimator for the diagonal of a matrix
- Handbook series linear algebra. Linear least squares solutions by Householder transformations
- Column subset selection problem is UG-hard
- Completing Any Low-rank Matrix, Provably
- LSRN: A Parallel Iterative Solver for Strongly Over- or Underdetermined Systems
- A sparse Johnson
- Approximate nearest neighbors and the fast Johnson-Lindenstrauss transform
- Computational Advertising: Techniques for Targeting Relevant Ads
- Julia: A Fresh Approach to Numerical Computing
- Single Pass Spectral Sparsification in Dynamic Streams
- Uniform Sampling for Matrix Approximation
- Algorithm 915, SuiteSparseQR
- A fast randomized algorithm for overdetermined linear least-squares regression
- IMPROVED ANALYSIS OF THE SUBSAMPLED RANDOMIZED HADAMARD TRANSFORM
- Blendenpik: Supercharging LAPACK's Least-Squares Solver
- Low-Rank Approximation and Regression in Input Sparsity Time
- Sparser Johnson-Lindenstrauss Transforms
- Extensions of Lipschitz mappings into a Hilbert space
- Communication Avoiding Rank Revealing QR Factorization with Column Pivoting
- Adaptive Sampling and Fast Low-Rank Matrix Approximation
- Efficient Computing of Regression Diagnostics
- The Hat Matrix in Regression and ANOVA
- Computing rank-revealing QR factorizations of dense matrices
- On Rank-Revealing Factorisations
- A BLAS-3 Version of the QR Factorization with Column Pivoting
- Matrix rank certification
- Nearly Tight Oblivious Subspace Embeddings by Trace Inequalities
- Input Sparsity Time Low-rank Approximation via Ridge Leverage Score Sampling
- Faster Kernel Ridge Regression Using Sketching and Preconditioning
- Randomized algorithms in numerical linear algebra
- Efficient Algorithms for Computing a Strong Rank-Revealing QR Factorization
- Spectrum Approximation Beyond Fast Matrix Multiplication: Algorithms and Hardness
- Density Independent Algorithms for Sparsifying k-Step Random Walks
- Why Are Big Data Matrices Approximately Low Rank?
- The Effect of Coherence on Sampling from Matrices with Orthonormal Columns, and Preconditioned Least Squares Problems
- Sparsity and incoherence in compressive sampling
- Tighter Low-rank Approximation via Sampling the Leveraged Element
- Structural Convergence Results for Approximation of Dominant Subspaces from Block Krylov Spaces
- Fast matrix rank algorithms and applications
- Faster Subset Selection for Matrices and Applications
- Algorithm 844
- Low-distortion subspace embeddings in input-sparsity time and applications to robust linear regression
- Sparsity lower bounds for dimensionality reducing maps
- Conditioning of Leverage Scores and Computation by QR Decomposition
This page was built for publication: Estimating Leverage Scores via Rank Revealing Methods and Randomization
