# 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. – Mahdi Cheraghchi May 28 '13 at 14:55
• In short - the thesis is about more general norms, which are often hard. – Yuval Filmus May 28 '13 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. – Sasho Nikolov May 28 '13 at 17:35