,Contents
About the Author . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xxi
Preface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xxiii
Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xxv
Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xxvii
CHAPTER 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1 The Historical Context . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Artificial Intelligence and Machine Learning . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.3 Algorithms Can Learn What Is Hidden in the Data . . . . . . . . . . . . . . . . . . . . . . 4
1.4 Typical Applications of Machine Learning . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
Speech Recognition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
Computer Vision . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
Multimodal Data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
Natural Language Processing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
Robotics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
Autonomous Cars . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
Challenges for the Future . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.5 Machine Learning: Major Directions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.5.1 Supervised Learning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.6 Unsupervised and Semisupervised Learning . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.7 Structure and a Road Map of the Book . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
CHAPTER 2 Probability and Stochastic Processes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.2 Probability and Random Variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.2.1 Probability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.2.2 Discrete Random Variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.2.3 Continuous Random Variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.2.4 Mean and Variance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.2.5 Transformation of Random Variables . . . . . . . . . . . . . . . . . . . . . . . . . 28
2.3 Examples of Distributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
2.3.1 Discrete Variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
2.3.2 Continuous Variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
2.4 Stochastic Processes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
2.4.1 First- and Second-Order Statistics . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
2.4.2 Stationarity and Ergodicity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
2.4.3 Power Spectral Density . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
2.4.4 Autoregressive Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
2.5 Information Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
vii
,viii Contents
2.5.1 Discrete Random Variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
2.5.2 Continuous Random Variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
2.6 Stochastic Convergence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
Convergence Everywhere . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
Convergence Almost Everywhere . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
Convergence in the Mean-Square Sense . . . . . . . . . . . . . . . . . . . . . . . 62
Convergence in Probability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
Convergence in Distribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
CHAPTER 3 Learning in Parametric Modeling: Basic Concepts and Directions . . . . . . . . . 67
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
3.2 Parameter Estimation: the Deterministic Point of View . . . . . . . . . . . . . . . . . . . 68
3.3 Linear Regression . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
3.4 Classification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
Generative Versus Discriminative Learning . . . . . . . . . . . . . . . . . . . . 78
3.5 Biased Versus Unbiased Estimation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
3.5.1 Biased or Unbiased Estimation? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
3.6 The Cramér–Rao Lower Bound . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
3.7 Sufficient Statistic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
3.8 Regularization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
Inverse Problems: Ill-Conditioning and Overfitting . . . . . . . . . . . . . . . 91
3.9 The Bias–Variance Dilemma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
3.9.1 Mean-Square Error Estimation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
3.9.2 Bias–Variance Tradeoff . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
3.10 Maximum Likelihood Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
3.10.1 Linear Regression: the Nonwhite Gaussian Noise Case . . . . . . . . . . . . 101
3.11 Bayesian Inference . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102
3.11.1 The Maximum a Posteriori Probability Estimation Method . . . . . . . . . 107
3.12 Curse of Dimensionality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
3.13 Validation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
Cross-Validation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
3.14 Expected Loss and Empirical Risk Functions . . . . . . . . . . . . . . . . . . . . . . . . . . 112
Learnability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
3.15 Nonparametric Modeling and Estimation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114
Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114
MATLAB® Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
CHAPTER 4 Mean-Square Error Linear Estimation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
4.2 Mean-Square Error Linear Estimation: the Normal Equations . . . . . . . . . . . . . . 122
4.2.1 The Cost Function Surface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123
4.3 A Geometric Viewpoint: Orthogonality Condition . . . . . . . . . . . . . . . . . . . . . . 124
, Contents ix
4.4 Extension to Complex-Valued Variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127
4.4.1 Widely Linear Complex-Valued Estimation . . . . . . . . . . . . . . . . . . . . 129
4.4.2 Optimizing With Respect to Complex-Valued Variables:
Wirtinger Calculus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132
4.5 Linear Filtering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134
4.6 MSE Linear Filtering: a Frequency Domain Point of View . . . . . . . . . . . . . . . . 136
Deconvolution: Image Deblurring . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137
4.7 Some Typical Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140
4.7.1 Interference Cancelation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140
4.7.2 System Identification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141
4.7.3 Deconvolution: Channel Equalization . . . . . . . . . . . . . . . . . . . . . . . . . 143
4.8 Algorithmic Aspects: the Levinson and Lattice-Ladder Algorithms . . . . . . . . . 149
Forward and Backward MSE Optimal Predictors . . . . . . . . . . . . . . . . 151
4.8.1 The Lattice-Ladder Scheme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154
4.9 Mean-Square Error Estimation of Linear Models . . . . . . . . . . . . . . . . . . . . . . . 158
4.9.1 The Gauss–Markov Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160
4.9.2 Constrained Linear Estimation: the Beamforming Case . . . . . . . . . . . 162
4.10 Time-Varying Statistics: Kalman Filtering . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166
Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172
MATLAB® Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 176
CHAPTER 5 Online Learning: the Stochastic Gradient Descent Family of Algorithms . . . . . 179
5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 180
5.2 The Steepest Descent Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181
5.3 Application to the Mean-Square Error Cost Function . . . . . . . . . . . . . . . . . . . . 184
Time-Varying Step Sizes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 190
5.3.1 The Complex-Valued Case . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193
5.4 Stochastic Approximation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 194
Application to the MSE Linear Estimation . . . . . . . . . . . . . . . . . . . . . 196
5.5 The Least-Mean-Squares Adaptive Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . 198
5.5.1 Convergence and Steady-State Performance of the LMS in Stationary
Environments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 199
5.5.2 Cumulative Loss Bounds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 204
5.6 The Affine Projection Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 206
Geometric Interpretation of APA . . . . . . . . . . . . . . . . . . . . . . . . . . . . 208
Orthogonal Projections . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 208
5.6.1 The Normalized LMS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 211
5.7 The Complex-Valued Case . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 213
The Widely Linear LMS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 213
The Widely Linear APA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 214
5.8 Relatives of the LMS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 214
The Sign-Error LMS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 214
The Least-Mean-Fourth (LMF) Algorithm . . . . . . . . . . . . . . . . . . . . . 215
Transform-Domain LMS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 215
About the Author . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xxi
Preface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xxiii
Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xxv
Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xxvii
CHAPTER 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1 The Historical Context . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Artificial Intelligence and Machine Learning . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.3 Algorithms Can Learn What Is Hidden in the Data . . . . . . . . . . . . . . . . . . . . . . 4
1.4 Typical Applications of Machine Learning . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
Speech Recognition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
Computer Vision . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
Multimodal Data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
Natural Language Processing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
Robotics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
Autonomous Cars . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
Challenges for the Future . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.5 Machine Learning: Major Directions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.5.1 Supervised Learning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.6 Unsupervised and Semisupervised Learning . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.7 Structure and a Road Map of the Book . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
CHAPTER 2 Probability and Stochastic Processes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.2 Probability and Random Variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.2.1 Probability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.2.2 Discrete Random Variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.2.3 Continuous Random Variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.2.4 Mean and Variance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.2.5 Transformation of Random Variables . . . . . . . . . . . . . . . . . . . . . . . . . 28
2.3 Examples of Distributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
2.3.1 Discrete Variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
2.3.2 Continuous Variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
2.4 Stochastic Processes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
2.4.1 First- and Second-Order Statistics . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
2.4.2 Stationarity and Ergodicity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
2.4.3 Power Spectral Density . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
2.4.4 Autoregressive Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
2.5 Information Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
vii
,viii Contents
2.5.1 Discrete Random Variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
2.5.2 Continuous Random Variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
2.6 Stochastic Convergence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
Convergence Everywhere . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
Convergence Almost Everywhere . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
Convergence in the Mean-Square Sense . . . . . . . . . . . . . . . . . . . . . . . 62
Convergence in Probability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
Convergence in Distribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
CHAPTER 3 Learning in Parametric Modeling: Basic Concepts and Directions . . . . . . . . . 67
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
3.2 Parameter Estimation: the Deterministic Point of View . . . . . . . . . . . . . . . . . . . 68
3.3 Linear Regression . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
3.4 Classification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
Generative Versus Discriminative Learning . . . . . . . . . . . . . . . . . . . . 78
3.5 Biased Versus Unbiased Estimation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
3.5.1 Biased or Unbiased Estimation? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
3.6 The Cramér–Rao Lower Bound . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
3.7 Sufficient Statistic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
3.8 Regularization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
Inverse Problems: Ill-Conditioning and Overfitting . . . . . . . . . . . . . . . 91
3.9 The Bias–Variance Dilemma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
3.9.1 Mean-Square Error Estimation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
3.9.2 Bias–Variance Tradeoff . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
3.10 Maximum Likelihood Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
3.10.1 Linear Regression: the Nonwhite Gaussian Noise Case . . . . . . . . . . . . 101
3.11 Bayesian Inference . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102
3.11.1 The Maximum a Posteriori Probability Estimation Method . . . . . . . . . 107
3.12 Curse of Dimensionality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
3.13 Validation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
Cross-Validation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
3.14 Expected Loss and Empirical Risk Functions . . . . . . . . . . . . . . . . . . . . . . . . . . 112
Learnability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
3.15 Nonparametric Modeling and Estimation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114
Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114
MATLAB® Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
CHAPTER 4 Mean-Square Error Linear Estimation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
4.2 Mean-Square Error Linear Estimation: the Normal Equations . . . . . . . . . . . . . . 122
4.2.1 The Cost Function Surface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123
4.3 A Geometric Viewpoint: Orthogonality Condition . . . . . . . . . . . . . . . . . . . . . . 124
, Contents ix
4.4 Extension to Complex-Valued Variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127
4.4.1 Widely Linear Complex-Valued Estimation . . . . . . . . . . . . . . . . . . . . 129
4.4.2 Optimizing With Respect to Complex-Valued Variables:
Wirtinger Calculus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132
4.5 Linear Filtering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134
4.6 MSE Linear Filtering: a Frequency Domain Point of View . . . . . . . . . . . . . . . . 136
Deconvolution: Image Deblurring . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137
4.7 Some Typical Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140
4.7.1 Interference Cancelation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140
4.7.2 System Identification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141
4.7.3 Deconvolution: Channel Equalization . . . . . . . . . . . . . . . . . . . . . . . . . 143
4.8 Algorithmic Aspects: the Levinson and Lattice-Ladder Algorithms . . . . . . . . . 149
Forward and Backward MSE Optimal Predictors . . . . . . . . . . . . . . . . 151
4.8.1 The Lattice-Ladder Scheme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154
4.9 Mean-Square Error Estimation of Linear Models . . . . . . . . . . . . . . . . . . . . . . . 158
4.9.1 The Gauss–Markov Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160
4.9.2 Constrained Linear Estimation: the Beamforming Case . . . . . . . . . . . 162
4.10 Time-Varying Statistics: Kalman Filtering . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166
Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172
MATLAB® Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 176
CHAPTER 5 Online Learning: the Stochastic Gradient Descent Family of Algorithms . . . . . 179
5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 180
5.2 The Steepest Descent Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181
5.3 Application to the Mean-Square Error Cost Function . . . . . . . . . . . . . . . . . . . . 184
Time-Varying Step Sizes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 190
5.3.1 The Complex-Valued Case . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193
5.4 Stochastic Approximation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 194
Application to the MSE Linear Estimation . . . . . . . . . . . . . . . . . . . . . 196
5.5 The Least-Mean-Squares Adaptive Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . 198
5.5.1 Convergence and Steady-State Performance of the LMS in Stationary
Environments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 199
5.5.2 Cumulative Loss Bounds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 204
5.6 The Affine Projection Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 206
Geometric Interpretation of APA . . . . . . . . . . . . . . . . . . . . . . . . . . . . 208
Orthogonal Projections . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 208
5.6.1 The Normalized LMS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 211
5.7 The Complex-Valued Case . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 213
The Widely Linear LMS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 213
The Widely Linear APA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 214
5.8 Relatives of the LMS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 214
The Sign-Error LMS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 214
The Least-Mean-Fourth (LMF) Algorithm . . . . . . . . . . . . . . . . . . . . . 215
Transform-Domain LMS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 215
