Perfect Sampling Using Mcmc Computer Science Essay

Published: Last Edited:

This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.

The research in Markov Chain Monte Carlo is increasing and with the newly proposed MCMC sampling methods which could tackle high complexity problems, the research in Signal Processing is also gaining much popularity. The new Markov Chain methods could produce independent and identically distributed (i.i.d) samples exactly from the desired distribution. They are termed as perfect samplers. In this paper, some perfect sampling methods like Coupling from the past (CFTP) and its extension called Gibbs coupler are reviewed before proceeding to the applications of perfect sampling in signal processing. An application of Gibbs coupler in multiuser detector of CDMA signals is explained in detail.

Markov chain Monte Carlo sampling is an important and successful Monte Carlo method in Computational science. The purpose of this paper is to review Markov chain based perfect sampling and its application in signal processing. Research in signal processing has also made significant strides in recent times. In statistical signal processing, from Bayesian point of view, all the relevant information that can be extracted from data about a signal unknown is contained in the posterior distributions of the unknowns. The analytical approach of computing posterior distributions is infeasible due to its high computational complexities. The Monte Carlo signal processing methods are simple and powerful numerical techniques for the Bayesian computation. The idea here is to generate samples from the posterior distribution and use them to extract relevant information. All the information that we can know about a signal unknown is summarized by its posterior densities or likelihoods. And if the samples can approximate the posterior densities or the likelihoods well, they can be used for inference and for carrying out the necessary computations.

The MCMC sampling produces samples as a sequence of random variables according to a transition kernel of the chain. The chain starts from an arbitrary state at t=0 and converges to its unique stationary distribution after some time. The samples produced after the convergence of the chain look like the samples from stationary distribution. The period from t=0 until the convergence is known as "Burn-in period". The samples which are generated after the Burn-in period are assumed to be true samples from a stationary distribution. There are many methods to assess the convergence of markov chains. But none of them guarantee that the chains have converged and that the samples produced are true samples from the desired distribution. A markov chain method which is proposed by Propp and Wilson guarantees that the samples are exactly from the stationary distribution, which is called Coupling from the past method. There are interesting extensions of CFTP algorithm. One such extension is the Gibbs coupler method, which is an implementation of the CFTP and combines CFTP scheme with Gibbs sampling.

The rest of the paper is organized in the following way: In section 2, CFTP is reviewed; In section 3, Gibbs Coupler is reviewed; In section 4, Signal processing is described; In section 5, some of the applications of perfect sampling in signal processing are discussed; In section 6, the application of Gibbs coupler in developing multiuser detector is explained; In section 7, experiments and results are shown; In section 8, a conclusion is given.

2. Coupling from the past algorithm

The CFTP uses the concept of coupling which involves running coupled markov chains that start from different initial states. The Markov chains in CFTP are run from the past (t<0) to the present (t=0) and the samples are drawn at a fixed time t=0, if the convergence of chains occur by the time t=0. CFTP was first defined for discrete state spaces, but later it was extended for continuous state spaces also. Consider an ergodic markov chain with discrete and finite state spaces of size M. If M copies of the chain which have different initial states are run, the chains will eventually converge and will be stationary by time t=0. Here the value of the chains at t=0 is taken as a perfect sample from the stationary distribution. All the M chains are initially started at t=-1 and are checked for convergence at t=0. If the convergence occurred by the time t=0, then the state of the chain at t=0 is taken as the sample from the desired distribution. If the convergence does not occur by the time t=0, then the starting time is further moved back to t=-2 and the chains are again checked for convergence. The process is repeated.

The two important points for the implementation of CFTP scheme are that for the transitions from t=k to t=k+1 where k<0, only one random number is used i.e. every time the starting time is shifted back by one time unit, only one new random number is generated which is R^(t+1). And the samples are drawn at t=0 only if the convergence occurred earlier.

For instance, in the following example the chains have started at t=-3 and converged at t=-1. i.e. the trajectories of the chains converged at t=-1 when they were started at t=-3 and the trajectory was completed at t=0 and x=1 is taken as sample.

D:\subjects\Dr.Mascagni\cftp (1).jpg

