# Solution 7 Computational Intelligence Lab 2015

## Problem 1

• Question: Find the permutation ${\displaystyle \sigma ^{min}}$ which minimizes the ${\displaystyle L^{2}}$ approximation ${\displaystyle ||\mathbf {x} -\mathbf {{\hat {x}}_{\sigma }} ||}$

### Solution

${\displaystyle ||\mathbf {x} -\mathbf {{\hat {x}}_{\sigma }} ||=\left\langle \mathbf {x} -\mathbf {{\hat {x}}_{\sigma }} ,\mathbf {x} -\mathbf {{\hat {x}}_{\sigma }} \right\rangle }$

${\displaystyle =\left\langle \sum _{k=1}^{K}z_{k}u_{k}-\sum _{k=1}^{\tilde {K}}z_{\sigma (k)}u_{\sigma (k)},\sum _{k=1}^{K}z_{k}u_{k}-\sum _{k=1}^{\tilde {K}}z_{\sigma (k)}u_{\sigma (k)}\right\rangle }$
${\displaystyle =\left\langle \sum _{k={\tilde {K}}+1}^{K}z_{\sigma (k)}u_{\sigma (k)},\sum _{k={\tilde {K}}+1}^{K}z_{\sigma (k)}u_{\sigma (k)}\right\rangle }$
${\displaystyle =\left(\sum _{k={\tilde {K}}+1}^{K}z_{\sigma (k)}u_{\sigma (k)}\right)^{T}\left(\sum _{k={\tilde {K}}+1}^{K}z_{\sigma (k)}u_{\sigma (k)}\right)}$
${\displaystyle =\sum _{k={\tilde {K}}+1}^{K}\sum _{j={\tilde {K}}+1}^{K}z_{\sigma (k)}z_{\sigma (j)}u_{\sigma (k)}^{T}u_{\sigma (j)}}$
${\displaystyle =\sum _{k={\tilde {K}}+1}^{K}z_{\sigma (k)}^{2}\qquad ({\text{since }}u_{\sigma (k)}^{T}u_{\sigma (j)}=0ifk\neq j,\quad u_{\sigma (k)}^{T}u_{\sigma (k)}=1)}$

Since ${\displaystyle \sigma ^{min}=\arg \min _{\sigma }||\mathbf {x} -\mathbf {{\hat {x}}_{\sigma }} ||=\arg \min _{\sigma }\sum _{k={\tilde {K}}+1}^{K}z_{\sigma (k)}^{2}}$, ${\displaystyle \sigma ^{min}}$ is a permutation such that ${\displaystyle \forall k>{\tilde {K}},j\leq {\tilde {K}}.z_{\sigma ^{min}(k)}\leq z_{\sigma ^{min}(j)}}$ (i.e. we keep the columns corresponding to the largest values of ${\displaystyle \mathbf {z} }$).