A relaxation-based approach for the orthogonal Procrustes problem with data uncertainties

The orthogonal Procrustes problem (OPP) deals with matrix approximations. The solution of this problem gives an orthogonal matrix to best transform one data matrix to another, in a Frobenius norm sense. In this work, we use semidefinite relaxation (SDR) to find the solutions of different OPP formulations. For the standard problem formulation, this approach yields an exact solution, i.e. no relaxation gap. We also address uncertainties in the data matrices and formulate a min-max robust problem. The robust problem, being non-convex, turns out to be a difficult optimization problem; however, it is relatively straight forward to approximate it into a convex optimization problem using SDR. Our preliminary results on robust problem show that the solution of the relaxed uncertain problem does not guarantee zero relaxation gap, and as a result, we cannot always find a solution, which satisfies the orthogonality constraint. In such cases we use orthogonalization, which gives the nearest orthogonal matrix from the SDR based solution. All these relaxed formulations, can be easily converted into a semidefinite program (SDP), for which polynomial time efficient algorithms exists. For the nominal problems, the presented approach may not be computationally efficient than other existing methods. In this work, our main contribution is to demonstrate that the SDR approach provides a unified framework to solve not only the standard OPP but can also solve the problems with uncertainties in the data matrices, which other existing approaches cannot handle.