# 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.

# 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)?

# 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.

# Norm of random matrices with independent entries

A few weeks ago, Ramon van Handel and I uploaded a paper entitled “Sharp non asymptotic bounds on the norm of random matrices with independent entries” to the arxiv. In this blog post, I’ll attempt to describe and motivate the results there.

The main motivation comes from the vast number of applications for bounds on the spectral norm of random matrices, some of which I have described on this blog (see herehere, and here). In many (applied) math problems one needs to control the spectral norm of a certain application-specific random matrix. A common approach, which has found great success, is to introduce randomness in the models and control this quantity on certain random matrices. Perhaps the simplest example of how randomness can help is the spectral norm of an ${n\times n}$ standard Wigner matrix, a symmetric matrix with iid standard gaussian entries. As each entry of the matrix is essentially of constant order the spectral norm of such a matrix can go up to ${\Omega(n)}$, however, due to a concentration phenomenon, it is almost always roughly ${2\sqrt{n}}$. Unfortunately, random matrix in many applications do not correspond to this simple model.

# An interesting problem by Mallat and Zeitouni

Last week, Ramon van Handel showed me a really cool open problem that I want to share with you today. The problem was posed by Stephane Mallat and Ofer Zeitouni in a nice short note available here.

The problem is remarkably simple to pose: Let ${g}$ be a gaussian random vector in ${\mathbb{R}^N}$ with a known covariance matrix ${\Sigma}$ and ${M. Now, for any orthonormal basis ${\mathcal{Q}}$ of ${\mathbb{R}^N}$, consider the following random variable: Given a draw of the random vector ${g}$, consider the ${\ell_2}$ norm of the largest projection of ${g}$ on a subspace generated by ${M}$ elements of the basis ${\mathcal{Q}}$. The question is:

# World Cup and coupon… Panini stickers collecting

The World Cup is under way and Cara and I are collecting World Cup panini stickers. Apparently, Panini stickers were not as popular in he US as they were in Portugal during my childhood – they were giving sticker albums in a soccer match we went to watch and Cara didn’t know what they were! So for those who don’t know, they are collective stickers for the world cup: there is essentially a sticker per player and around 20 players are represented on each team in the world cup, they can be bought in packs of 7 stickers and the objective is to collect all of them (this collection has 639 stickers) to fill the sticker album. We were discussing how many packs we would need to buy (each pack is around a dollar) to complete the collection and decided to actually estimate the numbers – I did it through the coupon collecting estimate and Cara through simulations, it was interesting to see the comparison.