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.
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 be an even positive integer. Given two sets of nodes consider the following random graph : For each pair of nodes, is an edge of with probability if and are in the same set and if they are in different sets. Each edge is drawn independently and .
(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 and can we recover the partition, with an efficient algorithm, from only looking at the graph (with high probability)?
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.
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 here, here, 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 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 , however, due to a concentration phenomenon, it is almost always roughly . Unfortunately, random matrix in many applications do not correspond to this simple model.
Pranjal, Moses, Ravishankar, Soledad, Rachel, and myself just uploaded our new paper “Relax, no need to round: Integrality of clustering formulation” to the arxiv and I would like to briefly describe some of the results here.
The problem is remarkably simple to pose: Let be a gaussian random vector in with a known covariance matrix and . Now, for any orthonormal basis of , consider the following random variable: Given a draw of the random vector , consider the norm of the largest projection of on a subspace generated by elements of the basis . The question is:
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.