# Deep Subspace Clustering with Block Diagonal Constraint
## 2 Deep Subspace Clustering Model with Block Diagonal Constraint
### Model Optimization  
According to Equation (2), the regularization term \(\|C\|_{\kappa}\) means that the sum of k smallest eigenvalues of \(L_{C}\) needs to be minimized, which is difficult to solve. However, according to the basic properties of the eigenvalues [20; 45], the regularization term can be rewritten as:  
\[\|C\|_{\kappa}=\sum_{i=N-k+1}^{N}\lambda_{i}(L_{C})=\min_{W}\langle L_{C},W \rangle\quad\text{s.t.}\quad W\in\mathcal{W}, \tag{7}\]  
where  
\[\mathcal{W}=\{W\in\mathbb{R}^{N\times N}:0\preceq W\preceq I,tr(W)=k\}. \tag{8}\]\(L_{C}=D_{C}-(C+C^{T})/2\), \(D_{C}\in\mathbb{R}^{N\times N}\) is a diagonal matrix whose diagonal elements are \(\sum_{j}(c_{ij}+c_{ji})/2\), \(W^{T}=\{w_{1},w_{2},\ldots,w_{N}\}\), and \(I\in\mathbb{R}^{N\times N}\) is the identity matrix. \(\langle L_{C},W\rangle\) denotes the inner product between the two matrices. Thus, Equation (4) can be rewritten as:  
\[ \begin{split}\min_{\Theta,Z,C,D,W}&\frac{1}{2}\|X- X^{{}^{\prime}}\|_{F}^{2}+\frac{1}{2}\|F-FZ\|_{F}^{2}+\frac{\alpha_{1}}{2}\|Z\|_{F}^{2} \\ &+\frac{\alpha_{2}}{2}\|Z-C\odot D\|_{F}^{2}+\frac{\alpha_{3}}{2} \|D\|_{F}^{2}\\ &+\alpha_{4}\langle L_{C},W\rangle\\ \text{s. t.}& C\in\mathcal{C},D\in\mathcal{D},W\in \mathcal{W}.\end{split}  \tag{9}\]  
Obviously, the model (9) is non-convex optimization problems, which is difficult to solve directly. Therefore, we intend to employ the alternating direction method (ADM) [46] to alternatively optimize variables \(\Theta\), \(Z\), \(D\), \(C\) and \(W\). **Update \(\Theta,Z\)**: While all other variables \(C\), \(D\) and \(W\) are fixed, we can update \(\Theta\), \(Z\) by solving sub-problem (10)  
\[ \begin{split}\min_{\Theta,Z}&\frac{1}{2}\|X-X^{{}^{ \prime}}\|_{F}^{2}+\frac{1}{2}\|F-FZ\|_{F}^{2}+\frac{\alpha_{1}}{2}\|Z\|_{F}^{ 2}\\ &+\frac{\alpha_{2}}{2}\|Z-C\odot D\|_{F}^{2}\\ \text{s. t.}& C\in\mathcal{C},D\in\mathcal{D}.\end{split}  \tag{10}\]  
It is worth noting that (10) is differentiable on \(\Theta\) and \(Z\), thus we use stochastic gradient descent to update \(\Theta\) and \(Z\). **Update \(D\)**: When other variables are fixed, the corresponding sub-problem for \(D\) is then given by  
\[ \begin{split}\min_{D}&\frac{\alpha_{2}}{2}\|Z-C\odot D \|_{F}^{2}+\frac{\alpha_{3}}{2}\|D\|_{F}^{2}\\ \text{s. t.}& D\in\mathcal{D}.\end{split}  \tag{11}\]  
The elements \(D_{ij}\) are independent of each other. Thus, we can update \(D_{ij}\) separately by the resulting sub-problem  
\[ \begin{split}\min_{D_{ij}}&(D_{ij}-\frac{\alpha_{2} C_{ij}Z_{ij}}{\alpha_{3}+\alpha_{2}C_{ij}^{2}})^{2}\\ \text{s. t.}& D_{ij}\geq D_{min}\end{split}  \tag{12}\]  
Solving the above formula, it can be obtained that:  
\[D_{ij}= \begin{cases}\frac{\alpha_{2}C_{ij}Z_{ij}}{\alpha_{3}+\alpha_{2}C_{ij }^{2}}&\text{if}\ \frac{\alpha_{2}C_{ij}Z_{ij}}{\alpha_{3}+\alpha_{2}C_{ij}^{2}}\geq D_{min};\\ D_{min}&\text{otherwise}.\end{cases}  \tag{13}\]  
We define \(P=A^{\odot-1}B\), where the matrices \(A\) and \(B\) are different but have the same size. We have \(P_{ij}=\frac{B_{ij}}{A_{ij}}\), which denotes the element-wise division. For convenience, the solution of (12) can be re-expressed as:  
\[\Pi_{\mathcal{D}}((\alpha_{2}C\odot C+\alpha_{3}))^{\odot-1}(\alpha_{2}C \odot Z)), \tag{14}\]  
where  
\[\Pi_{\mathcal{D}}(S)_{ij}= \begin{cases}S_{ij}&\text{if}\ \ S_{ij}\geq D_{min};\\ D_{min}&\text{otherwise}.\end{cases}  \tag{15}\]  
**Update** C: Fix all other variables \(Z,\Theta,D\) and \(W\) to update \(C\). The corresponding sub-problem for \(C\) is then given by  
\[\min_{C} \frac{\alpha_{2}}{2}\|Z-C\odot D\|_{F}^{2}+\alpha_{4}\langle L_{c},W\rangle\] (16) s. t. \[C\in\mathcal{C}\]  
The solution of (16) can be re-expressed as:  
\[\Pi_{\mathcal{C}}(\widetilde{C}), \tag{17}\]  
where  
\[\widetilde{C}_{ij}= \begin{cases}\frac{\alpha_{2}(D_{ij}Z_{ij}+D_{ ji}Z_{ji})-\alpha_{4}(\overline{W}_{ij}+\overline{W}_{ji})}{\alpha_{2}(D_{ij}^{ 2}+D_{ji}^{2})}&\text{if }\ i\
eq j;\\ \mathbf{0}&\text{otherwise},\end{cases}  \tag{18}\] \[\overline{W}=diag(W)1^{T}-W,\] \[\Pi_{\mathcal{C}}(S)_{ij}=