Node Sampling by Partitioning on Graphs via Convex Optimization

C. Rusu, J. Thompson

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

Abstract / Description of output

In this paper we deal with the problem of efficiently and accurately reconstructing a complete graph signal from partially observed noisy measurements. Given a graph structure, we propose a solution based on convex optimization techniques to partition the nodes of the graph into subsets such that sampling a graph signal from any of these subsets provides an accurate, low mean squared error for example, reconstruction of the original complete graph signal. We show how the proposed sampling set construction approach relates to optimal experimental design, sensor management, positioning and selection problems and provide numerical simulation results on synthetic and real-world graphs.
Original languageUndefined/Unknown
Title of host publication2017 Sensor Signal Processing for Defence Conference (SSPD)
Number of pages5
Publication statusPublished - 1 Dec 2017

Keywords / Materials (for Non-textual outputs)

  • graph theory
  • mean square error methods
  • optimisation
  • signal reconstruction
  • signal sampling
  • complete graph signal reconstruction
  • convex optimization techniques
  • graph partitioning
  • graph structure
  • low mean squared error
  • node sampling
  • numerical simulation
  • partially observed noisy measurements
  • positioning problem
  • real-world graphs
  • sampling set construction approach
  • selection problem
  • sensor management
  • synthetic graphs
  • Convex functions
  • Laplace equations
  • Noise measurement
  • Optimization
  • Partitioning algorithms
  • Signal processing
  • Symmetric matrices

Cite this