On the minimax mean-squared error of Compressed Sensing

Galen Reeves
Post-doc, Stanford University
Given on: Jan. 18th, 2013


In this talk I will focus on the minimax MSE of compressed sensing -- the minimum is over all possible recovery algorithms and the maximum is over all distributions on a vector obeying a given sparsity constraint. I will show how this quantity can be analyzed in terms of the fixed points a certain scalar estimation problem and discuss connections with robust estimation and the performance of greedy algorithms.

Time permitting, I will also present an alternative method for obtaining uniform upper bounds on the risk and discuss connections with recent phase transitions studied by Wu and Verdu.

This is joint work with David Donoho.