Low rank subspace clustering (LRSC)

Vidal, René; Favaro, Paolo (2014). Low rank subspace clustering (LRSC). Pattern recognition letters, 43, pp. 47-61. Elsevier 10.1016/j.patrec.2013.08.006

[img] Text
1-s2.0-S0167865513003012-main.pdf - Published Version
Restricted to registered users only
Available under License Publisher holds Copyright.

Download (1MB) | Request a copy

We consider the problem of fitting a union of subspaces to a collection of data points drawn from one or more subspaces and corrupted by noise and/or gross errors. We pose this problem as a non-convex optimization problem, where the goal is to decompose the corrupted data matrix as the sum of a clean and self-expressive dictionary plus a matrix of noise and/or gross errors. By self-expressive we mean a dictionary whose atoms can be expressed as linear combinations of themselves with low-rank coefficients. In the case of noisy data, our key contribution is to show that this non-convex matrix decomposition problem can be solved in closed form from the SVD of the noisy data matrix. The solution involves a novel polynomial thresholding operator on the singular values of the data matrix, which requires minimal shrinkage. For one subspace, a particular case of our framework leads to classical PCA, which requires no shrinkage. For multiple subspaces, the low-rank coefficients obtained by our framework can be used to construct a data affinity matrix from which the clustering of the data according to the subspaces can be obtained by spectral clustering. In the case of data corrupted by gross errors, we solve the problem using an alternating minimization approach, which combines our polynomial thresholding operator with the more traditional shrinkage-thresholding operator. Experiments on motion segmentation and face clustering show that our framework performs on par with state-of-the-art techniques at a reduced computational cost.

Item Type:

Journal Article (Original Article)


08 Faculty of Science > Institute of Computer Science (INF)
08 Faculty of Science > Institute of Computer Science (INF) > Computer Vision Group (CVG)

UniBE Contributor:

Favaro, Paolo


000 Computer science, knowledge & systems
500 Science > 510 Mathematics








Paolo Favaro

Date Deposited:

09 May 2014 09:50

Last Modified:

05 Oct 2015 09:20

Publisher DOI:


Uncontrolled Keywords:

Subspace clustering, Low-rank and sparse methods, Principal component analysis, Motion segmentation, Face clustering





Actions (login required)

Edit item Edit item
Provide Feedback