Name
Abstract | ||
|---|---|---|
We consider the $(ell_p,ell_r)$-Grothendieck problem, which seeks maximize the bilinear form $y^T A x$ for an input matrix $A$ over vectors $x,y$ with $|x|_p=|y|_r=1$. The problem is equivalent computing the $p to r^*$ operator norm of $A$. The case $p=r=infty$ corresponds the classical Grothendieck problem. main result is an algorithm for arbitrary $p,r ge 2$ with approximation ratio $(1+epsilon_0)/(sinh^{-1}(1)cdot gamma_{p^*} ,gamma_{r^*})$ for some fixed $epsilon_0 le 0.00863$. Comparing this with Krivineu0027s approximation ratio of $(pi/2)/sinh^{-1}(1)$ for the original Grothendieck problem, our guarantee is off from the best known hardness factor of $(gamma_{p^*} gamma_{r^*})^{-1}$ for the problem by a factor similar Krivineu0027s defect. Our approximation follows by bounding the value of the natural vector relaxation for the problem which is convex when $p,r ge 2$. We give a generalization of random hyperplane rounding and relate the performance of this rounding certain hypergeometric functions, which prescribe necessary transformations the vector solution before the rounding is applied. Unlike Krivineu0027s Rounding where the relevant hypergeometric function was $arcsin$, we have study a family of hypergeometric functions. The bulk of our technical work then involves methods from complex analysis gain detailed information about the Taylor series coefficients of the inverses of these hypergeometric functions, which then dictate our approximation factor. Our result also implies improved bounds for factorization through $ell_{2}^{,n}$ of operators from $ell_{p}^{,n}$ $ell_{q}^{,m}$ (when $pgeq 2 geq q$)--- such bounds are of significant interest in functional analysis and our work provides modest supplementary evidence for an intriguing parallel between factorizability, and constant-factor approximability. |
Year | Venue | DocType |
|---|---|---|
2018 | Electronic Colloquium on Computational Complexity (ECCC) | Journal |
Volume | Citations | PageRank |
abs/1804.03644 | 0 | 0.34 |
References | Authors | |
0 | 5 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Vijay V. S. P. Bhattiprolu | 1 | 1 | 3.06 |
| Mrinal Kanti Ghosh | 2 | 2 | 2.75 |
| V. Guruswami | 3 | 3205 | 247.96 |
| Euiwoong Lee | 4 | 47 | 15.45 |
| Madhur Tulsiani | 5 | 358 | 24.60 |