# Solution 8 Computational Intelligence Lab 2013

## Problem 1

• Question: Find the permutation ${\displaystyle \sigma ^{min}}$ such that the ${\displaystyle L^{2}}$ approximation is minimal

Copied solution from discussion:

${\displaystyle \sigma ^{min}=\arg \min _{\sigma }||\mathbf {f} -\mathbf {f} _{\sigma }||_{2}^{2}=\arg \min _{\sigma }<(\mathbf {f} -\mathbf {f} _{\sigma }),(\mathbf {f} -\mathbf {f} _{\sigma })>}$
${\displaystyle =\arg \min _{\sigma }<\mathbf {f} ,\mathbf {f} >-2<\mathbf {f} ,\mathbf {f} _{\sigma }>+<\mathbf {f} _{\sigma },\mathbf {f} _{\sigma }>}$
the first term is constant and we can neglect it in our minimization therefore we only have
${\displaystyle \arg \min _{\sigma }<\mathbf {f} _{\sigma },\mathbf {f} _{\sigma }>-2<\mathbf {f} ,\mathbf {f} _{\sigma }>}$
${\displaystyle =\arg \min _{\sigma }\sum _{k=1}^{K'}(z_{\sigma (k)}^{2})-2<\sum _{k=1}^{K}z_{k}u_{k},\sum _{k=1}^{K'}z_{\sigma (k)}u_{\sigma (k)}>}$
${\displaystyle =\arg \min _{\sigma }\sum _{k=1}^{K'}z_{\sigma (k)}^{2}-2\sum _{i=1}^{K}\sum _{j=1}^{K'}(z_{i}z_{\sigma (j)})}$
since ${\displaystyle }$ is only 1 if ${\displaystyle i=\sigma (j)}$ (and 0 otherwise) and this can only be the case at most for one pair of i and j, we only need one sum and since K' < K we have to sum over K'.
${\displaystyle =\arg \min _{\sigma }\sum _{k=1}^{K'}z_{\sigma (k)}^{2}-2\sum _{k=1}^{K'}z_{\sigma (k)}^{2}}$
${\displaystyle =\arg \min _{\sigma }-\sum _{k=1}^{K'}z_{\sigma (k)}^{2}}$
${\displaystyle =\arg \max _{\sigma }\sum _{k=1}^{K'}z_{\sigma (k)}^{2}}$
obviously this is maximized, if we keep the largest ${\displaystyle z_{\sigma (k)}}$ values.