Randomized numerical linear algebra: Foundations and algorithms (Q5887823)

scientific article; zbMATH DE number 7674565

Language	Label	Description	Also known as
English	Randomized numerical linear algebra: Foundations and algorithms	scientific article; zbMATH DE number 7674565

Statements

instance of

scholarly article

0 references

title

Randomized numerical linear algebra: Foundations and algorithms (English)

0 references

author

Joel A. Tropp

0 references

Per-Gunnar Martinsson

0 references

published in

Acta Numerica

0 references

publication date

14 April 2023

0 references

full work available at URL

https://arxiv.org/abs/2002.01387

0 references

describes a project that uses

0 references

0 references

0 references

0 references

0 references

0 references

0 references

0 references

0 references

0 references

Database-friendly random projections: Johnson-Lindenstrauss with binary coins.

0 references

Fast computation of low rank matrix approximations

0 references

Fast computation of low-rank matrix approximations

0 references

Strong converse for identification via quantum channels

0 references

Approximate nearest neighbors and the fast Johnson-Lindenstrauss transform

0 references

The Fast Johnson–Lindenstrauss Transform and Approximate Nearest Neighbors

0 references

Tracking join and self-join sizes in limited storage

0 references

The space complexity of approximating the frequency moments

0 references

Living on the edge: phase transitions in convex programs with random data

0 references

The Schur complement and its applications

0 references

On the bootstrap of $U$ and $V$ statistics

0 references

Sequential Sampling for Optimal Weighted Least Squares Approximations in Hierarchical Spaces

0 references

Faster Kernel Ridge Regression Using Sketching and Preconditioning

0 references

Revisiting Asynchronous Linear Solvers

0 references

A universal sampling method for reconstructing signals with simple Fourier transforms

0 references

Blendenpik: Supercharging LAPACK's Least-Squares Solver

0 references

On the Equivalence between Kernel Quadrature Rules and Random Feature Expansions

0 references

Spectral analysis of large dimensional random matrices

0 references

Templates for the Solution of Algebraic Eigenvalue Problems

0 references

Polynomial Threshold Functions, Hyperplane Arrangements, and Random Tensors

0 references

Twice-Ramanujan Sparsifiers

0 references

Accelerating Galerkin BEM for linear elasticity using adaptive cross approximation

0 references

Computing rank-revealing QR factorizations of dense matrices

0 references

Large-Scale Machine Learning with Stochastic Gradient Descent

0 references

Q4907706

0 references

Toward a unified theory of sparse dimensionality reduction in Euclidean space

0 references

Q4633910

0 references

Optimal principal component analysis in distributed and streaming models

0 references

Q4838168

0 references

Efficient sampling methods for discrete distributions

0 references

A Fast Butterfly Algorithm for the Computation of Fourier Integral Operators

0 references

Inequalities of Bernstein-Jackson-type and the degree of compactness of operators in Banach spaces

0 references

The convex geometry of linear inverse problems

0 references

Finding frequent items in data streams

0 references

Normal Approximation by Stein’s Method

0 references

Condition Numbers of Gaussian Random Matrices

0 references

On the Compression of Low Rank Matrices

0 references

Numerical linear algebra in the streaming model

0 references

Low-Rank Approximation and Regression in Input Sparsity Time

0 references

Optimal weighted least-squares methods

0 references

On the stability and accuracy of least squares approximations

0 references

Approximating Matrix Multiplication for Pattern Recognition Tasks

0 references

Nearly Tight Oblivious Subspace Embeddings by Trace Inequalities

0 references

Solving SDD linear systems in nearly m log 1/2 n time

0 references

Q2760174

0 references

A survey of direct methods for sparse linear systems

0 references

Fast linear algebra is stable

0 references

Communication-optimal Parallel and Sequential QR and LU Factorizations

0 references

Communication Avoiding Rank Revealing QR Factorization with Column Pivoting

0 references

Estimating Extremal Eigenvalues and Condition Numbers of Matrices

0 references

Q5121145

0 references

Q3093333

0 references

Fast Monte Carlo Algorithms for Matrices I: Approximating Matrix Multiplication

0 references

Fast Monte Carlo Algorithms for Matrices II: Computing a Low-Rank Approximation to a Matrix

0 references

Fast Monte Carlo Algorithms for Matrices III: Computing a Compressed Approximate Matrix Decomposition

0 references

Subspace Sampling and Relative-Error Matrix Approximation: Column-Based Methods

0 references

Relative-Error $CUR$ Matrix Decompositions

0 references

Randomized QR with Column Pivoting

0 references

Eigenvalues and Condition Numbers of Random Matrices

0 references

Q3959963

0 references

Flip-flop spectrum-revealing QR factorization and its applications to singular value decomposition

