Adaptive signal processing : next generation solutions

ADAPTIVE SIGNAL

PROCESSING

Adaptive and Learning Systems for Signal Processing,

Communications, and Control

Editor: Simon Haykin

Adali and Haykin / ADAPTIVE SIGNAL PROCESSING: Next Generation Solutions

Beckerman / ADAPTIVE COOPERATIVE SYSTEMS

Candy / BAYESIAN SIGNAL PROCESSING: CLASSICAL, MODERN, AND PARTICLE FILTERING

METHODS

Candy / MODEL-BASED SIGNAL PROCESSING

Chen and Gu / CONTROL-ORIENTED SYSTEM IDENTIFICATION: An H1 Approach

Chen, Haykin, Eggermont, and Becker / CORRELATIVE LEARNING: A Basis for Brain and

Adaptive Systems

Cherkassky and Mulier / LEARNING FROM DATA: Concepts, Theory, and Methods

Costa and Haykin / MULTIPLE-INPUT MULTIPLE-OUTPUT CHANNEL MODELS: Theory and

Practice

Diamantaras and Kung / PRINCIPAL COMPONENT NEURAL NETWORKS: Theory and

Applications

Farrell and Polycarpou / ADAPTIVE APPROXIMATION BASED CONTROL: Unifying Neural,

Fuzzy and Traditional Adaptive Approximation Approaches

Gini and Rangaswamy / KNOWLEDGE-BASED RADAR DETECTION: Tracking and

Classification

Ha¨ nsler and Schmidt / ACOUSTIC ECHO AND NOISE CONTROL: A Practical Approach

Haykin / UNSUPERVISED ADAPTIVE FILTERING: Blind Source Separation

Haykin / UNSUPERVISED ADAPTIVE FILTERING: Blind Deconvolution

Haykin and Puthussarypady / CHAOTIC DYNAMICS OF SEA CLUTTER

Haykin and Widrow / LEAST-MEAN-SQUARE ADAPTIVE FILTERS

Hrycej / NEUROCONTROL: Towards an Industrial Control Methodology

Hyva¨ rinen, Karhunen, and Oja / INDEPENDENT COMPONENT ANALYSIS

Kristic´, Kanellakopoulos, and Kokotovic´ / NONLINEAR AND ADAPTIVE CONTROL DESIGN

Mann / INTELLIGENT IMAGE PROCESSING

Nikias and Shao / SIGNAL PROCESSING WITH ALPHA-STABLE DISTRIBUTIONS AND

APPLICATIONS

Passino and Burgess / STABILITY ANALYSIS OF DISCRETE EVENT SYSTEMS

Sa´ nchez-Pen˜a and Sznaier / ROBUST SYSTEMS THEORY AND APPLICATIONS

Sandberg, Lo, Fancourt, Principe, Katagiri, and Haykin / NONLINEAR DYNAMICAL

SYSTEMS: Feedforward Neural Network Perspectives

Sellathurai and Haykin / SPACE-TIME LAYERED INFORMATION PROCESSING FOR WIRELESS

COMMUNICATIONS

Spooner, Maggiore, Ordo´n˜ez, and Passino / STABLE ADAPTIVE CONTROL AND ESTIMATION

FOR NONLINEAR SYSTEMS: Neural and Fuzzy Approximator Techniques

Tao / ADAPTIVE CONTROL DESIGN AND ANALYSIS

Tao and Kokotovic´ / ADAPTIVE CONTROL OF SYSTEMS WITH ACTUATOR AND SENSOR

NONLINEARITIES

Tsoukalas and Uhrig / FUZZY AND NEURAL APPROACHES IN ENGINEERING

Van Hulle / FAITHFUL REPRESENTATIONS AND TOPOGRAPHIC MAPS: From Distortion- to

Information-Based Self-Organization

Vapnik / STATISTICAL LEARNING THEORY

Werbos / THE ROOTS OF BACKPROPAGATION: From Ordered Derivatives to Neural

Networks and Political Forecasting

Yee and Haykin / REGULARIZED RADIAL BIAS FUNCTION NETWORKS: Theory and

Applications

ADAPTIVE SIGNAL

PROCESSING

Next Generation Solutions

Tu¨lay Adalı

Simon Haykin

Edited by

Wiley Series in Adaptive and Learning Systems for

Signal Processing, Communication, and Control

Copyright # 2010 by John Wiley & Sons, Inc. All rights reserved

