Speaker: Dustin Mixon
Title: An invitation to compressed sensing and related problems
Abstract: Compressed sensing emerged a decade ago as a shockingly effective alternative to classical Nyquist-Shannon sampling. The idea is that underdetermined linear systems of the form Ax=b are well-posed provided x exhibits enough known structure, and furthermore, the solution is easy to obtain provided A is drawn at random. For example, if x has many zero entries at unknown locations, then it can be reconstructed by solving a linear program determined by A. The success of compressed sensing has led to numerous follow-up questions, for example (1) how can one select A deterministically, and (2) how can random convex programs be of use to other applications? We will discuss the state of the art for (1) and then investigate k-means clustering as an instance of (2).
Note: This is part of the Invitations to Mathematics lecture series given each year in Autumn and Spring semesters. Pre-candidacy students can sign up for this lecture series by registering for one or two credit hours of Math 6193, class #16988 (with Prof H. Moscovici).
