Approximability of p → q Matrix Norms: Generalized Krivine Rounding and Hypercontractive Hardness
Vijay Bhattiprolu, Mrinalkanti Ghosh, Venkatesan Guruswami, Euiwoong Lee, Madhur Tulsiani · Society for Industrial and Applied Mathematics eBooks · 2019
We study the problem of computing the p → q operator norm of a matrix A in ℝm×n, defined as ‖A‖p→q : = supx∊ℝn\{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 is in [q, p], and the problem is hard to approximate within almost polynomial factors when 2 is not in [q,p]. For the case when 2 is in [q, p] we prove almost matching approximation and NP-hardness results. The regime when p 2 was studied by [Barak et. al., STOC’12] who gave sub-exponential 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 for approximating hypercontractive norms. We show that for any 1 < p < q < ∞ with 2 not in [p, q], ‖A‖p→q is hard to approximate within 2O(log1−∊ n) assuming NP is not contained in BPTIME(2logO(1) n)).