Published by John Wiley & Sons, Inc., Hoboken, New Jersey

Published simultaneously in Canada

Cover photo: Humuhumunukunukua¯pua’a, Hawaiian state fish.

Photo taken April 2007 in Honolulu, Hawaii during ICASSP 2007 where the idea for the book

was first conceived. Photo copyright # 2010 by Tu¨lay Adalı.

No part of this publication may be reproduced, stored in a retrieval system, or transmitted in any form or

by any means, electronic, mechanical, photocopying, recording, scanning, or otherwise, except as permitted

under Section 107 or 108 of the 1976 United States Copyright Act, without either the prior written

permission of the Publisher, or authorization through payment of the appropriate per-copy fee to the

Copyright Clearance Center, Inc., 222 Rosewood Drive, Danvers, MA 01923, (978) 750-8400, fax (978)

750-4470, or on the web at www.copyright.com. Requests to the Publisher for permission should be

addressed to the Permissions Department, John Wiley & Sons, Inc., 111 River Street, Hoboken, NJ 07030,

Limit of Liability/Disclaimer of Warranty: While the publisher and author have used their best efforts in

preparing this book, they make no representations or warranties with respect to the accuracy or completeness

of the contents of this book and specifically disclaim any implied warranties of merchantability or fitness for

a particular purpose. No warranty may be created or extended by sales representatives or written sales

materials. The advice and strategies contained herein may not be suitable for your situation. You should

consult with a professional where appropriate. Neither the publisher nor author shall be liable for any loss of

profit or any other commercial damages, including but not limited to special, incidental, consequential, or

other damages.

For general information on our other products and services or for technical support, please contact our

Customer Care Department within the United States at (800) 762-2974, outside the United States at

(317) 572-3993 or fax (317) 572-4002.

Wiley also publishes its books in a variety of electronic formats. Some content that appears in print may

not be available in electronic formats. For more information about Wiley products, visit our web site at

Library of Congress Cataloging-in-Publication Data:

Adaptive signal processing : next generation solutions / [edited by] Tu¨lay Adalı, Simon Haykin.

p. cm.

Includes bibliographical references.

ISBN 978-0-470-19517-8 (cloth)

1. Adaptive signal processing. I. Adalı, Tu¨lay II. Haykin, Simon, 1931–

TK5102.9.A288 2010

621.3820

2—dc22 2009031378

Printed in the United States of America

10 9 8 7 6 5 4 3 2 1

(201) 748-6011, fax (201) 748-6008, or online at http://www.wiley.com/go/permission.

www.wiley.com.

CONTENTS

Preface xi

Contributors xv

Chapter 1 Complex-Valued Adaptive Signal Processing 1

1.1 Introduction / 1

1.1.1 Why Complex-Valued Signal Processing / 3

1.1.2 Outline of the Chapter / 5

1.2 Preliminaries / 6

1.2.1 Notation / 6

1.2.2 Efficient Computation of Derivatives in the Complex Domain / 9

1.2.3 Complex-to-Real and Complex-to-Complex Mappings / 17

1.2.4 Series Expansions / 20

1.2.5 Statistics of Complex-Valued Random Variables and

Random Processes / 24

1.3 Optimization in the Complex Domain / 31

1.3.1 Basic Optimization Approaches in RN / 31

1.3.2 Vector Optimization in CN / 34

1.3.3 Matrix Optimization in CN / 37

1.3.4 Newton-Variant Updates / 38

1.4 Widely Linear Adaptive Filtering / 40

1.4.1 Linear and Widely Linear Mean-Square Error Filter / 41

1.5 Nonlinear Adaptive Filtering with Multilayer Perceptrons / 47

1.5.1 Choice of Activation Function for the MLP Filter / 48

1.5.2 Derivation of Back-Propagation Updates / 55

1.6 Complex Independent Component Analysis / 58

1.6.1 Complex Maximum Likelihood / 59

1.6.2 Complex Maximization of Non-Gaussianity / 64

1.6.3 Mutual Information Minimization: Connections to ML and MN / 66

1.6.4 Density Matching / 67

1.6.5 Numerical Examples / 71

1.7 Summary / 74

v

1.8 Acknowledgment / 76

1.9 Problems / 76

References / 79

Chapter 2 Robust Estimation Techniques for Complex-Valued

Random Vectors 87

2.1 Introduction / 87

2.1.1 Signal Model / 88

