Quick simulation of detector error probabilities in the presence ofmemory and nonlinearity

One would like to compare and analyze digital communication systems based upon their overall probability of error. Unfortunately, easily evaluated closed form expressions for these probabilities are almost impossible to derive due to the complexity of the stochastic systems usually encountered. Hence, one must often resort to simulation to obtain the desired quantities. The most obvious technique is Monte Carlo simulation, which directly counts the number of errors in repeated trials. The problem is that error probabilities are usually quite small, requiring numerous simulation runs to sufficiently “hit” the rare event to gain adequate knowledge of its statistics. This places severe demands on the computer's random number generator. Importance sampling strategies simulate under altered input signal distributions (e.g., translation or stretching) so as to “speedup” convergence of the error estimators. The authors discuss a speedup technique termed quick simulation based upon results in large deviation theory. The quick simulation method is shown to compare favorably with three other importance sampling techniques for simulating a simple nonlinear system with memory     

Poisson approximation for excursions of adaptive algorithms with alattice state space

This paper analyzes excursions of adaptive algorithms (such as the LMS) with a lattice state space. Under certain conditions on the input and disturbance statistics, the parameter estimate error forms a Markov chain. The approximations are valid if this chain has a strong tendency toward an equilibrium point. The distribution of the number of excursions in n units of time is approximated by a Poisson distribution. The mean and distribution of the time of the occurrence of the first excursion are approximated by those of an exponential distribution. Expressions for the error in the approximations are also derived. The approximations are shown to hold asymptotically as the excursion-defining set converges to the empty set. All the parameters required for the approximations and all expressions for the error in the approximations are calculable in a relatively straightforward manner     

Weak convergence and local stability properties of fixed step sizerecursive algorithms

A recursive equation that subsumes several common adaptive filtering algorithms is analyzed for general stochastic inputs and disturbances by relating the motion of the parameter estimate errors to the behavior of an unforced deterministic ordinary differential equation (ODE). The ODEs describing the motion of several common adaptive filters are examined in some simple settings, including the least mean square (LMS) algorithm and all three of its signed variants (the signed regressor, the signed error, and the sign-sign algorithms). Stability and instability results are presented in terms of the eigenvalues of a correlation-like matrix. This generalizes known results for LMS, signed regressor LMS, and signed error LMS, and gives new stability criteria for the sign-sign algorithm. The ability of the algorithms to track moving parameterizations can be analyzed in a similar manner, by relating the time varying system to a forced ODE. The asymptotic distribution about the forced ODE is an Ornstein-Uhlenbeck process, the properties of which can be described in a straightforward manner     

Asymptotically optimal quantizers for detection of i.i.d

The asymptotic probability of error for quantization in maximum-likelihood tests is analyzed. The authors assume quantizers with large numbers of levels generated from a companding function. A theorem that relates the companding function to the asymptotic probability of error is proved. The companding function is then optimized     

Analysis of momentum adaptive filtering algorithms

This article analyzes the momentum LMS algorithm and other momentum algorithms using asymptotic techniques that provide information regarding the almost sure behavior of the parameter estimates and their asymptotic distribution. The analysis does not make any assumptions on the autocorrelation function of the input process     

A note on the absolute epsilon entropy

A novel characterization of the absolute epsilon entropy of an ergodic information source is presented. This characterization allows one to derive a new lower bound to this quantity, which is shown to be tight in some interesting special cases     

Estimating random integrals from noisy observations: samplingdesigns and their performance

The problem of estimating a weighted average of a random process from noisy observations at a finite number of sampling points is considered. The performance of sampling designs with optimal or suboptimal, but easily computable, estimator coefficients is studied. Several examples and special cases are studied, including additive independent noise, nonlinear distortion with noise, and quantization noise     

Minimax estimation of unknown deterministic signals in colorednoise

The estimation of a deterministic signal corrupted by random noise is considered. The strategy is to find a linear noncausal estimator which minimizes the maximum mean square error over an a priori set of signals. This signal set is specified in terms of frequency/energy constraints via the discrete Fourier transform. Exact filter expressions are given for the case of additive white noise. For the case of additive colored noise possessing a continuous power spectral density, a suboptimal filter is derived whose asymptotic performance is optimal. Asymptotic expressions for the minimax estimator error are developed for both cases. The minimax filter is applied to random data and is shown to solve asymptotically a certain worst-case Wiener filter problem     

On the Monte Carlo simulation of digital communication systems in Gaussian noise

We consider the general problem of the simulation of highly reliable systems operating in the presence of Gaussian noise. Our methodology uses importance sampling which has been shown to be a particularly effective method in the general discipline of rare-event simulation. The methods we propose are optimal in a certain sense, i.e., they are efficient. We also give a new class of simulation distributions that are universally efficient in the sense that they depend only on a single scalar parameter, regardless of the dimensionality of the underlying system or of the error sets to be simulated.     

Mixed time scale recursive algorithms

We investigate the behavior of certain types of mixed time scale adaptive algorithms. These systems comprise a “fast” or quickly changing algorithm mutually coupled to a “slow” or slowly changing algorithm. They arise naturally in a variety of adaptive environments such as in IIR system identification, the training of recurrent neural networks, decision feedback equalization, and others. [These algorithms (despite their title) should not be confused with the mixed time scales of wavelet transforms or other algorithms associated with multiresolution signal processing]. We give conditions for when the system can be analyzed from the framework of a simpler “frozen state” system. This analysis extends some of the previous work of Solo (1995) and his coworkers