Self-assignment flows for unsupervised data labeling on graphs

• Verfasst von: Zisler, Matthias [VerfasserIn]
• Verfasst von: Zern, Artjom [VerfasserIn]
• Verfasst von: Petra, Stefania [VerfasserIn]
• Verfasst von: Schnörr, Christoph [VerfasserIn]
• Titel: Self-assignment flows for unsupervised data labeling on graphs
• Verf.angabe: Matthias Zisler, Artjom Zern, Stefania Petra, and Christoph Schnörr
• E-Jahr: 2020
• Jahr: July 8, 2020
• Umfang: 44 S.
• Fussnoten: Gesehen am 09.11.2020
• Titel Quelle: Enthalten in: Society for Industrial and Applied MathematicsSIAM journal on imaging sciences
• Ort Quelle: Philadelphia, Pa. : SIAM, 2008
• Jahr Quelle: 2020
• Band/Heft Quelle: 13(2020), 3, Seite 1113-1156
• ISSN Quelle: 1936-4954
• DOI: doi:10.1137/19M1298639
• Datenträger: Online-Ressource
• Sprache: eng
• K10plus-PPN: 1738117979

Abstract

This paper extends the recently introduced assignment flow approach for supervised image labeling to unsupervised scenarios where no labels are given. The resulting self-assignment flow takes a pairwise data affinity matrix as input data and maximizes the correlation with a low-rank matrix that is parametrized by the variables of the assignment flow, which entails an assignment of the data to themselves through the formation of latent labels (feature prototypes). A single user parameter, the neighborhood size for the geometric regularization of assignments, drives the entire process. By smooth geodesic interpolation between different normalizations of self-assignment matrices on the positive definite matrix manifold, a one-parameter family of self-assignment flows is defined. Accordingly, our approach can be characterized from different viewpoints, e.g., as performing spatially regularized, rank-constrained discrete optimal transport, or as computing spatially regularized normalized spectral cuts. Regarding combinatorial optimization, our approach successfully determines completely positive factorizations of self-assignments in large-scale scenarios, subject to spatial regularization. Various experiments, including the unsupervised learning of patch dictionaries using a locally invariant distance function, illustrate the properties of the approach.