2.1.2 Outline of the Chapter / 90

2.2 Statistical Characterization of Complex Random Vectors / 91

2.2.1 Complex Random Variables / 91

2.2.2 Complex Random Vectors / 93

2.3 Complex Elliptically Symmetric (CES) Distributions / 95

2.3.1 Definition / 96

2.3.2 Circular Case / 98

2.3.3 Testing the Circularity Assumption / 99

2.4 Tools to Compare Estimators / 102

2.4.1 Robustness and Influence Function / 102

2.4.2 Asymptotic Performance of an Estimator / 106

2.5 Scatter and Pseudo-Scatter Matrices / 107

2.5.1 Background and Motivation / 107

2.5.2 Definition / 108

2.5.3 M-Estimators of Scatter / 110

2.6 Array Processing Examples / 114

2.6.1 Beamformers / 114

2.6.2 Subspace Methods / 115

2.6.3 Estimating the Number of Sources / 118

2.6.4 Subspace DOA Estimation for Noncircular Sources / 120

2.7 MVDR Beamformers Based on M-Estimators / 121

2.7.1 The Influence Function Study / 123

2.8 Robust ICA / 128

2.8.1 The Class of DOGMA Estimators / 129

2.8.2 The Class of GUT Estimators / 132

2.8.3 Communications Example / 134

2.9 Conclusion / 137

2.10 Problems / 137

References / 138

Chapter 3 Turbo Equalization 143

3.1 Introduction / 143

3.2 Context / 144

vi CONTENTS

3.3 Communication Chain / 145

3.4 Turbo Decoder: Overview / 147

3.4.1 Basic Properties of Iterative Decoding / 151

3.5 Forward-Backward Algorithm / 152

3.5.1 With Intersymbol Interference / 160

3.6 Simplified Algorithm: Interference Canceler / 163

3.7 Capacity Analysis / 168

3.8 Blind Turbo Equalization / 173

3.8.1 Differential Encoding / 179

3.9 Convergence / 182

3.9.1 Bit Error Probability / 187

3.9.2 Other Encoder Variants / 190

3.9.3 EXIT Chart for Interference Canceler / 192

3.9.4 Related Analyses / 194

3.10 Multichannel and Multiuser Settings / 195

3.10.1 Forward-Backward Equalizer196

3.10.2 Interference Canceler197

3.10.3 Multiuser Case198

3.11 Concluding Remarks / 199

3.12 Problems / 200

References / 206

Chapter 4 Subspace Tracking for Signal Processing 211

4.1 Introduction / 211

4.2 Linear Algebra Review / 213

4.2.1 Eigenvalue Value Decomposition / 213

4.2.2 QR Factorization / 214

4.2.3 Variational Characterization of Eigenvalues/Eigenvectors

of Real Symmetric Matrices / 215

4.2.4 Standard Subspace Iterative Computational Techniques / 216

4.2.5 Characterization of the Principal Subspace of a Covariance

Matrix from the Minimization of a Mean Square Error / 218

4.3 Observation Model and Problem Statement / 219

4.3.1 Observation Model / 219

4.3.2 Statement of the Problem / 220

4.4 Preliminary Example: Oja’s Neuron / 221

4.5 Subspace Tracking / 223

4.5.1 Subspace Power-Based Methods / 224

4.5.2 Projection Approximation-Based Methods / 230

4.5.3 Additional Methodologies / 232

4.6 Eigenvectors Tracking / 233

4.6.1 Rayleigh Quotient-Based Methods / 234

CONTENTS vii

4.6.2 Eigenvector Power-Based Methods / 235

4.6.3 Projection Approximation-Based Methods / 240

4.6.4 Additional Methodologies / 240

4.6.5 Particular Case of Second-Order Stationary Data / 242

4.7 Convergence and Performance Analysis Issues / 243

4.7.1 A Short Review of the ODE Method / 244

4.7.2 A Short Review of a General Gaussian Approximation

Result / 246

4.7.3 Examples of Convergence and Performance Analysis / 248

4.8 Illustrative Examples / 256

4.8.1 Direction of Arrival Tracking / 257

4.8.2 Blind Channel Estimation and Equalization / 258

4.9 Concluding Remarks / 260

4.10 Problems / 260

References / 266

Chapter 5 Particle Filtering 271

5.1 Introduction / 272

5.2 Motivation for Use of Particle Filtering / 274