0 references

UTV tools: Matlab templates for rank-revealing UTV decompositions

0 references

10.1162/15324430260185619

0 references

A mathematical introduction to compressive sensing

0 references

Fast monte-carlo algorithms for finding low-rank approximations

0 references

Frequent Directions: Simple and Deterministic Matrix Sketching

0 references

A fast ``Monte-Carlo cross-validation'' procedure for large least squares problems with noisy data

0 references

Improved Matrix Algorithms via the Subsampled Randomized Hadamard Transform

0 references

Gaussian phase transitions and conic intrinsic volumes: steining the Steiner formula

0 references

0 references

0 references

0 references

0 references

A Block Lanczos Method for Computing the Singular Values and Corresponding Singular Vectors of a Matrix

0 references

A new formula for k-statistics

0 references

Q3796199

0 references

Q3086656

0 references

Pseudo-skeleton approximations by matrices of maximal volume

0 references

Randomized Iterative Methods for Linear Systems

0 references

Construction and arithmetics of $\mathcal H$-matrices

0 references

Improved Bounds for Small-Sample Estimation

0 references

A fast algorithm for particle simulations

0 references

Q2744679

0 references

Subspace Iteration Randomization and Singular Value Problems

0 references

Efficient Algorithms for Computing a Strong Rank-Revealing QR Factorization

0 references

A sparse matrix arithmetic based on ${\mathfrak H}$-matrices. I: Introduction to ${\mathfrak H}$-matrices

0 references

Q4513819

0 references

Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions

0 references

An Algorithm for the Principal Component Analysis of Large Data Sets

0 references

Coherence motivated sampling and convergence analysis of least squares polynomial chaos regression

0 references

Methods of conjugate gradients for solving linear systems

0 references

Q4902474

0 references

A stochastic estimator of the trace of the influence matrix for laplacian smoothing splines

0 references

Q4542583

0 references

Faster Johnson–Lindenstrauss transforms via Kronecker products

0 references

Extensions of Lipschitz mappings into a Hilbert space

0 references

On the distribution of the largest eigenvalue in principal components analysis

0 references

Q3139319

0 references

Q3236483

0 references

Numerical Linear Algebra

0 references

Randomized algorithms in numerical linear algebra

0 references

The price of privately releasing contingency tables and the spectra of random matrices with correlated rows

0 references

Spectrum estimation from samples

0 references

Q4278200

0 references

New and Improved Johnson–Lindenstrauss Embeddings via the Restricted Isometry Property

0 references

Preconditioned Low-rank Riemannian Optimization for Linear Systems with Tensor Product Structure

0 references

Estimating the Largest Eigenvalue by the Power and Lanczos Algorithms with a Random Start

0 references

Q5405152

0 references

Sparsified Cholesky and multigrid solvers for connection laplacians

0 references

Q3997990

0 references

Randomized Methods for Linear Constraints: Convergence Rates and Conditioning

0 references

Estimating a largest eigenvector by Lanczos and polynomial algorithms with a random start

0 references

Algorithm 971

0 references

Interpolative Butterfly Factorization

0 references

On Sketching Matrix Norms and the Top Singular Vector

0 references

Turnstile streaming algorithms might as well be linear sketches

0 references

Multidimensional butterfly factorization

0 references

Butterfly Factorization

0 references

Randomized algorithms for the low-rank approximation of matrices

0 references

Fast Randomized Iteration: Diffusion Monte Carlo through the Lens of Numerical Linear Algebra

0 references

Fast construction of hierarchical matrix representation from matrix-vector multiplication

0 references

The geometry of graphs and some of its algorithmic applications

0 references

Estimating the algorithmic variance of randomized ensembles via the bootstrap

0 references

Q3721269

0 references

Matrix concentration inequalities via the method of exchangeable pairs

0 references

Randomized Algorithms for Matrices and Data

0 references

CUR matrix decompositions for improved data analysis

0 references

Guarantees for the Kronecker fast Johnson-Lindenstrauss transform using a coherence and sampling argument

0 references

ASKIT: Approximate Skeletonization Kernel-Independent Treecode in High Dimensions

0 references

Random Fourier Series with Applications to Harmonic Analysis. (AM-101)

0 references

A Fast Randomized Algorithm for Computing a Hierarchically Semiseparable Representation of a Matrix

0 references

Compressing Rank-Structured Matrices via Randomized Sampling

0 references

Randomized methods for matrix computations

0 references

A fast direct solver for boundary integral equations in two dimensions

0 references

A Randomized Blocked Algorithm for Efficiently Computing Rank-revealing Factorizations of Matrices

0 references

A fast algorithm for the inversion of general Toeplitz matrices

