Sliding window orthonormal PAST algorithm

Roland Badeau, Karim Abed-Meraim, Gaël Richard, Bertrand David

TL;DR

This paper introduces the Sliding Window Orthonormal PAST (SW-OPAST) algorithm, a novel method for efficiently tracking signal subspaces. It achieves guaranteed orthonormality of the estimated subspace basis at each iteration, offering improved stability and faster convergence compared to existing methods, while maintaining computational efficiency.

What Problem Does This Paper Address?

In various signal processing applications like source localization and parameter estimation, accurately tracking the underlying signal subspace is crucial. Existing methods, such as the Projection Approximation Subspace Tracker (PAST), often struggle with either maintaining the orthonormality of the estimated subspace basis at every step or have high computational costs. While some orthonormal versions exist, they might sacrifice speed or global convergence properties. This paper aims to bridge this gap by developing an algorithm that combines the fast tracking response of sliding windows with the guaranteed orthonormality and global convergence properties of more advanced methods, all while keeping computational complexity low.

Methods

The core contribution is the Sliding Window Orthonormal PAST (SW-OPAST) algorithm. It builds upon the Sliding Window PAST (SW-PAST) algorithm by incorporating an orthonormalization step.

  • SW-PAST: This algorithm uses a sliding window to estimate the signal subspace. It's an iterative process that updates the subspace basis at each time step. The paper presents a slightly modified version of SW-PAST that performs a rank-two update at each time step.
  • SW-OPAST: This new algorithm introduces an orthonormalization step after the SW-PAST update. This ensures that the estimated subspace basis is always orthonormal. The key innovation lies in how this orthonormalization is integrated. Instead of directly orthonormalizing the primary subspace estimate (which can lead to instability in sliding window contexts), SW-OPAST uses a separate matrix variable to store the orthonormal basis. This separation allows the algorithm to benefit from the stability of the original SW-PAST while still achieving orthonormality.
  • Link to Natural Power (NP) Method: The paper establishes a connection between SW-OPAST and the Natural Power (NP) method. It shows that SW-OPAST can be viewed as a computationally efficient implementation of the NP method, inheriting its global convergence properties.

Datasets

The paper evaluates the performance of the proposed SW-OPAST algorithm using a synthetic dataset. This dataset consists of:

  • A sum of $r=4$ complex sinusoidal sources.
  • Complex white Gaussian noise, with a Signal-to-Noise Ratio (SNR) of 5.7 dB.
  • The frequencies of the sinusoids are designed to change abruptly at different time instances, simulating a "jump scenario." This scenario is used to test the algorithm's ability to track sudden changes in the signal.

The paper does not introduce new benchmark datasets but uses a well-defined synthetic signal to evaluate the tracking performance.

Key Insights and Ideas

  • Guaranteed Orthonormality at Each Step: The most significant insight is the development of an algorithm that guarantees the signal subspace basis is orthonormal at every iteration. This is crucial for applications that rely on orthonormal bases (e.g., MUSIC, minimum-norm estimators) and improves the robustness of the tracking.
  • Stability in Sliding Window Context: A key challenge in adapting orthonormalization techniques to sliding windows is maintaining stability. The paper's approach of using a separate variable for the orthonormal basis effectively circumvents the instability issues observed in previous attempts.
  • Efficient NP Method Implementation: SW-OPAST is shown to be a fast implementation of the Natural Power (NP) method. This means it inherits the desirable global convergence properties of NP methods while being computationally more efficient than existing NP implementations.
  • Faster Convergence than OPAST: The simulations demonstrate that SW-OPAST converges faster than the OPAST algorithm, particularly at the beginning of the signal and when tracking abrupt changes. This is attributed to the sliding window's responsiveness and the global convergence property inherited from the NP method.

Key Results

  • Tracking Performance: The SW-OPAST algorithm robustly tracks abrupt frequency variations in the test signal.
  • Convergence Speed: SW-OPAST shows faster convergence than SW-PAST at the signal's onset and offers a faster tracking response to sudden signal changes compared to OPAST.
  • Orthonormality Error: The orthonormality of the subspace basis estimates is measured by the error criterion $||W(t)^H W(t) - I||$. SW-OPAST and OPAST algorithms achieved maximum errors below -200 dB and -290 dB, respectively, significantly outperforming the standard PAST tracker (which reached -3.5 dB).
  • Computational Complexity: The algorithm achieves a linear complexity of $O(nr)$, making it computationally efficient.

Limitations and Future Work

  • Rank Deficiency: The paper notes that if the estimated subspace matrix $U(t)$ becomes rank deficient, the algorithm cannot be updated using the presented equations and must be re-initialized. While the authors state they did not encounter this issue with their test signals (even with noise), it remains a potential limitation in certain scenarios.
  • Future Work: The paper implicitly suggests that further exploration of the algorithm's performance in real-world scenarios and with different types of signals would be valuable. The successful demonstration of its capabilities in frequency estimation also opens doors for its application in other domains requiring subspace tracking.

Summary updated

Abstract

This paper introduces an orthonormal version of the sliding-window Projection Approximation Subspace Tracker (PAST). The new algorithm guarantees the orthonormality of the signal subspace basis at each iteration. Moreover, it has the same complexity as the original PAST algorithm, and like the more computationally demanding natural power (NP) method, it satisfies a global convergence property, and reaches an excellent tracking performance. 1.
BibTeX
@inproceedings{badeau2003sliding,
  author = {Roland Badeau and Karim Abed-Meraim and Gaël Richard and Bertrand David},
  title = {{Sliding window orthonormal PAST algorithm}},
  booktitle = {IEEE International Conference on Acoustics, Speech and Signal Processing},
  year = {2003},
  doi = {10.1109/icassp.2003.1199918},
}

Loading related content...

Figure