Unconditional bases and bit-level compression (Q2564044)

In a previous article [Appl. Comput. Harmon. Anal. 1, No. 1, 100-115 (1993; Zbl 0796.62083)] the author gave results showing that an orthogonal basis which is an unconditional basis for a functional class \({\mathcal F}\) furnishes an optimal representation of elements of \({\mathcal F}\) for certain de-noising and compression tasks. Since publication of that article, the author has received several queries which pointed out that the definition of compression in that article was based on counting the number of significant transform domain coefficients which must be retained to get acceptable reconstruction error in transform coding. These queries asked whether results could instead be formulated in terms of the number of bits stored. The purpose of this note is to point out that results analogous to that previous article hold under a model which measures bits encoded. There are two key results: The sparsity of the coefficients in an unconditional basis determines the rough asymptotics in \(\varepsilon\) for the number of bits which must be stored to reconstruct any memher of \({\mathcal F}\) to within \(\varepsilon\)-accuracy. A simple transform coding scheme based on uniform quantization and run-length encoding of the coefficients in the unconditional basis can achieve near-optimal asymptotics for the number of bits needed to represent any member of \({\mathcal F}\) to accuracy \(\varepsilon\). In short, when an unconditional basis for a class \({\mathcal F}\) exists, transform coding in that basis offers near-optimal representation of elements of \({\mathcal F}\).