0 references

On interpolation and integration in finite-dimensional spaces of bounded functions

0 references

randUTV

0 references

Householder QR Factorization With Randomization for Column Pivoting (HQRRP)

0 references

A block QR algorithm and the singular value decomposition

0 references

From Steiner formulas for cones to concentration of intrinsic volumes

0 references

Improved bounds for sparse recovery from subsampled random convolutions

0 references

Low-distortion subspace embeddings in input-sparsity time and applications to robust linear regression

0 references

LSRN: A Parallel Iterative Solver for Strongly Over- or Underdetermined Systems

0 references

How to generate random matrices from the classical compact groups

0 references

Q3219581

0 references

Input Sparsity Time Low-rank Approximation via Ridge Leverage Score Sampling

0 references

Stability of the Lanczos Method for Matrix Function Approximation

0 references

Q3425115

0 references

Paved with good intentions: analysis of a randomized block Kaczmarz method

0 references

Stochastic gradient descent, weighted sampling, and the randomized Kaczmarz algorithm

0 references

A simplified neuron model as a principal component analyzer

0 references

On the convergence to equilibrium of Kac's random walk on matrices

0 references

Universality laws for randomized dimension reduction, with applications

0 references

Compressed matrix multiplication

0 references

Numerically safe Gaussian elimination with no pivoting

0 references

Latent semantic indexing: A probabilistic analysis

0 references

Downdating the Rank-Revealing URV Decomposition

0 references

Q4348515

0 references

Randomized Sketches of Convex Programs With Sharp Guarantees

0 references

Iterative Hessian sketch: Fast and accurate solution approximation for constrained least-squares

0 references

Kac's walk on $n$-sphere mixes in $n\log n$ steps

0 references

The cut-off phenomenon for random reflections

0 references

Sparse Legendre expansions via $\ell_1$-minimization

0 references

Interpolation via weighted $\ell_{1}$ minimization

0 references

Restricted isometries for partial random circulant matrices

0 references

Stochastic Reformulations of Linear Systems: Algorithms and Convergence Theory

0 references

A fast randomized algorithm for overdetermined linear least-squares regression

0 references

A Randomized Algorithm for Principal Component Analysis

0 references

Random rotations: Characters and random walks on $SO(N)$

0 references

Fundamentals of Stein's method

0 references

Random vectors in the isotropic position

0 references

Row products of random matrices

0 references

Sampling from large matrices

0 references

On sparse reconstruction from Fourier and Gaussian measurements

0 references

Smoothed Analysis of the Condition Numbers and Growth Factors of Matrices

0 references

Positive definite functions on spheres

0 references

Q4413262

0 references

Q4745749

0 references

A DEIM Induced CUR Factorization

0 references

Graph Sparsification by Effective Resistances

0 references

Q4288559

0 references

Q4220521

0 references

The QLP Approximation to the Singular Value Decomposition

0 references

Matrix Algorithms

0 references

Q4611648

0 references

Gaussian elimination is not optimal

0 references

A randomized Kaczmarz algorithm with exponential convergence

0 references

The Laplacian Paradigm: Emerging Algorithms for Massive Graphs

0 references

Recovering Structured Signals in Noise: Least-Squares Meets Compressed Sensing

0 references

Q4768187

0 references

Q4337625

0 references

On spectral and numerical properties of random butterfly matrices

0 references

Freedman's inequality for matrix martingales

0 references

IMPROVED ANALYSIS OF THE SUBSAMPLED RANDOMIZED HADAMARD TRANSFORM

0 references

A comparison principle for functions of a uniformly random subspace

0 references

User-friendly tail bounds for sums of random matrices

0 references

An Introduction to Matrix Concentration Inequalities

0 references

The Expected Norm of a Sum of Independent Random Matrices: An Elementary Approach

0 references

Practical Sketching Algorithms for Low-Rank Matrix Approximation

0 references

Streaming Low-Rank Matrix Approximation with an Application to Scientific Simulation

0 references

Fast Estimation of $tr(f(A))$ via Stochastic Lanczos Quadrature

0 references

High-Dimensional Probability

0 references

Concentration inequalities for random tensors

0 references

Efficient algorithms for CUR and interpolative matrix decompositions

0 references

An introduction to finite tight frames

0 references

Q4633019

0 references

Computational Advertising: Techniques for Targeting Relevant Ads

0 references

A fast randomized algorithm for the approximation of matrices

0 references

Randomized Sparse Direct Solvers

0 references

Using Random Butterfly Transformations to Avoid Pivoting in Sparse Direct Methods

0 references

Identifiers

DOI

10.1017/S0962492920000021

0 references

Mathematics Subject Classification ID

0 references

0 references

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:5887823