This work studies two interrelated problems - online robust PCA (RPCA) and
online low-rank matrix completion (MC). In recent work by Cand\`{e}s et al.,
RPCA has been defined as a problem of separating a low-rank matrix (true data),
$L:=[\ell_1, \ell_2, \dots \ell_{t}, \dots , \ell_{t_{\max}}]$ and a sparse
matrix (outliers), $S:=[x_1, x_2, \dots x_{t}, \dots, x_{t_{\max}}]$ from their
sum, $M:=L+S$. Our work uses this definition of RPCA. An important application
where both these problems occur is in video analytics in trying to separate
sparse foregrounds (e.g., moving objects) and slowly changing backgrounds.
While there has been a large amount of recent work on both developing and
analyzing batch RPCA and batch MC algorithms, the online problem is largely
open. In this work, we develop a practical modification of our recently
proposed algorithm to solve both the online RPCA and online MC problems. The
main contribution of this work is that we obtain correctness results for the
proposed algorithms under mild assumptions. The assumptions that we need are:
(a) a good estimate of the initial subspace is available (easy to obtain using
a short sequence of background-only frames in video surveillance); (b) the
$\ell_t$'s obey a `slow subspace change' assumption; (c) the basis vectors for
the subspace from which $\ell_t$ is generated are dense (non-sparse); (d) the
support of $x_t$ changes by at least a certain amount at least every so often;
and (e) algorithm parameters are appropriately set

本文研究了在线的鲁棒主成分分析（robust PCA）和在线低秩矩阵补全（low-rank matrix completion）的问题并提出了实用的算法，主要的贡献是在容易满足的假设下提供了正确性结果。

在线矩阵补全和在线鲁棒主成分分析

Online Matrix Completion and Online Robust PCA

The recently established RPCA method provides us a convenient way to restore
low-rank matrices from grossly corrupted observations. While elegant in theory
and powerful in reality, RPCA may be not an ultimate solution to the low-rank
matrix recovery problem. Indeed, its performance may not be perfect even when
data are strictly low-rank. This is because conventional RPCA ignores the
clustering structures of the data which are ubiquitous in modern applications.
As the number of cluster grows, the coherence of data keeps increasing, and
accordingly, the recovery performance of RPCA degrades. We show that the
challenges raised by coherent data (i.e., the data with high coherence) could
be alleviated by Low-Rank Representation (LRR), provided that the dictionary in
LRR is configured appropriately. More precisely, we mathematically prove that
if the dictionary itself is low-rank then LRR is immune to the coherence
parameter which increases with the underlying cluster number. This provides an
elementary principle for dealing with coherent data. Subsequently, we devise a
practical algorithm to obtain proper dictionaries in unsupervised environments.
Our extensive experiments on randomly generated matrices verify our claims.

研究表明，当数据具有高相干性时，常规的 RPCA 方法表现不佳。使用低秩表示（LRR）能够缓解这一问题，并且当字典本身是低秩的时，LRR 更能有效地处理相干数据。作者设计了一种无监督环境下获取适当字典的实用算法，并在随机生成的矩阵上进行广泛实验以验证其结果。