Side-information-induced reweighted sparse subspace clustering

Hua Huang; Weiwei Wang; Chengwu Lu; Xiangchu Feng; Ruiqiang He

doi:10.3934/jimo.2020019

Article Contents

2021, Volume 17, Issue 3: 1235-1252. Doi: 10.3934/jimo.2020019

This issue Previous Article Robust equilibrium control-measure policy for a DC pension plan with state-dependent risk aversion under mean-variance criterion Next Article Maximizing reliability of the capacity vector for multi-source multi-sink stochastic-flow networks subject to an assignment budget

Side-information-induced reweighted sparse subspace clustering

1.
School of Mathematics and Statistics, Xidian University, Xi'an 710171, Shaanxi, China
2.
Key Laboratory of Group & Graph Theories and Applications, Chongqing University of Arts and Sciences, Chongqing 402160, China

^* Corresponding author: Weiwei Wang
^* Corresponding author: Weiwei Wang

Received: February 28, 2019

Revised: June 30, 2019

Early access: January 2020

Published: May 2021

The first author is supported by National Natural Science Foundation of China (Grants 61472303, 61772389)

Abstract Full Text(HTML) Figure(8) / Table(4) Related Papers Cited by

Abstract

Subspace clustering segments a collection of data from a union of several subspaces into clusters with each cluster corresponding to one subspace. The geometric information of the dataset reflects its intrinsic structure and can be utilized to assist the segmentation. In this paper, we propose side-information-induced reweighted sparse subspace clustering (SRSSC) for high-dimensional data clustering. In our method, the geometric information of the high-dimensional data points in a target space is utilized to induce subspace clustering as side-information. We solve the method by iterating the reweighted $ l_1 $-norm minimization to obtain the self-representation coefficients of the data and segment the data using the spectral clustering framework. We compare the performance of our proposed algorithm with some state-of-the-art algorithms using synthetic data and three famous real datasets. Our proposed SRSSC algorithm is the simplest but the most effective. In the experiments, the results of these clustering algorithms verify the effectiveness of our proposed algorithm.

Keywords:

Mathematics Subject Classification: Primary: 62H30, 68T10; Secondary: 90C26.

Citation:

Full Text(HTML)

Figure 1. Illustration of a simple instance of subspace clustering

Download: Full-size image PowerPoint slide

Figure 2. Angles of pairs of data in the databases

Download: Full-size image PowerPoint slide

Figure 3. Convergence of SRSSC on the Extended YaleB dataset

Download: Full-size image PowerPoint slide

Figure 4. Visualization of the similarity matrices that were obtained by the different methods

Download: Full-size image PowerPoint slide

Figure 5. Some sample images from the Extended Yale B database

Download: Full-size image PowerPoint slide

Figure 6. The average computation times of the different algorithms using the Yale B dataset

Download: Full-size image PowerPoint slide

Figure 7. Some sample images from the COIL 20 database (top) and the images that belong to the same object (bottom)

Download: Full-size image PowerPoint slide

Figure 8. Some sample images from the USPS database

Download: Full-size image PowerPoint slide

Table 1. Performance comparison of the different algorithms using the synthetic data

Algorithms		LSR	SMR	LRR	SSC	StrSSC	RSSC	Ours
Accuracy	Mean	93.57%	94.35%	92.46%	94.04%	94.08%	96.60%	97.00%
Accuracy	Median	92.85%	94.07%	92.13%	93.60%	93.70%	96.10%	96.90%

| Show Table

DownLoad: CSV

Table 2. The clustering errors (%) of some different algorithms using the Extended Yale B dataset

No. of subject	Algorithms	LSR	SMR	LRR	SSC	StrSSC	RSSC	Ours
2 Subjects	Mean	7.35	1.75	2.13	1.87	1.23	0.57	0.48
2 Subjects	Median	7.03	0.78	0.78	0	0	0	0
3 Subjects	Mean	9.92	3.03	3.49	3.29	2.84	1.08	0.78
3 Subjects	Median	10.41	2.08	2.08	0.52	0.52	0	0.52
4 Subjects	Mean	13.66	3.25	4.86	3.80	2.95	1.65	1.07
4 Subjects	Median	14.07	2.34	3.91	1.95	0.78	0.39	0.39
5 Subjects	Mean	17.56	3.91	5.92	4.33	3.31	2.21	1.40
5 Subjects	Median	17.81	2.50	4.99	2.50	1.25	0.62	0.62
6 Subjects	Mean	20.95	5.28	6.83	4.87	3.73	2.79	1.68
6 Subjects	Median	21.07	2.86	5.99	3.39	2.08	1.30	1.04
7 Subjects	Mean	24.31	6.38	7.75	5.40	4.01	3.43	2.03
7 Subjects	Median	24.10	3.13	7.14	4.46	2.68	1.79	1.34
8 Subjects	Mean	27.52	6.83	11.05	5.92	4.38	3.98	2.59
8 Subjects	Median	27.83	3.71	7.42	4.69	3.13	1.86	1.56
9 Subjects	Mean	31.01	7.14	10.32	6.46	4.56	4.55	2.84
9 Subjects	Median	31.42	4.51	7.81	4.77	3.65	2.43	1.65
10 Subjects	Mean	33.49	7.81	16.95	7.40	4.74	4.90	3.33
10 Subjects	Median	32.81	7.03	18.91	5.63	4.22	3.59	2.03

