Category Archives: Other Mathematical Topics

Generalized Power Method for SO(2) Synchronization

More great news, this time about Open Problem 10.1. of Ten Lectures and Forty-Two Open Problems in the Mathematics of Data Science: Nicolas Boumal (who has contributed to this blog!) has made significant progress on this problem on his new paper.

Continue reading Generalized Power Method for SO(2) Synchronization

Courant Institute of Mathematical Sciences

Finally, I am no longer in the job market! I am excited to announce that I will join the Courant Institute of Mathematical Sciences as an Assistant Professor in the Department of Mathematics with a joint appointment in the Center for Data Science!

I will join Courant in the Summer of 2016, until then I am spending a year in the Department of Mathematics at MIT as an Instructor of Applied Mathematics.

Warm thanks to all the other departments that hosted me this Spring and all of the people that helped me enjoy each and every visit, rendering my final decision extremely difficult! I had an amazing time, albeit completely exhausting.

The 4M-4 conjecture is false!

Cynthia Vinzant just disproved part (a) of the {4M-4} conjecture, see here!

We posed the {4M-4} conjecture two years ago, and there was even a monetary motivation for it! I will not go into details regarding the conjecture, you can read more about it either on a previous blog post of mine or a post of Dustin Mixon. In a nutshell it tries to predict how many phaseless measurements are needed to identify a complex vector of M dimensions. The conjecture was that (a) {4M-4} measurements are always needed and (b) {4M-4} measurements suffice (as long as sufficiently generic).

Continue reading The 4M-4 conjecture is false!

Tightness of the Angular Synchronization SDP relaxation and rank recovery

A few weeks ago, Nicolas, Amit, and myself uploaded our new paper entitled “Tightness of the maximum likelihood semidefinite relaxation for angular synchronization”. I am quite excited about this one as it is the first instance for which we were able to establish a rank recovery type of result! I will briefly explain the main result, its motivation, and describe some of the main ideas behind the proof.

Continue reading Tightness of the Angular Synchronization SDP relaxation and rank recovery

Lecture on Semidefinite Relaxation for Community Detection

Later today I am giving a lecture in IMPA, Brazil . It is part of a special course on Randomness, Matrices and High Dimensional Problems (given together with Roberto Oliveira). Below are the notes for today’s lecture. See here for a printer friendly version. The content is based on a result in here.

1. The problem we will focus on

Let {n} be an even positive integer. Given two sets of {\frac{n}2} nodes consider the following random graph {G}: For each pair {(i,j)} of nodes, {(i,j)} is an edge of {G} with probability {p} if {i} and {j} are in the same set and {q} if they are in different sets. Each edge is drawn independently and {p>q}.

(Think nodes as fans of Fluminense and Flamengo and edges representing friendships, in this model, fans of the same club are more likely to be friends)

For which values of {p} and {q} can we recover the partition, with an efficient algorithm, from only looking at the graph {G} (with high probability)?

Continue reading Lecture on Semidefinite Relaxation for Community Detection

Conditional Restricted Isometries

We have finally made (conditional) progress on the Paley ETF conjecture! Joel, Dustin, and I just uploaded our paper “A conditional construction of restricted isometries” to the arxiv. The conjecture states that a particularly simple deterministic construction, the Paley ETF (see below), satisfies the restricted isometry property past the squareroot bottleneck, we were able to establish this conditional on a folklore number theory conjecture.

Continue reading Conditional Restricted Isometries