Fast Low-Rank Subspace Segmentation
Lists
Only you see this
Abstract
Subspace segmentation is the problem of segmenting (or grouping) a set of <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="TeX">$n$ </tex-math></inline-formula> data points into a number of clusters, with each cluster being a (linear) subspace. The recently established algorithms such as Sparse Subspace Clustering (SSC), Low-Rank Representation (LRR) and Low-Rank Subspace Segmentation (LRSS) are effective in terms of segmentation accuracy, but computationally inefficient as they possess a complexity of <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="TeX">$O(n^{3})$ </tex-math></inline-formula> , which is too high to afford for the case where <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="TeX">$n$ </tex-math></inline-formula> is very large. In this paper we devise a fast subspace segmentation algorithm with complexity of <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="TeX">$O(n\log (n))$ </tex-math></inline-formula> . This is achieved by firstly using partial Singular Value Decomposition (SVD) to approximate the solution of LRSS, secondly utilizing Locality Sensitive Hashing (LSH) to build a sparse affinity graph that encodes the subspace memberships, and finally adopting a fast Normalized Cut (NCut) algorithm to produce the final segmentation results. Besides of high efficiency, our algorithm also has comparable effectiveness as the original LRSS method.
BibTeX
@article{zhang2014fast,
author = {Xin Zhang and Fuchun Sun and Guangcan Liu and Yi Ma},
title = {{Fast Low-Rank Subspace Segmentation}},
journal = {IEEE Trans. Knowl. Data Eng.},
year = {2014},
url = {https://openreview.net/forum?id=VW301yPCoYb},
}Loading related content...