Signal Processing - July 2017 - 64

target evaluations, the DM estimator is computationally more
large weights in Figure 1(b). Figure 1(d) and 1(e) use the conexpensive with respect to the number of proposal evaluations.
cept of MIS, i.e., there we use two proposal pdfs. The weights
In particular, s-MIS and DM require N and N 2 evaluations,
in Figure 1(d) are calculated using the standard formulation
respectively. Therefore, in scenarios where
of weight update from (15), while in Figthe number of proposals N is large, the
ure 1(e), they are computed according to
All of the AIS methods
O ^ N 2 h in the number of proposal evalua(16). It is clear that a smaller variance of the
presented and the
tions can be prohibitive. Alternative effiweights is achieved with the DM approach.
cient solutions have recently been devised to
Finally, the validity of the possible difconsiderations performed
mitigate this excess of computational load
ferent weighting schemes for MIS is justiare directly applicable to
[26], [27].
multidimensional-complex fied in [25] by using the concept of a proper
Figure 1 illustrates the processes of samset of weighted samples. More precisely, the
target densities.
pling and weighting based on the different
suitability of a particular MIS scheme is
methods explained in this section. More
guaranteed if the nonnormalized estimator
specifically, Figure 1(a) displays the generated samples and
ItN and the normalizing constant estimator Zt are unbiased and
associated weights when sampling from the target distribution
consistent, which also implies that the self-normalized estimais possible. We observe that all of the weights are equal in this
tor IuN is consistent.
case. For both Figure 1(b) and (c), the generation of samples is
performed using a single proposal pdf. However, the proposal
Adaptive importance sampling
pdfs, plotted with dashed lines, are differently located, and
therefore one can appreciate how the second choice is more
The basics of AIS
appropriate by observing the variability of the weight values.
The AIS methodology is based on an iterative process for
Note that the scale of the vertical axes is different to show the
gradual evolution of the single or multiple proposal densities

0.25

0.25

1.4
1.2

0.2

0.2

1
0.15

0.8

0.15

0.1

0.6

0.1

0.4

(a)

(b)
3

20

15

5

10

(c)

0.25

2.5

0.2

2

0.15

1.5

(d)

20

15

5

10

0

-5

-10

-20

20

15

10

5

0

0

-5

0

-10

0.05

-15

0.5

-15

0.1

1

-20

0

-5

-10

-15

0

20

15

10

5

0

-5

-10

-15

-20

0

20

15

10

5

0

-5

-10

-15

-20

0

0.05

0.2

-20

0.05

(e)

FIGURE 1. The approximations of the target pdf, r (x) , by different discrete probability distributions (displayed by thin bars with weights corresponding
to heights of the bars). The target pdfs are shown by solid lines, while the proposal pdfs are plotted with dashed lines. (a) The MC sampling directly from
the target, the ideal situation: an approximation with equally weighted samples, as they are drawn directly from the target. (b) IS, single-proposal pdf,
and (c) IS, single-proposal pdf [with a better location than that in (b)]. (b) and (c) are approximations with IS and a single proposal to show the effect of
the location: A better proposal placement leads to more uniform weights. (d) MIS with standard weights, and (e) MIS with DM weights. (d) and (e) are
approximations with MIS and two proposals to show the effect of the choice of the weighting scheme: The DM approach leads to more uniform weights
than the standard approach.

64

IEEE SIGNAL PROCESSING MAGAZINE

|

July 2017

|
Table of Contents for the Digital Edition of Signal Processing - July 2017
