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 realword signals are naturally sparse or approximately
sparse, compressed sensing translates into new approaches for efficient
data acquisition and compression.
