A simplified low rank and sparse graph for semi-supervised learning

• Sparse congruency representation is a simplified combination of the low rank and sparse representation.
• Sparse congruency representation saves great time when compared with the classical low rank based method.
• Sparse congruency representation uses only one parameter.
• Sparse congruency graph is more sparse and accurate than the low rank based method then used on the dataset containing overlapped subspaces.

Low rank representation is capable of capturing the global structure of mixed subspaces which are usually assumed to be independent. However, its computation is time-consuming. In practice, the data always distributes on subspaces that intersect or even overlap with each other. So the local structure of the data among the overlapping parts is important. Sparsity is a good property to accelerate the algorithm and capture the local linear structure. The drawback is that it breakups the low rank property of the reconstruction coefficient matrix when combining with low rank representation. In order to combine the two advantages properly, in this paper, we introduce a new constraint to the low rank representation matrix, which is called sparse congruency. Fortunately, we find that this new constraint is a simplification to the low rank and sparse constraints. Several experiments are implemented to demonstrate the efficiency of our method in semi-supervised classification.