A novel approach is presented for the detection and localization of changing periodicities in symbolic sequences. Various symbolic sequences like DNA can be modelled as stochastic processes that exhibit time-varying cyclostation- arity. The coding regions of the DNA, for instance, exhibit statistical periodicity with period three. The complexity-regularized maximum-likelihood estimates are developed in this paper for the statistical period of symbolic sequences. The changing periodicities along the sequence are discovered by using sliding windows. A cumulative sum test is also presented to detect the change points. The formulation in this paper avoids any kind of numerical mapping for the symbolic DNA sequences and does not impose any algebraic structure.

We present a new approach to localizing an isotropic energy source using measurements from distributed sensors based on kernel averaging techniques. The location estimate is easily and efficiently calculated in a decentralized fashion. Statistical properties are derived for a very general measurement model. Experiments suggest that the proposed estimator is much more robust and exhibits better performance characteristics than the popular least squares estimator under a variety of conditions.

We give a unified presentation of the conditional importance sampling estimators. We show that they are always better than their nonconditional counterparts. We then present the large deviation theory associated with these estimators. In particular, we give conditional simulation distributions that are optimal in the sense that they are efficient. Interestingly enough, these distributions will not in general be the usual exponential shifts. We give examples showing how to use the theory developed

In this paper, we present a new class of importance sampling simulation distributions, the universal distributions. We show that these distributions 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.

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.

Few results are available in the literature on failure time (in contrast with long time average) analysis of the least mean square (LMS) adaptive algorithms (filters). Such analysis is extremely important when failure of the algorithm could cause failure of the entire system in which they are employed. A system may fail upon the first occurrence of a large error (any value far from 0), or upon staying far from 0 for a period of time (a clump of large errors). We use a Poisson approximation to study excursions (failure) of the LMS algorithm and its three signed variants. The distribution and the mean of the first excursion are approximated with the mean and distribution of an exponential distribution. The number of excursions in n units of time is approximated by a Poisson distribution. We also approximate the mean of an excursion length (clump size). The approximations are derived asymptotically as the excursion-defining set converges to the empty set, and as the algorithm step size converges to 0.

Blind simulation techniques are Monte Carlo simulation strategies that can be carried out with little or no knowledge of the underlying probability law. We first show (in the independent and identically distributed setting) that by a strategy of selectively throwing away data samples, we can achieve arbitrarily close to the optimal performance gains promised by the importance sampling strategy known as quick simulation. In our attempt to generalize our results to Markovian structures, we are led necessarily to a consideration of their regeneration structure and hence to a general consideration of regenerative processes. We derive several new large deviation results for these processes. Using these techniques we then demonstrate the same surprising results hold for many regenerative processes.

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.

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.>

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.>

Some extensions that allow new estimating and bounding techniques for certain sequences of random variables controlled by a large deviation principle are given. These results can be thought of as generalizations and extensions of the Chernoff bound used in communications theory.>

A recursive equation which 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). Local stability of the ODE implies weak convergence of the algorithm while instability of the differential equation implies nonconvergence of the parameter estimates. The analysis does not require continuity of the update equation, and the asymptotic distribution of the parameter trajectories for all stable cases (under some mild conditions) is shown to be an Ornstein-Uhlenbeck process. 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 generates known results for LMS, signed regressor, and signed error LMS and gives new stability criteria for the sign-sign algorithm.>

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.>

An asymptotic analysis based on large deviation theory is presented for three representative nonlinear receivers operating in the presence of Gaussian noise, namely radiometers, differential phase shift keying, and memoryless detectors. En route to the results an extension to the Toeplitz distribution theorem is proved. This extension provides the key to obtaining closed-form expressions for the exponential rate of decrease of the probability of error for the first two detector structures. The solution to the rate constant problem for the memoryless detector is then shown to be given by the solution to a certain nonlinear Hammerstein integral equation. Several examples are presented.>

