Normalized Cuts and Data Clustering via Matrix Fractional Programming
IEEE Transactions on Mobile Computing · 2026 · 1-15
DOI: 10.1109/tmc.2026.3748126 ↗Kurz gefasst
Fachartikel in der Zeitschrift IEEE Transactions on Mobile Computing, 2026. Verfasst von Yannan Chen und 4 weiteren Autor:innen.
Abstract (Originalsprache)
The normalized cut (NCut) problem is a fundamental one in the area of data clustering. Despite its fractional structure, the NCut problem is seldom considered from a fractional programming (FP) perspective in the existing literature. The main reason is that the conventional FP method is inadequate for this problem case: the classical Dinkelbach's transform can only handle a single ratio and hence is limited to the two-class clustering, whereas the multi-class clustering involves multiple ratio terms. This work proposes a novel so-called multidimensional quadratic transform that is capable of dealing with the multi-ratio case; it recasts the NCut problem into a bipartite matching problem---which can be immediately solved by linear search. Furthermore, we explore the connection between the proposed FP method and the minorization-maximization (MM) theory, and in turn characterize the convergence behavior of our algorithm. Finally, we conduct experiments to numerically demonstrate the advantages of the proposed FP-based algorithm in a variety of data clustering and image segmentation tasks.
Zitieren
APA
Chen, Y., Huang, B., Zhao, L., Ding, C., & Shen, K. (2026). Normalized Cuts and Data Clustering via Matrix Fractional Programming. IEEE Transactions on Mobile Computing, 1-15. https://doi.org/10.1109/tmc.2026.3748126
Vancouver
Chen Y, Huang B, Zhao L, Ding C, Shen K. Normalized Cuts and Data Clustering via Matrix Fractional Programming. IEEE Transactions on Mobile Computing. 2026:1-15. doi:10.1109/tmc.2026.3748126
BibTeX
@article{Chen2026,
author = {Chen, Yannan and Huang, Beichen and Zhao, Licheng and Ding, Chris and Shen, Kaiming},
title = {Normalized Cuts and Data Clustering via Matrix Fractional Programming},
journal = {IEEE Transactions on Mobile Computing},
year = {2026},
pages = {1--15},
doi = {10.1109/tmc.2026.3748126}
}
EUVIMED