Matrix p-Norms Are NP-Hard to Approximate If p!=q1, 2, INFINITY

Julien M. Hendrickx, Alexander 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.
BibTeX
@article{hendrickx2010matrix,
  author = {Julien M. Hendrickx and Alexander Olshevsky},
  title = {{Matrix p-Norms Are NP-Hard to Approximate If p!=q1, 2, INFINITY}},
  journal = {SIAM J. Matrix Anal. Appl.},
  year = {2010},
  url = {https://openreview.net/forum?id=Ir4safCbdt},
}

Loading related content...

Figure