1
$\begingroup$

If $A$ is a $p \times p$ matrix, what is

$\max_{||u||_2=1} ||Au||_1 ?$

I am specifically interested in the case when $A$ is positive definite.

  • 0
    I don't think there is an explicit form. the norm is between $\|A\|_1$ and $\sqrt{n}\|A\|_1$.2011-08-02

1 Answers 1

4

I'll assume this is over the reals. You're looking for the norm of $A$ as a linear operator from $({\mathbb R}^p, \|\cdot\|_2)$ to $({\mathbb R}^p, \|\cdot\|_1)$. By duality, that is the same as the norm of $A^T$ as a linear operator from $({\mathbb R}^p, \|\cdot\|_\infty)$ to $({\mathbb R}^p, \|\cdot\|_2)$. Now the set of extreme points of the unit ball of $({\mathbb R}^p, \|\cdot\|_\infty)$ is $\{-1,1\}^p$, i.e. the set of $2^p$ vectors with all entries $\pm 1$, so your answer is the maximum of $\|A^T v\|_2$ for $v \in \{-1,1\}^p$.

  • 0
    Just tested this with a quick script. Duality is great!2011-08-02