Lang Withers (lwithers@psrw.com) Guest

Posted: Mon Sep 29, 1997 5:41 pm Subject: Question: Wavelets and convolution theorem




#26 Question: Wavelets and convolution theorem
Are there any wavelets that, in addition to having properties such as
(bi)orthogonality under translation and dilation, and the ability to
approximate piecewise linear functions, also have a fast convolution
algorithm (in either the "time"domain or the transform domain)?
A familiar and important property of the (discrete) Fourier basis is
its (circular) convolution property, enabling fast convolution in the
transform domain by means of FFTs. So it's natural to ask if there
exist wavelets with a similar property exploitable by means of the
pyramid algorithm, or anyway with some kind of fast convolution.
Here is a possible hint:
(1) John Whelchel observed (personal communication) that for the
Hadamard matrix H and a symmetric Toeplitz matrix T, the matrix H'TH
has half its offdiagonal elements reduced to zero. Here I'm using H'
to denote the inverse of H.
(2) Compare this with the well known
result that for the DFT matrix F = (w^{jk}), (with w =exp(i2pi/n) an
nth root of unity) and a cyclic matrix C, F'CF is diagonal. This
result follows from the relation FA=DF, where
D=diag(1,w,w^2,...,w^{n1}) and A is the cyclic shift matrix. (Any
cyclic (circulant) matrix is a linear combination of successive powers
of A.)
(3) Similar to (1), we find for the Haar wavelet transform
matrix W, the matrix W'*C*W has all 0's in the first row and column
(except the 1,1 element) (Also true for W^T*C*W, with W^T the
transpose of W.) This is weaker than Whelchel's note (1), but closer
to the Fourier case (2) because it applies to cyclic
matrices. Moreover, for cyclic matrices made from arithmetic (evenly
spaced) sequences, such as C with first row [3,5,7,9], the entire
lower right quarter of W'*C*W is an identity matrix. (The Haar wavelet
W is the only one I've looked at.) 
Thank you.
Lang Withers
PacificSierra Research Corporation
1400 Key Blvd., Suite 700, Arlington, VA 22209
phone:(703)8075694
fax: (703)5242420
email: lwithers@psrw.com
[Answer WD 6.11#21]
A similar question was posed in WD 4.2#38.
This generated two answers:[Answer WD 4.3#14]
[Answer WD 4.4#13] 
