Making the Nyström method highly accurate for low-rank approximations
Jianlin Xia
The Nystr\"om method is a convenient heuristic method to obtain low-rank
approximations to kernel matrices in nearly linear complexity. Existing studies
typically use the method to approximate positive semidefinite matrices with low
or modest accuracies. In this work, we propose a series of heuristic strategies
to make the Nystr\"om method reach high accuracies for nonsymmetric and/or
rectangular matrices. The resulting methods (called high-accuracy Nystr\"om
methods) treat the Nystr\"om method and a skinny rank-revealing factorization
as a fast pivoting strategy in a progressive alternating direction refinement
process. Two refinement mechanisms are used: alternating the row and column
pivoting starting from a small set of randomly chosen columns, and adaptively
increasing the number of samples until a desired rank or accuracy is reached. A
fast subset update strategy based on the progressive sampling of Schur
complements is further proposed to accelerate the refinement process. Efficient
randomized accuracy control is also provided. Relevant accuracy and singular
value analysis is given to support some of the heuristics. Extensive tests with
various kernel functions and data sets show how the methods can quickly reach
prespecified high accuracies in practice, sometimes with quality close to SVDs,
using only small numbers of progressive sampling steps.