Non-Negative Spherical Relaxations for Universe-Free Multi-Matching and
  Clustering
Johan Thunberg Florian Bernard
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).