Friday, May 27, 2011

Sampling from a multivariate normal in C++

Update 3 May 2013:  There was a Stackoverflow link to this, so I posted an answer with some updated code.


For some reason, it's hard to find code that lets you sample from a multivariate normal.  That's annoying.  So I followed Wikipedia's instructions for creating the sample.  I use Boost to generate univariate normal samples and Eigen to handle the matrix math.  Here's my current solution:
#ifndef __EIGENMULTIVARIATENORMAL_HPP
#define __EIGENMULTIVARIATENORMAL_HPP

#include <Eigen/Dense>

#include <math.h>

#include <boost/random/mersenne_twister.hpp>
#include <boost/random/normal_distribution.hpp>
#include <boost/random/variate_generator.hpp>

/**
    We find the eigen-decomposition of the covariance matrix.
    We create a vector of normal samples scaled by the eigenvalues.
    We rotate the vector by the eigenvectors.
    We add the mean.
*/
template<typename _Scalar, int _size>
class EigenMultivariateNormal
{
    boost::mt19937 rng;    // The uniform pseudo-random algorithm
    boost::normal_distribution<_Scalar> norm;  // The gaussian combinator
    boost::variate_generator<boost::mt19937&,boost::normal_distribution<_Scalar> >
       randN; // The 0-mean unit-variance normal generator

    Eigen::Matrix<_Scalar,_size,_size> rot;
    Eigen::Matrix<_Scalar,_size,1> scl;

    Eigen::Matrix<_Scalar,_size,1> mean;

public:
    EigenMultivariateNormal(const Eigen::Matrix<_Scalar,_size,1>& meanVec,
        const Eigen::Matrix<_Scalar,_size,_size>& covarMat)
        : randN(rng,norm)
    {
        setCovar(covarMat);
        setMean(meanVec);
    }

    void setCovar(const Eigen::Matrix<_Scalar,_size,_size>& covarMat)
    {
        Eigen::SelfAdjointEigenSolver<Eigen::Matrix<_Scalar,_size,_size> >
           eigenSolver(covarMat);
        rot = eigenSolver.eigenvectors();
        scl = eigenSolver.eigenvalues();
        for (int ii=0;ii<_size;++ii) {
            scl(ii,0) = sqrt(scl(ii,0));
        }
    }

    void setMean(const Eigen::Matrix<_Scalar,_size,1>& meanVec)
    {
        mean = meanVec;
    }

    void nextSample(Eigen::Matrix<_Scalar,_size,1>& sampleVec)
    {
        for (int ii=0;ii<_size;++ii) {
            sampleVec(ii,0) = randN()*scl(ii,0);
        }
        sampleVec = rot*sampleVec + mean;
    }
    
};

#endif

9 comments:

  1. Thank you for your code. I am however, having some problems with the use of templates. What exactly is the _Scalar and _size values?

    ReplyDelete
    Replies
    1. The _Scalar template parameter is probably either "float" or "double". The _size parameter, is the integer dimensionality of the Gaussian. Making it a template parameter means that it needs to be known at compile time, but it shouldn't be terribly difficult to tweak it to use the dynamically sized matrices/vectors.

      Delete
  2. This post was linked to in a Stack Overflow question. I thought I'd mention that your code has undefined behaviour because you're using reserved identifiers. Anything containing a double underscore or starting with an underscore followed by a capital letter is reserved.

    ReplyDelete
    Replies
    1. Hmm... I wasn't aware of the underscore-capital restriction.

      Thanks for the tip. The code is also old and needs some serious rethinking for more reasons than just that.

      Delete
  3. In the Stack Overflow question @Joseph is referring (I think), an answer contains a potential improvement to the code:

    http://stackoverflow.com/questions/16361226/error-while-creating-object-from-templated-class/16364899?noredirect=1#comment23457843_16364899

    Besides, I am running your code, and it seems to be sampling the same values every time I run the function. That's not supposed to happen, as it is supposed to be stocastic sampling!

    ReplyDelete
    Replies
    1. The pseudo-random number generator will always begin with the default seed using this code. If you create a new instance of EigenMultivariateNormal, then it will instantiate a new generator. To avoid that, you could declare the `rng` as a static object.

      Delete
    2. Hi In the Stack Overflow question

      https://stackoverflow.com/questions/16361226/error-while-creating-object-from-templated-class/16364899#16364899?newreg=471f143429ff4255b009c221394468f4

      @Jcooper mentioned that Eigen::internal::scalar_normal_dist_op::rng.seed((int)time(0)); is to be added to generate random numbers for running each time but i am unable to add the command any where can you tell me where to add the command to generate random numbers each time i call samples

      Delete
  4. Hi, i am trying to run the code that I think you posted on http://stackoverflow.com/questions/16361226/error-while-creating-object-from-templated-class#new-answer, I am able to compile it and to run it, but what I get in the file samples.txt, it's a matrix of "NaN".

    Could you help me?? I would like to use your code to implement a Mixture of 2D Gaussian.

    Thanks in advance

    ReplyDelete