Robust Streaming PCA
Authors: Daniel Bienstock
Minchan Jeong
Apurv Shukla
Se-Young Yun
Venue: NeurIPS 2022 Accept (2022)
Keywords: Statistical Modeling
Machine Learning

Abstract: We consider streaming principal component analysis when the stochastic data-generating model is subject to perturbations. While existing models assume a fixed covariance, we adopt a robust perspective where the covariance matrix belongs to a temporal uncertainty set. Under this setting, we provide fundamental limits on any algorithm recovering principal components. We analyze the convergence of the noisy power method and Oja’s algorithm, both studied for the stationary data generating model, and argue that the noisy power method is rate-optimal in our setting. Finally, we demonstrate the validity of our analysis through numerical experiments. 

Robust Streaming PCA
Daniel Bienstock
Minchan Jeong
Apury Shukla IEOR Department Columbia University
Se- Ye-Young Yun Graduate School of AI KAIST
IEOR Department
Graduate School of AI KAIST
Columbia University
{dano, as5197) edu, {mcjeong, (aaaeeyyun))kkiistt. ac kr
Abstract
We consider streaming principal component analysis when the stochastic data- generating model is subject to perturbations. While existing models assume a fixed covariance, adopt robust perspective where the covariance matrix belongs to a temporal uncertainty set. Under this setting, we provide fundamental limits convergence of any algorithm recovering principal components. We analyze the convergence of the noisy power method and Oja's algorithm, both studied for the stationary data generating model, and argue that the noisy power method is rate-optimal in our setting. Finally, we demonstrate the validity of our analysis through numerical experiments on synthetic and real-world dataset.
Introduction
Principal component analysis (PCA) is of the most extensively studied methods for obtaining the low-dimensional representation of observed data [22]. However, classical algorithms for PCA store all the observations and use cubic-time complexity. thereby imposing prohibitively large computation- time and space requirements.
Recently, several works on PCA have focused on the design and analysis of streaming algorithms with near-optimal memory and storage complexity [25, 29, 40, 43]. These algorithms assume that all the observations belong the same low-dimensional space. However, this situation is unlikely when the unknown/unexplored alterations corrupt system's 's observations. For instance, is well known that typical data attacks power grids can significantly change the estimated covariance matrix of the data observed from sensors [9, 10, 23]. Similarly, PCA can be used to explain stock returns in terms of macroeconomic factors [27]. and product pricing taking into account cross- cross-product elasticity and demands [45]. In all these scenarios, the underlying tata-generating model changes every instant, and the decisions are based on identifying the changed model.
Current work considers perturbations of the data lying in fixed now-dimensional space [49]. They determine the worst-case position of the adversarial data point to incur the maximum error in the subspace estimated through PCA and measure the distance between the two subspaces using the notion of the principal angle between them. Another line of work considers PCA through the lens of stochastic optimization [5, 42, 51, 52]. Our work differs from these approaches since we assume that the data-genert gett--enerating model changes at every time instant. Further, propose near-optimal algorithms for recovering principal components under this framework.
We assume system relies on the time-series of p-dimensional vectors sampled from time-varying model. The available observations are the vectors (x+) The noisy observation x, E TRP a vector lying in the column space of an unobserved full-rank matrix A, [Rpxk, Precisely, from the standard spiked covariance model [35], we consider the dime-dependent environment:
x; NoOpx1 A,A o
(I)
The authors are ordered alphabetically.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

where A, can vary with time. The parameter k < p is the desired number of principal components. Assuming A, belongs to a temporal uncertainty set (defined in the equation (2)). our goal is to recover the top-k principal components of the terminal subspace Ar. In financial applications, our model captures the market evolution in terms of the changing Ar with the ultimate goal of explaining the market conditions for an appropriately chosen T.
Previous works on the stationary environment assume A. = for all and have focused on computing a basis for the column space of the matrix A using streaming algorithms [21, 29, 33, 36, 38, 43]. The accurate reconstruction of the principal components for the standard streaming PCA problem depends on the magnitude of observation noise o, the dimension of observations p. the number of principal components k of the matrix A, and the spectral gap å between k-th and k 1-th spectrums. singular value of AA" In a marked departure from previous work, we study the case when the column space of A varies across time. This paper explores these avenues and proposes tractable analysis framework for the streaming PCA problem, robust to perturbations in the data-generating model. Our contributions can be summarized as follows:
1. (Lower Bound;
Section 4) Our first contribution is establishing fundamental lower bound for estimating the principal components when the covariance matrix belongs to a temporal uncertainty set Tu(6, r). In Theorem I, we derive the minimax bounds of the expected error for recovering the top singular vectors for any streaming algorithm. Because the underlying distribution can vary, observations from the far past become less important and the estimation of principal components associated with Ar should be determined by subset of samples. Simultaneously. it becomes imperative to find the block size B that can be used to recover the principal components. This is in sharp contrast to the standard spiked covariance model. We show that:
For TT the minimax estimation error decreases as Opp2/27-1/2).
On the other hand, for T' 22(1)2/3), the error stagnates 0(p2/811/3) and does not decrease upon collecting more observations'.
2. (Algorithm Analysis; Section 5) We then analyze two algorithms to recover the principal compo- nents extensively used in the standard streaming PCA setting; the noisy power method [29] and Oja's algorithm [48]. These algorithms represent two very different design principles for com- puting principal components from data in streaming fashion, processing data in blocks vis-à-vis single observations. We determine the optimal choice for critical parameters: the block size in the noisy power method on Lemma and the learning rate in Oja's algorithm on Lemma 2. Next, we leverage these results to obtain an upper bound on the convergence error for these algorithms in Theorem 2 and 3, respectively. From these results, we have:
The block size B for the noisy power method and inverse of the learning rate, Ç-1 for Oja's algorithm, plays a similar role even in the non-stationary environment. In either case, the optimal parameters scale with ((T where the perturbation budget.
The derived upper bound on the estimation error for the noisy power method matches the minimax error in terms of p, and I and becomes rate-optimal if it satisfies the mild conditions.
Notation. We fix notation throughout the main body of the paper. Matrices are denoted by bold uppercase letters (e.g. M) and vectors are denoted by bold lowercase letters (e.g. x). For M R M, denote the ith column of M. M., denote the submatrix consists with ith jth column of M and M., be the -elemet of M. II denote matrix 2-norm equivalently operator norm for matrices and standard 2-norm for vectors. We use St, (R²) for the class of orthogonal matrices in RRxk,, b(M) is the orthogonal matrix where the columns form basis for ran(M). s; (MM represents the ith largest singular value of the matrix.
The singular value decomposition of M is defined as SVD(M) = UDVT, where U E St. (R?). V e Sty (R+), and D E gpxk is diagonal matrix whose ith diagonal element equals s; (M). Therefore, we assume without loss of generality that the singular values and respective singular vectors are ordered from largest to smallest. We denote by M1 the orthogonal projection onto the orthogonal complement of the ran(M). Therefore, if rk(M) = and SVD(M) UDVT M given by M = I U,. UT i:r. Moreover, when rk(M) = rk(M) and SVD(M) = ÜDVT, the
For precise explanation forl' and Tu(ō, please refer the Section 3.

---

distance between ran and rM) is defined by:
d(ran(MM), ran = ((M) T 6(M)6(M || = U U - U Ü
We denote d(ran ran (M) by d(M, M) whenever clear from the context.
The letter A stands for abbreviation of sequence of matrices (At) We write X~A when each element X, sequence X' = (x:)²= are drawn from (0, A,A, + d²Ipxp). We denote the expectation of f2²) over x; (o A,A, + IxIpp) as Ex~ [f].
We denote O θ as the O, θ notation with ignore the multiplicative dependency of log(p(?)) or smaller.
2 Related Work
Principal component analysis (PCA) has been extensively studied across operations research, com- puter science, and other communities. We highlight how our work differs from existing literature.
Robust PCA. Robust PCA deals with the problem of retrieving the principal components robust to the presence of outliers in the data. The cornerstone work in this direction is the principal component pursuit framework wherein they assume that the matrix of observations M can be decomposed in terms of low-rank matrix and sparse matrix (with entries of arbitrarily large magnitude) S [15].
Several works consider the robust PCA problem and propose algorithms in the offline, batch, and online settings [17, 24, 26, 46]. Our work differs from this line of literature in two aspects: assump- tions about the data-generating model and convex optimization techniques. First, our data generation model is unrelated those considered the robust PCA literature. Further, rich theories from convex optimization can be used in the PCA framework to design efficient algorithms, but our problem is not amenable to such techniques.
Streaming PCA. Streaming algorithms for PCA have heen proposed, among other works on PCA [2, 29, 34, 43, 60). Algorithms analyzed in this work, such as the noisy power method [29] and Oja's algorithm [48], are iterative methods for estimating the principal components. These iterative schemes are instances of stochastic ixproximation-bassee solutions for the optimization formulation of the PCA problem [5]. The stochastic approximation is a root-finding framework extensively used for stochastic optimization [11, 37J. Oja's 's algorithm, originally proposed by [48], was the first such scheme.
This framework is also used to amalyze gradient-type and proximal-type incremental methods akin to algorithms for convex optimization. Stochastic gradient descent-based algorithms for the streaming PCA problem, where single observation is used every point in time update the principal components' estimate, have been extensively studied. Along this line, (30) propose GRASTA, an incremental online gradient method for learning GROUSE, based on the idea of gradient updates over the Grassmannian manifold. These and other related works consider Oja's algorithm for the standard streaming PCA problem [1, 16, 31, 31, 53, 59, 62]. However, all these works are based on completely different modeling assumption than this paper and do not provide theoretical guarantees for our setting.
different subspaces. Similarly, [6] proposes
Streaming and robust PCA algorithms are used in the presence of outliers or data with a lot of missing entries [18, 55). From this literature, the closest our work is the work robust subspace tracking [2, 30, 60). However, the robustness considered there is against erasures or sparse outliers. While these algorithms provide theoretical guarantees in that setting, those guarantees cannot be extended to our model. Considerations of erasures and outliers under the model proposed in this paper are beyond the scope of this work and remain an interesting future direction.
3 Mathematical Framework
Observations from the standard spiked covariance model belong to a fixed k-dimensional column space A E RR. Previous work has focused on reconstructing this space from the observed time series. Under our framework, we assume that the sequence of observations (xx){= follows the time-dependent spiked covariance model (I). We consider the problem of computing top-k singular
3

---

vectors of Ar. We formulate this model by addressing minimax optimization as robust optimization problem.
When the adversary is allowed to select a completely arbitrary sequence of matrices (A+) is impossible accurately recover the column space of Ar. Instead, we define temporal uncertainty sets to restrict the power of the adversary.
Definition 1.
Let I, 8 We only allow the sequence of matrices (A.) that lie in an temporal uncertainty set Tu(ó, I') defined as:
(u r) = (A.) sk(A,A 26
A,
(2)
We constrain the difference between any two consecutive covariance matrices of the underlying process by r. The assumption ss (A,A?) is crucial for establishing bounds of estimation error. It is also justified in any setting where the underlying phenomenology guarantees covariance of rank k; the stated lower bound excludes pathological cases of near-rank k or smaller.
Having described the constraints on the perturbation power, we present the algorithms and the performance metric of interest. In particular, consider (i) streaming algorithms, i.c., make single pass through the time series in chronological order; only the previous samples are stored at any point the past. These characteristics model the behavior of an algorithm that receives data in real-time and only stores samples in limited memory. Among those streaming algorithms, we consider (ii) the algorithms whose output is a set of k orthonormal vectors in R". Let denote by & the family of algorithms just described. The output of algorithm & & for given observations X = (x,)²=1 sampled using model (2) is a set of orthonormal vectors, which we denote by 6x. We will also view Φx as matrix in Rpxk or the subspace generated by Φxx
Following definition 2 illustrates how treat the lower bound and when we call the algorithm optimal. We note that this formulation has been widely studied [14, 57, 58].
Definition 2. Let A (At) E Tu(ó, I'), and Φ E 4.
1. The estimation error of d given X' ~ A is the distance between the space spanned by ox and the column space of Ar (d[ran( Ar), ox)). ) The metric can be easily extended to the cumulative error. Refer Appendix A for the discussion.
2. R is the maximum expected estimation eπror of ó under A over all A E Tu(6, 1').
R
sup Ex~A (al-A(d((an(AA)) (T), Φr), AETu(
3. R* is the minimax estimation error defined as the minimum of the largest expected estima- tion error incurred by 4b:
R" = R inf sup à AETu(G,))
Ex~ ((((aa((AT,,x)))))
&
4. An algorithm of the problem parameters T, 8, p. k, and r.
rate-optimal if Rd < C.RR. where constant C is independent
In this work, we establish the minimax estimation error RD and propose rate-optimal sublinear-time, single-pass algorithms for robust streaming PCA.
4 Minimax Lower Bound
When = (A+) belongs to the temporal uncertainty set Tu(6, (Definition 1), an algorithm designed to recover the principal components of Ar from the observations cannot guarantee zero estimation error. Our first goal is to obtain the minimax lower bound on the estimation error in the problem parameters T, 8, p, k and r.
In order to establish the lower bound, we leverage the fundamental limit of hypothesis tests [57]. The crux of the proof lies in constructing the set of worst-case hypotheses and establishing lower bound on the probability of error in distinguishing between these hypotheses using observed data. The complete proof is provided in Appendix D.

---

Theorem 1 (Lower Bound), Assume 8 >> 2 0 and p > 2k + 1. For any algorithm & E L there exists a sequence A E Tu(6, r) such that Ex~A [d(ran(Ar)))) 9x)] has lower bound with order:
min { 1,
1o² +
1/2
T
1/3
oo² + 6) 1/3 }
82
3
82
(3)
By taking inf we get the same lower bound for R
For the standard streaming PCA problem (Theorem with the case of r = 0), the fundamental limit is (((a/))(p(o> + 0)/T)//3), which has the expected ((1/vT) dependence [14, 58). On the other hand, in the presence of perturbations (T) the lower bound exhibits phase transition phenomenon, with the first term representing the effect of model ambiguity. To this end, define the critical time Te as
r
2/3
p + +6) 1/3
To
(4)
8
For T- OT)), the lower bound decreases with the rate of 1/vT However, when T= the first term dominates the second term, and R. becomes independent of the number of observations T. In this regime, the error stagnates ((TT5))1/3 (po + 5)/8²) 1/3). suggests, the information quickly becomes stale in a dynamic environment.
) Therefore,
intuition
Theorem 2 and 3 will prove that the noisy power method and Oja's algorithm attain near-optimal bound on the convergence guarantee. Theorem 2 guarantees that if $1 (A,A, = ((8), the upper bound for estimation error the noisy power method is of the following order:
NPM = Ō (()))
1/3 (po + ko) + =00 1/3
(5)
8²
That is. if po² dominates kō, the noisy power method becomes rate- under the controlled uncertainty with I') This regime is the case of noisy practical situations, with o² K 6.
Convergence Analysis
In this section, we analyze two algorithms for the robust streaming PCA problem. generic template for algorithms,, ø E & of interest to us is as follows: (i) á is initialized with a random matrix with orthonormal columns E Be*k; (ii) a running estimate of the principal components is maintained as the columns of U: (iii) observations are projected onto the column space of Ú to update this estimate.
We consider two algorithms: a robust version of the noisy power method (Algorithm 1) and Oja's algorithm (Algorithm 2). The critical difference between the noisy power method and Oja's algorithm the data used estimate the principal components. In the noisy power method, the estimates are updated after a batch of observations, whereas in Oja's algorithm, the estimates are updated after scaling every observation with the learning rate. Therefore, the parameters determining the performance of these algorithms are the batch size B for the robust power method and the learning rate ( for Oja's 's algorithm.
The analysis of these algorithms cannot be readily established with existing techniques when the covariance matrix belongs to temporal uncertainty set since they rely on showing that the estimates improve every iteration. Further, applying many concentration results requires random matrices to be bounded, which is not the case when the observations are sampled from (1). Therefore, in order to simplify the analysis of both algorithms, we introduce Assumption 1, adapted from [34].
Assumption 1. Let (A,) TT For ő > 8 and M, V for / E [7] satisfy the following:
consider the observations X
1. [| A + ooIpx while ||A,A|I| 5
2. ||x,X]" - (A,A + pxx))l < M a.s. and
3. [E [XXxT] - (A,A, + + I S..
5

---

When the observations follow model (1), we condition our analysis on the bigh-probability event é. Definition 3. Let SVD(A, + Ixpp)) U,D,U, and x, = z4. where 2, ~N pxp) We define the event C as:
{ Zzz E
- - log(2)??)) v log (2p
vt E [T]]]
=
The observations from model (1) satisfy Assumption with M = + (1 ( V = 2M + o²) with probability P(e] 2 1 L/T. Although after conditioning E|x,x; / |@| &
Ixxps we can use all the results Section 5.1 and 5.2 with multiplicative logarithmic + A,
factor. Please refer to Appendix B for the details.
5.1
Noisy Power Method
Algorithm Noisy Power Method with block size B [29]
1: Input: Stream of vectors: (x=) block size: B, dimensions: k
2: Sample each element of Ú(0) in 10,
3: for f 1: I, = [T/B] do
4: Y(E) 0 E Roxk
5: fort (e 1)B + 1: fB do
6: Y(E) Y(() + x Ú(E
7: end for
8:
Ú(() + Gram-Schmidt (())
9: end for
Output: (L)
The noisy power method an iterative algorithm for computing the top-k principal components of a matrix. Starting from the random matrix Ú(0) in R the algorithm runs for L iterations, each processing B samples. By repeating this procedure, expect the algorithm reconstruct the covariance matrix if the observations are derived from the fixed distribution.
When observations are drawn from model (1) under Assumption 1, the later observation can be sampled from distributions with shifted covariance. Unlike the standard case, for any algorithm @ E p the presence of perturbation prevents the convergence of the columns of Ú()) to the singular vectors of the final covariance matrix U()). The main difficulty here is that the columns of Ú()) do not converge towards a fixed set of vectors but keep tracking the time varying principal components. Recall that our ultimate objective is to recover the principal components associated with the terminal observation. Hence, we decompose the covariance matrix terms of the last observation and the remaining samples. For f-th block, we denote the covariance matrix for BB-th observation as M(() and have:
tB
1
Σ
x = E|xinx|a]+ + = A LB + +
(6)
B
(2-1)B+1
M(E)
Due to perturbations in the robust model, E({) is a non-zero mean random variable. Therefore, we first decompose E() in terms of the contribution due to inherent noise and the perturbations the robust model allows. Then, in Lemma 1, we decompose the error |[{{)]] with respect to the block size B and the allowed perturbations I' in the robust model. We provided complete proof in Appendix E.
Lemma 1 (Spectral norm of noise). Assume that the observations (xe)T= generated according to the Assumption With probability greater than 1 1/T, the matrices {()) the equation (6) are bounded by:
1+3/2
V Poog(22) (2g())))))
BT
max [[E(0)]
ISESL
3
B
2
when the block size larger than M² log(2pT))/V.
Lemma highlights the effect of allowing perturbations in the data generation model. From classical results in statistics, our intuition tells us that the effect of noise washes out as the block size increases, ie.. the error decays with the finveree square root' of the block size. Hence, barring memory and

