Name
Abstract | ||
|---|---|---|
We consider the following basic problem: given an $n$-variate degree-$d$ homogeneous polynomial $f$ with real coefficients, compute a unit vector $x mathbb{R}^n$ that maximizes $|f(x)|$. Besides its fundamental nature, this problem arises in many diverse contexts ranging from tensor and operator norms to graph expansion to quantum information theory. The homogeneous degree $2$ case is efficiently solvable as it corresponds to computing the spectral norm of an associated matrix, but the higher degree case is NP-hard. In this work, we give multiplicative approximation algorithms for this problem. Our algorithms leverage the tractability of the degree $2$ case, and output the best solution among a carefully constructed set of quadratic polynomials. They offer a trade-off between the approximation ratio and running time, which is governed by the number of quadratic problems we search over. Specifically, in $n^{O(q)}$ time, we get an approximation within factor $O_d((n/q)^{d/2-1})$ for arbitrary polynomials, and $O_d((n/q)^{d/4-1/2})$ for polynomials with non-negative coefficients. The approximation guarantees are with respect to the optimum of the level-$q$ SoS SDP relaxation of the problem, which the algorithm rounds to a unit vector. We also consider the case when $f$ is random with independent $pm 1$ coefficients, and prove that w.h.p the level-$q$ SoS solution gives a certificate within factor $tilde{O}_d((n/q)^{d/4-1/2})$ of the optimum. We complement our algorithmic results with some polynomially large integrality gaps for $d$-levels of the SoS relaxation. To obtain our results, we develop general techniques which help analyze the approximation obtained by higher levels of the SoS hierarchy. We believe these techniques will also be useful in understanding polynomial optimization for other constrained settings. |
Year | Venue | DocType |
|---|---|---|
2016 | Electronic Colloquium on Computational Complexity (ECCC) | Journal |
Volume | Citations | PageRank |
abs/1611.05998 | 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 |
| Euiwoong Lee | 3 | 47 | 15.45 |
| V. Guruswami | 4 | 3205 | 247.96 |
| Madhur Tulsiani | 5 | 358 | 24.60 |