Greedy subspace clustering.

Details

• Creators:
  Park, Dohyung ; Caramanis, Constantine ; Sanghavi, Sujay
• Corporate Creators:
  University of Texas at Austin. Data-Supported Transportation Operations & Planning Center (D-STOP)
• Corporate Contributors:
  University Transportation Centers Program (U.S.) ; United States. Dept. of Transportation. Office of the Assistant Secretary for Research and Technology
• Subject/TRT Terms:
  • Computer vision
  • Highway operations
  • Statistical analysis
  • Greedy algorithms
  • subspace clustering
• Publication/ Report Number:
  D-STOP/2016/111 ; Technical Report 111
• Resource Type:
  Tech Report
• Geographical Coverage:
  United States
• TRIS Online Accession Number:
  1643861
• Corporate Publisher:
  University of Texas at Austin. Data-Supported Transportation Operations & Planning Center (D-STOP)
• Abstract:
  We consider the problem of subspace clustering: given points that lie on or near the union of many low-dimensional linear subspaces, recover the subspaces. To this end, one first identifies sets of points close to the same subspace and uses the sets to estimate the subspaces. As the geometric structure of the clusters (linear subspaces) forbids proper performance of general distance based approaches such as K-means, many model-specific methods have been proposed. In this paper, we provide new simple and efficient algorithms for this problem. Our statistical analysis shows that the algorithms are guaranteed exact (perfect) clustering performance under certain conditions on the number of points and the affinity between subspaces. These conditions are weaker than those considered in the standard statistical literature. Experimental results on synthetic data generated from the standard unions of subspaces model demonstrate our theory. We also show that our algorithm performs competitively against state-of-the-art algorithms on real-world applications such as motion segmentation and face clustering, but with much simpler implementation and lower computational cost.
• Format:
  PDF
• Funding:
  DTRT13-G-UTC58
• Download URL:
  https://rosap.ntl.bts.gov/view/dot/32601/dot_32601_DS1.pdf
• File Type:
  [PDF - 556.17 KB]
• Collection(s):
  University Transportation Centers ; US Transportation Collection
• Main Document Checksum:
  urn:sha256:962e2493a545829402b92d6f51fd702389727eccb7f2a3a866eb217ba8739b30