Exploiting Low-Rank Objective Structure in Discrete Quadratic Optimization

Résumé fourni par la source

We study the problem of maximizing a complex-valued quadratic form over the $K^{\text{th}}$ roots of unity. We show that when the objective matrix $\mathbf{Q}^\star \in \mathbb{C}^{n \times n}$ of the quadratic has rank $r$, the global maximizer belongs to a candidate set of size $O(rn^{2r-1})$. This set can be constructed deterministically in $O(rn^{2r+1})$ time by enumerating the vertices of a hyperplane arrangement in $\mathbb{R}^{2r}.$ The algorithm is embarrassingly parallel; with~$P$ processors, the time complexity drops to $O(r n^{2r+1}/P)$. For approximately low-rank settings, where the objective matrix is a noise-perturbed variant of a rank-$r$ matrix, we prove that applying our framework to a spectral truncation yields a multiplicative $(1 - O(\left\|\mathbf{H}\right\|_2 / δ^{\star}))$-approximation guarantee, where $δ^{\star}$ denotes the eigengap of the underlying rank-$r$ matrix and $\mathbf{H}$ represents the perturbation. To scale to high-dimensional problems, we establish a randomized sampling variant. We prove that uniformly sampling $S \geq O(1/\varepsilon^{r-1})$ candidates achieves a $(1-\varepsilon)\cos^2(π/ K)$-approximation of the optimal rank-$r$ solution with high probability. Crucially, this sample size is entirely independent of $n$, reducing the overall runtime to $O(S \cdot n^2)$. Computational experiments on synthetic benchmarks and large-scale graphs for \textsc{Max-3-Cut} confirm that our algorithms match or exceed semi-definite programming solution quality on structured instances while enabling massive parallelization across heterogeneous hardware and scaling seamlessly to problems where $n \geq 10^6$.

Ce résumé expose les affirmations des auteurs. BNTIC ne l’interprète pas comme une validation indépendante des résultats.