Randomized algorithms in numerical linear algebra
From MaRDI portal
Publication:4594242
DOI10.1017/S0962492917000058zbMath1378.65084MaRDI QIDQ4594242
Santosh Vempala, Ravindran Kannan
Publication date: 17 November 2017
Published in: Acta Numerica (Search for Journal in Brave)
tensorpreconditioningmatrix productembeddingsregressionrandomized algorithmslow-rank approximationsampling methodintroductory survey
Linear regression; mixed models (62J05) Research exposition (monographs, survey articles) pertaining to numerical analysis (65-02) Iterative numerical methods for linear systems (65F10) Multilinear algebra, tensor calculus (15A69) Randomized algorithms (68W20) Preconditioners for iterative methods (65F08)
Related Items
Randomized numerical linear algebra: Foundations and algorithms, Three matrix factorizations from the steps of elimination, Best and random approximation of a convex body by a polytope, Solving sparse principal component analysis with global support, Pass-efficient randomized LU algorithms for computing low-rank matrix approximation, On the convergence of randomized and greedy relaxation schemes for solving nonsingular linear systems of equations, Unnamed Item, Random Sampling and Efficient Algorithms for Multiscale PDEs, Spatio-temporal proper orthogonal decomposition of turbulent channel flow, Unnamed Item, Estimating Leverage Scores via Rank Revealing Methods and Randomization, Bootstrapping the operator norm in high dimensions: error estimation for covariance matrices and sketching, LU and CR Elimination
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions
- On tail probabilities for martingales
- A theory of pseudoskeleton approximations
- Four algorithms for the the efficient computation of truncated pivoted QR approximations to a sparse matrix
- An algorithmic theory of learning: Robust concepts and random projection
- A sparse Johnson
- Computational Advertising: Techniques for Targeting Relevant Ads
- Optimal CUR Matrix Decompositions
- Uniform Sampling for Matrix Approximation
- IMPROVED ANALYSIS OF THE SUBSAMPLED RANDOMIZED HADAMARD TRANSFORM
- Randomized Algorithms for Matrices and Data
- Low-Rank Approximation and Regression in Input Sparsity Time
- Sparser Johnson-Lindenstrauss Transforms
- Fast computation of low-rank matrix approximations
- Sampling from large matrices
- Adaptive Sampling and Fast Low-Rank Matrix Approximation
- Relative-Error $CUR$ Matrix Decompositions
- Spectral Algorithms
- Strong converse for identification via quantum channels
- Nearly Tight Oblivious Subspace Embeddings by Trace Inequalities
- Input Sparsity Time Low-rank Approximation via Ridge Leverage Score Sampling
- An elementary proof of a theorem of Johnson and Lindenstrauss
- Numerical linear algebra in the streaming model
- Most Tensor Problems Are NP-Hard
- Lx = b
- Fast monte-carlo algorithms for finding low-rank approximations
- Fast Monte Carlo Algorithms for Matrices II: Computing a Low-Rank Approximation to a Matrix
- Low-distortion subspace embeddings in input-sparsity time and applications to robust linear regression
- Graph Sparsification by Effective Resistances
