Convex solution of a permutation problem

Abstract

In this paper, we show that a problem of finding a permuted version of k vectors from RN such that they belong to a prescribed rank r subset, can be solved by convex optimization. We prove that under certain generic conditions, the wanted permutation matrix is unique in the convex set of doubly-stochastic matrices. In particular, this implies a solution of the classical correspondence problem of finding a permutation that transforms one collection of points in Rk into the another one. Solutions to these problems have a wide set of applications in Engineering and Computer Science.