kmeans

Let

$$x_1,x_2,\dots x_n\in {\mathbb{R}}^m$$

find $\hat{x}\in {\mathbb{R}}^m$

such that

$$\min \sum _{k=1}^n|{\theta }_k|$$

where

$$\cos {\theta }_k=\frac{x_k\cdot \hat{x}}{||x_k||\cdot ||\hat{x}||}$$

cos defines $\forall x_j,x_k\in {\mathbb{R}}^m$

$$\cos \theta =\frac{x_j}{||x_j||}\cdot \frac{x_k}{||x_k||}$$

Equivalent form

$$\min -\sum _{k=1}^n\frac{x_k\cdot \hat{x}}{||x_k||\cdot ||\hat{x}||}=\min -\frac{1}{c}\sum _{k=1}^n\frac{1}{||x_k||}\left(\sum _{l=1}^m{x}_{kl}\cdot {\hat{x}}_l\right)$$

under condition

$$\sum _{l=1}^m({\hat{x}}_l{)}^2=c^2$$

where $c\in \mathbb{R},c>0.$

$$\mathcal{L}({\hat{x}}_1,{\hat{x}}_2,\dots ,{\hat{x}}_m,\lambda )=-\frac{1}{c}\sum _{k=1}^n\frac{1}{||x_k||}\left(\sum _{l=1}^m{x}_{kl}\cdot {\hat{x}}_l\right)+\lambda \left(\sum _{l=1}^m({\hat{x}}_l{)}^2-c^2\right)$$

For $1\le l\le n$, let

$$\frac{\partial \mathcal{L}({\hat{x}}_1,{\hat{x}}_2,\dots ,{\hat{x}}_m,\lambda )}{\partial {\hat{x}}_l}=-\frac{1}{c}\sum _{k=1}^n\frac{x_{kl}}{||x_k||}+2\lambda {\hat{x}}_l=0$$

then

$${\hat{x}}_l=\frac{1}{2\lambda c}\sum _{k=1}^n\frac{x_{kl}}{||x_k||}$$

replace ${\hat{x}}_l$ with above expression

$$\sum _{l=1}^m{\left(\frac{1}{2\lambda c}\sum _{k=1}^n\frac{x_{kl}}{||x_k||}\right)}^2=c^2$$

then

$$2\lambda c=\frac{1}{c}{\left(\sum _{l=1}^m{\left(\sum _{k=1}^n\frac{x_{kl}}{||x_k||}\right)}^2\right)}^{1/2}$$

$${\hat{x}}_l=c\cdot \left(\sum _{k=1}^n\frac{x_{kl}}{||x_k||}\right){\left(\sum _{l=1}^m{\left(\sum _{k=1}^n\frac{x_{kl}}{||x_k||}\right)}^2\right)}^{-1/2}$$

For $||x_k||=1$ and $c=1$,

$${\hat{x}}_l=\left(\sum _{k=1}^n{x}_{kl}\right){\left(\sum _{l=1}^m{\left(\sum _{k=1}^n{x}_{kl}\right)}^2\right)}^{-1/2}={\bar{x}}_l{\left(\sum _{l=1}^m{{\bar{x}}_l}^2\right)}^{-1/2}=\frac{{\bar{x}}_l}{||\bar{x}||}$$

$$\hat{x}=\frac{\bar{x}}{||\bar{x}||}$$

$$||x_j-x_k|{|}^2=x_j^T{x}_j-2x_j^T{x}_k+x_k^T{x}_k$$

$$||x_j-x_k|{|}^2=2(1-x_j^T{x}_k)$$