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.