Matrix p-Norms are NP-Hard to approximate if pne; 1, 2,∞

Julien M. Hendrickx; Alex Olshevsky

doi:10.1137/09076773X

Matrix p-Norms are NP-Hard to approximate if pne; 1, 2,∞

Julien M. Hendrickx, Alex Olshevsky

Industrial and Enterprise Systems Engineering

Research output: Contribution to journal › Article › peer-review

Abstract

We show that, for any rational p ε [1,∞) 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,∞) including p = 1, 2, unless P = NP, there is no polynomialtime algorithm which approximates the ∞, p mixed norm to some fixed relative precision.

Original language	English (US)
Pages (from-to)	2802-2812
Number of pages	11
Journal	SIAM Journal on Matrix Analysis and Applications
Volume	31
Issue number	5
DOIs	https://doi.org/10.1137/09076773X
State	Published - 2010

Keywords

Complexity
Matrix norms
NP-hardness

ASJC Scopus subject areas

Analysis

Access to Document

10.1137/09076773X

Fingerprint Dive into the research topics of 'Matrix p-Norms are NP-Hard to approximate if pne; 1, 2,∞'. Together they form a unique fingerprint.

Cite this

@article{5dc31becb0ed43a08bbcd5292df1f903,

title = "Matrix p-Norms are NP-Hard to approximate if pne; 1, 2,∞",

abstract = "We show that, for any rational p ε [1,∞) 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,∞) including p = 1, 2, unless P = NP, there is no polynomialtime algorithm which approximates the ∞, p mixed norm to some fixed relative precision.",

keywords = "Complexity, Matrix norms, NP-hardness",

author = "Hendrickx, {Julien M.} and Alex Olshevsky",

year = "2010",

doi = "10.1137/09076773X",

language = "English (US)",

volume = "31",

pages = "2802--2812",

journal = "SIAM Journal on Matrix Analysis and Applications",

issn = "0895-4798",

publisher = "Society for Industrial and Applied Mathematics Publications",

number = "5",

}

TY - JOUR

T1 - Matrix p-Norms are NP-Hard to approximate if pne; 1, 2,∞

AU - Hendrickx, Julien M.

AU - Olshevsky, Alex

PY - 2010

Y1 - 2010

N2 - We show that, for any rational p ε [1,∞) 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,∞) including p = 1, 2, unless P = NP, there is no polynomialtime algorithm which approximates the ∞, p mixed norm to some fixed relative precision.

AB - We show that, for any rational p ε [1,∞) 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,∞) including p = 1, 2, unless P = NP, there is no polynomialtime algorithm which approximates the ∞, p mixed norm to some fixed relative precision.

KW - Complexity

KW - Matrix norms

KW - NP-hardness

UR - http://www.scopus.com/inward/record.url?scp=79251470109&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=79251470109&partnerID=8YFLogxK

U2 - 10.1137/09076773X

DO - 10.1137/09076773X

M3 - Article

AN - SCOPUS:79251470109

VL - 31

SP - 2802

EP - 2812

JO - SIAM Journal on Matrix Analysis and Applications

JF - SIAM Journal on Matrix Analysis and Applications

SN - 0895-4798

IS - 5

ER -