# American Institute of Mathematical Sciences

June  2017, 11(3): 539-551. doi: 10.3934/ipi.2017025

## 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

* Corresponding author

Received  April 2016 Revised  February 2017 Published  April 2017

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.

Citation: Haixia Liu, Jian-Feng Cai, Yang Wang. Subspace clustering by (k,k)-sparse matrix factorization. Inverse Problems & Imaging, 2017, 11 (3) : 539-551. doi: 10.3934/ipi.2017025
##### References:

show all references

##### References:
The plot of RSS vs. the reduced dimension $s$
The ExtendedYale data B
ADMM Algorithm to solve Model (11)
 Data: Initialize $E=0$, $U=0$, $V=0$, $\lambda_1=0$, $\lambda_2=0$. 1 while not convergence do 2 │ Update $Z$ with Equation (14); 3 │ Update $E$ with Equation (15) and $U$, $V$ with Equation (16), respectively; 4 │ Update $\lambda_1$ with Equation (17) and $\lambda_2$ with Equation (18); 5 end
 Data: Initialize $E=0$, $U=0$, $V=0$, $\lambda_1=0$, $\lambda_2=0$. 1 while not convergence do 2 │ Update $Z$ with Equation (14); 3 │ Update $E$ with Equation (15) and $U$, $V$ with Equation (16), respectively; 4 │ Update $\lambda_1$ with Equation (17) and $\lambda_2$ with Equation (18); 5 end
The algorithm for proximity operator of $\frac{1}{2\alpha}(\|\cdot\|_{sp}^{k})^2$ with input $\mathbf{h}$
 Data: $\mathbf{h}\in\mathbb{R}^n$ and the parameter $\alpha$.     Result: $\mathbf{p}=\underset{\mathbf{g}}{\arg\min}\left\{\frac{1}{2\alpha}(\|\mathbf{g}\|^{sp}_{k})^2+\frac{1}{2}\|\mathbf{g}-\mathbf{h}\|^2_2\right\}$ 1 Let $\tilde{\mathbf{h}}=[\tilde{h}_1,\cdots,\tilde{h}_n]^T$, i.e., $\tilde{h}_i$ is the $i$-th largest element of $|\mathbf{h}|$. Let $\Pi$ be the permutation matrix such that $\tilde{\mathbf{h}}=\Pi|\mathbf{h}|$. For simplicity, define $\tilde{h}_0:=+\infty$, $\tilde{h}_{n+1}:=-\infty$ and $\gamma_{r,l}:=\sum^l_{i=k-r}\tilde{h}_i$ 2 Find $r\in\{0,\cdots,k-1\}$ and $l\in\{k,\cdots,n\}$ such that             $\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 $\mathbf{p}=[p_1,\ldots,p_n]^T$, where $p_i=\mathrm{sign}(h_i)(\Pi^{-1}\mathbf{q})_i$.
 Data: $\mathbf{h}\in\mathbb{R}^n$ and the parameter $\alpha$.     Result: $\mathbf{p}=\underset{\mathbf{g}}{\arg\min}\left\{\frac{1}{2\alpha}(\|\mathbf{g}\|^{sp}_{k})^2+\frac{1}{2}\|\mathbf{g}-\mathbf{h}\|^2_2\right\}$ 1 Let $\tilde{\mathbf{h}}=[\tilde{h}_1,\cdots,\tilde{h}_n]^T$, i.e., $\tilde{h}_i$ is the $i$-th largest element of $|\mathbf{h}|$. Let $\Pi$ be the permutation matrix such that $\tilde{\mathbf{h}}=\Pi|\mathbf{h}|$. For simplicity, define $\tilde{h}_0:=+\infty$, $\tilde{h}_{n+1}:=-\infty$ and $\gamma_{r,l}:=\sum^l_{i=k-r}\tilde{h}_i$ 2 Find $r\in\{0,\cdots,k-1\}$ and $l\in\{k,\cdots,n\}$ such that             $\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 $\mathbf{p}=[p_1,\ldots,p_n]^T$, where $p_i=\mathrm{sign}(h_i)(\Pi^{-1}\mathbf{q})_i$.
