# Riemannian Optimization on Relaxed Indicator Matrix Manifold

arXiv: https://arxiv.org/abs/2503.20505 · HTML: https://mlsanity.com/paper/2503.20505/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 50 of its 101 references that are in the map.
- First posted on arXiv 26 Mar 2025.

## Builds on (most cited first, 30 of 50)

- [Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distances](https://mlsanity.com/paper/1306.0895/) (2013)
- [Self-Supervised Transformers for Unsupervised Object Discovery using Normalized Cut](https://mlsanity.com/paper/2202.11539/) (2022)
- [Graph Clustering with Graph Neural Networks](https://mlsanity.com/paper/2006.16904/) (2020)
- [Contrastive and Non-Contrastive Self-Supervised Learning Recover Global and Local Spectral Embedding Methods](https://mlsanity.com/paper/2205.11508/) (2022)
- [Geoopt: Riemannian Optimization in PyTorch](https://mlsanity.com/paper/2005.02819/) (2020)
- [Manopt, a Matlab toolbox for optimization on manifolds](https://mlsanity.com/paper/1308.5200/) (2013)
- [Combinatorial Optimization with Physics-Inspired Graph Neural Networks](https://mlsanity.com/paper/2107.01188/) (2021)
- [Pymanopt: A Python Toolbox for Optimization on Manifolds using Automatic Differentiation](https://mlsanity.com/paper/1603.03236/) (2016)
- [On Penalty-based Bilevel Gradient Descent Method](https://mlsanity.com/paper/2302.05185/) (2023)
- [Efficient Riemannian Optimization on the Stiefel Manifold via the Cayley Transform](https://mlsanity.com/paper/2002.01113/) (2020)
- [Deep Clustering: A Comprehensive Survey](https://mlsanity.com/paper/2210.04142/) (2022)
- [Fast low-rank estimation by projected gradient descent: General statistical and algorithmic guarantees](https://mlsanity.com/paper/1509.03025/) (2015)
- [Skyformer: Remodel Self-Attention with Gaussian Kernel and Nystr"om Method](https://mlsanity.com/paper/2111.00035/) (2021)
- [Graph Contrastive Clustering](https://mlsanity.com/paper/2104.01429/) (2021)
- [DeepDPM: Deep Clustering With an Unknown Number of Clusters](https://mlsanity.com/paper/2203.14309/) (2022)
- [Averaging Stochastic Gradient Descent on Riemannian Manifolds](https://mlsanity.com/paper/1802.09128/) (2018)
- [The Machine Learning for Combinatorial Optimization Competition (ML4CO): Results and Insights](https://mlsanity.com/paper/2203.02433/) (2022)
- [A Brief Introduction to Manifold Optimization](https://mlsanity.com/paper/1906.05450/) (2019)
- [Escaping from saddle points on Riemannian manifolds](https://mlsanity.com/paper/1906.07355/) (2019)
- [Moving Object Detection for Event-based vision using Graph Spectral Clustering](https://mlsanity.com/paper/2109.14979/) (2021)
- [Riemannian Optimization via Frank-Wolfe Methods](https://mlsanity.com/paper/1710.10770/) (2017)
- [A Survey of Geometric Optimization for Deep Learning: From Euclidean Space to Riemannian Manifold](https://mlsanity.com/paper/2302.08210/) (2023)
- [McTorch, a manifold optimization library for deep learning](https://mlsanity.com/paper/1810.01811/) (2018)
- [A Framework of Constraint Preserving Update Schemes for Optimization on Stiefel Manifold](https://mlsanity.com/paper/1301.0172/) (2013)
- [Geodesic Convex Optimization: Differentiation on Manifolds, Geodesics, and Convexity](https://mlsanity.com/paper/1806.06373/) (2018)
- [A Tighter Analysis of Spectral Clustering, and Beyond](https://mlsanity.com/paper/2208.01724/) (2022)
- [Dykstra's Algorithm, ADMM, and Coordinate Descent: Connections, Insights, and Extensions](https://mlsanity.com/paper/1705.04768/) (2017)
- [Manifold Optimization Over the Set of Doubly Stochastic Matrices: A Second-Order Geometry](https://mlsanity.com/paper/1802.02628/) (2018)
- [Riemannian conjugate gradient methods: General framework and specific algorithms with convergence analyses](https://mlsanity.com/paper/2112.02572/) (2021)
- [Heterogeneous Tensor Decomposition for Clustering via Manifold Optimization](https://mlsanity.com/paper/1504.01777/) (2015)

## Built on by (most cited first, 5 of 5)

- [Nora: Normalized Orthogonal Row Alignment for Scalable Matrix Optimizer](https://mlsanity.com/paper/2605.03769/) (2026)
- [In-situ Autoguidance: Eliciting Self-Correction in Diffusion Models](https://mlsanity.com/paper/2510.17136/) (2025)
- [DASH-KV: Accelerating Long-Context LLM Inference via Asymmetric KV Cache Hashing](https://mlsanity.com/paper/2604.19351/) (2026)
- [Hadamard-Riemannian Optimization for Margin-Variance Ensemble](https://mlsanity.com/paper/2509.10189/) (2025)
- [Learning with Bilevel-Minimax Optimization for Efficient and Reliable Transfer Attacks](https://mlsanity.com/paper/2608.11815/) (2026)

## Abstract (arXiv)

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 ( O(n3) ), while RIM manifold optimization is ( 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 hrefhttps://github.com/Yuan-Jinghui/Riemannian-Optimization-on-Relaxed-Indicator-Matrix-Manifoldhere.