
-
Previous Article
Probabilistic interpretation of the Calderón problem
- IPI Home
- This Issue
-
Next Article
Recovering the boundary corrosion from electrical potential distribution using partial boundary data
Subspace clustering by (k,k)-sparse matrix factorization
Department of Mathematics, The Hong Kong University of Science and Technology, Clear Water Bay, Kowloon, Hong Kong, China |
High-dimensional data often lie in low-dimensional subspaces instead of the whole space. Subspace clustering is a problem to analyze data that are from multiple low-dimensional subspaces and cluster them into the corresponding subspaces. In this work, we propose a $(k,k)$-sparse matrix factorization method for subspace clustering. In this method, data itself is considered as the "dictionary", and each data point is represented as a linear combination of the basis of its cluster in the dictionary. Thus, the coefficient matrix is low-rank and sparse. With an appropriate permutation, it is also blockwise with each block corresponding to a cluster. With an assumption that each block is no more than $k$-by-$k$ in matrix recovery, we seek a low-rank and $(k,k)$-sparse coefficient matrix, which will be used for the construction of affinity matrix in spectral clustering. The advantage of our proposed method is that we recover a coefficient matrix with $(k,k)$-sparse and low-rank simultaneously, which is better fit for subspace clustering. Numerical results illustrate the effectiveness that it is better than SSC and LRR in real-world classification problems such as face clustering and motion segmentation.
References:
[1] |
P. K. Agarwal and N. H. Mustafa, k-means projective clustering, in Proceedings of the
twenty-third ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, ACM, 2004, 155–165.
doi: 10.1145/1055558.1055581. |
[2] |
A. Argyriou, R. Foygel and N. Srebro, Sparse prediction with the k-support norm, in Advances
in Neural Information Processing Systems, 2012, 1457–1465. |
[3] |
J. Bolte, S. Sabach and M. Teboulle,
Proximal alternating linearized minimization for nonconvex and nonsmooth problems, Mathematical Programming, 146 (2014), 459-494.
doi: 10.1007/s10107-013-0701-9. |
[4] |
V. Chandrasekaran, B. Recht, P. A. Parrilo and A. S. Willsky,
The convex geometry of linear inverse problems, Foundations of Computational mathematics,, 12 (2012), 805-849.
|
[5] |
G. Chen and G. Lerman,
Spectral curvature clustering (scc), International Journal of Computer Vision, 81 (2009), 317-330.
doi: 10.1007/s11263-008-0178-9. |
[6] |
J. P. Costeira and T. Kanade,
A multibody factorization method for independently moving objects, International Journal of Computer Vision, 29 (1998), 159-179.
|
[7] |
H. Derksen, Y. Ma, W. Hong and J. Wright, Segmentation of multivariate mixed data via lossy coding and compression in Electronic Imaging 2007, International Society for Optics and Photonics (2007), 65080H.
doi: 10.1117/12.714912. |
[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.
doi: 10.1109/TPAMI.2013.57. |
[9] |
P. Favaro, R. Vidal and A. Ravichandran, A closed form solution to robust subspace estimation and clustering, in 2011 IEEE Conference on Computer Vision and Pattern Recognition
(CVPR), IEEE, 2011, 1801–1807.
doi: 10.1109/CVPR.2011.5995365. |
[10] |
J. Feng, Z. Lin, H. Xu and S. Yan, Robust subspace segmentation with block-diagonal prior,
in IEEE Conference on Computer Vision and Pattern Recognition, IEEE, 2014, 3818–3825.
doi: 10.1109/CVPR.2014.482. |
[11] |
A. Goh and R. Vidal, Segmenting motions of different types by unsupervised manifold clustering, in IEEE Conference on Computer Vision and Pattern Recognition, IEEE, 2007, 1–6.
doi: 10.1109/CVPR.2007.383235. |
[12] |
L. N. Hutchins, S. M. Murphy, P. Singh and J. H. Graber,
Position-dependent motif characterization using non-negative matrix factorization, Bioinformatics, 24 (2008), 2684-2690.
doi: 10.1093/bioinformatics/btn526. |
[13] |
K. Lee, J. Ho and D. Kriegman,
Acquiring linear subspaces for face recognition under variable lighting, IEEE Transactions on Pattern Analysis and Machine Intelligence, 27 (2005), 684-698.
|
[14] |
G. Liu, Z. Lin and Y. Yu, Robust subspace segmentation by low-rank representation, in
Proceedings of the 27th international conference on machine learning, 2010, 663–670. |
[15] |
L. Lu and R. Vidal, Combined central and subspace clustering for computer vision applications, in Proceedings of the 23rd international conference on Machine learning, ACM,
2006, 593–600.
doi: 10.1145/1143844.1143919. |
[16] |
B. Nasihatkon and R. Hartley, Graph connectivity in sparse subspace clustering, in Computer
Vision and Pattern Recognition (CVPR), 2011 IEEE Conference on, IEEE, 2011, 2137–2144.
doi: 10.1109/CVPR.2011.5995679. |
[17] |
A. Y. Ng, M. I. Jordan and Y. Weiss,
On spectral clustering: Analysis and an algorithm, Advances in Neural Information Processing Systems, 2 (2002), 849-856.
|
[18] |
S. Oymak, A. Jalali, M. Fazel, Y. C. Eldar and B. Hassibi,
Simultaneously structured models with application to sparse and low-rank matrices, Information Theory, IEEE Transactions on, 61 (2015), 2886-2908.
doi: 10.1109/TIT.2015.2401574. |
[19] |
N. Parikh and S. Boyd,
Proximal algorithms, Foundations and Trends in optimization, 1 (2014), 127-239.
doi: 10.1561/2400000003. |
[20] |
M. J. D. Powell,
On search directions for minimization algorithms, Mathematical Programming, 4 (1973), 193-201.
doi: 10.1007/BF01584660. |
[21] |
S. R. Rao, R. Tron, R. Vidal and Y. Ma, Motion segmentation via robust subspace separation
in the presence of outlying, incomplete, or corrupted trajectories, in IEEE Conference on
Computer Vision and Pattern Recognition, IEEE, 2008, 1–8.
doi: 10.1109/CVPR.2008.4587437. |
[22] |
E. Richard, G. R. Obozinski and J. -P. Vert, Tight convex relaxations for sparse matrix factorization, in Advances in Neural Information Processing Systems, 2014, 3284–3292. |
[23] |
Y. Sugaya and K. Kanatani, Geometric structure of degeneracy for multi-body motion segmentation, in Statistical Methods in Video Processing, Springer, 2004, 13–25.
doi: 10.1007/978-3-540-30212-4_2. |
[24] |
M. E. Tipping and C. M. Bishop,
Mixtures of probabilistic principal component analyzers, Neural Computation, 11 (1999), 443-482.
doi: 10.1162/089976699300016728. |
[25] |
R. Vidal,
A tutorial on subspace clustering, IEEE Signal Processing Magazine, 28 (2010), 52-68.
|
[26] |
R. Vidal, Y. Ma and S. Sastry,
Generalized Principal Component Analysis (GPCA), Interdisciplinary Applied Mathematics, 40. Springer, New York, 2016.
doi: 10.1007/978-0-387-87811-9. |
[27] |
Y. -X. Wang, H. Xu and C. Leng, Provable subspace clustering: When LRR meets SSC, in
Advances in Neural Information Processing Systems, 2013, 64–72. |
[28] |
J. Yan and M. Pollefeys, A general framework for motion segmentation: Independent, articulated, rigid, non-rigid, degenerate and non-degenerate, in Computer Vision–ECCV 2006,
Springer, 2006, 94–106.
doi: 10.1007/11744085_8. |
[29] |
W. I. Zangwill,
Nonlinear Programming: A Unified Approach, vol. 196, Prentice-Hall Englewood Cliffs, NJ, 1969. |
[30] |
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. |
show all references
References:
[1] |
P. K. Agarwal and N. H. Mustafa, k-means projective clustering, in Proceedings of the
twenty-third ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, ACM, 2004, 155–165.
doi: 10.1145/1055558.1055581. |
[2] |
A. Argyriou, R. Foygel and N. Srebro, Sparse prediction with the k-support norm, in Advances
in Neural Information Processing Systems, 2012, 1457–1465. |
[3] |
J. Bolte, S. Sabach and M. Teboulle,
Proximal alternating linearized minimization for nonconvex and nonsmooth problems, Mathematical Programming, 146 (2014), 459-494.
doi: 10.1007/s10107-013-0701-9. |
[4] |
V. Chandrasekaran, B. Recht, P. A. Parrilo and A. S. Willsky,
The convex geometry of linear inverse problems, Foundations of Computational mathematics,, 12 (2012), 805-849.
|
[5] |
G. Chen and G. Lerman,
Spectral curvature clustering (scc), International Journal of Computer Vision, 81 (2009), 317-330.
doi: 10.1007/s11263-008-0178-9. |
[6] |
J. P. Costeira and T. Kanade,
A multibody factorization method for independently moving objects, International Journal of Computer Vision, 29 (1998), 159-179.
|
[7] |
H. Derksen, Y. Ma, W. Hong and J. Wright, Segmentation of multivariate mixed data via lossy coding and compression in Electronic Imaging 2007, International Society for Optics and Photonics (2007), 65080H.
doi: 10.1117/12.714912. |
[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.
doi: 10.1109/TPAMI.2013.57. |
[9] |
P. Favaro, R. Vidal and A. Ravichandran, A closed form solution to robust subspace estimation and clustering, in 2011 IEEE Conference on Computer Vision and Pattern Recognition
(CVPR), IEEE, 2011, 1801–1807.
doi: 10.1109/CVPR.2011.5995365. |
[10] |
J. Feng, Z. Lin, H. Xu and S. Yan, Robust subspace segmentation with block-diagonal prior,
in IEEE Conference on Computer Vision and Pattern Recognition, IEEE, 2014, 3818–3825.
doi: 10.1109/CVPR.2014.482. |
[11] |
A. Goh and R. Vidal, Segmenting motions of different types by unsupervised manifold clustering, in IEEE Conference on Computer Vision and Pattern Recognition, IEEE, 2007, 1–6.
doi: 10.1109/CVPR.2007.383235. |
[12] |
L. N. Hutchins, S. M. Murphy, P. Singh and J. H. Graber,
Position-dependent motif characterization using non-negative matrix factorization, Bioinformatics, 24 (2008), 2684-2690.
doi: 10.1093/bioinformatics/btn526. |
[13] |
K. Lee, J. Ho and D. Kriegman,
Acquiring linear subspaces for face recognition under variable lighting, IEEE Transactions on Pattern Analysis and Machine Intelligence, 27 (2005), 684-698.
|
[14] |
G. Liu, Z. Lin and Y. Yu, Robust subspace segmentation by low-rank representation, in
Proceedings of the 27th international conference on machine learning, 2010, 663–670. |
[15] |
L. Lu and R. Vidal, Combined central and subspace clustering for computer vision applications, in Proceedings of the 23rd international conference on Machine learning, ACM,
2006, 593–600.
doi: 10.1145/1143844.1143919. |
[16] |
B. Nasihatkon and R. Hartley, Graph connectivity in sparse subspace clustering, in Computer
Vision and Pattern Recognition (CVPR), 2011 IEEE Conference on, IEEE, 2011, 2137–2144.
doi: 10.1109/CVPR.2011.5995679. |
[17] |
A. Y. Ng, M. I. Jordan and Y. Weiss,
On spectral clustering: Analysis and an algorithm, Advances in Neural Information Processing Systems, 2 (2002), 849-856.
|
[18] |
S. Oymak, A. Jalali, M. Fazel, Y. C. Eldar and B. Hassibi,
Simultaneously structured models with application to sparse and low-rank matrices, Information Theory, IEEE Transactions on, 61 (2015), 2886-2908.
doi: 10.1109/TIT.2015.2401574. |
[19] |
N. Parikh and S. Boyd,
Proximal algorithms, Foundations and Trends in optimization, 1 (2014), 127-239.
doi: 10.1561/2400000003. |
[20] |
M. J. D. Powell,
On search directions for minimization algorithms, Mathematical Programming, 4 (1973), 193-201.
doi: 10.1007/BF01584660. |
[21] |
S. R. Rao, R. Tron, R. Vidal and Y. Ma, Motion segmentation via robust subspace separation
in the presence of outlying, incomplete, or corrupted trajectories, in IEEE Conference on
Computer Vision and Pattern Recognition, IEEE, 2008, 1–8.
doi: 10.1109/CVPR.2008.4587437. |
[22] |
E. Richard, G. R. Obozinski and J. -P. Vert, Tight convex relaxations for sparse matrix factorization, in Advances in Neural Information Processing Systems, 2014, 3284–3292. |
[23] |
Y. Sugaya and K. Kanatani, Geometric structure of degeneracy for multi-body motion segmentation, in Statistical Methods in Video Processing, Springer, 2004, 13–25.
doi: 10.1007/978-3-540-30212-4_2. |
[24] |
M. E. Tipping and C. M. Bishop,
Mixtures of probabilistic principal component analyzers, Neural Computation, 11 (1999), 443-482.
doi: 10.1162/089976699300016728. |
[25] |
R. Vidal,
A tutorial on subspace clustering, IEEE Signal Processing Magazine, 28 (2010), 52-68.
|
[26] |
R. Vidal, Y. Ma and S. Sastry,
Generalized Principal Component Analysis (GPCA), Interdisciplinary Applied Mathematics, 40. Springer, New York, 2016.
doi: 10.1007/978-0-387-87811-9. |
[27] |
Y. -X. Wang, H. Xu and C. Leng, Provable subspace clustering: When LRR meets SSC, in
Advances in Neural Information Processing Systems, 2013, 64–72. |
[28] |
J. Yan and M. Pollefeys, A general framework for motion segmentation: Independent, articulated, rigid, non-rigid, degenerate and non-degenerate, in Computer Vision–ECCV 2006,
Springer, 2006, 94–106.
doi: 10.1007/11744085_8. |
[29] |
W. I. Zangwill,
Nonlinear Programming: A Unified Approach, vol. 196, Prentice-Hall Englewood Cliffs, NJ, 1969. |
[30] |
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. |


Data: Initialize 1 while not convergence do 2 │ Update 3 │ Update 4 │ Update 5 end |
Data: Initialize 1 while not convergence do 2 │ Update 3 │ Update 4 │ Update 5 end |
Data: Result: 1 Let 2 Find $\frac{\tilde{h}_{k-r-1}}{\alpha+1}>\frac{\gamma_{r, l}}{l-k+(\alpha+1)(r+1)}\ge\frac{\tilde{h}_{k-r}}{\alpha+1}, $ $\tilde{u}_l>\frac{\gamma_{r, l}}{l-k+(\alpha+1)(r+1)}\ge \tilde{g}_{l+1}.$ 3 Define $ q_i = \left\{ \begin{array}{ll} \frac{\alpha}{\alpha+1}\tilde{h}_i & \textrm{if}\; i=1, \cdots, k-r-1\\ \tilde{h}_i-\frac{\gamma_{r, l}}{l-k+(\alpha+1)(r+1)}\\ & \textrm{if}\; i=k-r, \cdots, l\\ 0 & \textrm{if} \; i=l+1, \cdots, n \end{array} \right.$ 4 Set |
Data: Result: 1 Let 2 Find $\frac{\tilde{h}_{k-r-1}}{\alpha+1}>\frac{\gamma_{r, l}}{l-k+(\alpha+1)(r+1)}\ge\frac{\tilde{h}_{k-r}}{\alpha+1}, $ $\tilde{u}_l>\frac{\gamma_{r, l}}{l-k+(\alpha+1)(r+1)}\ge \tilde{g}_{l+1}.$ 3 Define $ q_i = \left\{ \begin{array}{ll} \frac{\alpha}{\alpha+1}\tilde{h}_i & \textrm{if}\; i=1, \cdots, k-r-1\\ \tilde{h}_i-\frac{\gamma_{r, l}}{l-k+(\alpha+1)(r+1)}\\ & \textrm{if}\; i=k-r, \cdots, l\\ 0 & \textrm{if} \; i=l+1, \cdots, n \end{array} \right.$ 4 Set |
# Classes | mean/median | SSC | LRR | (3, 3)-SMF | (4, 4)-SMF | ||
error | s | error | s | ||||
2 | mean | 15.83 | 6.37 | 3.38 | 18 | 3.53 | 18 |
median | 15.63 | 6.25 | 2.34 | 2.34 | |||
3 | mean | 28.13 | 9.57 | 6.19 | 25 | 6.06 | 25 |
median | 28.65 | 8.85 | 5.73 | 5.73 | |||
5 | mean | 37.90 | 14.86 | 11.06 | 35 | 10.04 | 35 |
median | 38.44 | 14.38 | 9.38 | 9.06 | |||
8 | mean | 44.25 | 23.27 | 23.08 | 50 | 22.51 | 50 |
median | 44.82 | 21.29 | 27.54 | 26.06 | |||
10 | mean | 50.78 | 29.38 | 25.36 | 65 | 23.91 | 65 |
median | 49.06 | 32.97 | 27.19 | 27.34 |
# Classes | mean/median | SSC | LRR | (3, 3)-SMF | (4, 4)-SMF | ||
error | s | error | s | ||||
2 | mean | 15.83 | 6.37 | 3.38 | 18 | 3.53 | 18 |
median | 15.63 | 6.25 | 2.34 | 2.34 | |||
3 | mean | 28.13 | 9.57 | 6.19 | 25 | 6.06 | 25 |
median | 28.65 | 8.85 | 5.73 | 5.73 | |||
5 | mean | 37.90 | 14.86 | 11.06 | 35 | 10.04 | 35 |
median | 38.44 | 14.38 | 9.38 | 9.06 | |||
8 | mean | 44.25 | 23.27 | 23.08 | 50 | 22.51 | 50 |
median | 44.82 | 21.29 | 27.54 | 26.06 | |||
10 | mean | 50.78 | 29.38 | 25.36 | 65 | 23.91 | 65 |
median | 49.06 | 32.97 | 27.19 | 27.34 |
SSC | LRR | (3, 3)-SMF | (4, 4)-SMF | |
Mean | 9.28 | 8.43 | 6.61 | 7.16 |
Median | 0.24 | 1.54 | 1.20 | 1.32 |
SSC | LRR | (3, 3)-SMF | (4, 4)-SMF | |
Mean | 9.28 | 8.43 | 6.61 | 7.16 |
Median | 0.24 | 1.54 | 1.20 | 1.32 |
[1] |
Yangyang Xu, Ruru Hao, Wotao Yin, Zhixun Su. Parallel matrix factorization for low-rank tensor completion. Inverse Problems and Imaging, 2015, 9 (2) : 601-624. doi: 10.3934/ipi.2015.9.601 |
[2] |
Tao Wu, Yu Lei, Jiao Shi, Maoguo Gong. An evolutionary multiobjective method for low-rank and sparse matrix decomposition. Big Data & Information Analytics, 2017, 2 (1) : 23-37. doi: 10.3934/bdia.2017006 |
[3] |
Wei Wan, Weihong Guo, Jun Liu, Haiyang Huang. Non-local blind hyperspectral image super-resolution via 4d sparse tensor factorization and low-rank. Inverse Problems and Imaging, 2020, 14 (2) : 339-361. doi: 10.3934/ipi.2020015 |
[4] |
Dan Zhu, Rosemary A. Renaut, Hongwei Li, Tianyou Liu. Fast non-convex low-rank matrix decomposition for separation of potential field data using minimal memory. Inverse Problems and Imaging, 2021, 15 (1) : 159-183. doi: 10.3934/ipi.2020076 |
[5] |
Yun Cai, Song Li. Convergence and stability of iteratively reweighted least squares for low-rank matrix recovery. Inverse Problems and Imaging, 2017, 11 (4) : 643-661. doi: 10.3934/ipi.2017030 |
[6] |
Huiyuan Guo, Quan Yu, Xinzhen Zhang, Lulu Cheng. Low rank matrix minimization with a truncated difference of nuclear norm and Frobenius norm regularization. Journal of Industrial and Management Optimization, 2022 doi: 10.3934/jimo.2022045 |
[7] |
Zhouchen Lin. A review on low-rank models in data analysis. Big Data & Information Analytics, 2016, 1 (2&3) : 139-161. doi: 10.3934/bdia.2016001 |
[8] |
Hua Huang, Weiwei Wang, Chengwu Lu, Xiangchu Feng, Ruiqiang He. Side-information-induced reweighted sparse subspace clustering. Journal of Industrial and Management Optimization, 2021, 17 (3) : 1235-1252. doi: 10.3934/jimo.2020019 |
[9] |
Baolan Yuan, Wanjun Zhang, Yubo Yuan. A Max-Min clustering method for $k$-means algorithm of data clustering. Journal of Industrial and Management Optimization, 2012, 8 (3) : 565-575. doi: 10.3934/jimo.2012.8.565 |
[10] |
Simon Foucart, Richard G. Lynch. Recovering low-rank matrices from binary measurements. Inverse Problems and Imaging, 2019, 13 (4) : 703-720. doi: 10.3934/ipi.2019032 |
[11] |
Simon Arridge, Pascal Fernsel, Andreas Hauptmann. Joint reconstruction and low-rank decomposition for dynamic inverse problems. Inverse Problems and Imaging, 2022, 16 (3) : 483-523. doi: 10.3934/ipi.2021059 |
[12] |
Ke Wei, Jian-Feng Cai, Tony F. Chan, Shingyu Leung. Guarantees of riemannian optimization for low rank matrix completion. Inverse Problems and Imaging, 2020, 14 (2) : 233-265. doi: 10.3934/ipi.2020011 |
[13] |
Ruiqi Yang, Dachuan Xu, Yicheng Xu, Dongmei Zhang. An adaptive probabilistic algorithm for online k-center clustering. Journal of Industrial and Management Optimization, 2019, 15 (2) : 565-576. doi: 10.3934/jimo.2018057 |
[14] |
Xianchao Xiu, Lingchen Kong. Rank-one and sparse matrix decomposition for dynamic MRI. Numerical Algebra, Control and Optimization, 2015, 5 (2) : 127-134. doi: 10.3934/naco.2015.5.127 |
[15] |
Baoli Shi, Zhi-Feng Pang, Jing Xu. Image segmentation based on the hybrid total variation model and the K-means clustering strategy. Inverse Problems and Imaging, 2016, 10 (3) : 807-828. doi: 10.3934/ipi.2016022 |
[16] |
Changming Song, Yun Wang. Nonlocal latent low rank sparse representation for single image super resolution via self-similarity learning. Inverse Problems and Imaging, 2021, 15 (6) : 1347-1362. doi: 10.3934/ipi.2021017 |
[17] |
Changguang Dong. Separated nets arising from certain higher rank $\mathbb{R}^k$ actions on homogeneous spaces. Discrete and Continuous Dynamical Systems, 2017, 37 (8) : 4231-4238. doi: 10.3934/dcds.2017180 |
[18] |
Hsin-Yi Liu, Hsing Paul Luh. Kronecker product-forms of steady-state probabilities with $C_k$/$C_m$/$1$ by matrix polynomial approaches. Numerical Algebra, Control and Optimization, 2011, 1 (4) : 691-711. doi: 10.3934/naco.2011.1.691 |
[19] |
Guojun Gan, Kun Chen. A soft subspace clustering algorithm with log-transformed distances. Big Data & Information Analytics, 2016, 1 (1) : 93-109. doi: 10.3934/bdia.2016.1.93 |
[20] |
Narciso Román-Roy, Ángel M. Rey, Modesto Salgado, Silvia Vilariño. On the $k$-symplectic, $k$-cosymplectic and multisymplectic formalisms of classical field theories. Journal of Geometric Mechanics, 2011, 3 (1) : 113-137. doi: 10.3934/jgm.2011.3.113 |
2020 Impact Factor: 1.639
Tools
Metrics
Other articles
by authors
[Back to Top]