Performance Analysis of Spectral Clustering on Compressed, Incomplete and Inaccurate Measurements

Understand

Spectral clustering is one of the most widely used techniques for extracting the underlying global structure of a data set.

• Compressed sensing and matrix completion have emerged as prevailing methods for efficiently recovering sparse and partially observed signals respectively.
• We combine the distance preserving measurements of compressed sensing and matrix completion with the power of robust spectral clustering.
• Our analysis provides rigorous bounds on how small errors in the affinity matrix can affect the spectral coordinates and clusterability.