Back to Search
Start Over
Inapproximability of matrix p → q norms.
- Source :
-
SIAM Journal on Computing . 2023, Vol. 52 Issue 1, p132-155. 24p. - Publication Year :
- 2023
-
Abstract
- We study the problem of computing the p q norm of a matrix A ∈ Rm×n, defined as ∣∣j4∣∣p-g = maxx∈Rn{0}'.||Ax|q/||x|p This problem generalizes the spectral norm of a matrix (p = q = 2) and the Grothendieck problem (p = ∞, q = 1) and has been widely studied in various regimes. When p ≥ q, the problem exhibits a dichotomy: constant factor approximation algorithms are known if 2 ∈ [g,p], and the problem is hard to approximate within almost polynomial factors when 2 [g,p]. The regime when p < q, known as Hypercontractive norms, is particularly significant for various applications but much less well understood. The case with p = 2 and q > 2 was studied by Barak et al. [Proceedings of the 4Ath Annual ACM Symposium on Theory of Computing, 2012, pp. 307--326], who gave subexponential algorithms for a promise version of the problem (which captures small-set expansion) and also proved hardness of approximation results based on the exponential time hypothesis. However, no NP-hardness of approximation is known for these problems for any p < q. We prove the first NP-hardness result (under randomized reductions) for approximating hypercontractive norms. We show that for any 1 < p < q < ∞ with 2 [p, g], ∣∣√4∣∣p--q is hard to approximate within 2°(log n)1-x) assuming NP g BPTIME(21log n A-). En rθute to the above result, we also prove almost tight results for the case when p > q with 2 ∈ [q, p]. [ABSTRACT FROM AUTHOR]
- Subjects :
- *MATRIX norms
*APPROXIMATION algorithms
*NP-hard problems
*POLYNOMIALS
*ALGORITHMS
Subjects
Details
- Language :
- English
- ISSN :
- 00975397
- Volume :
- 52
- Issue :
- 1
- Database :
- Academic Search Index
- Journal :
- SIAM Journal on Computing
- Publication Type :
- Academic Journal
- Accession number :
- 162778816
- Full Text :
- https://doi.org/10.1137/18M1233418