Greedy Subspace Clustering

The project team proposes to 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, the project team provides new simple and efficient algorithms for this problem. Their 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 the team's theory. The project team also shows that their 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.

• Record URL:
  http://ctr.utexas.edu/research/d-stop/research/

Language

• English

Project

• Status: Completed
• Funding: $33000
• Contract Numbers:

  DTRT13-G-UTC58

• Sponsor Organizations:

  Office of the Assistant Secretary for Research and Technology

  University Transportation Centers Program
  Department of Transportation
  Washington, DC  United States  20590
• Project Managers:

  Bhat, Chandra

• Performing Organizations:

  Data-Supported Transportation Operations and Planning Center

  University of Texas at Austin
  Austin, TX  United States  78701
• Principal Investigators:

  Caramanis, Constantine

• Start Date: 20141201
• Expected Completion Date: 20160930
• Actual Completion Date: 20160930
• Source Data: 111

Subject/Index Terms

• TRT Terms: Algorithms; Cluster analysis; Data analysis; Implementation; Statistical analysis
• Subject Areas: Data and Information Technology; Planning and Forecasting; Transportation (General);

Filing Info

• Accession Number: 01580147
• Record Type: Research project
• Source Agency: Data-Supported Transportation Operations and Planning Center
• Contract Numbers: DTRT13-G-UTC58
• Files: UTC, RIP
• Created Date: Oct 29 2015 11:59AM