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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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).

Improve this answer
$\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$
    – Nathaniel Johnston
    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$
    – Nathaniel Johnston
    Commented Oct 4, 2014 at 0:53

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .