## 3 SSC and LRR Clustering with LLE Regularization
### Solutions to LLE-SSC and LLE-LRR  
For the problems in (12) and (13), we use the Alternating Direction Method of Multipliers (ADMM) [27] to find the solutions. To deal with the sparse item and the nuclear norm item of \(\mathbf{Z}\) in (12) and (13), we separate the term of \(\mathbf{Z}\) by introducing an auxiliary \(\mathbf{S}\). Let \(\mathbf{S}=\mathbf{Z}\), then the problemsin (12) and (13) can be re-written as the following problems with the Augmented Lagrangian items for the introduced constraints,  
\[\min_{\mathbf{Z},\mathbf{S}}\|\mathbf{S}\|_{1}+\frac{\lambda_{1}}{2}\|\mathbf{X} -\mathbf{XZ}\|_{F}^{2}+\lambda_{2}tr(\mathbf{Z}\mathbf{L_{M}}\mathbf{Z}^{T})+ \langle\mathbf{G},\mathbf{Z}-\mathbf{S}\rangle+\frac{\gamma}{2}\|\mathbf{Z}- \mathbf{S}\|_{F}^{2}, \tag{14}\]  
\[\min_{\mathbf{Z},\mathbf{S}}\|\mathbf{S}\|_{*}+\frac{\lambda_{1}}{2}\|\mathbf{X }-\mathbf{XZ}\|_{F}^{2}+\lambda_{2}tr(\mathbf{Z}\mathbf{L_{M}}\mathbf{Z}^{T}) +\langle\mathbf{G},\mathbf{Z}-\mathbf{S}\rangle+\frac{\gamma}{2}\|\mathbf{Z}- \mathbf{S}\|_{F}^{2}, \tag{15}\]  
where \(\mathbf{G}\) is the Lagrangian multiplier and \(\gamma\) is the increasing weight parameter enforcing \(\mathbf{S}=\mathbf{Z}\). The problems in (14) and (15) can be solved by the following sub-problems with respect to \(\mathbf{Z}\), \(\mathbf{S}\) in an alternative manner by updating one when fixing the other. **(1) Fixing S, solve for \(\mathbf{Z}\)**  
When \(\mathbf{S}\) is fixed, the objective functions in the problems in (14) and (15) will be transformed to the same objective function as follows:  
\[f(\mathbf{Z})= \frac{\lambda_{1}}{2}\|\mathbf{X}-\mathbf{XZ}\|_{F}^{2}+\lambda _{2}tr(\mathbf{Z}\mathbf{L_{M}}\mathbf{Z}^{T})+\langle\mathbf{G},\mathbf{Z}- \mathbf{S}\rangle+\frac{\gamma}{2}\|\mathbf{Z}-\mathbf{S}\|_{F}^{2}. \tag{16}\]  
As \(f(\mathbf{Z})\) is a quadratic function with respect to \(\mathbf{Z}\), we set the derivative of \(f(\mathbf{Z})\) to zero and have  
\[(\lambda_{1}\mathbf{X}\mathbf{X}^{T}+\gamma\mathbf{I})\mathbf{Z}+\lambda_{2} \mathbf{Z}\mathbf{L_{M}}=\lambda_{1}\mathbf{X}^{T}\mathbf{X}+\gamma\mathbf{S} -\mathbf{G}. \tag{17}\]  
Then vectorizing the matrix \(\mathbf{Z}\), we can transform the above equation into the following linear equation and thus obtain the solution of \(\mathbf{Z}\). \[\left(\mathbf{I}\otimes(\lambda_{1}\mathbf{X}\mathbf{X}^{T}+\gamma\mathbf{I} )+\lambda\mathbf{L_{M}}\otimes\mathbf{I}\right)vec(\mathbf{Z})=vec(\lambda_{ 1}\mathbf{X}^{T}\mathbf{X}+\gamma\mathbf{S}-\mathbf{G}). \tag{18}\]  
**(2) Fixing Z, solve for \(\mathbf{S}\)**  
When \(\mathbf{Z}\) is fixed, the LLE-SSC and LLE-LRR optimization problems in (14) and (15) degenerate as the following problems:  
\[\min_{\mathbf{S}}\|\mathbf{S}\|_{1}+\langle\mathbf{G},\mathbf{Z}-\mathbf{S} \rangle+\frac{\gamma}{2}\|\mathbf{Z}-\mathbf{S}\|_{F}^{2}, \tag{19}\]  
\[\min_{\mathbf{S}}\|\mathbf{S}\|_{*}+\langle\mathbf{G},\mathbf{Z}-\mathbf{S} \rangle+\frac{\gamma}{2}\|\mathbf{Z}-\mathbf{S}\|_{F}^{2}. \tag{20}\]  
Let \(\mathbf{P}=\mathbf{Z}+\frac{\mathbf{G}}{\gamma}\), the above problems have the following equivalent forms:  
\[\min_{\mathbf{S}}\|\mathbf{S}\|_{1}+\frac{\gamma}{2}\|\mathbf{Z}-\mathbf{P}\| _{F}^{2}, \tag{21}\]  
\[\min_{\mathbf{S}}\|\mathbf{S}\|_{*}+\frac{\gamma}{2}\|\mathbf{Z}-\mathbf{P}\| _{F}^{2}. \tag{22}\]  
For the problem in (21), it has a closed-form solution [28] given by  
\[\mathbf{S}=sign(\mathbf{P})max\{|\mathbf{P}|-\frac{1}{\gamma},0\}. \tag{23}\]  
For the problem in (22), it also has a closed-form solution [29] given by  
\[\min_{\mathbf{Z},\mathbf{S}}\|\mathbf{S}\|_{*}+\frac{\lambda_{1}}{2}\|\mathbf{X }-\mathbf{XZ}\|_{F}^{2}+\lambda_{2}tr(\mathbf{Z}\mathbf{L_{M}}\mathbf{Z}^{T}) +\langle\mathbf{G},\mathbf{Z}-\mathbf{S}\rangle+\frac{\gamma}{2}\|\mathbf{Z}- \mathbf{S}\|_{F}^{2}, \tag{15}\]0  
where \(\mathbf{U}\mathbf{\Sigma}\mathbf{V}^{T}\) is the singular value decomposition (SVD) of \(\mathbf{P}\).