Fast Spectral Learning Using Lanczos Eigenspace Projections

Abstract

The core computational step in spectral learning – find-ing the projection of a function onto the eigenspace of a symmetric operator, such as a graph Laplacian – gen-erally incurs a cubic computational complexity O(N3). This paper describes the use of Lanczos eigenspace pro-jections for accelerating spectral projections, which re-duces the complexity to O(nTop + n2N) operations, where n is the number of distinct eigenvalues, and Top is the complexity of multiplying T by a vector. This approach is based on diagonalizing the restriction of the operator to the Krylov space spanned by the op-erator and a projected function. Even further savings can be accrued by constructing an approximate Lanc-zos tridiagonal representation of the Krylov-space re-stricted operator. A key novelty of this paper is the use of Krylov-subspace modulated Lanczos acceleration for multi-resolution wavelet analysis. A challenging prob-lem of learning to control a robot arm is used to test the proposed approach.