2018/02/21 by Vijay Bhattiprolu, Bhattiprolu, Vijay, Mrinalkanti Ghosh +7 · 1 citation
Mathematics · Engineering · #Mathematical Approximation and Integration #Advanced Numerical Analysis Techniques #Advanced Optimization Algorithms Research
paper · pdf · doi:10.48550/arxiv.1802.07425
We study the problem of computing the p→ q norm of a matrix A ∈ Rm × n, defined as ‖A‖p→ q ~:=~ max_x ∈ 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 ∈ [q,p], and the problem is hard to approximate within almost polynomial factors when 2 ∉ [q,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, 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 < ∞ with 2 ∉ [p,q], ‖A‖p→ q is hard to approximate within 2^O(log1-ε n) assuming NP \not⊆ BPTIME(2^logO(1) n). This suggests that, similar to the case of p ≥ q, the hypercontractive setting may be qualitatively different when 2 does not lie between p and q. - For all p ≥ q with 2 ∈ [q,p], we show ‖A‖p→ q is hard to approximate within any factor than 1/(γp^* ⋅ γq), where for any r, γr denotes the rth norm of a gaussian, and p^* is the dual norm of p.