L₂ optimal oracles and compression strategies for semiorthogonal wavelets
Markus H. Groß · Repository for Publications and Research Data (ETH Zurich) · 1996
The following paper discusses the problem of optimal coefficient rejection for approximations with semiorthogonal wavelets. A rejection strategy, a so-called oracle, computes the significance of an individual wavelet coefficient and is essential for lossy compression schemes. The oracles proposed in this paper are based on the L2 norm of the underlying functional space. The report starts with an error analysis in semiorthogonal settings and presents a scheme to compute the fractional energy in each complement space of a given iteration m. However, as opposed to orthogonal settings the mini mization of the overall approximation error while rejecting K out of N wavelets cannot be solved by sorting of the coefficients. Moreover, geometric interpretations of this global optimization task relate to common combinatorial problems of linear algebra and computational geometry. As a result, we propose a greedy construction scheme for an L2 oracle, which computes the conditional significance of individual wavelet coefficients and which operates in quadratic time. The compression strategy is first derived for 1D functions and extended to 2D nonstandard tensor product functions. Some results on real world data sets compare the oracle with standard rejection schemes for orthogonal bases.