Robust Subspace Tracking Algorithms in Signal Processing: A Brief Survey

Nội dung text: Robust Subspace Tracking Algorithms in Signal Processing: A Brief Survey

1. 16 REV Journal on Electronics and Communications, Vol. 11, No. 1–2, January–June, 2021 Regular Article Robust Subspace Tracking Algorithms in Signal Processing: A Brief Survey Le Trung Thanh1,2, Nguyen Viet Dung1,3, Nguyen Linh Trung1, Karim Abed-Meraim2 1 AVITECH, VNU University of Engineering and Technology, Hanoi, Vietnam 2 PRISME Laboratory, University of Orlộans, Orlộans, France 3 National Institute of Advanced Technologies of Brittany, Brest, France Correspondence: Nguyen Linh Trung, linhtrung@vnu.edu.vn Communication: submitted 26 May 2021, revised 22 June 2021, accepted 22 June 2021 Online publication: 23 June 2021, Digital Object Identifier: 10.21553/rev-jec.270 The associate editor coordinating the review of this article and recommending it for publication was Prof. Vo Nguyen Quoc Bao. Abstract– Principal component analysis (PCA) and subspace estimation (SE) are popular data analysis tools and used in a wide range of applications. The main interest in PCA/SE is for dimensionality reduction and low-rank approximation purposes. The emergence of big data streams have led to several essential issues for performing PCA/SE. Among them are (i) the size of such data streams increases over time, (ii) the underlying models may be time-dependent, and (iii) problem of dealing with the uncertainty and incompleteness in data. A robust variant of PCA/SE for such data streams, namely robust online PCA or robust subspace tracking (RST), has been introduced as a good alternative. The main goal of this paper is to provide a brief survey on recent RST algorithms in signal processing. Particularly, we begin this survey by introducing the basic ideas of the RST problem. Then, different aspects of RST are reviewed with respect to different kinds of non-Gaussian noises and sparse constraints. Our own contributions on this topic are also highlighted. Keywords– Streaming PCA, subspace tracking, robust algorithm, imperfect data, sparse outlier, impulse noise, colored noise, sparse subspace. 1 Introduction The attractive point of ST resides on two aspects. First, in a similar manner to batch subspace meth- Principal component analysis (PCA) and subspace es- ods [3], both the main components and the disturbance timation (SE) are widely used as a fundamental step components of data observation can be exploited in for dimensionality reduction and analysis. Their main many different ways. In fact, the subspace is simple to purpose is to extract low-dimensional subspaces from understand (i.e., in a statistical sense) and implement, high-dimensional data while still keeping as much thus proving its efficiency in many practical applica- relevant information as possible. Consequently, PCA tions. Second, different from batch subspace methods, and SE have found success in a wide range of fields, ST has a better trade-off between the accuracy and the from finance to neuroscience, with the most successful computational complexity, thus making it suitable for applications in computer science. The main difference time-sensitivity and real-time applications. Due to its between them is that PCA emphasizes the use of practical use, we can find a wide range of applications eigenvectors rather than of subspace as in SE. PCA in diverse fields [3–5], for example, direction of arrival in a standard set-up can be implemented by using ei- (DoA) tracking in radar and sonar, data compression ther eigenvalue decomposition (EVD) or singular value and filtering, blind channel estimation and equaliza- decomposition (SVD) and is proved to be optimal in tion, and pattern recognition, to name a few. terms of the Frobenius-norm approximation error by However, it is well-known that PCA/SE is very the Eckart-Young theorem [1]. sensitive to data corruptions. This fact remains across Recent years have witnessed an increasing interest the above important PCA classes in general and ST in adaptive processing [2]. It is mainly due to the fact in particular. PCA dealing with impulsive noise and that online applications generate a huge amount of data outliers is referred to as robust PCA. In 2011, it was re- streams over time and such streams are often with visited in a seminal work of Candes et al [6]. This work high veracity and velocity. It is known that veracity has attracted many research studies and applications, requires robust algorithms for handling imperfect data with over 4000 citations as of now. PCA for streaming while velocity demands (near) real-time processing. Ac- data with impulsive noise and outliers is referred to as cordingly, important classes of PCA, such as subspace robust subspace tracking (RST). It is considered much tracking (ST) also called PCA for streaming data or more difficult than the original ST [7]. streaming PCA or dynamic PCA, and ST with missing ST algorithms have been developed for over three data have drawn much research attention recently in decades [3, 4]. It has been around ten years since signal processing and modern data analysis. Delma’s survey [3] and we thus believe it is not only 1859-378X–2021-1203 â 2021 REV
2. L. T. Thanh et al.: Robust Subspace Tracking Algorithms in Signal Processing: A Brief Survey 17 Table I Surveys on PCA/SE and Subspace Tracking Paper Topic & scope Main contribution A survey on numerical methods for tracking the low-rank approximation of [4, 1990] Principal ST covariance matrices slowly varying with time. [3, 2010] Principal and minor ST A comprehensive survey on classical ST algorithms. [8, 2016] Principal component analysis A survey on adaptations of PCA for modern datasets and applications. A high-dimensional analysis framework for the state-of-the-art ST algorithms [9, 2018] Principal ST from incomplete observations. A survey on both classical and recent ST algorithms able to handle missing data [5, 2018] ST and streaming PCA and their performance guarantee. A survey on robust PCA, RST, and robust subspace recovery in the presence [10, 2018] Robust subspace learning of sparse outliers. [11, 2018] Robust PCA A survey on statistic and dynamic robust PCA algorithms. [12, 2018] Principal component analysis A survey on distributed PCA algorithms. A survey on works on robust subspace recovery when measurements are [13, 2018] Robust subspace recovery corrupted by sparse outliers. [14, 2018] Sparse PCA A survey on recent theoretical developments of sparse PCA. A survey on RST algorithms in the presence of different kinds of corruptions Ours RST (e.g. outliers, missing data, impulsive, and colored noise) and sparse subspace. important but the right time to do an up-to-date survey The main contributions of the above-mentioned pa- in order to highlight some aspects that were not men- pers are summarized in Table I. tioned in [3] as well as recent advances on this topic. 1.2 Main Contributions 1.1 Related Work To the best of our knowledge, we are not aware of any work that reviews the RST problem in the presence Due to the importance of ST, there have been a num- of different kinds of non-Gaussian noise. Although the ber of published surveys in the literature. One of the three surveys [10, 11, 13] reviewed some classes of first and earliest surveys on principal subspace tracking RST algorithms, they only discussed on sparse outliers. algorithms was carried on by Comon and Golub in [4]. Methods for other non-Gaussian noises (e.g., impulsive The survey focuses on methods with high and mod- noise and colored noise) have not been reviewed yet. erate computational complexity for tracking the low- Moreover, no survey exists on the problem of sparse rank approximation of covariance matrices which may ST in the literature. This observation motivates us to be slowly varying with time. In [3], Delmas provided a carry out a survey on the topic. comprehensive overview on developments of classical The main goal of this survey is to fill the gap in the ST algorithms with low (linear) complexity. literature addressing the following three kinds of non- Recently, different adaptations of PCA for modern Gaussian noises (including outliers, impulsive noise, datasets and applications were reviewed in [8]. How- and colored noise) and sparse constraints. Our contri- ever, PCA for streaming data or ST was not addressed. butions are as follows. First, in the context of missing The problem of tracking the underlying subspace of data and outliers, we review four main approaches for data from incomplete observations was discussed in [5] dealing with them. They are Grassmannian, recursive and [9]. Particularly, the former concerned method- least-squares (RLS), recursive projected compressive ological classes of ST algorithms that are able to deal sensing (ReProCS), and adaptive projected subgradient with missing data while the latter presented a high- method (APSM). Second, when the measurements are dimensional framework for analyzing their conver- corrupted by impulsive noise, we show that most of gence behavior. The survey in [10] carried out reviews state-of-the-art RST algorithms are based on improving on robust PCA, RST, and robust subspace recovery in the well-known PAST algorithm which belongs to the the presence of sparse outliers. Two similar surveys class of RLS methods. Two other appealing approaches to [10] have also been conducted in [11] and [13] including weighted RLS and adaptive Kalman filtering which respectively review (i) static and dynamic RPCA are also reviewed. Third, we outline two main classes algorithms, and (ii) the entire body of works on ro- of RST algorithms that are able to deal with colored bust sparse recovery. In the literature, there exist two noise: instrumental variable-based and oblique projec- others surveys on two adaptations of PCA which are tions. Finally, a short review on sparse ST algorithms distributed PCA [12] and sparse PCA [14]. is presented.
3. 18 REV Journal on Electronics and Communications, Vol. 11, No. 1–2, January–June, 2021 The structure of our review is as follows. Section 2 a point in the Grassmannian. Therefore, the Grassman- states the problem of RST. In Section 3, we provide nian approach offers several advantages such as a lower the state-of-the-art algorithms for the RST problem in number of parameters to optimize and limited memory the presence of missing data and outliers. The next usage and the resulting RST algorithms are often effi- two sections, 4 and 5, present RST algorithms that cient and scalable to high dimensional data [37]. are able to handle impulsive noise and colored noise, State-of-the-art RST algorithms include GRASTA [15], respectively. Section 6 provides a short review on sparse GOSUS [16], pROST [17, 18], and RoIGA [33, 34]. ST. Finally, Section 7 concludes the paper. In [15], He et al. proposed an efficient RST algorithm called Grassmannian robust adaptive ST (GRASTA) 2 Robust Subspace Tracking:Problem which is a robust version of GROUSE in [38]. GRASTA first uses an `1-norm cost function to reduce the effect Formulation of sparse outliers and then performs the incremental gradient on the Grassmann manifold of the subspace At each time t, we suppose to observe a signal x ∈ Rn t U. In [16], Xu et al. introduced an effective algorithm satisfying namely GOSUS for tracking subspace with structured- xt = Pt`t + Ptvt, (1) sparsity. GOSUS also incorporates an adaptive step- size for the incremental gradient on the manifold. ∈ Rnìn where Pt is an observation mask matrix indi- The effectiveness of GOSUS was demonstrated via ( ) = cating the i-th entry of xt is observed (i.e., Pt i, i 1) the real application of video background subtraction ( ) = ∈ Rnì1 or not (i.e., Pt i, i 0), vt is the (non-Gaussian) and multiple face tracking. In [17, 18], Hage et al. ` noise vector and t is the true signal living in a fixed proposed a method, namely pPOST that combines or slowly time-varying low-dimensional subspace of the advantages of Grassmannian optimization with a Rn ` = . More concretely, t Utwt in which wt is a non-convex sparsity measure. Instead of using the ` - ∈ Rnìr  1 weight vector and Ut (r n) is a basis norm regularization, pPOST uses the penalty with non- ∆
   matrix with d(Ut, Ut−1) = sin θ(Ut, Ut−1)  1 where convex `0-surrogates allows reconstruction even in the θ(Ut, Ut−1) denotes the largest principal angle between case when `1-based methods fail. Another algorithm Ut and Ut−1. dubbed robust intrinsic Grassmann average (RoIGA) The RST problem can be stated as follows: Given a was proposed by Rudrasis et al. in [33, 34]. RoIGA is a streaming set of observed signals {xt}t≥1 in (1), we wish to geometric approach to computing principal linear sub- estimate a rank-r matrix Ut such that it can cover the span spaces in finite and infinite dimensional reproducing of the complete-data noiseless signal `t. kernel Hilbert spaces. Among them, RoIGA is shown as In this paper, we consider the RST problem in the one of the fastest RST algorithms for handling missing presence of different kinds of the non-Gaussian noise data corrupted by outliers. vt: sparse outliers, impulse noise, and colored noise. Also, we review sparse ST algorithms under the con- 3.2 Recursive Least-Squares based Algorithms straint that the basis matrix Ut is sparse. Another line of the RST research is based on recur- 3 Robust Subspace Tracking in the sive least-squares (RLS) methods where the underly- ing subspace is recursively updated by minimizing a Presence of Missing Data &Outliers (weighted) least-squares objective function containing squared residuals and a penalty accounting for outliers. In the literature, there have been several studies on An efficient RLS-based algorithm is parallel estimation ST in the presence of outliers and missing data. The and tracking by recursive least squares (PETRELS) [39] proposed RST algorithms can be categorized into four which can be considered as an extension of the projec- main classes: (i) Grassmannian, (ii) recursive east- tion approximation ST (PAST) algorithm [40] in order Squares (RLS), (iii) recursive projected compressive to handle missing data. sensing (ReProCS), and (iv) adaptive projected subgra- Inspired by PETRELS, several robust variants have dient method (APSM). We summarize all the RST algo- been proposed to deal with outliers the same line rithms robust to outliers and missing data in Table II. such as [20, 27, 35, 36]. Robust online subspace es- timation and tracking (ROSETA) in [20] applies an 3.1 Grassmannian Algorithms adaptive step size at the stage of subspace estima- Many of RST algorithms are based on the Grassman- tion to enhance the convergence rate. Meanwhile the nian approach in which the ST procedure can be cast main idea of PETRELS-CFAR algorithm [27] is to han- into an optimization process on a Grassmann manifold. dle “outliers-removed” data (i.e., outliers are first re- More concretely, Grassman manifold is a space that moved before performing ST) using a Constant False parameterizes all r-dimensional linear subspaces of the Alarm Rate (CFAR) detector. Adopting the approach N-dimensional vector space. The underlying subspace of PETRELS-CFAR, but aiming to improve RST per- can be derived from averaging the column span of formance, we proposed an efficient algorithm called the (fully or partially) observed signals on the Grass- PETRELS-ADMM which is able to remove outliers mannian. Interestingly, each observed signal `t spans more effectively in [35, 36]. It includes two main stages: a one-dimensional subspace which can be described as outlier rejection and subspace estimation and tracking.
4. L. T. Thanh et al.: Robust Subspace Tracking Algorithms in Signal Processing: A Brief Survey 19 Table II RST Algorithms in the Presence of Both Missing Data and Sparse Outliers Missing Prior Convergence Computational Algorithm Method Outliers Initialization Data Information Guarantee Complexity GRASTA ` -norm + ADMM + 1    random  O(nr + r3) (2012 [15]) Grassmannian GOSUS ` -norm + ADMM + 2    random  - (2014 [16]) Grassmannian pROST ` -surrogate + Grassmannian 0    random  - (2014 [17, 18]) Conjugate Gradient MRMD Online max-norm    random  - (2014 [19]) regularization ROSETA ` -norm + ADMM + 1,2    random  O(nr2) (2015 [20]) RLS Roubst STAPSM APSM + CoSAMP∗    random  O(knr2) (2015 [21, 22]) ReProCS-cPCA ReProCS    batch  O(nr log2(n) log(1/e)) (2016 [23]) OTNNR Truncated nuclear-norm    random  - (2016 [24]) regularization OLP-RPCA `p-norm + singular    random  O(nr + r3) (2017 [25]) value thresholding L1-PCA ` -norm + 1    batch  O(nrω2)‡ (2018 [26]) Bit-flipping PETRELS-CFAR Robust statistic + RLS    batch  O(nr2 + nω)†† (2018 [27]) s-ReProCS ReProCS    batch  O(nr log(n) log(1/e)) (2019 [28]) NORST-miss ReProCS    batch  O(nr log(1/e)) (2019 [29]) L1-IRW `1-norm +    batch  O(k(nωr3 p + 2rnr2))† (2019 [30]) Bit-flipping OSTP Schatten quasi-norm +    random  O(nr2) (2019 [31]) Block-proximal gradient NORST ReProCS    batch  O(nr log(1/e)) (2020 [32]) RoIGA IGA# + Grassmannian    random  - (2020 [33, 34]) PETRELS-ADMM ` -norm + ADMM + 1    random  O(nr2) (2021 [35, 36]) RLS ∗ CoSAMP: Compressed Sampling Orthogonal Matching Pursuit # IGA: Intrinsic Grassmann Average  e : a desired subspace recovery accuracy ‡ ω: length of sliding window †† ω: length of training window † ω: length of sliding window; k: number of iterations; p: number of bit flips Outliers living in the measurement data are detected ReProCS-type algorithms use the piecewise constant and removed by a ADMM solver in an effective way. subspace change model described previously and start An improved PETRELS was then introduced to update with a “good” estimate of the initial subspace. At each the underlying subspace. In practice, the convergence time, they first solve a projected compressive sensing rate of RST-type algorithms is often faster than that problem to derive the sparse outliers, e.g., using `1 of Grassmmannian-based algorithms in slowly time- minimization followed by thresholding-based support varying environments. estimation. After that, the subspace direction change is then estimated by using projection-SVD [28]. 3.3 Recursive Projected Compressive Sensing based ReProCS provides not only a memory-efficient and Algorithms highly robust solution, but also a precise subspace Recursive projected compressive sensing (ReProCS)- estimation compared to the state-of-the-arts. However, based algorithms [23, 28, 29, 32] are also capable of ReProCS-type algorithms often require strong assump- tracking subspace in the presence of outliers and miss- tions on subspace changes, outlier magnitudes, and ing data. accurate initialization.
5. 20 REV Journal on Electronics and Communications, Vol. 11, No. 1–2, January–June, 2021 Table III RST Algorithms in the Presence of Impulsive Noise Burst SIRV α-stable Convergence Computational Algorithm Method Initialization noise noise noise Guarantee Complexity RPAST PAST + M-estimation  -  random  O(nr + r2) (2006 [41]) MCC-PAST Maximum correntropy  -  random  O(nr + r2) (2014 [42]) criterion (MCC) + PAST BNC-PAST Bounded nonlinear  -  random  O(nr + r2) (2014 [43]) covariance (BNC) + PAST robust KFVM Adaptive Kalman filter + O( ` + ` 2)+  - - random  nr r (2020 [44]) M-estimation O(`2r + `3) ROBUSTA Weighted RLS +    random  O(nr + r2) (2018 [27]) Mahalanobis distance `: length of the sliding window −: unknown or undetermined 3.4 Adaptive Projected Subgradient Method based 4.1 Robust Variants of PAST Algorithms To take into account impulsive noise, some methods Adaptive projected subgradient method (APSM) can proposed in the literature have mainly been based on provide a robust solution to the presence of missing robust statistics so far. Among them, some studies data and outliers [21, 22]. Main advantages of APSM have proposed robust variants of PAST to deal with are that convex constraints can be readily incorporated impulsive noise. In [41], a robust PAST (RPAST) was and it can be used as an alternative to constructing proposed. The algorithm first detects the occurrence the cost function from the sum of square errors like of the impulsive noise based on a threshold, and then RLS methods. The key idea of APSM stems from that eliminates undesirable effects by discarding contami- unknown parameters of regression models can be es- nated observations. The threshold is determined based timated from seeking a point in the intersection of all on an empirical function of noise variance with the the sets defined by measurements. In the context of ST, assumption that error vectors follow a Gaussian dis- based on the latest observed signals, a cost function tribution corrupted by additive impulsive noise. is properly chosen at each time instant which scores Zhang et al. introduced another PAST’s variant called a zero loss. The next task is to reach the intersection MCC-PAST via the maximum correntropy criterion point. To deal with sparse outliers, APSM-type algo- (MCC) in [42, 51, 52]. MCC-PAST exploits a correntropy rithms detect the time instances at which the observed as a new statistic, which can quantify both the time signals are corrupted by outliers via using sparsity- structures and statistics of two random processes, to aware greedy techniques (e.g. compressed sampling deal with impulsive noise. Accordingly, the maximum orthogonal matching pursuit as used in [22]) and then correntropy criterion (MCC) is applied as a substitute reject them. for the mean square error criterion in the objective function of PAST. Based on the RLS technique, the 3.5 Other Algorithms MCC-PAST algorithm was then developed. To extend Some other RST algorithms are able to track the the tracking capability of the MCC-PAS, a variable underlying subspace over time from measurements forgetting factor (FF) technique was also employed in corrupted by sparse outliers such as MRMD [19], the recursion process. In parallel, Shengyang et al. de- OTNNR [24], L1-PCA [26], L1-IRW [30], OLP- veloped another robust variant of PAST, namely BNC- RPCA [25], and OSTP [31]. Most of them use a `p- PAST, to track the underlying subspace via a differ- regularization (0 ≤ p ≤ 1) to discard the effect of out- ent criterion [43]. The authors defined a new concept liers. However, they are not designed for missing data. namely bounded non-linear covariance (BNC) to handle relative problems (including ST) in the presence of 4 Robust Subspace Tracking in the non-Gaussian noise with a heavy-tailed distribution. In particular, bounded nonlinear maps were employed Presence of Impulsive Noise to discard the effect of impulsive noise. Accordingly, a new robust PAST algorithm based on BNC was derived. By “impulsive”, we mean it can be burst noise [45, 46], spherically invariant random variable (SIRV) noise [47, 48], or alpha-stable noise [49, 50]. We note that even 4.2 Adaptive Kalman Filtering though these algorithms were described to reduce the Another good approach capable of handling im- effect of impulsive noise in general, most simulation pulsive noise is based on adaptive Kalaman filtering. results were shown for burst noise only. RST algorithms In [44], Liao et al. proposed a RST algorithm based that are robust to impulsive noise are summarized in on an adaptive Kalman filter with variable number of Table III. measurements (KFVM). The main idea of using the
6. L. T. Thanh et al.: Robust Subspace Tracking Algorithms in Signal Processing: A Brief Survey 21 Table IV RST Algorithms in the Presence of Colored Noise Convergence Computational Method Approach Initialization Guarantee Complexity IV-PAST IV + PAST random  3n` + O(nr) (2012 [53]) IVPM IV + propagator-based random  n(` + 2r) (2014 [54]) LOFF-VR-SREIV-PAST IV + PAST + 6nr + 5r2 + 4n random  (2020 [55]) adaptive forgetting factor +14r + O(nr) obPAST Oblique projection + random  3nr2 + 3nr + O(r3) (2005 [56]) PAST obYAST Oblique projection + random  5nr + O(r2 + n) + O(r3) (2012 [57]) YAST `: the dimension of IV vector. KFVM is to deal with the tracking of fast-varying the computational complexity of IV-based algorithms is subspace [58]. More concretely, when the underlying often higher than the original ones due to the selection subspace varies quickly, a small number of past obser- of the IV vector size. Specifically, in [53], two direct vations are exploited in the recursion and vice versa. To extensions of the PAST algorithms, named IV-PAST and handle the impulsive noise, the M-estimate technique extended IV-PAST, were proposed. It is shown that their is incorporated into the KFVNM algorithm. The com- performance is enhanced, comparing to the original plexity of the proposed KFVM-based algorithm is much ones. With the aim to improve further performance higher than the PAST-based algorithms especially when in subspace-based system identification applications, the number of observations used for subspace update several algorithms in conjunction with using IV were is large. addressed in [54]. The key idea is to adapt the propa- gator approach by exploiting the relationship between array signal processing and subspace identification. 4.3 Weighted Recursive Least-Squares Method Very recently, Chan et al. in [55] proposed a new Recently, based on robust statistics but different from robust variant of PAST capable of handing linear mod- the common two-step scheme mentioned above, we els with complex coefficients, multiple outputs, and proposed in [27] an RST algorithm with linear com- colored noises. In the proposed method, the authors putational complexity based on a weighted RLS ap- used a new adaptive forgetting factor and imposed a proach, namely ROBUSTA. On the theoretical aspect, `2-norm regularization into the objective function of we provided a converge analysis of ROBUSTA in the PAST. In particular, the adaptive forgetting factor was presence of SIRV noise. Interestingly, we showed that obtained at each time instant by minimizing the mean- it also corresponded to adaptive robust covariance esti- square deviation of the estimator from an extended mation. ROBUSTA outperformed many state-of-the-art IV linear model and IV-PAST. The additional `2-norm algorithms for burst noise, SIRV noise, and alpha-stable regularized term on the weight vectors is aimed to re- noise. Also, it can be easily adapted, in conjunction with duce the error variance and prevent the ill-conditioned pre-processing steps, to handle alpha-stable noise. computation at low SNR levels. Generally, if low com- putational complexity is concerned, IV-based methods 5 Robust Subspace Tracking in the require a IV vector uncorrelated with the noise which is not always met in practice. Presence of Colored Noise 5.2 Oblique Projection based Algorithms In the literature, RST algorithms that are robust to colored noise can be categorized into two groups: Another direction, which can avoid the above draw- (i) instrumental variable and (ii) oblique projection. We back, is based on oblique projection onto the subspace summarize these algorithms in Table IV. manifold, such as [56, 57]. It is due to the fact that the noise vector may lie in a low dimension subspace instead of being treated as full rank in the observation 5.1 Instrumental Variable based Algorithms space. Naturally, oblique projections arise in the solu- For colored noise, one of the main directions is tion to recover the signal. Accordingly, Chen et al. pro- to use the instrumental variable (IV) which allows posed a variant of PAST named oblique PAST (obPAST) avoiding biased estimate. An appealing benefit of this to track the signal subspace in [56]. In the same line, approach is easy to adapt derivation from classical based on the well-known YAST algorithm [65], Florian ST algorithms. While having improved performance, et al. introduced the new obYAST algorithm in [57].
7. 22 REV Journal on Electronics and Communications, Vol. 11, No. 1–2, January–June, 2021 Table V Sparse ST Algorithms Prior Convergence Computational Algorithm Method Initialization Information Guarantee Complexity OIST Oja method +  random  O(nr) (2016 [59]) soft-thresholding Streaming SPCA Row truncation +  batch  O(nr min(r, s log n)) (2015 [60]) QR decomposition ` -PAST PAST method + ` -norm 1 1  random  3nr2 + 3nr + O(r2) (2016 [61]) sample matrix inverse OVBSL Bayesian inference +  random  O(nr2 + nr) (2017 [62]) `2/`1-norm promotion 2-step approach + OPAST + nr2 + nr + O(r3) SS/DS-OPAST   3 3 / random 2 (2017 [63]) `1-norm approximation 3nr + O(nr ) SS/GSS-FAPI 2-step approach + FAPI + 2nr2 + 4nr + O(r2)/  random  (2020 [64]) Givens rotations 4nr + 4ns + O(r2) Both obPAST and obYAST minimized a new exponen- resulting truncated covariance matrix was realized to tial least-squares cost function where the orthogonal update the principal subspace. The authors also proved projection in the residual error term is replaced with that the proposed algorithm is consistent in the high- an oblique one. Experiment results indicate that this dimension regime. modification can facilitate the tracking ability of PAST In [61], Xiaopeng et al. introduced a new robust and YAST in the presence of colored noise. Table IV variant of PAST called `1-PAST. Specifically, the authors reports further information about these RST algorithms, modified the cost function of PAST by adding a `1-norm e.g. convergence and complexity. constraint imposed on the subspace matrix to control its sparsity. Accordingly, a new RLS algorithm like 6 Sparse Subspace Tracking PAST was derived to minimize the proposed objective function in an efficient way. The `1-PAST is robust and Recently, sparse subspace estimation and tracking have stable even when the number of observations is small. been attracted more attention from the signal process- In [62], Giampouras et al. developed a novel ro- ing community due to the fact that many modern bust sparse ST method namely OVBSL in the lens of datasets admit sparse representation has huge potential Bayesian inference. To deal with the sparsity constraint capabilities for analyzing them [66]. Although several on the subspace matrix, OVBSL utilized the group- algorithms have been introduced for sparse subspace sparsity inducing the convex `2/`1-norm. Since it be- estimation in the batch setting (see [67–69] for ex- longs to the family of Bayesian methods, no fine-tuning amples), there exist only a few studies on sparse ST parameter is required and the proposed algorithm is algorithms so far. fully automated. In [59], Chuang and Yue proposed an adaptive al- In this topic, we also proposed several two-stage gorithm called OIST (which stands for Oja’s algorithm approach based algorithms for sparse ST in [63, 64, 70]. with Iterative Soft Thresholding) for online sparse PCA. The main steps of the two-stage approach is as follows. The authors investigated a rank-one spiked model in a We first utilize a well-known ST algorithm from the high-dimension regime and indicated that the estimate literature (e.g. PAST or FAPI) to extract an orthonormal of the eigenvector from the sample covariance matrix basis of the underlying subspace. Then, we estimate a is inconsistent. To alleviate it, they introduced an ex- sparse weight matrix based on some criteria on sparsity tended version of Oja’s algorithm followed by a soft- such that it can span the same subspace. For example, thresholding step to promote sparsity on the estimate. in [63], two new algorithms SS-OPAST and DS-OPAST The asymptotic convergence, steady state, and phase were designed for sparse system matrix and sparse transition of OIST were also derived to understand source signals respectively. We particularly exploited its behavior in a high-dimension regime when the the natural gradient to find the sparsest matrix from the dimension is much larger than the number of obser- estimated orthonormal matrix by OPAST. In [64, 70], vations. However, OIST is designed for only rank-one we used FAPI in the first stage and then derived SS- subspaces, i.e. lines. In parallel, a novel online sparse FAPI, orthogonal SS-FAPI, and GSS-FAPI algorithms. PCA algorithm able to deal with rank-k spiked models Specifically, the sparsity criterion considered there is (k ≥ 1) was proposed via row truncation technique differentiable and smoother than the previous one in [60]. More concretely, a simple `2-norm based row in [63]. Accordingly, it facilitates the optimization by truncation operator was introduced to zero out rows employing the Newton method and Taylor expansions. whose leverage score is below a predefined threshold. To sum up, a performance comparison among these At each time instant, the QR decomposition of the sparse ST algorithms is given in Table V.
8. L. T. Thanh et al.: Robust Subspace Tracking Algorithms in Signal Processing: A Brief Survey 23 7 Conclusions space recovery,” Proceedings of the IEEE, vol. 106, no. 8, pp. 1380–1410, Aug 2018. ST has shown an increased interest in signal processing [14] H. Zou and L. Xue, “A selective overview of sparse with the aim of analyzing real-time big data problems principal component analysis,” Proceedings of the IEEE, vol. 106, no. 8, pp. 1311–1320, 2018. and its improvement is in parallel to recent advances [15] J. He, L. Balzano, and A. Szlam, “Incremental gradient in optimization. In this paper, we provided a brief on the Grassmannian for online foreground and back- survey on adaptive algorithms for RST which were ground separation in subsampled video,” in IEEE Conf. mostly developed over the last decade. We highlighted Comput. Vis.Pattern Recogn. IEEE, 2012, pp. 1568–1575. three classes of RST algorithms for dealing with non- [16] J. Xu, V. K. Ithapu, L. Mukherjee, J. M. Rehg, and V. Singh, “GOSUS: Grassmannian online subspace up- Gaussian noises including sparse outliers, impulsive dates with structured-sparsity,” in IEEE Int. Conf. Com- noise, and colored noise. The last decade has also put. Vis., Dec 2013, pp. 3376–3383. witnessed the widespread of high-dimensional data [17] F. Seidel, C. Hage, and M. Kleinsteuber, “pROST: analysis in which sparse representation-based methods a smoothed `p-norm robust online subspace tracking are successfully applied to many signal processing method for background subtraction in video,” Mach. Vis. Appl., vol. 25, no. 5, pp. 1227–1240, 2014. applications. Accordingly, sparse ST algorithms are also [18] C. Hage and M. Kleinsteuber, “Robust PCA and sub- reviewed in our survey. space tracking from incomplete observations using `0- surrogates,” Computational Statistics, vol. 29, no. 3-4, pp. 467–487, 2014. Acknowledgments [19] J. Shen, H. Xu, and P. Li, “Online optimization for max- norm regularization,” in Advances in Neural Information This work was supported by the National Foundation Processing Systems, 2014, pp. 1718–1726. for Science and Technology Development of Vietnam [20] H. Mansour and X. Jiang, “A robust online subspace estimation and tracking algorithm,” in IEEE Int. Conf. under Grant No. 102.04-2019.14. Acoust. Speech Signal Processing. IEEE, 2015, pp. 4065– 4069. [21] S. Chouvardas, Y. Kopsinis, and S. Theodoridis, “An References adaptive projected subgradient based algorithm for ro- IEEE Int. Conf. Acoust. Speech [1] I. Jolliffe, Principal Component Analysis, ser. Springer Se- bust subspace tracking,” in Signal Processing ries in Statistics. Springer-Verlag New York, 2002. , 2014, pp. 5497–5501. [2] T. Kolajo, O. Daramola, and A. Adebiyi, “Big data stream [22] ——, “Robust subspace tracking with missing entries: IEEE Transactions on Signal analysis: A systematic literature review,” Journal Big The set-theoretic approach,” Processing Data, vol. 6, no. 1, pp. 1–30, 2019. , vol. 63, no. 19, pp. 5060–5070, 2015. [3] J. P. Delmas, “Subspace tracking for signal processing,” [23] J. Zhan, B. Lois, H. Guo, and N. Vaswani, “Online (and Adaptive Signal Processing: Next Generation Solutions, pp. offline) robust PCA: Novel algorithms and performance Artif. Intell. Stat. 211–270, 2010. guarantees,” in , 2016, pp. 1488–1496. [4] P. Comon and G. H. Golub, “Tracking a few extreme [24] B. Hong, L. Wei, Y. Hu, D. Cai, and X. He, “Online ro- singular values and vectors in signal processing,” Pro- bust principal component analysis via truncated nuclear Neurocomputing ceedings of the IEEE, vol. 78, no. 8, pp. 1327–1343, 1990. norm regularization,” , vol. 175, pp. 216– [5] L. Balzano, Y. Chi, and Y. M. Lu, “Streaming PCA and 222, 2016. Proceedings of [25] K. G. Quach, C. N. Duong, K. Luu, and T. D. Bui, “Non- subspace tracking: The missing data case,” ` the IEEE, vol. 106, no. 8, pp. 1293–1310, Aug 2018. convex online robust PCA: Enhance sparsity via p-norm Computer Vision and Image Understanding [6] E. J. Candốs, X. Li, Y. Ma, and J. Wright, “Robust prin- minimization,” , cipal component analysis?” Journal of the ACM, vol. 58, vol. 158, pp. 126–140, 2017. no. 3, p. 11, 2011. [26] P. P. Markopoulos, M. Dhanaraj, and A. Savakis, “Adap- [7] N. Vaswani, Y. Chi, and T. Bouwmans, “Rethinking PCA tive l1-norm principal-component analysis with online IEEE Journal on Selected Topics Signal for modern data sets: Theory, algorithms, and applica- outlier rejection,” Processing tions,” Proceedings of the IEEE, vol. 106, no. 8, pp. 1274– , vol. 12, no. 6, pp. 1131–1143, 2018. 1276, Aug 2018. [27] N. Linh-Trung, V. D. Nguyen, M. Thameri, T. Minh- [8] I. T. Jolliffe and J. Cadima, “Principal component anal- Chinh, and K. Abed-Meraim, “Low-complexity adaptive IEEE Journal on ysis: a review and recent developments,” Philosophical algorithms for robust subspace tracking,” Selected Topics Signal Processing Transactions of the Royal Society A, vol. 374, no. 2065, p. , vol. 12, no. 6, pp. 1197– 20150202, 2016. 1212, 2018. [9] C. Wang, Y. C. Eldar, and Y. M. Lu, “Subspace estima- [28] P. Narayanamurthy and N. Vaswani, “Provable dynamic IEEE Transac- tion from incomplete observations: A high-dimensional robust PCA or robust subspace tracking,” tions on Information Theory analysis,” IEEE Journal on Selected Topics Signal Processing, , vol. 65, no. 3, pp. 1547–1577, vol. 12, no. 6, pp. 1240–1252, 2018. March 2019. [10] N. Vaswani, T. Bouwmans, S. Javed, and P. Narayana- [29] P. Narayanamurthy, V. Daneshpajooh, and N. Vaswani, murthy, “Robust subspace learning: Robust PCA, robust “Provable subspace tracking from missing data and ma- IEEE Transactions on Signal Processing subspace tracking, and robust subspace recovery,” IEEE trix completion,” , Signal Processing Magazine, vol. 35, no. 4, pp. 32–55, July pp. 4245–4260, 2019. 2018. [30] Y. Liu, K. Tountas, D. A. Pados, S. N. Batalama, and [11] N. Vaswani and P. Narayanamurthy, “Static and dynamic M. J. Medley, “L1-subspace tracking for streaming data,” Pattern Recognition robust PCA and matrix completion: A review,” Proceed- , vol. 97, p. 106992, 2020. ings of the IEEE, vol. 106, no. 8, pp. 1359–1379, Aug 2018. [31] X. Jia, X. Feng, W. Wang, H. Huang, and C. Xu, “Online [12] S. X. Wu, H. Wai, L. Li, and A. Scaglione, “A review schatten quasi-norm minimization for robust principal Inf. Sci. of distributed algorithms for principal component anal- component analysis,” , vol. 476, pp. 83–94, 2019. ysis,” Proceedings of the IEEE, vol. 106, no. 8, pp. 1321– [32] P. Narayanamurthy and N. Vaswani, “Fast robust sub- 1340, Aug 2018. space tracking via PCA in sparse data-dependent noise,” [13] G. Lerman and T. Maunu, “An overview of robust sub- IEEE Journal on Selected Areas in Information Theory, vol. 1, no. 3, pp. 723–744, 2020.
9. 24 REV Journal on Electronics and Communications, Vol. 11, No. 1–2, January–June, 2021 [33] R. Chakraborty, S. Hauberg, and B. C. Vemuri, “Intrin- algorithm based on maximum correntropy criterion for sic Grassmann averages for online linear and robust impulsive noise environments,” Acta Electonica Sinica, subspace learning,” in IEEE Conf. Comput. Vis. Pattern vol. 43, no. 3, p. 483, 2015. Recogn., 2017, pp. 6196–6204. [52] J. Zhang and T. Qiu, “A novel tracking method for fast [34] R. Chakraborty, L. Yang, S. Hauberg, and B. Vemuri, varying subspaces in impulsive noise environments,” in “Intrinsic Grassmann averages for online linear, robust 2016 Int. Conf. Signal Processing Commun. Syst., 2016, pp. and nonlinear subspace learning,” IEEE Transactions on 1–7. Pattern Analysis and Machine Intelligence, pp. 1–1, 2020. [53] T. Gustafsson, “Instrumental variable subspace tracking [35] L. T. Thanh, N. V. Dung, N. L. Trung, and K. Abed using projection approximation,” IEEE Transactions on Meraim, “Robust subspace tracking with missing data Signal Processing, vol. 46, no. 3, pp. 669–681, March 1998. and outliers via ADMM,” in European Signal Processing [54] G. Mercốre, L. Bako, and S. Lecœuche, “Propagator- Conf., 2019, pp. 1–5. based methods for recursive subspace model identifica- [36] ——, “Robust subspace tracking with missing data and tion,” Signal Processing, vol. 88, no. 3, pp. 468–491, 2008. outliers: Novel algorithm with convergence guarantee,” [55] S. Chan, H. Tan, and J. Lin, “A new variable forgetting IEEE Transactions on Signal Processing, vol. 69, pp. 2070– factor and variable regularized square root extended in- 2085, 2021. strumental variable PAST algorithm with applications,” [37] S. Hauberg, A. Feragen, R. Enficiaud, and M. J. Black, IEEE Trans. Aerosp. Electron. Syst., vol. 56, no. 3, pp. 1886– “Scalable robust principal component analysis using 1902, 2020. Grassmann averages,” IEEE Transactions on Pattern Anal- [56] Minhua Chen and Zuoying Wang, “Subspace tracking in ysis and Machine Intelligence, vol. 38, no. 11, pp. 2298– colored noise based on oblique projection,” in IEEE Int. 2311, 2016. Conf. Acoust. Speech Signal Processing, vol. 3, 2006, pp. [38] L. Balzano, R. Nowak, and B. Recht, “Online identifica- 556–559. tion and tracking of subspaces from highly incomplete [57] F. Yger, M. Berar, G. Gasso, and A. Rakotomamonjy, information,” in Annual Allerton Conf. Commun. Control “Oblique principal subspace tracking on manifold,” in Comput. IEEE, 2010, pp. 704–711. IEEE Int. Conf. Acoust. Speech Signal Processing, 2012, pp. [39] Y. Chi, Y. C. Eldar, and R. Calderbank, “Petrels: Paral- 2429–2432. lel subspace estimation and tracking by recursive least [58] S. Chan, Z. Zhang, and Y. Zhou, “A new adaptive squares from partial observations,” IEEE Transactions on kalman filter-based subspace tracking algorithm and Signal Processing, vol. 61, no. 23, pp. 5947–5959, Dec 2013. its application to DOA estimation,” in IEEE Int. Symp. [40] B. Yang, “Projection approximation subspace tracking,” Circuits Systt., 2006, pp. 4 pp.–132. IEEE Transactions on Signal Processing, vol. 43, no. 1, pp. [59] Chuang Wang and Y. M. Lu, “Online learning for sparse 95–107, 1995. PCA in high dimensions: Exact dynamics and phase [41] Shing-Chow Chan, Yu Wen, and Ka-Leung Ho, “A ro- transitions,” in IEEE Inf. Theory Works., 2016, pp. 186– bust past algorithm for subspace tracking in impulsive 190. noise,” IEEE Transactions on Signal Processing, vol. 54, [60] W. Yang and H. Xu, “Streaming sparse principal compo- no. 1, pp. 105–116, 2006. nent analysis,” in Int. Conf. Mach. Learn., 2015, pp. 494– [42] J. Zhang and T.-s. Qiu, “A robust correntropy based 503. subspace tracking algorithm in impulsive noise environ- [61] X. Yang, Y. Sun, T. Zeng, T. Long, and T. K. Sarkar, “Fast ments,” Digital Signal Processing, vol. 62, pp. 168–175, STAP method based on PAST with sparse constraint for 2017. airborne phased array radar,” IEEE Transactions on Signal [43] S. Luan, T. Qiu, L. Yu, J. Zhang, A. Song, and Y. Zhu, Processing, vol. 64, no. 17, pp. 4550–4561, 2016. “BNC-based projection approximation subspace tracking [62] P. V. Giampouras, A. A. Rontogiannis, K. E. Themelis, under impulsive noise,” IET Radar Sonar Navig., vol. 11, and K. D. Koutroumbas, “Online sparse and low-rank no. 7, pp. 1055–1061, 2017. subspace learning from incomplete data: A Bayesian [44] B. Liao, Z. Zhang, and S.-C. Chan, “A new robust view,” Signal Processing, vol. 137, pp. 199–212, 2017. Kalman filter-based subspace tracking algorithm in an [63] N. Lassami, K. Abed-Meraim, and A. Aùssa-El-Bey, “Low impulsive noise environment,” IEEE Trans. Circuits Syst. cost subspace tracking algorithms for sparse systems,” in II Express Briefs, vol. 57, no. 9, pp. 740–744, 2010. European Signal Processing Conf. IEEE, 2017, pp. 1400– [45] K. L. Blackard, T. S. Rappaport, and C. W. Bostian, 1404. “Measurements and models of radio frequency impul- [64] N. Lassami, A. Aùssa-El-Bey, and K. Abed-Meraim, “Low sive noise for indoor wireless communications,” IEEE J. cost sparse subspace tracking algorithms,” Signal Process- Sel. Areas Commun., vol. 11, no. 7, pp. 991–1001, 1993. ing, vol. 173, p. 107522, 2020. [46] W. J. Ebel and W. H. Tranter, “The performance of [65] R. Badeau, G. Richard, and B. David, “Fast and stable Reed-solomon codes on a bursty-noise channel,” IEEE YAST algorithm for principal and minor subspace track- Transactions on Communications, vol. 43, no. 2/3/4, pp. ing,” IEEE Transactions on Signal Processing, vol. 56, no. 8, 298–306, 1995. pp. 3437–3446, Aug 2008. [47] Kung Yao, “A representation theorem and its applica- [66] Z. Zhang, Y. Xu, J. Yang, X. Li, and D. Zhang, “A survey tions to spherically-invariant random processes,” IEEE of sparse representation: Algorithms and applications,” Transactions on Information Theory, vol. 19, no. 5, pp. 600– IEEE Access, vol. 3, pp. 490–530, 2015. 608, 1973. [67] T. T. Cai, Z. Ma, Y. Wu et al., “Sparse PCA: Optimal rates [48] E. Ollila, D. E. Tyler, V. Koivunen, and H. V. Poor, and adaptive estimation,” The Annals of Statistics, vol. 41, “Complex elliptically symmetric distributions: Survey, no. 6, pp. 3074–3110, 2013. new results and applications,” IEEE Transactions on Signal [68] D. Papailiopoulos, A. Dimakis, and S. Korokythakis, Processing, vol. 60, no. 11, pp. 5597–5625, 2012. “Sparse PCA through low-rank approximations,” in Int. [49] C. L. Nikias and M. Shao, Signal processing with alpha- Conf. Mach. Learn., 2013, pp. 747–755. stable distributions and applications. Wiley-Interscience, [69] V. Q. Vu, J. Cho, J. Lei, and K. Rohe, “Fantope projec- 1995. tion and selection: A near-optimal convex relaxation of [50] P. G. Georgiou, P. Tsakalides, and C. Kyriakakis, “Alpha- sparse PCA,” in Advances in Neural Information Processing stable modeling of noise and robust time-delay estima- Systems, 2013, pp. 2670–2678. tion in the presence of impulsive noise,” IEEE Transac- [70] N. Lassami, A. Aùssa-El-Bey, and K. Abed-Meraim, “Fast tions on Multimedia, vol. 1, no. 3, pp. 291–301, 1999. sparse subspace tracking algorithm based on shear and [51] J. Zhang, Q. Tian-shuang, and L. Sen, “A robust PAST givens rotations,” in Asilomar Conf. Signals Syst. Comput., 2019, pp. 1667–1671.
10. L. T. Thanh et al.: Robust Subspace Tracking Algorithms in Signal Processing: A Brief Survey 25 Le Trung Thanh received B.Sc. and M.Sc. Nguyen Linh Trung obtained his B.Eng. and degrees in Electronics and Telecommunica- Ph.D. degrees, both in Electrical Engineering, tions from VNU University of Engineering from Queensland University of Technology, and Technology, Vietnam National University, Brisbane, Australia, in 1998 and 2005. Since Hanoi (VNU) in 2016 and 2018 respectively. 2006, he has been on the faculty of VNU He is now pursuing his Ph.D. study at the University of Engineering and Technology, University of Orleans, France. His research Vietnam National University, Hanoi (VNU), interests include signal processing, subspace where he is currently an associate professor of tracking, tensor analysis, and system identifi- electronic engineering in the Faculty of Elec- cation. tronics and Telecommunications and director of the Advanced Institute of Engineering and Technology. He is interested in signal processing methods, including time-frequency signal analysis, blind processing, adaptive filtering, compressive sampling, tensor-based signal analysis, graph signal processing, and apply them to wireless communication, networking, and biomedical engineering. Karim Abed-Meraim was born in 1967. He received the State Engineering Degree Nguyen Viet Dung received the B.Sc. in from Ecole Polytechnique, Palaiseau, France, Electronics and Telecommunication Engineer- in 1990, the State Engineering Degree from ing from VNU University of Engineering Ecole Nationale Supộrieure des Tộlộcommu- and Technology, Vietnam National University, nications (ENST), Paris, France, in 1992, the Hanoi (VNU) in 2009, M.Sc. in Networks M.Sc. degree from Paris XI University, Orsay, and Telecommunications from ẫcole Normale France, in 1992 and the Ph.D. degree from the Supộrieure (ENS) de Cachan, Universitộ Paris ENST in 1995 (in the field of Signal Process- XI (now, University of Paris-Saclay, France), ing and communications). From 1995 to 1998, in 2012, and Ph.D. in Signal Processing from he took a position as a research staff at the the University of Orleans (France) in 2016. He Electrical Engineering Department of the University of Melbourne did a postdoc at CentraleSupộlec, University where he worked on several research project related to "Blind System of Paris-Saclay from 2017 to 2018. From 2019 to now, he is a research Identification for Wireless Communications", "Blind Source Sepa- engineer at Lab-STICC, UMR 6285 CNRS ENSTA Bretagne, Brest, ration", and "Array Processing for Communications", respectively. France. His research interests include channel modelling in array From 1998 to 2012 he has been Assistant then Associate Professor at signal processing, adaptive matrix and tensor analysis, blind source the Signal and Image Processing Department of Telecom-ParisTech. separation, and statistical performance analysis. His research interests are in signal processing for communications, adaptive filtering and tracking, array processing and statistical per- formance analysis. In September 2012 he joined the University of Orleans (PRISME Lab.) as a full Professor. He is the author of over 450 scientific publications including book chapters, international journal and conference papers and patents. Dr. Abed-Meraim is an IEEE Fellow, an IEEE SAM-TC member and a past associate editor for the IEEE Transactions on Signal Processing.