2010 • Journal Article
Matrix P-norms are NP-hard to approximate if p eq 1,2,infty
Authors:
Hendrickx, Julien ,
Olshevsky, Alex
Published in:
SIAM Journal on Matrix Analysis and Applications
Volume: 31 • Number: 5 • Pages: 2802-2812
We show that for any rational p in [1,infty) except p = 1, 2, unless P = NP, there is no polynomial-time algorithm for approximating the matrix p-norm to arbitrary relative precision. We also show that for any rational pin [1,infty) including p = 1, 2, unless P = NP, there is no polynomial-time algorithm approximates the infty, p mixed norm to some fixed relative precision.