A fast randomized algorithm for computing an approximate null space

DOI10.1007/s10543-023-00979-7zbMath1515.65085arXiv2206.00975OpenAlexW4378217996MaRDI QIDQ6161581

Yuji Nakatsukasa, Unnamed Author

Publication date: 5 June 2023

Published in: BIT (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2206.00975

zbMATH Keywords

sketchingrandomized algorithmnull spacemultiplicative perturbation theorysingular subspace

Mathematics Subject Classification ID

Numerical solutions to overdetermined systems, pseudoinverses (65F20) Inequalities involving eigenvalues and eigenvectors (15A42) Eigenvalues, singular values, and eigenvectors (15A18) Numerical methods for low-rank matrix approximation; matrix compression (65F55)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions
• An Analysis of the Total Least Squares Problem
• Rang revealing QR factorizations
• A fast randomized algorithm for the approximation of matrices
• Representation of conformal maps by rational functions
• Improved Matrix Algorithms via the Subsampled Randomized Hadamard Transform
• Communication-optimal Parallel and Sequential QR and LU Factorizations
• Computational Advertising: Techniques for Targeting Relevant Ads
• IMPROVED ANALYSIS OF THE SUBSAMPLED RANDOMIZED HADAMARD TRANSFORM
• Low-Rank Approximation and Regression in Input Sparsity Time
• A QUANTITATIVE FORMULATION OF SYLVESTER'S LAW OF INERTIA
• SYMMETRIC GAUGE FUNCTIONS AND UNITARILY INVARIANT NORMS
• Rank-Revealing QR Factorizations and the Singular Value Decomposition
• Relative Perturbation Theory: I. Eigenvalue and Singular Value Variations
• Relative Perturbation Theory: II. Eigenspace and Singular Subspace Variations
• Block Downdating of Least Squares Solutions
• Practical Sketching Algorithms for Low-Rank Matrix Approximation
• Automatic rational approximation and linearization of nonlinear eigenvalue problems
• Numerical linear algebra in the streaming model
• Streaming Low-Rank Matrix Approximation with an Application to Scientific Simulation
• DISTRIBUTION OF EIGENVALUES FOR SOME SETS OF RANDOM MATRICES
• The Rotation of Eigenvectors by a Perturbation. III
• Perturbation bounds in connection with singular value decomposition
• The AAA Algorithm for Rational Approximation
• From ESPRIT to ESPIRA: estimation of signal parameters by iterative rational approximation
• Randomized numerical linear algebra: Foundations and algorithms