Question

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.

Answer 1

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). 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!