| Show Table

DownLoad: CSV

Table 3. The clustering errors (%) of some comparative algorithms using the COIL 20 dataset

No. of subject	Algorithms	LSR	SMR	LRR	SSC	StrSSC	RSSC	Ours
2 Subjects	Mean	15.05	13.75	14.86	8.13	0.76	1.35	0.43
2 Subjects	Median	13.91	10.42	13.07	0	0	0	0
3 Subjects	Mean	22.16	21.97	21.81	10.87	1.86	1.37	0.72
3 Subjects	Median	20.22	19.44	19.65	1.85	0	0	0
20 Subjects	Mean(Mdian)	25.49	24.72	24.67	20.07	15.73	16.32	7.78

| Show Table

DownLoad: CSV

Table 4. The clustering errors (%) of some comparative algorithms using the USPS dataset

No. of subject	Algorithms	LSR	SMR	LRR	SSC	StrSSC	RSSC	Ours
2 Subjects	Mean	15.49	15.25	14.76	11.80	11.48	10.90	10.80
2 Subjects	Median	13.91	13.42	13.07	9.00	8.50	9.50	7.00
3 Subjects	Mean	29.13	28.91	28.81	27.59	27.88	27.44	26.67
3 Subjects	Median	27.02	16.34	26.37	21.83	25.67	23.82	21.33
10 Subjects	Mean(Median)	46.25	45.97	45.53	44.89	44.25	44.03	43.95

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

