Speaker
Description
Low Rank Approximation (LRA) of a matrix are invaluable for Numerical Linear Algebra and Data Science. Some recent papers propose superfast algorithms that output LRAs with near-optimal accuracy for a large class of inputs but, as ANY superfast LRA algorithm, fail on a large class of inputs as well. To narrow the latter class we first superfast compute a crude initial LRA by applying one of these or another superfast algorithm (we specify a novel class of such algorithms). Then we recursively refine that LRA superfast by extending iterative refinement algorithms for the solution of the systems of linear and nonlinear equations and by applying the recent techniques of oversampling and compression of J. A. Tropp, A. Yurtsever, M. Udell, V. Cevher, Streaming Low-Rank Matrix Approximation with an Application to Scientific Simulation, SIAM J. on Scientific Computing, 41, pp. A2430–A2463, 2019; this enables us to control rank growth in the refinement. We analyze our algorithms and test them numerically.