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.
Continue reading Norm of random matrices with independent entries
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.
Continue reading World Cup and coupon… Panini stickers collecting
Emmanuel Abbe, Georgina Hall, and myself just uploaded a paper on exact recovery in the stochastic block model (SBM), this post will be about this result.
The stochastic block model (SBM) with two communities (or equivalently the planted partition model) is perhaps the simplest model of random graph exhibiting a cluster behavior. Here we’ll look at the very simple form of the model where the graph has two equally sized clusters and vertices connect with probability within clusters and across clusters.
Continue reading Exact Recovery in the Stochastic Block Model
Yuehaw Khoo, Amit Singer, and myself just uploaded an open problem note to the arxiv entitled “Open problem: Tightness of maximum likelihood semidefinite relaxations”. This note is about a problem/conjecture that I think is really interesting and would love to hear your thoughts on. The note is already rather short (3 pages) but I will try to give an even more brief (and informal) description below.
Continue reading The rank recovery problem
Last week I gave a talk at the CISS 2014 conference here in Princeton about a new paper with Emmanuel Abbe, Annina Bracher, and Amit Singer. I thought it would be an excellent opportunity to talk about this problem in the blog.
The problem is very simple, given a graph and unknown Boolean variables on the vertices we observe edge-variables given by, for ,
where are iid random noise terms satisfying
Continue reading Boolean inverse problems on graphs and community detection
Today I am going to write about online math talks, possibly the least technical post I have written on this blog (excluding maybe this one). The other day I realized that there is a huge number of great math talks available online (on http://www.youtube.com/ , http://videolectures.net/ , and other websites) and that I rarely watch one. One of the reasons might be that these talks are not always easy to find and I am rarely suggested an online talk (unlike normal seminars, which all of us get emails about all the time). So I thought it would be really nice to make a list of interesting math talks that I have watched or am wanting to watch in the near future. Doing it on a blog post where I can also ask for the readers to comment suggesting talks, seems like the perfect solution. So below I am listing a few talks that I think are interesting (of course this is a bit biased to my interests) and I plan to edit with more as I come across them. Don’t hesitate in commenting with suggestions and I’ll also add them to the list.
Continue reading Online math talks
A few days ago Hau-tieng Wu, a colleague from Princeton that is now in Stanford, told me about an exciting new result of his in Phase Retrieval, he and his collaborators were able to show the convergence, to a global solution, of the Alternating Projections algorithm under very general conditions.
Given how difficult it seems to give good theoretical guarantees to the Alternating projection method, I was pretty excited with the news.
To put in prospective, alternative projections (also known, in a particular case, as Gerchberg-Saxton) was proposed over 40 years ago and it seems to be the method of choice for practitioners. However, it seemed to lack theoretical guarantees until recently. To the best of my knowledge, the only known guarantees for convergence of methods of this sort is, for Gaussian measurements this paper, and the results that are going to be discussed below.
Continue reading A conversation with Hau-Tieng Wu: Alternating Projections in Phase Retrieval