The Wavelet Digest Homepage
Return to the homepage
Search the complete Wavelet Digest database
Help about the Wavelet Digest mailing list
About the Wavelet Digest
The Digest The Community
 Latest Issue  Back Issues  Events  Gallery
The Wavelet Digest
   -> Volume 6, Issue 10

Question: Wavelets and convolution theorem
images/spacer.gifimages/spacer.gif Reply into Digest
Previous :: Next  
Author Message
Lang Withers (

PostPosted: Mon Sep 29, 1997 5:41 pm    
Subject: Question: Wavelets and convolution theorem
Reply with quote

#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 off-diagonal 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^{n-1}) 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
Pacific-Sierra Research Corporation
1400 Key Blvd., Suite 700, Arlington, VA 22209
fax: (703)524-2420

[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]
All times are GMT + 1 Hour
Page 1 of 1

Jump to: 

disclaimer -
Powered by phpBB

This page was created in 0.025309 seconds : 18 queries executed : GZIP compression disabled