ChapterZero

Yesterday Tropp gave me three problems to work on over the summer. The first one concerns sparse approximation: there’s general interest in finding probabilistic schemes for coming up with a sparse, quantized matrix which approximates a given matrix in some sense; he gave me two papers to read on previous approaches– A Fast Random Sampling Algorithm for Sparsifying Matrices, and Fast Computations of Low-Rank Matrix Approximations– and a preprint of a result he derived which gives a bound on the approximation error for any general scheme. My job is mainly to compare and contrast the performance of these difference schemes and the attendant error bounds, to see for what schemes and properties of his bound is tighter than the others. This will be my main concern for the next couple months.

The second and third are more theoretical. One is to find a bound on the expected Ky Fan k-norm of a standard Gaussian matrix, and the other is to find a bound on the expected value of where is a DFT matrix and are random restrictions to coordinates. Sweet stuff!