Low Rank Subspace Clustering

Introduction

Similar to sparse subspace clustering, low-rank subspace clustering (LRSC) aims to cluster points based on rank of the subspace they belong to. In the case of anomaly motion detection, the trajectories of similar moving objects can be thought of lying in a different low rank affine subspace. Intuitively, the rank of points for background will have the lowest subspace rank and the points for an anomaly will have the highest subspace rank of all (but still its rank will be way lower than the space in which the points lie in). Instead of minimizing L1 norm as done by SSC, LRSC algorithm tries to minimize the nuclear norm of the coefficient matrix.

Theorem

For data points drawn from a union of low rank independent linear subspaces, representation can be found by solving the following convex problem

where D is the dictionary matrix formed from the data points. Fortunately, the optimization has a closed form solution given by singular value decomposition of the dictionary :

For strictly independent subspaces, the non-zero entries of the coefficient matrix C correspond to the points in the same subspace.

Application to background separation

LRSC algorithm was tried only to separate the low rank video background from its sparse component using the motion trajectories of the keypoints of a frame. The points were detected using SURF features and tracked with KLT tracker. It can be seen from the following video that the results are not good enough as compared to the Robust PCA approach. One reason could be that the low rank subspaces for the background and the pedestrian motion are not entirely independent, and have some of correlation between them. The green points are intended for the background subspace whereas the blue points form the pedestrian subspace.

Novel extension for LRSC and SSC

While working with both SSC and LRSC algorithms to segment video objects using motion, we got an insight that the tajectory points can have sparsest representation using the points in the same subspace (SSC) and these subspaces are low rank (LRSC).

Hence, the anomalies can be detected by clustering the coefficient matrix C which is both low rank as well as sparse. The problem can be formulated as:

As discussed during the presentation, a simple condition for the solution to hold is that the dictionary D should be a fat matrix. This ensures that the null space of the matrix is non-trivial. A more detailed condition for the solution and the results from its application would be considered in future.