It is shown how large-deviations theory can be applied to construct an asymptotically efficient simulation distribution for Monte Carlo simulation using the importance sampling technique. A sufficient and necessary condition is given for the asymptotic efficiency of the candidate simulation distributions. This is done in the multidimensional setting that is required by many practical simulation problems. The result obtained is applied primarily in two areas. First, the generalization of previous work dealing with functionals of Markov chains is discussed. A second area of application is the simulation of nonlinear systems with Gaussian inputs. As an example of a system with Gaussian inputs, the simulation of a digital communication channel with nonlinear ISI (intersymbol interference) characteristic of satellite data links is considered. In the case of linear ISI, the asymptotically efficient exponentially twisted distribution turns out to agree with a method previously proposed by D. Lu and K. Yao (1988). The large-deviations point of view provides some useful insight on how to extent the Lu and Yao method to nonlinear channels.>

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.>

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.>

A modified proof of T. Berger's (1971) abstract alphabet source coding with a fidelity criterion theorem is provided, utilizing a variant of a result from large deviation theory. This proof does not use an asymptotic equipartition property of any kind, thus providing what appears to be a more direct approach to this key result.>

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.>

The companding model for quantizer design and analysis has been widely applied in the scalar quantization case. However, if the signal to be quantized is a vector, then the optimum companding system can be designed for only a limited number of distributions. On the other hand, multidimensional piecewise linear companders can be designed for any signal density, generating quantizers that are uniform on each region of the compander. These systems, while not optimal, can have asymptotic performance arbitrarily close to the optimum. Their analysis and implementation can be simpler than those of optimal systems. Piecewise linear companders for asymptotic multidimensional quantization are analyzed, and a method for their design is suggested.>

The companding model for quantizer design and analysis has been frequently used in various instances. However, if the signal to be quantized is a vector, then the optimum companding system can be designed for only a limited number of distributions. On the other hand, piecewise linear companders can be designed for any signal density, generating quantizers that are uniform on each region of the compander. These systems, while not optimal, can have performances which are close to the optimum, and their analysis and implementation can be simpler than those of optimal systems. In this paper we analyze piecewise linear companders for asymptotic multidimensional quantization, and we suggest methods for their design.

A proof of Shannon's source coding theorem is given using results from large deviation theory. In particular Sanov's theorem on convergence rates for empirical distributions is invoked to obtain the key large deviation result. This result is used directly to prove the source coding theorem for discrete memoryless sources. It is then shown how this theorem can be extended to ergodic Polish space valued sources and continuous distortion measures.

Previous literature on detector design has presented many tractable results using efficacy as a performance functional, which is a small signal or local approach. Some nonlocal issues of memoryless detection are considered. We argue that the asymptotic exponential rate of decrease of error probabilities, or Bayes risk, provides the appropriate asymptotic measure of performance. A main contribution is the development of an approximation for nonlocal design that retains the tractability of the efficacy approach. We have proved the local consistency of our approximation. Also, as a consequence of the analysis, new proofs for Pitman-Noether-like theorems have been obtained.

Explicit expressions are derived for derivatives at zero lag of the mean-square prediction error for a class of random processes that includes those with rational power spectra. A simple random process not in the class is demonstrated. A sufficient condition for membership in the class is given.

Approximate performance results are obtained for optimal detection of weak discrete time signals. The analysis parallels the "locally optimum" approach for detector design and is based on a small-signal Taylor series approximation to the Chernoff error probability bounds.

In many applications it is necessary to digitize data, knowing only that later on some random function of the digitized data will be of interest. This problem is investigated when the data digitizers are allowed to be multidimensional, i.e., they map aK-dimensional data vector into one of a set ofK-dimensional output vectors. It is shown that very complex distortion measures arise naturally. Results are given for the error measure defined as the squared value of the difference between the function of the digitized data and the function of the undigitized data.

A necessary and sufficient condition is presented for the normalized asymptoticrth power distortion of a mismatched multidimensional quantizer to converge to a certain optimum constant known as Bennett's integral. The dimensionality of our results is allowed to approach infinity in order to make some universal source coding comparisons to quantization theory.

It is assumed that a receiver's input is a digital signal corrupted by white Gaussian noise. The information symbols in the digital data stream are in general allowed to be correlated. The small signal maximum likelihood estimate of the channel impulse response is derived. We show that the estimator problem leads to a generalized eigenvalue problem. An example is presented.

