利用低秩结构加速复数二次优化，实现高效高精度求解。
Exploiting Low-Rank Objective Structure in Discrete Quadratic Optimization
- 通过分析目标矩阵的低秩特性，构造大小为O(rn^{2r-1})的候选集。
- 在近似低秩情况下，保证(1 - O(||H||₂/δ⋆))的乘法逼近率。
- 随机采样方案独立于问题规模，支持超大规模并行求解。
我们研究在K次单位根上最大化复数二次型的问题。当目标矩阵Q⋆∈ℂ^{n×n}的秩为r时，全局最大值点属于一个大小为O(rn^{2r−1})的候选集，该集合可在O(rn^{2r+1})时间内通过枚举ℝ^{2r}中超平面排列的顶点确定。算法可轻松并行化，使用P个处理器时时间复杂度降至O(r n^{2r+1}/P)。对于近似低秩情形（即目标矩阵为秩-r矩阵的噪声扰动），对谱截断应用本框架可获得乘法(1 - O(||H||₂/δ⋆))-近似保证，其中δ⋆为底层秩-r矩阵的特征值间隙，H为扰动项。为应对高维问题，我们提出随机采样变体：均匀采样S ≥ O(1/ε^{r−1})个候选点，以高概率实现(1−ε)cos²(π/K)的近似比。关键在于采样量与n无关，总时间降至O(S·n²)。在合成基准和大尺度图上的Max-3-Cut实验表明，该方法在结构化实例上性能媲美或超越半定规划，同时支持异构硬件上的大规模并行与超大规模扩展（n ≥ 10⁶）。
原文摘要 · Abstract (English)
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$.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。