Skip to main content
fixed citation to proof of 2 infty
Source Link
Suvrit
  • 28.6k
  • 7
  • 82
  • 150

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 thinkI think the paper of Barak et al cited above mentions that the norm will beis just the largest 2-norm of any row of the matrix (thanks to N. Johnston for pointing this out).

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 norm will be just the largest 2-norm of any row of the matrix.

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

Source Link
Suvrit
  • 28.6k
  • 7
  • 82
  • 150

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 norm will be just the largest 2-norm of any row of the matrix.