Rounding Sum-of-Squares Relaxations

STOC 2014.

abstract

We present a general approach to rounding semidefinite programming relaxations obtained by the Sum-of-Squares method (Lasserre hierarchy). Our approach is based on using the connection between these relaxations and the Sum-of-Squares proof system to transform a combining algorithm—an algorithm that maps a distribution over solutions into a (possibly weaker) solution—into a rounding algorithm that maps a solution of the relaxation to a solution of the original problem.

Using this approach, we obtain algorithms that yield improved results for natural variants of several well-known problems:

We give a quasipolynomial-time algorithm that approximates $\max_{\lVert x \rVert_2=1} P(x)$ within an additive factor of $\varepsilon\lVert P \rVert_{spectral}$ , where $\varepsilon>0$ is a constant, $P$ is a degree $d=O(1)$ , $n$ -variate polynomial with nonnegative coefficients, and $\lVert P \rVert_{spectral}$ is the spectral norm of a matrix corresponding to $P$ ’s coefficients. Beyond being of interest in its own right, obtaining such an approximation for general polynomials (with possibly negative coefficients) is a long-standing open question in quantum information theory, and our techniques have already led to improved results in this area (Brandão and Harrow, STOC ’13).
We give a polynomial-time algorithm that, given a subspace $V \subseteq \R^n$ of dimension $d$ that (almost) contains the characteristic function of a set of size $n/k$ , finds a vector $v\in V$ that satisfies $\mathbb E_i v_i^4 \geq \Omega(d^{-1/3} k(\mathbb E_i v_i^2)^2)$ . This is a natural analytical relaxation of the problem of finding the sparsest element in a subspace, and it is also motivated by a connection to the Small-Set Expansion problem shown by Barak et al. (STOC 2012). In particular our results yield an improvement of the previous best known algorithms for small-set expansion in a certain range of parameters.
We use this notion of $L_4$ vs. $L_2$ sparsity to obtain a polynomial-time algorithm with substantially improved guarantees for recovering a planted sparse vector $v$ in a random $d$ -dimensional subspace of $\R^n$ . If $v$ has $\mu n$ nonzero coordinates, we can recover it with high probability whenever $\mu\leq O(\min(1,n/d^2))$ . In particular, when $d\leq \sqrt{n}$ , this recovers a planted vector with up to $\Omega(n)$ nonzero coordinates. When $d\leq n^{2/3}$ , our algorithm improves upon existing methods based on comparing the $L_1$ and $L_\infty$ norms, which intrinsically require $\mu \leq O\left(1/\sqrt{d}\right)$ . We also show how this notion of $L_4$ vs. $L_2$ sparsity can be used to find a planted sparse vector in a random subspace, improving on a recent result of Demanet and Hand (2013).