[1]	R. G. Baraniuk and et al., Applications of sparse representation and compressive sensing [scanning the issue], Proceedings of the IEEE 98, 6 (2010), 906–909.
[2]	S. Boyd and et al., Distributed optimization and statistical learning via the alternating direction method of multipliers, Foundations & Trends in Machine Learning, 3 (2010), 1–122.
[3]	S. Boyd and L. Vandenberghe, Convex Optimization, Cambridge University Press, Cambridge, 2004. doi: 10.1017/CBO9780511804441.
[4]	M. Brbić and I. Kopriva, $\ell_0$-Motivated Low-Rank Sparse Subspace Clustering, IEEE Transactions on Cybernetics, 2018.
[5]	E. J. Candes, M. B. Wakin and S. P. Boyd, Enhancing sparsity by reweighted $l_1$minimization, Journal of Fourier Analysis & Applications, 14 (2008), 877-905. doi: 10.1007/s00041-008-9045-x.
[6]	H. Z. Chen and et al., Discriminative and coherent subspace clustering, Neurocomputing, 284 (2018), 177–186.
[7]	H. Z. Chen, W. Wang and X. Feng, Structured sparse subspace clustering with grouping-effect-within-cluster, Pattern Recognition, (2018), S0031320318301948.
[8]	E. Elhamifar and R. Vidal, Sparse subspace clustering: Algorithm, theory, and applications, IEEE Transactions on Pattern Analysis and Machine Intelligence, 35 (2013), 2765-2781.
[9]	M. Fazel, H. Hindi and S. P. Boyd, Log-det heuristic for matrix rank minimization with applications to Hankel and Euclidean distance matrices., American Control Conference, Proceedings of the 2003 IEEE, (2003).
[10]	A. S. Georghiades, P. N. Belhumeur and D. J. Kriegman, From few to many: Illumination cone models for face recognition under variable lighting and pose, IEEE Transactions on Pattern Analysis and Machine Intelligence, 23 (2001), 643-660.
[11]	I. F. Gorodnitsky and B. D. Rao, Sparse signal reconstruction from limited data using FOCUSS: A re-weighted minimum norm algorithm, IEEE Transactions on Signal Processing, 45 (2002), 600-616.
[12]	M. Grant, S. Boyd and Y. Ye, CVX: Matlab software for disciplined convex programming, (2008).
[13]	H. Hu, Z. Lin, J. Feng and et al., Smooth representation clustering, Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, (2014), 3834–3841.
[14]	J. J. Hull, A database for handwritten text recognition research, IEEE Trans. Pattern Anal. Mach. Intell., 16 (1994).
[15]	V. C. Klema and A. J. Laub, The singular value decomposition: Its computation and some applications, IEEE Transactions on Automatic Control, 25 (1980), 164-176. doi: 10.1109/TAC.1980.1102314.
[16]	V. P. Kshirsagar, M. R. Baviskar and M. E. Gaikwad, Face Recognition Using Eigenfaces, International Conference on Computer Research & Development, 2011.
[17]	K. C. Lee, J. Ho and D. J. Kriegman, Acquiring linear subspaces for face recognition under variable lighting, IEEE Transactions on Pattern Analysis & Machine Intelligence, 27 (2005), 684-698.
[18]	C.-G. Li, C. You and R. Vidal., Structured sparse subspace clustering: A joint affinity learning and subspace clustering framework, IEEE Transactions on Image Processing, 26 (2017), 2988-3001. doi: 10.1109/TIP.2017.2691557.
[19]	C. L. Liu and et al., Handwritten digit recognition: Benchmarking of state-of-the-art techniques, Pattern Recognition, 36 (2003), 2271–2285.
[20]	G. C. Liu and et al., Robust recovery of subspace structures by low-rank representation, IEEE Transactions on Pattern Analysis and Machine Intelligence, 35 (2013), 171–184.
[21]	C. Y. Lu, H. Min, Z. Q. Zhao and et al., Robust and efficient subspace segmentation via least squares regression, European Conference on Computer Vision. Springer, Berlin, Heidelberg, (2012), 347–360.
[22]	U. von Luxburg, A tutorial on spectral clustering, Statistics and Computing, 17 (2007), 395-416. doi: 10.1007/s11222-007-9033-z.
[23]	S. A. Nene, S. K. Nayar and H. Murase, Columbia Object Image Library (COIL-20) (CUCS-005-96), Department of Computer Science, Columbia University, 1996.
[24]	N. R. Pal and K. P. Sankar, A review on image segmentation techniques, Pattern Recognition, 26 (1993), 1277-1294.
[25]	P. Wang and et al., Structural Reweight Sparse Subspace Clustering, Neural Processing Letters, 2018.
[26]	J. B. Shi and J. Malik, Normalized cuts and image segmentation, IEEE Transactions on Pattern Analysis and Machine Intelligence, 22 (2000), 888-905.
[27]	R. Tibshirani, Regression Shrinkage and Selection via the LASSO: A retrospective., Journal of the Royal Statistical Society. Series B: Methodological, 73 (2011), 273-282. doi: 10.1111/j.1467-9868.2011.00771.x.
[28]	C. Tomasi and T. Kanade, Shape and motion from image streams under orthography: A factorization method, International Journal of Computer Vision, 9 (1992), 137-154.
[29]	R. Tron and R. Vidal, A Benchmark for the Comparison of 3-D Motion Segmentation Algorithms, 2007 IEEE Conference on Computer Vision and Pattern Recognition IEEE Computer Society, 2007.
[30]	R. Vidal, Subspace clustering, Signal Processing Magazine IEEE, 28 (2011), 52-68.
[31]	W. W. Wang, C. Y. Chen, H. Z. Chen and X. C. Feng, Unified discriminative and coherent semi-supervised subspace clustering, IEEE Transactions on Image Processing, 27 (2018), 2461-2470. doi: 10.1109/TIP.2018.2806278.
[32]	W. W. Wang and C. L. Wu, Image segmentation by correlation adaptive weighted regression, Neurocomputing, 267 (2017), 426-435.
[33]	W. W. Wang, B. Zhang and X. Feng, Subspace segmentation by correlation adaptive regression, IEEE Transactions on Circuits & Systems for Video Technology, 99 (2017), 1-1.
[34]	J. W. Wong, Signal-to-Noise Ratio (SNR), Encyclopedia of Radiation Oncology, 2013.
[35]	J. Xu, K. Xu, K. Chen and et al., Reweighted sparse subspace clustering, Computer Vision and Image Understanding, 138 (2015), 25–37.
[36]	J. Y. Yan and M. Pollefeys, A General Framework for Motion Segmentation: Independent, Articulated, Rigid, Non-rigid, Degenerate and Non-degenerate, Computer Vision-ECCV 2006, 2006.
[37]	Y. Yang, J. Feng, N. Jojic and et al., $\ell^{0} $-sparse subspace clustering, European Conference on Computer Vision, Springer, Cham, (2016), 731–747.
[38]	T. Zhang, A. Szlam, Y. Wang and G. Lerman, Hybrid linear modeling via local best-fit flats, International Journal of Computer Vision, 100 (2012), 217-240. doi: 10.1007/s11263-012-0535-6.