The CFTP scheme can be described in pseudo code form as follows

The CFTP method which is described above is computationally difficult for the problems where markov chains have large number of state spaces. So practically, it is quite limited. And in some applications which are important, an updating function with the property of monotonicity can be defined for a partial order imposed on state space S. So as a result of this only two chains will be used. CFTP algorithms that exploit monotonicity and antimonotonicity of the chains are termed as Sandwiched CFTP algorithms.

3. Gibbs Coupler

On large state spaces, the implementation of CFTP is complex because of the heavy computation in tracing all the markov chains which are started at every possible state. So, computationally more efficient algorithms have been proposed. Gibbs coupler is an interesting extension of the CFTP algorithm on binary state spaces. It is a coupling algorithm which can be applied to large state spaces without the need for monotone or antimonotone properties of the updating function. The coupling method used by the Gibbs coupler is component based. As it combines CFTP and Gibbs sampler, it takes the features of both of them. The overall framework of Gibbs coupler is based on CFTP which guarantees that unbiased samples will be obtained from the desired distribution. It is particularly important when sampling is done from high dimensional state spaces. When experimented on multi-dimensional binary variable space, Gibbs coupler is able to handle cases where monotonicity or antimonotonicity does not exist.

As Gibbs coupler is component based, suppose that the state of the chain has binary representation given by x1, x2, x3, …xn and S denotes the support of x at time t. Then S1, S2, S3, S4…Sn denote the support of x1, x2, x3,..xn at time t with individual component supports being {1},{-1}or{-1,1}.

Then the update of the support according to [2] is given as follows

Where Ri is the uniform random seed.

Then according to [1], the Gibbs coupler that generates exact samples is given by the following pseudo-code.

Where S is the collection of supports of x1,x2,x3,…xn . Convergence occurs if the supports of all the Si are singletons. The singleton supports define the generated sample if the convergence occurs at t=0.The concept of Sandwich distributions is considered an important ingredient in Gibbs coupler. The concept of sandwich distributions is that only two markov chains are traced instead of tracing all the chains like in CFTP. So the computation is reduced to a great extent. It can be proved that the sandwich distributions achieve the highest probability of convergence .So by using them, fastest convergence can be achieved. According to [1], they are defined for every time t and i by

D:\subjects\Dr.Mascagni\sandwich distributions.png

Though the Gibbs coupler has same rate of convergence as that of CFTP, for high dimensional state spaces, if the sandwich distributions are calculated in a straight forward manner, then it is computationally much more efficient than CFTP. And the Gibbs coupler is equivalent to the sandwiched CFTP algorithm for the problems where monotonicity exists.

4. Signal Processing

"Signal processing is an area of applied mathematics, systems engineering and electrical engineering. It deals with operations and analysis of signals or measurements of time varying and spatial varying physical quantities. Signals can be sound, images, electromagnetic radiation and sensor data."

The signal processing problems are addressed with increased complexity. This can be seen by the forms of models which are used for describing the phenomena of interest. In these models there are large number of unknowns that are to be estimated and the noise distributions are non- tractable for analytical derivations. And researchers are tending to resolve such complex problems because of the advancements of methods based on Monte Carlo simulations which include both Markov Chain Monte Carlo sampling and particle filtering. Many signal processing applications which include detection, filtering and estimation require evaluation of integrals, optimization and stochastic simulation. In signal processing methods which require stochastic simulation, samples must be generated from a multivariate probability distribution p(x|y) where x is the vector of unknown parameters and y is a vector of observations.

The statistical signal processing problems in wireless communications involve making inference about the information that is transmitted based on the received signals in the presence of various unknown channel distortions. And the solutions to these problems by conventional signal processing methods involve complex computations. The Monte Carlo methods which are simple and powerful numerical techniques provide optimal solutions for wireless signal processing problems.

5. Applications of Perfect sampling in signal processing

In signal processing, "sampling is the reduction of a continuous signal to a discrete signal". The implementation of Bayesian methods by means of Monte Carlo techniques like Markov Chain Monte Carlo and Particle filters have gained significant popularity in signal processing over the past few years. Some of the applications of perfect sampling in signal processing include Wavelet reconstruction of the signals, Restoration of binary images and Multiuser detection.

