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

Julien M. Hendrickx, Alex Olshevsky

Research output: Contribution to journalArticlepeer-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 languageEnglish (US)
Pages (from-to)2802-2812
Number of pages11
JournalSIAM Journal on Matrix Analysis and Applications
Volume31
Issue number5
DOIs
StatePublished - 2010

Keywords

  • Complexity
  • Matrix norms
  • NP-hardness

ASJC Scopus subject areas

  • Analysis

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