Robust estimation of structured covariance matrices

In the context of the narrowband array processing problem, robust methods for accurately estimating the spatial correlation matrix using a priori information about the matrix structure are developed. By minimizing the worse case asymptotic variance, robust, structured, maximum-likelihood-type estimates of the spatial correlation matrix in the presence of noises with probability density functions in the ∈-contamination and Kolmogorov classes are obtained. These estimates are robust against variations in the noise's amplitude distribution. The Kolmogorov class is demonstrated to be the natural class to use for array processing applications, and a technique is developed to determine exactly the size of this class. Performance of bearing estimation algorithms improves substantially when the robust estimates are used, especially when nonGaussian noise is present. A parametric structured estimate of the spatial correlation matrix that allows direct estimation of the arrival angles is also demonstrated     

Computationally efficient maximum likelihood estimation ofstructured covariance matrices

By invoking the extended invariance principle (EXIP), we present herein a computationally efficient method that provides asymptotic (for large samples) maximum likelihood (AML) estimation for structured covariance matrices and is referred to as the AML algorithm. A closed-form formula for estimating the Hermitian Toeplitz covariance matrices that makes AML computationally simpler than most existing Hermitian Toeplitz matrix estimation algorithms is derived. Although the AML covariance matrix estimator can be used in a variety of applications, we focus on array processing. Our simulation study shows that AML enhances the performance of angle estimation algorithms, such as MUSIC, by making them very close to the corresponding Cramer-Rao bound (CRB) for uncorrelated signals. Numerical comparisons with several structured and unstructured covariance matrix estimators are also presented     

Penalized maximum-likelihood image reconstruction usingspace-alternating generalized EM algorithms

Most expectation-maximization (EM) type algorithms for penalized maximum-likelihood image reconstruction converge slowly, particularly when one incorporates additive background effects such as scatter, random coincidences, dark current, or cosmic radiation. In addition, regularizing smoothness penalties (or priors) introduce parameter coupling, rendering intractable the M-steps of most EM-type algorithms. This paper presents space-alternating generalized EM (SAGE) algorithms for image reconstruction, which update the parameters sequentially using a sequence of small "hidden" data spaces, rather than simultaneously using one large complete-data space. The sequential update decouples the M-step, so the maximization can typically be performed analytically. We introduce new hidden-data spaces that are less informative than the conventional complete-data space for Poisson data and that yield significant improvements in convergence rate. This acceleration is due to statistical considerations, not numerical overrelaxation methods, so monotonic increases in the objective function are guaranteed. We provide a general global convergence proof for SAGE methods with nonnegativity constraints.     

Simple maximum-likelihood estimator of structured covariance parameters

The simple maximum-likelihood estimator of signal and noise powers for a full-rank structured covariance matrix model is derived. The performances of the presented estimator are compared with the Cramer-Rao lower bound.<>     

Estimation of structured covariance matrices

Covariance matrices from stationary time series are Toeplitz. Multichannel and multidimensional processes have covariance matrices of block Toeplitz form. In these cases and many other situations, one knows that the actual covariance matrix belongs to a particular subclass of covariance matrices. This paper discusses a method for estimating a covariance matrix of specified structure from vector samples of the random process. The theoretical foundation of the method is to assume that the random process is zero-mean multivariate Gaussian, and to find the maximum-likelihood covariance matrix that has the specified structure. An existence proof is given and the solution is interpreted in terms of a minimum-entropy principle. The necessary gradient conditions that must be satisfied by the maximum-likelihood solution are derived and unique and nonunique analytic solutions for some simple problems are presented. A major contribution of this paper is an iterative algorithm that solves the necessary gradient equations for moderate-sized problems with reasonable computational ease. Theoretical convergence properties of the basic algorithm are investigated and robust modifications discussed. In doing maximum-entropy spectral analysis of a sine wave in white noise from a single vector sample, this new estimation procedure causes no splitting of the spectral line in contrast to the Burg technique.     

On maximum-likelihood estimation of clock offset

Delay measurements from timing message exchanges between two clocks produce a maximum-likelihood estimator (MLE) of the clock offset when fixed delays in each direction are equal and unknown, and variable delays in each direction have an exponential distribution with an unknown mean. It is shown that the MLE corresponds to a previously proposed estimator of clock offset. The ML interpretation of the estimator provides further insight and motivation for its use.     

Multimode power modeling and maximum-likelihood estimation

