Chair: Pierre Duhamel, Ecole Nationale Superieure de Telecommunications, (FRANCE)
Kostas Berberidis, Computer Technology Institute (GREECE)
Sergios Theodoridis, Computer Technology Institute (GREECE)
The algorithm presented in this paper is an exact block processing counterpart of the recently introduced Fast Newton Transversal Filtering (FNTF) algorithm. The main trait of the new algorithm is that the block processing is done in such a way so that the resulting estimates are mathematically equivalent with the respective estimates of the FNTF algorithm. The required by the algorithm blocks can be much smaller than the filter length thus depending on the application the introduced processing delay can be negligible. In cases where the involved filter is of medium to long order the new algorithm offers a substantial saving in computational complexity without sacrificing performance.
C. Sidney Burrus, Rice University (USA)
Ivan W. Selesnick, Rice University (USA)
We describe a set of programs for circular convolution and prime length FFTs that are short, possess great structure, share many computational procedures, and cover a large variety of lengths. The programs make clear the structure of the algorithms and clearly enumerate independent computational branches that can be performed in parallel. Moreover, each of these independent operations is made up of a sequence of sub-operations which can be implemented as vector/parallel operations. This is in contrast with previously existing programs for prime length FFTs: they consist of straight line code, no code is shared between them, and they can not be easily adapted for vector/parallel implementations. We have also developed a program that automatically generates these programs for prime length FFTs.
Haesun Park, University of Minnesota
J. Ben Rosen, University of Minnesota
John Glick, University of San Diego (USA)
The Total Least Squares (TLS) method for solving an overdetermined system Ax = b is a generalization of the Least Squares (LS) method and allows errors E in the given m by n (m >= n) data matrix A. The commonly used TLS algorithm is based on the singular value decomposition (SVD) of the [A b]. However, in applications where the matrix A has a special structure, the SVD based methods may not always be appropriate, since they do not preserve the structure. Recently, a new formulation, called Structured Total Least Norm (STLN), and algorithm for computing solutions have been developed. STLN preserves any affine structure of A or [A b], and can minimize error in the discrete Lp norm, where p=1,2 or infinity. In this paper, we study the STLN method for problems in which the perturbation matrix E or [E r], where r=b-(A+E)x, keeps the Toeplitz structure like the data matrix A or [A b]. These structures occur in many problems such as deconvolution, transfer function modeling and linear prediction problems. In particular, STLN methods with L1 and L2 norms are compared with the LS and TLS methods and shown to improve the accuracy of the solutions significantly. When there is an outlier in the data, the STLN method with L1 norm is shown to produce solutions that are essentially not affected by the outlier.
Andrew E. Yagle, University of Michigan (USA)
We provide a novel approach to the design of fast algorithms for matrix multiplication: reformulation as a convolution implemented using pseudo-number-theoretic transforms. Writing the convolution as multiplication of polynomials evaluated off the unit circle reduces the number of multiplications without producing any error, since the (integer) elements of the product matrix are known to be bounded. The new algorithms are somewhat analogous to the arbitrary precision approximation (APA) algorithms, but have the following advantages: (1) a simple design procedure is specified for them; (2) they do not suffer from roundoff error; and (3) reasons for their existence is clear. The new algorithms are also non-commutative, so that they may be applied recursively to block matrix multiplication.
Wen-Hsien Fang, National Taiwan Institute of Technology (TAIWAN)
Yang-Lung Hwang, National Taiwan Institute of Technology (TAIWAN)
This paper is concerned with the development of new split algorithms for the design of linear least squares prediction filters with linear phase. The proposed fast algorithm, which fully expresses the inherent symmetry of the problem, requires lower computational complexity than other existing ones. Moreover, unlike other existing ones, the new recurrences involve only the order updates, which lend themselves to more efficient hardware implementations. For parallelization consideration, a new split Schur-like algorithm is also proposed to overcome the nonparallelizable inner product. Some numerical simulation results are provided to verify the proposed fast algorithms and highlight possible applications.
Jurgen Gotze, Technical University of Munich (GERMANY)
Martin Haardt, Technical University of Munich (GERMANY)
Josef A. Nossek, Technical University of Munich (GERMANY)
This paper presents efficient Schur-- type algorithms for estimating the column space (signal subspace) of a low rank data matrix corrupted by additive noise. Its computational structure and complexity are similar to that of an LQ-- decomposition, except for the fact that plane and hyperbolic rotations are used. Therefore, they are well suited for a parallel (systolic) implementation. The required rank decision, i.e., an estimate of the number of signals, is automatic, and updating as well as downdating are straightforward. The new scheme computes a matrix of minimal rank which is (gamma)-close to the data matrix in the matrix 2- norm, where (gamma) is a threshold that can be determined from the noise level. Since the resulting approximation error is not minimized, critical scenarios lead to a certain loss of accuracy compared to SVD-based methods. This loss of accuracy is compensated by using Unitary ESPRIT in conjunction with the Schur--type subspace estimation scheme. Unitary ESPRIT represents a simple way to constrain the estimated phase factors to the unit circle and provides a new reliability test. Due to the special algebraic structure of the problem, all required factorizations can be transformed into decompositions of real-valued matrices of the same size. The advantages of Unitary ESPRIT dramatically improve the resulting subspace estimates, such that the performance of Unitary Schur ESPRIT is comparable to that of SVD-based methods, at a fraction of the computational cost. Compared to the original Schur method, Unitary Schur ESPRIT yields improved subspace estimates with a reduced computational load, since it is formulated in terms of real-valued computations throughout.
Amy Bell, University of Michigan (USA)
Rajashri Joshi, University of Michigan (USA)
The wavelet transform is applied to integral equations with Toeplitz kernels, which arise in inverse scattering and linear least- squares estimation, resulting in a system of equations with block-slanted-Toeplitz structure. Previously, this linear system was sparsified by neglecting all entries below some threshold. However, in inverse scattering, the Toeplitz kernel need not be a rapidly decreasing function due to reflections from great depths, so that sparsification will not work. Instead, we exploit the block-slanted-Toeplitz structure to obtain fast algorithms similar to the multichannel Levinson and Schur algorithms. Since it is exact to within the wavelet-basis approximation, this approach is a valuable alternative to sparsification.
Benito Carnero, Swiss Federal Institute of Technology - Lausanne (SWITZERLAND)
Andrzej Drygajlo, Swiss Federal Institute of Technology - Lausanne (SWITZERLAND)
Orthogonal wavelet packet transforms, presented recently as powerful tools for nonstationary signal processing, suffered from the lack of efficient and time-domain transparent algorithms for their implementation. In this paper, we present an overlapped block lattice structure that allows fast short-time wavelet packet transform algorithms to be built in an equivalent manner to other short-time transforms, such as the short-time Fourier transform (STFT) based on the fast Fourier transform (FFT) algorithms. The outputs obtained with the overlapped block lattice are equivalent to those achieved by the well known tree-structured filter bank approach, though the implementation algorithms are different.
Michael Vrhel, National Institutes of Health (USA)
Chulhee Lee, National Institutes of Health (USA)
Michael Unser, National Institutes of Health (USA)
We introduce a general framework for the efficient computation of the continuous wavelet transform (CWT). The method allows arbitrary sampling along the scale axis, and achieves O(N) complexity per scale where N is the length of the signal. Our approach makes use of a compactly supported scaling function to approximate the analyzing wavelet. We derive error bounds on the wavelet approximation and show how to obtain any desired level of accuracy through the use of higher order representations. Finally, we present examples of implementation for different wavelets using polynomial spline approximations.
Wan-Chi Siu, Hong Kong Polytechnic (HONG KONG)
Yuk-Hee Chan, Hong Kong Polytechnic (HONG KONG)
Lap-Pui Chau, Hong Kong Polytechnic (HONG KONG)
It is always desirable to look for more efficient algorithms for the realization of the discrete cosine transform (DCT). In this paper, we generalize a formulation for converting a length-$2^n$ DCT transform into n groups of equations, then apply a novel technique for its implementation. The sizes of the groups are $2^m$, for m = n-1, ...., 0. While their structures are extremely regular. The realization can then be converted into the simplest recursive filter form, which is of particularly simple for practical implementation.