Fast Spectral Learning using Lanczos Eigenspace Projections

Sridhar MahadevanAAAI 2008 · OpenReview

Abstract

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 $O(N^3)$. This paper describes the use of Lanczos eigenspace projections for accelerating spectral projections, which reduces the complexity to $O(n T^{op} + n^2 N)$ operations, where $n$ is the number of distinct eigenvalues, and $T^{op}$ 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 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.

Introduction

Spectral learning is a cornerstone of modern machine learning, underpinning techniques for clustering, dimensionality reduction, and reinforcement learning. These methods rely on analyzing the eigenvalues and eigenvectors of symmetric operators, typically graph Laplacians. However, the standard approach—full diagonalization of an $N \times N$ matrix—requires $O(N^3)$ computations. As datasets scale to millions of instances, such as 3D mesh vertices or complex robotic state spaces, this cubic cost becomes a prohibitive bottleneck. This paper addresses the challenge of projecting functions onto these eigenspaces without the computational burden of full matrix decomposition.

Methodology

The proposed method leverages Lanczos iteration to construct a Krylov subspace, shifting the focus from the entire $N$-dimensional space to a much smaller, function-specific subspace.

  1. Krylov Subspace Projection: The method restricts the operator $T$ to a subspace spanned by the powers of $T$ acting on a specific function $f$.
  2. Tridiagonal Representation: The Lanczos algorithm efficiently transforms the large operator into a compact $m \times m$ tridiagonal matrix ($L_m$), where $m \ll N$. This matrix retains the essential spectral properties required for projection.
  3. Krylov-Accelerated Diffusion Wavelets: The primary innovation lies in applying this acceleration to Diffusion Wavelets. Traditionally, these are built by repeatedly squaring a large matrix to capture multiscale features. By building the wavelet tree on the tiny tridiagonal Lanczos matrix and mapping the basis functions back to the original space, the complexity is reduced from $O(N^3)$ to nearly linear $O(n T^{op} + n^2 N)$, where $T^{op}$ is the cost of matrix-vector multiplication.

Experimental Evaluation

The method was evaluated using the Acrobot task, a classic reinforcement learning benchmark involving a two-link, under-actuated robot arm. The goal is to learn an optimal control policy to swing the arm to a target height. Data was collected via random walks in a 4-dimensional state space, with sample sizes ranging from 100 to 1,000 states. Accelerated wavelets served as basis functions for Representation Policy Iteration (RPI).

Key Results

The experimental results demonstrate a significant reduction in computational overhead without sacrificing performance. In the Acrobot experiments, the time required to construct the wavelet tree for a 1,000-state sample dropped from approximately 70 seconds using standard methods to roughly 13 seconds using the Krylov-accelerated approach.

Comparison of running times between regular and Krylov-accelerated diffusion wavelets showing superior scaling for the proposed method.

Crucially, this speedup does not come at the cost of accuracy. The reinforcement learning agent using accelerated wavelets achieved the goal in the same number of steps as the standard version, confirming that the Krylov-subspace approximation maintains the quality of the learned control policy.

Learning curves for the Acrobot task demonstrating that Krylov-Lanczos wavelets achieve parity with standard diffusion wavelets in policy performance.

Conclusion and Future Work

By restricting complex operators to a function-specific Krylov subspace, this work provides a path toward scalable spectral learning. While the current implementation is designed for symmetric operators, future work could extend this to non-symmetric operators using Arnoldi iteration. Additionally, while the method shows clear benefits at 1,000 states, its true potential lies in scaling to massive datasets with millions of nodes where traditional $O(N^3)$ methods are entirely unfeasible. The efficiency of the method remains sensitive to the tolerance parameter ($\delta$), which governs the trade-off between precision and computational speed.

Summary updated

Abstract

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 O(N3). This paper describes the use of Lanczos eigenspace projections for accelerating spectral projections, which reduces 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 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.
BibTeX
@inproceedings{mahadevan2008fast,
  author = {Sridhar Mahadevan},
  title = {{Fast Spectral Learning using Lanczos Eigenspace Projections}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2008},
  url = {https://openreview.net/forum?id=SJZvSgbubr},
}
Figure