Energy-Based Sequential Sampling for Low-Rank PSD-Matrix Approximation

We introduce a pseudoconvex differentiable relaxation of the column-sampling problem for the Nyström approximation of positive-semidefinite (PSD) matrices. The relaxation is based on the interpretation of PSD matrices as integral operators and relies on the supports of measures to characterise samples of columns. We describe a class of gradient-based sequential sampling strategies which leverages the properties of the considered framework, and demonstrate its ability to produce accurate Nyström approximations. The time complexity of the stochastic variants of the discussed strategies is linear in the order of the considered PSD matrices, and the underlying computations can be easily parallelised.