analiza aiqbench
This paper presents a novel algorithmic extension of the Marcus theorem to enable efficient learning of sparse, doubly stochastic similarity graphs for clustering tasks. By integrating rank constraints and optimal transport theory, the proposed ANCMM method addresses key computational challenges in graph-based machine learning without relying on quantum mechanisms. The work advances theoretical foundations for scalable unsupervised learning but remains firmly within classical machine learning research.
Doubly Stochastic Adaptive Neighbors Clustering via the Marcus Mapping
arXiv:2408.02932v3 Announce Type: replace Abstract: Clustering is a fundamental task in machine learning and data science, and similarity graph-based clustering is an important approach within this domain. Doubly stochastic symmetric similarity graphs provide numerous benefits for clustering problems and downstream tasks, yet learning such graphs remains a significant challenge. Marcus theorem states that a strictly positive symmetric matrix can be transformed into a doubly stochastic symmetric matrix by diagonal matrices. However, in clustering, learning sparse matrices is crucial for computational efficiency. We extend Marcus theorem by proposing the Marcus mapping, which indicates that certain sparse matrices can also be transformed into doubly stochastic symmetric matrices via diagonal matrices. Additionally, we introduce rank constraints into the clustering problem and propose the Doubly Stochastic Adaptive Neighbors Clustering algorithm based on the Marcus Mapping (ANCMM). This ensures that the learned graph naturally divides into the desired number of clusters. We validate the effectiveness of our algorithm through extensive comparisons with state-of-the-art algorithms. Finally, we explore the relationship between the Marcus mapping and optimal transport. We prove that the Marcus mapping solves a specific type of optimal transport problem.
Abstract:Clustering is a fundamental task in machine learning and data science, and similarity graph-based clustering is an important approach within this domain. Doubly stochastic symmetric similarity graphs provide numerous benefits for clustering problems and downstream tasks, yet learning such graphs remains a significant challenge. Marcus theorem states that a strictly positive symmetric matrix can be transformed into a doubly stochastic symmetric matrix by diagonal matrices. However, in clustering, learning sparse matrices is crucial for computational efficiency. We extend Marcus theorem by proposing the Marcus mapping, which indicates that certain sparse matrices can also be transformed into doubly stochastic symmetric matrices via diagonal matrices. Additionally, we introduce rank constraints into the clustering problem and propose the Doubly Stochastic Adaptive Neighbors Clustering algorithm based on the Marcus Mapping (ANCMM). This ensures that the learned graph naturally divides into the desired number of clusters. We validate the effectiveness of our algorithm through extensive comparisons with state-of-the-art algorithms. Finally, we explore the relationship between the Marcus mapping and optimal transport. We prove that the Marcus mapping solves a specific type of optimal transport problem.
Machine Learning (cs.LG); Artificial Intelligence (cs.AI)
arXiv:2408.02932 [cs.LG]
(or arXiv:2408.02932v3 [cs.LG] for this version)
https://doi.org/10.48550/arXiv.2408.02932 Focus to learn more arXiv-issued DOI via DataCite
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
Text integral sub licența deschisă a publicației · 275 cuvinte
Subiecte conexe
From Vector Search to Agentic RAG: Building an Enterprise Research Analyst with hipVS
AMD · 15 iul. 2026
Running Variational Quantum Eigensolver with Qiskit Aer on AMD Instinct
AMD · 29 mai 2026
KnowledgeForge: mining gold from the ITSM ticket graveyard
AWS · 19 aug. 2026
PIRAMID: Progress and Plans
LessWrong · 27 iul. 2026