Yet another resampling algorithm

1

I searched for some resampling algorithms here and didn't find one similar enough to the one I'm going to post here. I don't think it's the fastest but it is simple enough to give it a shot.

Anyway, I will show first the "basic" version, then a slight modification to make the "upgraded" one. I haven't benchmarked it but I think the "basic" is O(N logN) and the "upgraded" is O(N). I could be wrong though.

p3 = []
probs = []
wsum = sum(w)

for i in range(len(p)):
    probs.append(random.uniform(0,1))
    w[i]=w[i]/wsum

x = w[0]
k = 0
j = 0

probs.append(1.0)
probs = sorted(probs)

while k<len(p)-1:    
    if x>probs[j]:
        p3.append(p[k])
        j=j+1
    else:        
        k=k+1
        x=x+w[k]

print p3

It can be seen that the slow part is probs = sorted(probs), which is O(N logN). But probs can be assigned from this array for a faster implementation: [1/N, 2/N, ... ,N-1/N, 1]. The "upgraded" version of the algorithm, would look like this in code:

for i in range(len(p)):
    probs.append(i/len(p))

Leaving the rest almost untouched, making the algorithm faster (because the array is already sorted). One problem is that it doesn't follow the premise of "random" sampling of particles. Nonetheless, for N big it's not a problem I think, keeping the resampling fairly accurate.

Finally, there are other parts that can be optimized. For example tweaking the code a bit, it isn't necessary to normalize w. But that's for another discussion :)

This question is marked "community wiki".

asked 22 Mar '12, 23:21

Francisco-3's gravatar image

Francisco-3
11●4
accept rate: 0%

edited 24 Mar '12, 17:23

Be the first one to answer this question!
Question text:

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • image?![alt text](/path/img.jpg "Title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported

learn more about Markdown

Tags:

×5,185
×89
×57
×38

Asked: 22 Mar '12, 23:21

Seen: 138 times

Last updated: 22 Mar '12, 23:21

Related questions

An O(N) unbiased resampler

Resampling: Walker Alias Method

Particle Filter: Resampling Wheel - why so complicated?

Why do we choose 2*maxValue in Resampling step?

Resampling Wheel

why the solution of unit3-20 uses the raw weight vector rather than normalized weight vector

Resampling

Could this explain the possible bias issues of using 2*Max in the resampling step?

Unit 3-19 right answer?

Resampling Wheel Algorithm - Description suggests ending up with fewer than N