It is known that circuits exhibit multiple modes of power consumption due to various factors such as the presence of many feedback (or sequential) elements, RAM, large size, etc. Previous power-estimation techniques have largely ignored this fact. For example, Monte Carlo simulation-based power estimators tend to produce estimates for the average power consumption that corresponds only to the most probable power mode of the circuit. This can be a cause for trouble later in the design step. The aim of this paper is twofold. First, an algorithm is proposed that estimates the total number of power modes of a circuit based on simulated data. This is then followed by a maximum-likelihood estimation procedure that produces the average values of the power modes along with their probabilities of occurrence. Theoretical ideas are supported by experimental results for ISCAS '85 benchmark circuits and a large industrial circuit. The proposed method is shown to perform well by capturing the multiple power modes for both large and small circuits even when the number of simulated samples is small while the Monte Carlo estimator does not. We conclude with a note that the proposed method is also applicable to other model selection problems in VLSI.     

Kullback proximal algorithms for maximum-likelihood estimation

Accelerated algorithms for maximum-likelihood image reconstruction are essential for emerging applications such as three-dimensional (3-D) tomography, dynamic tomographic imaging, and other high-dimensional inverse problems. In this paper, we introduce and analyze a class of fast and stable sequential optimization methods for computing maximum-likelihood estimates and study its convergence properties. These methods are based on a proximal point algorithm implemented with the Kullback-Liebler (KL) divergence between posterior densities of the complete data as a proximal penalty function. When the proximal relaxation parameter is set to unity, one obtains the classical expectation-maximization (EM) algorithm. For a decreasing sequence of relaxation parameters, relaxed versions of EM are obtained which can have much faster asymptotic convergence without sacrifice of monotonicity. We present an implementation of the algorithm using More's (1983) trust region update strategy. For illustration, the method is applied to a nonquadratic inverse problem with Poisson distributed data     

Computation of transform domain covariance matrices

It is often of interest in applications to compute the covariance matrix of a random process transformed by a fast unitary trasform. Here, the recursive definition of fast unitary transforms [1] is used to derive recursive relations for the covariance matrices of the transformed process. These relations lead to fast methods of computation of covariance matrices and to substantial reductions of the number of arithmetic operations required.     

Decision-directed maximum-likelihood estimation of OFDM framesynchronisation offset

The authors propose a method to estimate the synchronisation offset for orthogonal frequency division multiplexing (OFDM) frame alignment without resort to pilot tones. A decision-directed maximum-likelihood estimation of frame synchronisation offset is derived, and the performance of the proposed scheme is confirmed by computer simulation for QAM systems     

Hypothesis testing of complex covariance matrices

Letcal ybe a mean zero complex stationary Gaussian signal process depending on a vector parametertheta prime = { theta_{1}, theta_{2}, theta_{3} }whose components represent parameters of the covariance function R(r) ofcal y. These parameters are chosen astheta_{1} = R(0), theta_{2} = |R( tau )| /R(0), theta_{3} =phase ofR( tau), and they are simply related to the parameters of the spectral density ofcal y. This paper is concerned with the determination of most powerful (MP) tests that distinguish between random signals having different covariance functions. The tests are based uponNcorrelated pairs of independent observations oncal y. Although the MP test that distinguishes betweentheta = theta_{o}and the alternative hypothesistheta = theta_{1}has been solved previously [11], the problem of identifying the random signals is often complicated by the fact that the signal powertheta_{1} = R(0)is not a distinguishing feature of either hypothesis. This paper determines the MP invariant test that delineates between the composite hypothesislambda equiv R( tau)/R(0) = lambda_{0}and the composite alternativelambda = lambda_{1}. In addition, the uniformly MP invariant test that distinguishes between the composite hypothesestheta_{2} <_{=} | lambda_{o} |andtheta_{2} > | lambda_{0} |has also been found. In all cases, exact probability distributions have been obtained.     

Comparison on maximum-likelihood sequence estimation schemesincorporating carrier phase estimation

This paper compares the following two maximum likelihood sequence estimation schemes incorporating carrier phase estimation for coded MPSK: (1) the respective-state channel estimation and (2) the multiple differential detection. This paper confirms by analysis and computer simulation that both schemes have similar performance in the absence of intersymbol interference     

Iterative maximum-likelihood sequence estimation for space-timecoded systems

In previous work on decoding space-time codes, it is either assumed that perfect channel state information (CSI) is present, or a channel estimate is obtained using pilot symbols and then used as if it were perfect to extract symbol estimates. In the latter case, a loss in performance is incurred, since the resulting overall receiver is not optimal. We look at maximum-likelihood (ML) sequence estimation for space-time coded systems without assuming CSI. The log-likelihood function is presented for both-quasi-static and nonstatic fading channels, and an expectation-maximization (EM)-based algorithm is introduced for producing ML data estimates, whose complexity is much smaller than a direct evaluation of the log-likelihood function. Simulation results indicate the EM-based algorithm achieves a performance close to that of a receiver which knows the channel perfectly     

