MATRIX p-NORMS ARE NP-HARD TO APPROXIMATE IF p not equal to 1, 2, infinity

We show that, for any rational p ∈ [1,∞) [p is an element of the set [1, infinity)] 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 ∈ [1,∞) [p is an element of the set...

Full description

Bibliographic Details
Main Authors: Hendrickx, Julien, Olshevsky, Alexander
Other Authors: Massachusetts Institute of Technology. Laboratory for Information and Decision Systems
Format: Article
Language:en_US
Published: Society for Industrial and Applied Mathematics 2011
Online Access:http://hdl.handle.net/1721.1/64956