ORTHOGONAL TRACE-SUM MAXIMIZATION: TIGHTNESS OF THE SEMIDEFINITE RELAXATION AND GUARANTEE OF LOCALLY OPTIMAL...

Area of Science:

• Optimization Theory
• Linear Algebra
• Numerical Analysis

Background:

• The study addresses an optimization problem involving sums of traces of matrix quadratic forms in semiorthogonal matrices.
• This problem is a generalization of the synchronization of rotations, a key concept in various scientific fields.
• Existing methods face challenges due to the nonconvex nature of the problem.

Purpose of the Study:

• To investigate an optimization problem on the sum of traces of matrix quadratic forms in m semiorthogonal matrices.
• To analyze the effectiveness of semidefinite programming relaxation for solving this nonconvex problem.
• To generalize existing results on phase synchronization to a broader class of problems.

Main Methods:

• Formulation of an optimization problem involving matrix quadratic forms.
• Application of semidefinite programming relaxation.
• Analysis of the problem under an additive noise model with small noise (O(m^1/4)).
• Investigation of global optimality conditions.

Main Results:

• The semidefinite programming relaxation solves the original nonconvex problems exactly with high probability under a small additive noise model.
• The sufficient condition for global optimality is shown to be necessary with high probability under similar small noise conditions.
• These findings extend previous results on phase synchronization.

Conclusions:

• Semidefinite programming relaxation provides an effective method for solving a generalized synchronization of rotations problem.
• The study establishes a theoretical foundation for analyzing nonconvex optimization problems with noise.
• The results contribute to the understanding of global optimality conditions in matrix optimization and generalize phase synchronization theory.