### Online (and Offline) Robust PCA: Novel Algorithms and Performance Guarantees

**2016-01-29**

1601.07985 | cs.IT

In this work, we study the online robust principal components' analysis
(RPCA) problem. In recent work, RPCA has been defined as a problem of
separating a low-rank matrix (true data), $L$, and a sparse matrix (outliers),
$S$, from their sum, $M:=L + S$. A more general version of this problem is to
recover $L$ and $S$ from $M:=L + S + W$ where $W$ is the matrix of unstructured
small noise/corruptions. An important application where this problem occurs is
in video analytics in trying to separate sparse foregrounds (e.g., moving
objects) from slowly changing backgrounds. While there has been a large amount
of recent work on solutions and guarantees for the batch RPCA problem, the
online problem is largely open."Online" RPCA is the problem of doing the above
on-the-fly with the extra assumptions that the initial subspace is accurately
known and that the subspace from which $l_t$ is generated changes slowly over
time. We develop and study a novel "online" RPCA algorithm based on the
recently introduced Recursive Projected Compressive Sensing (ReProCS)
framework. Our algorithm improves upon the original ReProCS algorithm and it
also returns even more accurate offline estimates. The key contribution of this
work is a correctness result (complete performance guarantee) for this
algorithm under reasonably mild assumptions. By using extra assumptions --
accurate initial subspace knowledge, slow subspace change, and clustered
eigenvalues -- we are able to remove one important limitation of batch RPCA
results and two key limitations of a recent result for ReProCS for online RPCA.
To our knowledge, this work is among the first few correctness results for
online RPCA. Most earlier results were only partial results, i.e., they
required an assumption on intermediate algorithm estimates.

**Login to like/save this paper, take notes and configure your recommendations**

# Related Articles

**2017-05-24**

1705.08948 | cs.IT

Dynamic robust PCA refers to the dynamic (time-varying) extension of robust
PCA (RPCA). It assumes t… show more

**2018-04-24**

1804.08796 | stat.ML

Although the computational and statistical trade-off for modeling single
graphs, for instance, using… show more

**2017-09-19**

1709.06255 | stat.ML

This work obtains novel finite sample guarantees for Principal Component
Analysis (PCA). These hold … show more

**2017-12-17**

1712.06061 | cs.IT

In this work, we study the robust subspace tracking (RST) problem and obtain
one of the first two pr… show more

**2018-05-17**

1805.06837 | stat.ML

We propose a new method of estimation in topic models, that is not a
variation on the existing simpl… show more

**2019-03-21**

1903.09122 | cs.LG

In this paper, we analyze the finite sample complexity of stochastic system
identification using mod… show more

**2017-06-13**

1706.03896 | cs.LG

We present a mathematical analysis of a non-convex energy landscape for
robust subspace recovery. We… show more

**2018-10-06**

1810.03051 | cs.LG

We study the problem of subspace tracking in the presence of missing data
(ST-miss). In recent work,… show more

**2018-05-17**

1805.06834 | cs.LG

We present a high-dimensional analysis of three popular algorithms, namely,
Oja's method, GROUSE and… show more

**2019-03-07**

1903.02742 | cs.DS

We consider the extensively studied problem of $\ell_2/\ell_2$ compressed
sensing. The main contribu… show more

**2019-05-11**

1905.04447 | cs.DS

Many convex problems in machine learning and computer science share the same
form: \begin{align*} \m… show more

**2017-10-05**

1710.02101 | cs.LG

A Bernoulli Mixture Model (BMM) is a finite mixture of random binary vectors
with independent Bernou… show more

**2019-02-10**

1902.03653 | cs.LG

Given a linear regression setting, Iterative Least Trimmed Squares (ILTS)
involves alternating betwe… show more

**2018-11-12**

1811.04852 | cs.DS

We present classical sublinear-time algorithms for solving low-rank linear
systems of equations. Our… show more

**2018-09-11**

1809.04176 | cs.LG

This work takes the first steps towards solving the "phaseless subspace
tracking" (PST) problem. PST… show more

**2019-02-13**

1902.04972 | cs.LG

We study the following problem: recover a low-rank matrix from phaseless
(magnitude-only) linear pro… show more