The computational complexity of spectral norm of a matrix

How hard is computing the spectral norm of a matrix? This paper 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?

• 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. Commented May 28, 2013 at 14:55
• In short - the thesis is about more general norms, which are often hard. Commented May 28, 2013 at 15:27

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.
• 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 is better than the constant in Prop 1.5. Commented May 28, 2013 at 17:35