Partial-Update Adaptive Signal Processing,

TABLE OF CONTENTS 1. Introduction 1.1 Adaptive Signal Processing 1.2 Examples of Adaptive Filtering 1.2.1 Adaptive System Identification 1.2.2 Adaptive Inverse System Identification 1.3 Raison D'etre for Partial Coefficient Updates 1.3.1 Resource Constraints 1.3.2 Convergence Performance 1.3.3 System Identification with White Input Signal 1.3.4 System Identification with Correlated Input Signal2. Approaches to Partial Coefficient Updates 2.1 Introduction 2.2 Periodic Partial Updates 2.2.1 Example 1: Convergence Performance 2.2.2 Example 2: Convergence Difficulties 2.3 Sequential Partial Updates 2.3.1 Example 1: Convergence Performance 2.3.2 Example 2: Cyclostationary Inputs 2.3.3 Example 3: Instability 2.4 Stochastic Partial Updates 2.4.1 System Identification Example 2.5 M-Max Updates 2.5.1 Example 1: Eigenvalue Spread of R_M 2.5.2 Example 2: Convergence Performance 2.5.3 Example 3: Convergence Rate and Eigenvalues of R_M 2.5.4 Example 4: Convergence Difficulties 2.5.5 Example 5: Instability 2.6 Selective Partial Updates 2.6.1 Constrained Optimization 2.6.2 Instantaneous Approximation of Newton's Method 2.6.3 q-Norm Constrained Optimization 2.6.4 Averaged System 2.6.5 Example 1: Eigenanalysis 2.6.6 Example 2: Convergence Performance 2.6.7 Example 3: Instability 2.7 Set Membership Partial Updates 2.7.1 Example 1: Convergence Performance 2.7.2 Example 2: Instability 2.8 Block Partial Updates 2.9 Complexity Considerations3. Convergence and Stability Analysis 3.1 Introduction 3.2 Convergence Performance 3.3 Steady-State Analysis 3.3.1 Partial-Update LMS Algorithms Periodic partial updates Sequential partial updates Stochastic partial updates M-max partial updates 3.3.2 Partial-Update NLMS Algorithms 3.3.3 Simulation Examples for Steady-State Analysis 3.4 Convergence Analysis 3.4.1 Partial-Update LMS Algorithms Vectorization Steady-State Analysis Mean-Square Stability Mean Stability 3.4.2 Partial-Update NLMS Algorithms 3.4.3 Simulation Examples for Convergence Analysis4. Partial-Update Adaptive Filters 4.1 Introduction 4.2 Least-Mean-Square Algorithm 4.3 Partial-Update LMS Algorithms 4.3.1 Periodic-Partial-Update LMS Algorithm 4.3.2 Sequential-Partial-Update LMS Algorithm 4.3.3 Stochastic-Partial-Update LMS Algorithm 4.3.4 M-max LMS Algorithm 4.3.5 Computational Complexity 4.4 Normalized Least-Mean-Square Algorithm 4.5 Partial-Update NLMS Algorithms 4.5.1 Periodic-Partial-Update NLMS Algorithm 4.5.2 Sequential-Partial-Update NLMS Algorithm 4.5.3 Stochastic-Partial-Update NLMS Algorithm 4.5.4 M-max NLMS Algorithm 4.5.5 Selective-Partial-Update NLMS Algorithm 4.5.6 Set-Membership Partial-Update NLMS Algorithm 4.5.7 Computational Complexity 4.6 Affine Projection Algorithm 4.7 Partial-Update Affine Projection Algorithms 4.7.1 Periodic-Partial-Update APA 4.7.2 Sequential-Partial-Update APA 4.7.3 Stochastic-Partial-Update APA 4.7.4 M-max APA 4.7.5 Selective-Partial-Update APA 4.7.6 Set-Membership Partial-Update APA 4.7.7 Selective-Regressor APA 4.7.8 Computational Complexity 4.8 Recursive Least Squares Algorithm 4.9 Partial-Update RLS Algorithms 4.9.1 Periodic-Partial-Update RLS Algorithm 4.9.2 Sequential-Partial-Update RLS Algorithm 4.9.3 Stochastic-Partial-Update RLS Algorithm 4.9.4 Selective-Partial-Update RLS Algorithm 4.9.5 Set-Membership Partial-Update RLS Algorithm 4.9.6 Partial-Update RLS Simulations 4.9.7 Computational Complexity 4.10 Transform-Domain Least-Mean-Square Algorithm 4.10.1 Power Normalization 4.10.2 Comparison of Power Normalization Algorithms 4.11 Partial-Update Transform-Domain LMS Algorithms 4.11.1 Periodic-Partial-Update Transform-Domain LMS Algorithm 4.11.2 Sequential-Partial-Update Transform-Domain LMS Algorithm 4.11.3 Stochastic-Partial-Update Transform-Domain LMS Algorithm 4.11.4 M-max Transform-Domain LMS Algorithm 4.11.5 Computational Complexity 4.12 Generalized-Subband-Decomposition Least-Mean-Square Algorithm 4.12.1 Relationship Between GSD-LMS Coefficients and Equivalent Time Domain Response 4.12.2 Eigenvalue Spread of GSD Input Correlation Matrix 4.13 Partial-Update GSD-LMS Algorithms 4.13.1 Periodic-Partial-Update GSD-LMS Algorithm 4.13.2 Sequential-Partial-Update GSD-LMS Algorithm 4.13.3 Stochastic-Partial-Update GSD-LMS Algorithm 4.13.4 M-max GSD-LMS Algorithm 4.13.5 Computational Complexity 4.14 Simulation Examples: Channel Equalization5. Selected Applications 5.1 Introduction 5.2 Acoustic Echo Cancellation 5.3 Network Echo Cancellation 5.3.1 PNLMS and mu-Law PNLMS with Selective Partial Updates PNLMS mu-Law PNLMS Selective Partial Updates Simulation Examples 5.4 Blind Channel Equalization 5.4.1 Normalized CMA 5.4.2 Selective-Partial-Update NCMA 5.4.3 Simulation Examples 5.5 Blind Adaptive Linear Multiuser Detection 5.5.1 MUD in Synchronous DS-CDMA 5.5.2 Blind Multiuser NLMS Algorithm 5.5.3 Selective-Partial-Update NLMS for Blind Multiuser Detection 5.5.4 Simulation ExamplesA. Overview of Fast Sorting Algorithms A.1 Introduction A.2 Running Min/Max and Sorting Algorithms A.2.1 Divide-and-Conquer Approaches A.2.2 Maxline Algorithm A.2.3 The Gil-Werman Algorithm A.2.4 Sortline Algorithm A.3 Heapsort Algorithm