Contents
1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1 Digital signal processing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Multirate signal processing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2.1 Decimation by an integer factor M. . . . . . . . . . . . . . . . . . . 3
1.2.2 Interpolation by an integer factor L . . . . . . . . . . . . . . . . . . 4
1.3 Applications of multirate signal processing . . . . . . . . . . . . . . . . . . 5
1.3.1 Scalable representation of multimedia signals . . . . . . . . . 5
1.3.2 Subband coding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.3.3 Distributed measurement and sensor networks . . . . . . . . 8
1.4 Multirate statistical signal processing . . . . . . . . . . . . . . . . . . . . . . 13
1.5 Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.1 Inverse and ill-posed problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.1.1 Ill-posed linear operator equations . . . . . . . . . . . . . . . . . . . 18
2.1.2 Regularization of ill-posed operator equations . . . . . . . . . 19
2.2 Measuring inequality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.2.1 Definition of majorization . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.2.2 Geometrical properties of majorization . . . . . . . . . . . . . . . 24
2.2.3 Algebraic properties of majorization . . . . . . . . . . . . . . . . . 24
2.2.4 Schur-convex functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.3 Measuring information . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.3.1 Entropy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
2.3.2 Kullback-Leibler divergence . . . . . . . . . . . . . . . . . . . . . . . . . 29
2.4 Statistical inference . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
2.4.1 The Maximum Likelihood principle . . . . . . . . . . . . . . . . . . 32
2.4.2 The Maximum Entropy principle . . . . . . . . . . . . . . . . . . . . 32
2.4.3 Probability density estimation . . . . . . . . . . . . . . . . . . . . . . 36
2.4.4 Reliability of statistical inference principles . . . . . . . . . . . 37
2.5 Stochastic processes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
2.5.1 Stationary stochastic processes . . . . . . . . . . . . . . . . . . . . . . 38
2.5.2 The power spectrum . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
2.5.3 Processes with rational power spectra . . . . . . . . . . . . . . . . 41
2.5.4 Information rate of stochastic processes . . . . . . . . . . . . . . 43
3 Multirate Spectrum Estimation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
3.2 Mathematical modelling of the problem . . . . . . . . . . . . . . . . . . . . 45
3.3 The Maximum Entropy principle . . . . . . . . . . . . . . . . . . . . . . . . . . 48
3.4 A geometric interpretation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
3.5 Properties of the Maximum Entropy solution . . . . . . . . . . . . . . . 52
3.5.1 Uniqueness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
3.5.2 Existence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
3.5.3 Stability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
3.6 Computing the Maximum Entropy solution . . . . . . . . . . . . . . . . . 54
3.7 Simulated examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
3.8 Complements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
3.8.1 Does the estimate converge to the actual spectrum? . . . 62
3.8.2 Why is the cross-correlation information not used? . . . . 64
3.9 Open problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
4 Multirate Signal Estimation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
4.2 Stochastic least-square estimation . . . . . . . . . . . . . . . . . . . . . . . . . 68
4.2.1 Problem formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
4.2.2 Solution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
4.3 More on linear least-squares estimation . . . . . . . . . . . . . . . . . . . . . 70
4.4 Computing the estimator matrix . . . . . . . . . . . . . . . . . . . . . . . . . . 70
4.5 Simulated examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
4.6 Multirate least-squares estimation in practice . . . . . . . . . . . . . . . 77
4.7 Open problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
5 Multirate Time-Delay Estimation . . . . . . . . . . . . . . . . . . . . . . . . . . 85
5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
5.2 Time-delay estimation techniques . . . . . . . . . . . . . . . . . . . . . . . . . . 85
5.3 Time-delay estimation in multirate systems . . . . . . . . . . . . . . . . . 86
5.4 Multirate sensors that allow time-delay estimation . . . . . . . . . . . 90
5.4.1 Sensors based on linear-phase FIR filters . . . . . . . . . . . . . 90
5.4.2 Sensors based on Bessel IIR filters . . . . . . . . . . . . . . . . . . . 90
5.4.3 Sensors based on perfect-reconstruction filter banks . . . . 91
5.5 Laboratory experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
5.6 Multirate sensor fusion in the presence of time-delay . . . . . . . . . 99
5.6.1 Perfect reconstruction for arbitrary time-delays . . . . . . . 99
5.6.2 A practical design method using H∞ optimization . . . . . 102
5.6.3 Example designs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
5.7 Open problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
6 Optimal Multirate Decomposition of Signals . . . . . . . . . . . . . . . 107
6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
6.2 Review of FIR filter banks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110
6.2.1 Some basic notions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110
6.2.2 Orthogonal FIR filter banks (the class L) . . . . . . . . . . . . . 110
6.3 Scalability in the class L . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112
6.3.1 Ordering the filter banks in L based on their scalability 112
6.3.2 Scalability in terms of power distribution . . . . . . . . . . . . . 114
6.4 Embedding the ordering of scalability in a total ordering . . . . . 118
6.4.1 SCφ-optimality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118
6.4.2 An illustrative design example . . . . . . . . . . . . . . . . . . . . . . 121
6.5 SC-Optimality vs PCFB. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123
6.5.1 A constructive definition of the PCFB . . . . . . . . . . . . . . . 123
6.5.2 PCFB is an upper bound for L. . . . . . . . . . . . . . . . . . . . . . 125
6.5.3 Historical notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125
6.5.4 Approximating PCFB using the filter banks in L . . . . . . 126
6.6 SC-Optimality vs Subband Coding optimality . . . . . . . . . . . . . . . 127
6.7 Complements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129
6.7.1 Algorithmic aspects of finding an SCφ-optimal
element in L and previous works . . . . . . . . . . . . . . . . . . . . 130
6.7.2 Similarity with rate-distortion theory . . . . . . . . . . . . . . . . 131
6.7.3 On partial ordering and subjectivity . . . . . . . . . . . . . . . . . 132
6.8 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132
6.9 Open problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133
6.9.1 Extension to non-perfect-reconstruction filter banks . . . . 133
6.9.2 Extension to tree-structured filter banks . . . . . . . . . . . . . . 133
6.9.3 Scalability with respect to other error measures . . . . . . . 134
6.9.4 Scalability when an optimal synthesis system is used . . . 134
7 Information in Multirate Systems. . . . . . . . . . . . . . . . . . . . . . . . . . 135
7.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135
7.2 Information as distance from uniform spectrum . . . . . . . . . . . . . 136
7.3 An illustrative example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139
7.4 Redundancy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145
7.5 Scalability in terms of information . . . . . . . . . . . . . . . . . . . . . . . . . 146
7.6 Open problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147
7.6.1 Cross-correlation data are ignored . . . . . . . . . . . . . . . . . . . 147
7.6.2 Information rate of the low-rate signals . . . . . . . . . . . . . . . 148
7.6.3 INF-optimality, SC-optimality and PCFB . . . . . . . . . . . . 148
8 Distributed Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149
8.1 The need for distributed algorithms . . . . . . . . . . . . . . . . . . . . . . . . 149
8.2 Spectrum estimation as a convex feasibility problem . . . . . . . . . 150
8.3 Solution using generalized projections . . . . . . . . . . . . . . . . . . . . . . 153
8.4 Distributed algorithms based on local generalized projections . 155
Contents
8.4.1 The Ring Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156
8.4.2 The Star Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157
8.5 Open problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161
9 Epilogue . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165