How to smooth histograms with bins 1, 2, 4, ... wide?

Say I make histograms H1, H2, H4 ...of the same set of data with bins 1, 2, 4 ... wide. Then the bins containing a given $x$ have counts and averages

n1 av1 in H1,
n2 av2 in H2,
n4 av4 in H4 ...


How should one weight these to estimate data(x) ?
One possibility would be $\Sigma w_j \text{av}_j / \Sigma w_j$ with $w_j = n_j / j$, for the first two non-zero $n_j$.

The general goals are to fill holes where bins are empty, and to smooth bins with many data points.

(H2 etc. can either be built together with H1, or on-the-fly from H1 as needed: a space-time tradeoff.)

Added, trying to clarify: there are two related subquestions:

• local vs global:
If almost all the terms in $\Sigma K( x_j\, \text{near}\, x )$ are 0, there must be a better way. (For 1D it hardly matters, but in 2D or 3D, $N^2$, $N^3$ get big quickly.)
One way of finding $x_j$ near $x$ (to sum $K$ at those only) is to grow shells in a regular grid -- poor for clumpy or hole-y data. Another is to find $N_{\text{near}}$ nearest neighbours in a Kd tree -- but what should $N_{\text{near}}$ be ?

A method that adapts to clumpy data, as TINs (triangulations) adapt to terrains, would be nice.

(Years later) the magic words are "multiresolution" or "multiscale"; see e.g.
scholar allintitle: (multiscale|multiresolution) (histogram | estimation) .
Does anyone know of comparisons with conventional KDE on real data, 2d and up ?

• What's wrong with conventional kernel density estimation? Commented Oct 7, 2010 at 12:08
• Correct me, conventional KDE uses all the input data points for each estimate(x) -- quite unpractical for many points. I'm looking for ways to combine a) get some nearby points (a general problem), b) weight the values from this small sample Commented Oct 8, 2010 at 10:54
• If you use a kernel with a finite support (e.g., the quadratic Epanechnikov kernel), then only nearby points contribute anything to a kde. Even with a Gaussian kernel, the contribution of points more than 3 bandwidths from x is negligible. I would definitely use kde rather than your proposed approach. Commented Oct 9, 2010 at 22:39
• @Rob, thanks; I'll try to clarify the question, and split off "adaptive histograms" as a separate question. Commented Oct 11, 2010 at 16:40