Today’s post is about a recent paper of mine with Christopher Kennedy and Amit Singer entitled “Approximating the Little Grothendieck Problem over the Orthogonal and Unitary Groups”. Earlier this week, we finished a major revision to the paper (even the title was slightly changed) and I decided to take the opportunity to blog about it (in a previous blog post I blogged about an open problem that is raised by this work).
— Generalized orthogonal Procrustes Problem —
In this post I will motivate the problem using the orthogonal Procrustes problem: Given point clouds in of points each, the generalized orthogonal Procrustes problem consists of finding orthogonal transformations that best simultaneously align the point clouds. If the points are represented as the columns of matrices , where then the orthogonal Procrustes problem consists of solving
Since , (1) has the same solution as the complementary version of the problem
where has blocks given by . Note that is positive semidefinite.
— The little Grothendieck problem () —
where is a positive semidefinite matrix matrix.
Problem (3) is known to be NP-hard (if is a Laplacian matrix of a graph then (3) reduces to the Max-Cut problem). I briefly discribed a semidefinite relaxation for (3) proposed by Goemans and Williamson in the context of the Max-Cut problem:
Note that (4) is equivalent to the semidefinite program:
In the same blog post I explained how a simple rounding technique (to compute a solution to (3) from a solution to (4)) is guaranteed to produce a solution whose objective value is, in expectation, at least of the optimum. It turns out that one can show an approximation ratio of (instead of 0.878) for the general case using the same relaxation. This implies, in particular, that the value of (3) can never be smaller than times the value of (4). Interestingly, this was already known from the influential work of Grothendieck on norms of tensor products of Banach spaces.
— Little Grothendieck problem over the Orthogonal Group —
Just as in the unidimensional case, (6) is equivalent to a semidefinite program:
We propose the following approximation algorithm
Note that the Polar Decomposition can be efficiently computed via the Singular Value Decomposition as .
where is the constant defined in (8).
Moreover, we can also show a matching integrality gap meaning that this constant is optimal. I don’t want to go into this in much detail, but it essentially means that no other algorithm based on this natural semidefinite relaxation can have a better approximation ratio. This does not rule out the existence of a different efficient approximation algorithm that achieves a better ratio but, in these sort of problems, it tends to be the case that achieving better approximation ratios than the natural semidefinite relaxations is hard.
One of the interesting questions raised by this work is the behavior of . This was the subject of a previous blog post and I won’t discuss it much here. In a nutshell, we can give good lower bounds for this constant (that, in particular, show that our approximation ratio is larger than the best previously known, for all dimensions ) and conjecture that it is monotonically increasing with . I find it quite counter-intuitive that problem (2) should be getting easier to approximation as the dimension increases! Perhaps even more strange is that if we do all of the above working in , considering the unitary group , and define the analogous constant it seems to be decreasing with the dimension instead! We discussed this strange phenomenon in this blog post.