Many tasks in statistical signal processing such as estimation, detection, or model selection revolve around the processing of likelihood functions or a posteriori densities. In difficult problems, these functions are high dimensional and nonlinear, and the standard tasks of maximization or integration that involve them are very difficult to implement. In situations when the systems and signals are time-varying and are described by nonlinear equations, the problem can be even more difficult because the typical operations of filtering, prediction, smoothing have to be carried out on-line. In all these problems, the high-dimensionality of the space of the unknowns and the nonlinearity of the used models are a major challenge for accurate signal processing. If in addition, the used models are described by a non-Gaussian and/or non-additive noise, the difficulties are even more pronounced.

Monte Carlo based methods have become an important tool in addressing hard problems in statistical signal processing. These methods are in general computationally intensive, but due to the advances of computer technology in the past years and their inherent parallelism, the interest in these approaches has been steadily increasing. In brief, the methods are based on generating samples from desired distributions or functions, which are then used for estimation of unknowns or detection of signals. Importance sampling is a Monte Carlo method that is used for approximating densities of interest by samples that are drawn from another density. This method turns out to be very useful in Monte Carlo integration and optimization. The tutorial is focused on the use of importance sampling to statistical signal processing. There are two standard scenarios in which this methodology is applied. One allows for batch processing, and the other requires sequential (on-line) processing of the data. The tutorial therefore is composed of two parts, of which Part I describes importance sampling used in batch processing, and Part II focuses on importance sampling used in sequential methods.

In Part I of the tutorial the basic concepts of importance sampling for batch signal processing will be discussed. Issues such as the choice of the importance function for a simple implementation and a reduced computational load is addressed. Then, general classes of signal processing problems for which the approach is viable are summarized. Finally, applications and actual results for the optimal solution of such difficult problems as sinusoidal frequency estimation, direction of arrival estimation, and more general nonlinear problems are given. In Part II of the tutorial, three topics of sequential importance sampling will be addressed: theory, practical issues, and applications. First, the equations on which the theory of sequential importance sampling is based will be derived. Then, some practical and very important issues of the method that lead to its improved performance will be investigated. Finally, applications of sequential importance sampling that include detection and estimation in communications, target tracking, navigation, and recursive spectrum estimation will be examined.