Partial-Update Adaptive Signal Processing

APPENDIX A

Overview of fast sorting algorithms

A.1 Introduction

In this appendix we summarize the operation and computational complexity of sorting algorithms for use in data-dependent partial coefficient updates. Data-dependent partial-update algorithms require ranking of regressor data or a well-defined function of regressor data. In the context of complexity reduction, which is the chief objective of partial coefficient updates, the computational complexity of ranking is an important consideration. Efficient fast sorting algorithms are of particular interest in the design of partial-update adaptive filters. In this appendix we provide an overview of computationally efficient running min/max and sorting algorithms, as well as a traditional ...