An improved Dissimilarity-Based Sparse Subset Selection Algorithm

The newly proposed Dissimilarity-Based Sparse Subset Selection (DS3) algorithm can effectively perform clustering of data and select the representative for each cluster simultaneously. It can be formulated as a row-sparsity of membership matrix and minimizing coding loss problem. However, the DS3 algorithm is sensitive to regularization parameter due to the limitation of the used norm for measuring sparse term. To obtain the correct number of representatives and clusters, users need to choose the regularization parameter carefully. In view of this, we consider using the $l_{2,\mathrm{p}}$-norm to replace the norm used to measure the sparsity of membership matrix in DS3, and propose an improved DS3 (IDS3) algorithm. Compared with the original algorithm, IDS3 is more robust to the regularization parameter and can obtain a better clustering in a larger parameter value range. IDS3 can be solved by using the Fixed Point Iteration Method aided Alternating Direction Multiplier Method (FPIM-ADMM) framework. Experimental results on some applications such as video summarization and scene categorization demonstrate that the proposed method is superior to DS3.