On the concentrated stochastic likelihood function in array signal processing

The stochastic likelihood function [(STO)LF] associated with the narrowband signal processing problem can be concentrated with respect to the signal covariance matrix elements and the noise power. Although this is a known fact, no clear-cut derivation of the concentrated (STO)LF appears to be available in the literature. In this short paper we provide a simple, complete proof of the concentrated (STO)LF formula.The work of A. Nehorai was supported by the Air Force Office of Scientific Research under Grant no. F49620-93-1-0096, the Office of Naval Research under Grant no. N00014-91-J-1298, and the National Science Foundation under grant no. MIP-9122753. The work of P. Stoica was supported by the Swedish Research Council for Engineering Sciences under contract no. 93-669.     

Statistical analysis of decentralized MUSIC

For large-array processing problems there is a need for decentralized methods that are computationally efficient. A decentralized variant of the MUSIC algorithm, proposed in the literature, is here analysed from a statistical viewpoint, assuming that a large number of snapshots is available. As intuitively expected, the centralized MUSIC algorithm is more accurate than both the local and decentralized versions of MUSIC. More surprisingly, the decentralized variant of MUSIC is not always more accurate than the local MUSIC estimates. The theoretical analysis is supported by numerical examples.The work of Petre Stoica has been supported in part by grants from the Swedish Institute, the Royal Swedish Academy of Engineering Sciences, and the Swedish Research Council for Engineering Sciences.     

Study of Capon method for array signal processing

The mean-square error (MSE) of Capon estimate of the directions-of-arrival (DOA) is established in the narrowband array processing case. An improved Capon-like DOA estimator is proposed and its MSE is studied as well. Performance comparisons between the standard and improved Capon DOA estimates, and between these two estimates and the linear prediction DOA estimate, are performed. It is concluded that the improved Capon-like method introduced in this paper provides more accurate DOA estimates in most cases.This work has been supported by the Swedish Research Council for Engineering Sciences under contract 91–676.     

Instrumental variable methods for system identification

This paper gives a tutorial overview of instrumental variable methods. Comparisons are made to the least-squares method. An analysis including consistency and asymptotic distribution of the parameter estimates is included.Work supported in part by Swedish Research Council for Engineering Sciences under contract 95-800, and the Foundation for Strategic Research.     

On the direction estimation Cramér-Rao bounds in the presence of uncorrelated unknown noise

The deterministic and stochastic direction estimation Cramér-Rao bounds (CRBs) are studied in the presence of one signal and spatially uncorrelated sensor noise with unknown nonequal variances in array sensors. The explicit CRB expressions are obtained, and their relationship is studied showing some typical properties inherent in the nonidentical noise case.This work was supported in part by a grant from the Natural Sciences and Engineering Research Council (NSERC) of Canada and by the Russian Foundation of Basic Research under Grants 96-02-18621 and 97-02-17555.     

MODE-type algorithm for estimating damped, undamped, or explosive modes

We propose a new algorithm for estimating the parameters of damped, undamped, or explosive sinusoidal signals. The algorithm resembles the MODE algorithm, which is commonly used for direction of arrival estimation in the array signal processing field. It is derived as a natural approximation to an asymptotically (high-SNR) optimal parameter estimator and has excellent statistical accuracy. Nevertheless, it is computationally simple and easy to implement. Numerical examples are included to illustrate the performance of the proposed method.This work has been supported by the Swedish Research Council for Engineering Sciences (TFR).     

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

Model validation and model structure determination

This paper gives a tutorial overview of basic approaches for model validation and model structure determination.Work partially supported by the Swedish Research Council for Engineering Sciences under contract 98-654.     

Large-sample analysis of MUSIC and Min-Norm direction estimators in the presence of model errors

We analyze the large-sample mean square error (MSE) of MUSIC and Min-Norm direction-of-arrival (DOA) estimators under fairly general conditions, including mismodelling of the array response and the noise covariance. We separate the contributions to the MSE into a bias part caused by modelling errors and a variance part caused by finite (yet large) sample effects. The bias is simply evaluated by comparing the limiting estimate (corresponding to an infinite number of snapshots) with the true DOAs (which are known to the analyzer). To simplify the variance derivation we assume that the snapshots are complex i.i.d. Gaussian vectors and that the largest eigenvalues of their covariance matrix are distinct, but,otherwise, make none of the assumptions commonly used in previous analyses; in particular we do not constrain the snapshots to satisfy any model equation. The theoretical results obtained are illustrated by means of numerical examples using various modelling errors.The work of Petre Stoica was supported by the Swedish Research Council of Engineering Sciences under contract 91-676.     

