Non-Negative Spherical Relaxations for Universe-Free Multi-Matching and Clustering
This addresses optimization challenges in multi-matching and clustering for computer vision and data analysis, offering an incremental improvement by automating parameter adjustment and simplifying output generation.
The paper tackles the problem of multi-matching and clustering by proposing a non-negative spherical relaxation that avoids fixing the universe size beforehand and eliminates the need for post-processing to obtain binary results, achieving compelling results even compared to methods using ground truth parameters.
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).