ML p(r)ior | Online (and Offline) Robust PCA: Novel Algorithms and Performance Guarantees

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

2016-01-29
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.
PDF

Highlights - Most important sentences from the article

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

Related Articles

2017-05-24

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

Highlights - Most important sentences from the article

2018-04-24
1804.08796 | stat.ML

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

Highlights - Most important sentences from the article

2017-09-19

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

Highlights - Most important sentences from the article

2017-12-17

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

Highlights - Most important sentences from the article

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
PDF

Highlights - Most important sentences from the article

2019-03-21

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

Highlights - Most important sentences from the article

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
PDF

Highlights - Most important sentences from the article

2018-10-06

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

Highlights - Most important sentences from the article

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
PDF

Highlights - Most important sentences from the article

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
PDF

Highlights - Most important sentences from the article

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
PDF

Highlights - Most important sentences from the article

2017-10-05

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

Highlights - Most important sentences from the article

2019-02-10
1902.03653 | cs.LG

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

Highlights - Most important sentences from the article

2018-11-12

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

Highlights - Most important sentences from the article

2018-09-11
1809.04176 | cs.LG

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

Highlights - Most important sentences from the article

2019-02-13

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

Highlights - Most important sentences from the article