In this paper, a novel quantization scheme-adaptive companded pulse code modulation (ACPCM)-is proposed. It is shown that, for fine quantization of analog signals, ACPCM will outperform the widely used PCM and DPCM in the sense of minimizing the meansquared quantizing error. For autoregressive (AR)signals, ACPCM is shown to reduce to DPCM. Some examples and simulations are given to demonstrate the method.

Companding is a widely used method of implementing nonuniform quantizers. There are, however, problems in extending this technique to the multidimensional case. It is known, for example, that not all input probability densities can be quantized optimally in this fashion. In this note we characterize the class of probability density functions that can be optimally quantized with a multidimensional companding-type implementation.

A simple relative frequency type estimator of the prior probability in a mixture of two known density functions is presented. Examples are given demonstrating the ease of design and implementation of this estimator structure.

The twin tools of asymptotic quantization theory and rate-distortion theory are used to find an expression for the approximate total mean-squared distortion of the series connection of a nonuniform quantizer and a noisy channel. The nonuniform quantizer is modeled as a compressor followed by a uniform quantizer. The approximate total mean-squared error distortion is minimized over a class of parameterized compressor characteristics for input processes whose univariate probability density functions are members of the generalized Gaussian family.

This paper considers the problems associated with computing optimal minimum mean-square error quantizers. Most computational methods in current use are iterative. These iterative schemes are extremely sensitive to initial conditions. Various methods of obtaining good initial conditions are presented and discussed.

Asymptotic properties of therth power distortion measure associated with quantizedk-dimensional random variables are considered. Subject only to a moment condition, it is shown that the infimum over allNlevel quantizers of the quantityN^{r/k}times therth power average distortion converges to a finite constant asN \rightarrow \infty.

Two results in minimum mean square error quantization theory are presented. The first section gives a simplified derivation of a well-known upper bound to the distortion introduced by ak-dimensional optimum quantizer. It is then shown that an optimum multidimensional quantizer preserves the mean vector of the input and that the mean square quantization error is given by the sum of the component variances of the input minus the sum of the variances of the output.

The problem of implementing multidimensional quantizers is discussed. A general equation is derived that can be used to evaluate the performance of multidimensional compandors. It is demonstrated that the optimal compandor must be conformal almost everywhere. An example is given to show that asymptotically optimal performance could be obtained through nonconformal companding schemes. Random quantizers are discussed and two techniques are evaluated for reducing memory and computation time in the implementation of such devices.

Upper bounds to the asymptotic performance of block quantizers with difference distortion measures are derived. In many eases, these upper bounds approach known lower bounds as the block length of the quantizer approaches infinity. A condition for the optimal point density function of the output levels is derived. It is shown to particularize to a known result of Gersho. The behavior of the bounds for large block lengths is investigated.

Some properties of the optimal mean-square error uniform quantizer are treated. It is shown that the mean-square error (mse) is given by the input variance minus the output variance. Furthermore\lim_{N \rightarrow \infty}mse/(\Delta^{2}/12) \geq 1, whereNis the number of output levels and\Delta(a function ofM) is the step size of the uniform quantizer, with equality when the support of the random variable is contained in a finite interval. A class of probability densities is given for which the above limit is greater than one. It is shown that\lim_{N \rightarrow \infty}N^{2} \cdotmse=(b-a)^{2}/12, where(b-a)is the measure of the smallest interval that contains the support of the input random variable.

For a general class of optimal quantizers the variance of the output is less than that of the input. Also the mean value is preserved by the quantizing operation.

The problem of quantizing two-dimensional Gaussian random variables is considered. It is shown that, for all but a finite number of cases, a polar representation gives a smaller mean square quantization error than a Cartesian representation. Applications of the results to a transform coding scheme known as spectral phase coding are discussed.

The problem of quantizing a two-dimensional random variable whose bivariate density has circular symmetry is considered in detail. Two quantization methods are considered, leading to polar and rectangular representations. A simple necessary and sufficient condition is derived to determine which of these two quantization schemes is best. If polar quantization is deemed best, the question arises as to the ratio of the number of phase quantizer levels to that or magnitude quantizer levels when the product of these numbers is fixed. A simple expression is derived for this ratio that depends only upon the magnitude distribution. Several examples of common circularly symmetric bivariate densities are worked out in detail using these expressions.