5
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ I wonder if this is related to minimizing the infinity norm... $\endgroup$ Commented May 28, 2013 at 0:17
  • $\begingroup$ I have heard that this problem is a popular optimization interview question. $\endgroup$
    – Taha
    Commented Feb 21, 2018 at 1:05

2 Answers 2

3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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