3 ms·

A windowed graph Fourier transform (2012)

65 points by teleforce 3y ago

deleted 3y ago
[deleted]
defrost 3y ago
Sidestepping Signin: https://sci-hub.ru/10.1109/SSP.2012.6319640 https://sci-hub.ru/10.1109/SSP.2012.6319640 https://sci-hub.st/10.1109/SSP.2012.6319640 https://sci-hub.st/10.1109/SSP.2012.6319640 .. and for something not quite completely different: Wavelet theory has its origin in several disciplines; the types of functions that are now called wavelets were studied in quantum field theory, signal analysis, and function space theory. In all these areas, wavelet-like algorithms replaced the classical Fourier-type expansion of a function. It was not until the mid-1980s that these, at first, seemingly different notions were described in a unified manner. Because of the restricted scope of this monograph, we will not be able to address some ramifications of wavelet bases for so-called wavelet frames. The wavelet transform is an alternative to the classical windowed Fourier transform. [ ... ] https://www.sciencedirect.com/science/article/abs/pii/B9780128044087000084 https://www.sciencedirect.com/science/article/abs/pii/B97801...
michelpp 3y ago
A similar and more recent example of graph decomposition is the fast graphlet transform: https://github.com/fcdimitr/fglt https://github.com/fcdimitr/fglt This algorithm has a nice Algebraic formulation recently implemented with the GraphBLAS in LAGraph: https://github.com/GraphBLAS/LAGraph/blob/stable/experimental/algorithm/LAGraph_FastGraphletTransform.c https://github.com/GraphBLAS/LAGraph/blob/stable/experimenta...
CamperBob2 3y ago
I'm unclear on why I would want to "translate" a "signal" on an arbitrary weighted graph such as the Minnesota road map example, in the same sense that I might multiply a time-domain signal by a complex exponential to translate it to a higher or lower frequency in the frequency domain. The latter is an everyday operation in signal processing but what does it mean in other contexts? Are there any good concrete examples of what such a translation would accomplish?
- teleforce 3y ago
  It is related to spectral graph theory where associations between graph theory and linear algebra are being made where typically power iteration algoritm is then applied not unlike the venerable PageRank algorithm [1]. [1] The Power Iteration Algorithm in Practice: https://scicoding.com/the-power-iteration-algorithm-in-practice/ https://scicoding.com/the-power-iteration-algorithm-in-pract...
  - CamperBob2 3y ago
    That's interesting, but it doesn't answer my question. I think I'm missing too many prereqs on this one, unfortunately.
    - teleforce 3y ago
      If you are familiar with conventional spectral analysis, there are higher order spectral analysis. For example before feeding data to your machine learning or AI pipeline, you want transform the waveforms (EM, sound, etc) raw data into higher order spectral to provide more features hence better accuracy. You can use the raw data by simply using the scalar values namely amplitude, time and frequency but the accuracy is much better if you can use the higher order analysis of tine-frequency for examples short time Fourier Transform or spectogram (linear time-frequency), wavelet (time-scale) or the non-linear Cohen class (bilinear time-frequency e.g Wigner-Ville) [1]. But if your data is not a waveform but network (road traffic network, Internet network, sensor networks, etc), similarly you probably better off with higher order graph or hypergraph [2]. In this paper it proposed a linear transformation of graph networks using a new windowed graph Fourier Transform analogous to spectogram, but the spectral in graph here is not the waveform spectrum but the eigenvalues for the matrix representation of the graph. There were discussions few months back in HN on higher order graph or hypergraph approach for analyzing big data [3]. [1] Higher-order spectra analysis : a nonlinear signal processing framework: https://www.semanticscholar.org/paper/Higher-order-spectra-analysis-%3A-a-nonlinear-signal-Nikias-Petropulu/c7d16e16f45925abeb5149c5688dba54a0775853 https://www.semanticscholar.org/paper/Higher-order-spectra-a... [2] Hypergraph: https://en.m.wikipedia.org/wiki/Hypergraph https://en.m.wikipedia.org/wiki/Hypergraph [3] How big data carried graph theory into new dimensions: https://news.ycombinator.com/item?id=38120497 https://news.ycombinator.com/item?id=38120497

