Category Archives: Approximation Algorithms

The Lowner-Heinz Theorem and a simple result that should have a simpler proof

Approximation Algorithms, Other Mathematical Topics

A few months ago, while trying to show that the analysis in this paper is optimal (I discussed the paper in a past post), I was faced with the following question:

Given {d} non-negative variance values {v_1,\dots,v_d} that sum to {d}, consider a {d\times d} random matrix whose entries {(i,j)} are independent gaussians with mean zero and variance equal to {v_j}. For which choice of {v_1,\dots,v_d} is the expected value of the average singular value of that matrix maximized?

Continue reading The Lowner-Heinz Theorem and a simple result that should have a simpler proof →

Advertisements

Guest post by Andy Zhu: Alignment and Unique Games

Approximation Algorithms, Other Mathematical Topics

Happy holidays! Afonso asked me a while back to write a guest blog post, and I figured this would make a decent Christmas gift. Just to quickly introduce myself, I did some undergraduate mathematical research at Princeton University with Afonso. Today’s post is on some findings in this paper (to appear in the ITCS 2014 conference proceedings), which is joint work with Afonso, Amit Singer, and Moses Charikar from Princeton.

To align a pair of rotated images on the disc {D^2}, one simply measure the similarity of different rotations of the images and choose the best one (say cross-correlation in signal space, or phase correlation in frequency space). How about multiple noisy, rotated images? For a fixed noise distribution and sufficiently many observations, we certainly expect to be able to recover the underlying template. The main difficulty is that nothing is known about the rotations or the underlying image. We describe an approach to this multiple observation alignment problem using theory developed for the Unique Games problem.

Continue reading Guest post by Andy Zhu: Alignment and Unique Games →

The little Grothendieck problem over O(d)

Approximation Algorithms, Optimization

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 {n} point clouds in {\mathbb{R}^d} of {k} points each, the generalized orthogonal Procrustes problem consists of finding {n} orthogonal transformations that best simultaneously align the point clouds. If the points are represented as the columns of matrices {A_1,\dots,A_n}, where {A_i \in \mathbb{R}^{d\times k}} then the orthogonal Procrustes problem consists of solving

\displaystyle \min_{O_1,.. .,O_n \in O(d)} \sum_{i,j=1}^n ||O_i^T A_i - O_j^T A_j||_F^2. \ \ \ \ \ (1)

Since {||O_i^T A_i - O_j^T A_j||_F^2 = \|A_i\|_F^2+\|A_j\|_F^2 - 2\mathrm{tr}\left( (A_iA_j^T)^T O_i O_j^T \right)}, (1) has the same solution as the complementary version of the problem

\displaystyle \max_4{O_1,.. .,O_n \in O(d)} \sum_{i,j=1}^n \mathrm{tr}\left( C_{ij}^T O_i O_j^T \right), \ \ \ \ \ (2)

where {C\in\mathbb{R}^{dn\times dn}} has {d\times d} blocks given by {C_{ij} = A_iA_j^T}. Note that {C} is positive semidefinite.

In fact, we will focus on problems of the form (2), for any positive definite {C\in\mathbb{R}^{dn\times dn}} (which encodes a few other problems, see more here).

Continue reading The little Grothendieck problem over O(d) →

How to build a dual certificate for Synchronization over Z_2

Approximation Algorithms

A couple of weeks ago I gave a talk at PACM Graduate Student Seminar where I showed a neat simple proof for exact recovery of \mathbb{Z}_2 Synchronization on the presence of random outliers. Although this particular argument is not available in the literature (yet – it will appear as part of a future publication, keep an eye on this blog!), the result has been shown before by Lanhui and Amit with a different technique.

Synchronization over \mathbf{\mathbb{Z}_2} on a complete graph

Recover, up to a global sign, g_1,\dots,g_n\in\mathbb{Z}_2, given noisy \mathbb{Z}_2 relative measurements \rho_{ij}\approx g_ig_j^{-1}.

The problem is essentially the same as described in my last post with the difference that it’s over \mathbb{Z}_2 and not SO(2).  However, while in the Cheeger inequality for the Connection Laplacian paper and post we showed stability in the presence of adversarial noise, here we will show that if the noise is random one can achieve, with high probability, exact recovery.

Continue reading How to build a dual certificate for Synchronization over Z_2 →