\section{Extensions}\label{sec:extensions}
{\cred
mention that this has been published in TSP etc}


\subsection{Static Robust PCA}
A useful corollary of our result for RST is that NORST is also the {first online algorithm that provides a provable finite sample guarantee for the static Robust PCA problem}. 
Static RPCA is our problem setting with $J=1$, or in other words, with $\lt = \P \at$.


A recent work, \cite{xu_nips2013_1}, developed an online stochastic optimization based reformulation of PCP, called ORPCA, to solve this. Their paper provides only a partial guarantee because the guarantee assumes that the intermediate algorithm estimates, $\Phat_{(t)}$, are full-rank. Moreover the guarantee is only asymptotic.  Instead our result given below is a complete guarantee and is non-asymptotic.


\begin{corollary}[Static RPCA]\label{thm:rpca}
Consider Algorithm \ref{norst_basic} with $t_2=\infty$. Theorem \ref{thm1} holds with following modification: replace the slow subspace change assumption with a fixed subspace $\P$. Everything else remains as is, but with $r \equiv \rmat$. Under the assumptions of Theorem \ref{thm1}, all the conclusions hold with same probability. The time and memory complexity  are $O(n d r \log(1/\epsilon))$ and $O(n r \log n \log(1/\epsilon))$.
\end{corollary}


In applications such as ``robust'' dimensionality reduction \cite{dimreduce_app1, dimreduce_app2} where the objective is to just obtain the top-$r$ directions along which the variability of data is maximized, we only need the first $K\alpha = Cf^2r\log n \log(1/\zz)$ samples to obtain an $\zz$-accurate subspace estimate. If only these are used, the time complexity reduces to $O(n K \alpha r \log(1/\zz)) = O(n r^2 \log n \log^2(1/\epsilon))$. This is faster than even NO-RMC \cite{rmc_gd} and does not require $\tmax \approx n$; of course it requires the other extra assumptions discussed earlier.


\subsection{Subspace Tracking with Missing Data (ST-missing) and Dynamic Matrix Completion}
Another useful corollary of our result is a guarantee for the ST-missing problem.


Consider the subspace tracking with missing data (ST-missing) problem. By setting the missing entries at time $t$ to zero, and by defining $\T_t$ to be the set of missing entries at time $t$, we observe $n$-dimensional vectors that satisfy
\bea
\yt := \lt - \itt \itt{}' \lt, \text{ for } t = 1, 2, \dots, \tmax.
\label{eq:dynmc}
\eea
with $\xt \equiv \itt \itt{}' \lt$. This can be interpreted as a special case of the RST problem where the set $\T_t$ is known. Because there are no sparse corruptions (outliers), there is no $\xmint$. Thus the initialization error need not be $O(1/\sqrt{r})$ (needed in the RST result to ensure a reasonable lower bound on $\xmint$) and so one can even use random initialization. We assume that the initialization is obtained using the Random Orthogonal Model described in \cite{matcomp_candes}. As explained in \cite{matcomp_candes}, a basis matrix generated from this model is already $\mu$-incoherent. We have the following corollary. The only change in its proof is the proof of the first subspace update interval for the $j=0$ case.


\begin{corollary}[ST-missing]\label{cor:stmiss}
Consider NORST-Random (Algorithm \ref{algo:auto-dyn-mc}). If the assumptions of Theorem \ref{thm1} on $\at$ and $\vt$ hold, $\P_j$'s are $\mu$-incoherent,  $t_{j+1}-t_j > (K+2)\alpha$, $\Delta < 0.8$, the outlier fraction bounds given in Theorem \ref{thm1} hold, and if, for $t \in [t_0,t_1]$, $\outfraccol \le c/ (\log n)$, then all conclusions of Theorem \ref{thm1} on $\Phat_{(t)}$ and on $\lt$ hold with the same probability.
\end{corollary}
To our knowledge, the above is the first complete non-asymptotic guarantee for ST-missing; and the first result that allows changing subspaces. All existing guarantees are either partial guarantees (make assumptions on intermediate algorithm estimates), e.g., \cite{local_conv_grouse}, or provide only asymptotic results \cite{past,petrels}.
Moreover, from a dynamic matrix completion viewpoint, it is also giving a matrix completion solution without assuming that the set of observed entries is generated from a uniform or a Bernoulli model. Of course the tradeoff is that it needs many more observed entries. All these points will be discussed in detail in follow-up work where we will also numerically evaluate NORST-random for this problem.


