Quick description
When estimating a sum or integral of an expression which depends very much on the magnitude of some expression , try decomposing the sum or integral based on the dyadic regions
for
. This is a special case of the divide and conquer strategy. (Occasionally, one needs also to deal with the exceptional set
.)
Prerequisites
Undergraduate calculus. For more geometric integrals, a good geometric intuition is also useful.
Example 1
The Cauchy condensation test is a classic example of dyadic decomposition in action.
Example 2
Suppose we want to obtain upper and lower bounds for the integral

on the unit sphere in
, where
is surface measure,
is an exponent, and
is a parameter, which we assume to not lie on the unit sphere. For the purposes of this exercise, we are willing to lose multiplicative constants that depend on
and
, but we are interested in the behavior in
(in particular, how does this integral degenerate as
?)
Let's first deal with some easy cases. Suppose is quite small, e.g.
. Then we see that
is comparable to
. In this case a simple application of the base times height method gives upper and lower bounds of
(up to constants).
Similarly, when is quite large, e.g.
, then
is comparable to
, and the base times height method now gives upper and lower bounds of
(again up to constants).
Now we turn to the intermediate region . Here, the base times height method does not work so well. Indeed, if we let
, this method gives an upper bound of
and a lower bound of
(up to constants); these two bounds diverge as
. The problem here is that the integrand
is no longer of the uniformly distributed type that is amenable to the base times height bounds; instead, the integrand is quite large when
is nearly parallel to
, and quite small when
is distant from
.
After looking at the geometry of the situation, it becomes clear that the most important parameter controlling the magnitude of the integrand is the angle between
and
. Indeed, using some trigonometry (and taking advantage of useful simplifications that are available when one is willing to lose constants, e.g. that
is comparable to
) we soon see that the distance
between
and
is comparable to
. In particular, we see that the "natural" scale for
is that of
.
Once one sees this, it becomes natural to dyadically decompose with respect to , and specifically into the very near region
and dyadic shells
for
. (It is pointless to decompose the very near region any further, because when
,
is no longer the dominant influence on the integrand.) Actually, since
cannot exceed
, we can stop the decomposition once
exceeds
.
We can then apply the base times height method to each region. In the near region , the integrand has height bounded above and below by
(up to constants), and the base has measure
(up to constants), leading to a net bound of
. Similarly, on each shell
, the height is comparable to
, and the base is comparable to
(except possibly for the very last shell, but let's ignore this), leading to a net bound of
. Summing this geometric series, we obtain a final upper or lower bound comparable to
when
,
when
, and
when
.
General discussion
Dyadic decomposition is a fairly efficient technique that generally only "loses a logarithm" or "loses an epsilon exponent" compared to the optimal bound. This is because on many cases, the number of dyadic scales which are "active" or "important" is only logarithmically large with respect to some relevant parameter. For instance, if one is estimating a sum
by decomposing
into dyadic regions
, the number of such regions is only
, and so even if one only decides to estimate a single, "worst-case" region rather than handle all the regions at once, one only expects to be off by a factor of
at worst.
The only time when dyadic decomposition is truly inefficient is when one expects quite a lot of cancellation between different dyadic regions. In such cases, of course, this sort of decomposition should be avoided.
Sometimes (as one sees in Example 2) one does not want to dyadically decompose the very small or very low values of , thus for instance one could decompose the region
into dyadic regions
for
, but refuse to decompose the region
any further. The choice of when to decompose and when not to varies from problem to problem; one has to weigh the benefits of a decomposition against the costs.
For an integral such as , sometimes one wants to dyadically decompose the independent variable
, for instance into dyadic annuli
. In other cases, it makes more sense to decompose the dependent variable
, for instance into level sets
. The optimal choice of decomposition is often determined by the geometry of the situation. If, for instance, one is trying to integrate a function
which is becoming singular on some set
(e.g. a point, a line, a surface, etc.), then dyadically decomposing based on the distance to that set
, e.g. to sets
There is nothing sacred about powers of here. Sometimes it is more advantageous to use a sparser dyadic decomposition, e.g. powers of
, where
is a parameter to be optimized later.
It is often advantageous to decompose using smooth cutoffs rather than sharp cutoffs, especially if there is oscillation present and one wishes to maximize the effect of cancellation.
See also this expository article of Tao.
Comments
Thanks a lot for this clear
Fri, 08/05/2009 - 08:36 — Anonymous (not verified)Thanks a lot for this clear and precise page on Dyadic decompositions. With it, I have cleared all my doubts on the subject.
greetings
Miguel