Authors: Stošić, Marko 
Marques, Manuel
Costeira, João Paulo
Title: Convex solution of a permutation problem
Journal: Linear Algebra and Its Applications
Volume: 434
Issue: 1
First page: 361
Last page: 369
Issue Date: 1-Jan-2011
Rank: M22
ISSN: 0024-3795
DOI: 10.1016/j.laa.2010.08.028
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.
Keywords: Convex optimization | Doubly-stochastic matrices | Permutation | Perron-Frobenius theorem
Publisher: Elsevier
Project: FCT project PRINTART PTDC/EEA - CRO/098822/2008

Show full item record


checked on Jun 19, 2024

Page view(s)

checked on May 9, 2024

Google ScholarTM




Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.