Comparative performance study of element-space and beam-space MUSIC estimators

The goal of this paper is to show that in large samples the variances of the direction-of-arrival (DOA) estimates provided by the element-space MUSIC (i.e., MUSIC applied directly to the sensor output data) are always less than the corresponding variances associated with the beam-space MUSIC (i.e., MUSIC applied to spatially filtered sensor data).The work of A. Nehorai was supported by a grant from the Air Force Office of Scientific Research, under Grant No. AFOSR-90-0164 and the Office of Naval Research under Grant No. N00014-91-J-1298.     

Progress on a general numerical method for nonlinear higher index DAEs II

A method has been proposed for numerically solving lower dimensional, nonlinear, higher index differential algebraic equations for which more classical methods such as backward differentiation or implicit Runge-Kutta may not be appropriate. This method is based on solving nonlinear DAE derivative arrays. This paper discusses progress on the implementation of this method, resolves some of the issues involved, and lists some remaining problems. Computational experience on two prescribed path control problems is presented showing that the approach should prove practical for many applications.Research supported in part by the U.S. Army Research Office under DAALO3-89-D-0003, and the National Science Foundation under ECS-9012909 and DMS-9003401.     

A study of password security

We prove relationships between the security of a function generator when used in an encryption scheme and the security of a function generator when used in a UNIX-like password scheme.On leave of absence from the Computer Science Department, University of Toronto. Research partially supported by the Canadian Natural Sciences and Engineering Research Council Operating Grant A8092 and by a University of Toronto research grant.Research partially supported by the Canadian Natural Sciences and Engineering Research Council Operating Grant A3611.     

A note on the genericity of simultaneous stabilizability and pole assignability

In this paper we study the genericity of simultaneous stabilizability, simultaneous strong stabilizability, and simultaneous pole assignability, in linear multivariable systems. The main results of the paper had been previously established by Ghosh and Byrnes using state-space methods. In contrast, the proofs in the present paper are based on input-output arguments, and are much simpler to follow, especially in the case of simultaneous and simultaneous strong stabilizability. Moreover, the input-output methods used here suggest computationally reliable algorithms for solving these two types of problems. In addition to the main results, we also prove some lemmas on generic greatest common divisors which are of independent interest.This work was supported in part by the Natural Sciences and Engineering Research Council of Canada under Grant Number A-1240.This work was supported in part by The Army Research Office under Grant Number BAAG29-84-K-0005.This work was partially supported by the Department of Electronics, Government of India.     

A methodology for fast scheduling of partitioned systolic algorithms

Various methods for mapping signal processing algorithms into systolic arrays have been developed in the past few years. In this paper, efficient scheduling techniques are developed for the partitioning problem, i.e. problems with size that do not match the array size. In particular, scheduling for the Locally Parallel-Globally Sequential (LPGS) technique and the Locally Sequential-Globally Parallel (LSGP) technique are developed. The scheduling procedure developed exploits the fact that after LPGS and LSGP partitioning, the locality constraints are less stringent allowing for more flexibility in the choice of algorithms and inter-processor communication. A flexible scheduling order is developed that is useful in evaluating the trade-off between execution time and size of storage buffers. The benefits of the scheduling techniques are illustrated with the help of matrix multiplication and least squares examples. This work was supported in part by the UCSD/NSF Integrated Circuits And Systems Research Center and by the ARMY Research Office under Grant No. DAAL-03-90-G-0095.     

Signal processing using cellular neural networks

The cellular neural network (CNN) architecture combines the best features from traditional fully-connected analog neural networks and digital cellular automata. The network can rapidly process continuous-valued (gray-scale) input signals (such as images) and perform many computation functions which traditionally were implemented in digital form. Here, we briefly introduce the the theory of CNN circuits, provide some examples of CNN applications to image processing, and discuss work toward a CNN implementation in custom CMOS VLSI. The role of analog computer-aided design (CAD) will be briefly presented as it relates to analog neural network implementation.This work is supported in part by the Office of Naval Research under Contract N00014-89-J1402, and the National Science Foundation under grant MIP-8912639.     

Subband processing for broadband microphone arrays

