提出新型矩阵流形优化方法，加速指示矩阵求解并提升聚类性能。
Riemannian Optimization on Relaxed Indicator Matrix Manifold
- 构建松弛指示矩阵流形，基于黎曼几何设计高效优化工具
- 计算复杂度降至O(n)，比传统方法快得多且结果更优
- 适用于大规模聚类与图像去噪，理论证明收敛性
指示矩阵在机器学习中至关重要，但其优化是NP难问题。本文提出一种新的指示矩阵松弛方式，证明该松弛构成流形，称为松弛指示矩阵流形（RIM流形）。基于黎曼几何，构建了RIM流形上的优化工具箱，包括多种收缩映射方法，其中快速收缩法可高效生成测地线。RIM流形是双随机流形的推广，其优化复杂度为$\mathcal{O}(n)$，远低于传统双随机流形的$\mathcal{O}(n^3)$，且常取得更优结果。实验涵盖百万变量级图像去噪，并应用于比例切割（Ratio Cut）任务，给出严格的收敛性证明，聚类效果超越现有最优方法。代码开源：https://github.com/Yuan-Jinghui/Riemannian-Optimization-on-Relaxed-Indicator-Matrix-Manifold
原文摘要 · Abstract (English)
The indicator matrix plays an important role in machine learning, but optimizing it is an NP-hard problem. We propose a new relaxation of the indicator matrix and prove that this relaxation forms a manifold, which we call the Relaxed Indicator Matrix Manifold (RIM manifold). Based on Riemannian geometry, we develop a Riemannian toolbox for optimization on the RIM manifold. Specifically, we provide several methods of Retraction, including a fast Retraction method to obtain geodesics. We point out that the RIM manifold is a generalization of the double stochastic manifold, and it is much faster than existing methods on the double stochastic manifold, which has a complexity of \( \mathcal{O}(n^3) \), while RIM manifold optimization is \( \mathcal{O}(n) \) and often yields better results. We conducted extensive experiments, including image denoising, with millions of variables to support our conclusion, and applied the RIM manifold to Ratio Cut, we provide a rigorous convergence proof and achieve clustering results that outperform the state-of-the-art methods. Our Code in \href{https://github.com/Yuan-Jinghui/Riemannian-Optimization-on-Relaxed-Indicator-Matrix-Manifold}{here}.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。