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.

  • $\begingroup$ What do you mean by "minimizing $g$"? Do you have a fixed $x$? $\endgroup$ – Federico Poloni Aug 24 '12 at 14:09
  • $\begingroup$ Yes, that's what she means. $\endgroup$ – TerronaBell Aug 24 '12 at 14:36
  • $\begingroup$ (To elaborate: she said, "how can we choose U to minimize g," which makes me think x is fixed.) $\endgroup$ – TerronaBell Aug 24 '12 at 14:37
  • $\begingroup$ Yes, x is fixed. Sorry I should have mentioned that. I've written the problem in a bit of a bizarre way. $\endgroup$ – mathtick Aug 24 '12 at 15:16
  • $\begingroup$ 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$. $\endgroup$ – Will Sawin Aug 24 '12 at 17:29

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!

  • $\begingroup$ 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. $\endgroup$ – mathtick Aug 24 '12 at 15:43
  • $\begingroup$ Ah, yes, I'm maximizing! Sorry. But as you point out, Householder is still your friend. :-) $\endgroup$ – TerronaBell Aug 24 '12 at 15:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.