\begin{algorithm}[t!]
\caption{NORST-Random for subspace tracking with missing data (ST-missing)}


\label{algo:auto-dyn-mc}


Algorithm \ref{norst} with the following changes
\ben
\item Replace line 3 with: compute $\Phat_0 \leftarrow \Phat_\init \leftarrow \text{Generate an $n \times r$ basis matrix from the random orthogonal model}$;  $\tildej~\leftarrow~1$, $k~\leftarrow~1$

\item Replace line 6 with the following
\bi
\item $\bpsi \leftarrow \bm{I} - \hat{\pt}_{(t-1)}\hat{\pt}_{(t-1)}{}'$; $\tty_t \leftarrow \bpsi \yt$;
 $\xhat_t \leftarrow \I_{\T_t} ( \bpsi_{\T_t}{}' \bpsi_{\T_t} )^{-1} \bpsi_{\T_t}{}'\tty_t$;  $\hat{\bm{\ell}}_t \leftarrow \yt - \hat{\bm{x}}_t$.
\ei
\een

\end{algorithm}


\subsection{Fewer than $r$ directions change}
It is possible to relax the lower bound on outlier magnitudes if not all of the subspace directions change at a given subspace change time. Suppose that only $r_\ch < r$ directions change. When $r_\ch=1$, we recover the guarantee of \cite{rrpcp_dynrpca} but for NORST (which is a simpler algorithm than s-reprocs).


Let $\P_{j-1, \fx}$ denote a basis for the fixed component of $\P_{j-1}$ and let $\P_{j-1,\ch}$ denote a basis for its changing component. Thus,
$\P_{j-1} \R = [ \P_{j-1,\fx}, \P_{j-1,\ch}]$, where $\bm{R}$ is a $r \times r$ rotation matrix. 
We have
\begin{align}\label{eq:rchdef1}
\P_j = [\P_{j-1,\fx}, \P_{j,\chd}]
\end{align}
where $\P_{j, \chd}$ is the changed component and has the same dimension as $\P_{j-1, \ch}$. Thus,
\begin{align}\label{eq:rchdef2}
\SE(\P_{j-1},\P_j) = \SE( \P_{j-1,\ch}, \P_{j,\chd})
\end{align}
and so $\Delta = \max_j \SE(\P_{j-1},\P_j) = \max_j \SE( \P_{j-1,\ch}, \P_{j,\chd})$.
Let $\lambda_{\ch}^+$ denote the largest eigenvalue along any direction in $\P_{j,\chd}$.
\begin{corollary}\label{cor:rch}
In Algorithm \ref{algo:auto-reprocs-pca}, replace line 17 by $\Phat_{(t)} \leftarrow \basis(\Phat_{j-1}, \Phat_{j, k})$. For basis matrices $\P_1, \P_2$, we use $\P = \basis(\P_1, \P_2)$ to mean that $\P$ is a basis matrix with column span equal to the column span of $[\P_1, \P_2]$.
Assume that  \eqref{eq:rchdef1} and \eqref{eq:rchdef2} hold. Also assume that the conditions of Theorem \ref{thm1} holds with the lower bound on $\xmint$ relaxed to $\xmint \ge C (\zz \sqrt{\eta (r - r_\ch) \lambda^+} + (\zz + \Delta) \sqrt{\eta r_\ch \lambda_\ch^+})$.
Then, all conclusions of Theorem \ref{thm1} hold.
\end{corollary}
{"config": "arxiv", "file": "2006.08030/norst_it_extensions.tex"}