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

Hendrickx, Julien;Olshevsky, A.
(2010) SIAM Journal on Matrix Analysis and Applications — Vol. 31, n° 5, p. 2802-2812 (2010)

Files

76773.pdf
  • Restricted Access
  • Adobe PDF
  • 179.65 KB
Request a copy

Details

Authors
  • Hendrickx, Julienorcid-logoUCLouvain
    Author
  • Olshevsky, A.Massachusetts Institute of Technology
    Author
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.
Affiliations

Citations

  • APA
  • Chicago
  • FWB

Hendrickx, J., & Olshevsky, A. (2010). Matrix P-norms are NP-hard to approximate if p eq 1,2,infty. SIAM Journal on Matrix Analysis and Applications, 31(5), 2802-2812. https://doi.org/10.1137/09076773X (Original work published 2010)