We have the DFT(matrix form) $X = Wx$ ($W$ is the Fourier basis matrix, $x$ is the original signal in time domain, $X$ is in the frequency domain).

In mathematics, $x$ represents the coordinates of $X$ with respect to $W$. I don't know how this happens. I think $x = WX$ is right, because $X$ is in the space spanned by the $W$, thus $x$ is the linear combination of Fourier basis and Fourier coefficients. Thus $x = WX$.

Why is it valid? Can you tell me?



36''33', Prof. Strang gives a different explanation in wavelet transform, it differs from DFT.. That's why I am confused

  • 3
    $\begingroup$ If $X=Wx$, then $x=W^{-1}X$, not $WX$. $\endgroup$ – Dilip Sarwate Jun 4 '16 at 15:20
  • $\begingroup$ @DilipSarwate The question is, I don't think $X=Wx$ is right. $\endgroup$ – stander Qiu Jun 4 '16 at 22:48
  • $\begingroup$ that's not a question. $X=Wx$ is obviously right, given that you've defined it. $\endgroup$ – Marcus Müller Jun 4 '16 at 22:49
  • $\begingroup$ $X=Wx$ is defined by Oppenhiem, not me. I could not understand the meaning of it $\endgroup$ – stander Qiu Jun 4 '16 at 22:54
  • 3
    $\begingroup$ @Fat32 I've reopened it, but it seems like a nonsense question. $\endgroup$ – Peter K. Jun 5 '16 at 0:06

The Fourier matrix (which you refer to as Fourier basis matrix) is, according to Wolfram MathWorld, an $n\times n$ matrix with entries given by $\omega^{np}$ (with $\omega$ being the roots of unity). Here $n$ is the time index and $p$ is the frequency index.

Hence I think it's not reasonable to say that the Fourier matrix is either in the "time space" or the "frequency space" (or domain, if you like), since it is in both!

Also, there might be some confusion here due to the different meanings of the words like space, domain, basis, and vector, depending on the context.

So for linear algebra (from Wolfram MathWorld), we have:

  • (vector) space: A vector space V is a set that is closed under finite vector addition and scalar multiplication. The basic example is $n$-dimensional Euclidean space $R^n$, where every element is represented by a list of $n$ real numbers, scalars are real numbers [...].

  • vector: A vector is formally defined as an element of a vector space.

  • basis: A basis of a vector space V is defined as a subset $v_1,...,v_n$ of vectors in V that are linearly independent and span V.

As for sigProc (from Wikipedia), we have:

  • time / frequency domain: The time/frequency domain refers to the analysis of mathematical functions or signals with respect to time/frequency. Put simply, a time-domain graph shows how a signal changes over time, whereas a frequency-domain graph shows how much of the signal lies within each given frequency band over a range of frequencies.

  • (data) vector / 1D array: In computer science, an array is a data structure consisting of a collection of elements, each identified by at least one array index or key.

Hope this helps!

  • $\begingroup$ @standerQiu Btw, the two $W$'s in your last comment are different... Also, you could force them into the same "(output) = (transformation matrix) x (input)" form if you wanted by writing $X=Wx$ for DFT and $c=(W^{-1})x$ for DWT (still different $W$ matrices tho) $\endgroup$ – zahypeti Jun 5 '16 at 23:33
  • $\begingroup$ Eventually I find an answer to my question! Fourier matrix is either in the "time space" or the "frequency space" (or domain, if you like), since it is in both! Thx!! $\endgroup$ – stander Qiu Jun 6 '16 at 4:36

It's not valid. If any matrix $W$ is invertible (such as the DFT matrix is), then there's the inverse $W^{-1}$ with

$$\begin{align} W^{-1}W &=I\\ &\implies\\ X &= Wx \\ &\iff\\ W^{-1} X &= W^{-1}W x\\ &= Ix\\ &=x\text{ .} \end{align}$$

Now, the Discrete Fourier transform can be defined to be unitary, so that its inverse

$$W^{-1}=W^*$$ is but the hermitian of the original transform.

In no case are the DFT and IDFT identical.

  • $\begingroup$ @DilipSarwate thanks! I had a bit of a bad conscience by giving an answer that had little more content then your comment under the question; but that was really something I needed to point out. If $W=W^{-1}$, then either $W$ would have to be real (which can't be, because of the various shift properties of the DFT, for example), or wouldn't have only positive Eigenvalues – which would be a disaster for Parseval's Theorem, for example. $\endgroup$ – Marcus Müller Jun 4 '16 at 17:15
  • $\begingroup$ @MarcusMüller My question is not that.. I know $x = W^{H}X$, but in mathematics,$X$ is in the space spanned by Fourier basis $W$, so $x$ should be the linear combination of Fourier basis and Fourier coefficients -> $x = WX$ $\endgroup$ – stander Qiu Jun 4 '16 at 22:45
  • $\begingroup$ @standerQiu, no. Simply, no. $x=W^{-1}X$ the way you defined it. Just because the span is the same doesn't mean the operation and its inverse are the same. $\endgroup$ – Marcus Müller Jun 4 '16 at 22:47
  • 1
    $\begingroup$ @standerQiu Is your problem that $x$ has units of time and $X$ has units of frequency? If so, note that the DFT operates on sequences of numbers (you could say, on "vectors") with no units. We assign units to those sequences somewhat arbitrarily; or put another way, we interpret $x$ as samples in time and $X$ as samples in frequency, but it's just an interpretation (that happens to be useful). $W$ has no units, either. $\endgroup$ – MBaz Jun 5 '16 at 1:25
  • 3
    $\begingroup$ @MBaz and stander, while the arguments of $x(t)$ and $X(f)$ have units of time or frequency (respectively), these are the content of the continuous Fourier Transform. the DFT maps a set of dimensionless numbers, with dimensionless indices of integer value, from one domain (commonly called the "time domain") to another set of dimensionless numbers, also with dimensionless integer indices, in another domain (commonly called the "frequency domain"). the computer that crunches the numbers in the DFT has no idea of attached units. $\endgroup$ – robert bristow-johnson Jun 5 '16 at 6:45

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