1
$\begingroup$

The frequency domain is allegedly preferred because it replaces convolution of complexity $n^2$ with a diagonal matrix multiplication. Yet, I see that in z-domain we have multiplication of polynomials, $(a_0z+a_1z^{-1}+a_2z^{-2}+\ldots)(b_0z+b_1z^{-1}+b_2z^{-2}+\ldots)$, which is, despite its name, is nothing more than convolution with $n^2$ operations: you need multiply one polynomial with every term of the other and combine the terms. This looks like square convolution matrix rather than diagonal one. What is the benefit?

In this regards, I recalled my old question: why nobody speaks about eigenfunctions of the s- and z-domains? Everybody speaks that transfer function is linear and diagonal in the frequency (s- and z-domains). But, when you speak about linear operators, you must bring up their natural basis, especially when speak about diagonalization. How do eigenvectors look like in the Laplace and z-domain? What is the basis of this domain? Might be you do not need to prove the convolution theorem then?

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ You're conflating the $z$ plane with the frequency response of a system. If you're performing time-domain convolution by multiplying two signals together in the frequency domain, you do not use the $z$-domain transfer function as part of that process. As you noted, the transfer function follows directly from the associated difference equation, which maps closely to how you would implement convolution in the time domain. Secondly, "people do speak" of the eigenfunctions of linear systems: they are complex exponential functions. $\endgroup$
    – Jason R
    Jun 4, 2013 at 16:54
  • $\begingroup$ Thank you for understanding my confusion. Might be somebody will not just repeat it but gives an explanaion. Also, complex exponentials appear in Fourier transform. They are known there indeed. But Laplace and z-domain are something stronger and nobody speaks about their eigenfunctions. $\endgroup$
    – Val
    Jun 4, 2013 at 17:03
  • $\begingroup$ The eigenfunctions of linear systems are (decaying) exponentials and complex sinusoids. The complex Laplace transform encapsulates this information (write s = o + iw and see for yourself). $\endgroup$
    – Tom Kealy
    Sep 5, 2013 at 9:47
  • $\begingroup$ @TomKealy Where did you seen the proof of that? I've looked through the Gilbert Strang linear algebra and he demonstrates many systems with all kinds of eigenvectors and I do not remember that they all are exponentials. The only case where exponentials were eigenvectors was a fourier transform. $\endgroup$
    – Val
    Sep 5, 2013 at 10:47
  • $\begingroup$ I mean just replace the s in the Laplace transform with the expression above and an exponential and complex sinusoid pop out. e^i(theta) isn't an exponential, it's a sinusoid. The solution of an LTI differential eqn can be written as a linear sum of decaying exponentials and steady-state sinusoids - for example damped harmonic oscillators. $\endgroup$
    – Tom Kealy
    Sep 5, 2013 at 11:30

1 Answer 1

Reset to default
1
$\begingroup$

There may be a confusion here about how to cascade filters versus how to actual perform filtering.

There many different ways to implement linear time invariant filtering. If the filter can be represented as an FIR filter than two of the choices are time-domain convolution or frequency domain filtering such as overlap add. The later does indeed just require complex multiplication in the frequency domain (plus the actuall FFTs as well). For large filter length frequency domain processing is a lot more efficient but induces significant latency.

There are many, many other ways to implement filters as well.

Not sure what you mean by "diagonal matrix multiplication". For a system with a single input and a single output, this is just a simple vector multiply and there is no need for a matrix. While you can express time domain convolution as a matrix multiplication, it's not particularly efficient to actually implement it this way, so the matrix representation is mainly used for mathematical analysis.

EDIT: Lets use a specific example

Let's say you have a real signal of 1024 points and a real FIR filter of 1024 taps. Doing a direct convolution takes (roughly) 1024*1024 multiply-add operations for a total ca. 2.1 million scalar operations.

Doing it in the frequency domain requires a forward FFT, complex multiplication in the frequency domain and an inverse FFT. A forward FFT of length 1024 takes about 5*1024*log2(1024)= 51200 scalar operations. A complex multiply takes about 6 scalar operations. So the total would be 2*51200+6*1024 or roughly 110k operations. In this particular example the frequency domain multiplication is about 20 times more efficient than the time domain convolution.

DISCLAIMER: This example glosses over a lot of details of the frequency domain method, in particular zero-padding, doing efficiently complex FFTs of real valued signals and overlap handling. However, in terms of computational complexity these mostly cancel each other and don't make a big difference in total operation count.

Improve this answer
$\endgroup$
6
  • $\begingroup$ Mathematical analysys says that there are eighenspaces where matrix takes diagonal from (look for diagonalization and what it serves for). You like repeat the drilled definitions without looking at the example that I ask to dissect with your knowledge of convolution theorem. I was told that z-domain is a frequency domain and therefore complexity boils down to simple multiplication. But, I see that transfer function is polynomial in z-domain and multiplying polinomials has as much koefficient multiplications as convolution, I see no benefit doing anything in z-domain. $\endgroup$
    – Val
    Jun 4, 2013 at 15:51
  • $\begingroup$ Complexity of WHAT? What specifically are you trying to do and estimate? Filtering, cascading of transfer functions or something different? What is your application here? Why do you need matrices in the first place? $\endgroup$
    – Hilmar
    Jun 4, 2013 at 16:26
  • $\begingroup$ Computational complexity, en.wikipedia.org/wiki/Computational_complexity_theory Look at en.wikipedia.org/wiki/Matrix_diagonalization#Diagonalization and why do we like filtering in the frequency domain, en.wikipedia.org/wiki/Convolution_theorem Think why authors of that article speak about computational complexity, why don't they need application in the first place? Think about that. $\endgroup$
    – Val
    Jun 4, 2013 at 16:37
  • $\begingroup$ okay. I added a specific example in my answer. Does that help? $\endgroup$
    – Hilmar
    Jun 4, 2013 at 19:49
  • $\begingroup$ I am glad that you have realized that application is not necessary to make the statement. This is a progress. Now, you should understand that you exemplify what I already understand. You should understand that my concern is that multiplication in z-domain takes the same n^2 elementary multiplications. Read this and try to understand that z-transform is basically multiplication of polinomials that takes n^2 operations, fgiesen.wordpress.com/2012/08/26/z-transform-done-quick, and, then, answer. $\endgroup$
    – Val
    Jun 5, 2013 at 14:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.