MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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. $$

share|cite|improve this question
I wonder if this is related to minimizing the infinity norm... – Dustin G. Mixon May 28 '13 at 0:17
up vote 3 down vote accepted

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.

share|cite|improve this answer

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

share|cite|improve this answer
Thank you. It is relevant. – Taha May 28 '13 at 20:57

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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