\section{Nearly Optimal Robust Subspace Tracking (NORST)}\label{sec:norst}
 


In this section, we define the robust ST problem, explain the assumptions needed to make it identifiable, and then explain our proposed mini-batch solution and its guarantee. 


\subsection{Problem setting and algorithm design constraints}
At each time $t$, we observe a data vector $\yt \in \Re^n$ that satisfies
\bea
\yt := \lt + \x_t + \v_t, \text{ for } t = 1, 2, \dots, \tmax
\label{orpca_eq}
\eea
where  $\v_t$ is small unstructured noise, $\xt$ is the sparse outlier vector, and $\lt$ is the true data vector that lies in a fixed or slowly changing low-dimensional subspace of $\Re^n$, i.e.,
\[
\lt = \P_{(t)} \a_t
\]
where $\P_{(t)}$ is an $n \times r$ basis matrix with $r \ll n$ and with $\|(\I - \P_{(t-1)}\P_{(t-1)}{}')\P_{(t)}\|$ small compared to $\|\P_{(t)}\|=1$. 
We use $\T_t$ to denote the support set of $\xt$. As an example, in the video application, $\yt$ is the video image at time/frame $t$, $\lt$ is the background  at time $t$, $\T_t$ is the support of the foreground at $t$, and $\x_t$ equals the difference between foreground and background images on $\T_t$ while being zero everywhere else. Slow subspace change is typically a valid assumption for background images of videos taken using a static camera.
Given a good initial subspace estimate, $\Phat_{0}$, the goal is to develop a mini-batch algorithm to track $\Span(\P_{(t)})$ and $\lt$ either immediately or within a short delay.
A by-product is that $\x_t$, and $\T_t$ can also be tracked accurately. The initial subspace estimate, $\Phat_0$, can be computed  by applying a few iterations of any existing RPCA solutions, e.g., PCP \cite{rpca} or AltProj \cite{robpca_nonconvex}, on the first order $r$ data points, i.e., on $\Y_{[1,t_\train]}$, with $t_\train=Cr$.


\subsubsection{Dynamic RPCA} This is the offline version of the above problem. Define matrices $\L,\S,\V,\Y$ with $\L = [\l_1,\l_2, \dots \l_{\tmax}]$ and with $\Y,\S,\V$ similarly defined.  The goal is to recover $\L$ and its column space with accuracy $\zz$. We use $\rmat$ to denote the rank of $\L$. 
The maximum fraction of nonzeros in any row (column) of the outlier matrix $\S$ is denoted by $\outfracrow$ ($\outfraccol$).


\subsubsection{Algorithm constraints}
We will develop a nearly real-time tracking algorithm that (i) computes {\em an} online estimate of $\xt$ and its support $\T_t$, and of $\lt$ immediately at each time $t$ using the previous subspace estimate, $\Phat_{(t-1)}$, and observed data $\yt$; (ii) it updates the subspace estimates in a mini-batch fashion; and (iii) it provides improved smoothing estimates of all quantities after a delay that is within log factors of $r$. 
As we explain in Sec. \ref{tradeoffs}, recovering $\xt$, $\T_t$, and $\lt$, one at a time is the only way to obtain improved row-wise outlier tolerance compared to standard RPCA. However with doing this, correct recovery requires one extra assumption: slow enough subspace change compared to the minimum outlier magnitude. 


\subsection{Nearly Optimal Robust ST (NORST) via Recursive Projected Compressive Sensing (CS): main idea}
The algorithm begins with an initial subspace estimate $\Phat_0$. At each time $t$, we use $\Phat_{(t-1)}$ and $\yt$ to solve a noisy projected compressive sensing (CS) problem to estimate $\xt$ and its support $\T_t$ from $\tty_t = \bpsi \xt + \bt$. Here $\bpsi = \I -  \Phat_{(t-1)}\Phat_{(t-1)}{}'$, $\tty_t = \bpsi \yt$, and $\bt = \bpsi \lt +\bpsi \vt $ (is small under the slow subspace change assumption). This step uses $l_1$ minimization followed by thresholding to estimate $\T_t$, and Least Squares (LS) on $\That_t$ to get $\xhat_t$.
We compute $\lhat_t$ by subtraction as $\lhat_t = \yt - \xhat_t$. Every $\alpha$ time instants, we update the subspace estimate by solving the PCA problem using the previous $\alpha$ $\lhat_t$'s as observed data, i.e., by $r$-SVD on $\Lhat_{t;\alpha}$. This  is repeated $K$ times, each time with a new set of $\alpha$ $\lhat_t$'s. At this point, the algorithm enters the subspace change detect phase. The complete algorithm is specified in Algorithm \ref{algo:auto-reprocs-pca}, and explained in detail in Sec \ref{algo_details}. Besides $\alpha$ and $K$, it has two other parameters: $\xi$ (assumed upper bound on $\|\bt\|$) and $\omega_{supp}$ (threshold used for support recovery).


\subsection{Identifiability and other assumptions}
For this discussion assume that $\vt =0$. At each time $t$ we have just one $n$-length observed data vector $\yt$ but the subspace $\Pt$ is specified by $nr$ scalars (it is an $r$-dimensional subspace of $\Re^n$).

Thus, even if we had perfect data $\yt=\lt$ available, it would be impossible to exactly recover each different $\Pt$. 
One way to address this is by assuming that the $\Pt$'s do not change for at least $r$ time instants. 

\begin{assu}[Piecewise Constant Subspace Change]\label{def_pw_ss}
Let $t_1, \dots t_j, \dots t_J$ denote the subspace change times. Let $t_0=1$ and $t_{J+1}=\tmax$.
Assume that 
\[
\P_{(t)} = \P_j \text{ for all } t \in [t_j, t_{j+1}), \ j=1,2,\dots, J,
\]
with $t_{j+1} - t_j > r$. Since $\yt=\lt +\xt$ (is imperfect), our guarantee needs a larger lower bound than $r$.


\end{assu}


Even with the above assumption, a sparse $\xt$ and its support $\T_t$ cannot be correctly distinguished from $\lt = \P_j \at$ without more assumptions. Correct recovery of $\xt$ and $\T_t$ requires that (i) the $\xt$'s are sparse enough (ensured by bounding the maximum allowed outlier fractions per column), (ii) the columns of $\P_j$ are not sparse (ensured by the standard incoherence/denseness assumption from the RPCA literature \cite{matcomp_candes,rpca,robpca_nonconvex}), and (iii) the $\at$'s are bounded. (iv) Correct support recovery also requires subspace change that is slow enough compared to the minimum nonzero entry of $\xt$ (minimum outlier magnitude), denoted $\xmint$.


Correct subspace update requires that (v) the $r \times \alpha$ sub-matrices formed by a mini-batch of $\at$'s are well-conditioned, and (vi) the outlier support $\T_t$ changes enough over time so that there is at least  one outlier-free observation of each scalar entry of $\lt$ in each mini-batch of $\yt$'s.  One way to ensure (v) is to assume that the $\at$'s are i.i.d. while (vi) can be ensured by bounding the maximum fraction of outliers in any row of any $\alpha$-mini-batch sub-matrix of $\X$. We use $\outfracrow(\alpha)$ to denote this quantity.
We summarize the above assumptions on $\P_j$'s and $\at$'s in Assumption \ref{defmu}, those on the outlier fractions in  Assumption \ref{def_outfrac}, and slow subspace change compared to $\xmint$ in Assumption \ref{slow_ss}.


\begin{assu}[$\mu$-Incoherence]\label{defmu}
Assume the following.
\begin{enumerate}
\item (Left Incoherence) Assume that $\P_j$'s are $\mu$-incoherent with $\mu$ being a numerical constant. This means that

$
\max_{i=1,2,.., n} \|(\P_j)^{(i)}\|^2 \le \mu r/ n.
$
Here $\P^{(i)}$ denotes the $i$-th row of $\P$.


\item (Statistical Right Incoherence) Assume Assumption \ref{def_right_incoh}, i.e., the subspace coefficients $\at$ are zero mean, mutually independent, have identical diagonal covariance matrix $\Lam:=\E[\at \at']$, and are bounded: $\max_t \|\at\|^2 \le \mu r \lambda_{\max}(\Lam)$. Let $\lambda^+$ ($\lambda^-$), $f := \lambda^+/\lambda^-$ denote the maximum (minimum) eigenvalue and condition number of $\Lam$.
    

\end{enumerate}
\end{assu}
The second assumption above allows us to obtain high probability upper bounds on the tracking delay of our approach. As we explain later in Sec. \ref{why_stat_right_incoh}, it can be interpreted as a statistical version of right singular vectors' incoherence. The incoherence assumption on $\P_j$ is nearly equivalent to left singular vectors' incoherence. It is exactly equivalent if we consider the sub-matrices $\L_j:=[\l_{t_j},\l_{t_j+1}, \dots, \l_{t_{j+1}-1}]$.


\cred

\begin{assu}[Outliers are spread out]\label{def_outfrac}
Let $\outfraccol:=\max_t|\T_t|/n$; let $\outfracrow(\alpha)$ be the maximum fraction of nonzeros per row of any sub-matrix of $\X_{[t_\train,d]}$ with $\alpha$ consecutive columns, and let $\outfracrow_{\init}$ be the maximum fraction of outliers  per row of any sub-matrix of $\X_{[1,t_\train]}$.
Assume that $\outfraccol \leq \frac{c_1}{\mu r}$, $\outfracrow(\alpha) \leq \frac{c_2}{f^2}$, and $\outfracrow_{\init} \le \frac{c_3}{r}$.
\end{assu}


\begin{assu}[Slow subspace change] \label{slow_ss}
Let $\xmint: = \min_t \min_{i \in \Tt} |(\xt)_i|$ and let $\SE_j:= \SE(\P_{j-1}, \P_j)$.
Assume that  $\SE_j \le 0.8$ and $\SE_j \le \frac{c_4}{\sqrt{r}} \frac{\xmint}{\sqrt{\lambda^+}}$.
\end{assu}

{\em The order notation used here and below assumes that $f, \mu$ are constants.}


\subsection{Guarantees}


Before stating our main result, we define a few terms next.
\begin{definition}

Let the mini-batch size $\alpha := C f^2  r \log n$, 
the number of subspace update iterations needed to get an $\zz$ accurate estimate, $K =  K(\zz):=C \log (\dif/\zz)$, where $\Delta:=\max_j \SE_j$, 
noise power $\lambda_v^+ := \max_t \|\E[\vt\vt{}']\|$, and effective noise dimension, $r_v := \frac{\max_t \|\vt\|^2}{\lambda_v^+}$.

Recall from Algorithm  \ref{algo:auto-reprocs-pca} that $\that_j$ denotes the time at which the $j$-th subspace change is detected.


\end{definition}

We have the following result.

\begin{theorem}
Assume that Assumptions \ref{def_pw_ss}, \ref{defmu}, \ref{def_outfrac}, and \ref{slow_ss} hold. Assume that the noise $\vt$ is bounded, i.i.d. over time,  independent of $\T_t$, uncorrelated with $\lt$, i.e., $\E[\lt \vt{}'] = 0$, and with $r_v \leq Cr$, and $ \sqrt{\lambda_v^+/\lambda^-} < 0.01$. Also, assume that $\lt$'s and $\T_t$'s are independent.

Pick an $\zz$ that satisfies $c \sqrt{\lambda_v^+/\lambda^-} \leq \zz  \leq \min \left( c_3 \frac{1}{\sqrt{r}} \frac{\xmint}{\sqrt{\lambda^+}} , 0.01 \right)$.
Consider Algorithm \ref{algo:auto-reprocs-pca} with $K = K(\zz)$ as defined above,  $\alpha=Cf^2 r \log n$, $\omega_{evals} = 2 \zz^2 \lambda^+$,
$\zeta = \xmint/15$ and $\omega_{supp} = \xmint/2$.
If


\begin{enumerate}

\item $\max_t \|\vt\| \le c_5  \xmint  $,


\item  $t_{j+1}-t_j > (K+2)\alpha$, and $\SE_j > 9  \sqrt{f} \zz$


\item  initialization\footnote{This can be satisfied by using $C \log r$ iterations of AltProj \cite{robpca_nonconvex} on the first $t_\train = C r$ data samples.}:  $\SE(\Phat_0,\P_0) \le \min \left( c_6 \frac{1}{\sqrt{r}} \frac{\xmint}{\sqrt{\lambda^+}} , 0.25 \right)$;
    
\end{enumerate}

then, w.p. at least $1 - 10 \tmax n^{-10} $, 

\ben
\item $t_j \le \that_j \le t_j+2 \alpha$,
\begin{align*}
&\SE(\Phat_{(t)}, \P_{(t)})  \le \\
 &\left\{
\begin{array}{ll}
(\zz + \SE_j) & \text{ if }  t \in [t_j, \that_j+\alpha), \\
 (0.3)^{k-1} (\zz + \SE_j) & \text{ if }  t \in [\that_j+(k-1)\alpha, \that_j+ k\alpha), \\
\zz   & \text{ if }  t \in [\that_j+ K\alpha+\alpha, t_{j+1}),
\end{array}
\right.
\end{align*}
and $\|\lhat_t-\lt\| \le 1.2 \SE(\Phat_{(t)}, \P_{(t)})  \|\lt\|  + \|\vt\|$;

\item $\That_t =\T_t$ and the bound on $\|\xhat_t - \xt\|$ is the same as that on $\|\lhat_t-\lt\|$.

\een
The time complexity is $O(n \tmax r  \log (1/\zz) )$ and memory complexity is $O(n \alpha) = O(f^2 n r \log n)$.
\label{thm1}
\end{theorem}
\begin{proof} We prove this in Sec. \ref{sec:proof_norst}. \end{proof}

We have the following corollary for the smoothing NORST algorithm (last few lines of Algorithm \ref{algo:auto-reprocs-pca}). This is also a mini-batch approach with mini-batch size $(K+2) \alpha$ (instead of $\alpha$ for NORST).


\renewcommand{\offline}{\mathrm{smoothing}}
\begin{corollary}\label{cor:thm1}[Smoothing NORST for dynamic RPCA]
Under the assumptions of Theorem \ref{thm1}, the following also hold:
 $\SE(\Phat_{(t)}^{\offline}, \P_{(t)})  \le \zz$, $\|\lhat_t^{\offline}-\lt\| \le \zz \|\lt\| + \|\vt \|$ at all times $t$. Its time complexity is $O(n \tmax r  \log (1/\zz) )$ and memory complexity is $O(K n \alpha) = O(n r \log n \log (1/\zz) )$. All these quantities are computed within a delay of at most $(K+2)\alpha$.

\end{corollary}


The above result guarantees that NORST can detect subspace changes in delay at most $\alpha = C r\log n $ and track them to $\zz$ accuracy in delay at most $(K+2) \alpha =C r\log n  \log (\Delta/\zz) $. The corollary for smoothing NORST guarantees that, with this delay, each column of $\L$, $\lt$, is recovered to $\zz$ relative accuracy.
The minimum delay needed to compute an $r$-dimensional subspace even with perfect data $\yt=\lt$ is $r$. Thus, our result guarantees near optimal detection and tracking delay (``near optimal'' means that it is within log factors of the minimum delay). Moreover, the required lower bound on the delay between subspace change times is also near optimal.
Quick and reliable change detection is an important feature, e.g., this feature has been used in \cite{selin_reprocs} to detect structural changes in a dynamic social network.


 When the extra unstructured noise $\vt=0$, we can track to any $\zz>0$ otherwise we can track to $\zz  \ge \sqrt{\lambda_v^+/\lambda^-}$ (square root of the noise level). It is possible to slightly relax this requirement to $\zz \ge {\lambda_v^+/\lambda^-}$ by picking a larger $\alpha$,  $\alpha = C  (r \log n) (\lambda^- / \lambda_v^+)$, but it cannot be eliminated. 
The reason is that at each time $t$, we have an {\em under-determined} set of equations corrupted by unstructured noise $\vt$. Even assuming the subspace is known or has been perfectly estimated, it is under-determined: we have $n + r$ unknowns at each time $t$  but only $n$ observed scalars. This is also true for any other under-determined problem as well, e.g., standard RPCA or CS\footnote{To address a reviewer comment, one cannot get a consistent estimator for our problem, nor for standard RPCA or CS. Consistent estimator means that the recovery error goes to zero as the number of observed data points increases. For example for Least Squares estimation, one can show the estimator is consistent. But this is true because number of observed data points increases while the number of unknowns remains constant. In our case, the number of unknowns also increases with time $t$: at each $t$, we have $(n+r)$ unknowns even if $\Pt$ has been estimated.}.


Notice also that we have assumed that the ``effective noise dimension'', $r_v \in O(r)$. This requirement can be eliminated if we set $\alpha = C f^2 \max(r,r_v) \log n$. 


\cred

From the perspective of recovering the true data $\lt$, both $\vt$ and $\xt$ are noise or perturbations. The difference is that $\vt$ is a vector of small disturbances or modeling errors, while $\xt$ is a  sparse outlier vector with few nonzero entries. By definition, an outlier is an infrequent but large disturbance.
Our result tolerates what can be called ``bi-level perturbations'': the small perturbation $\vt$ needs to be small enough and the minimum outlier magnitude $\xmint$ needs to be large enough so that $\|\vt\| \le 0.2 \xmint$ (minimum outlier magnitude).
Moreover, $\xmint$ also needs to be large enough to satisfy Assumption \ref{slow_ss}. The need for both these assumptions is explained in Sec. \ref{tradeoffs}.


Assuming that $\xmint^2$ is of order ${\lambda^+}$ (signal power), Assumption \ref{slow_ss} requires that $\SE_j$ be $O(1/\sqrt{r})$. However this is not as restrictive as it may seem. The reason is that $\SE(.)$ is only measuring the sine of the largest principal angle. If all principal angles are roughly equal, then, this still allows the chordal subspace distance  ($l_2$ norm of the vector of sines of all $r$ principal angles) \cite{chordal_dist} to  be $O(1)$.
\cbl


Our result assumes a minor lower bound on $\SE_j$. This is needed to guarantee reliable subspace change detection. Changes that are smaller than order $\zz$ cannot be detected when the previous subspace is only tracked to accuracy $\zz$. However, such changes also increase the tracking error only by an extra factor of $\zz$ and hence can be treated as noise. If change detection is not important, then, as we explain in Sec. \ref{extends}, we can use a simpler NORST algorithm that does not need the lower bound.


Consider the piecewise constant subspace change assumption. In practice, e.g., in the video application, typically the subspaces change by a little at each time. This can be modeled as piecewise constant subspaces plus modeling error $\vt$. We explain this point in  Sec. \ref{extends} where we also provide a corollary for this setting. This corollary explains why the NORST algorithm ``works''  (gives good, but not perfect, subspace estimates and estimates of $\lt$) for real videos or for simulated data generated so that $\Pt$ changes a little at each $t$; see Sec. \ref{sec:sims} and more detailed experiments in \cite{rrpcp_review}.


To keep the theorem statement simple, we have used tighter bounds than required. Define the intervals $\J_{j,1} = [t_j, \that_j + \alpha)$, $\J_{j,k} := [\that_j + (k-1)\alpha, \that_j + k\alpha)$ for $k=2,3,\dots, K$, and $\J_{j,K+1} = [\that_j + (K+1)\alpha, t_{j+1})$. For $t \in \J_{j,k}$, for $k=1,2,\dots, K$, we only need $0.3^{k-1} (\zz+ \SE_j) \sqrt{r \lambda^+} \le c \min_{i \in \Tt} |(\xt)_i|$, i.e., the required lower bound on the minimum outlier magnitude at time $t$ decreases as the subspaces get estimated better. For the outliers $\xt$ for $t \in \J_{j,K+1} $, we do not require any lower bound. Secondly, if the outlier vector is such that some entries are very small while the others are large enough, then we can treat the smaller entries as ``noise'' $\vt$. This will work as long as these small entries are small enough so that the sum of their squares is sufficiently smaller than the square of the magnitude of the larger entries, i.e., for $t \in \J_{j,k}$, we can split $\xt$ as $\xt = (\xt)_{small} + (\xt)_{large}$ with the two components being such that $c \x_{t,large,min} \ge \|(\xt)_{small}\|$  and $c  \x_{t,large,min} \ge 0.3^{k-1} (\zz+ \max_j \SE_j)\sqrt{r \lambda^+}$.
Finally, if we also state the PCA-SDDN result in its most general form, the subspace error decay rate of $0.3$ can be replaced by $(6\sqrt{b_0} f)$ with $b_0:= \outfracrow$, so this requirement becomes $c  \x_{t,large,min} \ge (6\sqrt{b_0} f)^{k-1} (\zz+ \max_j \SE_j)\sqrt{r \lambda^+}$. With this change, the expression for $K$ becomes $K = \left \lceil \frac{\log \left( \semax / \zz \right)}{-\log(6 \sqrt{b_0} f)}  \right \rceil.$
Thus, a smaller $b_0$ means that the subspace error decays faster. This, in turn, means that a smaller $K$ suffices (faster tracking and a smaller required lower bound on $t_{j+1}-t_j$). It also means a smaller lower bound is needed on the outlier magnitudes at most times.


\subsection{How slow subspace change (Assumption \ref{slow_ss}) enables improved outlier tolerance}
\label{tradeoffs}

We explain here how the use of Assumption \ref{slow_ss} enables improved outlier tolerance. Briefly, the reason is we recover each outlier $\xt$ and its support $\T_t$ individually. To understand things simply, assume $\vt=0$.


Given a good previous subspace estimate, $\Phat_{(t-1)}$, slow subspace change implies that $\SE(\Phat_{(t-1)},\Pt)$ is small. 
Consider an $\alpha$ length interval $\J$ during with $\Phat_{(t-1)} = \Phat$ (computed in the previous $\alpha$ interval).
To exploit slow subspace change, we project each $\yt$ orthogonal to $\Phat$ to get $\tty_t : = \bpsi \st + \b_t $ where $\b_t:= \bpsi \lt $ is small because of above. Here $\bpsi:= \I - \Phat \Phat{}'$. 
Now $\bt$ itself does not have any structure. But, the matrix $\B_{\J}$ formed by the $\b_t$'s for $t \in \J$, is low rank with rank $r$ \footnote{The effective (stable) rank, of $\B_{\J}$  will be less than $r$ only if we assume more structure on subspace change, e.g., if we assume that only a few subspace directions change. Its exact rank will still be $r$.}.


Accurately recovering $\S_\J$ from $\tilde{\Y}_\J:= \bpsi \S_\J + \B_\J$ when $\B_\J$ has rank $r$ is impossible if the fraction of outliers in any row or in any column of $\S_\J$ is more than $c/r$. The reasoning is the same as that used for standard RPCA \cite{robpca_nonconvex}: we can construct a sparse matrix $\S_\J$ with rank $1/\max(\outfracrow,\outfraccol)$.


Thus if $\outfracrow = c$, we can construct a sparse $\S_\J$ with rank $1/c= C \ll r$ \footnote{A simple way to do this would be as follows. Let $b_0 = \outfracrow$ and suppose $b_0$ is a constant (is more than order $1/r$).
Let the support and nonzero entries of $\X_\J$ be constant for the first $b_0 \alpha$ columns; after this, move the nonzero entries down in such a way that there is no overlap of supports; and repeat this every $b_ 0 \alpha$ columns. With this, the $\outfracrow = b_0$ and the rank of $\X_\J$ is $\alpha/(b_0 \alpha) = 1/b_0$ since there are only $1/b_0$ unique vectors in this matrix construction.}.
If the rank of $\S_\J$ is less than $r$, that of $\bpsi \S_\J$ will also be less than $r$, making the recovery problem un-identifiable: if we try to find a matrix $\hat\B_\J$ of rank at most $r$ and a matrix $\hat\X_\J$ that is the sparsest and both satisfy $\tilde{\Y}_\J:= \bpsi \hat\S_\J + \hat\B_\J$, it is possible that we get the solution $\hat\B_\J = \B_\J + \bpsi \hat\S_\J$ and $\hat\X_\J = \bm{0}$. Because rank of $\bpsi \hat\S_\J$ is less than $r$ and that of $\B_\J$ is $r$, it is possible that the sum still has rank $r$. 


Thus, if we would like to improve row-wise outlier tolerance to $O(1)$, we cannot jointly recover all columns of  $\S_{\J}$ by exploiting the low rank structure of $\B_{\J}$. 
The only other way to proceed is as we do: recover them one $\st$ at a time from $\tty_t$. Here we can only use the fact that $\|\bt\|$ is small due to slow subspace change. The problem of recovering  a single $\st$ from $\tty_t$ is a standard noisy CS problem \cite{candes_rip}, with small noise $\bt$. To our best knowledge, there are no entry-wise recovery guarantees for CS. One can only bound $\|\xhat_{t,cs} - \xt\|$ by a constant (that depends on the restricted isometry constant of $\bpsi$), $C$, times $\|\bt\|$. Here $\xhat_{t,cs}$ is the output of the CS step (line 7 of Algorithm \ref{algo:auto-reprocs-pca}).
With this, correct support recovery, $\That_t = \T_t$, is ensured only if $\xmint > 2 C \|\bt\| $.
The worst case bound on $\|\bt\|$ comes from when the subspace has changed but the change has not been detected so that $\Phat_{(t-1)} = \Phat_{j-1}$ and $\Pt = \P_j$. At this time, $\|\bt\| \le  \max_j \SE(\Phat_{j-1}, \P_j) \sqrt{r}  \sqrt{\lambda^+}$. Also, we can show that $ \SE(\Phat_{j-1}, \P_j) \le \SE_j + \zz$. Thus, exact support recovery is guaranteed if Assumption \ref{slow_ss} holds and $\zz$ is chosen as specified in the theorem.


When $\vt \neq 0$, the bound on $\|\bt\|$ contains a $\|\vt\|$ term. In this case, exact support recovery also needs $\|\vt\| \le c_5 \xmint$.


Exact support recovery followed by LS on the recovered support and then subtraction to get $\lhat_t$ implies that $\lhat_t$ satisfies $\lhat_t  = \lt + \et$ with $\et:= -  \I_{\T_t} \underbrace{(\I_{\T_t}{}' \bpsi \I_{\T_t}{})^{-1} \I_{\T_t}{} \bpsi }_{\M_{s,t}} \lt$. Notice that $\et$ is sparse and linearly data-dependent and, conditioned on $\Phat$ and the support sets $\T_t$, the matrix $\M_{s,t}$ is deterministic. So we can apply the PCA-SDDN result from the previous section. It also needs statistical right incoherence, $q := \max_t \|\M_{s,t} \P_j\| \le C \SE(\Phat,\P_j) $ (holds by left incoherence and $\outfraccol < c/r$), and  $\outfracrow (\alpha) \le c$ (constant row-wise outlier fraction bound). If the support recovery were incorrect, the estimated support $\That_t$ would depend on $\b_t$ and hence on $\lt$. This would mean that, even conditioned on $\Phat$ and $\T_t$, the matrices $\M_{s,t}$ are not deterministic making the PCA-SDDN result inapplicable.


\input{algo-autonorst-it}  


\subsection{Understanding Statistical Right Incoherence}\label{why_stat_right_incoh}

\newcommand{\vv}{\bm{v}} 


Let $\L_j := \L_{[t_j, t_{j+1})}$.
From our assumptions, $\L_j = \P_j \A_j$ with $\A_j:= [\a_{t_j},\a_{t_j+1},\dots \a_{t_{j+1}-1}]$, the columns of $\A_j$ are zero mean, mutually independent, have identical covariance $\Lam$, $\Lam$ is diagonal, and  bounded. Let $d_j := t_{j+1}-t_j$.
Define a diagonal matrix $\Sigma$ with $(i,i)$-th entry $\sigma_i$ satisfying $\sigma_i^2 := \sum_t (a_t)_i^2 / d_j$. Define a $d_j \times r$ matrix $\tilde\V$ with the $t$-th entry of the $i$-th column being $(\tilde\vv_i)_t: = (\a_t)_i/ (\sigma_i \sqrt{d_j})$. Clearly, $\L_j = \P_j \Sigma \tilde{\V}'$ and each column of $\tilde\V$ is unit 2-norm. This can be interpreted as an approximation to the SVD of $\L_j$; we say approximation because the columns of $\tilde\V$ are not necessarily exactly mutually orthogonal.
However, if $d_j$ is large enough, one can argue using  scalar Hoeffding inequality (applicable because $\at$'s are bounded), that, whp,
(i) the columns of $\tilde\V$ are approximately mutually orthogonal, i.e. $|\tilde\vv_i' \tilde\vv_j | \le \epsilon$ for all $i \neq j$; and
(ii) $0.99 \lambda_i \le \sigma_i^2 \le 1.01 \lambda_i $ for all $i=1,2, \dots, r$. Thus, by the boundedness assumption on the $\at$'s,  the $t$-th row of $\tilde\V$ satisfies $\sum_{i=1}^r (\tilde\vv_i)_t^2  \le (1/d_j) (1/\min_i \sigma_{i}^2) \|\at\|^2 \le  (1/d_j) (1/\lambda^-) \mu r \lambda^+ = f \mu r / d_j$. This is the standard incoherence assumption with parameter $f \mu$.
Thus, whp, the approximate right singular vectors' matrix $\tilde\V$ of $\L_j$ satisfies the standard incoherence assumption.


\subsection{Nearly Optimal Robust ST via ReProCS (NORST-ReProCS): details}\label{algo_details}

Algorithm \ref{norst} uses the Recursive Projected Compressive Sensing framework introduced in \cite{rrpcp_perf}. 

It starts with a ``good'' estimate of the initial subspace. This can be obtained  by using a few iterations 
of AltProj applied to  $\Y_{[1,t_\train]}$ with $t_\train=Cr$.
It then iterates between (a) {\em Projected Compressive Sensing (CS) / Robust Regression\footnote{Robust Regression (with a sparsity model on the outliers) assumes that observed data vector $\y$ satisfies $\y = \Phat \a + \x + \b$ where $\Phat$ is a tall matrix (given), $\a$ is the vector of (unknown) regression coefficients, $\x$ is the (unknown) sparse outliers, $\b$ is (unknown) small noise/modeling error. An obvious way to solve this is by solving $\min_{\a,\x} \lambda \|\x\|_1+ \|\y - \Phat \a - \x\|^2$. In this, one can solve for $\a$ in closed form to get $\hat\a = \Phat'(\y-\x)$. Substituting this, the minimization simplifies to $\min_{\x} \lambda \|\x\|_1+ \|(\I - \Phat \Phat') (\y - \x)\|^2$. This is equivalent to the Lagrangian version of the projected CS problem that NORST solves (given in line 7 of  Algorithm \ref{algo:auto-reprocs-pca}). 
}} in order to estimate the sparse outliers, $\xt$'s, and hence the $\lt$'s, and (b) {\em Subspace Update} to update the estimates $\Phat_{(t)}$.
Projected CS proceeds as follows. At time $t$, if the previous subspace estimate, $\Phat_{(t-1)}$, is accurate enough, because of slow subspace change, projecting $\yt$ onto its orthogonal complement will nullify most of $\lt$. We compute $\tty_t:= \bpsi  \yt$ where $\bpsi := \I - \Phat_{(t-1)}\Phat_{(t-1)}{}'$. Clearly $\tty_t = \bpsi \xt + \bpsi (\lt+\vt)$ and $\| \bpsi  (\lt+\vt)\|$ is small due to slow subspace change and small $\vt$. Recovering $\xt$ from $\tty_t$ is now a CS / sparse recovery problem in small noise \cite{candes_rip}. 
We compute $\xhat_{t,cs}$ using noisy $l_1$ minimization followed by thresholding based support estimation to obtain $\That_t$. A Least Squares (LS) based debiasing step on $\That_t$ returns the final $\xhat_t$. We then estimate $\lt$ as $\lhat_t = \yt - \xhatt$.

The $\lhatt$'s are then used for the Subspace Update step 


which toggles between the ``detect'' phase and the ``update'' phase. It starts in the ``update'' phase with $\that_0 = t_\train$. We then perform $K$ $r$-SVD steps with the $k$-th one done at $t = \that_0 + k \alpha-1$. Each such step uses the last $\alpha$ estimates, i.e., uses $\Lhat_{t; \alpha}$. Thus at $t = \that_0 + K \alpha - 1$, the subspace update of $\P_0$ is complete. At this point, the algorithm enters the ``detect'' phase.

For any $j$, if the $j$-th subspace change is detected at time $t$, we set  $\that_j=t$. At this time, the algorithm enters the ``update'' (subspace update) phase. We then perform $K$ $r$-SVD steps with  the $k$-th $r$-SVD step done at $t = \that_j + k \alpha-1$ on $\Lhat_{t;\alpha}$. Thus, at $t = \that_{j,fin} = \that_j + K\alpha - 1$, the update is complete. At this $t$, the algorithm enters the ``detect'' phase.

To understand the change detection strategy, consider the $j$-th subspace change. Assume that the previous subspace $\P_{j-1}$ has been accurately estimated by $t= \that_{j-1,fin} = \that_{j-1}+K\alpha-1$ and that $\that_{j-1,fin} < t_j$. Let $\Phat_{j-1}$ denote this estimate. At this time, the algorithm enters the ``detect'' phase in order to detect the next ($j$-th) change. Let $\B_t:=(\I-\Phat_{j-1}\Phat_{j-1}{}')  \Lhat_{t;\alpha}$. At every $t = \that_{j-1,fin} + u \alpha-1$, $u=1,2,\dots$, we detect change by checking if the maximum singular value of $\B_t$ is above a pre-set threshold, $ \sqrt{\lthres \alpha}$, or not.
We claim that, with high probability (whp), under assumptions of Theorem \ref{thm1}, this strategy has no ``false subspace detections'' and correctly detects change within a delay of at most $2\alpha$ samples. The former is true because, for any $t$ for which $[t-\alpha+1, t] \subseteq [ \that_{j-1,fin}, t_j)$, all singular values of the matrix $\B_t$ will be close to zero (will be of order $\zz \sqrt{\lambda^+}$) and hence its maximum singular value will be below $ \sqrt{\lthres \alpha}$. Thus, whp, $\that_j \ge t_j$. To understand why the change {\em is} correctly detected within $2 \alpha$ samples, first consider $t =\that_{j-1,fin} + \lceil \frac{t_j - \that_{j-1,fin}}{\alpha} \rceil \alpha:= t_{j,*} $. Since we assumed that $\that_{j-1,fin}< t_j$ (the previous subspace update is complete before the next change), $t_j$ lies in the interval $[t_{j,*}-\alpha+1, t_{j,*}]$. Thus, not all of the $\lt$'s in this interval satisfy $\lt = \P_j \at$. Depending on where in the interval $t_j$ lies, the algorithm may or may not detect the change at this time.  However, in the {\em next} interval, i.e., for $t \in [t_{j,*}+1, t_{j,*} + \alpha]$,  all of the $\lt$'s satisfy $\lt = \P_j \at$. We can prove that, whp, $\B_t$ for this time $t$ {\em will} have maximum singular value that is above the threshold.

Thus, if the change is not detected at $t_{j,*}$, whp, it {\em will} get detected at $t_{j,*} + \alpha$. Hence, whp, either $\that_j = t_{j,*}$, or $\that_j =t_{j,*} + \alpha$, i.e., $t_j \le \that_j \le t_j + 2\alpha$.


\subsubsection{Algorithm parameters}
Algorithm \ref{norst} assumes knowledge of 4 model parameters: $r$, $\lambda^+$, $\lambda^-$ and $\xmint$ to set the algorithm parameters.
The initial dataset used for estimating $\Phat_0$ (using AltProj) can be used to get an accurate estimate of $r$, $\lambda^-$ and $\lambda^+$ using standard techniques. Thus one really only needs to set $\xmint$. If continuity over time is assumed, we can let it be time-varying and set it as $\min_{i \in \That_{t-1}}|(\xhat_{t-1})_i|$ at $t$.

\subsubsection{Time complexity} The time complexity is $O(n d r\log(1/\epsilon))$. We explain this in Appendix \ref{timecomp_derive}.


\section{Related Work} \label{rel_work}


We first briefly discuss related work on PCA and then discuss robust PCA and subspace tracking papers.
While there has been a large amount of work in the last decade on finite-sample guarantees for PCA \cite{nadler,normal_approx} and related problems, such as sparse PCA \cite{vince_vu_annals,sparsepca_cai} and kernel PCA \cite{kpca_first, kernelpca_nips} most of these assume either the spiked covariance model (noise is modeled as being isotropic) \cite{nadler, kernelpca_nips} or that the observed data $\yt$ is i.i.d. \cite{nadler,normal_approx} or consider noiseless settings \cite{vince_vu_annals, sparsepca_cai} (typical in sparse PCA). The setting that we study involves linearly data dependent noise $\wt = \M_t \lt$ with the dependency matrix $\M_t$ being time-varying. Thus, the noise is clearly not isotropic. Moreover, this also means  that the observed data $\yt = \lt + \wt + \vp_t$ cannot be identically distributed over time.  In fact, our guarantee is interesting only in the setting where $\M_t$ changes enough over time so that the time-averaged expected value of signal-noise correlation and of noise power is sufficiently smaller than their respective instantaneous values. 

We should mention also that, while many sophisticated eigenvector perturbation bounds exist in the literature \cite{svd_topic_est, rel_perturb, rel_perturb2}, these are designed for different settings than the one we are interested in. For our setting, only the classical Davis-Kahan sin theta theorem \cite{davis_kahan} applies. In our analysis, we need to bound the sine of the largest principal angle between the true and estimated subspaces, because this helps us get a bound on the ``noise''/error seen by the projected compressed sensing step at the next time instant. Thus, \cite{svd_topic_est}, which only provides coordinate-wise bounds, cannot be used. The perturbation seen by our sample covariance matrix is additive and our observed data $\yt$ is not identically distributed, and thus the results of \cite{rel_perturb,rel_perturb2} do not apply either.


The robust PCA (RPCA) problem has been extensively studied since the first two papers by Candes et al and Chandrasekharan at al \cite{rpca,rpca2} and follow-up work by Hsu et al \cite{rpca_zhang} all of which studied a convex optimization solution, called Principal Components Pursuit or PCP. A faster non-convex solution, called Alternating Projections or AltProj, was introduced in \cite{robpca_nonconvex}. Later work has studied a projected gradient descent based approach, RPCA-GD \cite{rpca_gd}. The problem of RPCA with partial support knowledge was studied in \cite{zhan_pcp_jp}.
All RPCA guarantees assume $\mu$-incoherence of left and right singular vectors of $\L$ (needed to ensure that $\L$ is not sparse). One way to ensure that $\X$ is not low rank is to assume that an entry of $\X$ is nonzero with probability $\rho$ independent of all others (Bernoulli model) and to assume a bound on $\rho$. This was assumed in \cite{rpca}. This can sometimes be a strong assumption, e.g., in the video setting, it requires that foreground objects are one pixel wide and jump around completely randomly over time. But, if it holds, and if another stronger left-right incoherence assumption holds\footnote{$\max_{i,j} |\U \V')_{i,j}| \le \sqrt{ \frac{\mu r }{nd} }$ where $\U,\V$ are the matrices of left and right singular vectors of $\L$}, then $\rho \in O(1)$ (linear sparsity) can be tolerated while also allowing the rank of $\L$, $\rmat$ to be grow nearly linearly with $\min(n,d)$ \cite{rpca}.
The other approach to ensure that $\X$ is low rank is to assume a bound of $O(1/\rmat)$ on the maximum fraction of nonzeros (outliers) in any row or in any column of $\X$. This is assumed in most of the later works \cite{rpca2,rpca_zhang,robpca_nonconvex,rpca_gd,rmc_gd}. 


Our work provides a fast mini-batch solution to the related problem of robust subspace tracking (RPCA with explicitly assuming slowly changing subspaces). Because we replace right incoherence by its statistical version, we are able to obtain guarantees on detection and tracking delay of our approach and show that both are nearly optimal (are within log factors of the minimum required delay $r$). 

This also means that the memory complexity of NORST is also near optimal: we only need to store $\alpha$ $n$-length vectors in memory with $\alpha = C r \log n$. Of course, any RPCA approach could also be applied in a mini-batch fashion on $\alpha$-consecutive column sub-matrices, and then it will also have the same memory complexity. We assume this here in our discussion. With this assumption, $\outfracrow$ gets replaced by $\outfracrow(\alpha)$ and $\rmat$ gets replaced by $r$ for the RPCA guarantees as well.

Because we assume a lower bound on the minimum outlier magnitudes that is proportional to $\SE_j$, we obtain the following improvement in outlier tolerance (explained in Sec. \ref{tradeoffs}).
Treating $f$ as a constant, {\em for any mini-batch after $t_\train$}, we only need $\outfracrow(\alpha) \in O(1)$. For standard RPCA, unless a random model on outlier support is assumed, $\max(\outfraccol,\outfracrow(\alpha)) \in O(1/r)$ is needed \cite{robpca_nonconvex}. For the video application, this implies that NORST tolerates slow moving and occasionally static foreground objects much better than standard RPCA methods that do not assume slow subspace change.  This is also corroborated by our experiments on real videos, e.g., see Fig \ref{fig:mr_full} in Sec. \ref{sec:sims} and also see a more detailed and quantitative evaluation on real data provided in \cite{rrpcp_review}.

Since our algorithm needs to be initialized with a standard batch RPCA approach such as AltProj \cite{robpca_nonconvex} applied to the first $t_\train = C r$ data points, for this initial short batch, we do need AltProj assumptions to hold and this is why we need  $\outfracrow_{\init} \le \frac{c_3}{r}$.


For the per column fraction, we also need $\outfraccol \in O(1/r)$. Thus, the overall fraction of outliers allowed in a given matrix is still $O(1/r)$, which is the same as standard RPCA, but these can be less spread out row-wise (some rows could have many more outliers than others).
\cbl

Moreover, we are able to guarantee that each column of $\L$, $\lt$, is recovered to $\zz$ relative accuracy and that the support of outliers can be recovered exactly. Neither is guaranteed by existing RPCA results, these only guarantee $\|\Lhat - \L\|_F \le \zz$.

Finally, in terms of time complexity, the NORST complexity of $O(n \alpha r\log(1/\zz))$ per mini-batch is comparable to that of simple (non-robust) PCA. In comparison to RPCA solutions, this is much faster than PCP \cite{rpca,rpca2,rpca_zhang} which needs $O(n \alpha^2 \frac{1}{\zz})$ and $r$-times faster than AltProj \cite{robpca_nonconvex} which needs $O(n \alpha r^2 \log(1/\zz))$. RPCA-GD \cite{rpca_gd} is as fast as NORST but requires an even tighter outlier fractions' bound than other RPCA solutions: $\max(\outfracrow,\outfraccol) \in O(1/ r^{3/2})$. 


Our work builds upon the simple-ReProCS (s-ReProCS) solution and guarantee \cite{rrpcp_dynrpca} and removes many of its limitations. 
S-ReProCS assumes a specific model of slow subspace change:  {\em only one} subspace direction can change at each change time, and the amount of change needs to be bounded. Even with this assumption, its tracking delay is of order $r \log n \log (1/\zz)$. Since only one direction is changing, this delay is $r$-times sub-optimal. The same is true for its required lower bound on subspace change times. 
A second limitation of s-ReProCS is that, in order to track subspaces to $\zz$ accuracy, it requires the initial subspace estimate to also be $\zz$ accurate. This, in turn, implies that one needs to run the AltProj or PCP algorithm on the initial mini-batch to convergence. Instead, our approach only requires the initial subspace error to be $O(1/\sqrt{r})$. Thus, only order $\log r$ iterations of AltProj suffice to initialize our algorithm.
Thirdly, the s-ReProCS guarantee needs a stronger statistical right incoherence assumption than ours: it needs an entry-wise bound of $\max_t \max_{i=1,2,\dots, r} |(\at)_i|^2 \le {\eta \lambda^+}$. Lastly, we develop important extensions of our main result for (i) only tracking subspace changes (without detecting the change), and (ii) for subspaces changing by a little at each time $t$.


An earlier version of Theorem \ref{thm1} appeared in ICML 2018 \cite{rrpcp_icml}. The results of the current manuscript improve upon the ICML result in various ways: we need a weaker statistical right incoherence assumption, a weaker lower bound on $\SE_j$, and we develop two important extensions of our main result for subspace changes at each time and for applications not requiring change detection. 
Moreover, \cite{rrpcp_icml} did not prove the result for PCA in data-dependent noise, but only used the result proved in our older ISIT paper \cite{pca_dd_isit}.

The problem of ST with missing data is a special case of robust ST, while ST with missing data and outliers is a simple generalization of robust ST. Interesting guarantees for both of these follow as easy corollaries of either our current result or of its earlier version from  \cite{rrpcp_icml}. A corollary of the result of  \cite{rrpcp_icml} for ST-miss is presented in \cite{rrpcp_tsp19}. 

In comparison to the result of  \cite{rrpcp_tsp19}, a similarly derived ST-miss corollary of our current result has all the advantages mentioned earlier in this paragraph.


\section{Extensions: subspace change at each time, subspace tracking without detection} \label{extends}

\newcommand{\tL}{\tilde\L}
\subsection{Subspace changing at each time}\label{change_every_t}
Suppose $\yt = \tilde\l_t + \xt$ where  $\tilde\l_t = \P_{(t)} \tilde\a_t$, $\Pt$ changes by a little at each time $t$, but has more significant changes at certain times $t_j$. 
We show here how this case can be handled by treating the error generated by changes at each time $t$ as extra unstructured noise $\vt$.


Assume that $\tilde\at$'s are zero mean, bounded, and i.i.d. with diagonal covariance matrix $\tilde\Lam$. Let $\tilde\lambda^+$ be its maximum eigenvalue and $\tilde{f}$ the condition number.


Define $\P_j$ as the matrix of top $r$ left singular vectors of the matrix $\tL_j:= [\tilde\l_{t_j}, \tilde\l_{t_j+1}, \dots, \tilde\l_{t_{j+1}-1}]$, or equivalently of $[\P_{(t_j)}, \P_{(t_j+1)}, \dots, \P_{(t_{j+1}-1)}]$.
Let $\at : = \P_j' \tilde\l_t$, $\lt : = \P_j \at$ and $\vt:= \tilde\l_t - \lt = \P_{j,\perp} \tilde\l_t$.

Another way to understand the above is that we are expressing $\tL_j = \L_j + \V_j$ where $\L_j$ is the rank-$r$ SVD of $\tL$, while $\V_j$ is the rest. While  $\L_j \V_j'= 0$, we cannot say anything about individual vectors $\lt \vt'$ or their expected value. In general, $ \E[\lt \vt{}'] \neq 0$. But even then, we can always use Cauchy-Schwarz to get the bound $\|\E[\lt \vt']| \| \le \sqrt{\lambda^+ \lambda_v^+}$.
Thus, to analyze this case, we need to modify Corollary \ref{cor:noisy_pca_sddn} for PCA-SDDN as follows: we now need $4 \sqrt{b} q f  + \frac{\lambda_v^+}{\lambda^-}+ \sqrt{\frac{\lambda_v^+}{\lambda^-} f} < 0.4 \epsilon_\SE$.  
There is no change to the required lower bound on $\alpha$.

From our definition of $\vt$, $\lambda_v^+ \le \SE(\P_j, \Pt)^2 \tilde\lambda^+$. Using $\lambda^+ \le \tilde\lambda^+$, $\tilde\lambda^- < \lambda^-$, a simple sufficient condition to ensure that the third term is small ($\lambda_v^+/\lambda^- \le 0.01 \zz^2/f$) is $ \SE(\P_j, \Pt)^2 \le 0.01 \zz^2 /\tilde{f}^2$.
\begin{corollary}[Subspace changing at each $t$]
Consider the setting defined in the first paragraph above.
If $ \SE(\P_j, \Pt)^2 < 0.01 \zz^2 /\tilde{f}^2$, Theorem \ref{thm1} applies with $\P_j$, $\lt$, and $\vt$ as defined above.
\end{corollary}


\subsection{NORST-NoDet: NORST without subspace change detection}\label{norst_nodet}
A simpler version of the NORST algorithm that does not detect change is as follows. The robust regression (projected CS) step is exactly as explained earlier. The subspace update step is much simpler:  it just updates $\Phat_{(t)}$ as the top $r$ left singular vectors of $\Lhat_{t; \alpha}$ once every $\alpha$ frames. We refer to it as NORST-NoDet. We have the following guarantee for it.

\begin{theorem}
Consider Algorithm \ref{algo:norst_nodet} with parameters set as $\alpha = C f^2 \mu r \log n $,  $\zeta = \xmint/15$ and $\omega_{supp} = \xmint/2$.
Assume everything stated in Theorem \ref{thm1} except the lower bound on $\SE_j$.
Then, w.p. at least $1 - 10 \tmax n^{-10} $,
\[
\SE(\Phat_{(t)}, \P_{(t)}) \le
 \left\{
\begin{array}{ll}
\min(4 f  \SE_j, 1) & \text{ if }  t \in \J_1, \\
 (0.3)^{k-1}  \min( 4 f  \SE_j, 1 ) & \text{ if }  t \in \J_k, \\
\zz:=  c \sqrt{\lambda_v^+/\lambda^-}    & \text{ if }  t \in \J_K,
\end{array}
\right.
\]

where $\J_1 = [\lfloor t_j/\alpha \rfloor \alpha ,  (\lfloor t_j/\alpha  \rfloor + 1)\alpha)$, $J_k = [\lfloor t_j/\alpha  \rfloor +1 )\alpha)+(k-1)\alpha, ( \lfloor t_j/\alpha)+ (k+1)  ) \alpha  \rfloor $ for $k =2, 3 , \cdots, K-1$ and $\J_K = [ (\lfloor t_j/\alpha  \rfloor +(K+1) ) \alpha, \lfloor t_{j+1}/\alpha \rfloor \alpha )$. \\


The time complexity is $O(n \tmax r \log (1/\zz) )$ and memory complexity is $O(n \alpha) = O(f^2 n r \log n \log (1/\zz) )$.
\label{thm1_newnorst}
\end{theorem}

The advantage of NORST-NoDet is that it does not require a lower bound on the amount of change, $\SE_j$, and it needs fewer algorithm parameters (does not need $K$ or $\omega_{evals}$).  The disadvantage is it does not detect subspace change, we cannot obtain a ``smoothing'' version of it that solves the dynamic RPCA problem to $\zz$ accuracy at all times, and  its subspace error bound is larger for the intervals during which the subspace changes, $ [\lfloor t_j/\alpha \rfloor \alpha ,  (\lfloor t_j/\alpha  \rfloor + 1)\alpha)$.
For times $t$ in this interval, the  bound is $\min(4 f  \SE_j, 1)$. Assuming small enough $\zz$, this is larger than  $(\zz + \SE_j)$ which is the NORST bound for this interval. The reason is  NORST stops tracking after the current subspace has been estimated accurately enough and until the next change is detected. During this period, it uses $\Phat_{j-1}$ as the estimate. But NORST-NoDet updates the subspace in every interval. For the change interval, the rank of $\L_{t;\alpha}$ is more than $r$. It can be $2r$ in general. This is why it is not possible to guarantee a better bound for the $r$-SVD estimate. At the same time, without extra assumptions, it is not possible to obtain a guarantee for  $2r$-SVD estimate either. 

For analyzing the change interval we use the following modification of PCA-SDDN. Its proof is in Appendix \ref{proofs_pca_section}. The proof of Theorem \ref{thm1_newnorst} is given in Appendix \ref{sec:proof}.

\begin{corollary}\label{pca_ssch}
Assume that $\yt = \lt + \wt + \vp_t$ with $\wt = \M_{2,t} \M_{1,t} \lt$, with $\lt = \P_0 \at$ for $t \in [1, \alpha_0]$ and $\lt = \P \at$ for $t \in [\alpha_0+1, \alpha]$, and $\SE(\P_0, \P) \le \Delta$.
Assume also that Assumptions \ref{def_right_incoh}, \ref{vt_assu} hold,  $\max_t \max(\|\M_{1,t} \P_0\|, \|\M_{1,t} \P\|) \le q < 1$, and the fraction of nonzeros in any row of the noise matrix $[\w_1, \w_2, \dots, \w_\tmaxpca]$ is equal to $\bz$.
Let $g: = \frac{\lambda_{v}^+}{\lambda^-}$. If $\Delta < c / f$,
and if
$\tmaxpca \ge \tmaxpca^*  = C \max\left( \frac{q^2 f^2}{\epsilon_\SE^2} r \log n, \frac{g f}{\epsilon_\SE^2} \max(r_v,r) \log n\right)$
then w.p. at least $1- 10n^{-10}$,
\begin{align*}
\SE(\Phat,\P) &\le 1.1 \left(3 ((\alpha_0 / \alpha) \Delta  + 4 \sqrt{\bz} q) f + \frac{\lambda_{v}^+ }{ \lambda^-} \right) \\
&\le 3.3 \Delta f  + 4.4 \sqrt{\bz} q f + 1.1 \frac{\lambda_{v}^+ }{ \lambda^-} .
\end{align*}
\end{corollary}
{"config": "arxiv", "file": "2006.08030/norst_algo_proof.tex"}