Fast Low-Rank Subspace Segmentation
Fast Low-Rank Subspace Segmentation
复制标题
DOI：
10.1109/tkde.2013.114
复制
发表时间：
2014-05
影响因子：
8.9
通讯作者：
Xin Zhang;F. Sun;Guangcan Liu;Yi Ma
中科院分区：
文献类型：
--
作者：
Xin Zhang;F. Sun;Guangcan Liu;Yi Ma
子空间分割是将一组n个数据点分割(或分组)成多个簇的问题，每个簇是一个(线性)子空间。最近提出的稀疏子空间聚类(SSC)、低秩子空间表示(LRR)和低秩子空间分割(LRSS)等算法在分割精度方面是有效的，但它们的计算效率较低，因为它们的复杂度为O(N3)，对于n很大的情况来说太高了。本文设计了一种复杂度为O(nlog(N))的快速子空间分割算法。首先使用部分奇异值分解(SVD)逼近LRSS的解，然后利用局部敏感散列(LSH)构建稀疏亲和图来编码子空间成员关系，最后采用快速归一化切割(NCut)算法产生最终的分割结果。该算法除了具有较高的效率外，还具有与原LRSS方法相当的有效性。
Subspace segmentation is the problem of segmenting (or grouping) a set of n 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 O(n3), which is too high to afford for the case where n is very large. In this paper we devise a fast subspace segmentation algorithm with complexity of O(n log (n)). 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.