Matrix p-Norms Are NP-Hard to Approximate If $p\neq1,2,\infty$
Authors:
- Julien M. HendrickxJHJulien M. Hendrickx
- Alex OlshevskyAOAlex Olshevsky
- 1 January 2010
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Matrix Analysis and Applications
- Vol. 31 (5) , 2802-2812
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.
Keywords
All Related Versions
This publication has 3 references indexed in Scilit:
- Some optimal inapproximability resultsJournal of the ACM, 2001
- Computing the norm ∥A∥∞,1 is NP-hard∗Linear and Multilinear Algebra, 2000
- Some NP-complete problems in quadratic and nonlinear programmingMathematical Programming, 1987