--- abstract: | This paper introduces Memory-limited Online Subspace Estimation Scheme (MOSES) for both estimating the principal components of <span><span> streaming</span></span> data and reducing its dimension. More specifically, <span><span> in various applications such as sensor networks,</span></span> the data vectors are presented sequentially to a user who has limited storage and processing time available. <span><span> Applied to such problems</span></span>, MOSES <span><span> can provide a running</span></span> estimate of leading principal components of the data that has arrived so far and also reduce its dimension. <span><span> MOSES generalises the popular incremental Singular Vale Decomposition (iSVD) to handle thin blocks of data, rather than just vectors</span></span>. This minor generalisation <span><span> in part allows us</span></span> to complement MOSES with a comprehensive statistical analysis, <span><span> thus providing the first theoretically-sound variant of iSVD, which has been lacking despite the empirical success of this method</span></span>. This generalisation also enables us to concretely interpret MOSES as an approximate solver for the underlying non-convex optimisation program. We find that MOSES <span><span> consistently surpasses the state of the art</span></span> in our numerical experiments with both synthetic and real-world datasets<span><span> , while being computationally inexpensive.</span></span> author: - 'Armin Eftekhari, Raphael A. Hauser, Andreas Grammenos[^1]' title: | MOSES: A Streaming Algorithm for\ Linear Dimensionality Reduction --- <span>***Keywords—*** Principal component analysis, Linear dimensionality reduction, Subspace identification, Streaming algorithms, Non-convex optimisation. </span> Introduction \[sec:intro0\] =========================== Linear models are pervasive in data and computational sciences and, <span><span> in particular</span></span>, <span>Principal Component Analysis</span> (PCA) is an indispensable tool for detecting linear structure in collected data @van2012subspace [@ardekani1999activation; @krim1996two; @tong1998multichannel; @vidal2016generalized; @hauser2018pca; @hauser2018pca2]. <span>Principal components</span> are the directions that preserve most of the "energy" of a dataset and can be used for linear dimensionality reduction, among other things. In turn, successful dimensionality reduction is at the heart of <span><span> statistical learning and serves to tackle the "curse of dimensionality" @hastie2013elements.</span></span> In this work, we are interested in both computing the principal components *and* reducing the dimension of data that is presented sequentially to a user. Due to hardware limitations, the user can only store small amounts of data, which in turn <span><span> would</span></span> severely limit the available processing time for each incoming data vector. For example, consider a network of battery-powered and cheap sensors that must relay their measurements to a central node on a daily basis. Each sensor has a small storage and does not have the power to relay all the raw data to the central node. One solution is then for each sensor to reduce the dimension of its data to make transmission to the central node possible. Even if each sensor had unlimited storage, the frequent daily updates scheduled by the central node would force each sensor to reduce the dimension of its data "on the go" before transmitting it to the central node. A number of similar problems are listed in @balzano2010online. Motivated by such scenarios, we are interested in developing a *streaming* algorithm for linear dimensionality reduction, namely, an algorithm with minimal storage and computational requirements. As more and more data vectors arrive, this algorithm would keep a running estimate of the principal components of the data *and* project the available data onto this estimate to reduce its dimension. <span><span> As discussed in Section \[sec:intro\], this is equivalent to designing a streaming algorithm for truncated Singular Value Decomposition (SVD).</span></span> Indeed, incremental SVD (iSVD) is a successful streaming algorithm that updates its estimate of the truncated SVD of the data matrix with every new incoming vector @bunch1978rank [@brand2006fast; @brand2002incremental; @comon1990tracking; @li2004incremental]. <span><span> However,</span></span> to the best of our knowledge and despite its popularity and empirical success, iSVD lacks comprehensive statistical guarantees. In fact, @balsubramani2013fast only very recently provided stochastic analysis for two of the variants of iSVD in @krasulina1969method [@oja1983subspace]. <span><span> More specifically,</span></span> in @balsubramani2013fast the authors studied how well the output of iSVD approximates the leading principal component of data, in expectation. Crucially, @balsubramani2013fast does *not* offer any guarantees for dimensionality reduction; see Section \[sec:lit review\] <span><span> for more details on iSVD</span></span> and review of the prior art. #### **Contributions** {#contributions .unnumbered} In this paper, <span><span> to address the shortcomings of iSVD,</span></span> we propose Memory-limited Online Subspace Estimation Scheme ($\alg$) for streaming dimensionality reduction. $\alg$ generalises iSVD to update its estimate with every incoming *thin* block of data, rather than with every incoming vector. This small <span><span> generalisation</span></span> is in part what enables us to complement $\alg$ with a comprehensive statistical analysis, <span><span> thus providing (to the best of our knowledge) the first theoretically-sound variant of iSVD.</span></span> Indeed, Theorem \[thm:stochastic result\] below considers the important case where the incoming data vectors are drawn from a zero-mean normal distribution. This stochastic setup is a powerful generalisation of the popular *spiked covariance* model common in statistical signal processing @johnstone2001distribution. Theorem \[thm:stochastic result\] states that $\alg$ nearly matches the performance of "offline" truncated SVD (which has unlimited memory and computing resources), provided that the corresponding covariance matrix is well-conditioned and has a small residual. Moreover, we concretely interpret $\alg$ as an approximate solver for the underlying non-convex optimisation program. We also find that $\alg$ consistently surpasses the state of the art in our numerical experiments with both synthetic and real-world datasets, <span><span> while being computationally inexpensive.</span></span> Introducing MOSES \[sec:intro\] =============================== Consider a sequence of vectors $\{y_t\}_{t=1}^T\subset \mathbb{R}^n$, presented to us sequentially, and let $$\label{eq:conc of yts} \Y_{T} := \l[ \begin{array}{cccc} y_1 & y_2 & \cdots & y_T \end{array} \r] \in\R^{n\times T},$$ for short. We conveniently assume throughout that $\Y_T$ is *centred*, namely, the entries of each row of $\Y_T$ sum up to zero. For an integer $r\le \rank(\Y_T)$, let us partition the SVD of $\Y_T$ into two orthogonal components as $$\begin{aligned} \Y_T & \overset{\text{SVD}}{=} {\boldsymbol{S}}_T {\boldsymbol{\Gamma}}_T \Q_T^* \qquad ( {\boldsymbol{S}}_T \in \text{O}(n), \, {\boldsymbol{Q}}_T \in \text{O}(T) ) \nonumber\\ & = {\boldsymbol{S}}_{T,r} {\boldsymbol{\Gamma}}_{T,r} \Q_{T,r}^*+ {\boldsymbol{S}}_{T,r^+} {\boldsymbol{\Gamma}}_{T,r^+} \Q_{T,r^+}^* \nonumber\\ & =: \Y_{T,r}+\Y_{T,r^+}, \label{eq:decomposition of Y}\end{aligned}$$ where $\text{O}(n)$ is the orthogonal group, containing all $n\times n$ matrices with orthonormal columns, and ${\boldsymbol{\Gamma}}_T\in \R^{n\times T}$ above contains the singular values in nonincreasing order. Moreover, ${\boldsymbol{S}}_{T,r} \in \R^{n\times r}$ contains leading $r$ principal components of $\Y_T$, <span><span> namely, the singular vectors corresponding to largest $r$ singular values of $\Y_T$ @eckart [@mirsky].</span></span> Given ${\boldsymbol{S}}_{T,r}$, we can reduce the dimension of data from $n$ to $r$ by projecting $\Y_T$ onto the column span of ${\boldsymbol{S}}_{T,r}$, that is, $$\begin{aligned} {\boldsymbol{S}}_{T,r}^*\cdot \Y_T & = {\boldsymbol{\Gamma}}_{T,r} {\boldsymbol{Q}}_{T,r}^* \in\mathbb{R}^{r\times T}. \qquad \mbox{(see \eqref{eq:decomposition of Y})} \label{eq:projected data matrix}\end{aligned}$$ Above, the projected data matrix ${\boldsymbol{S}}_{T,r}^* \Y_T\in\R^{r\times T}$ again has $T$ data vectors (namely, columns) but these vectors are embedded in (often much smaller) $\mathbb{R}^r$ rather than $\mathbb{R}^n$. <span><span> Note that $ \Y_{T,r} $ in is a rank-$r$ truncation of $\Y_T$, which we denote with $\Y_{T,r}=\SVD_r(\Y_T)$.</span></span> That is, $\Y_{T,r}$ is a best rank-$r$ approximation of $\Y_T$ with the corresponding residual $$\begin{aligned} \| \Y_T - \Y_{T,r} \|_F^2 & = \min_{\operatorname{rank}({\boldsymbol{X}})=r} \| \Y_T - {\boldsymbol{X}}\|_F^2 \nonumber\\ & = \| \Y_{T,r^+}\|_F^2 = \sum_{i\ge r+1} \sigma_i^2(\Y_T)\nonumber\\ & =: \rho_r^2(\Y_T), \label{eq:residual}\end{aligned}$$ where $\sigma_1(\Y_T)\ge \sigma_2(\Y_T)\ge \cdots $ are the singular values of $\Y_T$. <span><span> We also observe that</span></span> $$\begin{aligned} \Y_{T,r}& =\SVD_r(\Y_T) \nonumber\\ & = \underset{\operatorname{PCs}}{\underbrace{{\boldsymbol{S}}_{T,r}}} \cdot \underset{\operatorname{projected\; data}}{\underbrace{{\boldsymbol{\Gamma}}_{T,r} {\boldsymbol{Q}}_{T,r}^*}}. \qquad \mbox{(see (\ref{eq:decomposition of Y},\ref{eq:projected data matrix}))} \label{eq:low-rank est kept}\end{aligned}$$ That is, rank-$r$ truncation of $\Y_T$ encapsulates both leading $r$ principal components of $\Y_T$, namely ${\boldsymbol{S}}_{T,r}$, and the projected data matrix ${\boldsymbol{S}}_{T,r}^*{\boldsymbol{Y}}_T = {\boldsymbol{\Gamma}}_{T,r} {\boldsymbol{Q}}_{T,r}^*$. In other words, computing a rank-$r$ truncation of the data matrix both yields its principal components and reduces the dimension of ralphmiller@example.com. For a block size $b$, our strategy is to iteratively group every $b$ incoming vectors into an $n\times b$ block and then update a rank-$r$ estimate of the data received so far. We assume throughout that $r\le b\le T$ and in fact often take the block size as $b=O(r)$, where $O$ is the standard Big-O notation. It is convenient to assume that the number of blocks $K:=T/b$ is an integer. We call this simple algorithm $\alg$ for Memory-limited Online Subspace Estimation Scheme<span><span> , presented in an accessible fashion in Algorithm \[alg:MOSES\].</span></span> The output of $\alg$ after $K$ iterations is $$\wh{\Y}_{Kb,r}=\wh{\Y}_{T,r},$$ which contains both an estimate of leading $r$ principal components of $\Y_T$ and <span><span> also</span></span> the projection of $\Y_T$ onto this estimate, as discussed below. A <span><span> computationally</span></span> efficient implementation of $\alg$ is given in Algorithm \[alg:MOSES implement\], which explicitly maintains both the estimates of principal components and the projected data. As also discussed below, the storage and computational requirements of Algorithm \[alg:MOSES implement\] are nearly <span><span> minimal</span></span>. #### **Discussion** {#discussion .unnumbered} $\alg$ maintains a rank-$r$ estimate of the data received so far, and updates its estimate in every iteration to account for the new incoming block of data. More specifically, note that the final output of $\alg$, namely $\widehat{\Y}_{T,r}\in\mathbb{R}^{n\times T}$, is at most rank-$r$, and let $$\wh{\Y}_{T,r} \overset{\text{tSVD}}{=} \wh{{\boldsymbol{S}}}_{T,r} \wh{{\boldsymbol{\Gamma}}}_{T,r} \wh{{\boldsymbol{Q}}}_{T,r}^*$$ $$\l( \wh{{\boldsymbol{S}}}_{T,r}\in \text{St}(n,r), \, \wh{{\boldsymbol{Q}}}_{T,r}\in \text{St}(T,r) \r)$$ <span><span> be its thin SVD. Above, $\text{St}(n,r)$ is the Stiefel manifold, containing all $n\times r$ matrices with orthonormal columns, and the diagonal matrix $\wh{{\boldsymbol{\Gamma}}}_{T,r}\in \R^{r\times r}$ contains the singular values in nonincreasing order.</span></span> Then, $\wh{{\boldsymbol{S}}}_{T,r}\in\mathbb{R}^{n\times r}$ is $\alg$'s estimate of <span><span> leading</span></span> principal components of the data matrix $\Y_{T}$, and $$\wh{{\boldsymbol{S}}}_{T,r}^* \wh{\Y}_{T,r} = \wh{{\boldsymbol{\Gamma}}}_{T,r} \wh{{\boldsymbol{Q}}}_{T,r} \in \mathbb{R}^{r\times T}$$ is the projection of $\wh{\Y}_{T,r}$ onto this estimate. That is, $\wh{{\boldsymbol{S}}}_{T,r}^* \wh{\Y}_{T,r}$ is the $\alg$'s estimate of the projected data matrix. #### **Origins** {#origins .unnumbered} <span>iSVD</span> is a streaming algorithm that updates its estimate of (truncated) SVD of the data matrix with every new incoming vector @bunch1978rank [@brand2006fast; @brand2002incremental; @comon1990tracking; @li2004incremental]. <span><span> Despite its popularity and empirical success, iSVD lacks comprehensive statistical guarantees, as detailed in Section \[sec:lit review\].</span></span> $\alg$ generalises iSVD to update its estimate with every incoming block of data, rather than every data vector. As detailed later in Section \[sec:lit review\], <span><span> this minor extension in part enables us to complement $\alg$ with a comprehensive statistical analysis, summarised in Theorem \[thm:stochastic result\] below. In this sense, $\alg$ might be interpreted as a variant of iSVD that is both successful in practice and theoretically grounded.</span></span> <span><span> Working with data blocks</span></span> also allows us to concretely interpret $\alg$ as an approximate solver for the underlying non-convex program, as detailed in Section 3 of the supplementary material. #### **Storage and computational requirements** {#storage-and-computational-requirements .unnumbered} The efficient implementation of $\alg$ in Algorithm \[alg:MOSES implement\] is based on the ideas from iSVD and it is straightforward to verify that Algorithms \[alg:MOSES\] and \[alg:MOSES implement\] are indeed equivalent; at iteration $k$, the relation between the output of Algorithm \[alg:MOSES\] ($\wh{\Y}_{kb,r}$) and the output of Algorithm \[alg:MOSES implement\] ($\wh{{\boldsymbol{S}}}_{kb,r},\wh{{\boldsymbol{\Gamma}}}_{kb,r},\wh{{\boldsymbol{Q}}}_{kb,r}$) is $$\wh{\Y}_{kb,r}\overset{\text{tSVD}}{=}\wh{{\boldsymbol{S}}}_{kb,r}\wh{{\boldsymbol{\Gamma}}}_{kb,r}\wh{{\boldsymbol{Q}}}_{kb,r}^*.$$ More specifically, $\wh{{\boldsymbol{S}}}_{kb,r} \in\text{St}(n,r)$ is $\alg$'s estimate of leading $r$ principal components of $\Y_{kb}\in \mathbb{R}^{n\times kb}$, where we recall that $\Y_{kb}$ is the data received <span><span> up to iteration $k$</span></span>. Moreover, $$\wh{{\boldsymbol{S}}}_{kb,r}^* \wh{\Y}_{kb,r}= \wh{{\boldsymbol{\Gamma}}}_{kb,r}\wh{{\boldsymbol{Q}}}_{kb,r}^*\in \mathbb{R}^{r\times kb}$$ is the projection of $\wh{\Y}_{kb,r}$ onto this estimate, namely, $\wh{{\boldsymbol{S}}}_{kb,r}^* \wh{\Y}_{kb,r}$ is $\alg$'s estimate of the projected data matrix so far. In words, the efficient implementation of $\alg$ in Algorithm \[alg:MOSES implement\] explicitly maintains estimates of both principal components and the projected data, at every iteration. <span><span> As detailed in Section 2 of the supplementary material, Algorithm \[alg:MOSES implement\] requires $O(r(n+kr))$ bits of memory at iteration $k$. This is optimal, as it is impossible to store a rank-$r$ matrix of size $n\times kb$ with fewer bits when $b=O(r)$. On the other hand, Algorithm \[alg:MOSES implement\] performs $O(r^2(n+kb))=O(r^2(n+kr))$ flops in iteration $k$. The dependence of both storage and computational complexity on $k$ is because $\alg$ maintains both an estimate of principal components ($\wh{{\boldsymbol{S}}}_{kb,r}$) and an estimate of the projected data (${\boldsymbol{\Gamma}}_{kb,r}{\boldsymbol{Q}}_{kb,r}^*$). To maximise the efficiency, one might optionally "flush out" the projected data after every $n/b$ iterations, as described in the last step in Algorithm \[alg:MOSES implement\].</span></span> \[H\] **Input:** Sequence of vectors $\{y_t\}_{t\ge 1}\subset\mathbb{R}^n$, rank $r$, and block size $b\ge r$. **Output:** Sequence <span><span> $\{\wh{\Y}_{kb,r}\}_{k\ge 1}$</span></span>, where $\wh{\Y}_{kb,r}\in\mathbb{R}^{n\times kb}$ for every $k\ge 1$. **Body:**\ 1. Set $\wh{\Y}_{0,r}\leftarrow \{\}$. 2. For $k\ge 1$, repeat 1. Form $\y_k\in\mathbb{R}^{n\times b}$ by concatenating $\{y_t\}_{t=(k-1)b+1}^{kb}$. 2. Set $\widehat{\Y}_{kb,r}=\text{SVD}_{r}([ \widehat{\Y}_{(k-1)b,r} \,\,\, \y_{k}])$, where $\text{SVD}_r(\cdot)$ returns a rank-$r$ truncated SVD of its argument. Performance of MOSES \[sec:results\] ==================================== In this section, we study the performance of $\alg$ in a stochastic setup. Consider the probability space $(\R^n,\mathcal{B},\mu)$, where $\mathcal{B}$ is the Borel $\sigma$-algebra and $\mu$ is an *unknown* probability measure with zero mean, namely, $\int_{\R^n} y \, \mu(dy) = 0$. <span><span> Informally,</span></span> we are interested in finding an $r$-dimensional subspace $\U$ that <span><span> captures most of the mass of</span></span> $\mu$. That is, with $y$ drawn from this probability space, we are interested in finding an $r$-dimensional subspace $\U$ that minimises the *population risk*. <span><span> To be specific, we wish to solve</span></span> $$\begin{aligned} & \min_{\U\in\GR(n,r)} \underset{y\sim \mu}{\E}\l\| y - \P_{\U} y\r\|_2^2 \nonumber\\ & = \min_{\U\in\GR(n,r)} \int_{\R^n} \l\| y- \P_{\U} y\r\|_F^2 \, \mu(dy) =: \rho_r^2(\mu), \label{eq:direct}\end{aligned}$$ <span><span> where the Grassmanian $\text{G}(n,r)$ is the set of all $r$-dimensional subspaces in $\R^n$</span></span><span><span> , and $\rho_r(\mu)$ denotes the corresponding <span>residual</span>.</span></span> Since $\mu$ is unknown, we cannot directly solve Program , but suppose that instead we have access to the *training samples* $\{y_t\}_{t=1}^T \subset \R^{n}$, drawn independently from <span><span> the probability measure $\mu$</span></span>. Let us form $\Y_T\in\R^{n\times T}$ by concatenating these vectors, <span><span> similar to </span></span> . In lieu of Program , <span><span> we minimise the *empirical risk*, namely, we solve the optimisation program</span></span> $$\begin{aligned} & \min_{\U\in\GR(n,r)} \frac{1}{T}\sum_{t=1}^T \l\| y_t - \P_{\U}y_t \r\|_2^2 \nonumber\\ & = \min_{\U\in\GR(n,r)} \frac{1}{T} \l\|\Y_T - \P_{\U}\Y_T \r\|_F^2 . \qquad \text{(see \eqref{eq:conc of yts})}\end{aligned}$$ <span><span> Let $\SU_{T,r}\in\GR(n,r)$ be a minimiser of the above program, with the orthonormal basis ${\boldsymbol{S}}_{T,r}\in\text{St}(n,r)$.</span></span> <span><span> By the Eckart-Young-Mirsky Theorem @eckart [@mirsky], ${\boldsymbol{S}}_{T,r}$ consists of leading $r$ principal components of $\Y_T$, namely, it contains leading $r$ left singular vectors of $\Y_T$.</span></span> <span><span> Therefore, $$\begin{aligned} & \min_{\U\in\GR(n,r)} \frac{1}{T}\sum_{t=1}^T \l\| y_t - \P_{\U}y_t \r\|_2^2 \nonumber\\ & = \frac{1}{T}\l\|\Y_T - \P_{\SU_{T,r}}\Y_T \r\|_F^2 \nonumber\\ & = \frac{1}{T} \l\|\Y_T -\Y_{T,r} \r\|_F^2 \qquad \l(\Y_{T,r}=\text{SVD}_r(\Y_T)\r) \nonumber\\ & =: \frac{\rho_r^2(\Y_T) }{T}. \qquad \text{(see \eqref{eq:residual})} \label{eq:empirical}\end{aligned}$$</span></span>Given its principal components, we can then reduce the dimension of the data matrix $\Y_T\in\R^{n\times T}$ from $n$ to $r$ by computing ${\boldsymbol{S}}_{T,r}^*\Y_T\in \R^{r\times T}$. Note also that <span><span> the subspace</span></span> $\SU_{T,r}$ is a possibly sub-optimal choice in Program , namely, $$\underset{y\sim \mu}{\E} \|y-\P_{\SU_{T,r}}y\|_2^2 \ge \rho_r^2(\mu). \qquad \text{(see \eqref{eq:direct})}$$ But one would hope that <span><span> $\SU_{T,r}$</span></span> still nearly minimises Program , in the sense that $$\underset{y\sim \mu}{\E} \| y- \P_{\SU_{T,r}}y\|_2^2 \approx \rho_r^2(\mu), \label{eq:indirect 1}$$ with high probability over the choice of training data $\{y_t\}_{t=1}^T$. That is, one would hope that the *generalisation error* of Program is small. Above, $\underset{y\sim \mu}{\E}$ stands for expectation over $y$, so that the left-hand side of is still a random variable because of its dependence on <span><span> $\SU_{T,r}$ and, in turn, <span><span> on </span></span>the training data.</span></span> If the training data $\{y_t\}_{t=1}^T$ is presented to us sequentially and little storage is available, we cannot hope to directly solve Program . In this streaming scenario, we may apply $\alg$ to obtain the (rank-$r$) output $\wh{\Y}_{T,r}$. We then set $$\wh{\SU}_{T,r} = \mbox{span}(\wh{\Y}_{T,r}), \label{eq:span of output of MOSES}$$ with orthonormal basis <span><span> $\wh{{\boldsymbol{S}}}_{T,r}\in \text{St}(n,r)$</span></span>. Note that <span><span> $\wh{{\boldsymbol{S}}}_{T,r}$</span></span> is $\alg$' estimate of leading $r$ principal components of the data matrix $\Y_T$ and is possibly suboptimal in the sense that $$\| \Y_T-\wh{ \Y}_{T,r} \|_F \ge \rho_r(\Y_T). \qquad \mbox{(see \eqref{eq:empirical})}$$ <span><span> Again,</span></span> we would still hope that the output $\widehat{\Y}_{T,r}$ of $\alg$ is a nearly optimal choice in Program , in the sense that $$\| \Y_T-\wh{ \Y}_{T,r} \|_F \approx \rho_r(\Y_T), \label{eq:indirect 1.5}$$ with high probability over the choice of $\{y_t\}_{t=1}^T$. Moreover, <span><span> similar to</span></span> , $\wh{\SU}_{T,r}$ is again a possibly <span><span> sub-optimal</span></span> choice for Program , and yet we hope that $$\E_y\| y- \P_{\wh{\SU}_{T,r}}y\|_2^2 \approx \rho_r^2(\mu), \label{eq:ideal}$$ with high probability over the choice of $\{y_t\}_{t=1}^T$. To summarise, the key questions are whether (\[eq:indirect 1\],\[eq:indirect 1.5\],\[eq:ideal\]) hold. <span><span> We</span></span> answer these questions for the important case where $\mu$ is a zero-mean Gaussian probability measure with covariance matrix ${\boldsymbol{\Xi}}\in\R^{n\times n}$. For this choice of $\mu$ in , it is not difficult to verify that $$\rho_r^2(\mu) = \sum_{i=r+1}^n \lambda_i({\boldsymbol{\Xi}}), \label{eq:res of gaussian dist}$$ where $\lambda_1({\boldsymbol{\Xi}}) \ge \lambda_2({\boldsymbol{\Xi}})\ge \cdots $ are the eigenvalues of the covariance matrix ${\boldsymbol{\Xi}}$. From now on, <span><span> we use</span></span> $$\rho_r = \rho_r(\mu), \qquad \lambda_i=\lambda_i({\boldsymbol{\Xi}}), \qquad i\in [1:n].$$ For our choice of $\mu$ above, one can use standard tools to show that holds when $T$ is sufficiently large, <span><span> see</span></span> Section B of the supplementary material @eftekhari2016learning [@hauser2017quantifying; @vershynin2012close]. \[prop:first app\] Suppose that $\{y_t\}_{t=1}^T\subset\R^n$ are drawn independently from a zero-mean Gaussian <span><span> distribution</span></span> with <span><span> the</span></span> covariance matrix ${\boldsymbol{\Xi}}\in\R^{n\times n}$ and form $\Y_T\in\R^{n\times T}$ by concatenating these vectors, as in (\[eq:conc of yts\]). Suppose also that $\SU_{T,r}\in\GR(n,r)$ is the span of leading $r$ principal components of $\Y_T$. For $1\le \alpha \le \sqrt{T/\log T}$, it then holds that $$\frac{\rho_r^2(\Y_T)}{T} \lesssim {{ \alpha \rho_r^2}}, \label{eq:true residual prop}$$ $$\underset{y\sim \mu}{\E} \|y - \P_{\SU_{T,r}} y\|_2^2 \lesssim {{ \alpha \rho_r^2}} + {{\alpha (n-r)\lambda_1 \sqrt{\frac{ {\log T} }{T}}}}, \label{eq:gen err easy}$$ except with a probability of at most $T^{-C\alpha^2}$, <span><span> see (\[eq:residual\])</span></span>. <span><span> Here,</span></span> $C$ is a universal constant, <span><span> the value of which may change in every appearance.</span></span> Above, $\lesssim$ suppresses <span><span> some of the</span></span> universal constants for a more tidy presentation. In words, states that the generalisation error of Program is small, namely, <span><span> offline truncated SVD successfully estimates the unknown subspace from training data.</span></span> <span><span> Indeed</span></span>, holds when $\alpha = O(1)$ and $ T$ is sufficiently large. As the dimension $r$ of the subspace fit to the data approaches the ambient dimension $n$, <span><span> the right-hand of </span></span> vanishes, <span><span> see .</span></span> <span><span> In the streaming setup,</span></span> Theorem \[thm:stochastic result\] below states that $\alg$ approximately solves Program , namely, $\alg$ approximately estimates leading principal components of $\Y_T$ *and* reduces the dimension of data from $n$ to $r$ with only $O(r(n+T))$ bits of memory, rather than $O(nT)$ bits required for solving Program with offline truncated SVD. Moreover, $\alg$ approximately solves Program . In other words, $\alg$ satisfies *both* (\[eq:indirect 1.5\],\[eq:ideal\]). These statements are made concrete below and proved in Section C of the supplementary material. \[thm:stochastic result\] ***(Performance of MOSES)*** Suppose that $\{y_t\}_{t=1}^T\subset\R^n$ are drawn independently from a zero-mean Gaussian <span><span> distribution with the</span></span> covariance matrix ${\boldsymbol{\Xi}}\in\R^{n\times n}$ <span><span> and form $\Y_T$ by concatenating these vectors, as in (\[eq:conc of yts\]).</span></span> Let us define <span>$$\kappa_r^2 := \frac{\lambda_1}{\lambda_r}, \qquad \rho_r^2 = \sum_{i=r+1}^n \lambda_i, \qquad \rate_r := \kappa_r + \sqrt{\frac{2\alpha \rho_r^2}{p^{\frac{1}{3}}\lambda_r}}, \label{eq:spect of guassian thrm}$$</span>where $\lambda_1\ge \lambda_2 \ge \cdots$ are the eigenvalues of ${\boldsymbol{\Xi}}$. Let $\wh{\SU}_{T,r} = \operatorname{span}(\wh{\Y}_{T,r})$ be the span of the output of MOSES, as in (\[eq:span of output of MOSES\]). Then, for tuning parameters $1\le \alpha\le \sqrt{T/\log T}$ and $p>1$, <span><span> the output $\wh{\Y}_{T,r}$ of MOSES satisfies</span></span> <span>$$\begin{aligned} & \frac{\| \Y_T - \wh{\Y}_{T,r} \|_F^2}{T} \nonumber\\ & \lesssim \frac{\alpha \p^{\frac{1}{3}} 4^{p\eta_r^2} }{(\p^{\frac{1}{3}}-1)^2} \cdot \min\l ( \kappa_r^2 \rho_r^2, r\lambda_1+\rho_r^2\r)\cdot \l(\frac{T}{\p\eta^2_r b} \r)^{p\eta_r^2-1}, \label{eq:near residual of moses thm}\end{aligned}$$</span><span><span> explained in words after this theorem.</span></span> <span><span> Moreover, the output subspace $\wh{\SU}_{T,r}$ of MOSES satisfies</span></span> <span>$$\begin{aligned} & \underset{y\sim \mu}{\E} \|y - \P_{\wh{\SU}_{T,r}} y\|_2^2 \nonumber\\ & \lesssim \frac{\alpha\p^{ \frac{1}{3}}4^{p\eta_r^2} }{(\p^{\frac{1}{3}}-1)^2} \cdot \min\l ( \kappa_r^2 \rho_r^2, r\lambda_1+ \rho_r^2\r) \l(\frac{T}{\p\eta^2_r b} \r)^{p\eta_r^2-1} \nonumber\\ & + \alpha (n-r)\lambda_1 \sqrt{\frac{ {\log T} }{T}} , \label{eq:final bnd}\end{aligned}$$ </span><span><span> explained after this theorem.</span></span> <span><span> hold</span></span> except with a probability of at most $T^{-C\alpha^2}+ e^{-C\alpha r}$ and provided that $$b \ge \frac{\alpha \p^{\frac{1}{3}} r}{({\p^{\frac{1}{6}}}-1)^2}, \qquad b\ge C\alpha r, \qquad T \ge \p\eta_r^2 b.$$ The requirement $T\ge p\eta_r^2 b$ above is only for cleaner bounds. A general expression for arbitrary $T$ is given in the proof. #### **Discussion of Theorem \[thm:stochastic result\]** {#discussion-of-theorem-thmstochastic-result .unnumbered} On the one hand, states that <span><span> $\alg$ successfully reduces the dimension of streaming data, namely, holds under certain conditions:</span></span> <span><span> Loosely-speaking,</span></span> states that $\|\Y_T-\wh{\Y}_{T,r}\|_F^2$ scales with $\rho_r^2 T^{p\eta_r^2}/b^{p\eta^2_r -1}$, <span><span> where $\wh{\Y}_{T,r}$ is the output of MOSES.</span></span> <span><span> In contrast with , we have</span></span> $$\begin{aligned} & \|\Y_T - \wh{\Y}_{T,r}\|_F^2 \propto \l(\frac{T}{b}\r)^{p\eta_r^2-1} \rho_r^2(\Y_T) & \nonumber\\ & = \l(\frac{T}{b}\r)^{p\eta_r^2-1} \|\Y_T - \Y_{T,r}\|_F^2, \qquad \text{(see \eqref{eq:empirical})} \label{eq:gist} \end{aligned}$$ after ignoring the less important terms. In words, applying <span><span> (offline)</span></span> truncated SVD to $\Y_T$ outperforms the <span><span> (streaming)</span></span> $\alg$ by a polynomial factor in $T/b$. This polynomial factor can be negligible when the covariance matrix ${\boldsymbol{\Xi}}$ of the Gaussian data distribution is well-conditioned ($\kappa_r =O(1)$) and has a small residual ($\rho_r^2 =O(\lambda_r)$), in which case we will have $\eta_r =O(1)$, see . <span><span> Also setting</span></span> $p=O(1)$, then reads as $$\begin{aligned} \|\Y_T - \wh{\Y}_{T,r}\|_F^2 \propto \l(\frac{T}{b}\r)^{O(1)}\rho_r^2(\Y_T), \label{eq:intuition}\end{aligned}$$ <span><span> namely, (streaming) MOSES is comparable to offline truncated SVD.</span></span> In particular, when $\rank({\boldsymbol{\Xi}}) \le r$, we have by that $\rho_r=0$. Consequently, reads as $\wh{\Y}_{T,r}=\Y_{T,r}=\Y_T$. <span><span> That is,</span></span> the outputs of offline truncated SVD and $\alg$ coincide <span><span> in this case</span></span>. The dependence <span><span> in Theorem \[thm:stochastic result\]</span></span> on the condition number $\kappa_r$ and the residual $\rho_r$ is very likely *not* an artifact of the proof techniques; see . Indeed, when $\kappa_r\gg 1$, certain directions are less often observed in the incoming data vectors $\{ y_t\}_{t=1}^T$, which tilts the estimate of $\alg$ towards the dominant principal components corresponding to the very large singular values. Moreover, if $\rho_r \gg 1$, there are too many significant principal components, <span><span> while</span></span> $\alg$ can at most "remember" $r$ of them from its previous iteration. In this scenario, <span><span> fitting an $r$-dimensional subspace to data</span></span> is not a good idea in the first place <span><span> because even</span></span> the residual $\rho_r(\Y_T)$ of the offline truncated SVD will be large, and we should perhaps increase the dimension $r$ of the subspace fitted to the incoming data. As <span><span> the block size</span></span> $b$ increases, <span><span> the</span></span> performance of $\alg$ approaches that of the offline truncated SVD. In particular, when $b=T$, $\alg$ <span><span> reduces to offline truncated SVD, processing all of the ralphmiller@example.com.</span></span> This trend is somewhat imperfectly reflected in . On the other hand, Theorem \[thm:stochastic result\] and specifically state that <span><span> MOSES approximately estimates the (unknown) underlying subspace, namely,</span></span> holds under certain conditions. Indeed, for sufficiently large $T$, <span><span> loosely-speaking</span></span> reads as $$\begin{aligned} & \underset{y\sim\mu}{\E} \|y-\P_{\wh{\SU}_{T,r}}y\|_2^2 \propto \l( \frac{T}{b} \r)^{p\eta_r^2-1} \rho_r^2 \nonumber\\ & = \l( \frac{T}{b} \r)^{p\eta_r^2-1} \min_{\U\in\GR(n,r)} \underset{y\sim \mu}{\E}\l\| y - \P_{\U} y\r\|_2^2, $$ see Program . That is, the output of $\alg$ is sub-optimal for Program by a polynomial factor in $T$, which is negligible if the covariance matrix ${\boldsymbol{\Xi}}$ of the data distribution $\mu$ is well-conditioned and has a small residual, <span><span> as discussed earlier.</span></span> <span><span> As the closing remark, Section 3 of the supplementary material applies Theorem \[thm:stochastic result\] to the popular spiked covariance model as a special case, outlines the proof technique, and discusses extension to non-Gaussian stochastic models.</span></span> Prior Art \[sec:lit review\] ============================ In this paper, we presented $\alg$ for streaming (linear) dimensionality reduction, an algorithm with (nearly) minimal storage and computational requirements. <span><span> We can</span></span> think of $\alg$ as an online "subspace tracking" algorithm that identifies the linear structure of data as it arrives. Once the data has fully arrived, both principal components and the projected data are <span><span> already</span></span> made available by $\alg$<span><span> , ready for any additional processing.</span></span> <span><span>. At iteration $t$ and given the (truncated) SVD of $\Y_{t-1}$, iSVD aims to compute the (truncated) SVD of $\Y_t = [\Y_{t-1}\; y_t] \in\R^{n\times t}$, where $y_t\in\R^{n}$ is the newly arrived data vector and $\Y_{t-1}$ is the matrix formed by concatenating the previous data vectors</span></span> @bunch1978rank [@brand2006fast; @brand2002incremental; @comon1990tracking; @li2004incremental]. $\alg$ generalises iSVD to handle data blocks; see Algorithm \[alg:MOSES\]. This <span><span> minor generalisation</span></span> in part enables us to complement $\alg$ <span><span> (and iSVD)</span></span> with comprehensive statistical analysis in Theorem \[thm:stochastic result\], which has been lacking despite the popularity and empirical success of iSVD. <span><span> In fact</span></span>, @balsubramani2013fast only very recently provided stochastic analysis for two of the variants of iSVD in @krasulina1969method [@oja1983subspace]. The results in @balsubramani2013fast hold in expectation and for the special case of $r=1$, the first leading principal component. Crucially, these results measure the angle $\angle[\SU_{T,r},\wh{\SU}_{T,r}]$ between the true leading principal components of the data matrix and those estimated by iSVD. Such results are <span><span> therefore</span></span> inconclusive because <span><span> they are silent about the dimensionality reduction task <span><span> of iSVD</span></span>. Indeed,</span></span> iSVD <span><span> can</span></span> estimate both left and right leading singular vectors of the data matrix, namely, iSVD <span><span> can estimate</span></span> both the leading principal components of the data matrix $\wh{{\boldsymbol{S}}}_{T,r}$ *and* reduce the dimension of data by computing $\wh{{\boldsymbol{S}}}_{T,r}^* \wh{\Y}_{T,r}\in \R^{r\times T}$, where $\wh{{\boldsymbol{S}}}_{T,r}$ and $\wh{\Y}_{T,r}$ are the final outputs of iSVD. <span><span> Unlike</span></span> @balsubramani2013fast, Theorem \[thm:stochastic result\] and specifically assesses the quality of both of these tasks and establishes that, under certain conditions, $\alg$ performs nearly as well as <span><span> the</span></span> offline <span><span> truncated</span></span> SVD. $\operatorname{GROUSE}$ @balzano2013grouse is another algorithm for streaming PCA<span><span> , for data with possibly missing entries. GROUSE</span></span> can be interpreted as projected stochastic gradient descent on the Grassmannian manifold. GROUSE is effectively identical to iSVD when the incoming data is low-rank @balzano2013grouse. In @zhang2016global and <span><span> on the basis of</span></span> @balsubramani2013fast, the authors offer theoretical guarantees for GROUSE that again does <span>not</span> account for <span><span> the quality of dimensionality reduction</span></span>. Their results hold without any missing data, in expectation, and in a setup similar to the spiked covariance model. An alternative to GROUSE is SNIPE that has stronger theoretical guarantees in <span><span> the</span></span> case of missing data @eftekhari2016snipe [@eftekhari2016expect]. In Section \[sec:numerics\], we will numerically compare $\alg$ with GROUSE. <span><span> The closely-related method of Frequent Directions (FD) replaces the hard thresholding of the singular values in iSVD with soft thresholding @ghashami2016frequent [@desai2016improved]. Later, robust FD @luo2017robust improved the performance of FD and addressed some of its numerical issues. On the algorithmic side, FD keeps an estimate of ${\boldsymbol{S}}_{t,r} {\boldsymbol{\Gamma}}_{t,r}$, whereas $\alg$ also calculates the projected data, namely, it keeps an estimate of $\{{\boldsymbol{S}}_{t,r},{\boldsymbol{\Gamma}}_{t,r},{\boldsymbol{Q}}_{t,r}\}_t$; see Algorithm \[alg:MOSES implement\]. In terms of guarantees, the available guarantees for FD control the error incurred in estimating the principal components, whereas Theorem \[thm:stochastic result\] for $\alg$ also controls the error incurred in <span><span> the</span></span> dimensionality reduction step. Indeed, $$\begin{aligned} & \l\| {\boldsymbol{S}}_{T,r} {\boldsymbol{\Gamma}}_{T,r}^2 {\boldsymbol{S}}_{T,r}^* - \wh{{\boldsymbol{S}}}_{T,r} \wh{{\boldsymbol{\Gamma}}}_{T,r}^2 \wh{{\boldsymbol{S}}}_{T,r}^* \r\|_F \nonumber\\ & \le \| {\boldsymbol{Y}}_{T,r} - \wh{{\boldsymbol{Y}}}_{T,r} \|_F \cdot \l( \|{\boldsymbol{Y}}_{T,r}\| + \|\wh{{\boldsymbol{Y}}}_{T,r}\| \r ),\end{aligned}$$ namely, Theorem \[thm:stochastic result\] is a more general result than those exemplified by Theorem 1.1 in @ghashami2016frequent which, except for symmetric matrices, do not convey any information about the row-span. Another key difference is that Theorem \[thm:stochastic result\] is a stochastic result versus the deterministic Theorem 1.1 in @ghashami2016frequent and similar results. Indeed, an intermediate step to prove Theorem \[thm:stochastic result\] is the deterministic Lemma 2 in the supplementary material. An important feature of this work is to translate Lemma 2 into a stochastic result in learning theory, of interest to the machine learning and statistical signal processing communities. In Section \[sec:numerics\], we will numerically compare MOSES with FD. </span></span> <span><span> As detailed in Section 4 of the supplementary material, $\alg$ can be adapted to the dynamic case, where the distribution of data changes over time. This is achieved by using a "forgetting factor" in Step b of Algorithm \[alg:MOSES\]. Such an extension is crucial, as there are pathological examples where (static) $\alg$ and iSVD both fail to follow the changes in the distribution of data @desai2016improved. This important research direction is left for future work. </span></span> One might also view $\alg$ as a stochastic algorithm for PCA. Indeed, note that Program is equivalent to $$\begin{aligned} \begin{cases} \max \,\,\, \underset{y\sim\mu}{\E} \| {\boldsymbol{U}} {\boldsymbol{U}}^* y \|_F^2 \\ {\boldsymbol{U}}^* {\boldsymbol{U}} = {\boldsymbol{I}}_r \end{cases} & = \begin{cases} \max \,\,\, \underset{y\sim\mu}{\E} \langle {\boldsymbol{U}} {\boldsymbol{U}}^*, y y^* \rangle \\ {\boldsymbol{U}}^* {\boldsymbol{U}} = {\boldsymbol{I}}_r \end{cases} \nonumber\\ &= \begin{cases} \max \,\,\, \underset{y\sim\mu}{\E} \langle {\boldsymbol{U}} {\boldsymbol{U}}^*, y y^* \rangle \\ {\boldsymbol{U}}^* {\boldsymbol{U}} \preccurlyeq {\boldsymbol{I}}_r, \end{cases} \label{eq:prg review}\end{aligned}$$ where the maximisation is over <span><span> the</span></span> matrix ${\boldsymbol{U}}\in\R^{n\times r}$. Above, ${\boldsymbol{U}}^*{\boldsymbol{U}}\preccurlyeq {\boldsymbol{I}}_r$ is the unit ball with respect to the spectral norm and ${\boldsymbol{A}} \preccurlyeq {\boldsymbol{B}}$ means that ${\boldsymbol{B}}-{\boldsymbol{A}}$ is a positive semi-definite matrix. The last identity above holds because a convex function is always maximised on the boundary of the feasible set. <span><span> With</span></span> the Schur complement, we can equivalently write the last program above as $$\begin{aligned} \begin{cases} \max \,\,\, \underset{y\sim\mu}{\E} \langle {\boldsymbol{U}} {\boldsymbol{U}}^*, y y^* \rangle \\ \l[ \begin{array}{cc} {\boldsymbol{I}}_n & {\boldsymbol{U}} \\ {\boldsymbol{U}}^* & {\boldsymbol{I}}_r \end{array} \r] \succcurlyeq {\boldsymbol{0}}\end{cases} & = \begin{cases} \max \,\,\, \langle {\boldsymbol{U}} {\boldsymbol{U}}^*, {\boldsymbol{\Xi}} \rangle \\ \l[ \begin{array}{cc} {\boldsymbol{I}}_n & {\boldsymbol{U}} \\ {\boldsymbol{U}}^* & {\boldsymbol{I}}_r \end{array} \r] \succcurlyeq {\boldsymbol{0}},\end{cases} \label{eq:sdp formulation}\end{aligned}$$ where ${\boldsymbol{\Xi}}=\E [yy^*] \in\R^{n\times n}$ is the covariance matrix of the data distribution $\mu$. Program has a convex (in fact, quadratic) objective function that is *maximised* on a convex (conic) feasible set. We cannot hope to directly compute the gradient of the objective function above <span><span> (namely, $2{\boldsymbol{\Xi}}{\boldsymbol{U}}$)</span></span> because the distribution of $y$ and hence its covariance matrix ${\boldsymbol{\Xi}}$ are unknown. Given an iterate $\h{{\boldsymbol{S}}}_{t}$, one might instead draw a random vector $y_{t+1}$ from the probability measure $\mu$ and move along the direction $2y_{t+1}y_{t+1}^*\h{{\boldsymbol{S}}}_t$, motivated by the observation that $\E [2y_{t+1}y_{t+1}^*\h{{\boldsymbol{S}}}_t ]= 2{\boldsymbol{\Xi}}\widehat{{\boldsymbol{S}}}_t$. This is then followed by back projection onto the feasible set of Program . That is, $$\h{{\boldsymbol{S}}}_{t+1} = \mathcal{P}\l({\boldsymbol{S}}_t + 2\alpha_{t+1} y_{t+1}y_{t+1}^* \h{{\boldsymbol{S}}}_t \r),$$ for an appropriate step size $\alpha_{t+1}$. Above, $\mathcal{P}({\boldsymbol{A}})$ projects onto the unit spectral norm ball by setting to one all singular values of ${\boldsymbol{A}}$ that exceed one. The stochastic projected gradient ascent for PCA, described above, is itself closely related to the so-called *power method* and is at the heart of @mitliagkas2013memory [@oja1985stochastic; @sanger1989optimal; @kim2005iterative; @arora2012stochastic], all lacking a statistical analysis similar to Theorem \[thm:stochastic result\]. One notable exception is the power method in @mitliagkas2013memory which in a sense applies *mini-batch* stochastic projected gradient ascent to solve Program , with data blocks (namely, batches) of size $b=\Omega(n)$. There the authors offer statistical guarantees for the spiked covariance model, defined in Section \[sec:results\] of the supplementary material. As before, these guarantees are for the quality of estimated principal components and silent about the quality of projected data, which is addressed in Theorem \[thm:stochastic result\]. Note also that, especially when the data dimension $n$ is large, one disadvantage of this approach is its large block size; it takes a long time <span><span> (namely, $\Omega(n)$ iterations)</span></span> for the algorithm to update its estimate of the principal components,<span><span> a big disadvantage in the dynamic case.</span></span> In this setup, we may think of $\alg$ as a stochastic algorithm for PCA based on alternative minimisation rather than gradient ascent, as detailed in Section 3 of the supplementary material. Moreover, $\alg$ updates its estimate frequently, after receiving every $b=O(r)$ data vectors, and also maintains the projected data. In Section \[sec:numerics\], we numerically compare $\alg$ with the power method in @mitliagkas2013memory. A few closely related works are @hardt2014noisy [@de2014global; @jain2016streaming; @de2014global]. In the context of online learning and *regret minimisation*, @warmuth2008randomized [@arora2012stochastic] offer two algorithms, the former of which is not memory optimal and the latter does not have guarantees similar to Theorem \[thm:stochastic result\]; see also @boutsidis2015online. A Bayesian approach to PCA is studied in @roweis1998algorithms [@tipping1999probabilistic] and the *expectation maximisation* algorithm therein could be implemented in an online fashion but without theoretical guarantees. <span><span> More generally, $\alg$ might be interpreted as a deterministic *matrix sketching* algorithm. Common sketching algorithms either randomly sparsify a matrix, randomly combine its rows (columns), or randomly subsample its rows (columns) according to its *leverage scores* @tropp2017fixed [@chiu2013sublinear; @pourkamali2016randomized; @gittens2016revisiting; @ghashami2016frequent; @gilbert2012sketched]. In particular, FD was observed to outperform random sketching algorithms in practice @ghashami2016frequent. The relation between streaming algorithms and distributed computing is also perhaps worth pointing out; see Figure \[fig:cone tree\] of the supplementary material and @iwen2016distributed [@sameh2005parallel]</span></span>. Lastly, when the data vectors have missing entries, a closely related problem is low-rank matrix completion @davenport2016overview [@candes2009exact; @eftekhari2018weighted; @eftekhari2016mc]. Experiments \[sec:numerics\] ============================ In this section, we investigate the numerical performance of $\alg$ and compare it against <span><span> competing algorithms, namely</span></span>, GROUSE @balzano2013grouse, <span><span> the method of frequent directions (FD) @desai2016improved [@luo2017robust],</span></span> and the power method (PM) @mitliagkas2014streaming, <span><span> all detailed in Section \[sec:lit review\].</span></span> <span><span> On both synthetic and real-world datasets,</span></span> we reveal one by one the data vectors $\{y_t\}_{t=1}^T\subset \mathbb{R}^n$ and, for every $t$, <span><span> wish</span></span> to compute a rank-$r$ truncated SVD of <span><span> $[y_1,\cdots,y_t]$, the data arrived so far.</span></span> For the tests <span><span> on synthetic datasets</span></span>, the vectors $\{y_t\}_{t=1}^T$ are drawn independently from a zero-mean Gaussian distribution with <span><span> the</span></span> covariance matrix ${\boldsymbol{\Xi}}={\boldsymbol{S}}{\boldsymbol{\Lambda}}{\boldsymbol{S}}^*$, where ${\boldsymbol{S}}\in \text{O}(n)$ is a generic orthonormal basis obtained by orthogonalising a standard random Gaussian matrix. The entries of the diagonal matrix ${\boldsymbol{\Lambda}}\in\mathbb{R}^{n\times n}$ (the eigenvalues of the covariance matrix ${\boldsymbol{\Xi}}$) are selected according to the power law<span><span> , namely,</span></span> $\lambda_i = i^{-\alpha}$, for a positive $\alpha$. To be more succinct, where possible we <span><span> will</span></span> use <span>MATLAB</span>'s notation for specifying the value ranges in this section. To assess the performance of $\alg$, let $\Y_t=[y_1,\cdots,y_t]\in \mathbb{R}^{n\times t}$ be the data received by time $t$ and let $\widehat{\Y}^m_{t,r}$ be the output of $\alg$ at time $t$.[^2] Then the error incurred by $\alg$ is $$\frac{1}{t}\|\Y_t - \widehat{\Y}^m_{t,r}\|_F^2,$$ see Theorem \[thm:stochastic result\]. Recall from that the above error is always larger than the residual of $\Y_t$, namely $$\|\Y_t - \widehat{\Y}^m_{t,r}\|_F^2 \ge \|\Y_t - {\Y}_{t,r}\|_F^2 = \rho_r^2(\Y_t),$$ see . Above, ${\Y}_{t,r}=\SVD_r(\Y_t)$ is a rank-$r$ truncated SVD of $\Y_t$ and $\rho_r^2(\Y_t)$ is the corresponding residual. Later in this section, we compare $\alg$ against <span>GROUSE</span> @balzano2013grouse, <span><span> FD @desai2016improved</span></span>, <span><span> PM</span></span> @mitliagkas2013memory, described in Section \[sec:lit review\]. <span><span> In contrast with MOSES,</span></span> these algorithms only estimate the principal components of the data. More specifically, <span><span> let $\widehat{\SU}_{t,r}^g \in \text{G}(n,r)$ be the span of the output of GROUSE, with the outputs of the other algorithms defined similarly.</span></span> These algorithms then incur the errors $$\frac{1}{t} \| \Y_t - \P_{\widehat{\SU}_{t,r}^g} \Y_t \|_F^2, \qquad \frac{1}{t} \| \Y_t - \P_{\widehat{\SU}_{t,r}^f} \Y_t \|_F^2,$$ $$\frac{1}{t} \| \Y_t - \P_{\widehat{\SU}_{t,r}^p} \Y_t \|_F^2,$$ respectively. Above, $\P_{\mathcal{A}}\in \mathbb{R}^{n\times n}$ is the orthogonal projection onto the subspace $\mathcal{A}$. <span><span> Even though robust FD @luo2017robust improves over FD in the quality of matrix sketching, since the subspaces produced by FD and robust FD coincide, there is no need here for computing a separate error for robust FD.</span></span> We now set out to do various tests and report the results. <span><span> To ensure the reproducibility of our results, both the accompanying MATLAB code and the datasets used are publicly available</span></span>.[^3]\ **Ambient dimension:** On a synthetic dataset with $\alpha =1$ and $T=2000$, we first test $\alg$ by varying the ambient dimension as $n\in\{200:200:1200\}$, and setting the rank and block size to $r=15$, $b=2r=30$. The average error over ten trials is reported in Figure \[fig:num\_eval\_mos\_scaling\_var\_n\]. Note that the error is increasing in $n$, <span><span> which indeed agrees with Theorem \[thm:stochastic result\], as detailed in the supplementary material under the discussion of the spiked covariance model in Section \[sec:results\] therein. </span></span> <span>**Block size:**</span> On a synthetic dataset with $\alpha =1$ and $T=2000$, we test $\alg$ by setting the ambient dimension and rank to $n=1200$, $r=15$, and varying the block size as $b\in\{r:r:15r\}$. The average error over ten trials is reported in Figure \[fig:num\_eval\_mos\_scaling\_var\_b\]. Note that $\alg$ is robust against the choice of the block size and that, at the extreme case of $b=T$, error vanishes and $\alg$ reduces to offline truncated SVD. <span><span> This is predicted by Theorem \[thm:stochastic result\], as seen in . </span></span> <span>**Rank:**</span> On a synthetic dataset with $\alpha =1$ and $T=2000$, we test $\alg$ by setting the ambient dimension and block size to $n=1200$, $b=2r$, and varying the rank as $r\in\{5:5:25\}$. The average error over ten trials is reported in Figure \[fig:num\_eval\_mos\_scaling\_var\_r\]. As expected, the error is decreasing in the dimension $r$ of the subspace that we fit to the data and in fact, at the extreme case of $r=n$, there would be no ralphmiller@example.com. <span><span> This observation is corroborated with Theorem \[thm:stochastic result\] and, in particular, .</span></span> <span>**Comparisons on synthetic datasets:**</span> On synthetic datasets with $\alpha\in\{0.01,0.1,0.5,1\}$ and $T=2000$, we compare $\alg$ against GROUSE, <span><span> FD, and PM</span></span>.[^4] More specifically, we set the ambient dimension to $n=200$ and the rank to $r=10$. For $\alg$, the block size was set to $b=2r$. <span><span> For GROUSE, we set the step size to $2$. For FD and PM, the block size was set to $2r=20$ and $2n=400$,</span></span> respectively, as these values seemed to produced the best results overall for these algorithms. Both GROUSE and PM were initialised randomly, as prescribed in @balzano2013grouse [@mitliagkas2014streaming], <span><span> while FD does not require any initialisation</span></span>. The average errors of all three algorithms over ten trials versus time is shown in Figure \[fig:num\_eval\_mos\_synth\]. Because of its large blocks size of $O(n)$ @mitliagkas2014streaming, PM updates its estimate of the principal components much slower than $\alg$, but the two algorithms converge to similar errors. The slow updates of <span><span> PM is a major problem in a</span></span> dynamic scenario, where the distribution of data changes over time. We will also see later that $\alg$ is much faster than <span><span> PM and performs better on the real datasets we tested.</span></span> We <span><span> next</span></span> evaluate all these <span><span> four</span></span> algorithms on publicly-available <span><span> sensor network data</span></span>; we use four different datasets that contain *mote* (sensor node) voltage, humidity, light, and temperature measurements over time @deshpande2004model. <span>**Mote voltage dataset:**</span> The first dataset we evaluate has an ambient dimension of $n=46$ and has $T=7712$ columns. With $r=20$ and the rest of the parameters as described in the synthetic comparison above, the errors over time for all algorithms is shown in Figure \[fig:num\_eval\_mos\_real\_volt\] in logarithmic scale. $\alg$ <span><span> here outperforms GROUSE, FD, and PM</span></span>. <span>**Mote humidity dataset:**</span> The second dataset evaluated has an ambient dimension of $n=48$ and has $T=7712$ columns. This dataset contains the humidity measurements of motes. With $r=20$ and the rest of the parameters as described in the synthetic comparison above, the errors over time for all algorithms is shown in <span><span> Figure</span></span> \[fig:num\_eval\_mos\_real\_humidity\] in logarithmic scale. $\alg$ again outperforms the <span><span> other algorithms</span></span>. <span>**Mote light dataset:**</span> The third dataset has an ambient dimension $n=48$ and has $T=7712$ columns. This dataset contains the light measurements of the motes. With $r=20$ and the rest of the parameters as described in the synthetic comparison above, the errors over time for all algorithms is shown in in logarithmic scale. As before, $\alg$ outperforms the <span><span> competing</span></span> algorithms. <span>**Mote temperature dataset:**</span> The last real dataset we consider in this instance has an ambient dimension of $n=56$ and has $T=7712$ columns. This dataset contains the temperature measurements of the sensor motes and has mostly periodic value changes and infrequent spikes. With $r=20$ and the rest of the parameters as described in the synthetic comparison above, the errors over time for all algorithms is shown in <span><span> Figure</span></span> \[fig:num\_eval\_mos\_real\_temp\] in logarithmic scale. It is evident that $\alg$ outperforms the other <span><span> competing</span></span> algorithms. <span><span> <span>**Storage:**</span> We also performed memory complexity tests for all mote datasets above. Our experiments showed that often $\alg$ required the least amount of memory allocation against competing methods. Specifically, $\alg$ required $189.36$ Kb, $92.25$Kb, $127.02$Kb, and $215.97$Kb for the voltage, humidity, light, and temperature datasets, respectively. PM required $572.06$Kb, $638.80$Kb, $548.63$Kb, and $682.59$Kb, GROUSE required $2896.87$Kb, $2896.45$Kb, $2897.45$Kb, and $3769.42$Kb, and finally FD required $173.86$Kb, $281.82$Kb, $194.32$ Kb, $655.78$Kb for the same datasets. </span></span> <span>**Complexity on synthetic datasets:**</span> Let us now turn our attention to the computational <span><span> efficiency</span></span> of these <span><span> four</span></span> algorithms. On synthetic datasets with $\alpha = 1$ and <span><span> $T=10000$</span></span>, we compare the run-time of $\alg$ against <span><span> GROUSE, FD, and PM, with the parameters set as described in the synthetic tests earlier</span></span>. This simulation was carried out <span><span> using</span></span> <span>MATLAB</span> <span><span> 2018b</span></span> on a 2012 Mac Pro configured with Dual $6$-core Intel Xeon X5690 with $64$GB of <span>DDR3</span> <span>ECC</span> <span>RAM</span>. The average run-time of all three algorithms over five trials and for various choices of rank $r$ is shown in Figure \[fig:comp\_eval\_mos\]. We note that the computational cost of $\alg$ remains consistently small throughout these simulations, especially for large ambient dimensions and ranks where GROUSE and PM perform poorly <span><span> regardless of the desired recovery rank $r$ used; see <span><span> Figure</span></span> \[fig:comp\_eval\_mos\_r50\]. Interestingly enough, FD performs poorly when attempting a relatively low rank recovery ($r\in \{1,10\}$) and closely matches $\alg$ as $r$ increases, which can be attributed to the buffering size of FD.</span></span> \ \ **<span>Supplementary Material</span>** Overview ======== The supplementary material contains more details about MOSES, an optimisation interpretation of MOSES, the proofs of the main results, as well as the acknowledgements. Storage and Computational Requirements of MOSES \[sec:intro\] ============================================================= The efficient implementation of $\alg$ in Algorithm \[alg:MOSES implement\] is based on the ideas from incremental SVD and it is straightforward to verify that Algorithms \[alg:MOSES\] and \[alg:MOSES implement\] are indeed equivalent; at iteration $k$, the relation between the output of Algorithm \[alg:MOSES\] ($\wh{\Y}_{kb,r}$) and the output of Algorithm \[alg:MOSES implement\] ($\wh{{\boldsymbol{S}}}_{kb,r},\wh{{\boldsymbol{\Gamma}}}_{kb,r},\wh{{\boldsymbol{Q}}}_{kb,r}$) is $$\wh{\Y}_{kb,r}\overset{\text{SVD}}{=}\wh{{\boldsymbol{S}}}_{kb,r}\wh{{\boldsymbol{\Gamma}}}_{kb,r}\wh{{\boldsymbol{Q}}}_{kb,r}^*,$$ where the right-hand side above is the SVD of $\wh{\Y}_{kb,r}$. More specifically, $\wh{{\boldsymbol{S}}}_{kb,r} \in\mathbb{R}^{n\times r}$ has orthonormal columns and is the $\alg$'s estimate of leading $r$ principal components of $\Y_{kb}\in \mathbb{R}^{n\times kb}$, where we recall that $\Y_{kb}$ is the data received so far. Moreover, $$\wh{{\boldsymbol{S}}}_{kb,r}^* \wh{\Y}_{kb,r}= \wh{{\boldsymbol{\Gamma}}}_{kb,r}\wh{{\boldsymbol{Q}}}_{kb,r}^*\in \mathbb{R}^{r\times kb}$$ is the projection of $\wh{\Y}_{kb,r}$ onto this estimate, namely $\wh{{\boldsymbol{S}}}_{kb,r}^* \wh{\Y}_{kb,r}$ is $\alg$'s estimate of the projected data matrix so far. In words, the efficient implementation of $\alg$ in Algorithm \[alg:MOSES implement\] explicitly maintains estimates of both principal components and the projected data, at every iteration. Let us now evaluate the storage and computational requirements of $\alg$. At the start of iteration $k$, Algorithm \[alg:MOSES implement\] stores the matrices $$\wh{{\boldsymbol{S}}}_{(k-1)b,r}\in\mathbb{R}^{n\times r}, \qquad \wh{{\boldsymbol{\Gamma}}}_{(k-1)b,r} \in \mathbb{R}^{r\times r}, \qquad \wh{{\boldsymbol{Q}}}_{(k-1)b,r} \in\mathbb{R}^{(k-1)b\times r},$$ and after that also receives and stores the incoming block $\y_{k}\in\mathbb{R}^{n\times b}$. This requires $O(r(n + (k-1)b+1))+O(bn)$ bits of memory, because $\widehat{{\boldsymbol{\Gamma}}}_{(k-1)b,r}$ is diagonal. Assuming that $b=O(r)$, Algorithm \[alg:MOSES implement\] therefore requires $O(r(n+kr))$ bits of memory at iteration $k$. Note that this is optimal, as it is impossible to store a rank-$r$ matrix of size $n\times kb$ with fewer bits when $b=O(r)$. It is also easy to verify that Algorithm \[alg:MOSES implement\] performs $O(r^2(n+kb))=O(r^2(n+kr))$ flops in iteration $k$. The dependence of both storage and computational complexity on $k$ is due to the fact that $\alg$ maintains both an estimate of principal components in $\wh{{\boldsymbol{S}}}_{kb,r}$ and an estimate of the projected data in ${\boldsymbol{\Gamma}}_{kb,r}{\boldsymbol{Q}}_{kb,r}^*$. To maximise the efficiency, one might optionally "flush out" the projected data after every $n/b$ iterations, as described in the last step in Algorithm \[alg:MOSES implement\]. Optimisation Viewpoint \[sec:opt view\] ======================================= $\alg$ has a natural interpretation as an approximate solver for the non-convex optimisation program underlying PCA, which serves as its motivation. More specifically, recall that leading $r$ principal components of $\Y_T$ are obtained by solving the non-convex program $$\min_{\U\in \GR(n,r)} \l\| \Y_T - \P_{\U} \Y_T\r\|_F^2, \label{eq:pca 1}$$ where the minimization is over the Grassmannian $\GR(n,r)$, the set of all $r$-dimensional subspaces in $\R^n$. Above, $\P_{\U}\in\R^{n\times n}$ is the orthogonal projection onto the subspace $\U$. By construction in Section \[sec:intro\], note that $$\begin{aligned} \Y_T & = \l[ \begin{array}{cccc} y_1 & y_2 & \cdots & y_T \end{array} \r] \qquad \mbox{(see \eqref{eq:conc of yts})} \nonumber\\ & = \l[ \begin{array}{cccc} \y_1 & \y_2 & \cdots & \y_K \end{array} \r] \in\R^{n\times T}, \label{eq:brk blcks}\end{aligned}$$ where $\{\y_k\}_{k=1}^K$ are the incoming blocks of data. This allows us to rewrite Program as $$\begin{aligned} \min_{\U\in \GR(n,r)} \l\| \Y_T - \P_{\U} \Y_T\r\|_F^2 & = \min_{\U\in \GR(n,r)} \sum_{k=1}^K \l\| \y_{k} - \P_{\U} \y_{k}\r\|_F^2 \qquad \text{(see \eqref{eq:brk blcks})} \nonumber\\ & = \begin{cases} \min \sum_{k=1}^K \l\| \y_{k} - \P_{\U_K}\cdots \P_{\U_k} \y_{k}\r\|_F^2 & \\ \U_1 = \U_2 = \cdots =\U_K, \label{eq:nested} \end{cases}\end{aligned}$$ where the last minimisation above is over all identical subspaces $\{\U_k\}_{k=1}^K\subset \GR(n,r)$. Our strategy is to make a sequence of approximations to the program in the last line above. In the first approximation, we only keep the first summand in the last line of . That is, our first approximation reads as $$\begin{aligned} \begin{cases} \min \sum_{k=1}^K \l\| \y_{k} - \P_{\U_K}\cdots \P_{\U_k} \y_{k}\r\|_F^2 & \\ \U_1 = \U_2 = \cdots =\U_K \end{cases} & \ge \begin{cases} \min \l\| \y_{1} - \P_{\U_K}\cdots \P_{\U_1} \y_{1}\r\|_F^2 & \\ \U_1 = \U_2 = \cdots =\U_K \end{cases} \nonumber\\ & = \min_{\U\in\GR(n,r)} \l\| \y_1 - \P_{\U}\y_1 \r\|_F^2,\end{aligned}$$ where the second line above follows by setting $\U =\U_1=\cdots =\U_K$. Let $\wh{\SU}_{b,r}$ be a minimiser of the program in the last line above. Note that $\wh{\SU}_{b,r}$ simply spans leading $r$ principal components of $\y_1$, akin to Program . This indeed coincides with the output of $\alg$ in the first iteration, because $$\begin{aligned} \wh{\Y}_{b,r} & = \SVD_r(\y_1) \qquad \mbox{(see Algorithm \ref{alg:MOSES})} \nonumber\\ & = \P_{\wh{\SU}_{b,r}}\y_1. \qquad \mbox{(similar to the second line of \eqref{eq:low-rank est kept})} \label{eq:first iteration checks out} \end{aligned}$$ Next consider the next approximation in which we keep two of the summands in the last line of , namely $$\begin{aligned} \begin{cases} \min \sum_{k=1}^K \l\| \y_{k} - \P_{\U_K}\cdots \P_{\U_k} \y_{k}\r\|_F^2 & \\ \U_1 = \U_2 = \cdots =\U_K \end{cases} & \ge \begin{cases} \min \l\| \y_{1} - \P_{\U_K}\cdots \P_{\U_1} \y_{1}\r\|_F^2 + \l\| \y_{2} - \P_{\U_K}\cdots \P_{\U_2} \y_{2}\r\|_F^2 & \\ \U_1 = \U_2 = \cdots =\U_K, \end{cases}\end{aligned}$$ and then we substitute $\U_1 = \wh{\SU}_{b,r}$ above to arrive at the new program $$\begin{aligned} & \begin{cases} \min \,\,\, \| \y_{1} - \P_{\U_K}\cdots \P_{\U_2} \P_{\wh{\SU}_{b,r}} \y_{1}\|_F^2 + \l\| \y_{2} - \P_{\U_K}\cdots \P_{\U_2} \y_{2}\r\|_F^2 & \\ \U_2 = \U_3 = \cdots =\U_K \end{cases} \nonumber\\ & = \min_{\U \in \GR(n,r)} \,\,\, \| \y_{1} - \P_{\U} \P_{\wh{\SU}_{b,r}} \y_{1}\|_F^2 + \l\| \y_{2} - \P_{\U} \y_{2}\r\|_F^2,\end{aligned}$$ where the second program above follows by setting $\U=\U_2=\cdots =\U_K$. We can rewrite the above program as $$\begin{aligned} & \min_{\U \in \GR(n,r)} \,\,\, \| \y_{1} - \P_{\U} \P_{\wh{\SU}_{b,r}} \y_{1}\|_F^2 + \l\| \y_{2} - \P_{\U} \y_{2}\r\|_F^2 \nonumber\\ & = \min_{\U\in \GR(n,r)} \,\,\, \l\| \l[ \begin{array}{cc} \y_1 - \P_{\U}\P_{\wh{\SU}_{b,r}} \y_1 & \y_2 - \P_{\U} \y_2 \end{array} \r] \r\|_F^2 \nonumber\\ & = \min_{\U\in\GR(n,r)} \,\,\, \l\| \l[ \begin{array}{cc} \P_{\wh{\SU}_{b,r}^\perp} \y_1 & {\boldsymbol{0}}_{n\times b} \end{array} \r] + \P_{\U^\perp} \l[ \begin{array}{cc} \P_{\wh{\SU}_{b,r}}\y_1 & \y_2 \end{array} \r] \r\|_F^2 \nonumber\\ & = \| \P_{\wh{\SU}_{b,r}^\perp} \y_1 \|_F^2 + \min_{\U\in\GR(n,r)} \,\,\, \l\| \P_{\U^\perp} \l[ \begin{array}{cc} \P_{\wh{\SU}_{b,r}}\y_1 & \y_2 \end{array} \r] \r\|_F^2 \qquad \text{(see the text below)} \nonumber\\ & = \| \P_{\wh{\SU}_{b,r}^\perp} \y_1 \|_F^2 + \min_{\U\in\GR(n,r)} \,\,\, \l\| \P_{\U^\perp} \l[ \begin{array}{cc} \wh{\Y}_{b,r} & \y_2 \end{array} \r] \r\|_F^2, \qquad \mbox{(see \eqref{eq:first iteration checks out})}\end{aligned}$$ and let $\wh{\SU}_{2b,r}$ be a minimiser of the last program above. Above, $\perp$ shows the orthogonal complement of a subspace. The second to last line above follows because $\wh{\SU}_{2b,r}$ is always within the column span of $[\P_{\wh{\SU}_{b,r}}\y_1\,\,\, \y_2]$. Note also that $\wh{\SU}_{2b,r}$ is the span of leading $r$ principal components of the matrix $[\wh{\Y}_{1,r}\,\,\, \y_2]$, similar to Program . This again coincides with the output of $\alg$ in the second iteration, because $$\begin{aligned} \wh{\Y}_{2b,r} & = \SVD_r\l( \l[ \begin{array}{cc} \wh{\Y}_{b,r} & \y_2 \end{array} \r] \r) \qquad \mbox{(see Algorithm \ref{alg:MOSES})} \nonumber\\ & = \P_{\wh{\SU}_{2b,r}} \l[ \begin{array}{cc} \wh{\Y}_{b,r} & \y_2 \end{array} \r]. \qquad \mbox{(similar to the second line of \eqref{eq:low-rank est kept})}\end{aligned}$$ Continuing this procedure precisely produces the iterates of $\alg$. Therefore we might interpret $\alg$ as an optimisation algorithm for solving Program by making a sequence of approximations. Spiked Covariance Model and Additional Remarks\[sec:results\] ============================================================= A popular model in the statistics literature is the <span>spiked covariance</span> model, where the data vectors $\{y_t\}_{t=1}^T$ are drawn from a distribution with a covariance matrix ${\boldsymbol{\Xi}}$. Under this model, ${\boldsymbol{\Xi}}$ is a low-rank perturbation of the identity matrix @johnstone2001distribution [@vershynin2012close], namely $\lambda_1({\boldsymbol{\Xi}}) = \cdots =\lambda_r({\boldsymbol{\Xi}})=\lambda$ and $\lambda_{r+1}({\boldsymbol{\Xi}})=\cdots =\lambda_n({\boldsymbol{\Xi}})=~1$. Proposition \[prop:first app\] in this case reads as $$\E \|y-\P_{{\SU}_{T,r}} y\|_2^2 \propto {{ (n-r)}} + {{(n-r) \lambda \sqrt{\frac{ {\log T} }{T}}}}, \label{eq:sp cov 1}$$ where ${\SU}_{T,r}$ spans leading $r$ principal components of the data matrix $\Y_T$. In contrast, Theorem \[thm:stochastic result\] roughly speaking states that $$\E \|y-\P_{\wh{\SU}_{T,r}} y\|_2^2 \propto (n-r) \l( \frac{T\lambda}{bn}\r)^{\frac{n}{\lambda}} + {{(n-r) \lambda \sqrt{\frac{ {\log T} }{T}}}}, \label{eq:sp cov 2}$$ where $\wh{\SU}_{T,r}$ spans the output of $\alg$. When $\lambda\gtrsim n \log (T/b) = n\log K$ in particular, we find that the error bounds in (\[eq:sp cov 1\],\[eq:sp cov 2\]) are of the same order. That is, under the spiked covariance model, $\alg$ for streaming truncated SVD matches the performance of "offline" truncated SVD, provided that the underlying distribution has a sufficiently large spectral gap. In practice, (\[eq:sp cov 2\]) is often a conservative bound. #### Proof strategy. {#rem:proof} Starting with , the proof of Theorem \[thm:stochastic result\] in Section \[sec:theory\] of the supplementary material breaks down the error associated with $\alg$ into two components as $$\begin{aligned} \E_y\| y - \P_{\wh{\SU}_{T,r}}y \|_2 & \le \frac{1}{T} \| \Y_T - \P_{\wh{\SU}_{T,r}}\Y_T\|_F^2 + \l| \frac{1}{T} \|\Y_T -\P_{\wh{\SU}_{T,r} }\Y_T\|_F^2 - \E_y\| y - \P_{\wh{\SU}_{T,r}}y \|_2^2 \r|. \label{eq:brk down of error rem}\end{aligned}$$ That is, we bound the population risk with the empirical risk. We control the empirical risk in the first part of the proof by noting that $$\begin{aligned} \|\Y_T-\P_{\wh{\SU}_{T,r}} \Y_T\|_F & = \| \P_{\wh{\SU}_{T,r}^{\perp} } \Y_T\|_F \nonumber\\ & = \| \P_{\wh{\SU}_{T,r}^{\perp} } ( \Y_T - \wh{\Y}_{T,r})\|_F \qquad \mbox{(see \eqref{eq:span of output of MOSES})} \nonumber\\ & \le \| \Y_T - \wh{\Y}_{T,r}\|_F, \end{aligned}$$ where the last line gauges how well the output of $\alg$ approximates the data matrix $\Y_T$, see . We then bound $\|\Y_T-\wh{\Y}_{T,r}\|_F$ in two steps: As it is common in these types of arguments, the first step finds a deterministic upper bound for this norm, which is then evaluated for our particular stochastic setup. - The deterministic bound appears in Lemma \[lem:online trunc SVD\] and gives an upper bound for $\|\Y_T -\wh{\Y}_{T,r}\|_F$ in terms of the overall "innovation". Loosely speaking, the innovation $\| \P_{\SU_{(k-1)b,r}^\perp} \y_k\|_F$ at iteration $k$ is the part of the new data block $\y_k$ that cannot be described by the leading $r$ principal components of data arrived so
{'source': 'arXiv_out/1806'}