Computer Science – Numerical Analysis
Scientific paper
2009-12-06
SIAM Journal on Scientific Computing, 33 (2): 849-868, 2011
Computer Science
Numerical Analysis
13 pages, 6 tables
Scientific paper
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).
Rokhlin Vladimir
Tygert Mark
No associations
LandOfFree
A fast randomized algorithm for orthogonal projection does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with A fast randomized algorithm for orthogonal projection, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A fast randomized algorithm for orthogonal projection will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-242477