In Wavelet reconstruction of the signals, the CFTP scheme is applied in the reconstruction of signal using Bayesian wavelet analysis.

In the restoration of binary images, various Bayesian estimators including maximum a posteriori (MAP) and marginal posterior node (MPM) can be used in order to obtain an estimate of the true binary image. These estimators evaluate the posterior distributions. But for large N, it becomes computationally complex. So, perfect sampling methods like the sandwiched CFTP can be applied to simulate the posterior distributions.

Multiuser detection in CDMA is one field which has been benefited to a great extent by the perfect sampling schemes. Many multiusers detectors have been developed based on the Sandwiched CFTP, Gibbs Coupler and Gibbs sampler. Multiuser detection techniques in CDMA are used to recover transmitted signals at the receiver end.

6. Application of Gibbs Coupler in Multiuser detection of synchronous CDMA signals

"Code-division multiple access (CDMA) is a multiplexing technique which enables multiple users to access a common channel simultaneously." In CDMA systems which have large number of users, the transmitted signals from the users overlap in time and frequency. So in order to recover the signals transmitted by the users at the receiver end, multiuser detection techniques are used. These techniques have an advantage over the single-user matched filter, in which there is no information about the actual interference among users. The optimum multiuser detector is one efficient technique to recover the signals at the receiver end. Various different techniques have been developed in order to approach the performance of the optimum multiuser detector. The decorrelating detector which is in the class of linear detectors is very popular among them due to its computational simplicity. But in many cases, the performance of linear detectors is not optimal and so better solutions which can increase the performance have been proposed. Among them are the Markov Chain Monte Carlo sampling methods.

A multiuser detector is proposed recently which is developed under the Bayesian framework and implemented by the perfect sampling algorithm called Gibbs coupler. A salient feature of this proposed detector is the use of exact true samples from the posterior distributions which improves the performance of the detector.

The optimum multiuser detection is first explained before proceeding to the multiuser detector using Gibbs coupler. Consider a k-user synchronous CDMA channel which can be modeled as follows,


y is the received signal

S is the antipodal signature waveform

A is the amplitude of the user signal

b is the bit transmitted by the user

n is the white Gaussian noise and

T is the symbol duration

The main purpose of the multiuser detection is to correctly detect the transmitted symbols by each of the user. Here, in the above channel, it is assumed that except the bits transmitted by the user, all the remaining parameters are known. So the objective here is to estimate b. The single-user matched filter makes decision on the symbol of each user separately and it does not exploit information about the users' correlations and the users' interference is regarded as noise. Therefore it is not optimal when multiuser interference is present in CDMA systems. So a multiuser detection strategy must be employed for optimum multiuser detection. From Bayesian point of view, the estimate of b is optimum when it maximizes the posterior distribution. One of the solutions can be to use the maximum a posteriori (MAP) detector. A non-informative prior can be chosen for b because nothing is known a priori about b. Then according to [3], the posterior distribution for b can be expressed as follows,

Where represents cross correlations between the kth and lth signature waveform. A perfect sampling algorithm can be applied to compute the output of the MAP detector. One such method is the Gibbs coupler.

An important step in the implementation of Gibbs coupler is to determine sandwich distributions on full conditional distributions. In the multiuser detection problem, according to [2], from the posterior distributions, the full conditional distributions are readily derived for i=1, 2, 3, 4…k as

The sandwich distributions are obtained by maximizing and minimizing the above distributions on the support. On the above distributions, the maximum and minimum with respect to can be determined by checking the sign of AiAkpk. Then according to [2], the sandwich distributions at time t will be


The contains the indices of the elements that have not converged at time t, and contains the indices of the remaining elements that have converged at time t. According to the Gibbs coupler algorithm, the support of the i-th component is updated according to the support funtion at any time t. And the converged state at time t=0 is taken as the perfect sample from the posterior distribution.

