# Solution 8 Computational Intelligence Lab 2013

## Problem 1

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

Copied solution from discussion:

$\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 })>$
$=\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
$\arg \min _{\sigma }<\mathbf {f} _{\sigma },\mathbf {f} _{\sigma }>-2<\mathbf {f} ,\mathbf {f} _{\sigma }>$
$=\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)}>$
$=\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 $$ is only 1 if $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'.
$=\arg \min _{\sigma }\sum _{k=1}^{K'}z_{\sigma (k)}^{2}-2\sum _{k=1}^{K'}z_{\sigma (k)}^{2}$
$=\arg \min _{\sigma }-\sum _{k=1}^{K'}z_{\sigma (k)}^{2}$
$=\arg \max _{\sigma }\sum _{k=1}^{K'}z_{\sigma (k)}^{2}$
obviously this is maximized, if we keep the largest $z_{\sigma (k)}$ values.