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

Want to cluster a point cloud? Relax, no need to round!

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.

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  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:

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.

Exact Recovery in the Stochastic Block Model

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.

The rank recovery problem

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.

Boolean inverse problems on graphs and community detection

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

Online math talks

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.

A conversation with Hau-Tieng Wu: Alternating Projections in Phase Retrieval

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.

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

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 non-negative variance values that sum to , consider a random matrix whose entries are independent gaussians with mean zero and variance equal to . For which choice of is the expected value of the average singular value of that matrix maximized?