Abstract
The indicator matrix plays an important role in machine learning, butoptimizing it is an NP-hard problem. We propose a new relaxation of theindicator matrix and prove that this relaxation forms a manifold, which we callthe Relaxed Indicator Matrix Manifold (RIM manifold). Based on Riemanniangeometry, we develop a Riemannian toolbox for optimization on the RIM manifold.Specifically, we provide several methods of Retraction, including a fastRetraction method to obtain geodesics. We point out that the RIM manifold is ageneralization of the double stochastic manifold, and it is much faster thanexisting 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, includingimage denoising, with millions of variables to support our conclusion, andapplied the RIM manifold to Ratio Cut, we provide a rigorous convergence proofand 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}.