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...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Society for Industrial and Applied Mathematics
2011
|
| Online Access: | http://hdl.handle.net/1721.1/64956 |
| _version_ | 1811095867995717632 |
|---|---|
| author | Hendrickx, Julien Olshevsky, Alexander |
| author2 | Massachusetts Institute of Technology. Laboratory for Information and Decision Systems |
| author_facet | Massachusetts Institute of Technology. Laboratory for Information and Decision Systems Hendrickx, Julien Olshevsky, Alexander |
| author_sort | Hendrickx, Julien |
| collection | MIT |
| description | 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 [1, infinity)] including p = 1, 2, unless P = NP, there is no polynomialtime
algorithm which approximates the ∞, p [infinity, p] mixed norm to some fixed relative precision. |
| first_indexed | 2024-09-23T16:30:46Z |
| format | Article |
| id | mit-1721.1/64956 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T16:30:46Z |
| publishDate | 2011 |
| publisher | Society for Industrial and Applied Mathematics |
| record_format | dspace |
| spelling | mit-1721.1/649562022-10-02T08:12:23Z MATRIX p-NORMS ARE NP-HARD TO APPROXIMATE IF p not equal to 1, 2, infinity Hendrickx, Julien Olshevsky, Alexander Massachusetts Institute of Technology. Laboratory for Information and Decision Systems Olshevsky, Alexander Hendrickx, Julien Olshevsky, Alexander 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 [1, infinity)] including p = 1, 2, unless P = NP, there is no polynomialtime algorithm which approximates the ∞, p [infinity, p] mixed norm to some fixed relative precision. National Science Foundation (U.S.) (Grant ECCS-0701623) 2011-07-25T17:55:41Z 2011-07-25T17:55:41Z 2010-10 2010-07 Article http://purl.org/eprint/type/JournalArticle 0895-4798 1095-7162 http://hdl.handle.net/1721.1/64956 Hendrickx, Julien M., and Alex Olshevsky. “Matrix $p$-Norms Are NP-Hard to Approximate If $p\neq1,2,\infty$.” SIAM Journal on Matrix Analysis and Applications 31.5 (2010) : 2802. © 2010 Society for Industrial and Applied Mathematics en_US http://dx.doi.org/10.1137/09076773x SIAM Journal on Matrix Analysis and Applications Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. application/pdf Society for Industrial and Applied Mathematics SIAM |
| spellingShingle | Hendrickx, Julien Olshevsky, Alexander MATRIX p-NORMS ARE NP-HARD TO APPROXIMATE IF p not equal to 1, 2, infinity |
| title | MATRIX p-NORMS ARE NP-HARD TO APPROXIMATE IF p not equal to 1, 2, infinity |
| title_full | MATRIX p-NORMS ARE NP-HARD TO APPROXIMATE IF p not equal to 1, 2, infinity |
| title_fullStr | MATRIX p-NORMS ARE NP-HARD TO APPROXIMATE IF p not equal to 1, 2, infinity |
| title_full_unstemmed | MATRIX p-NORMS ARE NP-HARD TO APPROXIMATE IF p not equal to 1, 2, infinity |
| title_short | MATRIX p-NORMS ARE NP-HARD TO APPROXIMATE IF p not equal to 1, 2, infinity |
| title_sort | matrix p norms are np hard to approximate if p not equal to 1 2 infinity |
| url | http://hdl.handle.net/1721.1/64956 |
| work_keys_str_mv | AT hendrickxjulien matrixpnormsarenphardtoapproximateifpnotequalto12infinity AT olshevskyalexander matrixpnormsarenphardtoapproximateifpnotequalto12infinity |