Top banner   The Best Bits  A new technology called compressive
sensing slims down data at the source  Brian Hayes     Signals
and Samples           Vectors and Coins  Unknown sparse vector
to randomly selected subsetsClick to Enlarge ImageIn my efforts
to understand recent work on compressive sensing, I have found
it helpful to set aside all the messy details of sound waves and
photons, reducing the process to its mathematical essentials.
Imagine that the signal arrives at the sensor already in
numerical form; it is a vector, a sequence of N numbers. We are
assured that this signal vector is sparse: Only k of the
elements are nonzero. But we know nothing about where those k
elements lie or what their values are. Our task is to determine
the positions and values of the nonzero elements with as few
measurements as possible.  In this abstract and simplified
version of the sensing process, “making a measurement” means
selecting some subset of the signal elements and determining
their total value. If the subset h