Graduate Student / Postdoc Seminar

An Introduction to Compressed Sensing

Speaker: Rachel Ward

Location: Warren Weaver Hall 1302

Date: Friday, March 26, 2010, 1 p.m.


We know from linear algebra that there are infinitely many solutions x to equations of the form y = Ax if the system is under determined (that is, if A has more columns than rows). However, for many under determined systems, if the sparsest solution x* (or vector having the fewest nonzero elements) is sufficiently sparse, than x* will also have the smallest l1 norm among all infinity many solutions, that is

x* = arg min || z ||_1 subject to Az = y,

and the sparsest solution x* can then be efficiently recovered. The emerging area of compressed sensing is based on this simple phenomenon. Because many real-word signals are naturally sparse or approximately sparse, compressed sensing translates into new approaches for efficient data acquisition and compression.