Excellence in Research and Innovation for Humanity

International Science Index


Select areas to restrict search in scientific publication database:
10006802
Efficient Filtering of Graph Based Data Using Graph Partitioning
Abstract:
An algebraic framework for processing graph signals axiomatically designates the graph adjacency matrix as the shift operator. In this setup, we often encounter a problem wherein we know the filtered output and the filter coefficients, and need to find out the input graph signal. Solution to this problem using direct approach requires O(N3) operations, where N is the number of vertices in graph. In this paper, we adapt the spectral graph partitioning method for partitioning of graphs and use it to reduce the computational cost of the filtering problem. We use the example of denoising of the temperature data to illustrate the efficacy of the approach.
Digital Article Identifier (DAI):

References:

[1] Pascal Frossard Antonio Ortega David I Shuman, Sunil K. Narang and Pierre Vandergheynst, “The emerging field of signal processing on graphs,” IEEE Signal Processing Magazine, pp. 83–98, May 2013.
[2] Jose M. F. Moura Aliaksei Sandryhaila, “Discrete signal processing on graphs,” IEEE Transactions on Signal Processing, vol. 61, pp. 1644–1656, 2013.
[3] F. R. K. Chung, Spectral Graph Theory, AMS, 1996.
[4] P. Vandergheynst D. K. Hammond and R. Gribonval, “Wavelets on graphs via spectral graph theory,” J. Appl. Comp. Harm. Anal, vol. 30, no. 2, pp. 129150, 2011.
[5] Markus P¨uschel and Jos´e M. F. Moura, “Algebraic signal processing theory: Foundation and 1-D time,” IEEE Transactions on Signal Processing, vol. 56, no. 8, pp. 3572–3585, 2008.
[6] Markus P¨uschel and Jos´e M. F. Moura, “Algebraic signal processing theory: 1-D space,” IEEE Transactions on Signal Processing, vol. 56, no. 8, pp. 3586–3599, 2008.
[7] A. Sandryhaila and J. M. F. Moura, “Discrete signal processing on graphs: Graph fourier transform,” in IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP), pp. 6167-6170, 2013.
[8] J. M. F. Moura A. Sandryhaila, “Discrete signal processing on graphs: Graph filters,” in IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP), pp. 6163-6166, 2013.
[9] J. M. F. Moura A. Sandryhaila, “Discrete signal processing on graphs: Frequency analysis,” IEEE Transactions on Signal Processing, vol. 62, no. 12, pp. 3042–3054, 2014.
[10] P. Lancaster and M. Tismenetsky, The Theory of Matrices, Academic Press, 2nd edition, 1985.
[11] Jose M. F. Moura Jelena Kovacevic Siheng Chen, Aliaksei Sandryhaila, “Signal denoising on graphs via graph filtering,” in IEEE Global Conference on Signal and Information Processing (GlobalSIP),, December 2014.
[12] Kang-Pu Paul Liu Alex Pothen, Horst D. Simon, “Partitioning sparse matrices with eigenvectors of graphs,” Report, NAS Systems Division, NASA Ames Research Center, 1989.
Vol:11 No:11 2017Vol:11 No:10 2017Vol:11 No:09 2017Vol:11 No:08 2017Vol:11 No:07 2017Vol:11 No:06 2017Vol:11 No:05 2017Vol:11 No:04 2017Vol:11 No:03 2017Vol:11 No:02 2017Vol:11 No:01 2017
Vol:10 No:12 2016Vol:10 No:11 2016Vol:10 No:10 2016Vol:10 No:09 2016Vol:10 No:08 2016Vol:10 No:07 2016Vol:10 No:06 2016Vol:10 No:05 2016Vol:10 No:04 2016Vol:10 No:03 2016Vol:10 No:02 2016Vol:10 No:01 2016
Vol:9 No:12 2015Vol:9 No:11 2015Vol:9 No:10 2015Vol:9 No:09 2015Vol:9 No:08 2015Vol:9 No:07 2015Vol:9 No:06 2015Vol:9 No:05 2015Vol:9 No:04 2015Vol:9 No:03 2015Vol:9 No:02 2015Vol:9 No:01 2015
Vol:8 No:12 2014Vol:8 No:11 2014Vol:8 No:10 2014Vol:8 No:09 2014Vol:8 No:08 2014Vol:8 No:07 2014Vol:8 No:06 2014Vol:8 No:05 2014Vol:8 No:04 2014Vol:8 No:03 2014Vol:8 No:02 2014Vol:8 No:01 2014
Vol:7 No:12 2013Vol:7 No:11 2013Vol:7 No:10 2013Vol:7 No:09 2013Vol:7 No:08 2013Vol:7 No:07 2013Vol:7 No:06 2013Vol:7 No:05 2013Vol:7 No:04 2013Vol:7 No:03 2013Vol:7 No:02 2013Vol:7 No:01 2013
Vol:6 No:12 2012Vol:6 No:11 2012Vol:6 No:10 2012Vol:6 No:09 2012Vol:6 No:08 2012Vol:6 No:07 2012Vol:6 No:06 2012Vol:6 No:05 2012Vol:6 No:04 2012Vol:6 No:03 2012Vol:6 No:02 2012Vol:6 No:01 2012
Vol:5 No:12 2011Vol:5 No:11 2011Vol:5 No:10 2011Vol:5 No:09 2011Vol:5 No:08 2011Vol:5 No:07 2011Vol:5 No:06 2011Vol:5 No:05 2011Vol:5 No:04 2011Vol:5 No:03 2011Vol:5 No:02 2011Vol:5 No:01 2011
Vol:4 No:12 2010Vol:4 No:11 2010Vol:4 No:10 2010Vol:4 No:09 2010Vol:4 No:08 2010Vol:4 No:07 2010Vol:4 No:06 2010Vol:4 No:05 2010Vol:4 No:04 2010Vol:4 No:03 2010Vol:4 No:02 2010Vol:4 No:01 2010
Vol:3 No:12 2009Vol:3 No:11 2009Vol:3 No:10 2009Vol:3 No:09 2009Vol:3 No:08 2009Vol:3 No:07 2009Vol:3 No:06 2009Vol:3 No:05 2009Vol:3 No:04 2009Vol:3 No:03 2009Vol:3 No:02 2009Vol:3 No:01 2009
Vol:2 No:12 2008Vol:2 No:11 2008Vol:2 No:10 2008Vol:2 No:09 2008Vol:2 No:08 2008Vol:2 No:07 2008Vol:2 No:06 2008Vol:2 No:05 2008Vol:2 No:04 2008Vol:2 No:03 2008Vol:2 No:02 2008Vol:2 No:01 2008
Vol:1 No:12 2007Vol:1 No:11 2007Vol:1 No:10 2007Vol:1 No:09 2007Vol:1 No:08 2007Vol:1 No:07 2007Vol:1 No:06 2007Vol:1 No:05 2007Vol:1 No:04 2007Vol:1 No:03 2007Vol:1 No:02 2007Vol:1 No:01 2007