Inapproximability of Matrix $p\to q$ Norms

Abstract

We study the problem of computing the $p\to 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\ge 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<q$, known as \emph{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, 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]$, $\Vert A{\Vert }_{p\to q}$ is hard to approximate within $2^{O({\log }^{1-\epsilon }n)}$ assuming $NP⊈BPTIME(2^{{\log }^{O(1)}n})$. This suggests that, similar to the case of $p\ge q$, the hypercontractive setting may be qualitatively different when $2$ does not lie between $p$ and $q$. - For all $p\ge q$ with $2\in [q,p]$, we show $\Vert A{\Vert }_{p\to q}$ is hard to approximate within any factor than $1/({\gamma }_{p^{\ast }}\cdot {\gamma }_q)$, where for any $r$, ${\gamma }_r$ denotes the $r^{th}$ norm of a gaussian, and $p^{\ast }$ is the dual norm of $p$.