ECCC-Report TR18-037https://eccc.weizmann.ac.il/report/2018/037Comments and Revisions published for TR18-037en-usWed, 21 Feb 2018 18:03:46 +0200
Paper TR18-037
| Inapproximability of Matrix $p \rightarrow q$ Norms |
Vijay Bhattiprolu,
Mrinalkanti Ghosh,
Venkatesan Guruswami,
Euiwoong Lee,
Madhur Tulsiani
https://eccc.weizmann.ac.il/report/2018/037We study the problem of computing the $p\rightarrow q$ norm of a matrix $A \in R^{m \times n}$, defined as \[ \|A\|_{p\rightarrow q} ~:=~ \max_{x \,\in\, R^n \setminus \{0\}} \frac{\|Ax\|_q}{\|x\|_p} \] This problem generalizes the spectral norm of a matrix ($p=q=2$) and the Grothendieck problem ($p=\infty$, $q=1$), and has been widely studied in various regimes. When $p \geq q$, the problem exhibits a dichotomy: constant factor approximation algorithms are known if $2 \in [q,p]$, and the problem is hard to approximate within almost polynomial factors when $2 \notin [q,p]$.
The regime when $p$ is less than $q$, known as hypercontractive norms, is particularly significant for various applications but much less well understood. The case $p = 2$ and $q > 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 study the hardness of approximating matrix norms in both the above cases and prove the following results:
- We show that for any $1< p < q < \infty$ with $2 \notin [p,q]$, $\|A\|_{p\rightarrow q}$ is hard to approximate within $2^{O(\log^{1-\epsilon}\!n)}$ assuming $NP \not\subseteq BPTIME(2^{\log^{O(1)}\!n})$. This suggests that, similar to the case of $p \geq q$, the hypercontractive setting may be qualitatively different when $2$ does not lie between $p$ and $q$.
- For all $p \geq q$ with $2 \in [q,p]$, we show $\|A\|_{p\rightarrow q}$ is hard to approximate within any factor smaller than $1/(\gamma_{p^*} \cdot \gamma_q)$, where $\gamma_r$ denotes the $r^{th}$ norm of the standard Gaussian, and $p^*$ is the dual norm of $p$.Wed, 21 Feb 2018 18:03:46 +0200https://eccc.weizmann.ac.il/report/2018/037