GoDec: Randomized Low-rank & Sparse Matrix Decomposition in Noisy Case

This paper is accepted by ICML 2011 for presentation. Now the final version is ready and can be downloaded from here GO.

Abstract:

Low-rank and sparse structures have been profoundly studied in matrix completion and compressed sensing. In this paper, we develop “Go Decomposition” (GoDec) to efficiently and robustly estimate the low-rank part $L$ and the sparse part $S$ of a matrix $X=L+S+G$ with noise $G$. GoDec alternatively assigns the low-rank approximation of $X-S$ to $L$ and the sparse approximation of $X-L$ to $S$. The algorithm can be significantly accelerated by bilateral random projections (BRP). We also propose GoDec for matrix completion as an important variant. We prove that the objective value $\|X-L-S\|_F^2$ converges to a local minimum, while $L$ and $S$ linearly converge to local optimums. Theoretically, we analyze the influence of $L$, $S$ and $G$ to the asymptotic/convergence speeds in order to discover the robustness of GoDec. Empirical studies suggest the efficiency, robustness and effectiveness of GoDec comparing with representative matrix decomposition and completion tools, e.g., Robust PCA and OptSpace.

The most interesting aspect of GoDec is that it builds an extremely simple model and develops an fast, randomized algorithm to produce an approximated low-rank + sparse decomposition when rank and cardinality are constrained, and the extra noise exists. This is always the case in real applications, where the model complexity needs to be pre-determined, and neither the low-rank nor sparse part is the noise.

Another interesting aspect is that the linear convergence, asymptotic speed and robustness to the noise of GoDec can be well proved in the scheme of “alternating projections on manifolds”. Actually, the naive GoDec can be written as alternating projections of one variable on two manifolds. By analysing the properties of the manifolds and projections, some significant theoretical conclusions can be drawn.

An important variant of GoDec can be applied to matrix completion problem with competitive efficiency.

The GoDec algorithm itself is fairly simple for implementation.

Here is two applications of GoDec in computer vision (similar effect with RPCA, but with different model assumption and algorithm, and much faster speed):

Experiment on background modeling of four 200-frame surveillance video sequences

Top left: lobby in an office building (resolution 128X160, learning time 39.75 seconds). Top right: shopping center (resolution 256X320, learning time 203.72 seconds). Bottom left: Restaurant (resolution 120X160, learning time 36.84 seconds). Bottom right: Hall of a business building (resolution 144X176, learning time 47.38 seconds).

Experiment on shadow/light removal of face images from four individuals in Yale B database.

Each individual has 64 images with resolution 192X168 and needs 24 seconds learning time.

It is worthy to note the difference between GoDec and Robust PCA with its extension stable principal component pursuit (SPCP). They have intersections on their application tasks. But their assumptions to data, their models and optimization algorithms are extirely different, thus they works for different situations.

Advertisements

About tianyizhou

Research Assistant at University Washington, Seattle, Working on Machine Learning & Statistics in MODE lab leaded by Prof. Carlos Guestrin, and MELODI lab leaded by Prof. Jeff Bilmes.
This entry was posted in Tianyi's work and tagged , , , , , , , , . Bookmark the permalink.

2 Responses to GoDec: Randomized Low-rank & Sparse Matrix Decomposition in Noisy Case

  1. Igor Carron says:

    Tianyi,

    Is there an implementation of GoDec available somewhere ?

    Cheers,

    Igor.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s