A fast randomized algorithm for orthogonal projection

DOI10.1137/090779656MaRDI QIDQ3095088zbMATH OpenOpenAlexFDO

Authors Ed S. Coakley, Mark Tygert, Vladimir Rokhlin

Publication date 28 October 2011

Published in SIAM Journal on Scientific Computing (Search for Journal in Brave)

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

zbMATH Keywords

least squaresnormal equationsnumerical stabilityregression

Mathematics Subject Classification ID

Numerical solutions to overdetermined systems, pseudoinverses (65F20) Randomized algorithms (68W20)

Abstract: We describe an algorithm that, given any full-rank matrix A having fewer rows than columns, can rapidly compute the orthogonal projection of any vector onto the null space of A, as well as the orthogonal projection onto the row space of A, provided that both A and its adjoint can be applied rapidly to arbitrary vectors. As an intermediate step, the algorithm solves the overdetermined linear least-squares regression involving the adjoint of A (and so can be used for this, too). The basis of the algorithm is an obvious but numerically unstable scheme; suitable use of a preconditioner yields numerical stability. We generate the preconditioner rapidly via a randomized procedure that succeeds with extremely high probability. In many circumstances, the method can accelerate interior-point methods for convex optimization, such as linear programming (Ming Gu, personal communication).

Recommendations

• A fast randomized algorithm for overdetermined linear least-squares regression
• Faster least squares approximation
• Randomized algorithms in numerical linear algebra
• A fast randomized algorithm for computing an approximate null space
• A fast randomized algorithm for the approximation of matrices

Cited in

(17)

• Normal projection: deterministic and probabilistic algorithms
• On the perturbation of an \(L^2\)-orthogonal projection
• Randomized core reduction for discrete ill-posed problem
• Tikhonov regularization and randomized GSVD
• A fast randomized algorithm for overdetermined linear least-squares regression
• OrthoMADS: A Deterministic MADS Instance with Orthogonal Directions
• Infeasibility and Error Bound Imply Finite Convergence of Alternating Projections
• Deterministic APSP, Orthogonal Vectors, and More
• Random reordering in SOR-type methods
• Fast randomized iteration: diffusion Monte Carlo through the Lens of numerical linear algebra
• Computationally Efficient Decompositions of Oblique Projection Matrices
• Preconditioners for Krylov subspace methods: An overview
• A fast randomized algorithm for computing an approximate null space
• Faster least squares approximation
• New multiplicative perturbation bounds on orthogonal projection
• Survey of a class of iterative row-action methods: the Kaczmarz method
• Efficient algorithms for Tucker decomposition via approximate matrix multiplication

Describes a project that uses

Uses Software

• Blendenpik

This page was built for publication: A fast randomized algorithm for orthogonal projection

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3095088)