Convex solution of a permutation problem

✍ Scribed by Marko Stošić; Manuel Marques; João Paulo Costeira

• Publisher: Elsevier Science
• Year: 2011
• Tongue: English
• Weight: 164 KB
• Volume: 434
• Category: Article
• ISSN: 0024-3795
• DOI: 10.1016/j.laa.2010.08.028

✦ Synopsis

In this paper, we show that a problem of finding a permuted version of k vectors from R N 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 R k into the another one. Solutions to these problems have a wide set of applications in Engineering and Computer Science.