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):

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).

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.

Tianyi,

Is there an implementation of GoDec available somewhere ?

Cheers,

Igor.

Hi Igor,

we just published a google site for GoDec: https://sites.google.com/site/godecomposition

You can find the MatLab on: http://sites.google.com/site/godecomposition/code

Cheers,

Tianyi