5
$\begingroup$

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?

Thank you in advance.

$\endgroup$

1 Answer 1

4
$\begingroup$

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

$\endgroup$
7
  • 4
    $\begingroup$ 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). $\endgroup$ Commented Oct 3, 2014 at 17:34
  • $\begingroup$ @NathanielJohnston: ah thanks! I just guessed the answer given what holds for the induced $\infty$-norm :-) $\endgroup$
    – Suvrit
    Commented Oct 3, 2014 at 18:09
  • $\begingroup$ 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) $\endgroup$
    – f10w
    Commented Oct 3, 2014 at 19:48
  • $\begingroup$ 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}$. $\endgroup$
    – f10w
    Commented Oct 3, 2014 at 19:48
  • 2
    $\begingroup$ 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}$. $\endgroup$ Commented Oct 4, 2014 at 0:53

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.