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. $$
2
-
$\begingroup$ I wonder if this is related to minimizing the infinity norm... $\endgroup$– Dustin G. MixonCommented May 28, 2013 at 0:17
-
$\begingroup$ I have heard that this problem is a popular optimization interview question. $\endgroup$– TahaCommented Feb 21, 2018 at 1:05
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
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.
$\begingroup$
$\endgroup$
0
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).
answered May 28, 2013 at 20:07