<p>The answer to your question is the contents of section 1.3.2, titled "[w]hen $\mathcal{P}_{p,r}$ is known to be difficult". (Here $\mathcal{P}_{p,r}$ is the problem of computing the norm $\|A\|_{p,r} = \sup_{\|x\|_p=1} \|Ax\|_r$.) According to that section, the only cases which are known to be difficult are $\mathcal{P}_{\infty,1},\mathcal{P}_{\infty,2},\mathcal{P}_{2,1}$. For example, $\mathcal{P}_{\infty,1}$ (even restricted to positive semidefinite matrices) is a generalization of MAX CUT. Since $\|B'B\|_{\infty,1} = \|B\|_{\infty,2}^2$, $\mathcal{P}_{\infty,2}$ is also hard. Finally, $\mathcal{P}_{2,1}$ is as hard as $\mathcal{P}_{\infty,2}$ as part of the more general observation (proved in section 1.3.1) that $\mathcal{P}_{p,r}$ is as hard as $\mathcal{P}_{1/(1-1/r), 1/(1-1/p)}$.</p>

<p>The thesis goes on to prove that $\mathcal{P}_{p,r}$ is hard whenever $p &gt; r$ - this is the chapter you were reading (chapter 2).</p>

<p>Section 1.3.1 described some easy cases: $\mathcal{P}_{1,\ast}$, the symmetric $\mathcal{P}_{\ast,\infty}$, and the case that MCH mentioned, $\mathcal{P}_{2,2}$. Section 1.3.3 covers some approximability results, several novel of which are described in section 1.4 and the remaining chapters.</p>

<p>The title of section 1.3.2 appears in the table of contents (page iii) - just a hint for next time.</p>

CC BY-SA 3.0
2013-05-28T17:35:43.217Z
It's a bit strange the thesis does not mention that an approximation to $\|A\|_{\infty \rightarrow 1}$ follows from Grothendieck's inequality, and the related algorithmic work of Alon and Naor. Krivine's bound $\pi/2\ln(1 + \sqrt{2})$ in [Alon-Naor](http://www.cims.nyu.edu/~naor/homepage%20files/cutnorm.pdf) is better than the constant in Prop 1.5.
Sasho Nikolov
CC BY-SA 3.0
2013-05-28T15:25:04.827Z
2013-05-28T15:25:04.827Z
Yuval Filmus
<p>How hard is computing the spectral norm of a matrix? This <a href="http://www2.isye.gatech.edu/~nemirovs/Daureen.pdf">paper</a> says,</p>

<blockquote>
  <p>... it suffices to say that, except for few particular cases, the Matrix
  Norm problem is NP-hard.</p>
</blockquote>

<p>I expected that the relevant chapter 2 would describe those exceptional cases but failed to find it.</p>

<p>Can anyone suggest a more definitive reference for computational complexity of spectral norm of a matrix?</p>

CC BY-SA 3.0
2013-05-28T14:55:17.337Z
Spectral norm is the maximum singular value of the matrix, and can thus be computed in polynomial time, say by computing the singular value decomposition.
Mahdi Cheraghchi
CC BY-SA 3.0
2013-05-28T15:27:07.117Z
In short - the thesis is about more general norms, which are often hard.
Yuval Filmus
<np-hardness><quantum-computing><matrices><quantum-information><norms>
The computational complexity of spectral norm of a matrix
Omar Shehab
# The computational complexity of spectral norm of a matrix

(Asked by: username_0 on 2013-05-28)

How hard is computing the spectral norm of a matrix? This [paper](http://www2.isye.gatech.edu/~nemirovs/Daureen.pdf) says,

> ... it suffices to say that, except for few particular cases, the Matrix
> Norm problem is NP-hard.

I expected that the relevant chapter 2 would describe those exceptional cases but failed to find it.

Can anyone suggest a more definitive reference for computational complexity of spectral norm of a matrix?

**Tags:** np-hardness, quantum-computing, matrices, quantum-information, norms
> **Comments:**
> **username_1**: Spectral norm is the maximum singular value of the matrix, and can thus be computed in polynomial time, say by computing the singular value decomposition.  
> **username_2**: In short - the thesis is about more general norms, which are often hard.  

---

## 1 answers

### Answer by username_2 on 2013-05-28. Score: 9 | Accepted answer

The answer to your question is the contents of section 1.3.2, titled "[w]hen $\mathcal{P}\_{p,r}$ is known to be difficult". (Here $\mathcal{P}\_{p,r}$ is the problem of computing the norm $\|A\|\_{p,r} = \sup\_{\|x\|\_p=1} \|Ax\|\_r$.) According to that section, the only cases which are known to be difficult are $\mathcal{P}\_{\infty,1},\mathcal{P}\_{\infty,2},\mathcal{P}\_{2,1}$. For example, $\mathcal{P}\_{\infty,1}$ (even restricted to positive semidefinite matrices) is a generalization of MAX CUT. Since $\|B'B\|\_{\infty,1} = \|B\|\_{\infty,2}^2$, $\mathcal{P}\_{\infty,2}$ is also hard. Finally, $\mathcal{P}\_{2,1}$ is as hard as $\mathcal{P}\_{\infty,2}$ as part of the more general observation (proved in section 1.3.1) that $\mathcal{P}\_{p,r}$ is as hard as $\mathcal{P}\_{1/(1-1/r), 1/(1-1/p)}$.

The thesis goes on to prove that $\mathcal{P}\_{p,r}$ is hard whenever $p > r$ - this is the chapter you were reading (chapter 2).

Section 1.3.1 described some easy cases: $\mathcal{P}\_{1,\ast}$, the symmetric $\mathcal{P}\_{\ast,\infty}$, and the case that MCH mentioned, $\mathcal{P}\_{2,2}$. Section 1.3.3 covers some approximability results, several novel of which are described in section 1.4 and the remaining chapters.

The title of section 1.3.2 appears in the table of contents (page iii) - just a hint for next time.

> **Comments:**
> **username_3**: It's a bit strange the thesis does not mention that an approximation to $\|A\|_{\infty \rightarrow 1}$ follows from Grothendieck's inequality, and the related algorithmic work of Alon and Naor. Krivine's bound $\pi/2\ln(1 + \sqrt{2})$ in [Alon-Naor](http://www.cims.nyu.edu/~naor/homepage%20files/cutnorm.pdf) is better than the constant in Prop 1.5.  

---

