A generalized Levinson algorithm for covariance extension with application to multiscale autoregressive modeling

Efficient computation of extensions of banded, partially known covariance matrices is provided by the classical Levinson algorithm. One contribution of this paper is the introduction of a generalization of this algorithm that is applicable to a substantially broader class of extension problems. This generalized algorithm can compute unknown covariance elements in any order that satisfies certain graph-theoretic properties, which we describe. This flexibility, which is not provided by the classical Levinson algorithm, is then harnessed in a second contribution of this paper, the identification of a multiscale autoregressive (MAR) model for the maximum-entropy (ME) extension of a banded, partially known covariance matrix. The computational complexity of MAR model identification is an order of magnitude below that of explicitly computing a full covariance extension and is comparable to that required to build a standard autoregressive (AR) model using the classical Levinson algorithm.     

On the rationale of maximum-entropy methods

We discuss the relations between maximum-entropy (MAXENT) and other methods of spectral analysis such as the Schuster, Blackman-Tukey, maximum-likelihood, Bayesian, and Autoregressive (AR, ARMA, or ARIMA) models, emphasizing that they are not in conflict, but rather are appropriate in different problems. We conclude that: 1) "Orthodox" sampling theory methods are useful in problems where we have a known model (sampling distribution) for the properties of the noise, but no appreciable prior information about the quantities being estimated. 2) MAXENT is optimal in problems where we have prior information about multiplicities, but no noise. 3) The full Bayesian solution includes both of these as special cases and is needed in problems where we have both prior information and noise. 4) AR models are in one sense a special case of MAXENT, but in another sense they are ubiquitous in all spectral analysis problems with discrete time series. 5) Empirical methods such as Blackman-Tukey, which do not invoke even a likelihood function, are useful in the preliminary, exploratory phase of a problem where our knowledge is sufficient to permit intuitive judgments about how to organize a calculation (smoothing, decimation, windows, prewhitening, padding with zeroes, etc.) but insufficient to set up a quantitative model which would do the proper things for us automatically and optimally.     

Notes on maximum-entropy processing (Corresp.)

Maximum-entropy processing is a method for computing the power density spectrum from the firstNlags of the autocorrelation function. Unlike the discrete Fourier transform, maximum-entropy processing does not assume that the other lag values are zero. Instead, one mathematically ensures that the fewest possible assumptions about unmeasured data are made by choosing the spectrum that maximizes the entropy for the process. The use of the maximum entropy approach to spectral analysis was introduced by Burg [1]. In this correspondence, the authors derive the maximum-entropy spectrum by obtaining a spectrum that is forced to maximize the entropy of a stationary random process.     

A computationally efficient multivariate maximum-entropy density estimation (MEDE) technique

Density estimation is the process of taking a set of multivariate data and finding an estimate for the probability density function (pdf) that produced it. One approach for obtaining an accurate estimate of the true density f(x) is to use the polynomial-moment method with Boltzmann-Shannon entropy. Although rigorous mathematically, the method is difficult to implement in practice because the solution involves a large set of simultaneous nonlinear integral equations, one for each moment or joint moment constraint. Solutions available in the literature are generally not easily applicable to multivariate data, nor computationally efficient. In this paper, we take the functional form that was developed in this problem and apply pointwise estimates of the pdf as constraints. These pointwise estimates are transformed into basis coefficients for a set of Legendre polynomials. The procedure is mathematically similar to the multidimensional Fourier transform, although with different basis functions. We apply this technique, called the maximum-entropy density estimation (MEDE) technique, to a series of multivariate datasets.     

Multidimensional Polynomial Transform Algorithm For Multidimensional Discrete Hartley Transform

In this paper, we present an index permutation-based fast algorithm for the multidimensional discrete Hartley transform (MD-DHT). By reordering the MD-DHT input sequence, we first convert the MD-DHT into a multiple sum that contains a number of one-dimensional discrete W transforms (1D-DWTs). We then use a combination of the 1D-DWTs and the multidimensional polynomial transform to compute the multiple sum. It is shown that the number of multiplications and additions required for the proposed algorithm are approximately 1/m and 2m+1/3m times that of the commonly used row-column DHT method, respectively. The developed algorithm is also simple in structure and easy to realize in programming.     

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

Constrained estimates of multipath covariance

