Sampling large data on graphs

Han Shomorony, A. Salman Avestimehr

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We consider the problem of sampling from data defined on the nodes of a weighted graph, where the edge weights capture the data correlation structure. As shown recently, using spectral graph theory one can define a cut-off frequency for the bandlimited graph signals that can be reconstructed from a given set of samples (i.e., graph nodes). In this work, we show how this cut-off frequency can be computed exactly. Using this characterization, we provide efficient algorithms for finding the subset of nodes of a given size with the largest cut-off frequency and for finding the smallest subset of nodes with a given cut-off frequency. In addition, we study the performance of random uniform sampling when compared to the centralized optimal sampling provided by the proposed algorithms.

Original languageEnglish (US)
Title of host publication2014 IEEE Global Conference on Signal and Information Processing, GlobalSIP 2014
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages933-936
Number of pages4
ISBN (Electronic)9781479970889
DOIs
StatePublished - Feb 5 2014
Externally publishedYes
Event2014 IEEE Global Conference on Signal and Information Processing, GlobalSIP 2014 - Atlanta, United States
Duration: Dec 3 2014Dec 5 2014

Publication series

Name2014 IEEE Global Conference on Signal and Information Processing, GlobalSIP 2014

Other

Other2014 IEEE Global Conference on Signal and Information Processing, GlobalSIP 2014
CountryUnited States
CityAtlanta
Period12/3/1412/5/14

Keywords

  • Cut-off frequency
  • Graph signal processing
  • Sampling
  • Spectral graph theory

ASJC Scopus subject areas

  • Signal Processing
  • Information Systems

Fingerprint Dive into the research topics of 'Sampling large data on graphs'. Together they form a unique fingerprint.

Cite this