Spectral Analysis of Signals: The Missing Data Case (Synthesis Lectures on Signal Processing)

SPECTRAL ANALYSIS OF SIGNALS The Missing Data Case

Copyright © 2005 by Morgan & Claypool All rights reserved. No part of this publication may be reproduced, stored in a retrieval system, or transmitted in any form or by any means – electronic, mechanical, photocopy, recording, or any other except for brief quotations in printed reviews, without the prior permission of the publisher. Spectral Analysis of Signals, The Missing Data Case Yanwei Wang, Jian Li, and Petre Stoica www.morganclaypool.com ISBN: 1598290002 Library of Congress Cataloging-in-Publication Data

First Edition 10 9 8 7 6 5 4 3 2 1 Printed in the United States of America

SPECTRAL ANALYSIS OF SIGNALS The Missing Data Case Yanwei Wang Diagnostic Ultrasound Corporation Bothell, WA 98021

Jian Li Department of Electrical and Computer Engineering, University of Florida, Gainesville, FL 32611, USA

Petre Stoica Department of Information Technology, Division of Systems and Control, Uppsala University, Uppsala, Sweden

M &C

Mor gan

& Cl aypool

Publishers

ABSTRACT Spectral estimation is important in many fields including astronomy, meteorology, seismology, communications, economics, speech analysis, medical imaging, radar, sonar, and underwater acoustics. Most existing spectral estimation algorithms are devised for uniformly sampled complete-data sequences. However, the spectral estimation for data sequences with missing samples is also important in many applications ranging from astronomical time series analysis to synthetic aperture radar imaging with angular diversity. For spectral estimation in the missing-data case, the challenge is how to extend the existing spectral estimation techniques to deal with these missing-data samples. Recently, nonparametric adaptive filtering based techniques have been developed successfully for various missing-data problems. Collectively, these algorithms provide a comprehensive toolset for the missing-data problem based exclusively on the nonparametric adaptive filter-bank approaches, which are robust and accurate, and can provide high resolution and low sidelobes. In this lecture, we present these algorithms for both one-dimensional and twodimensional spectral estimation problems.

KEYWORDS Adaptive filter-bank, APES (amplitude and phase estimation), Missing data, Nonparametric methods, Spectral estimation

v

Contents 1.

Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.1 Complete-Data Case . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Missing-Data Case . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

2.

APES for Complete Data Spectral Estimation . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.2 Problem Formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.3 Forward-Only APES Estimator . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.4 Two-Step Filtering-Based Interpretation . . . . . . . . . . . . . . . . . . . . . . . . 8 2.5 Forward–Backward Averaging . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.6 Fast Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

3.

Gapped-Data APES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 3.2 GAPES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 3.2.1 Initial Estimates via APES . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 3.2.2 Data Interpolation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 3.2.3 Summary of GAPES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 3.3 Two-Dimensional GAPES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 3.3.1 Two-Dimensional APES Filter . . . . . . . . . . . . . . . . . . . . . . . . 18 3.3.2 Two-Dimensional GAPES . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 3.4 Numerical Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 3.4.1 One-Dimensional Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 3.4.2 Two-Dimensional Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

4.

Maximum Likelihood Fitting Interpretation of APES . . . . . . . . . . . . . . . . . 31 4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 4.2 ML Fitting Based Spectral Estimator . . . . . . . . . . . . . . . . . . . . . . . . . . 31 4.3 Remarks on the ML Fitting Criterion . . . . . . . . . . . . . . . . . . . . . . . . . . 33

vi

CONTENTS

5.

One-Dimensional Missing-Data APES via Expectation Maximization. .35 5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 5.2 EM for Missing-Data Spectral Estimation . . . . . . . . . . . . . . . . . . . . . 36 5.3 MAPES-EM1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 5.4 MAPES-EM2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 5.5 Aspects of Interest . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 5.5.1 Some Insights into the MAPES-EM Algorithms . . . . . . . . 45 5.5.2 MAPES-EM1 versus MAPES-EM2 . . . . . . . . . . . . . . . . . . . 46 5.5.3 Missing-Sample Estimation . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 5.5.4 Initialization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 5.5.5 Stopping Criterion. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .47 5.6 MAPES Compared With GAPES . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 5.7 Numerical Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48

6.

Two-Dimensional MAPES via Expectation Maximization and Cyclic Maximization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 6.2 Two-Dimensional ML-Based APES . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 6.3 Two-Dimensional MAPES via EM . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 6.3.1 Two-Dimensional MAPES-EM1 . . . . . . . . . . . . . . . . . . . . . . 64 6.3.2 Two-Dimensional MAPES-EM2 . . . . . . . . . . . . . . . . . . . . . . 68 6.4 Two-Dimensional MAPES via CM . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 6.5 MAPES-EM versus MAPES-CM . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74 6.6 Numerical Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 6.6.1 Convergence Speed . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76 6.6.2 Performance Study. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .78 6.6.3 Synthetic Aperture Radar Imaging Applications . . . . . . . . . 82

7.

Conclusions and Software . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87 7.1 Concluding Remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87 7.2 Online Software . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91 The Authors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97

vii

Preface This lecture considers the spectral estimation problem in the case where some of the data samples are missing. The challenge is how to extend the existing spectral estimation techniques to deal with these missing-data samples. Recently, nonparametric adaptive filtering based techniques have been developed successfully for various missing-data spectral estimation problems. Collectively, these algorithms provide a comprehensive toolset for the missing-data problem based exclusively on the nonparametric adaptive filter-bank approaches. They provide the main topic of this book. The authors would like to acknowledge the contributions of several other people and organizations to the completion of this lecture. We are grateful to our collaborators on this topic, including Erik G. Larsson, Hongbin Li, and Thomas L. Marzetta, for their excellent work and support. In particular, we thank Erik G. Larsson for providing us the Matlab codes that implement the two-dimensional GAPES algorithm. Most of the topics described here are outgrowths of our research programs in spectral analysis. We would like to thank those who supported our research in this area: the National Science Foundation, the Swedish Science Council (VR), and the Swedish Foundation for International Cooperation in Research and Higher Education (STINT). We also wish to thank Jose’ M. F. Moura for inviting us to write this lecture and Joel Claypool for publishing our work.

viii

List of Abbreviations 1-D

one-dimensional

2-D

two-dimensional

APES

amplitude and phase estimation

AR

autoregressive

ARMA

autoregressive moving-average

CAD

computer aided design

CM

cyclic maximization

DFT

discrete Fourier transform

EM

expectation maximization

FFT

fast Fourier transform

FIR

finite impulse response

GAPES

gapped-data amplitude and phase estimation

LS

least squares

MAPES

missing-data amplitude and phase estimation

MAPES-CM

missing-data amplitude and phase estimation via cyclic maximization

MAPES-EM

missing-data amplitude and phase estimation via expectation maximization

ML

maximum likelihood

RCF

robust Capon filter-bank

RF

radio frequency

RMSEs

root mean-squared errors

SAR

synthetic aperture radar

WFFT

windowed fast Fourier transform

1

C H A P T E R

1

Introduction Spectral estimation is important in many fields including astronomy, meteorology, seismology, communications, economics, speech analysis, medical imaging, radar, and underwater acoustics. Most existing spectral estimation algorithms are devised for uniformly sampled complete-data sequences. However, the spectral estimation for data sequences with missing samples is also important in a wide range of applications. For example, sensor failure or outliers can lead to missing-data problems. In astronomical, meteorological, or satellite-based applications, weather or other conditions may disturb sample taking schemes (e.g., measurements are available only during nighttime for astronomical applications), which will result in missing or gapped data [1]. In synthetic aperture radar imaging, missing-sample problems arise when the synthetic aperture is gapped to reduce the radar resources needed for the high-resolution imaging of a scene [2–4]. For foliage and ground penetrating radar systems, certain radar operating frequency bands are reserved for applications such as aviation and cannot be used, or they are under strong electromagnetic or radio frequency interference [5, 6] so that the corresponding samples must be discarded, both resulting in missing data. Similar problems arise in data fusion via ultrawideband coherent processing [7].

1.1

COMPLETE-DATA CASE

For complete-data spectral estimation, extensive work has already been carried out in the literature, see, e.g., [8]. The conventional discrete Fourier transform (DFT) or fast Fourier transform based methods have been widely used for spectral estimation

2

SPECTRAL ANALYSIS OF SIGNALS

tasks because of their robustness and high computational efficiency. However, they suffer from low resolution and poor accuracy problems. Many advanced spectral estimation methods have also been proposed, including parametric [9–11] and nonparametric adaptive filtering based approaches [12, 13]. One problem associated with the parametric methods is order selection. Even with properly selected order, it is hard to compare parametric and nonparametric approaches since the parametric methods (except [11]) do not provide complex amplitude estimation. In general, the nonparametric approaches are less sensitive to data mismodelling than their parametric counterparts. Moreover, the adaptive filter-bank based nonparametric spectral estimators can provide high resolution, low sidelobes, and accurate spectral estimates while retaining the robust nature of the nonparametric methods [14, 15]. These include the amplitude and phase estimation (APES) method [13] and the Capon spectral estimator [12]. However, the complete-data spectral estimation methods do not work well in the missing-data case when the missing data samples are simply set to zero. For the DFT-based spectral estimators, setting the missing samples to zero corresponds to multiplying the original data with a windowing function that assumes a value of one whenever a sample is available, and zero otherwise. In the frequency domain, the resulting spectrum is the convolution between the Fourier transform of the complete data and that of the windowing function. Since the Fourier transform of the windowing function typically has an underestimated mainlobe and an extended pattern of undesirable sidelobes, the resulting spectrum will be poorly estimated and contain severe artifacts. For the parametric and adaptive filtering based approaches, similar performance degradations will also occur.

1.2

MISSING-DATA CASE

For missing-data spectral estimation, various techniques have been developed previously. In [16] and [17], the Lomb–Scargle periodogram is developed for irregularly sampled (unevenly spaced) data. In the missing-data case, the Lomb–Scargle

INTRODUCTION

periodogram is nothing but DFT with missing samples set to zero. The CLEAN algorithm [18] is used to estimate the spectrum by deconvolving the missing-data DFT spectrum (the so-called “dirty map”) into the true signal spectrum (the socalled “true clean map”) and the Fourier transform of the windowing function (the so-called “dirty beam”) via an iterative approach. Although the CLEAN algorithm works for both missing and irregularly sampled data sequences, it cannot resolve closely spaced spectral lines, and hence it may not be a suitable tool for highresolution spectral estimation. The multi-taper methods [19, 20] compute spectral estimates by assuming certain quadratic functions of the available data samples. The coefficients in the corresponding quadratic functions are optimized according to certain criteria, but it appears that this approach cannot overcome the resolution limit of DFT. To achieve high resolution, several parametric algorithms, e.g., those based on an autoregressive or autoregressive moving-average models, were used to handle the missing-data problem [21–24]. Although these parametric methods can provide improved spectral estimates, they are sensitive to model errors. Nonparametric adaptive filtering based techniques are promising for the missing-data problem, as we will show later.

1.3

SUMMARY

In this book, we present the recently developed nonparametric adaptive filtering based algorithms for the missing-data case, namely gapped-data APES (GAPES) and the more general missing-data APES (MAPES). The outlines of the remaining chapters are as follows: Chapter 2: In this chapter, we introduce the APES filter for the complete-data case. The APES filter is needed for the missing-data algorithm developed in Chapter 3. Chapter 3: We consider the spectral analysis of a gapped-data sequence where the available samples are clustered together in groups of reasonable size.

3

4

SPECTRAL ANALYSIS OF SIGNALS

Following the filter design framework introduced in Chapter 2, GAPES is developed to iteratively interpolate the missing data and to estimate the spectrum. A two-dimensional extension of GAPES is also presented. Chapter 4: In this chapter, we introduce a maximum likelihood (ML) based interpretation of APES. This framework will lay the ground for the general missing-data problem discussed in the following chapters. Chapter 5: Although GAPES performs quite well for gapped data, it does not work well for the more general problem of missing samples occurring in arbitrary patterns. In this chapter, we develop two MAPES algorithms by using a “ML fitting” criterion as discussed in Chapter 4. Then we use the well-known expectation maximization (EM) method to solve the so-obtained estimation problem iteratively. We also demonstrate the advantage of MAPES-EM over GAPES by comparing their design approaches. Chapter 6: Two-dimensional extensions of the MAPES-EM algorithms are developed. However, because of the high computational complexity involved, the direct application of MAPES-EM to large data sets, e.g., two-dimensional data, is computationally prohibitive. To reduce the computational complexity, we develop another MAPES algorithm, referred to as MAPES-CM, by solving a “ML fitting” problem iteratively via cyclic maximization (CM). MAPES-EM and MAPES-CM possess similar spectral estimation performance, but the computational complexity of the latter is much lower than that of the former. Chapter 7: We summarize the book and provide some concluding remarks. Additional online resources such as Matlab codes that implement the missing-data algorithms are also provided.

5

C H A P T E R

2

APES for Complete Data Spectral Estimation 2.1

INTRODUCTION

Filter-bank approaches are commonly used for spectral analysis. As nonparametric spectral estimators, they attempt to compute the spectral content of a signal without using any a priori model information or making any explicit model assumption about the signal. For any of these approaches, the key element is to design narrowband filters centered at the frequencies of interest. In fact, the well-known periodogram can be interpreted as such a spectral estimator with a data-independent filter-bank. In general, data-dependent (or data-adaptive) filters outperform their data-independent counterparts and are hence preferred in many applications. A well-known adaptive filter-bank method is the Capon spectral estimator [12]. More recently, Li and Stoica [13] devised another adaptive filter-bank method with enhanced performance, which is referred to as the amplitude and phase estimation (APES). APES surpasses its rivals in several aspects [15, 25] and find applications in various fields [1, 26–31]. In this chapter, we derive the APES filter from pure narrowband-filter design considerations [32]. It is useful as the initialization step of the algorithms in Chapter 3. The remainder of this chapter is organized as follows: The problem formulation is given in Section 2.2 and the forward-only APES filter is presented in Section 2.3. Section 2.4 provides a two-step filtering interpretation of the APES estimator. Section 2.5 shows how the forward–backward averaging can be used

6

SPECTRAL ANALYSIS OF SIGNALS

to improve the performance of the estimator. A brief discussion about the fast implementation of APES appears in Section 2.6.

2.2

PROBLEM FORMULATION

Consider the problem of estimating the amplitude spectrum of a complex-valued N−1 . For a frequency ω of interest, the uniformly sampled discrete-time signal {yn }n=0

signal yn is modeled as yn = α(ω) e j ωn + en (ω),

n = 0, . . . , N − 1,

ω ∈ [0, 2π),

(2.1)

where α(ω) denotes the complex amplitude of the sinusoidal component at frequency ω, and en (ω) denotes the residual term (assumed zero-mean), which includes the unmodeled noise and interference from frequencies other than ω. The N−1 for any given frequency ω. problem of interest is to estimate α(ω) from {yn }n=0

2.3

FORWARD-ONLY APES ESTIMATOR

Let h(ω) denote the impulse response of an M-tap finite impulse response (FIR) filter-bank h(ω) = [h 0 (ω) h 1 (ω) · · · h M−1 (ω)]T ,

(2.2)

where (·)T denotes the transpose. Then the filter output can be written as h H (ω)¯yl , where y¯ l = [yl yl+1 · · · yl+M−1 ]T ,

l = 0, . . . , L − 1

(2.3)

are the M ×1 overlapping forward data subvectors (snapshots) and L = N − M + 1. Here (·) H denotes the conjugate transpose. For each ω of interest, we consider the following design objective: min

α(ω),h(ω)

L−1 
 h H (ω)¯yl − α(ω) e j ωl 2

s.t.

h H (ω)a(ω) = 1,

(2.4)

l=0

where a(ω) is an M × 1 vector given by a(ω) = [1 e j ω · · · e j ω(M−1) ]T .

(2.5)

APES FOR COMPLETE DATA SPECTRAL ESTIMATION

In the above approach, the filter-bank h(ω) is designed such that 1. the filtered sequence is as close to a sinusoidal signal as possible in a least squares (LS) sense; 2. the complex spectrum α(ω) is not distorted by the filtering. ¯ Let g(ω) denote the normalized Fourier transform of y¯ l : ¯ g(ω) =

L−1 1
y¯ l e −j ωl L l=0

(2.6)

and define L−1
ˆ = 1 y¯ l y¯ H . R L l=0 l

(2.7)

A straightforward calculation shows that the objective function in (2.4) can be rewritten as L−1  2 1
 H  h (ω)¯yl − α(ω) e j ωl  L l=0

ˆ ¯ = h H (ω)Rh(ω) − α ∗ (ω)h H (ω)g(ω) − α(ω)g¯ H (ω)h(ω) + |α(ω)|2 2 2 ˆ ¯ ¯ = |α(ω) − h H (ω)g(ω)| + h H (ω)Rh(ω) − |h H (ω)g(ω)| ,

(2.8)

where (·)∗ denotes the complex conjugate. The minimization of (2.8) with respect to α(ω) is given by ˆ ¯ α(ω) = h H (ω)g(ω).

(2.9)

Insertion of (2.9) in (2.8) yields the following minimization problem for the determination of h(ω): min h(ω)

ˆ h H (ω)S(ω)h(ω)

s.t.

h H (ω)a(ω) = 1,

(2.10)

where ˆ ˆ − g(ω) ¯ g¯ H (ω). S(ω)
R

(2.11)

7

8

SPECTRAL ANALYSIS OF SIGNALS

The solution to (2.10) is readily obtained [33] as ˆh(ω) =

Sˆ −1 (ω)a(ω) . a H (ω)Sˆ −1 (ω)a(ω)

(2.12)

This is the forward-only APES filter, and the forward-only APES estimator in (2.9) becomes ˆ α(ω) =

2.4

¯ a H (ω)Sˆ −1 (ω)g(ω) . ˆ H −1 a (ω)S (ω)a(ω)

(2.13)

TWO-STEP FILTERING-BASED INTERPRETATION

The APES spectral estimator has a two-step filtering interpretation: passing the N−1 through a bank of FIR bandpass filters with varying center frequency data {yn }n=0

ˆ ω, and then obtaining the spectrum estimate α(ω) for ω ∈ [0, 2π) from the filtered data. For each frequency ω, the corresponding M-tap FIR filter-bank is given by (2.12). Hence the output obtained by passing y¯ l through the FIR filter ˆh(ω) can be written as ˆh H (ω)¯yl = α(ω)[ˆh H (ω)a(ω)] e j ωl + w¯ l (ω) = α(ω) e j ωl + w¯ l (ω),

(2.14)

where w¯ l (ω) = ˆh H (ω)¯el (ω) denotes the residue term at the filter output and the second equality follows from the identity ˆh H (ω)a(ω) = 1.

(2.15)

Thus, from the output of the FIR filter, we can obtain the LS estimate of α(ω) as ˆ ¯ α(ω) = ˆh H (ω)g(ω).

2.5

(2.16)

FORWARD–BACKWARD AVERAGING

Forward–backward averaging has been widely used for enhanced performance in many spectral analysis applications. In the previous section, we obtained the APES

APES FOR COMPLETE DATA SPECTRAL ESTIMATION

filter by using only forward data vectors. Here we show that forward–backward averaging can be readily incorporated into the APES filter design by considering both the forward and the backward data vectors. Let the backward data subvectors (snapshots) be constructed as ∗ y˘ l = [y N−l−1

∗ ∗ y N−l−2 · · · y N−l−M ]T ,

l = 0, . . . , L − 1.

(2.17)

We require that the outputs obtained by running the data through the filter both forward and backward are as close as possible to a sinusoid with frequency ω. This design objective can be written as min

h(ω),α(ω),β(ω)

s.t.

L−1     1
h H (ω)¯yl − α(ω) e j ωl 2 + h H (ω)˘yl − β(ω) e j ωl 2 2L l=0

h H (ω)a(ω) = 1.

(2.18)

ˆ ¯ The minimization of (2.18) with respect to α(ω) and β(ω) gives α(ω) = h H (ω)g(ω) ˆ and β(ω) = h H (ω)˘g(ω), where g˘ (ω) is the normalized Fourier transform of y˘ l : g˘ (ω) =

L−1 1
y˘ l e −j ωl . L l=0

(2.19)

It follows that (2.18) leads to min h(ω)

h H (ω)Sˆ f b (ω)h(ω)

s.t.

h H (ω)a(ω) = 1,

(2.20)

where ¯ g¯ H (ω) + g˘ (ω)˘g H (ω) ˆ f b − g(ω) Sˆ f b (ω)
R 2

(2.21)

L−1
ˆ f = 1 R y¯ l y¯ lH , L l=0

(2.22)

L−1
ˆb= 1 R y˘ l y˘ lH , L l=0

(2.23)

with

9

10

SPECTRAL ANALYSIS OF SIGNALS

and ˆ ˆ ˆ f b = R f + Rb . (2.24) R 2 ˆ to emphasize on the fact that it is estimated ˆ f instead of R Note that here we use R from the forward-only approach. The solution of (2.20) is given by ˆhf b (ω) =

Sˆ f−1 b (ω)a(ω) . a H (ω)Sˆ −1 (ω)a(ω)

(2.25)

fb

Because of the following readily verified relationship y˘ l = J y¯ ∗L−l−1 ,

(2.26)

we have g˘ (ω) = Jg¯ ∗ (ω) e −j ω(L−1) ,

(2.27)

ˆ T J, ˆ b = JR R f

(2.28)

