# Markov-Embedded Affinity Learning with Connectivity Constraints for Subspace Clustering
## 4 Proposed Method
Thus, our model is developed as  
\[ \begin{split}\min_{Z}&\frac{1}{2}\|X-XZ\|_{F}^{2}+ \frac{\alpha}{2}\|P_{N}-Z\|_{F}^{2}+\gamma\|Z\|_{F}^{2}+\beta\textit{Tr}(ZL_{N }Z^{T}),\\ &\textit{s.t.}\;\textit{diag}(Z)=0,\end{split}  \tag{10}\]where \(\beta\geq 0\), \(L_{N}\) is the graph Laplacian matrix of the fine-grained neighbor matrix \(P_{N}\), \(L_{N}=Diag(P_{N}1^{*})-P_{N}\in R^{n\times n}\), \(1^{*}\) is a vector with all elements being \(1\), and \(Diag(\cdot)\) converts the input vector into a diagonal matrix. The affinity matrix \(Z\) in Equation (10) essentially reveals the correlation of the data, which is expected to have non-negativity and symmetry properties in our model. Thus, the matrix \(Z\) can be treated as a connected graph and is significant if it contains \(k\) connected components that correspond to the \(k\) clusters of the data. According to the Ky Fan theorem, ideally, the number of zero eigenvalues of the Laplacian matrix of \(Z\) is equal to the number of connected components in \(Z\). In order to better ensure this property, we further impose a connectivity constraint in our model. We define the graph Laplacian matrix of \(Z\) as \(L_{Z}=Diag(Z1^{*})-Z\); then, the connectivity constraint can be expressed as \(\min\sum_{i=1}^{k}\lambda_{i}(L_{Z})\)[15], where \(\lambda_{i}(\cdot)\) is the \(i\)-th smallest eigenvalue of the input matrix. Since the connectivity constraint is more efficient in preserving the data structure information and helps as a penalty, we replace the Frobenius norm with the connectivity constraint and further develop our model as  
\[ \begin{split}\min_{Z}&\frac{1}{2}\|X-XZ\|_{F}^{2}+ \frac{\alpha}{2}\|P_{N}-Z\|_{F}^{2}+\gamma\sum_{i=1}^{k}\lambda_{i}(L_{Z})+ \beta\text{Tr}(ZL_{N}Z^{T}),\\ s.t.\,\,diag(Z)=0,Z\geq 0,Z=Z^{T},\end{split}  \tag{11}\]  
where \(\gamma\geq 0\). In Equation (11), \(\sum_{i=1}^{k}\lambda_{i}(L_{Z})\), as a connectivity constraint, can effectively partition the connected components on the graph and connect the samples within the clusters. This characteristic of the connectivity constraint can improve the algorithm's ability to handle the group structure of the data, thereby enhancing the clustering performance. It is noted that there are excessive restrictions on the affinity matrix \(Z\) in the model. These restrictions may limit the expression of \(Z\). Thus, we introduce an intermediate variable \(B\) to alleviate this problem in a way similar to [15]:  
\[ \begin{split}\min_{Z,B}&\frac{1}{2}\|X-XZ\|_{F}^{2}+ \frac{\alpha}{2}\|P_{N}-Z\|_{F}^{2}+\gamma\sum_{i=1}^{k}\lambda_{i}(L_{B})+ \beta\text{Tr}(ZL_{N}Z^{T})+\frac{\zeta}{2}\|Z-B\|_{F}^{2},\\ s.t.\,\,diag(B)=0,B\geq 0,B=B^{T},\end{split}  \tag{12}\]  
where \(L_{B}=Diag(B1^{*})-B\), and, when \(\zeta\geq 0\), by minimizing Equation (12), we can make \(B=Z\). Moreover, introducing \(\|Z-B\|_{F}^{2}\) ensures that the subproblems related to \(Z\) and \(B\) are strongly convex, which is more convenient for optimization. Equation (12) is named Markov-Embedded Affinity Learning with Connectivity Constraints for Subspace Clustering (MKSC). MKSC has four balancing parameters: \(\{\zeta,\alpha,\beta,\gamma\}\). In Equation (12), \(\zeta\) controls the speed at which matrix \(Z\) and \(B\) become similar. The larger the value of \(\zeta\), the faster \(Z\) and \(B\) become similar, and vice versa. Similar to \(\zeta\), a controls the speed of approximation between \(P_{N}\) and \(Z\). The larger the value of \(\alpha\), the faster \(P_{N}\) and \(Z\) approximate each other, and vice versa. For \(\gamma\), the larger \(\gamma\) is, the stronger the connectivity constraint on the affinity matrix \(Z\). \(\beta\) controls the manifold, which can affect the model's ability to handle nonlinear data.