Ronald DeVore

Title: Decoders for Compressed Sensing

Abstract: In compressed sensing, we encode a discrete signal $x\in \R^N$ by the vector $y=\Phi x$ where $\Phi$ is a suitably chosen $n\times N$ matrix with $n<<N$.  The vector $x$ is underdetermined by $y$ and so decoding $y$ is a typical inverse problem. We shall discuss various ways of decoding $y$ including $\ell_1$ minimization and greedy algorithms. We shall discuss the performance of encoder-decoder pairs in terms of accuracy for a given computational budget.