Exploiting Low-Rank Objective Structure in Discrete Quadratic Optimization

We study the maximization of a positive semidefinite Hermitian quadratic form over vectors whose entries are $K$-th roots of unity, for any $K\ge 2$, a problem that contains Max-Cut ($K=2$), Max-3-Cut ($K=3$), and $K$-ary phase detection. When the objective matrix has rank $r$, the problem reduces to a search over directions on the unit sphere of ${\mathbb{C}}^r$: rounding each coordinate of $\mathbf{Vc}$, where $\mathbf{V}$ is the matrix factor of the given Hermitian matrix, to the nearest root turns a direction $\mathbf{c}$ into a candidate, and some direction yields an optimum. Exact search enumerates $O(r{n}^{2r-1})$ candidates. In this paper, we analyze the simplest alternative, which rounds $S$ uniformly random directions and keeps the best. One random direction is $(1-\epsilon )$-optimal with probability at least $(\epsilon /2{)}^{r-1}\min \{1,\frac{K}{\pi }\sqrt{\epsilon /2}\}$, for every $n$, so $S=O((2/\epsilon {)}^{r-1/2}\log (1/\delta ))$ samples and $O(Snr)$ time give a $(1-\epsilon )$-optimal solution with probability $1-\delta$. For noisy objectives ${\mathbf{Q}}^{\star }+\mathbf{H}$, rounding a rank-$r$ truncation loses at most $2n({\lambda }_{r+1}^{\star }+2\{\mathbf{H}{\}}_2)$, with no eigengap condition. In Max-3-Cut experiments, the number of samples needed for a near-best cut does not grow with $n$ on random regular graphs with up to $10^6$ vertices and on tori with up to $10^5$, per our settings; on graphs small enough to solve exactly, 100 samples reach $99.8\%$ of the rank-2 optimum on average; and on planted three-community graphs, whose objective is low rank plus noise, the bound for noisy objectives becomes informative as $n$ grows.