65 points by teleforce 3y ago

deleted 3y ago

[deleted]

Sidestepping Signin: https://sci-hub.ru/10.1109/SSP.2012.6319640 https://sci-hub.ru/10.1109/SSP.2012.6319640 https://sci-hub.st/10.1109/SSP.2012.6319640 https://sci-hub.st/10.1109/SSP.2012.6319640 .. and for something not quite completely different: Wavelet theory has its origin in several disciplines; the types of functions that are now called wavelets were studied in quantum field theory, signal analysis, and function space theory. In all these areas, wavelet-like algorithms replaced the classical Fourier-type expansion of a function. It was not until the mid-1980s that these, at first, seemingly different notions were described in a unified manner. Because of the restricted scope of this monograph, we will not be able to address some ramifications of wavelet bases for so-called wavelet frames. The wavelet transform is an alternative to the classical windowed Fourier transform. [ ... ] https://www.sciencedirect.com/science/article/abs/pii/B9780128044087000084 https://www.sciencedirect.com/science/article/abs/pii/B97801...

michelpp 3y ago

A similar and more recent example of graph decomposition is the fast graphlet transform: https://github.com/fcdimitr/fglt https://github.com/fcdimitr/fglt This algorithm has a nice Algebraic formulation recently implemented with the GraphBLAS in LAGraph: https://github.com/GraphBLAS/LAGraph/blob/stable/experimental/algorithm/LAGraph_FastGraphletTransform.c https://github.com/GraphBLAS/LAGraph/blob/stable/experimenta...

CamperBob2 3y ago

I'm unclear on why I would want to "translate" a "signal" on an arbitrary weighted graph such as the Minnesota road map example, in the same sense that I might multiply a time-domain signal by a complex exponential to translate it to a higher or lower frequency in the frequency domain. The latter is an everyday operation in signal processing but what does it mean in other contexts? Are there any good concrete examples of what such a translation would accomplish?

teleforce 3y ago
It is related to spectral graph theory where associations between graph theory and linear algebra are being made where typically power iteration algoritm is then applied not unlike the venerable PageRank algorithm [1]. [1] The Power Iteration Algorithm in Practice: https://scicoding.com/the-power-iteration-algorithm-in-practice/ https://scicoding.com/the-power-iteration-algorithm-in-pract...
- CamperBob2 3y ago
  That's interesting, but it doesn't answer my question. I think I'm missing too many prereqs on this one, unfortunately.
  - teleforce 3y ago
    If you are familiar with conventional spectral analysis, there are higher order spectral analysis. For example before feeding data to your machine learning or AI pipeline, you want transform the waveforms (EM, sound, etc) raw data into higher order spectral to provide more features hence better accuracy. You can use the raw data by simply using the scalar values namely amplitude, time and frequency but the accuracy is much better if you can use the higher order analysis of tine-frequency for examples short time Fourier Transform or spectogram (linear time-frequency), wavelet (time-scale) or the non-linear Cohen class (bilinear time-frequency e.g Wigner-Ville) [1]. But if your data is not a waveform but network (road traffic network, Internet network, sensor networks, etc), similarly you probably better off with higher order graph or hypergraph [2]. In this paper it proposed a linear transformation of graph networks using a new windowed graph Fourier Transform analogous to spectogram, but the spectral in graph here is not the waveform spectrum but the eigenvalues for the matrix representation of the graph. There were discussions few months back in HN on higher order graph or hypergraph approach for analyzing big data [3]. [1] Higher-order spectra analysis : a nonlinear signal processing framework: https://www.semanticscholar.org/paper/Higher-order-spectra-analysis-%3A-a-nonlinear-signal-Nikias-Petropulu/c7d16e16f45925abeb5149c5688dba54a0775853 https://www.semanticscholar.org/paper/Higher-order-spectra-a... [2] Hypergraph: https://en.m.wikipedia.org/wiki/Hypergraph https://en.m.wikipedia.org/wiki/Hypergraph [3] How big data carried graph theory into new dimensions: https://news.ycombinator.com/item?id=38120497 https://news.ycombinator.com/item?id=38120497