Georgia Institute of Technology College of Sciences

In the last 10 years, compressed sensing has arisen as an entirely new area of mathematics, combining ideas from convex programming, random matrices, theoretical computer science and many other fields. Candes (one of the originators of the area) recently spoke about two quite recent and exciting developments, but it might be interesting to revisit the fundamentals, and see where a lot of the ideas in the more recent works have developed. In this talk, I will discuss some of the earlier papers (Candes-Romberg-Tao), define the compressed sensing problem, the key restricted isometry property and how it relates to the Johnson-Lindenstrauss lemma for random projections. I'll also discuss some of the more TCS ideas such as compressed sensing through group testing, and hopefully some of the greedy algorithm ideas as well. Finally, if time allows, I'll draw parallels with other problems, such as matrix completion, phase retrieval etc. The talk will be quite elementary, requiring only a knowledge of linear algebra, and some probability.