Thrun, Burgard, and Fox's Low-variance resampling?

[ssfrr]

I'm using the following resampling algorithm (with replacement) from Thrun, Burgard, and Fox's "Probabilistic Robotics" as part of a particle filter implementation. Would this be appropriate to include among StatsBase's sampling algorithms?

One nice thing is that it consumes only a single random number. I'm not sure whether it has other non-desirable properties though. I'm definitely not a statistician.

This picture (copyright the authors) was useful in understanding how it works:

(as implemented it assumes that the weight vector is normalized, but that's an easy fix. I'm returning the weights of the sampled items as well)

"""
Given the current state estimate X and weight vector w, resample a new set of
states. We use the low-variance resampling algorithm from Thrun, Burgard, and Fox's
"Probabilistic Robotics". By default it will keep the number of samples constant
"""
function sample(X, w, M=size(X, 2))
    X2 = similar(X, (size(X, 1), M))
    w2 = zeros(M)
    r = rand(Uniform(0, 1/M))
    c = w[1]
    i = 1

    for m in 1:M
        # calculate the next sample point
        U = r + (m - 1) * (1/M)
        # find the first weight that puts us past the sample point
        while c < U
            i += 1
            c = c + w[i]
        end
        X2[:, m] = X[:, i]
        w2[m] = w[i]
    end
    X2, w2
end

[kmsquire]

I've used this method before--it's great when speed and coverage of your space are more important than actual randomness.

I could see it added as an alternate method to what's available in sampling.jl right now, but not be selected by the polyalgorithm. That said, I haven't spent any time maintaining StatsBase, so it would be good to hear opinions from people who actually have.

[jamesonquinn]

I just came upon a use-case for this. If I wrote it into statsBase and submitted a PR, would it be looked on favorably? This is after all only a thread from 2015...

[nalimilan]

I guess it would be fine to add as an option.