# Ordered Subspace Clustering for Complex Non-Rigid Motion by 3D Reconstruction
## 4 Solutions  
For the problem (4), the algorithm named alternating direction method of multipliers (ADMM) [24] is used to search for the optimized solution. Let \(U=ZS\), then problem in Equation (4) is turned to the problem with the augmented Lagrangian with two constraints. \[ \begin{split}\min_{X,Z,U,E}&\frac{1}{2}\|X-XZ\|_{F}^{2}+ \frac{\lambda}{2}\|Z^{T}Z\|_{1}+\lambda_{1}\|U\|_{2,1}+\frac{\gamma}{2}\|U-ZR \|_{F}^{2}\\ &+\lambda_{2}\|X\|_{*}+\frac{\lambda_{3}}{2}\|E\|_{1}+\frac{ \gamma_{1}}{2}\|W-RX^{\#}-E\|_{F}^{2}\\ &+\langle F,U-ZR\rangle+\langle G,W-RX^{\#}-E\rangle\\ &\text{s.t. }diag(Z)=0,Z\geq 0,\end{split}  \tag{6}\]  
where \(F\) and \(G\) are Lagrangian multipliers and \(\gamma\), \(\gamma_{1}\) are weight parameters for the term \(U=ZS\) and \(W=RX^{\#}+E\). Now we can solve Equation (6) by the following four sub-problems for \(X\), \(Z\), \(U\), and \(E\) when fixing other variables alternatively. 1. Fix \(Z\), \(U\) and \(E\), solve for \(X\) by  
\[\min_{X}f(X)\frac{1}{2}\|X-XZ\|_{F}^{2}+\lambda_{2}\|X\|_{*}+\langle G,W-RX^{ \#}-E\rangle+\frac{\gamma_{1}}{2}\|W-RX^{\#}-E\|_{F}^{2}. \tag{7}\]  
equivalently, we have  
\[\min_{X}f(X)=\lambda_{2}\|X\|_{*}+\frac{\gamma_{1}}{2}\|X-(X_{k}-\frac{\theta f (X_{k})}{\gamma})\|_{F}^{2}. \tag{8}\]  
where \(\theta f(X_{k})\) is the derivative of \(f(X)\) when \(X=X_{k}\), and \(Z=SVD(C)\), \(C=X_{k}-\frac{\theta f(X_{k})}{\gamma}\). 2. Fix \(X\), \(U\) and \(E\), solve for \(Z\) by  
\[ \begin{split}\min_{Z}f(Z)&=\frac{1}{2}\|X-XZ\|_{F}^{ 2}+\frac{\lambda}{2}\|Z^{T}Z\|_{1}+\langle F,U-ZS\rangle+\frac{\gamma}{2}\|U- ZS\|_{F}^{2},\\ &\text{s.t. }diag(Z)=0,Z\geq 0.\end{split}  \tag{9}\]  
To be noted, \(Z\) is element-wise nonnegative, so (9) can be turned into:  
\[f(Z)= \frac{1}{2}\|X-XZ\|_{F}^{2}+\frac{\lambda}{2}e^{T}Z^{T}Ze+\langle F,U-ZS\rangle+\frac{\gamma}{2}\|U-ZS\|_{F}^{2}, \tag{10}\]  
where \(e\in R^{n}\) is a vector of all \(1\). So the model (9) is a classical convex quadratic problem which has many practical solutions. Here a simple and efficient solution via projected gradient is adopted. Firstly, we compute the derivative of \(f(Z)\) for \(Z\),  
\[\partial f(Z)= -X^{T}(X-XZ)+\lambda_{1}Ze-FS^{T}-\gamma(U-ZS)S^{T}, \tag{11}\]  
where \(e\in R^{n\times n}\) is a matrix in which every element is \(1\). Then to obtain the optimized solution, for function \(f(Z)\), the derivative is set to be zero and we have  
\[XX^{T}Z+Z(\lambda_{1}e+\gamma SS^{T})=X^{T}X+FS^{T}+\gamma US^{T}. \tag{12}\]  
3. Fix \(X\), \(E\) and \(Z\), and solve for \(U\) by  
\[\min_{U}f_{1}(U)= \lambda_{2}\|U\|_{2,1}+\langle F,U-ZS\rangle+\frac{\gamma}{2}\| U-ZS\|_{F}^{2}. \tag{13}\]  
Equivalently, we have  
\[\min_{U}f_{1}(U)=\lambda_{1}\|U\|_{2,1}+\frac{\gamma}{2}\|U-(ZS-\frac{1}{ \gamma}F)\|_{F}^{2}. \tag{14}\]Denote \(Q=ZS-\frac{1}{\gamma}F\), problem (8) can be solved in [14],  
\[U_{i}= \begin{cases}\frac{\|Q_{i}\|-\frac{\lambda_{1}}{\gamma}}{\|Q_{i}\|}Q_{i}& \text{if }\|Q_{i}\|>\frac{\lambda_{1}}{\gamma}\\ 0&\text{otherwise,}\end{cases}  \tag{15}\]  
where \(U_{i}\) stands for the \(i\)-th column of \(U\), \(Q_{i}\) stands for the \(i\)-th column of \(Q\) respectively. Here is the closed-form solution. 4. Fix \(Z\), \(X\) and \(U\), solve for \(E\) by  
\[\min_{E}\frac{\lambda_{2}}{2}\|E\|_{1}+\langle G,W-RX^{\#}-E\rangle+\frac{ \gamma_{1}}{2}\|W-RX^{\#}-E\|_{F}^{2}, \tag{16}\]  
which is equivalent to  
\[\min_{E}f_{1}(E)=\lambda_{2}\|E\|_{1}+\frac{\gamma}{2}\|E-(W-RX^{\#}-\frac{G}{ \gamma})\|_{F}^{2} \tag{17}\]  
This problem can be easily solved by the current sparse subspace clustering method. Combining all the above updating formulas, we summarize the step for proposed OSC-NRSfM in Algorithm 1. The parameter setting refers to that in [14]. For Algorithm 1, usually we apply ADMM to find the optimized solution. By solving four sub-problems step by step, we can repeat the searching process to obtain the final solution. ```
0: The input data \(X\), maximal iteration number \(N\), parameters \(\lambda,\lambda_{1},\lambda_{2},\gamma,\gamma_{1}\), constant \(\rho\).