The core computational step in spectral learning — finding the projection of a function onto the eigenspace of a symmetric operator, such as a graph Laplacian — generally incurs a cubic computational complexity. This paper describes the use of Lanczos eigenspace projections for accelerating spectral projections, which reduces the complexity to quadratic in the number of distinct eigenvalues. This approach is based on diagonalizing the restriction of the operator to the Krylov space spanned by the operator and a projected function. Even further savings can be accrued by constructing an approximate Lanczos tridiagonal representation of the Krylov-space restricted operator. A key novelty of this paper is the use of Krylov-subspace modulated Lanczos acceleration for multi-resolution wavelet analysis. A challenging problem of learning to control a robot arm is used to test the proposed approach.
Subjects: 12. Machine Learning and Discovery; 12.1 Reinforcement Learning
Submitted: Apr 9, 2008