5.3 The Basic Idea / 278

5.4 The Choice of Proposal Distribution and Resampling / 289

5.4.1 Choice of Proposal Distribution / 290

5.4.2 Resampling / 291

5.5 Some Particle Filtering Methods / 295

5.5.1 SIR Particle Filtering / 295

5.5.2 Auxiliary Particle Filtering / 297

5.5.3 Gaussian Particle Filtering / 301

5.5.4 Comparison of the Methods / 302

5.6 Handling Constant Parameters / 305

5.6.1 Kernel-Based Auxiliary Particle Filter / 306

5.6.2 Density-Assisted Particle Filter / 308

5.7 Rao–Blackwellization / 310

5.8 Prediction / 314

5.9 Smoothing / 316

5.10 Convergence Issues / 320

5.11 Computational Issues and Hardware Implementation / 323

5.12 Acknowledgments / 324

5.13 Exercises / 325

References / 327

viii CONTENTS

Chapter 6 Nonlinear Sequential State Estimation for Solving

Pattern-Classification Problems 333

6.1 Introduction / 333

6.2 Back-Propagation and Support Vector Machine-Learning

Algorithms: Review / 334

6.2.1 Back-Propagation Learning / 334

6.2.2 Support Vector Machine / 337

6.3 Supervised Training Framework of MLPs Using Nonlinear Sequential

State Estimation / 340

6.4 The Extended Kalman Filter / 341

6.4.1 The EKF Algorithm / 344

6.5 Experimental Comparison of the Extended Kalman Filtering Algorithm

with the Back-Propagation and Support Vector Machine

Learning Algorithms / 344

6.6 Concluding Remarks / 347

6.7 Problems / 348

References / 348

Chapter 7 Bandwidth Extension of Telephony Speech 349

7.1 Introduction / 349

7.2 Organization of the Chapter / 352

7.3 Nonmodel-Based Algorithms for Bandwidth Extension / 352

7.3.1 Oversampling with Imaging / 353

7.3.2 Application of Nonlinear Characteristics / 353

7.4 Basics / 354

7.4.1 Source-Filter Model / 355

7.4.2 Parametric Representations of the Spectral Envelope / 358

7.4.3 Distance Measures / 362

7.5 Model-Based Algorithms for Bandwidth Extension / 364

7.5.1 Generation of the Excitation Signal / 365

7.5.2 Vocal Tract Transfer Function Estimation / 369

7.6 Evaluation of Bandwidth Extension Algorithms / 383

7.6.1 Objective Distance Measures / 383

7.6.2 Subjective Distance Measures / 385

7.7 Conclusion / 388

7.8 Problems / 388

References / 390

Index 393

CONTENTS ix

PREFACE

WHY THIS NEW BOOK?

Adaptive filters play a very important role in most of today’s signal processing and

control applications as most real-world signals require processing under conditions

that are difficult to specify a priori. They have been successfully applied in such

diverse fields as communications, control, radar, and biomedical engineering,

among others. The field of classical adaptive filtering is now well established and a

number of key references—a widely used one being the book Adaptive Filter

Theory by Simon Haykin—provide a comprehensive treatment of the theory and

applications of adaptive filtering.

A number of recent developments in the field, however, have demonstrated how

significant performance gains could be achieved beyond those obtained using the

standard adaptive filtering approaches. To this end, those recent developments have

propelled us to think in terms of a new generation of adaptive signal processing

algorithms.

As data now come in a multitude of forms originating from different applications

and environments, we now have to account for the characteristics of real life data:

† Non-Gaussianity;

† Noncircularity;

† Nonstationarity; and

† Nonlinearity.

Such data would typically exhibit a rich underlying structure and demand the

development of new tools, hence, the writing of this new book.

ORGANIZATION OF THE BOOK

The book consists of seven chapters that are organized in five subsections as follows.

xi

Fundamental Issues: Optimization, Efficiency, and Robustness in

the Complex Domain

Chapter 1 by Adalı and Li and Chapter 2 by Ollilla and Koivunen constitute the first

subsection of the book.

The first chapter of the book addresses the key problem of optimization in the

complex domain, and fully develops a framework that enables taking full advantage

of the power of complex-valued processing. The fundamental relationships for the

derivation and analysis of adaptive algorithms in the complex domain are established

based on Wirtinger calculus, and their successful application is demonstrated for two

basic problems in adaptive signal processing: filtering and independent component

