Dror Baron - Compression of multi-dimensional functions with discontinuities

Surflet algorithm

Discontinuities in data often provide vital information, and representing these discontinuities sparsely is an important goal for approximation and compression algorithms. We considered an M-dimensional horizon class, in which M-dimensional functions contain a smooth (M-1)-dimensional singularity separating smooth regions. Such a function in M=2 dimensions appears above. We characterized the metric entropy of these signals, and provided multi-scale representations that enable to achieve the metric entropy. Our constructive solutions rely on a hierarchical geometric tiling, where each atom of our tiling dictionary contains polynomial surfaces - and is thus called a surflet. An important insight for compression is that the large number of higher-order coefficients need not take too much coding length, because they can be quantized coarsely. Additionally, coefficients are correlated between scales, and prediction is used to reduce coding length. Slides from a talk I gave on this topic in June 2009 appear here.
Last updated June 2009