ChapterZero

I’ve been studying (nonasymptotic) random matrix theory from Vershynin’s lecture notes, which are pretty awesome despite the typos and at least one flawed argument. After just the first three lectures, I was able to almost construct a nice proof of the Johnson-Lindenstrauss lemma — there was one detail that eluded me.

The techniques used are simple:

• Markov’s inequality in its various guises (especially as the “Laplace transform method”);
• the interchangeability of tail bounds, moment bounds, and existence of characteristic functions;
• union bounds;
• concentration of measure on the sphere and in gaussian space;
• and, the most sophisticated (if you take the isoperimetric arguments that give you concentration of measure as givens), chaining arguments that exploit the link between metric spaces and the deviations of random variables attached to points in the spaces.

If you’re interested in seeing how some of those magical ‘with high probability’ results are derived, I strongly recommend those notes. In fact, now that I’ve seen some of these types of results, a little bit of the mystery of Vapnik’s results linking training error to overall risk using the VC dimension has evaporated– it seems like the type of result you could get using these techniques.

Overall, the magic of these methods is two-fold: first, that you can get any practical results from Markov’s inequality, and second, that concentration of measure exists. It’s fascinating and beautiful stuff!

As a concrete example of these principles in application, here’s a problem I’m working on today:

Let be an random gaussian matrix. Show that has the restricted isometry property of order , with , when

The RIP is useful in compressed sensing applications, where it says that will act as an almost-isometry on vectors that are sparse.