0
$\begingroup$

I need to scale my histogram as I cannot store them with large numbers. Hence, I need to normalize it. I have taken normalization factor as sum of total population. But this need to happen recursively. As samples arrive, I need to count them and scale them iteratively. Any formula to iteratively update?

I have histogram both in 1D and 2D.

Will be grateful for any pointers.

$\endgroup$
0
$\begingroup$

Here is one naive approach, let me explain with an example:

Suppose we have a normalized histogram with just 3 bins (hist[1], hist[2], hist[3]). Let the size of the current population be 100. Then, a new value can be binned as follows :

The following is a pseudo-code :

update_hist (curr_population_size, hist, new_element) {

    bin_index = determine_bin_index (new_element);
    new_population_size = curr_population_size + 1;

    for i = 1 to number_of_bins(hist)
        if i == bin_index then
            hist[i] = (hist[i]*curr_population_size + 1)/new_population_size;
        else        
            hist[i] = (hist[i]*curr_population_size)/new_population_size;
    endfor

    return hist
}

Now Suppose, hist[1] = 0.3,hist[2] = 0.2, and hist[3] = 0.5. Then, by the above pseudo-code, a new value, when arrives, and whose bin is determined to be say 2, updates the hist as :

hist[1] = (0.3*100  )/101 = 0.3069306930693069
hist[2] = (0.2*100+1)/101 = 0.2079207920792079
hist[3] = (0.5*100  )/101 = 0.4950495049504950

A note of caution : Repeated multiplications and divisions with large numbers may result in erroneous values due to rounding errors introduced by floating point arithmetic.

$\endgroup$
  • 1
    $\begingroup$ I think this is pseudocode; that in itself is fine but please confirm; otherwise some readers may wonder whether some language is being used that they don't know. (If it's some particular language, the point is made for me.) $\endgroup$ – Nick Cox Jan 16 '16 at 10:49
  • 1
    $\begingroup$ Please spell out the assumptions here. It seems that the bins are all supposed predefined. $\endgroup$ – Nick Cox Jan 16 '16 at 10:51
  • $\begingroup$ @NickCox Yes it is pseudocode, I have updated my answer. Well yes, the number of bins is predefined here because, as the question only asks for updating an existing histogram, with new streaming incoming values. $\endgroup$ – Swaroop Jan 17 '16 at 5:53
  • $\begingroup$ Thanks for the clarification. Sometimes bins will be predictable in advance, but not always. $\endgroup$ – Nick Cox Jan 17 '16 at 13:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.