Pilot-assisted maximum-likelihood frequency-offset estimation for OFDM systems

For orthogonal frequency-division multiplexing (OFDM) signals that suffer from frequency-selective fading, we derive the maximum-likelihood (ML) pilot-assisted carrier frequency offset (CFO) estimate and show that most proposals based on repetitive pilot symbols did not use the complete set of sufficient statistics. We convert the problem of obtaining the ML solution from searching exhaustively over the entire uncertainty range to that of solving a spectrum polynomial, thereby greatly reducing the computational load. By properly truncating the polynomial, we obtain a closed-form expression for the corresponding zeros so that the root-searching procedure is greatly simplified. The complexity of locating the desired root is further reduced at almost no expense of performance degradation by an alternate algorithm that uses the fact that the solution is related to the root of a special factor of the polynomial. This alternate method is very attractive for its simplicity and excellent performance that, even at low signal-to-noise ratios (SNRs), is very close to the corresponding Crame/spl acute/r-Rao lower bound. A detailed analysis of the mean-squared error performance is presented and the analysis is validated by simulations.     

Capon estimation of covariance sequences

Estimating the covariance sequence of a wide-sense stationary process is of fundamental importance in digital signal processing (DSP). A new method, which makes use of Fourier inversion of the Capon spectral estimates and is referred to as theCapon method, is presented in this paper. It is shown that the Capon power spectral density (PSD) estimator yields an equivalent autoregressive (AR) or autoregressive moving-average (ARMA) process; hence, theexact covariance sequence corresponsing to the Capon spectrum can be computed in a rather convenient way. Also, without much accuracy loss, the computation can be significantly reduced via an approximate Capon method that utilizes the fast Fourier transform (FFT). Using a variety of ARMA signals, we show that Capon covariance estimates are generally better than standard sample covariance estimates and can be used to improve performances in DSP applications that are critically dependent on the accuracy of the covariance sequence estimates.This work was supported in part by National Science Foundation Grant MIP-9308302, Advanced Research Project Agency Grant MDA-972-93-1-0015, the Senior Individual Grant Program of the Swedish Foundation for Strategic Research and the Swedish Research Council for Engineering Sciences (TFR).     

Joint maximum-likelihood parameter estimation for burst DSspread-spectrum transmission

We first derive the joint optimal maximum-likelihood (ML) estimator of the carrier phase, both Doppler shift and Doppler rate, and the spreading code delay for a short burst direct sequence/spread spectrum (DS/SS) transmission in the absence of the data modulation. The typical burst duration is three data bit periods (60 ms). The performance of the joint estimator is analytically derived separately for high and low carrier-to-noise ratio (CNR) values. A suboptimal ML estimator based on the method of averaged periodogram is proposed for the data modulation present case, allowing the joint estimation of the data bit values. Then the above parameters are assumed correctly estimated and a segmentation approach is adopted, deriving the optimal joint ML estimator for the bit synchronization epoch and data. Simulations show the joint estimators perform reliable down to a CNR of approximately 30 dB·Hz     

Exact and approximate maximum-likelihood parameter estimation forquasi-synchronous CDMA signals

In order to construct the optimal decorrelator for a quasi-synchronous (QS) code-division multiple-access receiver, it is necessary to estimate the user delays. However, in a QS system, it is shown that delay estimation is equivalent to estimating a parameter vector which is related linearly to the received signal. An exact maximum-likelihood (ML) solution using alternating maximization is first developed for joint estimation of the user delay vectors and amplitudes. Suboptimal recursive least squares (RLS) and least mean square algorithms are then presented which approximate the true ML solution. It is shown that the optimal decorrelator and demodulated symbols are also generated by the RLS algorithm. Simulation and analytical results are presented for the bit-error rate performance of the adaptive receiver, and the average squared error of the estimated delay vectors is compared with the Cramer-Rao bound     

NAR estimators of spatial covariance matrices for adaptive arraydetection

The theory of noise-alone-reference (NAR) power estimation is extended to the estimation of spatial covariance matrices. A NAR covariance estimator insensitive to signal presence is derived. The SNR (signal-to-noise ratio) loss incurred by using this estimator is independent of the input SNR and is less than that encountered with the maximum likelihood covariance estimator given that the same number of uncorrelated snapshots is available to both estimators. The analysis assumes first a deterministic signal. The results are extended and generalized to signals with unknown parameters or random signals. For the random signal case, generalized and quasi-NAR covariance estimators are presented