Block-wise constrained sparse graph for face image representation

Subspace segmentation is one of the hottest issues in computer vision and machine learning fields. Generally, data (e.g. face images) are lying in a union of multiple linear subspaces, therefore, it is the key to find a block diagonal affinity matrix, which would result in segmenting data into different clusters correctly. Recently, graph construction based segmentation methods attract lots of attention. Following this line, we propose a novel approach to construct a Sparse Graph with Block-wise constraint for face representation, named SGB. Inspired by the recent study of least square regression coefficients, SGB firstly generates a compact block-diagonal coefficient matrix. Meanwhile, graph regularizer brings in a sparse graph, which focuses on the local structure and benefits multiple subspaces segmentation. By introducing different graph regularizers, our graph would be more balanced with b-matching constraint for balanced data. By using k-nearest neighbor regularizer, more manifold information can be preserved for unbalanced data. To solve our model, we come up with a joint optimization strategy to learn block-wise and sparse graph simultaneously. To demonstrate the effectiveness of our method, we consider two application scenarios, i.e., face clustering and kinship verification. Extensive results on Extended YaleB, ORL and kinship dataset Family101 demonstrate that our graph consistently outperforms several state-of-the-art graphs. Particularly, our method raises the performance bar by around 14% in kinship verification application.