Fast Algorithms for Multidimensional Harmonic Retrieval

Classic multidimensional harmonic retrieval is the estimation problem in a variety of practical applications, including sensor array processing, radar, mobile communications, multiple-input multiple-output (MIMO) channel estimation and nuclear magnetic resonance spectroscopy. Numerous parametric subspace approaches have been proposed recently to solve this problem, among which the so-called ESPRIT-based algorithms are most popular due to their computational efficiency and comparably simple implementations. In these algorithms certain shift invariances contained in the measurements are exploited to estimate the parameters of interest by solving a joint eigenvalue problem. In many applications the measurements are obtained through uniform sampling along one or multiple dimensions. In these cases, the ESPRIT methods usually fail to exploit all prior information contained in the highly structured measurement data resulting in a significant performance loss in the parameter estimation.

In this work a different approach towards multidimensional harmonic retrieval is taken. A suitable parameterization enables the estimation of the harmonics of interest separately along the various dimensions, thus avoiding the computationally expensive optimization of a multidimensional cost function which would otherwise be required. This procedure makes the estimation problem computationally tractable while retaining much of the benefits inherent in the multidimensional nature of the measurement data such as, for example, relatively mild uniqueness conditions and high resolution capability compared to one dimensional data. Several matrix rank and polynomial rooting criteria are derived to obtain the parameters of interest separately along the various dimensions. New insight is gained from interpreting the proposed rank criteria in diverse contexts: as a relaxation approach in minimizing the classic root-MUSIC criterion, in a Gaussian-elimination framework, and as a rooting-based solution of the multiple invariance equations. The different viewpoints not only yield new stochastic uniqueness conditions for the rank reduction estimators, but also lead to efficient parameter association strategies to correctly group the parameters corresponding to a specific multidimensional harmonic signal. Further, a link between the popular ESPRIT-type methods and the root-MUSIC based approaches is discovered that allows to reformulate the rank reduction idea in terms of a joint generalized eigenproblem. Casting the multidimensional harmonic retrieval problem as an eigenproblem significantly simplifies the parameter estimation and association procedure and makes the algorithm equally applicable to the cases of pure and damped harmonic retrieval.

Simulation results obtained from synthetic data for the single and multiple snapshot case are presented and illustrate that the proposed algorithms are competitive with other existing methods from both a numerical viewpoint and also in terms of estimation performance. Further, in the example of parametric MIMO channel identification, it is demonstrated that the novel algorithms perform well if applied to real measurement data obtained from a channel-sounding campaign.