提出紧凑的凸松弛方法,高效求解低秩矩阵优化问题。
Compact Lifted Relaxations for Low-Rank Optimization
- 通过去冗余的提升松弛,将大尺寸半定约束压缩为两个小规模约束。
- 在矩阵补全与降维回归中,松弛规模可缩小至不超过n+m的半定矩阵。
- 新提出的投影割平面能显著增强低秩松弛效果,适合大规模优化场景。
我们为n×m矩阵上的秩约束二次优化问题构建了可处理的凸松弛方法,这类问题通常仅在目标或约束具有谱结构时才有有效松弛。本文推导出无需谱项的提升型半定松弛。尽管直接提升会引入维度为n²+nm+1的大型半定约束,但我们证明了矩矩阵中的多个块是冗余的,从而得到等价的紧凑松弛:仅包含两个维度分别为nm+1和n+m的半定约束。此外,我们提出了新的有效不等式——投影割,利用低秩矩阵的线性像仍保持低秩的性质,大幅强化低秩松弛。针对矩阵补全、降维回归等问题,进一步结合结构特性,获得更紧凑的公式,其半定矩阵维度最高仅为低秩决策矩阵两维之和(即最多n+m)。总体而言,本方法为一大类低秩二次问题提供了可扩展的半定界。
原文摘要 · Abstract (English)
We develop tractable convex relaxations for rank-constrained quadratic optimization problems over $n \times m$ matrices, a setting for which tractable relaxations are typically only available when the objective or constraints admit spectral structure. We derive lifted semidefinite relaxations that do not require such spectral terms. Although a direct lifting introduces a large semidefinite constraint in dimension $n^2 + nm + 1$, we prove that many blocks of the moment matrix are redundant and derive an equivalent compact relaxation that only involves two semidefinite constraints of dimension $nm + 1$ and $n+m$, respectively. We also derive a new class of valid inequalities for low-rank problems, which we call projection cuts, that exploit the fact that rank constraints are inherited by linear images of a low-rank matrix, to strengthen our low-rank relaxations substantially. For matrix completion and reduced-rank regression problems, among others, we exploit additional structure to obtain even more compact formulations involving semidefinite matrices of dimension at most the sum of the two dimensions of the low-rank decision matrix (i.e., of size at most $n+m$). Overall, we obtain scalable semidefinite bounds for a broad class of low-rank quadratic problems.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。