Matrix P-norms are NP-hard to approximate if p eq 1,2,infty

DIAL.pr - BOREAL

Primary tabs

Authors	:	(Auteur) Hendrickx, Julien [UCL] (Auteur) Olshevsky, A. [Massachusetts Institute of Technology]
Document type	:	Article de périodique (Journal article) – Article de recherche
Abstract	:	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.
Access type	:	Accès restreint
Publication date	:	2010
Language	:	Anglais
Journal information	:	"SIAM Journal on Matrix Analysis and Applications" - Vol. 31, no. 5, p. 2802-2812 (2010)
Peer reviewed	:	yes
issn	:	0895-4798
e-issn	:	1095-7162
Publication status	:	Publié
Affiliations	:	UCL - SST/ICTM/INMA - Pôle en ingénierie mathématique Massachusetts Institute of Technology - LIDS
Links	:	[Handle]http://hdl.handle.net/2078.1/89624 [DOI]https://doi.org/10.1137/09076773X

Bibliographic reference	Hendrickx, Julien ; Olshevsky, A.. Matrix P-norms are NP-hard to approximate if p eq 1,2,infty. In: SIAM Journal on Matrix Analysis and Applications, Vol. 31, no. 5, p. 2802-2812 (2010)
Permanent URL	http://hdl.handle.net/2078.1/89624