# Deep Subspace Clustering with Block Diagonal Constraint
## 2 Deep Subspace Clustering Model with Block Diagonal Constraint
### Model Formulation  
Given the input samples set \(X=\{x_{1},x_{2},\cdots,x_{N}\}\), which consists of \(N\) samples. Each sample may be raw data or manually extracted features, such as images or extracted image features. As illustrated in Figure 1, our deep network model selects the convolutional auto-encoder as the basic framework and uses fully connected without bias and nonlinear activation as the self-expression layer. Let \(\Theta\) denote the auto-encoder module parameters, which can be decomposed into encoder parameters \(\theta_{e}\) and decoder parameters \(\theta_{d}\). \(Z\) denotes the self-expression module parameters, which is the representation matrix. \(F=\{f_{1},f_{2},\cdots,f_{N}\}\) is the latent representation corresponding to \(X=\{x_{1},x_{2},\cdots,x_{N}\}\), which is learned by the encoder. Therefore, latent feature \(f_{i}=\varphi(x_{i},\theta_{e})\), \(\varphi(\cdot)\) means to map the original data to latent feature. The output of decoder is \(X^{{}^{\prime}}=\left\{x_{1}^{\prime},x_{2}^{\prime},\ldots,x_{N}^{\prime}\right\}\), which is a function of \(\widetilde{\Theta}=\{\Theta,Z\}\). The naive deep subspace clustering can be formulated as a minimization problem as follows:  
\[\underset{\Theta}{\min}\quad\frac{1}{2}\|X-X^{{}^{\prime}}\|_{F}^{2}+\frac{1 }{2}\|F-FZ\|_{F}^{2}+\alpha_{1}\|Z\|_{p}, \tag{1}\]  
where \(\alpha_{1}\) is a positive trade-off parameter that balances the terms of the objective function. Here, DSC-Net uses \(\frac{1}{2}\|F-FZ\|_{F}^{2}\) to measure the self-expression errors, \(\frac{1}{2}\|X-X^{{}^{\prime}}\|_{F}^{2}\) to calculate the reconstruction cost and \(\|Z\|_{p}\) as a prior structure regularization of self-expressive representation \(Z\), which is used to avoid trivial solution. Subspace clustering methods based on self-expressive property firstly learn a representation matrix, and then spectral clustering is performed on the representation matrix to obtain the clustering result. Thus, the representation matrix plays an important role in spectral clustering. Whether it can truly reflect the similarity between data samples will directly affect the clustering performance. The ideal representation matrix in spectral clustering should have obvious block diagonal structure since all the inter-cluster affinities should be zero. To approximate such a structure, sparse or low-rank priors are adopted to the self-expressive representation matrix. there are two main types of constrained representation matrices: \(l_{1}\) norm to pursue sparsity [17] and nuclear norm to pursue low-rankness [15]. However, these two constraints are too rough and cannot guarantee a good diagonal structure. Unlike these indirect structure priors, [PERSON] et al. (2019) firstly proposed block diagonal regularization terms to directly constrain the representation matrix as a block diagonal structure. **Theorem 1** (([PERSON] et al., 2019)). : _For any \(Z\geq 0\), \(Z=Z^{T}\), the multiplicity \(k\) of the eigenvalue 0 of \(L_{Z}\) equals the number of connected components (blocks) in \(Z\), where \(L_{Z}=D-Z\), \(D\) is a diagonal matrix with diagonal element \(D_{ii}=\sum_{i=1}^{N}Z_{ij}\)._  
This theorem provides theoretical support for the the block diagonal constraint. We can know with Theorem 1 that \(Z\) is \(k\) block diagonal ( which means that \(Z\) has \(k\) connected components) if and only if  
\[\lambda_{i}(L_{Z})=\left\{ \begin{array}{ll}>0,&\quad i=1,\cdots,N-k;\\ =0,&\quad i=N-k+1,\cdots,N;\end{array} \right.\]  
where \(\lambda_{i}(L_{Z})(i=1,\cdots,N)\) are the eigenvalues of \(L_{Z}\) in decreasing order. Thus, we can employ the sum of the \(k\) smallest eigenvalues of \(L_{Z}\) as the \(k\) block diagonal regularizer, i.e.,  
\[\|Z\|_{\kappa}=\sum_{i=N-k+1}^{N}\lambda_{i}(L_{Z}). \tag{2}\]  
Obviously, the representation matrix \(Z\) is \(k\) block diagonal when \(\|Z\|_{\kappa}=0\).