Suivi d'espace dominant par la méthode des puissances itérées

Roland Badeau, Gaël Richard, Bertrand DavidHAL 2003

TL;DR

This paper introduces a novel sliding window version of the API subspace tracking algorithm, SW-API, which offers faster adaptation to abrupt signal changes compared to existing methods. By leveraging a less restrictive approximation and a sliding window, SW-API achieves comparable or superior performance to state-of-the-art algorithms while maintaining computational efficiency.

What Problem Does This Paper Address?

Estimating dominant subspaces is crucial in various signal processing applications like adaptive filtering, source localization, and parameter estimation. Many existing subspace tracking algorithms, such as PAST and NIC, rely on iterative optimization or approximations of the power iteration method. While these methods are effective, they often use exponential windows that smooth out signal variations, leading to slower responses to sudden changes. This paper addresses the need for subspace tracking algorithms that are both computationally efficient and capable of rapidly adapting to dynamic signal environments.

Methods

The core of this paper is the development of the Sliding Window API (SW-API) algorithm. It builds upon the API (Approximated Power Iterations) method, which itself is derived from the power iteration method for subspace tracking. The key innovations are:

  • Sliding Window: Instead of an exponential decay window, SW-API uses a sliding window. This allows the algorithm to focus on recent data, enabling quicker adaptation to signal variations.
  • Less Restrictive Approximation: SW-API employs an approximation that is less restrictive than the "projection approximation" used in some prior work. This contributes to its improved performance.
  • Efficient Updates: The paper details how to derive efficient recursive updates for the necessary matrices, particularly focusing on the update of the subspace basis matrix $W(t)$ and the covariance matrix $C_{xx}(t)$.
  • SW-FAPI Algorithm: A "fast" version, SW-FAPI, is also proposed, which further optimizes computations by making specific choices for matrix square roots, reducing the overall complexity.

The algorithm guarantees the orthonormality of the generated matrix at each iteration and satisfies a global and exponential convergence property, inherited from the power iteration method.

Datasets

Not discussed in the paper. The paper uses simulated data for evaluation.

Key Insights and Ideas

  • Sliding Window Advantage: The most significant insight is that a sliding window, despite potentially being more computationally demanding in some contexts, offers a crucial advantage in tracking applications: much faster reaction to abrupt signal changes. This is demonstrated through simulations.
  • API's Adaptability: The API algorithm, when adapted with a sliding window, proves to be a strong contender, outperforming several established methods like PAST, NIC, NP3, and OPAST in terms of tracking speed and accuracy.
  • Computational Efficiency: The SW-API algorithm achieves these performance gains without a significant increase in computational complexity compared to its predecessors, making it practical for real-time applications.
  • Orthonormality Guarantee: The algorithm's ability to maintain an orthonormal subspace basis at every step is a key feature, contributing to numerical stability and reliable performance.

Key Results

The paper presents simulation results demonstrating the effectiveness of SW-API:

  • Faster Tracking: SW-API shows a significantly faster response to abrupt frequency changes in the simulated sinusoidal signals compared to the FAPI (exponential window) method.
  • Superior Performance: SW-FAPI is shown to be more accurate than SW-OPAST and SW-NIC, as evidenced by the lower error angles in the simulations.
  • Robustness: The algorithm is robust to variations in the signal, as indicated by the performance plots.
  • Computational Complexity: The SW-API algorithm has a complexity of $O((n+1)r)$, where $n$ is the dimension of the data vectors and $r$ is the dimension of the dominant subspace. The fast version, SW-FAPI, achieves this complexity.

Limitations and Future Work

  • Invertibility Assumption: The derivation of the SW-API and SW-FAPI algorithms relies on the assumption that certain matrices (specifically $J + y(t)h(t)$) are invertible. While the authors state they have not encountered cases where this assumption fails in their simulations, it remains a potential limitation. They mention that a solution for non-invertible cases has been proposed in prior work [7].
  • Choice of Square Root: The paper notes that the choice of the square root for certain matrices (like $p(t)$ in SW-FAPI) does not affect performance, but it implies that different choices might exist. Further exploration of these choices could be a future direction.
  • Real-World Data: The simulations are conducted on synthetic data. Applying and validating the algorithm on real-world, noisy datasets would be a valuable next step.

Summary updated

Abstract

International audience
BibTeX
@inproceedings{badeau2003suivi,
  author = {Roland Badeau and Gaël Richard and Bertrand David},
  title = {{Suivi d'espace dominant par la méthode des puissances itérées}},
  booktitle = {HAL},
  year = {2003},
}
Figure