How to approximate histogram(f(x)) from histogram(x)?

Question

I have a histogram of a variable x, and I would like to get the histogram of f(x). Let's just say the transformation function is elementary and smooth. Is there a good method (maybe unbiased?) to transform the histogram(x) into histogram(f(x)), without having to re-aggregate on the raw samples?

Some ideas I had:

• transform bin center, and then rounding; seems to leave a lot of gaps in the result though
• transform bin center, and proportionally incrementing the two closest bins; gets rid of some of the gaps, but not entirely
• thought of using some linear interpolation to increase the bin count of the original by 10x, and then transforming these back down to 1/10 size; have not tried this yet

Seems like it would be a common thing to do, so I don't want to reinvent the wheel here.

Answer 1

Computing $f(x)$ for the original samples then re-computing the histogram will give greater accuracy, because the original histogram destroys information about the distribution. But, assuming you can't do this for some reason, here's a possible way to do what you asked.

The exact approach would be to treat the original histogram as the true distribution, then use the change of variables formula to obtain the distribution after transforming by $f$. Here's an approximation scheme. The idea is to use the original histogram to create a small, synethetic dataset where each point has a weight that reflects its probability. These points can then be transformed and used to construct a new histogram.

For each bin in the original histogram, sample $k$ points uniformly at random within the boundaries of the bin. This gives a list of synthetic points $\tilde{X} = \{\tilde{x}_1, \dots, \tilde{x}_n\}$ (where $n$ is equal to $k$ times the number of bins). Let $W = \{w_1, \dots, w_n\}$ be a list of corresponding weights, where each $w_i$ is equal to the height of the histogram in the bin from which $\tilde{x_i}$ was sampled. Transform the synthetic points using the function $f$, giving a list of transformed points $\tilde{Y} = \{\tilde{y}_1, \dots, \tilde{y}_n\}$, where each $\tilde{y}_i = f(\tilde{x}_i)$. Finally, compute a weighted histogram of the transformed points $\tilde{Y}$, using weights $W$. As opposed to an ordinary histogram (where the number of points in each bin are added up), here the weights of the points in each bin are added up. Normalize as needed.

Answer 2

I discovered a method that is giving me fairly good results. Given a bin $start$ and $end$, the trick is to evaluate the transform function between $f(start)$ to $f(end)$ and find all the bins the transformed curve segment would intersect. Assuming all the samples from the original $histogram(x)$ are evenly distributed inside each bin, increment each intersecting bin proportional to how much of the curve segment's domain passes through that bin.

I ended up discretizing my transformation functions into piecewise linear functions, in order to make the intersection and value distribution calculations simpler. I would suggest perhaps using Newton's method for arbitrary functions; if you know the function apriori, you could provide an analytic solution to the intersection as well.

If the transformation function has small derivatives relative to bin size, you shouldn't notice much bias in assuming a flat sample distribution for each bin. I suppose if this is a problem in your case, you can try adaptively sized bins, to capture more resolution in detailed areas. Alternatively, you could make some assumptions about the underlying curve, and do some kind of interpolation or curve fitting on the histogram to get a better estimate of the bin sample distribution. I didn't experiment with this though, so I can't say how well they would work.