This paper considers array processing for wideband signals. The optimization techniques and associated performance results correspond to steerable but fixed beam microphone arrays, to be used in hearing aid applications, both in free-space and reverberant conditions. We first review the results on maximum energy (ME) broadband arrays. We subsequently formulate optimization criteria for array subband processing. The uniformly spaced subband and the non-uniformly spaced subband using quadrature mirror filter approaches are treated. Finally, various simulation results for free-space and reverberant conditions are presented to demonstrate the usefulness of this class of microphone arrays, as well as the feasibility of quadrature mirror filter-based subband processing.This work was partially supported by the House Ear Institute and the Retirement Research Foundation.     

Direction-of-arrival estimation in applications with multipath and few snapshots

This paper analyzes two direction-of-arrival (DOA) estimation algorithms used in the presence of multipath propagation and with very few snapshots. The conditional maximum likelihood (CML) algorithm and the method of direction estimation (MODE) are discussed. The estimates provided by these algorithms are shown to coincide for large number of snapshots or large signal-to-noise ratio. Necessary and sufficient conditions are derived for the algorithms to yield unique estimates. It is shown that their uniqueness conditions coincide with the minimal uniqueness condition on the array, that is independent of the algorithm used (if the array does not satisfy this minimal condition, no DOA estimation method can give unique estimates). Numerical examples are presented to demonstrate the theoretical results.The work of A. Nehorai and D. Starer was supported by the Air Force Office of Scientific Research under Grant No. AFOSR-90-0164 and by the Office of Naval Research under Grant No. N00014-91-J-1298.     

Area efficient computing structures for concurrent error detection in systolic arrays

A method of designing testable systolic architectures is proposed in this paper. Testing systolic arrays involves mapping of an algorithm into a specific VLSI systolic architecture, and then modifying the design to achieve concurrent testing. In our approach, redundant computations are introduced at the algorithmic level by deriving two versions of a given algorithm. The transformed dependency matrix (TDM) of the first version is a valid transformation matrix while the second version is obtained by rotating the first TDM by 180 degrees about any of the indices that represent the spatial component of the TDM. Concurrent error detection (CED) systolic array is constructed by merging the corresponding systolic array of the two versions of the algorithm. The merging method attempts to obtain the self testing systolic array at minimal cost in terms of area and speed. It is based on rescheduling input data, rearranging data flow, and increasing the utilization of the array cells. The resulting design can detect all single permanent and temporary faults and the majority of the multiple fault patterns with high probability. The design method is applied to an algorithm for matrix multiplication in order to demonstrate the generality and novelty of our approach to design testable VLSI systolic architectures.This work has been supported by a grant from the Natural Sciences and Engineering Research Council of Canada.     

On identifiability and information-regularity in parametrized normal distributions

We describe methods to establish identifiability and information-regularity of parameters in normal distributions. Parameters are considered identifiable when they are determined uniquely by the probability distribution and they are information-regular when their Fisher information matrix is full rank. In normal distributions, information-regularity implies local identifiability, but the converse is not always true. Using the theory of holomorphic mappings, we show when the converse is true, allowing information-regularity to be established without having to explicitly compute the information matrix. Some examples are given.This work was supported by the Air Force Office of Scientific Research under Grant no. F49620-93-1-0096, the National Science Foundation under Grant no. MIP-9122753, and the Office of Naval Research under Grant no. N00014-91-J-1298.     

Nonplanar switchable arrays

On-line signal processing and automatic control applications give rise to numerous examples of computationally intense algorithms. Architectures which are algorithmically specialized and provide massive parallelism are necessary to cope with such computational requirements. Systolic arrays, which feature parallelism, local communications, and VLSI compatability appear to match up well with these computational requirements.This paper summarizes recent research on a general class of nonplanar systolic arrays. These arrays feature closed-loop data flow. The arrays may be switched dynamically to facilitate I/O simplicity and to accommodate iterative calculations without intermediate I/O interdiction. The closed-loop data flows also facilitate restructuring of the array to accommodate specific algorithmic requirements. The potential for multiuser, multialgorithm operation is also enhanced.Matrix operations are used as examples in the development. Algorithms as diversified as the Riccati equation, LU factorization, the Faddeev algorithm, FFT calculation, and controllability Grammians can be implemented on the nonplanar architectures.This research was sponsored in part by SDIO/IST and managed by the Army Research Office under contract P24962-MA SDI.