Suppose $x \in \mathbb{R}^n$, $B,U \in \mathbb{R}^n\times\mathbb{R}^n$ and $U$ a unitary matrix. Define $g\_{U}(x) = || BUx||$ where $||.||$ is some norm or norm-ish function on $\mathbb{R}^n$ (not unitarily invariant obviously). How can we choose $U$ in the unitary matrices to minimize $g$? Or what kind of results are there regarding the minimum value?


I'm particularly interested in $||.||\_{\infty}$, the tail expectation, and maybe also the quantile function (i.e. $||x||$ is the $k$th largest element ... which will not be a norm.)


I'm mostly looking to "bind" this problem in the right way so that I can read the most appropriate material. I would imagine this kind of problem has been studied to death in various contexts. Or maybe I'm not seeing that the problem is in fact trivial or I've mis-specified it.



Results for minimizing the norm w.r.t a unitary matrix
In short: Householder transformations.


More specifically: for $||\cdot||\_\infty$, first think about the case where $B$ is the identity. Then you simply need to rotate $x$ such that it points along some axis -- this way all of the "mass" is concentrated in a single component. More explicitly, you can construct $U$ as a Householder transformation onto a multiple of the first basis vector $e\_1$, as is done in QR factorization (see description [here](http://en.wikipedia.org/wiki/QR_decomposition#Using_Householder_reflections)). If $B$ is not the identity, then you want $Ux$ to be some vector such that $BUx=e\_1$ or equivalently $Ux = B^{-1}e\_1=:y$ (assuming $B$ is invertible). Again the Householder trick applies, this time using $y$ instead of $e\_1$.


The $k$th largest element will be maximized when the first $k$ elements have equal magnitude and the remaining elements are zero. Once again, you can find the appropriate Householder rotation $U$ onto this vector. (Of course, if you don't actually care about $U$ itself and just want the value of the norm, you could compute this value directly as $||x||/\sqrt{k}$.)


Not sure what you mean by "tail expectation" in this context!


