Riemannian Optimization on Relaxed Indicator Matrix Manifold
This work addresses a fundamental optimization challenge in machine learning, particularly for tasks like clustering and image denoising, with incremental improvements in efficiency and performance.
The paper tackles the NP-hard problem of optimizing indicator matrices by proposing a new relaxation that forms a manifold, called the Relaxed Indicator Matrix Manifold (RIM manifold), and develops Riemannian optimization tools for it, achieving faster complexity (O(n) vs. O(n^3)) and better clustering results than state-of-the-art methods.
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}.