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.

本文提出了一系列启发式策略，使 Nyström 方法在 nonsymmetric 或 rectangular 矩阵中具有高准确度，通过交替方向细化过程，将 Nyström 方法和瘦秩揭示分解作为快速枢轴策略。