## 3 A Trimmed-Clustering Based \(I_{1}\)-PCA Model
### Relating \(l_{1}\)-PCA to Two-Groups K-Means Clustering
That is,  
\[\underset{s_{i}\in[-1,1]}{max}\|\sum_{i=1}^{n}s_{i}(x_{i}-c)\|\underset{2}{ \propto}\underset{s_{i}\in[-1,1]}{max}\|\sum_{i=1}^{n}s_{i}(x_{i}-c)\|\sum_{2 }^{2}. \tag{4}\]  
We will see that the variable \(s_{i}\) in the \(l_{1}\)-PCA model is the difference of the two indicator variables of the \(k\)-means clustering algorithm. That is, \(s_{i}=l_{i,1}-l_{i,2}\). The above squared \(l_{2}\) norm function leads to the following binary quadratic programming problem:  
\[\underset{s\in[-1,1]^{n}}{max}s^{T}X_{c}{}^{T}X_{c}s \tag{5}\]  
where \(X_{c}=[x_{1}-c,x_{2}-c,\dots,x_{n}-c]\) and \(s=[s_{1},s_{2},\dots,s_{n}]\in\mathbb{R}^{n}\). Let \(s_{i}=l_{i,1}-l_{i,2}\in\{-1,1\}\), \(\hat{u}=\lambda\cdot u\) with \(\|u\|_{2}=1\) and \(\lambda\) is a constant. The theoretical justification is complete if Equation (2) can be expressed as the above binary quadratic programming problem. It is noted that Equation (2) can be rewritten as  
\[ \begin{array}{l}J(\hat{u},c,l)=\sum\limits_{i=1}^{n}\left(l_{i,1}\|(x_{i}-c )-\hat{u}\|_{2}^{2}+l_{i,2}\|(x_{i}-c)+\hat{u}\|_{2}^{2}\right)\\ =\sum\limits_{i=1}^{n}\left(l_{i,1}(\|x_{i}-c\|_{2}^{2}-2(x_{i}-c)^{T}\hat{u}+ \lambda^{2})+l_{i,2}(\|x_{i}-c\|_{2}^{2}+2(x_{i}-c)^{T}\hat{u}+\lambda^{2}) \right)\\ =\sum\limits_{i=1}^{n}\|\|x_{i}-c\|_{2}^{2}-2\lambda\sum\limits_{i=1}^{n}s_{ i}((x_{i}-c)^{T}u)+n\lambda^{2}\end{array}  \tag{6}\]  
The second and third equality hold because \(\|\hat{u}\|_{2}^{2}=\lambda^{2}\) and \(\hat{u}=\lambda\cdot u\). Thus,  
\[J(\hat{u},c,l)=\sum\limits_{i=1}^{n}\|\|x_{i}-c\|_{2}^{2}-2\lambda\sum\limits_ {i=1}^{n}s_{i}((x_{i}-c)^{T}u)+n\lambda^{2} \tag{7}\]  
To minimize (7) with respect to \(\lambda\), we need the following claim. Figure 3: (**a**) First projection vector obtained by \(l_{1}\)-PCA. (**b**) Cluster centers obtained by two-group \(k\)-means clustering model. **Claim**: The global minimum value of the FUNCTION \(f(x)=-2\gamma x+nx^{2}\) is \(f(\gamma)=-\frac{\gamma^{2}}{n}\). Here, \(\gamma\) and \(n\) are constants. \(n\) is a positive number. **Proof**: \(f^{\prime}(x)=2 nx-2\gamma.f^{\prime}(x)=0\Rightarrow x=\gamma/n\),  
\[f^{\prime\prime}(x)=2n>0\Rightarrow x=\gamma/n\text{ is the global minimum}.\]  
By taking \(\gamma=2\sum_{i=1}^{n}s_{i}((x_{i}-c)^{T}u)\) and \(x=\lambda\) in the above claim, Equation (7) is written as  
\[ \begin{array}{l}\underset{\hat{u},l}{\min}\ J(\hat{u},c,l)=\underset{s_{i} \in[-1,1]}{\min}\underset{u}{\min}\underset{\hat{u}}{\min}\underset{i=1}{ \sum}\|x_{i}-c\|_{2}^{2}-\frac{1}{n}\underset{i=1}{\sum}s_{i}((x_{i}-c)^{T}u )\bigg{)}^{2}\\ =\underset{\hat{u}\in[-1,1]}{\min}\underset{u}{\min}-\frac{1}{n}\underset{i =1}{\sum}s_{i}((x_{i}-c)^{T}u)\bigg{)}^{2}\\ =\underset{\hat{u}\in[-1,1]}{\min}-\frac{1}{n}\underset{i=1}{\sum}\underset{ i=1}{\sum}s_{i}(x_{i}-c)\underset{2}{\sum}\\ =\underset{\hat{u}\in[-1,1]^{n}}{\min}-\frac{1}{n}\underset{i=1}{\sum}s^{T}X _{c}{}^{T}X_{c}s\\ \propto\underset{\hat{u}\in[-1,1]^{n}}{max}s^{T}X_{c}{}^{T}X_{c}s,\end{array} \]  
which is equal to (5). The third equality holds because \(\underset{\|\|u\|_{2}=1}{min}-x^{T}u=-\|x\|_{2}\). In other words, the \(l_{1}\)-PCA is essentially equivalent to the two-group \(k\)-means clustering model. This equivalence has three major implications. First, the projection vector \(u\) estimated by the \(l_{1}\)-PCA is the normalized vector difference between the two cluster centers, \(\hat{u}+c\) and \(\hat{u}-c\), obtained by the clustering algorithm. That is, \(u=\hat{u}/\|\hat{u}\|_{2}\). Second, the binary vector \(s_{i}\) introduced in Equation (3) is the difference of the two indicator variables of the two-group \(k\)-means clustering model. Third, the projection vector \(u\) can be obtained without data centralization procedure.