Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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|improve this question
    
I wonder if this is related to minimizing the infinity norm... –  Dustin G. Mixon May 28 '13 at 0:17

2 Answers 2

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|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|improve this answer
    
Thank you. It is relevant. –  Taha May 28 '13 at 20:57

Your Answer

 
discard

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.