Maximal norm-1 projection

Suppose I have a real unitary matrix $U$ and a unit vector $\mathbf{x}, \|\mathbf{x}\|_2 = 1$. What is the solution to the following problem?

$$\widehat{\mathbf{x}} = \arg\max_{\mathbf{x}, ~\|\mathbf{x}\|_2 = 1}\|U\mathbf{x}\|_1.$$

-
I wonder if this is related to minimizing the infinity norm... – Dustin G. Mixon May 28 '13 at 0:17

One solution is to take $x$ to be proportional to the column sums of $U$. Indeed, we have that $$\widehat{x} = \arg \max_{||y||_{\infty} = 1, ||x||_2 = 1} y^T U x$$ which suggests we should pick $x$ proportional to $U^T \widehat{y}$ where $$\widehat{y} = \arg \max ||U^T y||_2$$ where the maximum is taken over $y$ with $\infty$-norm equal to $1$. But this is maximizing a convex function over a convex set, so the maximum occurs at the corners of the cube $[-1,1]^n$. Moreover, because $U$ is unitary, its easy to see it actually doesn't matter which corner we pick. So we might as well pick $y = (1,1,..,1)^T$, leading to the claim in the first sentence of this answer. Picking other corners gives other solutions.

-

The following may be of interest: K. Drakakis, "On the calculation of the l2 -> l1 induced matrix norm", Int. J. Algebra, 2009 (3), No 5, 231-240 (pdf).

-
Thank you. It is relevant. – Taha May 28 '13 at 20:57