mlsanityData to 14 Oct 2026

Riemannian Optimization on Relaxed Indicator Matrix Manifold

arXiv 2503.20505 ↗First posted 26 Mar 2025cs.LG stat.MLcited by 5

Not on the map. Why?

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.

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

50 of 101 references.

References · 50

  1. 2013Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distancescited by 2,316
  2. 2022Self-Supervised Transformers for Unsupervised Object Discovery using Normalized Cutcited by 167
  3. 2020Graph Clustering with Graph Neural Networkscited by 163
  4. 2022Contrastive and Non-Contrastive Self-Supervised Learning Recover Global and Local Spectral Embedding Methodscited by 149
  5. 2020Geoopt: Riemannian Optimization in PyTorchcited by 114
  6. 2013Manopt, a Matlab toolbox for optimization on manifoldscited by 113
  7. 2021Combinatorial Optimization with Physics-Inspired Graph Neural Networkscited by 108
  8. 2016Pymanopt: A Python Toolbox for Optimization on Manifolds using Automatic Differentiationcited by 94
  9. 2023On Penalty-based Bilevel Gradient Descent Methodcited by 87
  10. 2020Efficient Riemannian Optimization on the Stiefel Manifold via the Cayley Transformcited by 80
  11. 2022Deep Clustering: A Comprehensive Surveycited by 78
  12. 2015Fast low-rank estimation by projected gradient descent: General statistical and algorithmic guaranteescited by 70
38 more
  1. 2021Skyformer: Remodel Self-Attention with Gaussian Kernel and Nystr"om Methodcited by 63
  2. 2021Graph Contrastive Clusteringcited by 61
  3. 2022DeepDPM: Deep Clustering With an Unknown Number of Clusterscited by 52
  4. 2018Averaging Stochastic Gradient Descent on Riemannian Manifoldscited by 39
  5. 2022The Machine Learning for Combinatorial Optimization Competition (ML4CO): Results and Insightscited by 39
  6. 2019A Brief Introduction to Manifold Optimizationcited by 35
  7. 2019Escaping from saddle points on Riemannian manifoldscited by 33
  8. 2021Moving Object Detection for Event-based vision using Graph Spectral Clusteringcited by 28
  9. 2017Riemannian Optimization via Frank-Wolfe Methodscited by 21
  10. 2023A Survey of Geometric Optimization for Deep Learning: From Euclidean Space to Riemannian Manifoldcited by 21
  11. 2018McTorch, a manifold optimization library for deep learningcited by 16
  12. 2013A Framework of Constraint Preserving Update Schemes for Optimization on Stiefel Manifoldcited by 13
  13. 2018Geodesic Convex Optimization: Differentiation on Manifolds, Geodesics, and Convexitycited by 13
  14. 2022A Tighter Analysis of Spectral Clustering, and Beyondcited by 13
  15. 2017Dykstra's Algorithm, ADMM, and Coordinate Descent: Connections, Insights, and Extensionscited by 12
  16. 2018Manifold Optimization Over the Set of Doubly Stochastic Matrices: A Second-Order Geometrycited by 12
  17. 2021Riemannian conjugate gradient methods: General framework and specific algorithms with convergence analysescited by 12
  18. 2015Heterogeneous Tensor Decomposition for Clustering via Manifold Optimizationcited by 10
  19. 2021A Simple Approach to Automated Spectral Clusteringcited by 10
  20. 2022First-Order Algorithms for Min-Max Optimization in Geodesic Metric Spacescited by 10
  21. 2020Distributionally Robust Weighted k-Nearest Neighborscited by 9
  22. 2021Manifold optimization for non-linear optimal transport problemscited by 8
  23. 2022CCCP is Frank-Wolfe in disguisecited by 8
  24. 2021Closed-form geodesics and trust-region method to calculate Riemannian logarithms on Stiefel and its quotient manifoldscited by 7
  25. 2024Nonnegative Matrix Factorization in Dimensionality Reduction: A Surveycited by 7
  26. 2024Revisiting Self-Supervised Heterogeneous Graph Learning from Spectral Clustering Perspectivecited by 7
  27. 2024Double-Bounded Optimal Transport for Advanced Clustering and Classificationcited by 6
  28. 2024A Margin-Maximizing Fine-Grained Ensemble Methodcited by 6
  29. 2021tensorflow-riemopt: A Library for Optimization on Riemannian Manifoldscited by 5
  30. 2023Fast and Simple Spectral Clustering in Theory and Practicecited by 5
  31. 2024Doubly Stochastic Adaptive Neighbors Clustering via the Marcus Mappingcited by 4
  32. 2024Achieving More with Less: A Tensor-Optimization-Powered Ensemble Methodcited by 4
  33. 2019Riemannian optimization with a preconditioning scheme on the generalized Stiefel manifoldcited by 2
  34. 2021Memory-Efficient Approximation Algorithms for Max-k-Cut and Correlation Clusteringcited by 2
  35. 2024Label Learning Method Based on Tensor Projectioncited by 2
  36. 2023Cut-matching Games for Generalized Hypergraph Ratio Cutscited by 1
  37. 2024Graph Cuts with Arbitrary Size Constraints Through Optimal Transportcited by 1
  38. 2025Double-Bounded Nonlinear Optimal Transport for Size Constrained Min Cut Clusterincited by 1

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2025: 2; 2026: 3.

5 papers.

  1. 2026Nora: Normalized Orthogonal Row Alignment for Scalable Matrix Optimizercited by 5
  2. 2025In-situ Autoguidance: Eliciting Self-Correction in Diffusion Modelscited by 2
  3. 2026DASH-KV: Accelerating Long-Context LLM Inference via Asymmetric KV Cache Hashingcited by 1
  4. 2025Hadamard-Riemannian Optimization for Margin-Variance Ensemblecited by 0
  5. 2026Learning with Bilevel-Minimax Optimization for Efficient and Reliable Transfer Attackscited by 0