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?

  • 4
    $\begingroup$ 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. $\endgroup$ – Mahdi Cheraghchi May 28 '13 at 14:55
  • 4
    $\begingroup$ In short - the thesis is about more general norms, which are often hard. $\endgroup$ – 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.

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

| cite | improve this answer | |
  • 2
    $\begingroup$ 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. $\endgroup$ – Sasho Nikolov May 28 '13 at 17:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.