For instance, suppose that the desired sample size is M. The maximum a posteriori(MAP) estimate is computed once the M samples are acquired. There are many ways to find the MAP estimate, one approach is to compute the posterior probability of every perfect sample, and the estimate with highest probability will be the MAP estimate. An alternative approach is to consider the samples of each bi ,for i=1,2,3,4,..M independently, in this case the sample that appears most frequently is the MAP estimate.

In general, if Gibbs coupler is used to obtain perfect samples in the multiuser detection, there are actually two ways to obtain i.i.d samples. In the first way, an independent gibbs coupler is used to draw each sample. Though these samples provide accurate results, there is bit more computation involved in obtaing them. In the second way, Gibbs coupler is only used as a guage to detect the burn-in period of the Gibbs sampler. More specifically,after obtaining a perfect sample using

Gibbs coupler, we can switch to the Gibbs sampler using the obtained perfect samples, as an initial state.And once the samples are obtained, Bayesian estimators MAP and MPM can be computed.

With these two estimators and the above two ways of generating samples, four detectors can be defined according to [3]

MAP detector using only Gibbs Coupler

MAP detector using both Gibbs Coupler and Gibbs sampler

MPM detector using only Gibbs Coupler

MPM detector using both Gibbs Coupler and Gibbs sampler

7. Experiments and results

A series of experiments were conducted to demonstrate the performance of the proposed detectors and to compare them with the performance of already existing techniques. In the first two experiments, the proposed detectors on the systems with negative cross-correlations are studied. In these two experiments, a 31 bit Gold sequence was used as the spreading code of 31 user system. There was equal power for the users in the first experiment. Under different Signal to noise ratios (SNRs), bit error rates (BERs) of 3, 4 detectors are examined. And the detectors used 300 samples in formulating the decisions. The results of the first user are shown in the following graph diagram. The performance of decorrelating detector and multistage detector is also shown in the graph. We can see that MAP using GCGS and MPM using GCGS curves almost overlap which indicate that the performance of these two detectors is almost similar. Additionally, the bit error rates of these two detectors is almost same as the bit error rate of a single user, especially at high signal to noise ratios. Compared with other existing detectors, the MAP using GCGS and MPM using GCGS perform better.

The following are the bit error rates of the proposed detectors of the first user as functions of signal to noise ratios.

Fig: There are 31 users with equal power.

In the second experiment, the near-far effect in the above 31 user system is studied. Here the Signal to noise ratio of the first user was fixed at 8 dB and for the remaining 30 users, it was allowed to vary from -10 dB below to 6dB above the first user. Then again the bit error rates of MAP using GCGS and MPM using GCGS were examined. The results are shown in the following graph.

Fig: There are 31 users and the signal to noise ratio of the first user is 8dB

We can notice that though the BER of decorrelator is too far away from the bound. As the decorrelator is near- far resistant, the bit error rates of the decorrelator do not change with the change in the interference strength. The other detectors perform very well than the decorrelator. We can observe that the two proposed Bayesian detectors have lower bit error rates than the two multistage detectors throughout the region that is tested.

In the next two experiments that are conducted, there were four users. 11 samples were recorded throughout these two experiments for Monte Carlo computation. First, the four users were given equal power. For various SNRs, the bit error rates of MAP using Gibbs coupler and MPM using Gibbs coupler and MAP using Gibbs sampler were evaluated of the first user. The results demonstrated that the bit error rate of MAP Gibbs coupler detector is slightly better than that of MPM Gibbs coupler and MAP GCGS detectors and that its performance almost overlaps with that of the optimum detector. Though the performance of multistage detectors is better than the decorrelator, it is lower than that of the proposed detectors.

8. Conclusion

In this paper, perfect sampling methods are reviewed with the emphasis being given to CFTP and its extension Gibbs coupler. The applications of perfect sampling in signal processing are discussed. Multiuser detection scheme using Gibbs coupler is mainly focused. It is shown that the performance of multiuser detector using Gibbs coupler was better than that of the existing multiuser detectors. There is a great scope for perfect sampling in the signal processing field, but an important weakness of the current perfect sampling algorithms is that they cannot meet the deadlines, so in theory, they cannot be applied to sequential signal processing. But hopefully this may change in the near future because of the extensive research going in the field of signal processing using perfect sampling.