Sparse and low-rank approximations of large symmetric matrices using biharmonic interpolation

Abstract

Symmetric matrices are widely used in machine learning problems such as kernel machines and manifold learning. Using large datasets often requires computing low-rank approximations of these symmetric matrices so that they fit in memory. In this paper, we present a novel method based on biharmonic interpolation for low-rank matrix approximation. The method exploits knowledge of the data manifold to learn an interpolation operator that approximates values using a subset of randomly selected landmark points. This operator is readily sparsified, reducing memory requirements by at least two orders of magnitude without significant loss in accuracy. We show that our method can approximate very large datasets using twenty times more landmarks than other methods. Further, numerical results suggest that our method is stable even when numerical difficulties arise for other methods.