Dror Baron -
Compression of multi-dimensional functions with discontinuities
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.
-
V. Chandrasekaran,
M. B. Wakin,
D. Baron,
and R. G. Baraniuk,
"Representation and Compression of Multi-Dimensional Piecewise Functions
Using Surflets,"
IEEE Transactions on Information Theory,
vol. 55, No. 1, pp. 374-400, January 2009
(pdf).
-
V. Chandrasekaran,
M. B. Wakin,
D. Baron,
and R. G. Baraniuk,
"Surflets: A Sparse Representation for Multidimensional Functions
Containing Smooth Discontinuities,"
2004 IEEE International Symposium on Information Theory
(ISIT2004), Chicago, IL, June 2004
(pdf).
-
V. Chandrasekaran,
M. B. Wakin,
D. Baron,
and R. G. Baraniuk,
"Compression of Higher Dimensional Functions Containing Smooth
Discontinuities,"
Proceedings of 38th Annual Conference on Information Sciences and
Systems (CISS2004), Princeton, NJ, March 2004
(pdf).
Slides from a talk I gave on this topic in June 2009 appear
here.
Last updated June 2009