When multipath propagation occurs, the covariance among signals traveling along rays emanating from a common source is expected to be larger than the covariance between signals generated by independent sources. Several data adaptive constrained estimates of the covariance are derived by the author as bilinear forms and some simulations are presented. The ability of a bilinear form to distinguish a 0-dB (relative to uncorrelated noise) correlated arrival pair from a 0-dB independent source is studied using an expected narrowband cross-spectral matrix corresponding to a simulated acoustic field with a 32-element line array at Nyquist spacing. An adaptive set of filter vectors obtained from the classical minimum variance problem are found to minimize sidelobe interference to 2 dB above the background noise level at the cost of reduced peaks having an 18-dB output above the uncorrelated background     

Multicomponent Multidimensional Signals

In this brief paper, we extend the notion of multicomponent signal into multiple dimensions. A definition for multidimensional instantaneous bandwidth is presented and used to develop criteria for determining the multicomponent nature of a signal. We demonstrate application of the criteria by testing the validity of a multicomponent interpretation for a complicated nonstationary texture image.     

Multidimensional spectral estimation

Methods of multidimensional power spectral estimation are reviewed. Seven types of estimators are discussed: Fourier, separable, data extension, MLM, MEM, AR, and Pisarenko estimators. Particular emphasis is given to MEM where current research is quite active. Theoretical developments are reviewed and computational algorithms are discussed.     

Multidimensional fast-Fourier-transform algorithm

A multidimensional fast-Fourier-transform algorithm is developed for the computation of multidimensional Fourier and Fourier-like discrete transforms; it has considerably less multiplications than the conventional fast-Fourier-transform methods.     

Modeling of perturbed covariance sequences

An algorithm for obtaining a state-space (Markovian) model of a random process from a finite number of estimated covariance lags is presented and compared to other SVD-based methods. The new algorithm performs well for small data sets in which the estimated covariance sequence is perturbed by estimation errors, and may not even be positive definite. Simulation results are presented for a second-order Markov process.     

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.     

Multidimensional BIFORE transform

The BIFORE transform is generalised to r dimensions. The corresponding power spectrum consists of ?i = 1r(1+ki) spectral points (Nt = 2ki), which are invariant under cyclic shifts of the r-dimensional input data. A physical interpretation of the BIFORE power spectrum is presented.     

Multidimensional bilinear transformations

The bilinear transformation is extended to transform multi-variable polynomials, using discrete convolution and the Kronecker product. This approach is very simple, easy for computer implementation, and useful in complex curve fitting and stability studies of discrete systems and the design of digital filters etc.     

一种基于二维最大熵的SAR图像自适应阈值分割算法

MSTAR目标图像分割是研究SAR图像分割的重要内容,基于最大熵原理,利用二维直方图设计适应度函数,借助遗传算法实现自适应阈值选取,以确定每个像素点的归属,经实际图像测试,对于含噪SAR图像中目标、背景和阴影的分割具有很好的效果,抑噪功能强.     

多维DFT的多维多项式变换与离散W变换算法

本文首先通过引进一种序列的重排技术将m(m2) 维离散Fourier变换 (m-D DFT)转化为一系列的一维广义离散Fourier变换(GDFT)的多重和.然后引入一维离散W变换(DWT)以及多维多项式变换(MD-PT)计算该多重和以减少冗余的算术运算,从而得到了高效的多维DFT算法,该算法与常用的行-列DFT算法相比,乘法仅约为行-列法的1/2m,而加法仅约为行-列法的(2m+1)/4m.对于2维DFT的计算,本文方法同单纯的多项式变换方法相比,乘法与加法分别减少50%与40%左右.另外,本文算法计算结构简单,易于编程实现,通过数值实验验证了本文算法的高效性.     

On the existence of a class of maximum-entropy probability density functions (Corresp.)

Existing theory on the maximum-entropy solution to the moment problem is extended. Criteria for identifying moment vectors whose maximum-entropy solution cannot have a certain exponential form are formulated. A proof of the uniqueness of maximum-entropy solutions is provided. A numerical procedure and some numerical results are presented.     

An exact fundamental and covariance algorithm

An exact algorithm is developed for computing a linear system's fundamental and output covariance matrix. It requires only that the system's plant matrix be spectrally decomposable into distinct eigenvalues.     

Systolic square root covariance Kalman filtering

The square root covariance Kalman filter (SRCF) and the square root covariance Kalman predictor (SRCP) are derived from a least squares viewpoint. A new systolic array architecture is presented which is suitable for implementing both forms of the filter. The systolic SRCF is found to be comparable with other architectures in the literature in terms of size, speed and processor utilization. The SRCP is faster than any comparable architecture withO(2n) timesteps between measurements.