Stable Spectral Learning Based on Schur Decomposition

Nicolò Colombo, Nikos VlassisUAI 2015

Abstract

Spectral learning methods provide a computationally efficient alternative to iterative algorithms like Expectation-Maximization, yet they are often criticized for their sensitivity to noise and model misspecification. This paper presents a novel spectral learning framework based on Schur decomposition. By replacing standard eigen-decomposition with orthogonal triangularization, the proposed method achieves significantly higher numerical stability and improved error bounds. Empirical evaluations on multi-view data and Hidden Markov Models (HMMs) demonstrate that the Schur-based approach consistently outperforms traditional eigenvalue-based methods in parameter recovery and classification accuracy.

Introduction

Spectral learning has emerged as a powerful paradigm for estimating parameters in latent variable models, such as Hidden Markov Models (HMMs) and mixture models. Unlike iterative methods like Expectation-Maximization (EM), which are prone to local optima, spectral methods leverage linear algebra to find global solutions in a single pass. However, these methods possess a significant weakness: extreme sensitivity to noise and model misspecification.

In practice, observable matrices—constructed from empirical data frequencies—rarely satisfy the ideal mathematical assumptions of the model. Furthermore, when eigenvalues are closely spaced (small eigengaps), the resulting eigenvectors become highly unstable. This instability can lead to catastrophic failures, such as the recovery of imaginary probabilities. Colombo and Vlassis address these issues by proposing a shift from eigen-decomposition to Schur decomposition.

Methodology: The Schur Pivot

The core contribution of this work is the replacement of standard matrix diagonalization with Schur triangularization. In a standard spectral approach, an observable matrix $M$ is decomposed into $X \Lambda X^{-1}$, where $X$ is a matrix of eigenvectors. If $X$ is poorly conditioned, small perturbations in $M$ are amplified.

The proposed algorithm instead uses the Schur decomposition $M = UTU^T$, where $U$ is an orthogonal matrix and $T$ is upper triangular. This approach offers several advantages:

  1. Numerical Stability: Orthogonal matrices are perfectly conditioned, ensuring that noise is not amplified during the transformation.
  2. Diagonal Preservation: The real eigenvalues of $M$ remain on the diagonal of $T$, allowing for parameter recovery.
  3. Robustness to Noise: By allowing $T$ to be triangular rather than strictly diagonal, the algorithm accommodates noise more effectively than methods that force a perfect diagonalization.

The authors provide a rigorous perturbation analysis, showing that the estimation error for the Schur-based method depends linearly on the condition number of the underlying probability matrices, a significant improvement over the fourth-power dependence found in classical bounds.

Experimental Evaluation

The researchers evaluated the Schur-based algorithm against classical eigenvalue-based methods using simulated multi-view data and HMMs.

Multi-view Data

In experiments involving mixtures of product distributions, the Schur-based approach demonstrated superior performance across various sample sizes. As shown in Figure 1, the recovery error ($E_{schur}$) was consistently lower than that of the eigenvalue method ($E_{eig}$). For instance, at $N=2000$ samples, the Schur error was 0.039 compared to 0.120 for the classical approach.

Performance comparison on multi-view data ($d=10, p=5$).

Hidden Markov Models

The robustness of the Schur method was further tested on HMMs with varying dimensions ($d=5$ to $30$). The Schur method maintained a higher recovery ratio ($R$), which measures the percentage of correctly identified hidden state parameters. This advantage was particularly pronounced in lower-dimensional spaces ($d=5$), where the classical method frequently failed to recover parameters entirely ($R=0$).

HMM parameter recovery performance across different dimensions.

Conclusion

By leveraging the stability of orthogonal matrices through Schur decomposition, this work provides a more robust foundation for spectral learning. The resulting algorithm offers smoother error bounds and superior empirical performance in noisy or low-dimensional settings. Future work may involve integrating this approach with tensor factorization or random projections to further mitigate the impact of eigenvalue gaps, maintaining the global optimality of spectral methods while enhancing their practical reliability.

Summary updated

BibTeX
@inproceedings{colombo2015stable,
  author = {Nicolò Colombo and Nikos Vlassis},
  title = {{Stable Spectral Learning Based on Schur Decomposition}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2015},
}
Figure