# Results for minimizing the norm w.r.t a unitary matrix

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.

-
What do you mean by "minimizing $g$"? Do you have a fixed $x$? –  Federico Poloni Aug 24 '12 at 14:09
Yes, that's what she means. –  TerronaBell Aug 24 '12 at 14:36
(To elaborate: she said, "how can we choose U to minimize g," which makes me think x is fixed.) –  TerronaBell Aug 24 '12 at 14:37
Yes, x is fixed. Sorry I should have mentioned that. I've written the problem in a bit of a bizarre way. –  mathtick Aug 24 '12 at 15:16
Isn't choosing $U$ a unitary matrix and minimizing some $f(Ux)$ equivalent to $f(y)$, with $||y||_2=||x||_2$? In particular, if $||cx||=c||x||$, then you are just minimizing $||Bx||/||x||_2$. –  Will Sawin Aug 24 '12 at 17:29

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). 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}$.)
I think you are maximizing but I the same reasoning applies: to minimize the infinity norm: rotate or reflect the x onto the "diagonal" i.e. something like the "1" vector. For //minimizing// the $k$th worst, I suppose it's trivial. You can always make $BUX=e_1$ which will always have $k$th worst (in absolute value) of zero. For the tail expectation, I mean the average of the $k$ largest components. –  mathtick Aug 24 '12 at 15:43