Approximability of p → q Matrix Norms: Generalized Krivine Rounding and Hypercontractive Hardness
Approximability of p → q Matrix Norms: Generalized Krivine Rounding and Hypercontractive Hardness
复制标题
DOI：
10.1137/1.9781611975482.83
复制
发表时间：
2019-01
影响因子：
2.1
通讯作者：
V. Bhattiprolu;Mrinalkanti Ghosh;V. Guruswami;Euiwoong Lee;Madhur Tulsiani
中科院分区：
文献类型：
--
作者：
V. Bhattiprolu;Mrinalkanti Ghosh;V. Guruswami;Euiwoong Lee;Madhur Tulsiani
我们研究计算一个\(m\times n\)实矩阵\(A\)的\(p\rightarrow q\)算子范数的问题，其定义为\(\|A\|_{p\rightarrow q}:=\sup_{x\in\mathbb{R}^n\setminus\{0\}}\frac{\|Ax\|_q}{\|x\|_p}\)。这个问题推广了矩阵的谱范数（\(p = q = 2\)）以及格罗滕迪克问题（\(p=\infty,q = 1\)），并且在各种情形下已被广泛研究。当\(p\geq q\)时，该问题呈现出一种二分性：如果\(2\in[q,p]\)，则存在常数因子近似算法；而当\(2\notin[q,p]\)时，该问题在几乎多项式因子内是难以近似的。对于\(2\in[q,p]\)的情况，我们证明了几乎匹配的近似结果和NP - 困难性结果。当\(p<q\)且\(2\notin[q,p]\)的情形由[Barak等人，STOC’12]进行了研究，他们针对该问题的一个限定版本（其涵盖了小集合扩张）给出了次指数算法，并且还基于指数时间假设证明了近似困难性结果。然而，对于任何\(p<q\)的这些问题，尚未有近似的NP - 困难性结果被知晓。我们证明了关于近似超压缩范数的第一个NP - 困难性结果。我们表明，对于任何\(1<p<q<\infty\)且\(2\notin[p,q]\)，假设\(NP\)不包含在\(BPTIME(2^{\log^{O(1)}n})\)中，\(\|A\|_{p\rightarrow q}\)在\(2^{O(\log^{1-\varepsilon}n)}\)内是难以近似的。
We study the problem of computing the p → q operator norm of a matrix A in R m × n , defined as || A || p → q := sup x ∈ R 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 2 O (log 1 − ε n ) assuming NP is not contained in BPTIME(2 log O (1) n ) .