The rank recovery problem

Yuehaw Khoo, Amit Singer, and myself just uploaded an open problem note to the arxiv entitled “Open problem: Tightness of maximum likelihood semidefinite relaxations”. This note is about a problem/conjecture that I think is really interesting and would love to hear your thoughts on. The note is already rather short (3 pages) but I will try to give an even more brief (and informal) description below.

A few blog posts ago I talked about how to build dual certificates to show that a certain semidefinite relaxation gives exact recovery for a specific problem, called synchronization, that amounts to recover labels of the vertices of a graph given pairwise measurements on the edges that correspond to noisy products between the labels of the nodes.

Essentially, these relaxation work is by first formulating a minimization problem (whose optimum solution is usually the Maximum Likelihood Estimator) that is too hard to solve and to then consider a convex relaxation of that problem. Meaning, to extend the set of feasible solutions of the problem to a (nice) convex set, where we can use the power of convex optimization. In order for the relaxation to provide exact recovery, two things must happen: (A) The ground truth (planted solution) is the minimizer of the original hard problem and (B) the optimum solution of the relaxed problem belongs to the smaller feasible set of the original problem. Interestingly, in many applications, we have observed that (B) has a tendency to happen even in regimes where (A) does not hold, meaning that the relaxation is computing the MLE. However, to the best of my knowledge there is not rigorous understanding of this phenomenon. Note that as we don’t have a way of explicitly describing the optimizer, as it is not the ground truth, dual certificate arguments become very difficult to carry out. The challenge posed consists exactly of understanding this behavior.

In order to illustrate the problem I am going to quickly describe the generalized Procrustes problem: There is an unknown underlying point cloud of points in , (where columns of represent the coordinates of the points) and unknown orthogonal transformations in , satisfying . We are given noisy measurements of the form \(A_i = O_iA + \sigma \eta\), with and is a matrix with i.i.d. entries. To recover the rotations (and then by rotating back and averaging) we interested in minimizing (this is essentially equivalent to an MLE):

which is an intractable problem in general (note that it has a non convex and exponentially large search space).

Let us rewrite the problem: has the same solution as maximizing which, by taking and with blocks , is equivalent to

A very natural semidefinite relaxation is obtained by simply dropping the non-convex rank constraint, giving the following Semidefinite Programming (which can be solved efficiently)

(Note how similar this problem is to Synchronization, when ).

The issue is that, for , the nature of~(1) together with the continuous nature of the orthogonal transformations variables will make exact recovery under noise impossible, even if we solved~(2), this means that (A) never happens. Remarkably we observe that, even then, the optimum point of the relaxation~(3) is a rank solution, which means that it is a feasible solution to~(2), meaning that (B) happens, we call this rank recovery. Based on these observations we conjecture that (B) happens with high probability below a certain level of noise. You can see suggestive numerical experiments in the note.

We used the generalized Procrustes to illustrate the phenomenon but the truth is that it was observed in many different problems: In the multireference alignment problem, in the global registration problem by , and in camera motion estimation by, etc. Yet, to the best of my knowledge, there is no theoretical understanding of this rank recoveryphenomenon. It would be great to understand this phenomenon for all these problems!

Advertisement