Restricted Connection Orthogonal Matching Pursuit for Sparse Subspace Clustering

Wenqi Zhu, Shuai Yang, Yuesheng ZhuIEEE Signal Processing Letters 2019 · DOI · OpenReview

TL;DR

This paper introduces RCOMP-SSC, a novel algorithm that improves the accuracy of Sparse Subspace Clustering (SSC) while maintaining its computational efficiency. By restricting the number of connections each data point can form during the Orthogonal Matching Pursuit (OMP) process, RCOMP-SSC achieves better clustering performance, especially in the presence of noise and for large datasets.

What Problem Does This Paper Address?

Subspace clustering (SC) is a powerful technique for grouping high-dimensional data that can be approximated as a union of low-dimensional subspaces. Sparse Subspace Clustering (SSC) is a popular SC method that leverages sparse self-representation to identify these subspaces. However, standard SSC can be computationally expensive, especially for large datasets. While Orthogonal Matching Pursuit (OMP) can accelerate SSC (leading to SSC-OMP), this speedup often comes at the cost of reduced clustering accuracy, particularly when the data contains noise. Existing methods to improve SSC-OMP, like AOMP-SSC and SSC-ROMP, tend to increase computational complexity or alter the original data distribution. This paper aims to bridge this gap by proposing a method that enhances accuracy and robustness to noise without sacrificing computational efficiency or distorting the data.

Methods

The core innovation of this paper is the Restricted Connection Orthogonal Matching Pursuit for Sparse Subspace Clustering (RCOMP-SSC). The authors observe that the number of connections a data point forms (both as a source and a target of connections) significantly impacts clustering accuracy. Too many connections, especially spurious ones due to noise or data points near subspace intersections, can degrade performance.

RCOMP-SSC addresses this by introducing a "connection limit" (rcon) for each data point during the OMP iteration. Instead of allowing OMP to greedily select as many neighbors as needed (up to a fixed k), RCOMP-SSC restricts the total number of connections a data point can participate in. This is achieved through a novel "control matrix" framework. This matrix modulates the inner products used by OMP to select neighbors. Specifically, it can zero out potential connections, effectively dropping data points or limiting their selection as neighbors. This framework is designed to be scalable and adaptable, allowing for the implementation of various data point selection strategies. The authors propose setting rcon=2 as a general rule, which tends to create a more balanced connectivity structure and makes the algorithm robust to noise.

Datasets

The paper evaluates RCOMP-SSC on:

  • Synthetic data: Generated with varying numbers of subspaces, dimensions, data points per subspace, and noise levels.
  • Real-world datasets:
    • Usps: A handwritten digit dataset (0-9) used for image segmentation.
  • Extended Yale B (EYaleB): A dataset of frontal face images under varying illumination conditions, used for face image clustering.

Key Insights and Ideas

  • Connection count matters: The number of connections a data point forms is a crucial factor in subspace clustering accuracy, not just the sparsity parameter k in OMP.
  • Over-connectivity is detrimental: Excessive connections, especially those formed due to noise or data points at subspace intersections, can weaken the subspace detection property and reduce accuracy.
  • Restricting connections improves robustness: By limiting the number of connections per data point (RCOMP-SSC), the algorithm becomes more robust to noise and better handles data points near subspace boundaries.
  • Scalable control framework: The proposed control matrix framework offers a flexible and scalable way to implement restricted connection strategies, allowing for integration with other selection methods.
  • Balancing accuracy and efficiency: RCOMP-SSC aims to strike a balance, offering improved accuracy and noise robustness over SSC-OMP while remaining computationally efficient.

Key Results

  • Synthetic Data: RCOMP-SSC demonstrates superior accuracy compared to OMP and SSC, especially in the presence of noise. It also shows better performance as data density increases, where OMP's accuracy declines.
  • Usps Dataset: RCOMP-SSC achieves higher accuracy across different dataset sizes (200-1000 samples) compared to OMP, AOMP, ROMP, SSC, ENSC, and LRR. It is also significantly faster than most methods, except for OMP.
  • EYaleB Dataset: RCOMP-SSC outperforms other methods in face image clustering across varying numbers of persons (5-38), showcasing its effectiveness in multi-class scenarios.
  • Computational Efficiency: RCOMP-SSC is significantly faster than SSC and comparable to OMP, making it suitable for large-scale applications.

Limitations and Future Work

  • Parameter Tuning: While rcon=2 is suggested as a general rule, the optimal value might still depend on the specific dataset characteristics. The paper doesn't extensively explore the impact of varying rcon beyond this general guideline.
  • Future Work: The authors suggest that their control matrix framework is scalable and can be adapted for other data point selection strategies, implying potential for further research in this direction. The paper also implicitly suggests that exploring different connection restriction strategies beyond a simple count could be a fruitful avenue.

Summary updated

Abstract

Sparse Subspace Clustering (SSC) is one of the most popular methods for clustering a group of data points lying in a union of low-dimensional subspaces. However, SSC may suffer from heavy computational burden. Applying Orthogonal Matching Pursuit (OMP) on SSC may accelerate the computation but the trade-off is the loss of clustering accuracy. In this letter, we propose a noise-robust algorithm, Restricted Connection Orthogonal Matching Pursuit for Sparse Subspace Clustering (RCOMP-SSC), to improve the clustering accuracy and remain computationally efficient by restricting the number of connections of each data point during the iteration of OMP. Also, we develop a framework of control matrix to realize RCOMP-SSC. The proposed control matrix can be applied to other selection strategies for data point. Our analysis and experiments on synthetic data and two real-world databases (EYaleB & Usps) have demonstrated that our algorithm outperforms other methods in clustering accuracy.
BibTeX
@article{zhu2019restricted,
  author = {Wenqi Zhu and Shuai Yang and Yuesheng Zhu},
  title = {{Restricted Connection Orthogonal Matching Pursuit for Sparse Subspace Clustering}},
  journal = {IEEE Signal Processing Letters},
  year = {2019},
  doi = {10.1109/lsp.2019.2953638},
}
Figure