OPIT: A Simple but Effective Sparse Subspace Tracking Method

In this work, we propose a new provable effective method called OPIT (which stands for Online Power Iteration via Thresholding) for tracking the sparse principal subspace of data streams over time. Particularly, OPIT introduces a new adaptive variant of power iteration with space and computational complexity linear to the data dimension. In addition, a new column-based thresholding operator is developed to regularize the subspace sparsity. Utilizing both advantages of power iteration and thresholding operation, OPIT is capable of tracking the underlying subspace in both classical and high dimensional regimes.

Demo

Please run

• demo_effect_forgetting_factor.m: To illustrate the effect of the forgetting factor on the performance of OPIT
• demo_noise_effect.m: To illustrate the effect of noise on the performance of OPIT
• demo_nonstationary.m: To illustrate the performance of OPIT in nonstationary environments
• demo_low_dimension_comparison.m: To illustrate the performance of subspace tracking algorithms in the classical setting
• demo_high_dimension_comparison.m: To illustrate the performance of subspace tracking algorithms in high dimension

State-of-the-art algorithms for comparison

• LORAF: P. Strobach, “Low-rank adaptive filters”. IEEE Trans. Signal Process., 1996.
• OPAST: K. Abed-Meraim et al. “Fast orthonormal PAST algorithm”. IEEE Signal Processing Letters, 2000.
• FAPI: R. Badeau et al. “Fast approximated power iteration subspace tracking”. IEEE Trans. Signal Process., 2015.
• GFAPI: M. Arjomandi-Lari et al. “Generalized YAST algorithm for signal subspace tracking”. Signal Process., 2015.
• SSPCA: W. Yang and H. Xu, “Streaming sparse principal component analysis”. Proc. ICML, 2015.
• L1-PAST: X. Yang et al. “Fast STAP method based on PAST with sparse constraint for airborne phased array radar”. IEEE Trans. Signal Process., 2016.
• SSFAPI: N. Lassami et a. “Low cost sparse subspace tracking algorithms”. Signal Process., 2020.
• PETRELS-ADMM: L.T. Thanh et al. "Robust Subspace Tracking with Missing Data and Outliers: Novel Algorithm with Convergence Guarantee". IEEE Trans. Signal Process., 2021.

Some Experimental Results

• Effect of the sparsity level

  

• OPIT vs SOTA Algorithms in High Dimension

• Performance of SST algorithms with different data dimensions and sample sizes

Reference

This code is free and open source for research purposes. If you use this code, please acknowledge the following paper.

[1] L.T. Thanh, K. Abed-Meraim, N.L. Trung, & A. Hafiance. "Sparse Subspace Tracking in High Dimensions". Proc. 47th IEEE ICASSP, 2022.

[2] L.T. Thanh, K. Abed-Meraim, N. L. Trung, & A. Hafiane. "OPIT: A Simple and Effective Method for Sparse Subspace Tracking in High-dimension and Low-sample-size Context". IEEE Trans. Signal Process., 2024.