Compressed sensing refers to research in signal processing that allows fast, efficient dimension reduction, and to research in high dimensional geometry and analysis that has produced methods for getting good reconstructions from far fewer measurements than traditionally believed necessary. Recent results from our team promise to redefine the state-of-the-art further. We have developed the means, using discrete, nonconvex methods, to generate a representation of the data that is almost optimally sparse — close to the theoretical information content of the signal. 1

Universal Dimension Reduction

New signal processing research has given rise to methods for doing fast, efficient dimension reduction.

• valuable for real-time processing (e.g. video at frame speed), or processing large volumes of data (e.g. hyperspectral data, with millions of pixels with hundreds of (mostly redundant) dimensions each)
• like a "stochastic Fourier transform":
  • like a Fourier transform, it need not be adapted to the data, and is information preserving
  • unlike a Fourier transform, almost all signals can be well-represented with greatly reduced dimensions; the stochastic analog of being "bandlimited" is a very general phenomenon.
• information preservation comes with a constant factor of the most expensive, data customized, nonlinear dimension reduction
• provably preserves both linear and nonlinear geometry of the data (manifold properties)
  • provably preserves class separation, for classification/detection applications
  • data can be reconstructed from the reduced version (doing so efficiently is an area undergoing research)

Inversion of Severely Undersampled Data

New research in high dimensional geometry and analysis has produced methods for getting good reconstructions from far fewer measurements than traditionally believed necessary.

• much like the inverse of the data reduction method
• applies to data that is compressible in some way
• measurements do not need to know the manner of compressibility
• not applicable to all measurements; a good model is those measurements that would be information preserving if there were more of them
• example: inverting CT radiography with a handful of projection angles. Having all angles would allow perfect reconstruction. For most data, a handlful of angles suffice.

Links

Exact recontstructions from surprisingly little data

Exact reconstruction of sparse signals via nonconvex minimization

Nonconvex compressed sensing and error correcton

Slides discussing this work