The error rate (mean % and median %) for face clustering on Extended Yale dataset B
 # 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
The error rate (mean %/median %) for motion segmentation on Hopkins155 dataset
 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 & 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 & Imaging, 2020, 14 (2) : 339-361. doi: 10.3934/ipi.2020015 [4] Yun Cai, Song Li. Convergence and stability of iteratively reweighted least squares for low-rank matrix recovery. Inverse Problems & Imaging, 2017, 11 (4) : 643-661. doi: 10.3934/ipi.2017030 [5] 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 [6] Hua Huang, Weiwei Wang, Chengwu Lu, Xiangchu Feng, Ruiqiang He. Side-information-induced reweighted sparse subspace clustering. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020019 [7] Baolan Yuan, Wanjun Zhang, Yubo Yuan. A Max-Min clustering method for $k$-means algorithm of data clustering. Journal of Industrial & Management Optimization, 2012, 8 (3) : 565-575. doi: 10.3934/jimo.2012.8.565 [8] Simon Foucart, Richard G. Lynch. Recovering low-rank matrices from binary measurements. Inverse Problems & Imaging, 2019, 13 (4) : 703-720. doi: 10.3934/ipi.2019032 [9] Ke Wei, Jian-Feng Cai, Tony F. Chan, Shingyu Leung. Guarantees of riemannian optimization for low rank matrix completion. Inverse Problems & Imaging, 2020, 14 (2) : 233-265. doi: 10.3934/ipi.2020011 [10] Ruiqi Yang, Dachuan Xu, Yicheng Xu, Dongmei Zhang. An adaptive probabilistic algorithm for online k-center clustering. Journal of Industrial & Management Optimization, 2019, 15 (2) : 565-576. doi: 10.3934/jimo.2018057 [11] Xianchao Xiu, Lingchen Kong. Rank-one and sparse matrix decomposition for dynamic MRI. Numerical Algebra, Control & Optimization, 2015, 5 (2) : 127-134. doi: 10.3934/naco.2015.5.127 [12] Baoli Shi, Zhi-Feng Pang, Jing Xu. Image segmentation based on the hybrid total variation model and the K-means clustering strategy. Inverse Problems & Imaging, 2016, 10 (3) : 807-828. doi: 10.3934/ipi.2016022 [13] Changguang Dong. Separated nets arising from certain higher rank $\mathbb{R}^k$ actions on homogeneous spaces. Discrete & Continuous Dynamical Systems - A, 2017, 37 (8) : 4231-4238. doi: 10.3934/dcds.2017180 [14] 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 & Optimization, 2011, 1 (4) : 691-711. doi: 10.3934/naco.2011.1.691 [15] 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 [16] 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 [17] Michel Crouzeix. The annulus as a K-spectral set. Communications on Pure & Applied Analysis, 2012, 11 (6) : 2291-2303. doi: 10.3934/cpaa.2012.11.2291 [18] Sangye Lungten, Wil H. A. Schilders, Joseph M. L. Maubach. Sparse inverse incidence matrices for Schilders' factorization applied to resistor network modeling. Numerical Algebra, Control & Optimization, 2014, 4 (3) : 227-239. doi: 10.3934/naco.2014.4.227 [19] Yitong Guo, Bingo Wing-Kuen Ling. Principal component analysis with drop rank covariance matrix. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020072 [20] Zhengshan Dong, Jianli Chen, Wenxing Zhu. Homotopy method for matrix rank minimization based on the matrix hard thresholding method. Numerical Algebra, Control & Optimization, 2019, 9 (2) : 211-224. doi: 10.3934/naco.2019015

2019 Impact Factor: 1.373