Non-negative Spherical Relaxations for Universe-Free Multi-matching and Clustering
(2023) 23nd Scandinavian Conference on Image Analysis, SCIA 2023 In Lecture Notes in Computer Science 13886. p.260-277- Abstract
We propose a novel non-negative spherical relaxation for optimization problems over binary matrices with injectivity constraints, which in particular has applications in multi-matching and clustering. We relax respective binary matrix constraints to the (high-dimensional) non-negative sphere. To optimize our relaxed problem, we use a conditional power iteration method to iteratively improve the objective function, while at same time sweeping over a continuous scalar parameter that is (indirectly) related to the universe size (or number of clusters). Opposed to existing procedures that require to fix the integer universe size before optimization, our method automatically adjusts the analogous continuous parameter. Furthermore, while our... (More)
We propose a novel non-negative spherical relaxation for optimization problems over binary matrices with injectivity constraints, which in particular has applications in multi-matching and clustering. We relax respective binary matrix constraints to the (high-dimensional) non-negative sphere. To optimize our relaxed problem, we use a conditional power iteration method to iteratively improve the objective function, while at same time sweeping over a continuous scalar parameter that is (indirectly) related to the universe size (or number of clusters). Opposed to existing procedures that require to fix the integer universe size before optimization, our method automatically adjusts the analogous continuous parameter. Furthermore, while our approach shares similarities with spectral multi-matching and spectral clustering, our formulation has the strong advantage that we do not rely on additional post-processing procedures to obtain binary results. Our method shows compelling results in various multi-matching and clustering settings, even when compared to methods that use the ground truth universe size (or number of clusters).
(Less)
- author
- Thunberg, Johan LU and Bernard, Florian
- publishing date
- 2023
- type
- Chapter in Book/Report/Conference proceeding
- publication status
- published
- subject
- keywords
- Clustering, Multi-matching, Permutation synchronization, Spectral clustering, Spectral methods
- host publication
- Image Analysis - 23rd Scandinavian Conference, SCIA 2023, Proceedings
- series title
- Lecture Notes in Computer Science
- editor
- Gade, Rikke ; Felsberg, Michael and Kämäräinen, Joni-Kristian
- volume
- 13886
- pages
- 18 pages
- publisher
- Springer Science and Business Media B.V.
- conference name
- 23nd Scandinavian Conference on Image Analysis, SCIA 2023
- conference location
- Lapland, Finland
- conference dates
- 2023-04-18 - 2023-04-21
- external identifiers
-
- scopus:85161392089
- ISSN
- 1611-3349
- 0302-9743
- ISBN
- 9783031314377
- DOI
- 10.1007/978-3-031-31438-4_18
- language
- English
- LU publication?
- no
- additional info
- Publisher Copyright: © 2023, The Author(s), under exclusive license to Springer Nature Switzerland AG.
- id
- 2b87b862-e231-4941-a3e4-fc28949712c9
- date added to LUP
- 2024-09-04 17:52:38
- date last changed
- 2024-09-05 09:25:19
@inproceedings{2b87b862-e231-4941-a3e4-fc28949712c9,
abstract = {{<p>We propose a novel non-negative spherical relaxation for optimization problems over binary matrices with injectivity constraints, which in particular has applications in multi-matching and clustering. We relax respective binary matrix constraints to the (high-dimensional) non-negative sphere. To optimize our relaxed problem, we use a conditional power iteration method to iteratively improve the objective function, while at same time sweeping over a continuous scalar parameter that is (indirectly) related to the universe size (or number of clusters). Opposed to existing procedures that require to fix the integer universe size before optimization, our method automatically adjusts the analogous continuous parameter. Furthermore, while our approach shares similarities with spectral multi-matching and spectral clustering, our formulation has the strong advantage that we do not rely on additional post-processing procedures to obtain binary results. Our method shows compelling results in various multi-matching and clustering settings, even when compared to methods that use the ground truth universe size (or number of clusters).</p>}},
author = {{Thunberg, Johan and Bernard, Florian}},
booktitle = {{Image Analysis - 23rd Scandinavian Conference, SCIA 2023, Proceedings}},
editor = {{Gade, Rikke and Felsberg, Michael and Kämäräinen, Joni-Kristian}},
isbn = {{9783031314377}},
issn = {{1611-3349}},
keywords = {{Clustering; Multi-matching; Permutation synchronization; Spectral clustering; Spectral methods}},
language = {{eng}},
pages = {{260--277}},
publisher = {{Springer Science and Business Media B.V.}},
series = {{Lecture Notes in Computer Science}},
title = {{Non-negative Spherical Relaxations for Universe-Free Multi-matching and Clustering}},
url = {{http://dx.doi.org/10.1007/978-3-031-31438-4_18}},
doi = {{10.1007/978-3-031-31438-4_18}},
volume = {{13886}},
year = {{2023}},
}