analysis (ICA). Two important classes of filters, namely, the widely linear and non￾linear filters are studied as well as the two main approaches for performing ICA, maxi￾mum likelihood and maximization of non-Gaussianity. In the design of these

solutions, the emphasis is placed on taking the full statistical information into account

as well as the choice of nonlinear functions for the efficient use of information. It is

shown that the framework based on Wirtinger calculus naturally addresses both of

these considerations, and besides significantly simplifying the derivations and ana￾lyses, also eliminates the need for many restrictive assumptions such as circularity

of signals and extends the power of many convenient tools in analysis introduced

for the real-valued case to complex-valued signal processing.

The second chapter in this subsection addresses the problem of multichannel

processing of complex-valued signals in cases where the underlying ideal assumptions

on signal and noise models are not necessarily true or there are observations that highly

deviate from the mean. Specifically, estimation techniques, which are robust both

to deviations from the commonly invoked circularity and/or Gaussianity assumption

and to outliers, are developed and analyzed. The methods are based on matrix-valued

statistics such as M-estimators of scatter and pseudo-scatter matrices. The robustness

and statistical efficiency of the methods are illustrated in several applications such as

beamforming, direction-of-arrival estimation, separation of sources, detection of

circularity or the number of sources. Both numerical simulations as well as analytical

results are provided, employing the widely used concepts of influence function and

asymptotic efficiency.

Turbo Signal Processing for Equalization

This section consists of Chapter 3 written by Regalia.

Turbo processing aims to combine receiver components via information exchange

for performance enhancements, as a means of joint optimization. This chapter reviews

the basic principles of turbo equalization, in which the traditionally separate tech￾niques of channel equalization and error correction decoding are combined in an itera￾tive loop. Various schemes are treated, including maximum a posterior channel

estimation, decision feedback channel equalizers, blind turbo algorithms in which

the channel coefficients are estimated as part of the iterative procedure, and three￾level turbo schemes using differential encoding. Numerous examples are included

xii PREFACE

to clarify the operation and performance features of the various constituent elements,

and convergence tools and extensions to multi-user channels are outlined as well.

Tracking in the Subspace Domain

The third section of the book consists of Chapter 4 by Delmas.

Research in subspace and component-based techniques originated in statistics in

the middle of the last century through the problem of linear feature extraction

solved by the Karhunen–Loe¨ve transform. It has been applied to signal processing

about three decades ago and the importance of using the subspace and component￾based methodology has been demonstrated by many examples in data compression,

data filtering, parameter estimation, and pattern recognition. The main reason for

the interest in subspace and component-based methods stems from the fact that they

consist in splitting the observations into a set of desired and interfering components,

and as such, they not only provide new insight into many problems, but also offer

a good tradeoff between achieved performance and computational complexity.

Over the past few years, new potential applications have emerged, and subspace

and component methods have been adopted in new diverse areas such as smart anten￾nas, sensor arrays, multiuser detection, speech enhancement, and radar systems to

name but a few. These new applications have also underlined the importance of the

development of adaptive procedures as well as ways to handle nonstationarity. In

this chapter on tracking in the subspace domain, the emphasis is on the class of

low-complexity decompositions for dominant and minor subspaces, and dominant

and minor eigenvector tracking, while other important more classical schemes are

also discussed. The algorithms are derived using different iterative procedures

based on linear algebraic methods, and it is shown that the majority of these algorithms

can be viewed as heuristic variations of the power method.

Nonlinear Sequential State Estimation

This subsection of the book consists of Chapter 5 by Djuric and Bugallo and Chapter 6

by Haykin and Arasaratnam.

Particle filtering belongs to a more recent generation of sequential processing

methods, where the objectives are not simply the tracking of unknown states from

noisy observations but also the estimation of the complete posterior distributions of

the states. This is achieved by clever approximations of the posterior distributions

with discrete random measures. Chapter 5 presents the essentials of particle filtering,

provides details about the implementation of various types of particle filters, and

demonstrates their use through various examples. It also provides some more

advanced concepts including Rao –Blackwellization, smoothing, and discussion on

convergence and computational issues.

The second chapter in this section addresses a novel application of the extended

Kalman filter (EKF) for the training of a neural network (e.g., multilayer perceptron)

to solve difficult pattern recognition problems. To be specific, the training process is

viewed as a nonlinear sequential estimation problem, for which the EKF is well suited.

PREFACE xiii