March 26:  Rachel Ward, CIMS

An introduction to compressed sensing
  

  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.