Locally linear representation for image clustering

The construction of the similarity graph plays an essential role in a spectral clustering (SC) algorithm. There exist two popular schemes to construct a similarity graph, i.e. the pairwise distance-based scheme (PDS) and the linear representation-based scheme (LRS). It is notable that the above schemes suffered from some limitations and drawbacks, respectively. Specifically, the PDS is sensitive to noises and outliers, while the LRS may incorrectly select inter-subspaces points to represent the objective point. These drawbacks degrade the performance of the SC algorithms greatly. To overcome these problems, a novel scheme to construct the similarity graph is proposed, where the similarity computation among different data points depends on both their pairwise distances and the linear representation relationships. This proposed scheme, called locally linear representation (LLR), encodes each data point using a collection of data points that not only produce the minimal reconstruction error but also are close to the objective point, which makes it robust to noises and outliers, and avoids selecting inter-subspaces points to represent the objective point to a large extent.