Tree Approximation and Optimal Encoding
Applied and Computational Harmonic AnalysisPublished 1 September 2001
Albert Cohen, Wolfgang Dahmen, Ingrid Daubechies, Ronald DeVore
Citations165
SJR quartileQ1
SJR score2.05
SNIP2.06
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
It is shown that the restrictions of tree approximation cost little in terms of rates of approximation, and encoders for compression are designed that provide upper estimates for the Kolmogorov entropy of Besov balls.
Abstract
Tree approximation is a new form of nonlinear approximation which appears naturally in some applications such as image processing and adaptive numerical methods. It is somewhat more restrictive than the usual n-term approximation. We show that the restrictions of tree approximation cost little in terms of rates of approximation. We then use that result to design encoders for compression. These encoders are universal (they apply to general functions) and progressive (increasing accuracy is obtained by sending bit stream increments). We show optimality of the encoders in the sense that they provide upper estimates for the Kolmogorov entropy of Besov balls.
Keywords
Computer ScienceMathematics
Computers in PhysicsTen Lectures on Wavelets
15,386 Citations1992Ingrid Daubechies, Christopher Heil
This paper presents a meta-analyses of the wavelet transforms of Coxeter’s inequality and its applications to multiresolutional analysis and orthonormal bases.
Communications on Pure and Applied MathematicsOrthonormal bases of compactly supported wavelets
8,187 Citations1988Ingrid Daubechies
This work construct orthonormal bases of compactly supported wavelets, with arbitrarily high regularity, by reviewing the concept of multiresolution analysis as well as several algorithms in vision decomposition and reconstruction.
IEEE Transactions on Signal ProcessingEmbedded image coding using zerotrees of wavelet coefficients
4,813 Citations1993J.M. Shapiro
Communications on Pure and Applied MathematicsBiorthogonal bases of compactly supported wavelets
2,648 Citations1992Albert Cohen, Ingrid Daubechies +1 more
Munich Personal RePEc Archive (Ludwig Maximilian University of Munich)Curvelets: A Surprisingly Effective Nonadaptive Representation for Objects with Edges
1,335 Citations2000Emmanuel J. Candès, David L. Donoho
The basic issues of efficient m-term approximation, the construction of efficient adaptive representation, theConstruction of the curvelet frame, and a crude analysis of the performance of curvelet schemes are explained.
Acta NumericaNonlinear approximation
859 Citations1998Ronald DeVore
This is a survey of nonlinear approximation, especially that part of the subject which is important in numerical computation, and emphasis will be placed on approximation by piecewise polynomials and wavelets as well as their numerical implementation.
IEEE Transactions on Image ProcessingAn image multiresolution representation for lossless and lossy compression
615 Citations1996Amir Said, William A. Pearlman
A new image multiresolution transform that is suited for both lossless (reversible) and lossy compression, and entropy obtained with the new transform is smaller than that obtained with predictive coding of similar complexity.
Memoirs of the American Mathematical SocietyMaximal functions measuring smoothness
292 Citations1984Ronald DeVore, Robert Sharpley
IEEE Transactions on Signal ProcessingAnalysis of low bit rate image transform coding
289 Citations1998Stéphane Mallat, Frédéric Falzon
Calculations based on high-resolution quantizations prove that the distortion rate D(R) of an image transform coding is proportional to 2/sup -2R/ when R is large enough, and shows that the compression performance of an orthonormal basis depends mostly on its ability to approximate images with a few nonzero vectors.
Advances in Computational MathematicsThe best m-term approximation and greedy algorithms
169 Citations1998Vladimir Temlyakov
Two theorems on nonlinear term approximations with regard to two dictionaries: the Haar basis and the set of all characteristic functions of intervals are equivalent in a very strong sense are proved.
IEEE Transactions on Information TheoryOn the importance of combining wavelet-based nonlinear approximation with coding strategies
141 Citations2002Albert Cohen, Ingrid Daubechies +2 more
This paper provides a mathematical analysis of transform compression in its relationship to linear and nonlinear approximation theory, and forms a family of functions/stochastic processes for which they provide efficient descriptions in a rate-distortion sense.
Applied Numerical MathematicsStable multiscale bases and local error estimation for elliptic problems
93 Citations1997Stephan Dahlke, Wolfgang Dahmen +2 more
It is shown that the locality of corresponding multiresolution processes combined with certain norm equivalences involving weighted sequence norms of wavelet coefficients leads to adaptive space refinement strategies which are guaranteed to converge in a wide range of cases, again including operators of negative order.
Constructive ApproximationRestricted Nonlinear Approximation
81 Citations2000Albert Cohen, Ronald DeVore +1 more
A new form of nonlinear approximation called restricted approximation is introduced, a generalization of n -term wavelet approximation in which a weight function is used to control the terms in the wavelet expansion of the approximant.
Constructive ApproximationAn Adaptive Compression Algorithm in Besov Spaces
66 Citations2000Lucien Birgé, Pascal Massart
A new algorithm providing an approximation $\tilde f of f with a prescribed number D of nonzero coefficients in its expansion with the optimal rate D-α of approximation with respect to the Lq -norm when f belongs to some Besov space Bαp,∈fty whenever α>(1/p-1/q)+ .
Wavelet analysis and its applicationsNonlinear Approximation and Adaptive Techniques for Solving Elliptic Operator Equations
64 Citations1997Stephan Dahlke, Wolfgang Dahmen +1 more
After demonstrating the gain of nonlinear approximation over linear approximation measured in a Sobolev scale, it is reviewed some recent results on the SoboleV and Besov regularity of solutions to elliptic boundary value problems.
Applied and Computational Harmonic AnalysisUnconditional Bases and Bit-Level Compression
59 Citations1996David L. Donoho
The purpose of this note is to point out that results analogous to [2] hold under a model which measures bits encoded.
WIT transactions on information and communication technologiesOptimal Entropy Encoders For Mining MultiplyResolved Data
7 Citations2000Ronald DeVore, Laura Johnson +2 more
A prototype client-server implementation of image analysis and compression is described which is based on the recently developed theory of Cohen, Dahmen, DeVore, and Daubechies for optimal entropy data encoders for purposes of compression, storage, and transmission of data which can be developed into a multi-resolution framework.