# On the induced matrix norm $\| \cdot \|_{2,\infty}$

The induced norm of the matrix $A$ as a map from $(\mathbb R^n , \| \cdot \|_p)$ to $(\mathbb R^m, \| \cdot \|_q)$ is given by $$\| A \|_{p,q} = \sup_{x\in\mathbb{R}^n\setminus \{0\}} \frac{\|Ax\|_q}{\|x\|_p}.$$

I would like to compute $\| \cdot \|_{2,\infty}$. In this paper: On the Calculation of the $l_2\to l_1$ Induced Matrix Norm, the authors presented the results for any $p,q\in\{1,2,\infty\}$, except for $p=2$ and $q=\infty$.

So I would like to know if this is still an open problem. And if it is, then is there any result on finding a tight and easy-to-compute upper bound on the norm?

Computing such induced norms is a hard problem. For the case of $p=2$ and $q \ge 2$, have a look at this paper by Barak et al. to see how tricky the problem is.

Typically, for other than the nice cases of $1,2, \infty$ style, these norms are NP-hard to compute, with well-known results for the case $p \ge q$ (see also e.g.: "Matrix norms are NP-Hard to approximate"). The paper of Barak et al focuses on the hypercontractive case of $p < q$.

For the specific case of $p=2$ and $q=\infty$ mentioned above, I think the paper of Barak et al cited above mentions that the norm is just the largest 2-norm of any row of the matrix (thanks to N. Johnston for pointing this out).

• In fact, the Barak et. al. paper that you linked explicitly says that the $2\rightarrow\infty$ norm is just the largest 2-norm of any row of the matrix (on page 3). Commented Oct 3, 2014 at 17:34
• @NathanielJohnston: ah thanks! I just guessed the answer given what holds for the induced $\infty$-norm :-) Commented Oct 3, 2014 at 18:09
• Thanks, Suvrit and @NathanielJohnston. I had figured it out too. The adjoint operator of $A$, mapping $(\mathbb R^m , \| \cdot \|_p^*) = (\mathbb R^m , \| \cdot \|_{p/(p-1)})$ to $(\mathbb R^n, \| \cdot \|_q^*) = (\mathbb R^n, \| \cdot \|_{p/(p-1)})$ is the transpose matrix $A^T$. Since $\|A\|_{p,q} = \|A^T\|_{q/(q-1),p/(p-1)}$, we have $\|A\|_{2,\infty}=\|A^T\|_{1,2}$ and so we can apply the result of the case $1\to 2$. (next below)
– f10w
Commented Oct 3, 2014 at 19:48
• But now I have another problem. The paper you cited (Paper 2) contradicts the paper that I cited (Paper 1). The equation (2h) in Paper 1 says that $\|A\|_{\infty,2}$ is the largest 2-norm of any row, while in Paper 2 this should be the value of $\|A\|_{2,\infty}$.
– f10w
Commented Oct 3, 2014 at 19:48
• Either Paper 1 is mistaken/has a typo, or there's a notational mix-up in it that I'm missing. $\|A\|_{\infty,2}$ can't be the largest 2-norm of any row. For a counterexample, let $A$ be the matrix with first row all $1$ and elsewhere all $0$... multiplying $A$ by the all-ones vector shows that $\|A\|_{\infty,2} \geq n$, but the largest $2$-norm of a row is just $\sqrt{n}$. Commented Oct 4, 2014 at 0:53