I am a PhD. in pure mathematics.

  1. Could you please illustrate the following statement: the eigenvectors of a graph Laplacian behave similarly to a Fourier basis, motivating the development of graph-based Fourier analysis theory.
  2. I am reading the interesting paper, but could not get how the Fourier transform is extended to the graph Fourier transform as illustrated on page 23. Indeed, why should the matrix V be considered as the extension of (discrete) Fourier transform?
  • $\begingroup$ To those voting to close for not being signal processing related: The paper linked to above is from EUSIPCO, the premier signal processing conference in Europe. That makes it very relevant to SE.SP, even if it's a bit more mathematical than some other questions we field here. $\endgroup$ – Peter K. Jun 15 '20 at 15:21

This is a valid question within the context of GSP although, it might not sound like much of a digital signal processing question.

To understand that point, you need to understand what the eigenvalues/eigenvectors tell us (about a matrix), then how is the Laplacian constructed (and what it means) and then relate it to DSP.

The Eigendecomposition of a matrix is a way of expressing the matrix as a product of eigenvalues and eigenvectors. To understand their geometrical interpretation, imagine that each row of the matrix describes a vector in some n-dimensional space. A vector has a beginning and an end and it points towards a direction. The eigendecomposition of a matrix decomposes the "most common" direction that these vectors are pointing towards as a sum of some elementary vectors (eigenvectors) multiplied by their strengths (eigenvalues).

If you were to fill a matrix with vectors that are pointing towards the same direction and asked for its eigendecomposition, you would get back 1 eigenvector at maximum strength. That eigenvector points towards the direction that all vectors in the matrix point towards. Try it here

If you were to fill a matrix with two subsets of vectors where one subset points in some direction and the other points to some other direction, you will get a different mixture.Try it here. You can try different values and explore this notion, I am just providing some simple illustrative examples here. For more information on how this is applied to image/signal processing more generally, you might want to see here.

Moving on to the Laplacian: The Laplacian, in Graph Theory is a very important matrix because it is the bridge to Spectral Graph Theory. The Laplacian's definition is of course one but there are different shortcuts depending on the type of graph you are dealing with. For example, for simple undirected graphs, you don't really have to evaluate the difference between the Degree and Adjacency matrices since that would result in a -1 when two nodes are adjacent and a 0 if they were not and the main diagonal filled with the degree of each node.

This is the construction. And the point is that the Laplacian can be used to broadly characterise graphs. It becomes very useful when you are dealing with graphs that are intractably (for a human brain) big. But, informally, the Laplacian is giving us a "proper" way (from the point of view of functional mathematics) to encode the connectivity of the graph and work with it algebraicaly.

If you couple this with the eigendecomposition, you can see how the pattern of node connectivity (how nodes are connected with each other) can be decomposed into sub-structures via the eigendecomposition we described earlier.

This is where the connection is made between the Fourier Transform, that is used to decompose a waveform into a sum of sinusoidal components and a graph's spectral decomposition, that is used to decompose the pattern of connectivity into a sum of sub-patterns. (All this, under specific constraints of course, so that these things do not break).

The last thing that remains now is to link all this with digital signal processing. DSP has its roots in Time Series analysis. Graphs are mathematical objects that capture relationships, how are these two things combined?

The answer to this is in the way you can map a signal on to a graph or, knowing that the signal originates from a process of which the graph is known, make some inferences about the signal. This latter case is very topical in biomedical signal processing and specifically brain connectivity, where you can infer which areas of the brain exchange information to achieve a certain cognitive task. (Those colourful matrices are basically weight matrices of graphs but you infer them through a series of correlations between various waveforms).

In the presentation (paper (?)) that you cite, this is outlined around slides 6 to 8, where some basic examples are given on trying to map certain processes on networks, then process the networks and conclude to something about the signal itself. And then slides 52 onwards provide some more concrete practical examples.

Hope this helps

  • $\begingroup$ Thanks a lot. Your comments are so amazing. $\endgroup$ – Ali Bagheri May 21 '20 at 6:19
  • $\begingroup$ Thank you. Glad to hear that this was useful. I hope you stay on it and come back and tell us more about it too :) . GSP is an emerging branch and there is a lot of "new" information in the processing of graphs. $\endgroup$ – A_A May 21 '20 at 10:32
  • $\begingroup$ Thanks and sure. It will be great if you let me know any link, paper, or discussion which makes sharp me on this subject as much as possible. Email: alihoular@gmail.com $\endgroup$ – Ali Bagheri May 21 '20 at 11:46
  • $\begingroup$ @AliBagheri You have more chances of getting a quicker and more information rich response if you were to post a specific question on this board :) There is also a chat option, for things that might require some clarification before becoming a specific question. $\endgroup$ – A_A May 23 '20 at 21:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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