Algorithmic Combinatorics Seminar, Summer 2002

Abstract: Wavelets and filter banks have become useful in digital signal processing in part because of their ability to represent piecewise smooth signals with relative efficiency. For such signals, the discrete wavelet transform (DWT) developed as a main tool for signal compression (JPEG 2000), fast algorithms, and signal estimation and modeling (noise suppression and image segmentation, etc). While the spectral factorization approach is the most convenient method to construct the classic Daubechies wavelets (and the corresponding digital filters), it is not applicable anymore to more advanced design problems where additional constraints are imposed. A typical case comes with the construction of multiwavelets (corresponding to filter banks with relaxed requirements on their time-invariance). As for many of these problems, the design equations can be written as a multivariate polynomial system of equations. Accordingly, Gröbner algorithms offer an effective way to obtain solutions in these cases. We will detail in this talk some examples of this algebraic approach to the design of filter banks.

Abstract: We discuss the sum-of-digits function and related quantities. In particular, the elementary method of Delange will be presented, as well as the use of the Mellin-Perron summation formula, as introduced by Flajolet. Several applications to counting problems from Theoretical Computer Science (Horton-Strahler numbers, Odd-Even Merge, Carry Propagation) are also sketched.