¯ g¯ H (ω)]T J, g˘ (ω)˘g H (ω) = J [g(ω)

(2.29)

and

where J denotes the exchange matrix whose antidiagonal elements are ones and the remaining elements are zeros. So Sˆ f b (ω) can be conveniently calculated as Sˆ f b (ω) =

Sˆ f (ω) + JSˆ Tf (ω) J 2

,

(2.30)

where ˆ f − g(ω) ¯ g¯ H (ω). Sˆ f (ω)
R

(2.31)

Given the forward–backward APES filter ˆhf b (ω), the forward–backward spectral estimator can be written as αˆ f b (ω) =

¯ a H (ω)Sˆ f−1 b (ω)g(ω) . a H (ω)Sˆ −1 (ω)a(ω) fb

(2.32)

APES FOR COMPLETE DATA SPECTRAL ESTIMATION

11

Note that due to the above relationship, the forward–backward estimator of β(ω) can be simplified as βˆf b (ω) = hfHb (ω)˘g(ω) = αˆ f∗b e −j ω(N−1) ,

(2.33)

which indicates that from βˆf b (ω) we will get the same forward–backward spectral estimator αˆ f b (ω). In summary, the forward–backward APES filter and APES spectral estimator ˆ and S(ω) ˆ still has the same forms as in (2.12) and (2.13), but R are replaced by ˆ f b and Sˆ f b (ω) are persymmetric matrices. ˆ f b and Sˆ f b (ω), respectively. Note that R R ˆ f and Sˆ f (ω), they are generally Compared with the non-persymmetric estimates R better estimates of the true R and Q (ω), where R and Q (ω) are the ideal covariance matrices with and without the presence of the signal of interest, respectively. See Chapter 4 for more details about R and Q (ω). For simplicity, all the APES-like algorithms we develop in the subsequent chapters are based on the forward-only approach. For better estimation accuracy, the forward–backward averaging is used in all numerical examples.

2.6

FAST IMPLEMENTATION

The direct implementation of APES by simply computing (2.13) for many different ω of interest is computationally demanding. Several papers in the literature have addressed this problem [29, 34–36]. Here we give a brief discussion about implementing APES efficiently. ˆ To avoid the inversion of an M × M matrix S(ω) for each ω, we use the matrix inversion lemma (see, e.g., [8]) to obtain ˆ −1 ˆ −1 ¯ g¯ H (ω)R ˆ −1 + R g(ω) . Sˆ −1 (ω) = R ˆ −1 g(ω) ¯ 1 − g¯ H (ω)R

(2.34)

12

SPECTRAL ANALYSIS OF SIGNALS

ˆ −1/2 denote the Cholesky factor of R ˆ −1 , and let Let R ˆ −1/2 a(ω) aˇ (ω) = R ˆ −1/2 g(ω) ¯ gˇ (ω) = R ζ (ω) = aˇ H (ω)ˇa(ω) (ω) = aˇ H (ω)ˇg(ω) ε(ω) = gˇ H (ω)ˇg(ω).

(2.35)

Then we can write (2.12) and (2.13) as ˆ −1/2 ] H [(1 − ε(ω))ˇa(ω) + (ω)ˇg(ω)] ˆh(ω) = [R ζ (ω)(1 − ε(ω)) + |(ω)|2

(2.36)

and ˆ α(ω) =

(ω) ζ (ω)(1 − ε(ω)) + |(ω)|2

(2.37)

ˆ whose implementation requires only the Cholesky factorization of the matrix R that is independent of ω. This strategy can be readily generalized to the forward–backward averaging case. Since the complete-data case is not the focus of this book, we refer the readers to [29, 34–36] for more details about the efficient implementations of APES.

13

C H A P T E R

3

Gapped-Data APES 3.1

INTRODUCTION

One special case of the missing-data problem is called gapped data, where the measurements during certain periods are not valid due to many reasons such as interference or jamming. The difference between the gapped-data problem and the general missing-data problem, where the missing samples can occur at arbitrary places among the complete data set, is that for the gapped-data case, there exists group(s) of available data samples where within each group there are no missing samples. Such scenarios exist in astronomical or radar applications where large segments of data are available in spite of the fact that the data between these segments are missing. For example, in radar signal processing, the problem of combining several sets of measurements made at different azimuth angle locations can be posed as a problem of spectral estimation from gapped data [2, 4]. Similar problems arise in data fusion via ultrawideband coherent processing [7]. In astronomy, data are often available as groups of samples with rather long intervals during which no measurements can be taken [17, 37–41]. The gapped-data APES (GAPES) considers using the APES filter (as introduced in Chapter 2) for the spectral estimation of gapped-data. Specifically, the GAPES algorithm consists of two steps: (1) estimating the adaptive filter and the corresponding spectrum via APES and (2) filling in the gaps via LS fit. In the remainder of this chapter, one-dimensional (1-D) and twodimensional (2-D) GAPES are presented in Sections 3.2 and 3.3, respectively. Numerical results are provided in Section 3.4.

14

SPECTRAL ANALYSIS OF SIGNALS

3.2

GAPES

N−1 Assume that some segments of the 1-D data sequence {yn }n=0 are unavailable. Let

y
[ y1 y2 · · · y N−1 ]T
T
y1T y2T · · · yPT

(3.1)

be the complete data vector, where y1 , . . . , yP are subvectors of y, whose lengths are N1 , . . . , N P , respectively, with N1 + N2 + · · · + N P = N. A gapped-data vector γ is formed by assuming yp , for p = 1, 3, . . . , P (P is always an odd number), are available:
γ
y1T

y3T

···

yPT

T


µ
y2T

y4T

···

yPT−1

.

(3.2)

Similarly, T

(3.3)

denotes all the missing samples. Then γ and µ have dimensions g × 1 and (N − g ) × 1, respectively, where g = N1 + N3 + · · · + NP is the total number of available samples.

3.2.1 Initial Estimates via APES We obtain the initial APES estimates of h(ω) and α(ω) from the available data γ as follows. Choose an initial filter length M0 such that an initial full-rank covariance maˆ trix R can be built with the filter length M0 using only the available data segments. This indicates 

max(0, Np − M0 + 1) > M0 .

(3.4)

p∈{1,3,...,P }

Let L p = Np − M0 + 1 and let J be the subset of {1, 3, . . . , P} for which L p > 0. Then the filter-bank h(ω) is calculated from (2.11) and (2.12) by using the

GAPPED-DATA APES

15

following redefinitions: ˆ = 1 R p∈J

¯ g(ω) =

p−1 +L p −1  N1 +···+N 

Lp

l=N1 +···+Np−1

p−1 +L p −1  N1 +···+N 

1 p∈J

p∈J

Lp

p∈J

y¯ l y¯ lH ,

(3.5)

y¯l e −j ωl .

(3.6)

l=N1 +···+Np−1

Note that the data snapshots used above have a size of M0 × 1 whose elements are only from γ, and hence they do not contain any missing samples. Correspondingly, ˆ and g(ω) ¯ the R estimated above have sizes of M0 × M0 and M0 × 1, respectively. Next, the filter-bank h(ω) is applied to the available data γ and the LS ¯ estimate of α(ω) from the filter output is calculated by using (2.16), where g(ω) is replaced by (3.6). Note that in the above filtering process, only the available samples are passed through the filter. The initial LS estimate of α(ω) is based on these so-obtained filter outputs only.

3.2.2 Data Interpolation ˆ Now we consider the estimation of µ based on the initial spectral estimates α(ω) and ˆh(ω) obtained as outlined above. Under the assumption that the missing data have the same spectral content as the available data, we can determine γˆ under the condition that the output of the filter ˆh(ω) fed with the complete data sequence ˆ is as close as possible (in the LS sense) to α(ω) ˆ made from γ and µ e −j ωl , for ˆ l = 0, . . . , L − 1. Since usually we evaluate α(ω) on a K-point DFT grid, ωk = 2πk/K for k = 0, . . . , K − 1 (usually we have K > N ),we obtain µ as the solution to the following LS problem: min µ

L−1  K −1  

2 ˆh H (ωk )¯yl − α(ω ˆ k ) e j ωk l  .

(3.7)

k=0 l=0

Note that by estimating µ this way, we remain in the LS fitting framework of APES.

16

SPECTRAL ANALYSIS OF SIGNALS

The quadratic minimization problem (3.7) can be readily solved. Let    H  ˆh (ωk ) hˆ ∗0 · · · hˆ ∗M0 −1 0 0 0       ˆH 0 hˆ ∗ · · · hˆ ∗ 0  0 M 0 −1 0   h (ωk )   H(ωk ) =   ∈ C L×N = .. .. .. ..     . . . .     H ∗ ∗ ˆ ˆ ˆ 0 0 0 h 0 · · · h M0 −1 h (ωk ) (3.8) and



1



   e j ωk    ˆ k)  η(ωk ) = α(ω  ∈ C L×1 . . ..     j ωk (L−1) e

(3.9)

Using this notation we can write the objective function in (3.7) as 2   y 0 K −1   .  H(ωk )  ..  − η(ωk ) .   k=0 y N−1

(3.10)

Define the L × g and L × (N − g ) matrices A(ωk ) and B(ωk ) from H(ωk ) via the following equality:  y0  .  .  H(ωk )   .  = A(ωk )γ + B(ωk )µ. y N−1

(3.11)

d(ωk ) = η(ωk ) − A(ωk )γ.

(3.12)



Also, let

With this notation the objective function (3.10) becomes K −1  k=0

B(ωk )µ − d(ωk )2 ,

(3.13)

GAPPED-DATA APES

17

whose minimizer with respect to µ is readily found to be

ˆ = µ

K −1 

−1 H

B (ωk )B(ωk )

k=0

K −1 

 B (ωk )d(ωk ) . H

(3.14)

k=0

3.2.3 Summary of GAPES ˆ has become available, the next logical step should consist Once an estimate µ of reestimating the spectrum and the filter-bank, by applying APES to the data ˆ According to the discussion around (2.4), this entails sequence made from γ and µ. the minimization with respect to h(ωk ) and α(ωk ) of the function L−1  K −1  

 h H (ωk )yˆ¯ − α(ωk ) e j ωk l 2 l

(3.15)

k=0 l=0

ˆ Evidently, the minsubject to h H (ωk )a(ωk ) = 1, where yˆ¯ l is made from γ and µ. K −1 can be decoupled into K imization of (3.15) with respect to {h(ωk ), α(ωk )}k=0

minimization problems of the form of (2.4), yet we prefer to write the criterion function as in (3.15) to make the connection with (3.7). In effect, comparing (3.7) and (3.15) clearly shows that the alternating estimation of {α(ωk ), h(ωk )} and µ outlined above can be recognized as a cyclic optimization (see [42] for a tutorial of cyclic optimization) approach for solving the following minimization problem: min

L−1  K −1  

 h H (ωk )¯yl − α(ωk ) e j ωk l 2

µ,{α(ωk ),h(ωk )}

s.t.

h H (ωk )a(ωk ) = 1.

k=0 l=0

(3.16) A step-by-step summary of GAPES is as follows: Step 0: Obtain an initial estimate of {α(ωk ), h(ωk )}. Step 1: Use the most recent estimate of {α(ωk ), h(ωk )} in (3.16) to estimate µ by minimizing the so-obtained cost function, whose solution is given by (3.14). Step 2: Use the latest estimate of µ to fill in the missing data samples and estimate K −1 by minimizing the cost function in (3.16) based on the {α(ωk ), h(ωk )}k=0

18

SPECTRAL ANALYSIS OF SIGNALS

interpolated data. (This step is equivalent to applying APES to the complete data.) Step 3: Repeat steps 1–2 until practical convergence. The practical convergence can be decided when the relative change of the cost function in (3.16) corresponding to the current and previous estimates is smaller than a preassigned threshold (e.g.,  = 10−3 ). After convergence, we have a final K −1 ˆ k )}k=0 . If desired, we can use the final interpolated data spectral estimate {α(ω

sequence to compute the APES spectrum on a grid even finer than the one used in the aforementioned minimization procedure. Note that usually the selected initial filter length satisfies M0 < M due to the missing data samples, so there are many practical choices to increase the filter length after initialization, which include, for example, increasing the filter length after each iteration until it reaches M. For simplicity, we choose to use filter length M right after the initialization step.

3.3

TWO-DIMENSIONAL GAPES

In this section, we extend the GAPES algorithm developed previously to 2-D data matrices.

3.3.1 Two-Dimensional APES Filter Consider the problem of estimating the amplitude spectrum of a complex-valued −1,N2 −1 , where the data matrix uniformly sampled 2-D discrete-time signal {yn1 ,n2 }nN11=0,n 2 =0

has dimension N1 × N2 . For a 2-D frequency (ω1 , ω2 ) of interest, the signal yn1 ,n2 is described as yn1 ,n2 = α(ω1 , ω2 ) e j (ω1 n1 +ω2 n2 ) + e n1 ,n2 (ω1 , ω2 ), n2 = 0, . . . , N2 − 1,

ω1 , ω2 ∈ [0, 2π),

n1 = 0, . . . , N1 − 1, (3.17)

where α(ω1 , ω2 ) denotes the complex amplitude of the 2-D sinusoidal component at frequency (ω1 , ω2 ) and e n1 ,n2 (ω1 , ω2 ) denotes the residual matrix (assumed

GAPPED-DATA APES

19

zero-mean), which includes the unmodeled noise and interference from frequencies other than (ω1 , ω2 ). The 2-D APES algorithm derived below estimates α(ω1 , ω2 ) from {yn1 ,n2 } for any given frequency pair (ω1 , ω2 ). Let Y be an N1 × N2 data matrix 

y0,0

  y1,0  Y
 .  ..  y N1 −1,0

y0,1

...

y0,N2 −1

y1,1 .. .

... .. .

y1,N2 −1 .. .

y N1 −1,1

...

y N1 −1,N2 −1

    ,  

(3.18)

and let H(ω1 , ω2 ) be an M1 × M2 matrix that contains the coefficients of a 2-D FIR filter 

h 0,0 (ω1 , ω2 )

  h 1,0 (ω1 , ω2 )  H(ω1 , ω2 )
 ..  .  h M1 −1,0 (ω1 , ω2 )

h 0,1 (ω1 , ω2 )

...

h 0,M2 −1 (ω1 , ω2 )

h 1,1 (ω1 , ω2 ) .. .

... .. .

h 1,M2 −1 (ω1 , ω2 ) .. .

h M1 −1,1 (ω1 , ω2 ) . . .

    .  

h M1 −1,M2 −1 (ω1 , ω2 ) (3.19)

Let L1
N1 − M1 + 1 and L2
N2 − M2 + 1. Then we denote by X¯ = H(ω1 , ω2 )  Y

(3.20)

the following L1 × L2 output data matrix obtained by filtering Y through the filter determined by H(ω1 , ω2 )

x¯l 1 ,l 2 =

M 2 −1 1 −1 M   m 1 =0 m 2 =0

h ∗m 1 ,m 2 (ω1 , ω2 )yl 1 +m 1 ,l 2 +m 2

= vec H (H(ω1 , ω2 ))¯yl 1 ,l 2 ,

(3.21)

20

SPECTRAL ANALYSIS OF SIGNALS

where vec(·) denotes the operation of stacking the columns of a matrix onto each other. In (3.21), y¯ l 1 ,l 2 is defined by 

yl 1 ,l 2 +1

yl 1 ,l 2

...

yl 1 ,l 2 +M2 −1



    yl 1 +1,l 2 y . . . y l +1,l +1 l +1,l +M −1 1 2 1 2 2   y¯ l 1 ,l 2
vec(Y¯ l 1 ,l 2 )
vec   . . .. .. .. ..   . . .   yl 1 +M1 −1,l 2 yl 1 +M1 −1,l 2 +1 . . . yl 1 +M1 −1,l 2 +M2 −1 (3.22) ˆ 1 , ω2 ) and the filter coefficient matrix The APES spectrum estimate α(ω ˆ 1 , ω2 ) are the minimizers of the following LS criterion: H(ω min

α(ω1 ,ω2 ),H(ω1 ,ω2 )

L 2 −1  1 −1 L 

x¯l

1 ,l 2

2 − α(ω1 , ω2 ) e j (ω1 l 1 +ω2 l 2 )

l 1 =0 l 2 =0

s.t.

vec H (H(ω1 , ω2 ))a M1 ,M2 (ω1 , ω2 ) = 1.

(3.23)

Here a M1 ,M2 (ω1 , ω2 ) is an M1 M2 × 1 vector given by a M1 ,M2 (ω1 , ω2 )
a M2 (ω2 ) ⊗ a M1 (ω1 ),

(3.24)

where ⊗ denotes the Kronecker matrix product and a Mk (ωk )
[1

e j ωk

...

e j (Mk −1)ωk ]T ,

k = 1, 2.

(3.25)

Substituting X¯ into (3.23), we have the following design objective for 2-D APES: minα(ω1 ,ω2 ),H(ω1 ,ω2 ) s.t.

 vec(H(ω1 , ω2 )  Y) − α(ω1 , ω2 )a L

1 ,L2

vec H (H(ω1 , ω2 ))a M1 ,M2 (ω1 , ω2 ) = 1,

2 (ω1 , ω2 ) (3.26)

where a L1 ,L2 (ω1 , ω2 ) is defined similar to a M1 ,M2 (ω1 , ω2 ). The solution to (3.26) can be readily derived. Define ˆ = R

2 −1 1 −1 L  1 L y¯ l ,l y¯ H L1 L2 l 1 =0 l 2 =0 1 2 l 1 ,l 2

(3.27)

GAPPED-DATA APES

21

¯ 1 , ω2 ) denote the normalized 2-D Fourier transform of y¯ l 1 ,l 2 : and let g(ω ¯ 1 , ω2 ) = g(ω

2 −1 1 −1 L  1 L y¯ l ,l e − j (ω1 l 1 +ω2 l 2 ) . L1 L2 l 1 =0 l 2 =0 1 2

(3.28)

The filter H(ω1 , ω2 ) that minimizes (3.26) is given by ˆ 1 , ω2 )) = vec(H(ω

H aM 1 ,M2

Sˆ −1 (ω1 , ω2 )a M1 ,M2 (ω1 , ω2 ) (ω1 , ω2 )Sˆ −1 (ω1 , ω2 )a M ,M (ω1 , ω2 ) 1

(3.29)

2

and the APES spectrum is given by ˆ 1 , ω2 ) = α(ω

H ¯ 1 , ω2 ) (ω1 , ω2 )Sˆ −1 (ω1 , ω2 )g(ω aM 1 ,M 2 , aH (ω1 , ω2 )Sˆ −1 (ω1 , ω2 )a M ,M (ω1 , ω2 ) M1 ,M2

1

(3.30)

2

where ˆ 1 , ω2 )
R ˆ − g(ω ¯ 1 , ω2 )g¯ H (ω1 , ω2 ). S(ω

(3.31)

3.3.2 Two-Dimensional GAPES Let G be the set of sample indices (n1 , n2 ) for which the data samples are available, and U be the set of sample indices (n1 , n2 ) for which the data samples are missing. The set of available samples {yn1 ,n2 : (n1 , n2 ) ∈ G} is denoted by the g × 1 vector γ, whereas the set of missing samples {yn1 ,n2 : (n1 , n2 ) ∈ U} is denoted by the (N1 N2 − g ) × 1 vector µ. The problem of interest is to estimate α(ω1 , ω2 ) given γ. Assume we consider a K 1 × K 2 -point DFT grid: (ωk1 , ωk2 ) = (2πk 1 / K 1 , 2π k 2 /K 2 ), for k1 = 0, . . . , K 1 − 1 and k2 = 0, . . . , K 2 − 1 (with K 1 > N1 and K 2 > N2 ). The 2-D GAPES algorithm tries to solve the following minimization problem: min

µ, {α(ωk1, ωk2 ), H(ωk1, ωk2 )}

K 2 −1 1 −1 K  

 vec(H(ωk , ωk )  Y ) − α(ωk , ωk )a L ,L (ωk , ωk )2 1 2 1 2 1 2 1 2

k1 =0 k 2 =0

s.t.

vec H (H(ωk1, ωk2 ))a M1 ,M2 (ωk1 , ωk2 ) = 1,

via cyclic optimization [42].

(3.32)

22

SPECTRAL ANALYSIS OF SIGNALS

For the initialization step, we obtain the initial APES estimates of H(ω1 , ω2 ) and α(ω1 , ω2 ) from the available data γ in the following way. Let S be the set of snapshot indices (l 1 , l 2 ) such that the elements of the corresponding initial data snapshot indices {(l 1 , l 2 ), . . . , (l 1 , l 2 + M20 − 1), . . . , (l + M10 − 1, l 2 ), . . . , (l 1 + M10 − 1, l 2 + M20 − 1)} ∈ G. Define the set of M10 M20 × 1 vectors {¯yl 1 ,l 2 : (l 1 , l 2 ) ∈ S}, which contain only the available data samples, and let |S| be the number of vectors in S. Furthermore, define the initial sample covariance matrix  ˆ = 1 y¯ l ,l y¯ H . R |S| (l ,l )∈S 1 2 l 1 ,l 2

(3.33)

1 2

ˆ The size of the initial filter matrix M10 × M20 must be chosen such that the R calculated in (3.33) has full rank. Similarly, the initial Fourier transform of the data snapshots is given by ¯ 1 , ω2 ) = g(ω

1  y¯ l ,l e − j (ω1 l 1 +ω2 l 2 ) . |S| (l ,l )∈S 1 2

(3.34)

1 2

So the initial estimates of H(ω1 , ω2 ) and α(ω1 , ω2 ) can be calculated by (3.29)– ˆ and g(ω ¯ 1 , ω2 ) given above. (3.31) but by using the R Next, we introduce some additional notation that will be used later for the step of interpolating the missing samples. Let the L1 L2 × (L2 N1 − M1 + 1) matrix T be defined by 

I L1

   T=  



0 L1 ,M1 −1 I L1

   .  

0 L1 ,M1 −1 ..

.

(3.35)

I L1 Hereafter, 0 K1 ,K2 denotes a K 1 × K 2 matrix of zeros only and I K stands for the K × K identity matrix. Furthermore, let G be the following (L2 N1 − M1 + 1) × N1 N2

GAPPED-DATA APES

23

Toeplitz matrix: 

h1H 01,L1 −1

   G(ω1 , ω2 ) =   

h2H

01,L1 −1

...

0

...

0

H hM 2 .. .

... .. .

0 .. .

H hM 2

0 .. .

h1H .. .

01,L1 −1 .. .

h2H .. .

01,L1 −1 . . . .. .. . .

0

···

0

h1H

H 01,L1 −1 h2H 01,L1 −1 . . . h M 2

      

(3.36) where {hm 2 }mM22=1 are the corresponding columns of H(ω1 , ω2 ). With these definitions, we have ¯ = vec(H(ω1 , ω2 )  Y) = TG vec(Y). vec(X)

(3.37)

By making use of (3.37), the estimate of µ based on the initial estimates ˆ 1 , ω2 ) is given by the solution to the following problem: ˆ 1 , ω2 ) and H(ω α(ω

min µ

    2 ˆ 0 , ω0 )a L1 ,L2 (ω0 , ω0 ) TG(ω0 , ω0 ) α(ω     .. . . vec (Y) −     . . . TG(ω K1 −1 , ω K2 −1 ) ˆ K1 −1 , ω K2 −1 )a L1 ,L2 (ω K1 −1 , ω K2 −1 ) α(ω (3.38)

To solve (3.38), let the matrices Gγ (ωk1 , ωk2 ) and Gµ (ωk1 , ωk2 ) be defined implicity by the following equality: G(ωk1 , ωk2 ) vec(Y) = Gγ (ωk1 , ωk2 )γ + Gµ (ωk1 , ωk2 )µ,

(3.39)

where γ and µ are the vectors containing the available samples and missing samples, respectively. In other words, Gγ (ωk1 , ωk2 ) and Gµ (ωk1 , ωk2 ) contain the columns of G(ωk1 , ωk2 ) that correspond to the indices in G and U, respectively. By introducing the following matrices:   ˜ γ
 G 

TGγ (ω0 , ω0 ) .. . TGγ (ω K1 −1 , ω K2 −1 )

   

(3.40)

24

SPECTRAL ANALYSIS OF SIGNALS

and



TGµ (ω0 , ω0 ) .. .

 ˜ µ
 G 

  , 

(3.41)

2 ˜ µµ + G ˜ γγ − α G ˜ ,

(3.42)

TGµ (ω K1 −1 , ω K2 −1 ) the criterion (3.38) can then be written as min µ

where

  ˜
 α 

ˆ 0 , ω0 )a L1 ,L2 (ω0 , ω0 ) α(ω .. .

  . 

(3.43)

ˆ K1 −1 , ω K2 −1 )a L1 ,L2 (ω K1 −1 , ω K2 −1 ) α(ω The closed-form solution of the quadratic problem (3.42) is easily obtained as  ˜ H ˜ −1 ˜ H  ˜ γ γ . ˜ −G ˆ = G (3.44) Gµ α µ µ Gµ A step-by-step summary of 2-D GAPES is as follows: Step 0: Obtain an initial estimate of {α(ω1 , ω2 ), h(ω1 , ω2 )}. Step 1: Use the most recent estimate of {α(ω1 , ω2 ), h(ω1 , ω2 )} in (3.32) to estimate µ by minimizing the so-obtained cost function, whose solution is given by (3.44). Step 2: Use the latest estimate of µ to fill in the missing data samples and estimate −1,K 2 −1 by minimizing the cost function in (3.32) {α(ω1 , ω2 ), H(ω1 , ω2 )}kK11=0,k 2 =0

based on the interpolated data. (This step is equivalent to applying 2-D APES to the complete data.) Step 3: Repeat steps 1–2 until practical convergence.

3.4

NUMERICAL EXAMPLES

We now present several numerical examples to illustrate the performance of GAPES for the spectral analysis of gapped data. We compare GAPES with windowed FFT (WFFT). A Taylor window with order 5 and sidelobe level −35 dB is used for WFFT.

GAPPED-DATA APES

25

3.4.1 One-Dimensional Example In this example, we consider the 1-D gapped-data spectral estimation. To implement GAPES, we choose K = 2N for the iteration steps and the final spectrum is estimated on a finer grid with K = 32. The initial filter length is chosen as M0 = 20, and we use M = N/2 = 64 after the initialization step. We calculate the corresponding WFFT spectrum via zero-padded FFT. The true spectrum of the simulated signal is shown in Fig. 3.1(a), where we have four spectral lines located at f 1 = 0.05 Hz, f 2 = 0.065 Hz, f 3 = 0.26 Hz, and f 4 = 0.28 Hz with complex amplitudes α1 = α2 = α3 = 1 and α4 = 0.5. Besides these spectral lines, Fig. 3.1(a) also shows a continuous spectral component centered at 0.18 Hz with a width b = 0.015 Hz and a constant modulus of 0.25. The data sequence has N = 128 samples where the samples 23–46 and 76–100 are missing. The data is corrupted by a zero-mean circularly symmetric complex white Gaussian noise with variance σn2 = 0.01. In Fig. 3.1(b) the WFFT is applied to the data by filling in the gaps with zeros. Note that the artifacts due to the missing data are quite severe in the spectrum. Figs. 3.1(c) and 3.1(d) show the moduli of the WFFT and APES spectra of the complete data sequence, where the APES spectrum demonstrated superior resolution compared to that of WFFT. Figs. 3.1(e) and 3.1(f ) illustrate the moduli of the WFFT and APES spectra of the data sequence interpolated via GAPES. Comparing Figs. 3.1(e) and 3.1(f ) with 3.1(c) and 3.1(d), we note that GAPES can effectively fill in the gaps and estimate the spectrum.

3.4.2 Two-Dimensional Examples GAPES applied to simulated data with line spectrum: In this example we consider a data matrix of size 32 × 50 consisting of three noisy sinusoids, with frequencies (1,0.8), (1,1.1), and (1.1,1.3) and amplitudes 1, 0.7, and 2, respectively, embedded in white Gaussian noise with standard deviation 0.1. All samples in the columns 10–20 and 30–40 are missing. The true spectrum is shown in Fig. 3.2(a) and the missing-data pattern is shown in Fig. 3.2(b). In Fig. 3.2(c) we show the

1.2

Modulus of Complex Amplitude

Modulus of Complex Amplitude

SPECTRAL ANALYSIS OF SIGNALS

1

0.8

0.6

0.4

0.2

1.2

1

0.8

0.6

0.4

0.2

0 0

0.1

0.2

0.3

0.4

0 0

0.5

0.1

Frequency (Hz)

0.2

Modulus of Complex Amplitude

Modulus of Complex Amplitude

1

0.8

0.6

0.4

0.5

0.4

0.5

0.4

0.5

1.2

1

0.8

0.6

0.4

0.2

0.2

0.05

0.1

0.15

0.2

0.25

0.3

0.35

0 0

0.4

0.1

Frequency (Hz)

0.2

0.3

Frequency (Hz)

(c)

(d) Modulus of Complex Amplitude

1.2

1

0.8

0.6

0.4

1.2

1

0.8

0.6

0.4

0.2

0.2

0 0

0.4

(b)

1.2

0 0

0.3

Frequency (Hz)

(a)

Modulus of Complex Amplitude

26

0.05

0.1

0.15

0.2

0.25

Frequency (Hz)

(e)

0.3

0.35

0.4

0 0

0.1

0.2

0.3

Frequency (Hz)

(f)

FIGURE 3.1: Modulus of the gapped-data spectral estimates [N = 128, σn2 = 0.01, two gaps involving 49 (40%) missing samples]. (a) True spectrum, (b) WFFT, (c) complete-data WFFT, (d) complete-data APES, (e) WFFT with interpolated data via GAPES, and (f ) GAPES.

GAPPED-DATA APES 2 1.8

5

1.6

10

1.4 1.2

2.0000

15

1.0000 1 0.7000

0.8

20

0.6

25 0.4 0.2 0

30 0

0.5

1

1.5

10

2

20

(a) 2

1.8

1.8

1.6

1.6

1.4

50

1.4

1.2

1.2

2.0014

2.0028

0.98937

1.0103

1

1 0.70254

0.8

0.6

0.4

0.4

0.2

0.2 0

0.5

1

0.7024

0.8

0.6

1.5

2

0

0

0.5

(c)

1

1.5

2

1.5

2

(d)

2

2

1.8

1.8

1.6

1.6

1.4

1.4

1.2

1.2

1.0147

2.1452

0.66132

1.0461

1

1 0.77715

0.8

0.6

0.4

0.4

0.2

0.2 0

0.5

1

0.6949

0.8

0.6

0

40

(b)

2

0

30

1.5

2

0

0

(e)

0.5

1

(f)

FIGURE 3.2: Modulus of the 2-D spectra. (a) True spectrum, (b) 2-D data missing pattern, the black stripes indicate missing samples, (c) 2-D complete-data WFFT, (d) 2-D complete-data APES with a 2-D filter of size 16 × 25, (e) 2-D WFFT, and (f ) 2-D GAPES with an initial 2-D filter of size 10 × 8.

27

28

SPECTRAL ANALYSIS OF SIGNALS

(a)

(b)

(c)

5

10

15

20

25

30

35

40

45 5

10

15

20

25

(d)

30

35

40

45

(e)

(f)

FIGURE 3.3: Modulus of the SAR images of the backhoe data obtained from a 48 × 48 data matrix with missing samples. (a) 3-D CAD model and K-space data, (b) 2-D completedata WFFT, (c) 2-D complete-data APES with a 2-D filter of size 24 × 36, (d) 2-D data missing pattern, the black stripes indicate missing samples, (e) 2-D WFFT, and (f ) 2-D GAPES with an initial 2-D filter of size 20 × 9.

GAPPED-DATA APES

29

512 × 512 WFFT spectrum of the full data. In Fig. 3.2(d) we show the 512 × 512 APES spectrum of the full data obtained by using a 2-D filter matrix of size 16 × 25. Fig. 3.2(e) shows the WFFT spectrum obtained by setting the missing samples to zero. Fig. 3.2(f ) shows the GAPES spectrum with an initial filter of size 10 × 8. Comparing Fig. 3.2(f ) with 3.2(d), we can see that GAPES still gives very good spectral estimates as if there were no missing samples. GAPES applied to SAR data: In this example we apply the GAPES algorithm to the SAR data. The “Backhoe Data Dome, Version 1.0” consists of simulated wideband (7–13 GHz), full polarization, complex backscatter data from a backhoe vehicle in free space. The 3-D computer-aided design (CAD) model of the backhoe vehicle is shown in Fig. 3.3(a), with a viewing direction corresponding to (approximately) 45◦ elevation and 45◦ azimuth. The backscattered data has been generated over a full upper 2π steradian viewing hemisphere, which is also illustrated in Fig. 3.3(a). We consider a 48 × 48 HH polarization data matrix collected at 0◦ elevation, from approximately a 3◦ azimuth cut centered around 0◦ azimuth, covering approximately a 0.45 GHz bandwidth centered around 10 GHz. In Fig. 3.3(b) we show the SAR image obtained by applying WFFT to the full data. Fig. 3.3(c) shows the image obtained by the application of APES to the full data with a 2-D filter of size 24 × 36. Note that the two closely located vertical lines (corresponds to the loader bucket) are well resolved by APES because of its super resolution. To simulate the gapped data, we create artificial gaps in the phase history data matrix by removing the columns 10–17 and 30–37, as illustrated in Fig. 3.3(d). In Fig. 3.3(e) we show the result of applying WFFT to the data where the missing samples are set to zero. Significant artifacts due to the data gapping can be observed. Fig. 3.3(f ) shows the resulting image of GAPES after one iteration. (Further iteration did not change the result visibly.) To perform the interpolation, we apply 2-D GAPES with an initial filter matrix of size 20 × 9 on a 96 × 96 grid. After the interpolation step, the spectrum of the so-obtained interpolated data matrix is computed via 2-D APES with the same filter size as that used in Fig. 3.3(c). We can see that GAPES can still resolve the two vertical spectral lines clearly.

31

C H A P T E R

4

Maximum Likelihood Fitting Interpretation of APES 4.1

INTRODUCTION

In this chapter, we review the APES algorithm for complete-data spectral estimation following the derivations in [13], which provide a “maximum likelihood (ML) fitting” interpretation of the APES estimator. They pave the ground for the missing-data algorithms we will present in later chapters.

4.2

ML FITTING BASED SPECTRAL ESTIMATOR

Recall the problem of estimating the amplitude spectrum of a complex-valued uniformly sampled data sequence introduced in Section 2.2. The APES algorithm N−1 for any given frequency ω. derived below estimates α(ω) from {yn }n=0

Partition the data vector y = [y0

y1 · · ·

y N−1 ]T

(4.1)

into L overlapping subvectors (data snapshots) of size M × 1 with the following shifted structure: y¯ l = [yl

yl+1 · · ·

yl+M−1 ]T ,

l = 0, . . . , L − 1,

(4.2)

32

SPECTRAL ANALYSIS OF SIGNALS

where L = N − M + 1. Then, according to the data model in (2.1), the lth data snapshot y¯ l can be written as y¯ l = α(ω)a(ω) · e j ωl + e¯ l (ω),

(4.3)

where a(ω) is an M × 1 vector given by (2.5) and e¯ l (ω) = [e l (ω)e l+1 (ω) · · · e l+M−1 (ω)]T . The APES algorithm mimics a ML approach to estimate α(ω) by assuming that e¯ l (ω), l = 0, 1, . . . , L − 1, are zero-mean circularly symmetric complex Gaussian random vectors that are statistically independent of each other and have the same unknown covariance matrix 
Q (ω) = E e¯ l (ω)¯elH (ω) .

(4.4)

Then the covariance matrix of y¯ l can be written as  2 R = α(ω) a(ω)a H (ω) + Q (ω).

(4.5)

L−1 in our case are overlapping, they are not statistically Since the vectors {¯el (ω)}l=0

independent of each other. Consequently, APES is not an exact ML estimator. Using the above assumptions, we get the normalized surrogate log-likelihood function of the data snapshots {¯yl } as follows: L−1   
H 1 1 y¯ l − α(ω)a(ω)e j ωl ln p({¯yl }α(ω), Q (ω)) = −M ln π − lnQ (ω) − L L l=0

×Q−1 (ω)[ y¯ l − α(ω)a(ω)e j ωl ]  L−1   1 −1   = −M ln π − ln Q(ω) − tr Q (ω) L l=0


y¯ l − α(ω)a(ω)e

j ωl




y¯ l − α(ω)a(ω)e

 j ωl H

(4.6)

 ,

(4.7)

where tr{·} and | · | denote the trace and the determinant of a matrix, respectively. For any given α(ω), maximizing (4.7) with respect to Q (ω) gives L−1  ˆ α (ω) = 1 Q [¯yl − α(ω)a(ω)e j ωl ][¯yl − α(ω)a(ω)e j ωl ] H . L l=0

(4.8)

ML FITTING INTERPRETATION OF APES

33

Inserting (4.8) into (4.7) yields the following concentrated cost function (with changed sign)

  L−1    1  

 H  ˆ α (ω) =  y¯ l − α(ω)a(ω)e j ωl y¯ l − α(ω)a(ω)e j ωl  , G = Q   L l=0

(4.9)

ˆ and ¯ which is to be minimized with respect to α(ω). By using the notation g(ω), R, ˆ S(ω) defined in (2.6), (2.7), and (2.11), respectively, the cost function G in (4.9) becomes   H ˆ + |α(ω)|2 a(ω)a H (ω) − g(ω)α ¯ (ω)a H (ω) − α(ω)a(ω)g¯ H (ω) G = R   H ˆ − g(ω) ¯ ¯ ¯ g¯ H (ω) + [α(ω)a(ω) − g(ω)][α(ω)a(ω) (4.10) − g(ω)] = R    H ˆ I + Sˆ −1 (ω)[α(ω)a(ω) − g(ω)][α(ω)a(ω) ¯ ¯ = S(ω) , (4.11) − g(ω)] ˆ where S(ω) can be recognized as an estimate of Q (ω). Making use of the identity     I + AB = I + BA, we get    H ˆ −1 ˆ 1 + [α(ω)a(ω) − g(ω)] ¯ ¯ . S (ω) [α(ω)a(ω) − g(ω)] G = S(ω)

(4.12)

Minimizing G with respect to α(ω) yields ˆ α(ω) =

¯ a H (ω)Sˆ −1 (ω)g(ω) . ˆ H −1 a (ω)S (ω)a(ω)

(4.13)

Making use of the calculation in (4.10), we get the estimate of Q (ω) as H ˆ (ω) = S(ω) ˆ ˆ ˆ ¯ ¯ Q + [α(ω)a(ω) − g(ω)][ α(ω)a(ω) − g(ω)] .

(4.14)

ˆ (ω) is the ˆ In the APES algorithm, α(ω) is the sought spectral estimate and Q estimate of the nuisance matrix parameter Q (ω).

4.3

REMARKS ON THE ML FITTING CRITERION

The phrase ML fitting criterion used above can be commented as follows. In some estimation problems, using the exact ML method is computationally prohibitive or even impossible. In such problems one can make a number of simplifying assumptions and derive the corresponding ML criterion. The estimates that minimize the

34

SPECTRAL ANALYSIS OF SIGNALS

so-obtained surrogate ML fitting criterion are not exact ML estimates, yet usually they have good performance and generally they are by design much simpler to compute than the exact ML estimates. For example, even if the data are not Gaussian distributed, a ML fitting criterion derived under the Gaussian hypothesis will often lead to computationally convenient and yet accurate estimates. Another example here is sinusoidal parameter estimation from data corrupted by colored noise: the “ML” fitting criterion derived under the assumption that the noise is white leads to parameter estimates of the sinusoidal components whose accuracy asymptotically achieves the exact Cram´er–Rao bound (derived under the correct assumption of colored noise), see [43, 44]. The APES method ([13, 15]) is another example where a surrogate “ML” fitting criterion, derived under the assumption that the data snapshots are Gaussian and independent, leads to estimates with excellent performance. We follow the same approach in the following chapters by extending the APES method to the missing-data case.

35

C H A P T E R

5

One-Dimensional Missing-Data APES via Expectation Maximization 5.1

INTRODUCTION

In Chapter 3 we presented GAPES for gapped-data spectral estimation. GAPES iteratively interpolates the missing data and estimates the spectrum. However, GAPES can deal only with missing data occurring in gaps and it does not work well for the more general problem of missing data samples occurring in arbitrary patterns. In this chapter, we consider the problem of nonparametric spectral estimation for data sequences with missing data samples occurring in arbitrary patterns (including the gapped-data case) [45]. We develop two missing-data amplitude and phase estimation (MAPES) algorithms by using a “ML” fitting criterion as derived in Chapter 4. Then we use the well-known expectation maximization (EM) [42, 46] method to solve the so-obtained estimation problem iteratively. Through numerical simulations, we demonstrate the excellent performance of the MAPES algorithms for missing-data spectral estimation and missing-data restoration. The remainder of this chapter is organized as follows: In Section 5.2, we give a brief review of the EM algorithm for the missing-data problem. In Sections 5.3 and 5.4, we develop two nonparametric MAPES algorithms for the missing-data spectral estimation problem via the EM algorithm. Some aspects of interest are

36

SPECTRAL ANALYSIS OF SIGNALS

discussed in Section 5.5. In Section 5.6, we compare MAPES with GAPES for the missing-data problem. Numerical results are provided in Section 5.7 to illustrate the performance of the MAPES-EM algorithms.

5.2

EM FOR MISSING-DATA SPECTRAL ESTIMATION

Assume that some arbitrary samples of the uniformly sampled data sequence N−1 are missing. Because of these missing samples, which can be treated as {yn }n=0

unknowns, the surrogate log-likelihood fitting criterion in (4.6) cannot be maximized directly. We show below how to tackle this general missing-data problem through the use of the EM algorithm. Recall that the g × 1 vector γ and the (N − g ) × 1 vector µ contain all the available samples (incomplete data) and all the missing samples, respectively, of the N × 1 complete data vector y. Then we have the following relationships: N−1 γ ∪ µ = {yn }n=0

(5.1)

γ ∩ µ = φ,

(5.2)

where φ denotes the empty set. Let θ = {α(ω), Q (ω)}. An estimate θˆ of θ can be obtained by maximizing the following surrogate ML fitting criterion involving the available data vector γ: θˆ = arg max ln p(γ | θ). θ

(5.3)

If µ were available, the above problem would be easy to solve (as shown in the previous chapter). In the absence of µ, however, the EM algorithm maximizes the conditional (on γ) expectation of the joint log-likelihood function of γ and µ. The algorithm is iterative. At the ith iteration, we use θˆ i−1 from the previous iteration to update the parameter estimate by maximizing the conditional expectation: 
 (5.4) θˆ i = arg max E ln p(γ, µ | θ)  γ, θˆ i−1 . θ

It can be shown [42, 47] that for each iteration, the increase in the surrogate loglikelihood function is greater than or equal to the increase in the expected joint

1-D MISSING-DATA APES VIA EM

37

surrogate log-likelihood in (5.4), i.e.,
  ln p(γ | θˆ i ) − ln p(γ | θˆ i−1 ) ≥ E ln p(γ, µ | θˆ i )  γ, θˆ i−1
  − E ln p(γ, µ | θˆ i−1 )  γ, θˆ i−1 .

(5.5)

Since the data snapshots {¯yl } are overlapping, one missing sample may occur in many snapshots (note that there is only one new sample between two adjacent data snapshots). So two approaches are possible when we try to estimate the missing data: estimate the missing data separately for each snapshot y¯ l by ignoring any possible L−1 by observing the over lappings. In overlapping, or jointly for all snapshots {¯yl }l=0

the following two sections, we make use of these ideas to develop two different MAPES-EM algorithms, namely MAPES-EM1 and MAPES-EM2.

5.3

MAPES-EM1

L−1 In this section we assume that the data snapshots {¯yl }l=1 are independent of each

other, and hence we estimate the missing data separately for different data snap¯ l denote the vectors containing the shots. For each data snapshot y¯ l , let γ¯ l and µ available and missing elements of y¯ l , respectively. In general, the indices of the missing components could be different for different l. Assume that γ¯ l has dimension g l × 1, where 1 ≤ g l ≤ M is the number of available elements in the snapshot y¯ l . (Although g l could be any integer that belongs to the interval 0 ≤ g l ≤ M, we assume for now that g l = 0. Later we will explain what happens when g l = 0.) ¯ l are related to y¯ l by unitary transformations as follows: Then γ¯ l and µ γ¯ l = S¯ gT (l ) y¯ l

(5.6)

¯ l = S¯ mT (l ) y¯ l , µ

(5.7)

where S¯ g (l ) and S¯ m (l ) are M × g l and M × (M − g l ) unitary selection matrices such that S¯ gT (l )S¯ g (l ) = Ig l ,

(5.8)

S¯ mT (l )S¯ m (l ) = I M−g l ,

(5.9)

38

SPECTRAL ANALYSIS OF SIGNALS

and S¯ gT (l )S¯ m (l ) = 0g l ×(M−g l ) .

(5.10)

For example, if M = 5 and we observe the first, third, and fourth components of y¯ l , then g l = 3, 

1



0

 0  ¯Sg (l ) =  0  0  0

0

 0   0  1  0

0 1 0 0

(5.11)

and 

0

 1   S¯ m (l ) = 0  0  0



0

 0   0 .  0  1

(5.12)

Because we clearly have y¯ l = [S¯ g (l )S¯ gT (l ) + S¯ m (l )S¯ mT (l )] y¯ l ¯ , = S¯ g (l )γ¯ + S¯ m (l )µ l

l

(5.13)

¯ l } is obtained by the joint normalized surrogate log-likelihood function of {γ¯ l , µ substituting (5.13) into (4.7)

L−1 1 1 ¯ l } | α(ω), Q (ω)) = −M ln π − ln | Q (ω) | − tr Q−1 (ω) ¯l ln p({γ¯ l , µ S¯ g (l )γ¯ l + S¯ m (l )µ L L l=0 

 H ¯ l − α(ω)a(ω) e j ωl − α(ω)a(ω) e j ωl S¯ g (l )γ¯ l + S¯ m (l )µ .

(5.14)

1-D MISSING-DATA APES VIA EM

Owing to the Gaussian assumption on y¯ l , the random vectors     ¯l S¯ mT (l ) µ y¯ l , = l = 0, . . . , L − 1 S¯ T (l ) γ¯ l

39

(5.15)

g

are also Gaussian with mean   S¯ mT (l ) a(ω)α(ω) e j ωl , ¯ST (l )

l = 0, . . . , L − 1

(5.16)

g

and covariance matrix   S¯ mT (l ) Q (ω) S¯ m (l ) S¯ T (l )

¯Sg (l ) ,

l = 0, . . . , L − 1.

(5.17)

g

From the Gaussian distribution of

µ ¯l γ¯ l ,

it follows that the probability density func¯ l conditioned on γ¯ l (for given θ = θˆ i−1 ) is a complex Gaussian with mean tion of µ ¯ l [48]: b¯ l and covariance matrix K ¯ l ), ¯ l | γ¯ l , θˆ i−1 ∼ CN (b¯ l , K µ

(5.18)

where 
 ¯ l  γ¯ l , θˆ i−1 b¯ l = E µ = S¯ mT (l )a(ω)αˆ i−1 (ω) e j ωl

−1 ˆ i−1 (ω)S¯ g (l ) S¯ T (l )Q ˆ i−1 (ω)S¯ g (l ) γ¯ − S¯ T (l )a(ω)αˆ i−1 (ω) e j ωl  + S¯ mT (l )Q l g g (5.19) and 
 ¯ l = cov µ ¯ l  γ¯ l , θˆ i−1 K ˆ i−1 (ω)S¯ m (l ) = S¯ T (l )Q



−1 ˆ i−1 (ω)S¯ g (l ) S¯ T (l )Q ˆ i−1 (ω)S¯ g (l ) ˆ i−1 (ω)S¯ m (l ). S¯ gT (l )Q − S¯ mT (l )Q g m

(5.20) Expectation: We evaluate the conditional expectation of the surrogate loglikelihood in (5.14) using (5.18)–(5.20), which is most easily done by adding and

40

SPECTRAL ANALYSIS OF SIGNALS

¯ l in (5.14) as follows: subtracting the conditional mean b¯ l from µ  ¯ l − α(ω)a(ω) e j ωl S¯ g (l )γ¯ l + S¯ m (l )µ     ¯ l − b¯ l ) + S¯ g (l )γ¯ l + S¯ m (l )b¯ l − α(ω)a(ω) e j ωl . = S¯ m (l )(µ



(5.21)

The cross-terms that result from the expansion of the quadratic term in (5.14) vanish when we take the conditional expectation. Therefore the expectation step yields 

 1 i−1 i−1 ˆ ¯ l }|α(ω), Q (ω)) | {γ¯ l }, αˆ (ω), Q (ω) E ln p({γ¯ l , µ L  L−1  1 ¯ l S¯ T (l) S¯ m (l)K = −M ln π − ln |Q (ω)| − tr Q−1 (ω) m L l=0    H + S¯ g (l)γ¯ l + S¯ m (l)b¯ l − α(ω)a(ω)e j ωl S¯ g (l)γ¯ l + S¯ m (l)b¯ l − α(ω)a(ω)e j ωl .

(5.22) Maximization: The maximization part of the EM algorithm produces updated estimates for α(ω) and Q (ω). The normalized expected surrogate loglikelihood (5.22) can be rewritten as   L−1   H   1 Γ¯ l + z¯ l − α(ω)a(ω) e j ωl z¯ l − α(ω)a(ω) e j ωl , −M ln π − ln |Q (ω)| − tr Q−1 (ω) L l=0

(5.23) where we have defined ¯ l S¯ T (l) Γ¯ l
S¯ m (l)K m

(5.24)

z¯ l
S¯ g (l)γ¯ l + S¯ m (l)b¯ l .

(5.25)

and

According to the derivation in Chapter 4, maximizing (5.23) with respect to α(ω) and Q (ω) gives αˆ 1 (ω) =

¯ a H (ω)S¯ −1 (ω)Z(ω) a H (ω)S¯ −1 (ω)a(ω)

(5.26)

1-D MISSING-DATA APES VIA EM

41

and H ¯ ¯ ¯ ˆ 1 (ω) = S(ω) + [αˆ 1 (ω)a(ω) − Z(ω)][ αˆ 1 (ω)a(ω) − Z(ω)] , Q

(5.27)

L−1  ¯Z(ω)
1 z¯ l e −j ωl L l=0

(5.28)

L−1 L−1 1 1 ¯ ¯ ¯ H (ω). S(ω)
Z z¯ l z¯ H − Z(ω) Γ¯ l + L l=0 L l=0 l

(5.29)

where

and

This completes the derivation of the MAPES-EM1 algorithm, a step-by-step summary of which is as follows: Step 0: Obtain an initial estimate of {α(ω), Q (ω)}. Step 1: Use the most recent estimate of {α(ω), Q (ω)} in (5.19) and (5.20) to ¯ l , respectively. Note that b¯ l can be regarded as the current calculate b¯ l and K estimate of the corresponding missing samples. Step 2: Update the estimate of {α(ω), Q (ω)} using (5.26) and (5.27). Step 3: Repeat steps 1 and 2 until practical convergence. Note that when g l = 0, which indicates that there is no available sample in the current data snapshot y¯ l , S¯ g (l) and γ¯ do not exist and S¯ m (l) is an M × M l

identity matrix; hence, the above algorithm can still be applied by simply removing any term that involves S¯ g (l) or γ¯ in the above equations. l

5.4

MAPES-EM2

Following the observation that the same missing data may enter in many snapshots, we propose a second method to implement the EM algorithm by estimating the missing data simultaneously for all data snapshots. Recall that the available and missing data vectors are denoted as γ ( g × 1 vector) and µ[(N − g ) × 1 vector], respectively. Let y˜ denote the LM × 1 vector

42

SPECTRAL ANALYSIS OF SIGNALS

obtained by concatenating all the snapshots   y¯ 0  .    y˜
 ..  = Sg γ + Sm µ,   y¯ L−1

(5.30)

where Sg (LM × g ) and Sm (LM × (N − g )) are the corresponding selection matrices for the available and missing data vectors, respectively. Because of the overlapping of {¯yl }, Sg and Sm are not unitary, but they are still orthogonal to each other: SgT Sm = 0g ×(N−g ) .

(5.31)

Instead of (5.6) and (5.7), we have from (5.30)  −1 T γ = SgT Sg Sg y˜ = S˜ gT y˜

(5.32)

 −1 T µ = SmT Sm Sm y˜ = S˜ mT y˜ .

(5.33)

and

The matrices S˜ g and S˜ m introduced above are defined as  −1 S˜ g
Sg SgT Sg

(5.34)

 −1 S˜ m
Sm SmT Sm ,

(5.35)

and

and they are also orthogonal to each other: S˜ gT S˜ m = 0g ×(N−g ) .

(5.36)

Note that SgT Sg and SmT Sm are diagonal matrices where each diagonal element indicates how many times the corresponding sample appears in y˜ owing to the overlapping of {¯yl }. Hence both SgT Sg and SmT Sm can be easily inverted.

1-D MISSING-DATA APES VIA EM

43

Now the normalized surrogate log-likelihood function in (4.6) can be written as

1 1 ln p(˜y | α(ω), Q (ω)) = −M ln π − ln |D(ω)| L L 1 − [ y˜ − α(ω)ρ(ω)] H D−1 (ω)[ y˜ − α(ω)ρ(ω)], L (5.37)

where ρ(ω) and D(ω) are defined as



 e j ω0 a(ω)   ..  ρ(ω)
 .   j ω(L−1) e a(ω)

and



Q (ω)

 D(ω)
 



0 ..

0

(5.38)

 . 

.

(5.39)

Q (ω)

Substituting (5.30) into (5.37), we obtain the joint surrogate log-likelihood of γ and µ: 1 1 ln p(γ, µ | α(ω), Q (ω)) = −LM ln π − ln |D(ω)| − [Sg γ + Sm µ − α(ω)ρ(ω)] H L L  × D−1 (ω)[Sg γ + Sm µ − α(ω)ρ(ω)] + C J , (5.40)

where CJ is a constant that accounts for the Jacobian of the nonunitary transformation between y˜ and γ and µ in (5.30). To derive the EM algorithm for the current set of assumptions, we note that ˆ i−1 (ω), we have (as in (5.18)–(5.20)) for given αˆ i−1 (ω) and Q µ | γ, θˆ i−1 ∼ CN (b, K),

(5.41)

where


 b = E µ | γ, θˆ i−1



−1   ˆ i−1 (ω)S˜ g S˜ T D ˆ i−1 (ω)S˜ g γ − S˜ gT ρ(ω)αˆ i−1 (ω) = S˜ mT ρ(ω)αˆ i−1 (ω) + S˜ mT D g (5.42)

44

SPECTRAL ANALYSIS OF SIGNALS

and   K = cov µ | γ, θˆ i−1

−1 ˆ i−1 (ω)S˜ m − S˜ T D ˆ i−1 (ω)S˜ g S˜ T D ˆ i−1 (ω)S˜ g ˆ i−1 (ω)S˜ m . S˜ T D = S˜ T D m

m

g

g

(5.43)

Expectation: Following the same steps as in (5.21) and (5.22), we obtain the conditional expectation of the surrogate log-likelihood function in (5.40):   1 i−1 i−1 ˆ ln p(γ, µ | α(ω), Q (ω)) | γ, αˆ (ω), Q (ω) E L  1 1 −1  = −M ln π − ln |D(ω)| − tr D (ω) Sm KSmT L L   H + [Sg γ + Sm b − α(ω)ρ(ω)][Sg γ + Sm b − α(ω)ρ(ω)] (5.44) + C J. Maximization: To maximize the expected surrogate log-likelihood function in (5.44), we need to exploit the known structure of D(ω) and ρ(ω). Let  z0  .   .. 
Sg γ + Sm b   z L−1 

(5.45)

denote the data snapshots made up of the available and estimated data samples, where each zl , l = 0, . . . , L − 1, is an M × 1 vector. Also let Γ0 , . . . , Γ L−1 be the M × M blocks on the block diagonal of Sm KSmT . Then the expected surrogate log-likelihood function we need to maximize with respect to α(ω) and Q (ω) becomes (to within an additive constant)

 L−1      1 j ωl j ωl H zl − α(ω)a(ω)e − ln |Q (ω)| − tr Q (ω) Γl + zl − α(ω)a(ω) e . L l=0 −1

(5.46) The solution can be readily obtained by a derivation similar to that in Section 5.3: αˆ 2 (ω) =

a H (ω)S˜ −1 (ω)Z(ω) a H (ω)S˜ −1 (ω)a(ω)

(5.47)

1-D MISSING-DATA APES VIA EM

45

and ˜ ˆ 2 (ω) = S(ω) + [αˆ 2 (ω)a(ω) − Z(ω)][αˆ 2 (ω)a(ω) − Z(ω)] H , Q

(5.48)

where S(ω) and Z(ω) are defined as L−1 L−1 1 1 ˜
Γl + zl z H − Z(ω)Z H (ω) S(ω) L l=0 L l=0 l

(5.49)

and Z(ω)


L−1 1 zl e −j ωl . L l=0

(5.50)

The derivation of the MAPES-EM2 algorithm is thus complete, and a step-by-step summary of this algorithm is as follows: Step 0: Obtain an initial estimate of {α(ω), Q (ω)}. Step 1: Use the most recent estimates of {α(ω), Q (ω)} in (5.42) and (5.43) to calculate b and K. Note that b can be regarded as the current estimate of the missing sample vector. Step 2: Update the estimates of {α(ω), Q (ω)} using (5.47) and (5.48). Step 3: Repeat steps 1 and 2 until practical convergence.

5.5

ASPECTS OF INTEREST

5.5.1 Some Insights into the MAPES-EM Algorithms ˆ 1 (ω)} in (5.26) and (5.27) [or {αˆ 2 (ω), Q ˆ 2 (ω)} in (5.47) and Comparing {αˆ 1 (ω), Q ˆ (ω)} in (4.13) and (4.14), we can see that the EM algorithms ˆ (5.48)] with {α(ω), Q are doing some intuitively obvious things. In particular, the estimator of α(ω) estimates the missing data and then uses the estimate {b¯ l } (or b) as though it were correct. The estimator of Q (ω) does the same thing, but it also adds an extra ¯ l (or K), which can be regarded as a term involving the conditional covariance K generalized diagonal loading operation to make the spectral estimate robust against estimation errors.

46

SPECTRAL ANALYSIS OF SIGNALS

We stress again that the MAPES approach is based on a surrogate likelihood function that is not the true likelihood of the data snapshots. However, such surrogate likelihood functions (for instance, based on false uncorrelatedness or Gaussian assumptions) are known to lead to satisfactory fitting criteria, under fairly reasonable conditions (see, e.g., [42, 49]). Furthermore, it can be shown that the EM algorithm applied to such a surrogate likelihood function (which is a valid probability distribution function) still has the key property in (5.5) to monotonically increase the function at each iteration.

5.5.2 MAPES-EM1 Versus MAPES-EM2 Because at each iteration and at each frequency of interest ω, MAPES-EM2 estimates the missing samples only once (for all data snapshots), it has a lower computational complexity than MAPES-EM1, which estimates the missing samples separately for each data snapshot. It is also interesting to observe that MAPES-EM1 makes the assumption that the snapshots {¯yl } are independent when formulating the surrogate data likelihood function, and it maintains this assumption when estimating the missing data—hence a “consistent” ignoring of the overlapping. On the other hand, MAPES-EM2 makes the same assumption when formulating the surrogate data likelihood function, but in a somewhat “inconsistent” manner it observes the overlapping when estimating the missing data. This suggests that MAPES-EM2, which estimates fewer unknowns than MAPES-EM1, may not necessarily have a (much) better performance, as might be expected (see the examples in Section 5.7).

5.5.3 Missing-Sample Estimation For many applications, such as data restoration, estimating the missing samples is needed and can be done via the MAPES-EM algorithms. For MAPES-EM2, at each frequency of interest ω, we take the conditional mean b as an estimate of the missing sample vector. The final estimate of the missing sample vector is the average of all b obtained from all frequencies of interest. For MAPES-EM1, at

1-D MISSING-DATA APES VIA EM

47

each frequency ω of interest, there are multiple estimates (obtained from different overlapping data snapshots) for the same missing sample. We calculate the mean of these multiple estimates before averaging once again across all frequencies of interest. We remark that we should not consider the {b¯ l } (or b) at each frequency ω as an estimate of the ω-component of the missing data because other frequency components contribute to the residue term as well, which determines the covariance matrix Q (ω) in the APES model.

5.5.4 Initialization Since in general there is no guarantee that the EM algorithm will converge to a global maximum, the MAPES-EM algorithms may converge to a local maximum, which depends on the initial estimate θˆ 0 used. To demonstrate the robustness of our MAPES-EM algorithms to the choice of the initial estimate, we will simply let the initial estimate of α(ω) be given by the WFFT with the missing data samples set to zero. The initial estimate of Q (ω) follows from (4.8), where again, the missing data samples are set to zero.

5.5.5 Stopping Criterion We stop the iteration of the MAPES-EM algorithms whenever the relative change   in the total power of the spectra corresponding to the current αˆ i (ωk ) and previous   i−1 αˆ (ωk ) estimates is smaller than a preselected threshold (e.g.,  = 10−3 ): K −1 i K −1 i−1 |αˆ (ωk )|2 − k=0 |αˆ (ωk )|2 | |k=0 K −1 i−1 k=0 |αˆ (ωk )|2

≤ ,

(5.51)

ˆ where we evaluate α(ω) on a K -point DFT grid: ωk = 2πk/K , for k = 0, . . . , K − 1.

5.6

MAPES COMPARED WITH GAPES

As explained above, MAPES is derived from a surrogate ML formulation of the APES algorithm; on the other hand, GAPES is derived from a LS formulation

48

SPECTRAL ANALYSIS OF SIGNALS

of APES [32]. In the complete-data case, these two approaches are equivalent in the sense that from either of them we can derive the same full-data APES spectral estimator. So at first, it might look counterintuitive that these two algorithms (MAPES and GAPES) will perform differently for the missing-data problem (see the numerical results in Section 5.7). We will now give a brief discussion about this issue. The difference between MAPES and GAPES concerns the way they estimate µ when some data samples are missing. Although MAPES-EM estimates each missing sample separately for each frequency ωk (and for each data snapshot y¯ l in MAPES-EM2) while GAPES estimates each missing sample by considering all K frequencies together, the real difference between them concerns the different criteria used in (3.16) and (5.3) for the estimation of µ: GAPES estimates the missing sample µ based on a LS fitting of the filtered data, h H (ωk )¯yl . On the other hand, MAPES estimates the missing sub-sample µ directly from {¯yl } based on an ML fitting criterion. Because the LS formulation of APES focuses on the output of the filter h(ωk ) (which is supposed to suppress any other frequency components except ωk ), the GAPES algorithm is sensitive to the errors in h(ωk ) when it tries to estimate the missing data. This is why GAPES performs well in the gapped-data case, since there a good estimate of h(ωk ) can be calculated during the initialization step. However, when the missing samples occur in an arbitrary pattern, the performance of GAPES degrades. Yet the MAPES-EM does not suffer from such a degradation.

5.7

NUMERICAL EXAMPLES

In this section we present detailed results of a few numerical examples to demonstrate the performance of the MAPES-EM algorithms for missing-data spectral estimation. We compare MAPES-EM with WFFT and GAPES. A Taylor window with order 5 and sidelobe level −35 dB is used for WFFT. We choose K = 32N to have a fine grid of discrete frequencies. We calculate the corresponding WFFT spectrum via zero-padded FFT. The so-obtained WFFT spectrum is

1-D MISSING-DATA APES VIA EM

49

used as the initial spectral estimate for the MAPES-EM and GAPES algorithms. The initial estimate of Q (ω) for MAPES-EM has been discussed before, and the initial estimate of h(ω) for GAPES is calculated from (2.12), where the missing samples are set to zero. We stop the MAPES-EM and the GAPES algorithms using the same stopping criterion in (5.51) with  being selected as 10−3 and 10−2 , respectively. The reason we choose a larger  for GAPES is that it converges relatively slowly for the general missing-data problem and its spectral estimate would not improve much if we used an  < 10−2 . All the adaptive filtering algorithms considered (i.e. APES, GAPES, and MAPES-EM) use a filter length of M = N/2 for achieving high resolution. The true spectrum of the simulated signal is shown in Fig. 5.1(a), where we have four spectral lines located at f 1 = 0.05 Hz, f 2 = 0.065 Hz, f 3 = 0.26 Hz, and f 4 = 0.28 Hz with complex amplitudes α1 = α2 = α3 = 1 and α4 = 0.5. Besides these spectral lines, Fig. 5.1(a) also shows a continuous spectral component centered at 0.18 Hz with a width b = 0.015 Hz and a constant modulus of 0.25. The data sequence has N = 128 samples among which 51 (40%) samples are missing; the locations of the missing samples are chosen arbitrarily. The data is corrupted by a zero-mean circularly symmetric complex white Gaussian noise with variance σn2 = 0.01. In Fig. 5.1(b), the APES algorithm is applied to the complete data and the resulting spectrum is shown. The APES spectrum will be used later as a reference for comparison purposes. The WFFT spectrum for the incomplete data is shown in Fig. 5.1(c), where the artifacts due to the missing data are readily observed. As expected, the WFFT spectrum has poor resolution and high sidelobes and it underestimates the true spectrum. Note that the WFFT spectrum will be used as the initial estimate for the GAPES and MAPES algorithms. Fig. 5.1(d) shows the GAPES spectrum. GAPES also underestimates the sinusoidal components and gives some artifacts. Apparently, owing to the poor initial estimate of h(ωk ) for the incomplete data, GAPES converges to one of the local minima of the cost function in (3.16). Figs. 5.1(e) and 5.1(f ) show the MAPES-EM1 and MAPES-EM2

1.2

Modulus of Complex Amplitude

Modulus of Complex Amplitude

SPECTRAL ANALYSIS OF SIGNALS

1

0.8

0.6

0.4

0.2

0 0

1.2

1

0.8

0.6

0.4

0.2

0.1

0.2

0.3

0.4

0 0

0.5

0.1

Frequency (Hz)

Modulus of Complex Amplitude

Modulus of Complex Amplitude

1

0.8

0.6

0.4

0.2

0.4

0.5

0.4

0.5

0.4

0.5

1.2

1

0.8

0.6

0.4

0.2

0.1

0.2

0.3

0.4

0 0

0.5

0.1

Frequency (Hz)

0.2

0.3

Frequency (Hz)

(c)

(d) Modulus of Complex Amplitude

1.2

1

0.8

0.6

0.4

0.2

0 0

0.3

(b)

1.2

0 0

0.2

Frequency (Hz)

(a)

Modulus of Complex Amplitude

50

1.2

1

0.8

0.6

0.4

0.2

0.1

0.2

0.3

0.4

0.5

0 0

Frequency (Hz)

(e)

0.1

0.2

0.3

Frequency (Hz)

(f)

FIGURE 5.1: Modulus of the missing-data spectral estimates [N = 128, σn2 = 0.01, 51 (40%) missing samples]. (a) True spectrum, (b) complete-data APES, (c) WFFT, (d) GAPES with M = 64 and  = 10−2 , (e) MAPES-EM1 with M = 64 and  = 10−3 , and (f ) MAPES-EM2 with M = 64 and  = 10−3 .

1-D MISSING-DATA APES VIA EM

51

spectral estimates. Both MAPES algorithms perform quite well and their spectral estimates are similar to the high-resolution APES spectrum in Fig. 5.1(b). The MAPES-EM1 and MAPES-EM2 spectral estimates at different iterations are plotted in Figs. 5.2(a) and 5.2(b), respectively. Both algorithms converge quickly with MAPES-EM1 converging after 10 iterations while MAPES-EM2 after only 6. The data restoration performance of MAPES-EM is shown in Fig. 5.3. The missing samples are estimated using the averaging approach we introduced previously. Figs. 5.3(a) and 5.3(b) display the real and imaginary parts of the interpolated data, respectively, obtained via MAPES-EM1. Figs. 5.3(c) and 5.3(d) show the corresponding results for MAPES-EM2. The locations of the missing samples are also indicated in Fig. 5.3. The missing samples estimated via the MAPESEM algorithms are quite accurate. More detailed results for MAPES-EM2 are shown in Fig. 5.4. (Those for MAPES-EM1 are similar.) For a clear visualization, only the estimates of the first three missing samples are shown in Fig. 5.4. The real and imaginary parts of the estimated samples as a function of frequency are plotted in Figs. 5.4(a) and 5.4(b), respectively. All estimates are close to the corresponding true values, which are also indicated in Fig. 5.4. It is interesting to note that larger variations occur at frequencies where strong signal components are present. The results displayed so far were for one randomly picked realization of the data. Using 100 Monte Carlo simulations (varying the realizations of the noise, the initial phases of the different spectral components, and the missing-data patterns), we obtain the root mean-squared errors (RMSEs) of the magnitude and phase estimates of the four spectral lines at their true frequency locations. These RMSEs for WFFT, GAPES, and MAPES-EM are listed in Tables 5.1 and 5.2. Based on this limited set of Monte Carlo simulations, we can see that the two MAPES-EM algorithms perform similarly, and that they are much more accurate than WFFT and GAPES. A similar behavior has been observed in several other numerical experiments.

i=0

1

Modulus

Modulus

SPECTRAL ANALYSIS OF SIGNALS

0.5

0 0.2

0.3

0.4

i=1

1

0.5

0

0.1

0.2

0.3

0.4

0.2

0.3

0.4

0.5

i=1

1

0.5

0.5

i=2

1

0

Modulus

Modulus

0.1

0 0

0.5

0

0.1

0.2

0.3

0.4

0.5

i=2

1

0.5

0 0

0.1

0.2

0.3

0.4

0.5

i=3

1

0

Modulus

Modulus

0.5

0.5

Modulus

Modulus

0.1

0

0.5

0

0.1

0.2

0.3

0.4

0.5

i=3

1

0.5

0 0

0.1

0.2

0.3

0.4

0.5

i=4

1

0

Modulus

Modulus

i=0

1

0 0

0.5

0

0.1

0.2

0.3

0.4

0.5

i=4

1

0.5

0 0

0.1

0.2

0.3

0.4

0.5

i=5

1

0

Modulus

Modulus

52

0.5

0

0.1

0.2

0.3

0.4

0.5

i=5

1

0.5

0 0

0.1

0.2

0.3

0.4

0.5

Frequency (Hz)

(a)

0

0.1

0.2

0.3

0.4

0.5

Frequency (Hz)

(b)

FIGURE 5.2: Modulus of the missing-data spectral estimates obtained via the MAPESEM algorithms at different iterations [N = 128, σn2 = 0.01, 51 (40%) missing samples]. (a) MAPES-EM1 and (b) MAPES-EM2.

1-D MISSING-DATA APES VIA EM

Real Part of Signal

4

True Data Interpolated Data Missing Data Locations

2

0

−2

−4

20

40

60

80

100

120

n

(a) Imaginary Part of Signal

4

True Data Interpolated Data Missing Data Locations

2

0

−2

−4

20

40

60

80

100

120

n

(b) Real Part of Signal

4

True Data Interpolated Data Missing Data Locations

2

0

−2

−4

20

40

60

80

100

120

n

(c) Imaginary Part of Signal

4

True Data Interpolated Data Missing Data Locations

2

0

−2

−4

20

40

60

80

100

120

n

(d) FIGURE 5.3: Interpolation of the missing samples [N = 128, σn2 = 0.01, 51 (40%) missing samples]. (a) Real part of the data interpolated via MAPES-EM1, (b) imaginary part of the data interpolated via MAPES-EM1, (c) real part of the data interpolated via MAPESEM2, and (d) imaginary part of the data interpolated via MAPES-EM2.

53

SPECTRAL ANALYSIS OF SIGNALS

Real Part of Missing Sample Estimates

2.5 2 1.5 1 0.5 0 −0.5

1st Missing Sample 2nd Missing Sample 3rd Missing Sample True Value (1st) True Value (2nd) True Value (3rd)

−1 −1.5 −2

−2.5

0

0.1

0.2

0.3

0.4

0.5

Frequency (Hz)

(a) Imaginary Part of Missing Sample Estimates

54

2.5 2 1.5 1 0.5 0 −0.5 1st Missing Sample 2nd Missing Sample 3rd Missing Sample True Value (1st) True Value (2nd) True Value (3rd)

−1 −1.5 −2 −2.5 0

0.1

0.2

0.3

0.4

0.5

Frequency (Hz)

(b) FIGURE 5.4: Estimation of the first three missing samples versus frequency [N = 128, σn2 = 0.01, 51 (40%) samples are missing, vertical dotted lines indicate the true frequency locations of the spectral components with the closely spaced lines indicating the continuous spectral component]. (a) Real part and (b) imaginary part of the missing samples estimated via MAPES-EM2.

1-D MISSING-DATA APES VIA EM

55

TABLE 5.1: RMSEs of the Magnitude Estimates Obtained via the WFFT, GAPES, and MAPES-EM Spectral Estimators

WFFT

GAPES

MAPES-EM1

MAPES-EM2

Signal 1

0.420

0.175

0.010

0.011

Signal 2

0.417

0.205

0.010

0.010

Signal 3

0.419

0.169

0.010

0.009

Signal 4

0.205

0.164

0.009

0.011

Next, we increase the number of missing samples to 77 (60% of the original data). The results of WFFT, WFFT GAPES, MAPES-EM 1, and MAPESEM2 are shown in Figs. 5.5(a)–5.5(d), respectively. The signal amplitudes in the WFFT spectrum are low presumably due to the small (40%) amount of available data samples. The artifacts are so high that we can hardly identify the signal components. GAPES also performs poorly [see Fig. 5.5(b)], as expected. The MAPES-EM algorithms provide excellent spectral estimates with relatively minor artifacts. In our next experiment, we keep the 40% data missing rate but increase the noise variance to σn2 = 0.1 (10 dB higher than in the previous experiments). The

TABLE 5.2: RMSEs of the Phase (Radian) Estimates Obtained via the WFFT, GAPES, and MAPES-EM Spectral Estimators

WFFT

GAPES

MAPES-EM1

MAPES-EM2

Signal 1

0.077

0.042

0.021

0.021

Signal 2

0.059

0.038

0.024

0.025

Signal 3

0.099

0.037

0.012

0.013

Signal 4

0.133

0.029

0.022

0.022

1.2

Modulus of Complex Amplitude

Modulus of Complex Amplitude

SPECTRAL ANALYSIS OF SIGNALS

1

0.8

0.6

0.4

0.2

1.2

1

0.8

0.6

0.4

0.2

0 0

0.1

0.2

0.3

0.4

0 0

0.5

0.1

Frequency (Hz)

0.2

0.3

0.4

0.5

0.4

0.5

Frequency (Hz)

(a)

(b)

1.2

Modulus of Complex Amplitude

Modulus of Complex Amplitude

56

1

0.8

0.6

0.4

0.2

1.2

1

0.8

0.6

0.4

0.2

0 0

0.1

0.2

0.3

Frequency (Hz)

(c)

0.4

0.5

0 0

0.1

0.2

0.3

Frequency (Hz)

(d)

FIGURE 5.5: Modulus of the missing-data spectral estimates [N = 128, σn2 = 0.01, 77 (60%) missing samples] obtained via. (a) WFFT, (b) GAPES with M = 64 and  = 10−2 , (c) MAPES-EM1 with M = 64 and  = 10−3 , and (d) MAPES-EM2 with M = 64 and  = 10−3 .

corresponding moduli of the spectral estimates of complete-data WFFT, APES, missing-data WFFT, GAPES, MAPES-EM1, and MAPES-EM2 are plotted in Figs. 5.6(a)–5.6(f ), respectively. Again, the performance of the MAPES-EM algorithms is excellent. In our last experiment, we plot the RMSEs of the MAPES-EM1 estimates as functions of the missing sample rate in Fig. 5.7. Only the RMSEs of the estimates of first spectral line located at f 1 = 0.05 Hz are plotted since the results for others

1.2

Modulus of Complex Amplitude

Modulus of Complex Amplitude

1-D MISSING-DATA APES VIA EM

1

0.8

0.6

0.4

0.2

0 0

1.2

1

0.8

0.6

0.4

0.2

0.1

0.2

0.3

0.4

0 0

0.5

0.1

Frequency (Hz)

0.2

Modulus of Complex Amplitude

Modulus of Complex Amplitude

1

0.8

0.6

0.4

0.2

0.5

0.4

0.5

0.4

0.5

1.2

1

0.8

0.6

0.4

0.2

0.1

0.2

0.3

0.4

0 0

0.5

0.1

Frequency (Hz)

0.2

0.3

Frequency (Hz)

(c)

(d)

1.2

Modulus of Complex Amplitude

Modulus of Complex Amplitude

0.4

(b)

1.2

1

0.8

0.6

0.4

0.2

0 0

0.3

Frequency (Hz)

(a)

0 0

57

1.2

1

0.8

0.6

0.4

0.2

0.1

0.2

0.3

0.4

0.5

0 0

0.1

Frequency (Hz)

(e)

0.2

0.3

Frequency (Hz)

(f)

FIGURE 5.6: Modulus of the missing-data spectral estimates [N = 128, σn2 = 0.1, 51 (40%) missing samples] obtained via (a) complete-data WFFT, (b) complete-data APES, (c) WFFT, (d) GAPES with M = 64 and  = 10−2 , (e) MAPES-EM1 with M = 64 and  = 10−3 , and (f ) MAPES-EM2 with M = 64 and  = 10−3 .

SPECTRAL ANALYSIS OF SIGNALS 0.18

0.16

SNR=0 SNR=5 SNR=10 SNR=15 SNR=20

0.14

RMSE

0.12

0.1

0.08

0.06

0.04

0.02

0 0.1

0.15

0.2

0.25

0.3 0.35 0.4 missing sample rate

0.45

0.5

0.55

0.6

0.45

0.5

0.55

0.6

(a) 0.14

0.12

SNR=0 SNR=5 SNR=10 SNR=15 SNR=20

0.1

0.08 RMSE

58

0.06

0.04

0.02

0 0.1

0.15

0.2

0.25

0.3 0.35 0.4 missing sample rate

(b) FIGURE 5.7: RMSEs of the estimates of the first spectral line located at f 1 = 0.05 Hz obtained via MAPES-EM1. (a) Amplitude and (b) Phase (radian).

1-D MISSING-DATA APES VIA EM

59

are similar. Each result is based on 100 Monte Carlo simulations (by varying, in each trial, the realization of the noise, the initial phases of the different spectral components, and the missing-data pattern). The signal-to-noise ratio (SNR) is defined as SNR1 = 10 log10

|α1 |2 σn2

(dB),

(5.52)

with α1 being the complex amplitude of the first sinusoid. For each fixed SNR, the RMSEs increase as the number of missing samples increases. Also as expected, the RMSEs decrease when the SNR increases. Similar results can be observed for MAPES-EM2.

61

C H A P T E R

6

Two-Dimensional MAPES via Expectation Maximization and Cyclic Maximization 6.1

INTRODUCTION

In Chapter 5, we proposed the 1-D MAPES-EM algorithms to deal with the general missing-data problem where the missing data samples occur in arbitrary patterns [45]. The MAPES-EM algorithms were derived following a ML fitting based approach in which a ML fitting problem was solved iteratively via the EM algorithm. MAPES-EM exhibits better spectral estimation performance than GAPES does. However, the MAPES-EM algorithms are computationally intensive due to estimating the missing samples separately for each frequency of interest. The direct application of MAPES-EM to large data sets, e.g., 2-D data, is computationally prohibitive. Herein we consider the problem of 2-D nonparametric spectral estimation of data matrices with missing data samples occurring in arbitrary patterns [50]. First, we present the 2-D extensions of the MAPES-EM algorithms introduced in [45] in the 1-D case. Then we develop a new MAPES algorithm, referred to as MAPES-CM, by solving an ML problem iteratively via cyclic maximization (CM) [42]. MAPES-EM and MAPES-CM possess similar spectral estimation

62

SPECTRAL ANALYSIS OF SIGNALS

performance, but the computational complexity of the latter is much lower than that of the former. The remainder of this chapter is organized as follows: In Section 6.2, we review the 2-D nonparametric APES algorithm. In Section 6.3, we present 2-D extensions of the MAPES-EM algorithms and develop the 2-D MAPES-CM algorithm in Section 6.4. In Section 6.5, we compare MAPES-CM with MAPESEM, from both theoretical and computational points of view. Numerical examples are provided in Section 6.6 to demonstrate the performance of the MAPES algorithms.

6.2

TWO-DIMENSIONAL ML-BASED APES

In this section we provide the 2-D extension of APES, devised via a ML fitting based approach, for complete-data spectral estimation. Consider the 2-D problem introduced in Section 3.3.1. Partition the N1 × N2 data matrix 

y0,0

  y1,0  Y
 .  ..  y N1 −1,0

y0,1

···

y0,N2 −1

y1,1 .. .

··· .. .

y1,N2 −1 .. .

y N1 −1,1

···

y N1 −1,N2 −1

      

(6.1)

into L1 L2 overlapping submatrices of size M1 × M2 :  Y¯ l 1 ,l 2

yl 1 ,l 2

  yl +1,l 1 2  = . ..   yl 1 +M1 −1,l 2

yl 1 ,l 2 +1

···

yl 1 ,l 2 +M2 −1

yl 1 +1,l 2 +1 .. .

··· .. .

yl 1 +1,l 2 +M2 −1 .. .

yl 1 +M1 −1,l 2 +1

···

yl 1 +M1 −1,l 2 +M2 −1

    ,  

(6.2)

where l 1 = 0, . . . , L1 − 1, l 2 = 0, . . . , L2 − 1, L1
N1 − M1 + 1, and L2
N2 − M2 + 1. Increasing M1 and M2 typically increases the spectral resolution at the cost of reducing the statistical stability of the spectral estimates due to the

2-D MAPES VIA EM AND CYCLIC MAXIMIZATION

63

reduced number of submatrices. Typically, we choose M1 = N1 /2 and M2 = N2 /2 [13, 15]. Recall that y¯ l 1 ,l 2 = vec[Y¯ l 1 ,l 2 ]

(6.3)

a(ω1 , ω2 ) = a M2 (ω2 ) ⊗ a M1 (ω1 ),

(6.4)

and

where ⊗ denotes the Kronecker matrix product, and a Mk (ωk )
[1

e j ωk

···

e j (Mk −1)ωk ]T ,

k = 1, 2.

(6.5)

Then, according to (3.17), the snapshot vector y¯ l 1 ,l 2 corresponding to Y¯ l 1 ,l 2 can be written as y¯ l 1 ,l 2 = [α(ω1 , ω2 )a(ω1 , ω2 )] · e j (ω1 l 1 +ω2 l 2 ) + e¯ l 1 ,l 2 (ω1 , ω2 ),

(6.6)

where e¯ l 1 ,l 2 (ω1 , ω2 ) is formed from {e n1 ,n2 (ω1 , ω2 )} in the same way as y¯ l 1 ,l 2 is made from {yn1 ,n2 }. To estimate α(ω1 , ω2 ), the APES algorithm mimics an ML estima−1,L2 −1 are zero-mean circularly symmetric tor by assuming that {¯el 1 ,l 2 (ω1 , ω2 )}lL1 1=0,l 2 =0

complex Gaussian random vectors that are statistically independent of each other and have the same unknown covariance matrix   Q (ω1 , ω2 ) = E e¯ l 1 ,l 2 (ω1 , ω2 )¯elH1 ,l 2 (ω1 , ω2 ) .

(6.7)

Using the above assumptions, we get the normalized surrogate log-likelihood function of the data snapshots {¯yl 1 ,l 2 } as follows: 1 ln p({¯yl 1 ,l 2 } | α(ω1 , ω2 ), Q (ω1 , ω2 )) L1 L2 = −M1 M2 ln π − ln |Q (ω1 , ω2 )| −

2 −1 1 −1 L  H 1 L y¯ l 1 ,l 2 − α(ω1 , ω2 )a(ω1 , ω2 ) e j (ω1 l 1 +ω2 l 2 ) L1 L2 l 1 =0 l 2 =0

(6.8)

64

SPECTRAL ANALYSIS OF SIGNALS

  Q−1 (ω1 , ω2 ) y¯ l 1 ,l 2 − α(ω1 , ω2 )a(ω1 , ω2 ) e j (ω1 l 1 +ω2 l 2 )

2 −1 1 −1 L 1 L = −M1 M2 ln π − ln |Q (ω1 , ω2 )| − tr Q−1 (ω1 , ω2 ) L1 L2 l 1 =0 l 2 =0   y¯ l 1 ,l 2 − α(ω1 , ω2 )a(ω1 , ω2 ) e j (ω1 l 1 +ω2 l 2 )   H y¯ l 1 ,l 2 − α(ω1 , ω2 )a(ω1 , ω2 ) e j (ω1 l 1 +ω2 l 2 ) . (6.9) Just as in the 1-D case, the maximization of the above surrogate likelihood function gives the APES estimator ˆ 1 , ω2 ) = α(ω

¯ 1 , ω2 ) a H (ω1 , ω2 )Sˆ −1 (ω1 , ω2 )g(ω a H (ω1 , ω2 )Sˆ −1 (ω1 , ω2 )a(ω1 , ω2 )

(6.10)

and ˆ 1 , ω2 ) + [αˆ ML (ω1 , ω2 )a(ω1 , ω2 ) − g(ω ˆ (ω1 , ω2 ) = S(ω ¯ 1 , ω2 )] Q ¯ 1 , ω2 )] H , × [αˆ ML (ω1 , ω2 )a(ω1 , ω2 ) − g(ω

(6.11)

ˆ 1 , ω2 ) are as defined in Section 3.3.1. ˆ g(ω ¯ 1 , ω2 ), and S(ω where R,

6.3

TWO-DIMENSIONAL MAPES VIA EM

Assume that some arbitrary elements of the data matrix Y are missing. Because of these missing data samples, which can be treated as unknowns, the log-likelihood function (6.8) cannot be maximized directly. In this section, we will show how to tackle this missing-data problem, in the ML context, using the EM and CM algorithms. A comparison of these two approaches is also provided.

6.3.1 Two-Dimensional MAPES-EM1 We assume that the data snapshots {Y¯ l 1 ,l 2 } (or {¯yl 1 ,l 2 }) are independent of each other, and we estimate the missing data separately for different data snapshots. For each ¯ l 1 ,l 2 denote the vectors containing the available data snapshot y¯ l 1 ,l 2 , let γ¯ l 1 ,l 2 and µ and missing elements of y¯ l 1 ,l 2 , respectively. Assume that γ¯ l 1 ,l 2 has dimension g l 1 ,l 2 × 1, where 1 ≤ g l 1 ,l 2 ≤ M1 M2 is the number of available elements in the

2-D MAPES VIA EM AND CYCLIC MAXIMIZATION

¯ l 1 ,l 2 are related to y¯ l 1 ,l 2 by unitary transformations snapshot y¯ l 1 ,l 2 . Then γ¯ l 1 ,l 2 and µ as follows: γ¯ l 1 ,l 2 = S¯ gT (l 1 , l 2 )¯yl 1 ,l 2

(6.12)

¯ l 1 ,l 2 = S¯ mT (l 1 , l 2 )¯yl 1 ,l 2 , µ

(6.13)

where S¯ g (l 1 , l 2 ) and S¯ m (l 1 , l 2 ) are M1 M2 × g l 1 ,l 2 and M1 M2 × (M1 M2 − g l 1 ,l 2 ) unitary selection matrices such that S¯ T (l 1 , l 2 )S¯ g (l 1 , l 2 ) = Ig , S¯ T (l 1 , l 2 )S¯ m (l 1 , l 2 ) = g

l 1 ,l 2

m

I M1 M2 −g l1 ,l2 , and S¯ gT (l 1 , l 2 )S¯ m (l 1 , l 2 ) = 0g l1 ,l2 ×(M1 M2 −g l1 ,l2 ) . For example, let M1 = 3, M2 = 2, and let   Y¯ l 1 ,l 2 =  



yl 1 ,l 2







yl 1 +2,l 2

yl 1 +2,l 2 +1

 , 

(6.14)

where each  indicates a missing sample. Then we have g l 1 ,l 2 = 3, y¯ l 1 ,l 2 = [yl 1 ,l 2



yl 1 +2,l 2





yl 1 +2,l 2 +1 ]T ,

(6.15)

and 

1 0

 0    ¯Sg (l 1 , l 2 ) =  0  0  0  0

0 1 0 0 0

0





 0   0 ,  0  0  1

0

 1    ¯Sm (l 1 , l 2 ) =  0  0  0  0

0 0 0 1 0 0

0



 0   0 .  0  1  0

(6.16)

Because we have   y¯ l 1 ,l 2 = S¯ g (l 1 , l 2 )S¯ gT (l 1 , l 2 ) + S¯ m (l 1 , l 2 )S¯ mT (l 1 , l 2 ) y¯ l 1 ,l 2 ¯ l 1 ,l 2 = S¯ g (l 1 , l 2 )γ¯ l 1 ,l 2 + S¯ m (l 1 , l 2 )µ

(6.17)

65

66

SPECTRAL ANALYSIS OF SIGNALS

¯ l 1 ,l 2 } is obtained the joint normalized surrogate log-likelihood function of {γ¯ l 1 ,l 2 , µ by substituting (6.17) into (6.9) 1 ¯ l 1 ,l 2 } | α(ω1 , ω2 ), Q (ω1 , ω2 )) ln p({γ¯ l 1 ,l 2 , µ L1 L2

2 −1 1 −1 L 1 L = −M1 M2 ln π − ln |Q (ω1 , ω2 )| − tr Q −1 (ω1 , ω2 ) L1 L2 l 1 =0 l 2 =0

¯ l 1 ,l 2 − α(ω1 , ω2 )a(ω1 , ω2 ) e j (ω1 l 1 +ω2 l 2 ) S¯ g (l 1 , l 2 )γ¯ l 1 ,l 2 + S¯ m (l 1 , l 2 )µ

H  j (ω1 l 1 +ω2 l 2 ) ¯Sg (l 1 , l 2 )γ¯ ¯ ¯ l 1 ,l 2 − α(ω1 , ω2 )a(ω1 , ω2 ) e . l 1 ,l 2 + Sm (l 1 , l 2 )µ (6.18) ¯ l 1 ,l 2 conditioned Just as in the 1-D case, the probability density function of µ i−1 on γ¯ l 1 ,l 2 (for given θ = θˆ ) is complex Gaussian with mean b¯ l 1 ,l 2 and covariance ¯ l ,l : matrix K 1 2

i−1 ¯ l ,l ), ¯ l 1 ,l 2 | γ¯ l 1 ,l 2 , θˆ ∼ CN (b¯ l 1 ,l 2 , K µ 1 2

(6.19)

where    i−1 ¯ l 1 ,l 2  γ¯ l 1 ,l 2 , θˆ b¯ l 1 ,l 2 = E µ = S¯ mT (l 1 , l 2 )a(ω1 , ω2 )αˆ i−1 (ω1 , ω2 ) e j (ω1 l 1 +ω2 l 2 ) ˆ i−1 (ω1 , ω2 )S¯ g (l 1 , l 2 )S¯ T (l 1 , l 2 )Q ˆ i−1 (ω1 , ω2 )S¯ g (l 1 , l 2 )−1 + S¯ mT (l 1 , l 2 )Q g   (6.20) × γ¯ l 1 ,l 2 − S¯ gT (l 1 , l 2 )a(ω1 , ω2 )αˆ i−1 (ω1 , ω2 ) e j (ω1 l 1 +ω2 l 2 ) and    ¯ l ,l = cov µ ˆ i−1  ¯ ¯ K γ , θ l 1 ,l 2 l 1 ,l 2 1 2 ˆ i−1 (ω1 , ω2 )S¯ m (l 1 , l 2 ) − S¯ T (l 1 , l 2 )Q ˆ i−1 (ω1 , ω2 )S¯ g (l 1 , l 2 ) = S¯ mT (l 1 , l 2 )Q m  ˆ i−1 (ω1 , ω2 )S¯ g (l 1 , l 2 )−1 S¯ T (l 1 , l 2 )Q ˆ i−1 (ω1 , ω2 )S¯ m (l 1 , l 2 ). × S¯ gT (l 1 , l 2 )Q g (6.21)

2-D MAPES VIA EM AND CYCLIC MAXIMIZATION

67

Expectation: The conditional expectation of the surrogate log-likelihood in (6.18) according to (6.19)–(6.21) is given by

1 ¯ l 1 ,l 2 } | α(ω1 , ω2 ), Q (ω1 , ω2 ))| ln p({γ¯ l 1 ,l 2 , µ E L1 L2  i−1 i−1 ˆ {γ¯ l 1 ,l 2 }, αˆ (ω1 , ω2 ), Q (ω1 , ω2 )  = −M1 M2 ln π − ln |Q (ω1 , ω2 )| − tr Q−1 (ω1 , ω2 ) 2 −1  1 −1 L 1 L ¯ l ,l S¯ T (l 1 , l 2 ) S¯ m (l 1 , l 2 )K × 1 2 m L1 L2 l 1 =0 l 2 =0   + S¯ g (l 1 , l 2 )γ¯ l 1 ,l 2 + S¯ m (l 1 , l 2 )b¯ l 1 ,l 2 − α(ω1 , ω2 )a(ω1 , ω2 ) e j (ω1 l 1 +ω2 l 2 )  H   . × S¯ g (l 1 , l 2 )γ¯ l 1 ,l 2 + S¯ m (l 1 , l 2 )b¯ l 1 ,l 2 − α(ω1 , ω2 )a(ω1 , ω2 ) e j (ω1 l 1 +ω2 l 2 )

(6.22) Maximization: The normalized expected surrogate log-likelihood (6.22) can be rewritten as



− M1 M2 ln π − ln |Q (ω1 , ω2 )| − tr Q−1 (ω1 , ω2 )   + z¯ l 1 ,l 2 − α(ω1 , ω2 )a(ω1 , ω2 ) e j (ω1 l 1 +ω2 l 2 ) 

× z¯ l 1 ,l 2 − α(ω1 , ω2 )a(ω1 , ω2 ) e

2 −1  1 −1 L 1 L Γ¯ l 1 ,l 2 L1 L2 l 1 =0 l 2 =0



  j (ω1 l 1 +ω2 l 2 ) H

,

(6.23)

where we have defined ¯ l ,l S¯ T (l 1 , l 2 ) Γ¯ l 1 ,l 2
S¯ m (l 1 , l 2 )K 1 2 m

(6.24)

z¯ l 1 ,l 2
S¯ g (l 1 , l 2 )γ¯ l 1 ,l 2 + S¯ m (l 1 , l 2 )b¯ l 1 ,l 2 .

(6.25)

and

Maximizing (6.23) gives αˆ 1 (ω1 , ω2 ) =

¯ 1 , ω2 ) a H (ω1 , ω2 )S¯ −1 (ω1 , ω2 )Z(ω a H (ω1 , ω2 )S¯ −1 (ω1 , ω2 )a(ω1 , ω2 )

(6.26)

68

SPECTRAL ANALYSIS OF SIGNALS

and ¯ 1 , ω2 ) + [αˆ 1 (ω1 , ω2 )a(ω1 , ω2 ) − Z(ω ¯ 1 , ω2 )] ˆ 1 (ω1 , ω2 ) = S(ω Q ¯ 1 , ω2 )] H , × [αˆ 1 (ω1 , ω2 )a(ω1 , ω2 ) − Z(ω

(6.27)

where ¯ 1 , ω2 )
Z(ω

2 −1 1 −1 L 1 L z¯ l ,l e−j (ω1 l 1 +ω2 l 2 ) L1 L2 l 1 =0 l 2 =0 1 2

(6.28)

and ¯ 1 , ω2 )
S(ω

2 −1 2 −1 1 −1 L 1 −1 L 1 L 1 L ¯ 1 , ω2 )Z ¯ H (ω1 , ω2 ). z¯ l ,l z¯ H − Z(ω Γ¯ l 1 ,l 2 + L1 L2 l 1 =0 l 2 =0 L1 L2 l 1 =0 l 2 =0 1 2 l 1 ,l 2

(6.29) This completes the derivation of the 2-D MAPES-EM1 algorithm, a step-by-step summary of which is as follows: Step 0: Obtain an initial estimate of {α(ω1 , ω2 ), Q (ω1 , ω2 )}. Step 1: Use the most recent estimate of {α(ω1 , ω2 ), Q (ω1 , ω2 )} in (6.20) and (6.21) ¯ l ,l , respectively. Note that b¯ l ,l can be regarded as to calculate b¯ l ,l and K 1 2

1 2

1 2

the current estimate of the corresponding missing samples. Step 2: Update the estimate of {α(ω1 , ω2 ), Q (ω1 , ω2 )} using (6.26) and (6.27). Step 3: Repeat steps 1 and 2 until practical convergence.

6.3.2 Two-Dimensional MAPES-EM2 MAPES-EM2 utilizes the EM algorithm by estimating the missing data simultaneously for all data snapshots. Let y = vec[Y]

(6.30)

denote the vector of all the data samples. Recall that γ and µ denote the vectors containing the available and missing elements of y, respectively, where γ has a size of g × 1.

2-D MAPES VIA EM AND CYCLIC MAXIMIZATION

69

We let y˜ denote the L1 L2 M1 M2 × 1 vector obtained by concatenating all the snapshots:   y˜
 

y¯ 0,0 .. .

   = Sg γ + Sm µ, 

(6.31)

y¯ L1 −1,L2 −1 where Sg (which has a size of L1 L2 M1 M2 × g ) and Sm (which has a size of L1 L2 M1 M2 × (N1 N2 − g )) are the corresponding selection matrices for the available and missing data vectors, respectively. Because of the overlapping of the vectors {¯yl 1 ,l 2 }, Sg and Sm are not unitary, but they are still orthogonal to each other: SgT Sm = 0g ×(N1 N2 −g ) . So instead of (6.12) and (6.13), we have from (6.31):  −1 T γ = SgT Sg Sg y˜ = S˜ gT y˜

(6.32)

−1 T  µ = SmT Sm Sm y˜ = S˜ mT y˜ ,

(6.33)

and

where the matrices S˜ g and S˜ m introduced above are defined as S˜ g
Sg (SgT Sg )−1 , S˜ m
Sm (ST Sm )−1 , and they are also orthogonal to each other: S˜ T S˜ m = 0g ×(N N −g ) . m

g

1

2

Now the normalized surrogate log-likelihood function in (6.8) can be written as 1 ln p(˜y | α(ω1 , ω2 ), Q (ω1 , ω2 )) L1 L2 1 1 ln |D(ω1 , ω2 )| − [˜y − α(ω1 , ω2 )ρ(ω1 , ω2 )] H = −M1 M2 ln π − L1 L2 L1 L2 × D−1 (ω1 , ω2 )[˜y − α(ω1 , ω2 )ρ(ω1 , ω2 )], (6.34) where ρ(ω1 , ω2 ) and D(ω1 , ω2 ) are defined as  e j (ω1 0+ω2 0) a(ω1 , ω2 )  .. ρ(ω1 , ω2 )
 .  e j [ω1 (L1 −1)+ω2 (L2 −1)] a(ω1 , ω2 )

   

(6.35)

70

SPECTRAL ANALYSIS OF SIGNALS

and   D(ω1 , ω2 )
 

Q (ω1 , ω2 )

0 ..

0

.

   

(6.36)

Q (ω1 , ω2 )

Substituting (6.31) into (6.34), we obtain the joint surrogate log-likelihood of γ and µ: 1 ln p(γ, µ | α(ω1 , ω2 ), Q (ω1 , ω2 )) L1 L2

1 = − L1 L2 M1 M2 ln π − ln |D(ω1 , ω2 )| L1 L2 H −1 D (ω1 , ω2 ) − [Sg γ + Sm µ − α(ω1 , ω2 )ρ(ω1 , ω2 )] × [Sg γ + Sm µ − α(ω1 , ω2 )ρ(ω1 , ω2 )] + CJ

(6.37)

where CJ is a constant that accounts for the Jacobian of the nonunitary transformation between y˜ and γ and µ in (6.31). To derive the EM algorithm for the current set of assumptions, we have i−1 ∼ CN (b, K), µ | γ, θˆ

(6.38)

where   i−1  b = E µ γ, θˆ

  ˆ i−1 (ω1 , ω2 )S˜ g S˜ T D ˆ i−1 (ω1 , ω2 )S˜ g −1 = S˜ mT ρ(ω1 , ω2 )αˆ i−1 (ω1 , ω2 ) + S˜ mT D g   × γ − S˜ gT ρ(ω1 , ω2 )αˆ i−1 (ω1 , ω2 ) (6.39)

and    i−1 K = cov µ γ, θˆ ˆ i−1 (ω1 , ω2 )S˜ m − S˜ T D ˆ i−1 (ω1 , ω2 )S˜ g = S˜ mT D m   ˆ i−1 (ω1 , ω2 )S˜ g −1 S˜ T D ˆ i−1 (ω1 , ω2 )S˜ m × S˜ gT D g

(6.40)

2-D MAPES VIA EM AND CYCLIC MAXIMIZATION

71

Expectation: The conditional expectation of the surrogate log-likelihood function in (6.37) is given as

  1 i−1 i−1 ˆ  ˆ E ln p(γ, µ | α(ω1 , ω2 ), Q (ω1 , ω2 )) γ, α (ω1 , ω2 ), Q (ω1 , ω2 ) L1 L2  1  1 = − M1 M2 ln π − ln |D(ω1 , ω2 )| − tr D−1 (ω1 , ω2 ) Sm KSmT L1 L2 L1 L2    H  + Sg γ + Sm b − α(ω1 , ω2 )ρ(ω1 , ω2 ) Sg γ + Sm b − α(ω1 , ω2 )ρ(ω1 , ω2 ) + CJ .

(6.41) Maximization: To maximize the expected surrogate log-likelihood function in (6.41), we again exploit the known structure of D(ω1 , ω2 ) and ρ(ω1 , ω2 ). Let    

z0,0 .. .

  
Sg γ + Sm b 

(6.42)

z L1 −1,L2 −1 denote the data snapshots made up of the available and estimated data samples, where each zl 1 ,l 2 (l 1 = 0, . . . , L1 − 1 and l 2 = 0, . . . , L2 − 1) is an M1 M2 × 1 vector. Also let Γ0,0 , . . . , Γ L1 −1,L2 −1 be the M1 M2 × M1 M2 blocks on the block diagonal of Sm KSmT . Then the expected surrogate log-likelihood function we need to maximize with respect to α(ω1 , ω2 ) and Q (ω1 , ω2 ) becomes (to within an additive constant)

2 −1  1 −1 L 1 L Γl 1 ,l 2 L1 L2 l 1 =0 l 2 =0  − α(ω1 , ω2 )a(ω1 , ω2 ) e j (ω1 l 1 +ω2 l 2 )    j (ω1 l 1 +ω2 l 2 ) H − α(ω1 , ω2 )a(ω1 , ω2 ) e .

− ln |Q (ω1 , ω2 )| − tr Q−1 (ω1 , ω2 )  + zl 1 ,l 2  × zl 1 ,l 2

(6.43)

The solution becomes αˆ 2 (ω1 , ω2 ) =

a H (ω1 , ω2 )S−1 (ω1 , ω2 )Z(ω1 , ω2 ) a H (ω1 , ω2 )S−1 (ω1 , ω2 )a(ω1 , ω2 )

(6.44)

72

SPECTRAL ANALYSIS OF SIGNALS

and ˆ 2 (ω1 , ω2 ) = S(ω1 , ω2 ) + [αˆ 2 (ω1 , ω2 )a(ω1 , ω2 ) − Z(ω1 , ω2 )] Q × [αˆ 2 (ω1 , ω2 )a(ω1 , ω2 ) − Z(ω1 , ω2 )] H ,

(6.45)

where S(ω1 , ω2 ) and Z(ω1 , ω2 ) are defined as S(ω1 , ω2 )


2 −1 2 −1 1 −1 L 1 −1 L 1 L 1 L Γl 1 ,l 2 + zl ,l z H L1 L2 l 1 =0 l 2 =0 L1 L2 l 1 =0 l 2 =0 1 2 l 1 ,l 2

− Z(ω1 , ω2 )Z H (ω1 , ω2 ). and Z(ω1 , ω2 )


(6.46)

2 −1 1 −1 L 1 L zl ,l e −j (ω1 l 1 +ω2 l 2 ) . L1 L2 l 1 =0 l 2 =0 1 2

(6.47)

The derivation of the MAPES-EM2 algorithm is thus complete, and a step-by-step summary of this algorithm is as follows: Step 0: Obtain an initial estimate of {α(ω1 , ω2 ), Q (ω1 , ω2 )}. Step 1: Use the most recent estimates of {α(ω1 , ω2 ), Q (ω1 , ω2 )} in (6.39) and (6.40) to calculate b and K. Note that b can be regarded as the current estimate of the missing sample vector. Step 2: Update the estimates of {α(ω1 , ω2 ), Q (ω1 , ω2 )} using (6.44) and (6.45). Step 3: Repeat steps 1 and 2 until practical convergence.

6.4

TWO-DIMENSIONAL MAPES VIA CM

Next we consider evaluating the spectrum on the K 1 × K 2 -point DFT grid. Instead of dealing with each individual frequency (ωk1 , ωk2 ) separately, we consider the following maximization problem:

K 2 −1 1 −1 K − ln |Q (ωk1 , ωk2 )| − max µ,{α(ωk1,ωk2 ),Q (ωk1,ωk2 )}

k1 =0 k2 =0



2 −1 1 −1 L 1 L L1 L2 l 1 =0 l 2 =0  j (ωk l 1 +ωk l 2 ) H

2 y¯ l 1 ,l 2 − α(ωk1 , ωk2 )a(ωk1 , ωk2 ) e 1    −1 j (ωk1 l 1 +ωk2 l 2 ) , × Q (ωk1 , ωk2 ) y¯ l 1 ,l 2 − α(ωk1 , ωk2 )a(ωk1 , ωk2 ) e

(6.48)

2-D MAPES VIA EM AND CYCLIC MAXIMIZATION

73

where the objective function is the summation over the 2-D frequency grid of all the frequency-dependent complete-data likelihood functions in (6.8) (within an additive constant). We solve the above optimization problem via a CM approach. i−1 formed from {αˆ i−1 (ωk , ωk ), First, assuming that the previous estimate θˆ 1

2

ˆ i−1 (ωk , ωk )} is available, we maximize (6.48) with respect to µ. This step can Q 1 2 be reformulated as min

K 2 −1 1 −1 K

µ



 H  ˆ i−1 −1 y˜ − αˆ i−1 (ωk1 , ωk2 )ρ(ωk1 , ωk2 ) D (ωk1 , ωk2 )

k =0 k =0

1  2  × y˜ − αˆ i−1 (ωk1 , ωk2 )ρ(ωk1 , ωk2 ) ,

(6.49)

ˆ i−1 (ω1 , ω2 ) have been defined previously. Recalling where y˜ , ρ(ωk1 , ωk2 ), and D that y˜ = Sg γ + Sm µ, we can easily solve the optimization problem in (6.49) as its objective function is quadratic in µ:   K K 2 −1 2 −1 1 −1 K 1 −1 K  −1   ˆ i−1 −1 ˆ i−1 (ωk , ωk ) Sm ˆ = SmH D SmH D (ωk1 , ωk2 ) µ 1 2 k 1 =0 k 2 =0 × [αˆ i−1 (ωk1 , ωk2 )ρ(ωk1 , ωk2 )

k1 =0 k 2 =0

− Sg γ].

(6.50)

A necessary condition for the inverse in (6.50) to exist is that L1 L2 M1 M2 > N1 N2 − g , which is always satisfied. ˆ has become available, we reestimate {α(ωk1 , ωk2 )} and Once an estimate µ ˆ This can be done by {Q (ωk1 , ωk2 )} by maximizing (6.48) with µ replaced by µ. maximizing each frequency term separately: max

α(ωk1 ,ωk2 ),Q(ωk1 ,ωk2 )

− ln |Q(ωk1 , ωk2 )| −

2 −1 1 −1 L 1 L L1 L2 l 1 =0 l 2 =0

 H yˆ¯ l 1 ,l 2 − α(ωk1 , ωk2 )a(ωk1 , ωk2 ) e j (ωk1 l 1 +ωk2 l 2 )   × Q−1 (ωk1 , ωk2 ) yˆ¯ l 1 ,l 2 − α(ωk1 , ωk2 )a(ωk1 , ωk2 ) e j (ωk1 l 1 +ωk2 l 2 ) ,

(6.51) which reduces to the 2-D APES problem. A cyclic maximization of (6.48) can be implemented by the alternating maximization with respect to µ and, respectively, α(ωk1 , ωk2 ) and Q (ωk1 , ωk2 ). A stepby-step summary of 2-D MAPES-CM is as follows:

74

SPECTRAL ANALYSIS OF SIGNALS

Step 0: Obtain an initial estimate of {α(ωk1 , ωk2 ), Q (ωk1 , ωk2 )}. Step 1: Use the most recent estimates of {α(ωk1 , ωk2 ), Q (ωk1 , ωk2 )} in (6.50) to estimate the missing samples. Step 2: Update the estimates of {α(ω1 , ω2 ), Q (ωk1 , ωk2 )} using 2-D APES applied to the data matrices with the missing sample estimates from step 1 [see (6.10) and (6.11)]. Step 3: Repeat steps 1 and 2 until practical convergence.

6.5

MAPES-EM VERSUS MAPES-CM

Consider evaluating the spectrum for all three MAPES algorithms on the same DFT grid. Since all three algorithms iterate step 1 and step 2 until practical convergence, we can compare their computational complexity separately for each step. •

In step 1, MAPES-CM estimates the missing samples via (6.50), which can be rewritten in a simplified form as  −1  H  ˆ = SmH Ds Sm Sm Dυ − SmH Ds Sg γ , µ

(6.52)

where Ds


K 2 −1 1 −1 K

ˆ i−1 (ωk , ωk )]−1 [D 1 2

(6.53)

k 1 =0 k2 =0

and Dυ


K 2 −1 1 −1 K

ˆ i−1 (ωk , ωk )]−1 αˆ i−1 (ωk , ωk )ρ(ωk , ωk ). [D 1 2 1 2 1 2

(6.54)

k 1 =0 k 2 =0

ˆ i−1 (ωk , ωk ) is block diagonal When computing Ds and Dυ , the fact that D 1 2 can be exploited to reduce the computational complexity. Comparing (6.52) with (6.39) and (6.40) [or (6.20) and (6.21)], which have to be evaluated for each frequency (ωk1 , ωk2 ) [and for each snapshot (l 1 , l 2 ) for (6.20) and (6.21)], we note that the computational complexity of MAPES-CM is much lower.

2-D MAPES VIA EM AND CYCLIC MAXIMIZATION

•

75

In step 2, MAPES-CM uses the standard APES algorithm, which can be efficiently implemented [34, 35] as discussed in Section 2.6. As for the MAPES-EM spectral estimators αˆ 1 (ω1 , ω2 ) and αˆ 2 (ω1 , ω2 ), they have the same structure as the APES estimator in (6.10), but with two differences. The first one is using the conditional mean (b¯ l ,l or b) of the missing 1 2

samples as their estimates. The second one is the additional terms (Γ¯ l 1 ,l 2 and ¯ l ,l and K) of the missing data Γl ,l ) that involve the covariance matrices (K 1 2

1 2

in the S¯ and S matrices. Because MAPES-EM uses different estimates for the missing data at different frequencies, those techniques used to efficiently implement APES cannot be applied here (see Section 2.6). As a result, no efficient algorithms are available to calculate the corresponding spectral estimate. In summary, the MAPES-CM algorithm possesses a computational complexity that is much lower than that of MAPES-EM.

6.6

NUMERICAL EXAMPLES

In this section, we present three numerical examples to illustrate the performance of the MAPES algorithms for the 2-D missing-data spectral estimation problem. We compare the MAPES algorithms with the WFFT and the GAPES [3]. A Taylor window with order 5 and sidelobe level −35 dB is used to obtain the WFFT spectral estimates. All the 2-D spectra are plotted with a dynamic range of 35 dB. As in the 1-D case, we simply let the initial estimate of α(ω1 , ω2 ) be given by the WFFT with the missing data samples set to zero. The initial estimate of Q (ω1 , ω2 ) follows from the 2-D counterpart of (4.8), where again, the missing data samples are set to zero. For the initialization of GAPES, we consider two cases. If the data missing pattern is arbitrary and no initial filter with a proper size can be chosen, we use the same initial estimates of α(ω1 , ω2 ) and Q (ω1 , ω2 ) as for MAPES, and the initial estimate of H(ω1 , ω2 ) follows from (3.29), where the missing samples are set to zero. If the data is gapped, as in examples

76

SPECTRAL ANALYSIS OF SIGNALS

discussed in Sections 6.6.2 and 6.6.3, we follow the initialization step considered in Chapter 3. We stop the iteration of all iterative algorithms whenever the relative change in the total power of the 2-D spectra corresponding to the current (αˆ i (ωk1 , ωk2 )) and previous (αˆ i−1 (ωk1 , ωk2 )) estimates is smaller than a preselected threshold (e.g.,  = 10−2 ):   K1 −1  K2 −1  k1 =0

k 2 =0

  −1  K2 −1 i−1 ˆ (ωk1 , ωk2 )|2  |αˆ i (ωk1 , ωk2 )|2 − kK11=0 k2 =0 |α ≤ .  K1 −1  K2 −1 i−1 ˆ (ωk1 , ωk2 )|2 k1 =0 k2 =0 |α (6.55)

6.6.1 Convergence Speed In our first example, we study the convergence properties of the MAPES algorithms. We use a 1-D example for simplicity. (Note that a similar 1-D example was considered in Chapter 5 but without the MAPES-CM algorithm, which has been introduced in this chapter.) The true spectrum of the simulated signal is shown in Fig. 5.1(a), where we have four spectral lines located at f 1 = 0.05 Hz, f 2 = 0.065 Hz, f 3 = 0.26 Hz, and f 4 = 0.28 Hz with complex amplitudes α1 = α2 = α3 = 1 and α4 = 0.5. Besides these spectral lines, Fig. 5.1(a) also shows a continuous spectral component centered at 0.18 Hz with a width of 0.015 Hz and a constant modulus of 0.25. The data sequence has N1 = 128 (N2 = 1) samples out of which 51 (40%) samples are missing; the locations of the missing samples are chosen arbitrarily. The data are corrupted by a zero-mean circularly symmetric complex white Gaussian noise with standard deviation 0.1. In Fig. 6.1(a), the APES algorithm is applied to the complete data and the resulting spectrum is shown. The APES spectrum will be used later as a reference for comparison purposes. The WFFT spectrum for the incomplete data is shown in Fig. 6.1(b). As expected, the WFFT spectrum has poor resolution and high sidelobes, and it underestimates the true spectrum. Note that the WFFT spectrum will be used as initial estimate for both the GAPES and MAPES algorithms in this

1.2

Modulus of Complex Amplitude

Modulus of Complex Amplitude

2-D MAPES VIA EM AND CYCLIC MAXIMIZATION

1

0.8

0.6

0.4

0.2

0 0

1.2

1

0.8

0.6

0.4

0.2

0.1

0.2

0.3

0.4

0 0

0.5

0.1

Frequency (Hz)

0.2

1.2

1

0.8

0.6

0.4

0.2

0.4

0.5

0.4

0.5

1

0.8

0.6

0.4

0.2

0.1

0.2

0.3

0.4

0 0

0.5

0.1

0.2

0.3

Frequency (Hz)

(c)

(d)

1.2

Modulus of Complex Amplitude

Modulus of Complex Amplitude

0.5

1.2

Frequency (Hz)

1

0.8

0.6

0.4

0.2

0 0

0.4

(b) Modulus of Complex Amplitude

Modulus of Complex Amplitude

(a)

0 0

0.3

Frequency (Hz)

1.2

1

0.8

0.6

0.4

0.2

0.1

0.2

0.3

Frequency (Hz)

(e)

0.4

0.5

0 0

0.1

0.2

0.3

Frequency (Hz)

(f)

FIGURE 6.1: Modulus of the missing-data spectral estimates [N1 = 128, N2 = 1, 51 (40%) missing samples]. (a) Complete-data APES, (b) WFFT, (c) GAPES with M1 = 64 and M2 = 1, (d) MAPES-CM with M1 = 64 and M2 = 1, (e) MAPES-EM1 with M1 = 64 and M2 = 1, and (f ) MAPES-EM2 with M1 = 64 and M2 = 1.

77

78

SPECTRAL ANALYSIS OF SIGNALS

example. Fig. 6.1(c) shows the GAPES spectrum, which also underestimates the sinusoidal components and gives some artifacts due to the poor initial estimate of H(ω1 , ω2 ). The MAPES-CM spectrum is plotted in Fig. 6.1(d). Figs. 6.1(e) and 6.1(f ) show the MAPES-EM1 and MAPES-EM2 spectra, respectively. All the MAPES algorithms perform quite well and their missing-data spectral estimates are similar to the high-resolution complete-data APES spectrum in Fig. 6.1(a). The MAPES and GAPES spectral estimates at different iterations are plotted in Figs. 6.2(a)–6.2(d). Among the MAPES algorithms, MAPES-CM is the fastest to converge, after three iterations. MAPES-EM converges more slowly, with MAPES-EM1 converging after 11 and MAPES-EM2 after 9 iterations. Because of the relatively poor initial filter-bank H(ω1 , ω2 ) used in this example, the GAPES algorithm performs relatively poorly and converges relatively slowly, after ten iterations. In the following examples where the gapped-data initialization step in Chapter 3 can be applied, GAPES usually converges faster, within a few iterations. For illustration purposes, in Figure 6.2 we only plot the first four iterations of each method and note that the convergence behavior of each algorithm does not change significantly in the remaining iterations.

6.6.2 Performance Study In this example, we illustrate the performance of the MAPES algorithms for 2-D spectral estimation. We consider a 16 × 16 data matrix consisting of three 2-D sinusoids (signals 1, 2, and 3) at normalized frequencies (4/16, 5/16), (6/16, 5/16), and (10/16, 9/16) and with complex amplitudes equal to 1, 0.7, and 2, respectively, embedded in zero-mean circularly symmetric complex Gaussian white noise with standard deviation 0.1. All the samples in rows 4, 8, 11, 14, and in columns 3, 6, 7, 11, 12, 14 are missing, which amounts to over 50% of the total number of data samples. The true amplitude spectrum is plotted in Fig. 6.3(a) with the estimated amplitude values given next to each sinusoid. Each spectrum is obtained on a 64 × 64 grid. The WFFT spectrum of the complete data is shown in Fig. 6.3(b) along with the estimated magnitudes of the sinusoids at their true locations. The

Modulus

Modulus

2-D MAPES VIA EM AND CYCLIC MAXIMIZATION i=0

1 0.5 0 0.2

0.3

0.4

0.5

i=1

1

0

Modulus

Modulus

0.1

0.5 0 0.2

0.3

0.4

0.2

i=2

1 0.5 0.2

0.3

0.4

0.1

0.2

0.4

0.5

i=2

0.5 0

i=3

0.5

0.1

0.2

0.3

0.4

0.5

i=3

1 0.5 0

0.2

0.3

0.4

0.5

i=4

1

0

Modulus

0.1

0.5 0

0.1

0.2

0.3

0.4

0.5

i=4

1 0.5 0

0

0.1

0.2

0.3

0.4

0.5

0

0.1

Frequency (Hz)

0.2

0.3

0.4

0.5

Frequency (Hz)

(b) Modulus

(a) Modulus

0.3

1

0.5

Modulus

0.1

1

0

i=0

1 0.5 0

i=0

1 0.5 0

0.1

0.2

0.3

0.4

0.5

i=1

1

0

Modulus

0

Modulus

0.5

i=1

1

0

0

0.5 0

0.1

0.2

0.3

0.4

0.5

i=1

1 0.5 0

0.1

0.2

0.3

0.4

0.5

i=2

1

0

Modulus

0

Modulus

0.4

0 0

0.5 0

0.1

0.2

0.3

0.4

0.5

i=2

1 0.5 0

0.1

0.2

0.3

0.4

0.5

i=3

1

0

Modulus

0

Modulus

0.3

0.5

0.5

Modulus

Modulus

0.1

0

Modulus

0.1

0 0

Modulus

i=0

1 0.5 0

0

0.5 0

0.1

0.2

0.3

0.4

0.5

i=3

1 0.5 0

0.1

0.2

0.3

0.4

0.5

i=4

1

0

Modulus

0

Modulus

79

0.5 0

0.1

0.2

0.3

0.4

0.5

i=4

1 0.5 0

0

0.1

0.2

0.3

0.4

0.5

Frequency (Hz)

(c)

0

0.1

0.2

0.3

0.4

0.5

Frequency (Hz)

(d)

FIGURE 6.2: Modulus of the missing-data spectral estimates obtained at different iterations [N1 = 128, N2 = 1, 51 (40%) missing samples]. (a) MAPES-CM, (b) MAPESEM1, (c) MAPES-EM2, and (d) GAPES.

80

SPECTRAL ANALYSIS OF SIGNALS 0

0

0

0.1 0.2

0.2

0.2

1.0000

0.3

0.99808

0.7000

0.4

1.005

0.68569

0.4

0.70055

0.4

0.5 0.6

0.6

0.6

2.0000

2.0014

2.0017

0.7 0.8

0.8

0.8

0.9 0

0.2

0.4

0.6

0.8

0

0.2

(a)

0.4

0.6

0.8

0

0.2

(b)

0.4

0.6

0.8

(c)

0

0

2 4

0.2

0.2 0.42636

0.9768

6 0.32908

0.4

0.64683

0.4

8 10

0.6

0.6 0.84218

1.9866

12 0.8

14

0.8

16 2

4

6

8

10

12

14

16

0

0.2

(d)

0.4

0.6

0.8

0.2

0.2

0.99644

0.69643

0.4

0.6 1.9936

1.9853

0.8

0.2

0.4

(g)

0.6

0.70751

0.4

0.6 1.9916

0.8

0.8

0.8

0.2 1.0136

0.6

0.6

0

1.0069 0.70073

0.4

(f)

0

0

0.2

(e)

0

0.4

0

0.8

0

0.2

0.4

(h)

0.6

0.8

0

0.2

0.4

0.6

0.8

(i)

FIGURE 6.3: Modulus of the 2-D spectra. (a) True spectrum, (b) 2-D complete-data WFFT, (c) 2-D complete-data APES with M1 = M2 = 8, (d) 2-D data missing pattern, the black stripes indicate missing samples, (e) 2-D WFFT, (f ) 2-D GAPES with M1 = M2 = 8, (g) 2-D MAPES-EM1 with M1 = M2 = 8, (h) 2-D MAPES-EM2 with M1 = M2 = 8, and (i) 2-D MAPES-CM with M1 = M2 = 8.

2-D MAPES VIA EM AND CYCLIC MAXIMIZATION

81

TABLE 6.1: Computational Complexities of the WFFT, GAPES, MAPES-EM, and MAPES-CM Spectral Estimators

WFFT GAPES MAPES-EM1 MAPES-EM2 MAPES-CM Flops 3 × 105

3 × 109

1 × 1014

6 × 1012

3 × 1011

two closely spaced sinusoids are smeared together. Fig. 6.3(c) shows the APES spectrum, also constructed from the complete data, which has well-separated spectral peaks and accurately estimated magnitudes. The data missing pattern is displayed in Fig. 6.3(d). The WFFT spectrum for the missing-data case is shown in Fig. 6.3(e), which underestimates the sinusoids and contains strong artifacts due to the zeros assumed for the missing samples. Fig. 6.3(f ) shows the spectrum estimated by GAPES, with an initial filter of size 2 × 2. In Figs. 6.3(g)–6.3(i), we show the spectra estimated by MAPES-EM1, MAPES-EM2, and MAPES-CM, respectively. The GAPES algorithm estimates the signal magnitudes much more accurately than the WFFT, but not as well as the MAPES algorithms. All MAPES algorithms perform well giving accurate spectral estimates and clearly separated spectral peaks. Now we compare the computational complexities of these algorithms for the example in Fig. 6.3. The numbers of floating point operations (Flops) needed for different algorithms are given in Table 6.1. The WFFT algorithm is the most efficient, and GAPES is more efficient than the MAPES algorithms. Among MAPES, MAPES-CM is 20 times faster than MAPES-EM2, which is about 17 times faster than MAPES-EM1. The results displayed so far were for one typical realization of the data. Using 100 Monte Carlo simulations (by varying the realizations of the noise), we obtain the RMSEs of the magnitude and phase estimates of the three sinusoids at their true locations for WFFT, GAPES, and MAPES. The RMSEs of the magnitude and phase estimates are listed in Tables 6.2 and 6.3, respectively. MAPES-EM1 gives the best accuracy followed closely by MAPES-EM2 and MAPES-CM. GAPES is slightly less accurate, whereas the accuracy corresponding to the WFFT is much lower.

82

SPECTRAL ANALYSIS OF SIGNALS

TABLE 6.2: RMSEs of the Magnitude Estimates Obtained via the WFFT, GAPES, MAPES-EM, and MAPES-CM Spectral Estimators

WFFT

GAPES

MAPES-EM1

MAPES-EM2

MAPES-CM

Signal 1

0.577

0.021

0.010

0.013

0.014

Signal 2

0.372

0.053

0.009

0.014

0.014

Signal 3

1.156

0.011

0.008

0.011

0.015

6.6.3 Synthetic Aperture Radar Imaging Applications In the following two examples, we illustrate the applications of the missing-data algorithms to synthetic aperture radar (SAR) imaging using incomplete phasehistory data. Two-dimensional high-resolution phase-history data of a Slicy object at 0◦ azimuth angle were generated using XPATCH [51], a high frequency electromagnetic scattering prediction code for complex 3-D objects. A photo of the Slicy object taken at 45◦ azimuth angle is shown in Fig. 6.4(a). The original data matrix has a size of 288 × 288 with a resolution of 0.043 m in both range and cross-range. Fig. 6.4(b) shows the modulus of the 2-D WFFT image of the original data. Here, we consider only a 32 × 32 center block of the phase-history data. The APES image of the complete 32 × 32 data is shown in Fig. 6.4(c). The data missing pattern is displayed in Fig. 6.4(d), where the samples in rows 4, 14, 15, 22, 27,

TABLE 6.3: RMSEs of the Phase (Radian) Estimates Obtained via the WFFT, GAPES, MAPES-EM, and MAPES-CM Spectral Estimators

WFFT

GAPES

MAPES-EM1

MAPES-EM2

MAPES-CM

Signal 1

0.148

0.010

0.009

0.009

0.009

Signal 2

0.145

0.013

0.012

0.015

0.016

Signal 3

0.057

0.006

0.004

0.004

0.006

2-D MAPES VIA EM AND CYCLIC MAXIMIZATION

(a)

(b) 5

10

15

20

25

30 5

10

15

20

25

30

(c)

(d)

(e)

(f)

(g)

(h)

FIGURE 6.4: Modulus of the SAR images of the Slicy object obtained from a 32 × 32 data matrix with missing samples. (a) Photograph of the object (taken at 45◦ azimuth angle), (b) 2-D WFFT for a 288 × 288 (not 32 × 32) data matrix, (c) 2-D complete-data APES with M1 = M2 = 16, (d) 2-D data missing pattern, the black stripes indicate missing samples, (e) 2-D WFFT, (f ) 2-D GAPES with M1 = M2 = 16, (g) 2-D MAPES-CM with M1 = M2 = 16, and (h) 2-D MAPES-CM followed by 2-D rank-deficient RCF with a 20 × 20 filter-bank and a unit radius spherical constraint.

83

84

SPECTRAL ANALYSIS OF SIGNALS 60

60

50

50

40

40

30

30

20

20

10

10

10

20

30

40

50

60

10

20

30

(a)

40

60

60

25

50

50

20

40

40

15

30

30

10

20

20

5

10

10

10

15

(c)

20

25

30

60

(b)

30

5

50

10

20

30

40

50

(d)

60

10

20

30

40

50

60

(e)

FIGURE 6.5: Modulus of the SAR images of the Backhoe data obtained from a 32 × 32 data matrix with missing samples. (a) 2-D complete-data WFFT, (b) 2-D complete-data APES with a 2-D filter of size 16 × 16, (c) 2-D data missing pattern, the black stripes indicate missing samples, (d) 2-D WFFT, and (e) 2-D MAPES-CM with a 2-D filter of size 16 × 16.

28 and in columns 8, 9, 10, 20, 21, 22, 26, 27 are missing (possibly due to both angular diversity and strong interferences), resulting in 40% missing data. Fig. 6.4(e) shows the WFFT image, which has low resolution, high sidelobes, and smeared features. By using an initial filter matrix of size 6 × 6, the GAPES image is shown in Fig. 6.4(f ), where strong artifacts around the dihedrals are readily observed. The image reconstructed via MAPES-CM is shown in Fig. 6.4(g), which is quite similar to the complete-data image in Fig. 6.4(c). By observing that the missing-data algorithms developed previously estimate the missing data samples, we can achieve better spectral estimation performance,

2-D MAPES VIA EM AND CYCLIC MAXIMIZATION

85

for example, higher resolution than APES, based on the (complete) data interpolated via MAPES. It is known that the rank-deficient robust Capon filter-bank (RCF) spectral estimator [52] has higher resolution than the existing nonparametric spectral estimators. Hence based on the data interpolated via MAPES-CM, we apply rank-deficient RCF with a 20 × 20 filter-bank and a spherical steering vector uncertainty set with unit radius. The resulting image is shown in Fig. 6.4(h), which exhibits no sidelobe problem and retains all important features of Slicy. Compared with Fig. 6.4(b), we note that although the data size was reduced from 288 × 288 to 32 × 32 and from the reduced data matrix 40% of the samples were omitted, we can still obtain an image similar to that obtained by the WFFT applied to the original high-resolution data. [Note that we cannot get a similar high-resolution image with all the well-separated features and without sidelobe problem by simply thresholding Fig. 6.4(f ), 6.4(g), or even 6.4(c).] Next, we consider a 32 × 32 data matrix from the “Backhoe Data Dome, Version 1.0.” At 0◦ elevation, the data are collected from a 2◦ azimuth cut centered around 90◦ azimuth, covering a 0.3 GHz bandwidth centered around 10 GHz. Fig. 6.5(a) shows the WFFT image of the complete data matrix with smeared features. Fig. 6.5(b) shows the APES image of the complete data with a 16 × 16 2-D filter. Some smeared features in Fig. 6.5(a) are clearly observed here, such as the one located at row 26 and column 20. Fig. 6.5(c) illustrates the data missing pattern, where the samples in row 5, 13, 14, 21, 22, 27 and in columns 8, 9, 10, 18, 19, 20, 26, 27 are missing. Figs 6.5(d) and 6.5(e) show the WFFT and MAPESCM images of the missing-data matrix. It can be observed that despite the missing samples, MAPES-CM can still give a spectral estimate that has all the features shown in Fig. 6.5(b).

87

C H A P T E R

7

Conclusions and Software 7.1

CONCLUDING REMARKS

We have presented some recent results on nonparametric spectral analysis with missing samples. In particular, we have provided detailed discussions on using GAPES for the gapped-data and the more general MAPES for the arbitrarily missed-data spectral estimation problems. Both 1-D and 2-D applications are considered. Among these incomplete-data algorithms, GAPES has the least computational complexity, while MAPES-EM tends to give the best performance. According to their computational complexities, these algorithms can be arranged in ascending order, starting from the most efficient one: GAPES, MAPES-CM, MAPES-EM2, and MAPES-EM1. Clearly, there is a tradeoff between spectral estimation performance and computational efficiency. The reader needs to find out which algorithm is the best choice for each particular application, in terms of estimation accuracy and computational complexity. We now provide some general guidelines based on our own experience: 1. If the missing samples are grouped together and large continuous data segments are available, GAPES is recommended due to its good performance for the gapped-data problem and low computational complexity. 2. If the missing samples occur in arbitrary patterns, the MAPES algorithms should be used due to their excellent performances. MAPESCM is faster than MAPES-EM1 and MAPES-EM2, but with slightly

88

SPECTRAL ANALYSIS OF SIGNALS

worse performance. Hence MAPES-CM may be used for long 1-D data sequences or 2-D data matrices. MAPES-EM1 or its faster version, MAPES-EM2, may be used when computation is not a serious concern.

7.2

ONLINE SOFTWARE

Several Matlab codes of the algorithms discussed within this book can be downloaded from ftp://www.sal.ufl.edu/ywang. Here is a list of the available codes: 1. MAPES1D EM1.m

This function implements 1-D MAPES-EM1.

2. MAPES1D EM2.m

This function implements 1-D MAPES-EM2.

3. MAPES2D CM.m

This function implements 2-D MAPES-CM.

4. MAPES2D EM1.m

This function implements 2-D MAPES-EM1.

5. MAPES2D EM2.m

This function implements 2-D MAPES-EM2.

6. GAPES1 GappedData.m

This function implements 1-D GAPES for gapped-data spectral analysis.

7. GAPES1D MissingData.m

This function implements 1-D GAPES for arbitrarily missed-data spectral analysis.

8. GAPES2D GappedData

This is a directory that contains 2-D GAPES software for gapped-data spectral analysis.

9. GAPES2D GappedData.m

This is an example that demonstrates how to use 2-D GAPES for gapped data spectral analysis.

CONCLUSIONS AND SOFTWARE

10. dispimage.m

This is a function that plots 2-D spectrum.

11. taylor1.m

This is a function that calculates 1-D

89

Taylor window with sidelobe level −35 dB. 12. taylor2.m

This is a function that calculates 2-D Taylor window with sidelobe level −35 dB.

Note that the above Matlab codes are provided for verification purposes only. They are not optimized for specific applications.

91

References [1] P. Stoica, E. G. Larsson, and J. Li, “Adaptive filterbank approach to restoration and spectral analysis of gapped data,” Astron. J., vol. 120, pp. 2163–2173, Oct. 2000. doi:10.1086/301572 [2] E. Larsson, G. Liu, P. Stoica, and J. Li, “High-resolution SAR imaging with angular diversity,” IEEE Trans. Aerosp. Electron. Syst., vol. 37, no. 4, pp. 1359–1372, Oct. 2001. doi:10.1109/7.976971 [3] E. Larsson, P. Stoica, and J. Li, “Amplitude spectrum estimation for twodimensional gapped data,” IEEE Trans. Signal Processing, vol. 50, no. 6, pp. 1343–1354, June 2002. doi:10.1109/TSP.2002.1003059 [4] E. Larsson and J. Li, “Spectral analysis of periodically gapped data,” IEEE Trans. Aerosp. Electron. Syst., vol. 39, no. 3, pp. 1089–1097, July 2003. doi:10.1109/TAES.2003.1238761 [5] J. Salzman, D. Akamine, R. Lefevre, and J. Kirk, Jr., “Interrupted synthetic aperture radar (SAR),” in Proc. 2001 IEEE Radar Conf., Atlanta, GA, May 2001, pp. 117–122. doi:10.1109/NRC.2001.922962 [6] J. Salzman, D. Akamine, and R. Lefevre, “Optimal waveforms and processing for sparse frequency UWB operation,” in Proc. 2001 IEEE Radar Conf., Atlanta, GA, May 2001, pp. 105–110. doi:10.1109/NRC.2001.922960 [7] K. M. Cuomo, J. E. Piou, and J. T. Mayhan, “Ultrawide-band coherent processing,” IEEE Trans. Antennas Propagat., vol. 47, no. 6, pp. 1094–1107, June 1999. doi:10.1109/8.777137 [8] P. Stoica and R. L. Moses, Introduction to Spectral Analysis. Englewood Cliffs, NJ: Prentice-Hall, 1997. [9] J. P. Burg, “Maximum entropy spectral analysis,” in presented at the Proc. 37th Meeting Society Exploration Geophys., Oklahoma City, OK, Oct. 1967.

92

REFERENCES

[10] R. Schmidt, “A signal subspace approach to multiple emitter location and spectral estimation,” Ph.D. dissertation, Stanford University, CA, Nov. 1981. [11] J. Li and P. Stoica, “Efficient mixed-spectrum estimation with applications to target feature extraction,” IEEE Trans. Signal Processing, vol. 44, pp. 281– 295, Feb. 1996. doi:10.1109/78.485924 [12] J. Capon, “High resolution frequency-wavenumber spectrum analysis,” Proc. IEEE, vol. 57, pp. 1408–1418, Aug. 1969. [13] J. Li and P. Stoica, “An adaptive filtering approach to spectral estimation and SAR imaging,” IEEE Trans. Signal Processing, vol. 44, no. 6, pp. 1469–1484, June 1996. doi:10.1109/78.506612 [14] P. Stoica, A. Jakobsson, and J. Li, “Capon, APES and matched-filterbank spectral estimation,” Signal Process., vol. 66, no. 1, pp. 45–59, April 1998. doi:10.1016/S0165-1684(97)00239-9 [15] H. Li, J. Li, and P. Stoica, “Performance analysis of forward-backward matched-filterbank spectral estimators,” IEEE Trans. Signal Processing, vol. 46, pp. 1954–1966, July 1998. doi:10.1109/78.700967 [16] N. Lomb, “Least-squares frequency analysis of unequally spaced data,” Astrophys. Space Sci., pp. 447–462, 1976. doi:10.1007/BF00648343 [17] J. D. Scargle, “Studies in astronomical time series analysis II: Statistical aspects of spectral analysis of unevenly spaced data,” Astrophys. J., vol. 263, pp. 835–853, Dec. 1982. doi:10.1086/160554 [18] J. A. H¨ogbom, “Aperture synthesis with a non-regular distribution of interferometer baselines,” Astron. Astrophy. Suppl., vol. 15, pp. 417–426, 1974. [19] T. Bronez, “Spectral estimation of irregularly sampled multidimensional processes by generalized prolate spheroidal sequences,” IEEE Trans. Acoust. Speech Signal Process., vol. 36, no. 12, pp. 1862–1873, Dec. 1988. doi:10.1109/29.9031 [20] I. Fodor and P. Stark, “Multitaper spectrum estimation for time series with gaps,” IEEE Trans. Signal Processing, vol. 48, no. 12, pp. 3472–3483, Dec. 2000. doi:10.1109/78.887039

REFERENCES

93

[21] R. H. Jones, “Maximum likelihood fitting of ARMA models to time series with missing observations,” Technometrics, vol. 22, no. 3, pp. 389–395, Aug. 1980. [22] B. Porat and B. Friedlander, “ARMA spectral estimation of time series with missing observations,” IEEE Trans. Inform. Theory, vol. 30, no. 4, pp. 601– 602, July 1986. [23] Y. Rosen and B. Porat, “Optimal ARMA parameter estimation based on the sample covariances for data with missing observations,” IEEE Trans. Inform. Theory, vol. 35, no. 2, pp. 342–349, Mar. 1989. doi:10.1109/18.32128 [24] P. Broersen, S. de Waele, and R. Bos, “Estimation of autoregressive spectra with randomly missing data,” in Proc. 20th IEEE Instrument. Measure. Technol. Conf., Vail, CO, vol. 2, May 2003, pp. 1154–1159. [25] P. Stoica, H. Li, and J. Li, “Amplitude estimation of sinusoidal signals: Survey, newresults, and an application,” IEEE Trans. Signal Processing, vol. 48, no. 2, pp. 338–352, Feb. 2000. doi:10.1109/78.823962 [26] M. R. Palsetia and J. Li, “Using APES for interferometric SAR imaging,” IEEE Trans. Imaging Processing, vol. 7, no. 9, pp. 1340–1353, Sep. 1998. doi:10.1109/83.709665 [27] F. Gini and F. Lombardini, “Multilook APES for multibaseline SAR interferometry,” IEEE Trans. Signal Processing, vol. 50, no. 7, pp. 1800–1803, July 2002. doi:10.1109/TSP.2002.1011219 [28] ——, “Multibaseline post-processing for SAR interferometry,” presented at the Proc. IEEE Sensor Array Multichannel Signal Process. Workshop (SAM), Sitges, Spain, July 2004. [29] R. Wu, Z.-S. Liu, and J. Li, “Time-varying complex spectral analysis via recursive APES,” IEE Proc. Radar Sonar Navigation, vol. 145, no. 6, pp. 354–360, Dec. 1998. doi:10.1049/ip-rsn:19982435 [30] D. J. Russell and R. D. Palmer, “Application of APES to adaptive arrays on the CDMA reverse channel,” IEEE Trans. Veh. Technol., vol. 53, no. 1, pp. 3–17, Jan. 2004. doi:10.1109/TVT.2003.821991

94

REFERENCES

[31] H. Li, W. Sun, P. Stoica, and J. Li, “Two-dimensional system identification using amplitude estimation,” IEEE Signal Processing Lett., vol. 9, no. 2, pp. 61–63, Feb. 2002. doi:10.1109/97.991139 [32] P. Stoica, H. Li, and J. Li, “A new derivation of the APES filter,” IEEE Signal Processing Lett., vol. 6, no. 8, pp. 205–206, Aug. 1999. doi:10.1109/97.774866 [33] H. L. Van Trees, Optimum Array Processing, Part IV of Detection, Estimation, and Modulation Theory. New York, NY: John Wiley and Sons, Inc., 2002. [34] Z.-S. Liu, H. Li, and J. Li, “Efficient implementation of Capon and APES for spectral estimation,” IEEE Trans. Aerosp. Electron. Syst., vol. 34, no. 4, pp. 1314–1319, Oct. 1998. doi:10.1109/7.722716 [35] E. Larsson and P. Stoica, “Fast implementation of two-dimensional apes and capon spectral estimators,” Multidimen. Syst. Signal Process., vol. 13, pp. 35–54, Jan. 2002. doi:10.1023/A:1013891327453 [36] E. G. Larsson, J. Li, and P. Stoica, “High-resolution nonparametric spectral analysis: Theory and applications,” in High-Resolution and Robust Signal Processing, Y. Hua, A. B. Gershman, and Q. Cheng Eds. New York: MarcelDekker, 2003. [37] D. D. Meisel, “Fourier transforms of data sampled in unequally spaced segments,” Astron. J., vol. 84, no. 1, pp. 116–126, Jan. 1979. doi:10.1086/112397 [38] J. D. Scargle, “Studies in astronomical time series analysis III: Fourier transforms, autocorrelation functions, and cross-correlation functions of unevenly spaced data,” Astrophys. J., vol. 343, pp. 874–887, Aug. 1989. doi:10.1086/167757 [39] D. H. Roberts, J. Leh´ar, and J. W. Dreher, “Time series analysis with CLEAN I: Derivation of a spectrum,” Astron. J., vol. 93, no. 4, pp. 968– 989, April 1987. doi:10.1086/114383 [40] G. B. Rybicki and W. H. Press, “Interpolation, realization, and reconstruction of noisy, irregularly sampled data,” Astrophys. J., vol. 398, pp. 169–176, Oct. 1992. doi:10.1086/171845

REFERENCES

95

[41] W. Press and G. Rybicki, “Fast algorithm for spectral analysis of unevenly sampled data,” Astrophys. J., pp. 277–280, Mar. 1989. doi:10.1086/167197 [42] P. Stoica and Y. Selen, “Cyclic minimizers, majorization techniques, and the expectation-maximization algorithm: A refresher,” IEEE Signal Processing Mag., vol. 21, no. 1, pp. 112–114, Jan. 2004. doi:10.1109/MSP.2004.1267055 [43] P. Stoica and A. Nehorai, “Statistical analysis of two nonlinear least-squares estimators of sine-wave parameters in the colored-noise case,” Circuits Syst. Signal Process., vol. 8, no. 1, pp. 3–15, 1989. doi:10.1007/BF01598742 [44] P. Stoica, A. Jakobsson, and J. Li, “Sinusoid parameter estimation in the colored noise case: Asymptotic Cram´er-Rao bound, maximum likelihood and nonlinear least-squares,” IEEE Trans. Signal Processing, vol. 45, no. 8, pp. 2048–2059, Aug. 1997. doi:10.1109/78.611203 [45] Y. Wang, P. Stoica, J. Li, and T. Marzetta, “Nonparametric spectral analysis with missing data via the EM algorithm,” Digital Signal Processing, submitted for publication. [46] A. P. Dempster, N. M. Laird, and D. B. Rubin, “Maximum-likelihood from incomplete data via the EM algorithm,” J. Royal Stat. Soc., vol. 39, no. 1, pp. 1–38, 1977. [47] G. Casella and R. L. Berger, Statistical Inference. Pacific Grove, CA: Duxbury, 2001. [48] S. M. Kay, Fundamentals of Statistical Signal Processing: Estimation Theory. Upper Saddle River, NJ: Prentice Hall, 1993. [49] L. Ljung, System Identification: Theory for the User 2nd ed. Englewood Cliffs, NJ: Prentice-Hall, 1999. [50] Y. Wang, P. Stoica, and J. Li, “Two-dimensional nonparametric spectral analysis in the missing data case,” IEEE Trans. Aerosp. Electron. Syst., submitted for publication. [51] D. J. Andersh, M. Hazlett, S. W. Lee, D. D. Reeves, D. P. Sullivan, and Y. Chu, “XPATCH: A high-frequency electromagnetic scattering prediction

96

REFERENCES

code and environment for complex three-dimensional objects,” IEEE Antennas Propagat. Mag., vol. 36, no. 1, pp. 65–69, Feb. 1994. [52] Y. Wang, J. Li, and P. Stoica, “Rank-deficient robust Capon filter-bank approach to complex spectral estimation,” IEEE Trans. Signal Processing, to be published.

97

The Authors YANWEI WANG Yanwei Wang received the B.Sc. degree in electrical engineering from the Beijing University of Technology, China, in 1997 and the M.Sc. degree, again in electrical engineering from the University of Florida, Gainesville, in 2001. Since January 2000, he has been a research assistant with the Department of Electrical and Computer Engineering, University of Florida, where he received the Ph.D. degree in December 2004. Currently, he is with the R&D group of Diagnostic Ultrasound Corp. His research interests include spectral estimation, medical tomographic imaging, and radar/array signal processing.

JIAN LI Jian Li received the M.Sc. and Ph.D. degrees in electrical engineering from The Ohio State University, Columbus, in 1987 and 1991, respectively. From April 1991 to June 1991, she was an Adjunct Assistant Professor with the Department of Electrical Engineering, The Ohio State University, Columbus. From July 1991 to June 1993, she was an Assistant Professor with the Department of Electrical Engineering, University of Kentucky, Lexington. Since August 1993, she has been with the Department of Electrical and Computer Engineering, University of Florida, Gainesville, where she is currently a Professor. Her current research interests include spectral estimation, array signal processing, and their applications. Dr. Li is a member of Sigma Xi and Phi Kappa Phi. She received the 1994 National Science Foundation Young Investigator Award and the 1996 Office of Naval Research Young Investigator Award. She was an Executive Committee Member of the 2002 International Conference on Acoustics, Speech, and Signal Processing, Orlando, Florida, May 2002. She has been an Associate Editor of the

98

THE AUTHORS

IEEE Transactions on Signal Processing since 1999 and an Associate Editor of the IEEE Signal Processing Magazine since 2003. She is presently a member of the Signal Processing Theory and Methods (SPTM) Technical Committee of the IEEE Signal Processing Society.

PETRE STOICA Petre Stoica (F’94) received the D.Sc. degree in automatic control from the Polytechnic Institute of Bucharest (BPI), Bucharest, Romania, in 1979 and an honorary doctorate degree in science from Uppsala University (UU), Uppsala, Sweden, in 1993. He is Professor of system modeling with the Department of Systems and Control at UU. Previously, he was a Professor of system identification and signal processing with the Faculty of Automatic Control and Computers at BPI. He held longer visiting positions with Eindhoven University of Technology, Eindhoven, The Netherlands; Chalmers University of Technology, Gothenburg, Sweden (where he held a Jubilee Visiting Professorship); UU; The University of Florida, Gainesville; and Stanford University, Stanford, CA. His main scientific interests are in the areas of system identification, time series analysis and prediction, statistical signal and array processing, spectral analysis, wireless communications, and radar signal processing. He has published seven books, ten book chapters, and some 450 papers in archival journals and conference records on these topics. The most recent book he coauthored, with R. Moses, is entitled Introduction to Spectral Analysis (Englewood Cliffs, NJ: Prentice-Hall, 1997). He has also edited two books on signal processing advances in wireless communications and mobile communications, published by Prentice-Hall in 2001. He is on the editorial boards of five journals in the field: Journal of Forecasting; Signal Processing; Circuits, Signals, and Signal Processing; Digital Signal Processing—A Review Journal; and Multidimensional Systems and Signal Processing. He was a Co-Guest Editor for several special issues on system identification, signal processing, spectral analysis, and radar for some of the aforementioned journals, as well as for Proceeding of the IEEE.

THE AUTHORS

99

Dr. Stoica was a corecipient of the IEEE ASSP Senior Award for a paper on statistical aspects of array signal processing. He was also a recipient of the Technical Achievement Award of the IEEE Signal Processing Society for fundamental contributions to statistical signal processing with applications in time series analysis, system identification, and array signal processing. In 1998, he was the recipient of a Senior Individual Grant Award of the Swedish Foundation for Strategic Research. He was also a corecipient of the 1998 EURASIP Best Paper Award for Signal Processing for a work on parameter estimation of exponential signals with time-varying amplitude, a 1999 IEEE Signal Processing Society Best Paper Award for a paper on parameter and rank estimation of reduced-rank regression, a 2000 IEEE Third Millennium Medal, and the 2000 W. R. G. Baker Prize Paper Award for a paper on maximum likelihood methods for radar. He was a member of the international program committees of many topical conferences. From 1981 to 1986, he was the Director of the International Time Series Analysis and Forecasting Society, and he has been a member of the IFAC Technical Committee on Modeling, Identification, and Signal Processing since 1994. He is also a member of the Romanian Academy and a Fellow of the Royal Statistical Society.