Matrix p-Norms Are NP-Hard to Approximate If $p\neq1,2,\infty$

Authors:
  • JHJulien M. Hendrickx
    Julien M. Hendrickx
  • AOAlex Olshevsky
    Alex Olshevsky

Abstract
We show that, for any rational $p\in[1,\infty)$ except $p=1,2$, unless $P=NP$, there is no polynomial time algorithm which approximates the matrix p-norm to arbitrary relative precision. We also show that, for any rational $p\in[1,\infty)$ including $p=1,2$, unless $P=NP$, there is no polynomial-time algorithm which approximates the $\infty,p$ mixed norm to some fixed relative precision.

This publication has 3 references indexed in Scilit: