Return to Revisions

One solution is to take $x$ to be norm-one and 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 \widehat{y}$ where $$\widehat{y} = \arg \max ||U^T y||_2 $$ where the maximum is taken over $||y||_2=1$. But this is maximizing a convex function over a convex set, so the maximum occurs at the corners $\{-1,1\}^n$. Moreover, because $U$ is unitatory its easy to see its actually independent of the choices which corner we pick. So we might as well pick $y = (1,1,..,1)^T$, leading to the solution in the first sentence. Picking other corners gives other solutions.