---

data issues, larger block size is better when I = O. In contrast, covariance perturbations add errors proportional to the block size. Consequently, we have a trade-off between two terms in this case, and an optimal block size exists depending on the r.
We establish the convergence guarantee of the robust power method in Theorem 2. In the proof of Theorem 2 (Appendix F), we bound the distance, d d(U()), Ú(L) between the output of Algorithm 1, (L) and k-orthonormal vectors spanning the column space of Ar, (L). We identify the optimal block size B, the unique parameter for the noisy power method, and establish an upper bound on the estimation error of the noisy power method.
Theorem 2 (Robust power method). Assume that 5 2 0.710² and (Vlgg()))( When the observations (x, satisfies the assumption 1, for B = ([011/1og(2213)) /2/3) we have:
d(ran(Ar), NPMx) =0 (OTlog((pP +0.7T/B
(8)
6
with probability 1 1 12/TT 2(p--+1) -
When r = 1//00////////// / (V we have that (VT log (2g())7)))1/3 =0(() Therefore, the condi- tion r in Theorem 2 necessary avoid trivial upper bound @(1). This condition encompasses several applications of interest alluded to earlier. For example, in the financial applications alluded to earlier, individual market changes of interest happen on millisecond time scale. It is of significant interest to terminally detect incremental market changes. Our results hold on to the large value of cumulative changes and allow to study them. They further imply that the noisy power method is rate-optimal for non-trivial values of I' When the observations follow model (I), under the event Es. Theorem shows that the robust power method can achieve an estimation error of:
((T)
1/3 (poo + k0) + +6) 1/3
-
RNPM RNPM= =
82
if = -[maxxT(xxxx 8 (1oo2) r ((c((p-k41) + +e
and ē = O(8).
Then it becomes order-wise identical to the fundamental limit established in Theorem I when po² dominates kō. The first condition on T illustrates when past observations become less critical. The probability for the upper bound on the noisy power method [29] with random initialization should not be small to construct expectation bounds from the high probability bound. We address this regime by condition on H, which is coarse due to exponential terms and (po?)-1-
Establishing bounds on the estimation error when the underlying singular vectors change is intricate since the subspace which consecutive observations belong potentially different. Conventional proofs that analyze noisy power methods or Oja's 's algorithm show that under variety of assumptions at every iteration É, the distance between the estimated and true subspace, di (E), (()) decreases. For instance, the proof in [29] requires (() O(Vk/p), which does not hold under our O(
model since [f) M( (((-1))l I| is, in general, greater than / Vk/p. Similarly, the concentration approach in [33] can be used only when the covariance matrix is time-invariant. We briefly describe
our proof technique to establish Theorem 2, deferring details to Appendix F. Let M( denotes
the product I (M(2) + E()). Then, the output of the algorithm Ú1+ is an orthonormal basis of (1 which estimates the first i principal components U1:k of the M(L). To address this, we construct sequences of k and (p k) dimeeniionl subspaces of R" from observations EB (( 1/ denoted by (N(() JE=1 1 E ( and {w(0) E (tR( respectively, such that for all iterations e:
and ((0)))))00)))))))))))))) <1, 3. ((),,()), w(++1), d(Ux+1,p() N(+)) = (()
1. (aN(MM())E(()))N S. raan(N(
S Can (a((w(+))),
2. [(M(()+ + E(()))
The initial random matrix Úz (0) consists of both (1) and W()) with high probability. From the first two properties, at every iteration É, the projection of Ú 1) in ((() is amplified more than
7

---

that on O and thus (L) becomes very close to W(.) after sufficiently large L. From the last property, we can conclude that W(4) is close to UI++(L) where the distance between W and 11: L) proportional to [[E(L]]]. Combining these ideas with Lemma establishes the results.
5.2
Oja's Algorithm
Algorithm 2 Oja's Algorithm with learning rate Ç [48]
1: Input: Stream of vectors: (xx (xx)(=1 learning rate: Ç, and dimensions: p,
2: Sample each element of (0) in 10,,
3: for f.- = 1 ' do
4: ((t) +- Gram-Schmidt((pxx
(xxx, (t( 1))
5: end for
6: Output: (T)
We now establish the convergence guarantee for Oja's Algorithm (Algorithm 2) when observations follow the equation (I), Unlike the noisy power method, Oja's Algorithm multiplicative in its construction of the estimated subspace. We extend the existing analysis for Oja's 's algorithm [3, 33, 34] by considering a virtual block with B = B = ( observations. Building upon the analysis framework for the noisy power method and intuition from binomial approximation (1 + (x) = (1 + x) we establish the convergence guarantees for Oja's is's algorithm. Like the previous section, decompose the block with target M()) and error matrix (E) as:
II (Lxx (
II (Ixx + (((x)nx))) E()) Moja(() + ô+o E'()). (10) 1m(e-1)8+1
(8- 1)-41
where E' is scaled error matrix. In Lemma 2. we provide bound for scaled error matrix with respect to the learning parameter Ç. or the virtual block size B5- = ={-1 similar to Lemma 1. The proof is provided in Appendix G.
Lemma 2 (Spectral norm of noise, Oja's algorithm case). Assume that the observations (xx !T generated according to the Assumption With probability greater than L/T, , the matrices El(() on the equation (10) are bounded by:
22 log(pT2)
B 2
max ISPSI.
(1E1
+ +((I))
(11)
Be
when the virtual block size B₃ 5-1 is larger than 2M log(p(T
The difference in parameter M, rather than V. as in the case of Lemma arises due to the use of a different concentration inequality. The estimator of the noisy power method averages the outer product of vectors (equation (10)), making it straightforward to use Bernstein's 's inequality. On the other hand, Oja's algorithm averages the product of random matrices rather than the sum of random matrices. Therefore, we introduce the multiplicative concentration inequality [32], which requires the (probabilistic) norm bound for matrices. Combining multiplicative concentration inequalities with Lemma and the techniques developed for the noisy power method, we obtain convergence guarantee for Oja's algorithm Theorem 3. The complete proof is provided in Appendix H.
Theorem 3 (Oja's algorithm). Assume that ò 2 0.71 and I = O(8' /( (()3(-)))) M2 log(pT)))). When the observations {x satisfies the assumption 1, for (-1 = O(M2/3 1og(pT2)) /2/33 we have:
((ran(Ar), Ojax) - (MPTlog(pT
+ 0.75T)
(12)
5
with probability 1 2/T - 0(p-k+1) (l(p)
Unlike the noisy power method, the upper bound in Theorem 3 is (p2/3) rather than the optimal- dependence of (3) from Theorem It is unclear whether the upper bound can be improved. Sharpening our analysis with two-phase strategy [33, 39] (wherein the first phase identifies good initial point and the second phase establishes convergence given an initial point) might be an excellent direction for future investigation.
8

---

Numerical Results
Key observations from Theorem and 3 on each algorithm illustrate; (i) the existence of the optimal block size B and the learning rate to obtain the minimum recovery error, and (ii) 3- dependencies of that optimal and 1/ç. In order to verify the established results for both algorithms, this section provides the performance of algorithms for various environments. We synthesized the A (A,) and sample X' (x))== from A. We generate (A,) E R as the product of three matrices, U, (R²), D, E (; diagonal), and V, E St, (R*). To obtain the matrix of the next step, we rotate the first matrix as U, = - R, (R, E sO())). The vectors x, are sampled from the model (I). More details for experimental setup are described in Appendix I.
Noisy Power Method
Oja's Algorithm
Optimal Learning Parameter
0.6
T-0e-5
T-0m-5
r=le-$
r=le-5
Noisy power mothod Oja's algorithm
T=
T=
d(Uia. (n
0.4
T=
T=5e-5
2000 Gee 800
0.2
90
10"
10
10
10-1
10
10-1
10
F=12-04
1==5-05
1=
Block Size B
Learning Rate 5
1-
(a) Distance between true column space of Ar(; U2:k) (b) Empirical optimal block size and leaming rate Ç and estimated space at 7c; Ú1 as varies. as varies.
Figure 1: Numerical results with synthesized streams of vectors. We used the setting (a, 8, k)) (0.15, 1.0, 100, 5).
Our first observation in Figure 1a is that convergence error decreases the block size increases without any covariance perturbation (T= This behavior is expected since increasing the number of past information results better accuracy guarantees for the recovered space in the absence of covariance shift. However, if the covariance perturbation exists (I' >>>>> 0), the optimal learning parameter exists, and we have the smaller optimal block size with stronger perturbation. This phenomenon is also expected since an increase in the adversarial budget implies that the past information becomes less relevant. Our observations also corroborate our theoretical results in Theorem 1.
In Figure lb, we focus on the optimal value of the block size and the inverse of the learning rate 1/C and its variation with the perturbation budget Т. We plot the empirically optimal learning rate for the case of the noisy power method and Oja's algorithm with F-2/3, We observe that the optimal block size and the inverse learning rate are proportional to 2-2/3, This experimental dependency of 2-2/3 verifies the theoretically prescribed results in Theorem 2 and 3.
6.1 Experiments on Stock Price Dataset
We provide the real-world benchmark using the S&P500 stock market dataset [44] in Kaggle to test our findings in the non-stationary environment. Refer the Appendix for the non-stationarity of environments and further experimental details that do not appear in the main paper.
The stream of vectors consisted of 133(= p) companies' normalized daily returns. Since each company in S&P500 has a different time horizon of available information, considered 133 companies with the cost information from Mar. 18, 1980, to Jul.22, 2022 (T'= = 10677). Then we calculated the 'daily return,' which is the difference of adjusted close cost between two days; normalized by the adjusted close cost of the day. The stream of vectors from the environment can be seen as sampled from vare-ng distributions with I 0.17.
The objective to predict the principal components of the covariance matrix of daily returns as in [4, 54, 61]. We tested the noisy power method and Oja's algorithm on the preprocessed stream. For the target space Ar, we used the k-dimensional subspace consisting of top-k singular vectors of covariance estimator calculated with the final 500 samples (k= (c=,,...,5),

---

Estimating S&P500 Daily Return Covariance
1.0
1.0
1.0
0.8
d(U Ü
0.8
0.8
0.6
0.4
0.6
0.6
0.2
0.4
0.4
k
3
0.0
500
1000
500
1000
0
500
1000
or 15ç
or 3000
B 150g -1
1.0
1.0
d(U Ü1.)
0.8
Noisy power method
0.6
Oja's algorithm
0.8
0.4
5=
500
1000
500
1000
or 400g-1
or 700g-1
Figure 2: S&P500 stock market daily return prediction, for k: 1.,,...,
The results in Figure 2 indicate that our findings are also valid in the real-world environment with covariance shifts. First, each result shows optimal parameters regimes observed at the U-shaped curves recovery errors. Furthermore, the result the noisy power method with varying block size akin to the recovery error on Oja's algorithm, plotted with scaled inverse learning rate (-1, These two observations support the main findings in Figure la. We also note that different scaling for each k is natural since we have different spectral gaps å between k-th and k+ 1-th spectrums.
7 Conclusion
the streaming PCA settings with lime-varying covariance, we analyzed the fundamental lower bound of the minimax error and estimation errors for the noisy power method and Oja's 's algorithm. Under this framework, when no perturbation exists (I' = 0), our theoretical result on a lower limit coincides with the order of the traditional outcome. Furthermore, when perturbation exists (L 0), have a non-avoidable positive minimax recovery error, although the time horizon becomes arbitrarily long. Next, found that the noisy power method order-wisely achieves this recovery becomes rate-optimal the σ² = 2(k5/p). For the optimal learning parameters B or Ç-1, we showed that optimal block size and inverse learning rate minimizing recovery multiplicative factor and proportional to 3/22, Experimental results both the synthetic data and real-world environments support the theoretical findings on the learning parameters.
and
similar up to
Although our analysis requires the spectral gap assumption, recent line of literature considers effective rank [12. 50] crucial metric. Therefore, establishing guarantees for robust streaming PCA in terms of effective rank is perfect direction for future work.
Acknowledgement
DB and AS were supported by DARPA Lagrange award. MJ and SY were supported by Institute of Information Communications Technology Planning Evaluation (ITTP) grant funded by the Korea (overnmen((MSTT) (N..2022-0-003) Development of Goal-Oriented, Reinforcement Learning Techniques for Contact-Rich Robotic Manipulation Everyday Objects; No. No.2019-0-000055 Artificial Intelligence Graduate School Program(KAIST)).
10

---

References
[1] K. Abed-Meraim, Attallah, A. Chkeif, and Y. Hua. Orthogonal oja algorithm. IEEE Signal Processing Letters, 7(5):116-119) 2000.
[2] K. Abed-Meraim, A. Chkeif, and Y. Hua. Fast orthonormal past algorithm. IEEE Signal Processing Letters, 7(3):60-62, 2000.
[3] Zeyuan Allen-Zhu and Yuanzhi Li. First efficient convergence for streaming k-pea: A global, gap-free, and near-optimal rate. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 487-492, 2017.
[4] Samreen Fatima and. THE APPLICATION OF PRINCIPAL COMPONENT ANALYSIS AND FACTOR ANALYSIS TO STOCK MARKETS RETURNS. International Journal of Advanced Research, 7(5):77-005, May 2019.
[5] Raman Arora, Andrew Cotter, Karen Liveseu, and Nathan Srebro. Stochastic optimization for pea and pls. In Communication, Control, and Computing (Allerton), 2012 50th Annual Allerton Conference on, pages 861-868. IEEE, 2012.
[6] Laura Balzano, Robert Nowak, and Benjamin Recht. Online identification and tracking of subspaces from highly incomplete information. In 2010 48th Annual allerton conference on communication, control, and computing (Allerton), pages 704-711. IEEE, 2010.
[7] Thomas Bendokat, Ralf Zimmermann, and P. A. Absil. A grassmann manifold handbook: Basic geometry and computational aspects, 2020.
[8] Rajendra Bhatia. Matrix analysis, volume 169, Springer Science & Business Media, 2013.
[9] Daniel Bienstock and Mauro Escobar. Stochastic defense against complex grid attacks. IEEE Transactions on Control of Network Systems, 7(2):842-88) 854, 2020.
[10] Daniel Bienstock and Apurv Shukla. Variance-aware optimal power flow: Addressing the tradeoff between cost, security, and variability, IEEE Trunsactions Control of Network Systems, 6(3):1185-1199 2019.
[11] Vivek Borkar. Stochastic approximation: a dynamical systems viewpoint, volume 48. Springer, 2009.
[12] Florentina Bunea and Luo Xiao. On the sample covariance matrix estimator of reduced effective rank population matrices, with applications to fpea. Bernoulli, 21) 1200-1220,,,,, 2015.
[13] John Burkardt. The truncated normal distribution. Department of Scientific Computing Website, Florida State University, 1:35, 2014.
[14] Tony Cai, Zongming Ma, and Yihong Wu. Optimal estimation and rank detection for sparse spiked covariance matrices. Probubility Theory and Related Fields, 161(3):811-855 Apr 2015.
[15] Emmanuel J Candès, Xiaodong Li. Yi Ma, and John Wright. Robust principal component analysis? Journal of the ACM (JACM). 58(3):1-37, 2011.
[16] Minshuo Chen, Lin Yang. Mengdi Wang, and Tuo Zhao. Dimensionality reduction for stationary time series via stochastic nonconvex optimization. arXiv preprint arXiv: 123 2018.
[17] Yeshwanth Cherapanamjeri, Prateek Jain, and Praneeth Netrapalli. Thresholding based outlier robust pea. In Conference on Learning Theory, pages 993-628. PMLR, 2017.
[18] Yuejie Chi, Yonina C. Eldar, and Robert Calderbank. Petrels: Parallel subspace estimation and tracking by recursive least squares from partial observations. IEEE Transactions on Signal 2013.
Processing, 61 6233::5944-5595
[19] John H. Conway, Ronald H. Hardin, and Neil J. A. Sloane. Packing lines, planes, etc.: packings Grassmannian spaces. Experimental Mathematics, 5(2):139 159, 1996.
[20] Wei Dai, Youjian Liu, and B. Rider. Quantization bounds grassmann manifolds of arbitrary dimensions and mimo communications with feedback. In GLOBECOM '05. IEEE Global Telecommunications Conference, 2005., volume 3. pages 5 pp.-, 2005.
[21] David Donoho, Matan Gavish, and Iain Johnstone. Optimal shrinkage of cigenvalues in the spiked covariance model. The Annals of Statistics, 46(4):1742 1778, 2018.
[22] G.H. Dunteman. Principal Components Analysis. Number No. 69 in Sage Publications.
SAGE Publications, 1989.

---

[23] Mauro Escobar, Daniel Bienstock, and Michael Chertkov. Learning from power system data stream. In 2019 IEEE Milan PowerTech, pages 1-6. IEEE, 2019.
[24] Jiashi Feng, Huan Xu, and Shuicheng Yan. Online robust pea via stochastic optimization. In Advances in Neural Information Processing Systems, pages 404-412, 2013.
[25] Mina Ghashami, Edo Liberty, Jeff M. Phillips, and David P. Woodruff. Frequent directions:
Simple and deterministic matrix sketching. SIAM Journal on Computing, 45(5):1762-1792. 2016.
[26] John Goes, Teng Zhang, Raman Arora, and Gilad Lerman. Robust stochastic principal compo- nent analysis. In Artificial Intelligence and Statistics, pages 266-274. PMLR, 2014.
[27] Donald Goldfarb and Garud lyengar. Robust portfolio selection problems. Mathematics of operations research, 28(1):1-35) 2003.
[28] Gene H Golub and Charles F Van Loan, Matrix computations (4th ed), volume 3. JHU Press, 2012.
[29] Moritz Hardt and Eric Price. The noisy power method: A meta algorithm with applications. In Advances in Neural Information Processing Systems, pages 2861-2866 2014.
[30] Jun He, Laura Balzano, and John C. Lui. Online Robust Subspace Tracking from Partial Information. arXiv e-prints, page arXiv: 1 109.3827, September 2011.
[31] Amelia Henriksen and Rachel Ward. Adaoja: Adaptive learning rates for streaming pea, 2019.
[32] De Huang, Jonathan Niles-Weed, Joel A Tropp, and Rachel Ward. Matrix concentration for products. arXiv preprint (:Xii:2003.05433: 2020.
[33] De Huang, Jonathan Niles-Weed, and Rachel Ward. Streaming k- k-pca: Efficient guarantees for oja's 'ss algorithm, beyond rank-one updates. In Mikhail Belkin and Samory Kpotufe, editors, Conference on Learning Theory, COLT 2021, 15-19 August 2021, Boulder, Colorado, USA, volume 134 of Proceedings of Machine Learning Research, pages 2463-2498. PMLR, 2021.
[34] Prateek Jain, Chi Jin, Sham M Kakade, Praneeth Netrapalli, and Aaron Sidford. Streaming pea: Matching matrix bernstein and near-optimal finite sample guarantees for oja's algorithm. In Conference on Learning Theory, pages 114--1166 2016.
[35] lain M. Johnstone. On the distribution of the largest eigenvalue in principal components analysis. The Annals of Statistics, 29(2):295~ 327, 2001.
[36] lain M Johnstone and Debashis Paul. Pea in high dimensions: An orientation. Proceedings of the IEEE, 106(8):1777-1222 2018.
[37] Harold Kushner and G George Yin. Stochastic approximation and recursive algorithms and applications, volume 35. Springer Science & Business Media, 2003.
[38] Chris Junchi Li, Mengdi Wang, Han Liu, and Tong Zhang. Near-optimal stochastic approxima- tion for online principal component estimation. Mathematical Programming, 167(1):55-97, 2018.
[39] Xin Liang. On the optimality of the oja's algorithm for online PCA. CoRR, abs/2104.00512. 2021.
[40] Edo Liberty. Simple and deterministic matrix sketching. In Proceedings of the 19th ACM SIGKDD International Conference Knowledge Discovery and Data Mining, KDD '13, page 581-588, New York, NY, USA, 2013. Association for Computing Machinery.
[41] André L. G. Mandolesi. Grassmann angles between real or complex subspaces, 2021.
[42] Poorya Mianjy and Raman Arora. Stochastic pea with & and E regularization. In ICML, 2018.
[43]
Ioannis Mitliagkas, Constantine Caramanis, and Prateek Jain. Memory limited, streaming pea. In Proceedings gs of the 26th International Conference on Neural Information Processing Systems Red Hook, NY, USA, 2013, Curran Associates Inc
Volume 2, NIPS' 13, page
[44] Paul Mooney. Stock Market Data (NASDAQ, NYSE, S&P500).
markee--aaaaaaaaaaaaaaaaaaaaaaaa Version 64.
[45] Jonas Mueller, Vasilis Syrgkanis, and Matt Taddy. Low-rank bandit methods for high- dimensional dynamic pricing. Advances in Neural Information Processing Systems, 32, 2019.
12

---

[46] Praneeth Narayanamurthy and Namrata Vaswani. Provable dynamic robust pea or robust subspace tracking. IEEE Transactions on Information Theory, 65(3):154-11577, 2018.
[47] Yuri Neretin. On jordan angles and the triangle inequality in grassmann manifolds. Geometriae Dedicata, 86:81-91, 06 2001.
[48] Erkki Oja and Juha Karhunen. On stochastic approximation of the eigenvectors and eigenvalues of the expectation of random matrix. Journal of mathematical analysis and applications, 106(1):69-84 84, 1985.
[49] Daniel L. Pimentel-Alarcón, Aritra Biswas, and Claudia R Solís-Lemus. Adversarial principal component analysis. In 2017 IEEE International Symposium on Information Theory (ISIT), pages 2363-2367. IEFE, 2017.
[50] Olivier Roy and Martin Vetterli. The effective rank: A measure of effective dimensionality. In 2007 15th European signal processing conference, pages 606-610, IEEE, 2007.
[51] Ohad Shamir. Convergence of stochastic gradient descent for pea. In International Conference on Machine Learning, pages 257-265, 2016.
[52) Ohad Shamir. Fast stochastic algorithms for svd and pea: Convergence properties and convexity. In International Conference on Machine Learning, pages 248-256, 2016.
[53] Wenjie Song, Jianke Zhu, Yang Li, and Chun Chen. Image alignment by online robust pea via stochastic gradient descent. IEEE Transactions on Circuits and Systems for video Technology, 26(7):1241-1233 2015.
[54] Wataru Souma. Characteristics of principal components in stock price correlation. Frontiers in Physics, 9, 2021.
[55] Le Trung Thanh, Nguyen Viet Dung, Nguyen Linh Trung, and Karim Abed- Meraim. Robust subspace tracking with missing data and outliers: Novel algorithm with convergence guarantee. IEEE Transactions on Signal Processing, 69:2070-2085, 2021.
[56] Joel A. Tropp. An introduction matrix concentration incqualities. Foundations and Trends@ in Machine Learning, 8(1-2):1-230, 2015.
[57] Alexandre B Tsybakov. Introduction to nonparametric estimation. Springer Science & Business
Media, 2008
(58) Vincent Q. Vu and Jing Lei. Minimax sparse principal subspace estimation in high dimensions. The Annals of Statistics, 41(6):2905 - 2947, 2013.
[59] Sissi Xiaoxiao Wu, Hoi-To Wai, Anna Scaglione, and Neil Jacklin. The power-oja method for decentralized subspace estimation/tracking.. In 2017 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 3524-3528, 2017.
[60] Bin Yang. Projection approximation subspace tracking. IEEE Transactions on Signal Processing,
4311)995-107, 1995.
[61] Libin Yang. An Application of Principal Component Analysis to Stock Portfolio Management. PhD thesis, Department of Economics and Finance, University of Canterbury, 2015.
[62] Puyudi Yang, Cho-Jui Hsieh, and Lane-Ling Wang. History pea: A new algorithm for streaming pea. arXiv preprint
2018
13


Reviews:
[{"review_id": "wDA5jkDGNSw", "reviewer": "Reviewer_UR4D", "summary": "This paper presents a novel streaming principal component analysis (PCA) method. A major novelty in the model is that the it investigates a robust perspective, where the covariance matrix belongs to a temporal uncertainty set.\n\nThe contributions are two-fold. On one hand, the paper provides a fundamental lower bound for estimating the principal components within the considered framework, namely when the covariance matrix belongs to a temporal uncertainty set. On the other hand, the authors provide an analysis for two algorithms to recover the principal components extensively used in the standard streaming PCA setting.", "questions": "See Weaknesses, mainly related to positioning with respect to the state of the art and weak experimentations.", "limitations": "See Weaknesses", "rating": 6, "confidence": 2, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "\nThe paper is relatively well written, and the contributions are clearly identified.\n\nA major issue of this paper is its position within the state of the art. While the authors do cite some relevant related methods, it seems that the authors either consider robust PCA literature, or streaming PCA literature, but never both frameworks.\n\nAnother issue with respect to the state of the art is that the authors provide some critics wrt related works [46, 11, 50, 25], as they consider “Oja’s algorithm … and do not provide a benchmark comparison”. However, this is exactly what the present paper does: it presents an Oja’s algorithm, and does not provide a benchmark comparison.\n\nExperiments are not comprehensive. It is missing any analysis with a comparative study, neither in the main paper nor in the appendix. It is also missing some benchmark on real datasets that allows to clearly motivate the proposed work.\n\nThere are many spelling and grammatical errors, such as “it satisfies mild condition”, “the columns form basis”, “the ith largest eigenvalue “, “and and”, “we assume … and then draws”, “it is hard to compute of the“, “Note that if the we…”, “These feature models the behavior”, “these hypothesis”, “We consider following algorithms…”, “We used following parameters”,… and many others. A proofreading of the paper is required.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "mj-SPwnU8PC", "reviewer": "Reviewer_pYST", "summary": "This paper studies the properties of streaming PCA in a dynamic environment.  In particular, the authors consider the problem of recovering the top k eigenvectors of the last observation in the stream even when the associated covariance matrices are drifting.  The authors establish a minimax lower bound for the problem and show that the iterated power method achieves the minimax rate.  They also derive convergence rates for Oja’s algorithm in this setting, another commonly used method for streaming PCA. \n", "questions": "- Some recent work has emerged on PCA where the problem complexity is captured by the effective rank, defined as $r(\\Sigma) = tr(\\Sigma)/ \\lambda_1(\\Sigma)$ instead of the dimension.  Do you believe that some of your analysis will be useful for deriving minimax rates in this setup?  Either way, I believe that this line of work should be cited and mentioned briefly.    \n- The Gaussian spiked covariance model is a bit more restrictive than other setups considered in the literature (although these papers consider an IID stream).  Could you discuss how much the minimax results depend on the Gaussianity assumption?  It seems that the assumption is not needed in for deriving upper bounds for the streaming algorithms. \n", "limitations": "Yes, the authors are honest about the suboptimality of the rate for Oja's algorithm.  It may also be worthwhile to state that minimax results may be pessimistic regarding the difficulty of the problem when more structure is present.  ", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- The authors address an interesting problem that, to the best of my knowledge, has not been studied very much: streaming PCA with time-varying covariance matrices.  \n- The authors consider the problem of recovering the top k eigenvectors opposed to the the top eigenvector, which has only recently started to be addressed in some generality in the streaming PCA literature. \n- The minimax rate is a nice result that characterizes the difficulty of the problem and also quantifies the effect of drift well.  \n- The authors show that a commonly used streaming method (noisy power method) attains the minimax rate and also provide analysis for another widely used algorithm (Oja’s algorithm).  \n- On the technical side, the time-varying nature of the problem leads to additional complications and more involved/novel analysis.  \n\nWeaknesses:\n- To me, it appears that this time-varying covariance matrix setting is novel but somewhat unnatural. I believe that the authors should provide better motivation for their problem.  Arguably, the top k eigenvectors of the expectation of the sample covariance is a more natural target than the eigenspace for the last element in the data stream.  Under mild perturbations, one would expect that the mean of this expectation would still converge to some limit and is a meaningful target.  One would also expect that that recovering this eigenspace is much easier.  \n- While the spiked covariance matrix is a common setup, minimax rates for this class have rather poor dependence on dimension.  If one solely considers regimes suggested by these bounds, then one of the main benefits of streaming methods, namely low space requirements, is lost.  See Q1 below.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "NDM7w3Qi1h2", "reviewer": "Reviewer_3FNv", "summary": "The authors analyze the convergence of the noisy power method and Oja’s algorithm in the field of robust streaming PCA.", "questions": "Can the authors  precise if they tested the algorithms in the presence of outliers or partly observed data?", "limitations": "The authors have well addressed the limitations of their work.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n1) The paper is well  organized.\n2) This study about the fundamental limit of the minimax error and convergence of the noisy power method and Oja’s algorithm is welcome and well conducted.\n\nWeaknesses: \n1) There are missing references about key works in the field of streaming PCA. Please see:\nL Balzano, “On the equivalence of Oja's algorithm and GROUSE”, International Conference on Artificial Intelligence and Statistics, AISTATS 2022, Valencia, Spain, March 2022.\nOja's improvements:\nK. Abed-Meraim, S. Attallah, A. Chkeif, Y. Hua, “Orthogonal Oja algorithm\", IEEE Signal Processing Letters, Volume 7, no. 5, pages 116-119, 2000.\nS. Wu, H. Wai, A. Scaglione, N. Jacklin, “The Power-Oja method for decentralized subspace estimation/tracking”, IEEE International Conference on Acoustics, Speech and Signal Processing, ICASSP 2017, pages 3524-3528, 2017.\nPAST/OPAST\nB. Yang, “Projection approximation subspace tracking\", IEEE Transactions on Signal Processing, Volume 43, pages 95–107, January 1995.\nK. Abed-Meraim, A. Chkeif, Y. Hua, “Fast orthonormal PAST algorithm,” IEEE Signal Processing Letters, Volume 7, No. 3, pages60–62, 2000.\nPETRELS and its improvements\nY. Chi, R. Calderbank, Y. Eldar, “PETRELS: Parallel subspace estimation and tracking by recursive least squares from partial observations\", IEEE Transactions on Signal Processing, Volume 61, No. 23, pages 5947–5959, 2013.\nN. Linh-Trung, V. Nguyen, M. Thameri, T. Minh-Chinh, K. Abed-Meraim, \"Low-complexity adaptive algorithms for robust subspace tracking\", IEEE Journal of Selected Topics in Signal Processing, Volume 12, No. 6, pages 1197-1212, 2018.\nL. Thanh, N. Dung, N. Linhtrung, K. Abed Meraim, \"Robust Subspace Tracking with Missing Data and Outliers: Novel Algorithm with Convergence Guarantee\", IEEE Transactions on Signal Processing, 2021.\n\n2) The authors missed to indicate in one or two sentence that streaming algorithms attempt to deal either or both the presence of outliers or partly observed data.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "K37RaE-1MrE", "reviewer": "Reviewer_i2FX", "summary": "This work analysis streaming PCA algorithms in the time varying covariance model and shows that the noisy power method that relies on a batch of samples at each update is Reta-optimal, as opposed to Oja's method that relies on a single sample per update. The proposed theory deviates from the mainstream setting where the fixed covariance model is employed. The proposed theory sheds light onto the performance of streaming PCA algorithms in a setting where the covariance matrix changes over time. The proposed theory is demonstrated practically on synthetic data.", "questions": "1. Multiple redundant words and typos (e.g., 2 in line 38 instead of (2), \"of\" in line 133, \"the\" in line 136, \"zt\" instead of \"wt\" in line 224, period in line 318). Please go through the paper again and fix all inconsistencies. \n\n2. Please rephrase lines 97-98. They are hard to follow. \n\n3. Lines 135-139 present how quickly the At can vary. This is not mentioned earlier in the abstract or the introduction. Please mention this briefly in the abstract and/or introduction so that the reader is aware of this setting and is not misled into assuming no conditions on the rate of change of At.\n\n4. Is the assumption 1 in definition 1 relevant in practice? Please provide examples.\n\n5. Does Algorithm 1 need input batch size, B, with xt? If so, please add it to the pseudocode. \n\n6. Does algorithm 2 require input learning rate, \\zeta? If so, please add it to the pseudocode. \n\n7. Line 301 refers to line 6 in Algorithm 2 but there are only 5 lines. Please edit this typo.\n\n8. In the experimental studies, can we please see what happens for larger perturbation \\Tau? Does the trend in Figure 1(a) hold for larger \\Tau?\n\n9. Please comment on the behavior of Oja's algorithm in Figure 1(a). It appears that larger learning rates are better for larger perturbations. Why? Please elaborate.\n", "limitations": "A limitation is method in the text and posed a future work. ", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. The paper is well-written and has a good flow.\n2. The proposed theory is motivated with practical examples.\n3. This work provided convergence analysis two important algorithms, namely the noisy power method and Oja's method under time varying covariance model.\n4. The proposed theory in corroborated by synthetic studies.\n\nWeaknesses:\n1. Multiple redundant words and typos. \n2. Some of the text is hard to follow.\n3. Some analysis of the synthetic studies is missing.\n\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept