Node Sampling by Partitioning on Graphs via Convex Optimization

C. Rusu; J. Thompson

doi:10.1109/SSPD.2017.8233246

Node Sampling by Partitioning on Graphs via Convex Optimization

C. Rusu, J. Thompson

School of Engineering

Research output: Chapter in Book/Report/Conference proceeding › Conference 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 language	Undefined/Unknown
Title of host publication	2017 Sensor Signal Processing for Defence Conference (SSPD)
Pages	1-5
Number of pages	5
DOIs	https://doi.org/10.1109/SSPD.2017.8233246
Publication status	Published - 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

Access to Document

10.1109/SSPD.2017.8233246

Signal Processing in the Networked Battlespace
Mulgrew, B., Davies, M., Hopgood, J. & Thompson, J.
EPSRC
1/04/13 → 30/06/18
Project: Research

Cite this

@inproceedings{9ebf3fbdce1343859ac85582a56b2d6b,

title = "Node Sampling by Partitioning on Graphs via Convex Optimization",

abstract = "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.",

keywords = "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",

author = "C. Rusu and J. Thompson",

year = "2017",

month = dec,

day = "1",

doi = "10.1109/SSPD.2017.8233246",

language = "Undefined/Unknown",

pages = "1--5",

booktitle = "2017 Sensor Signal Processing for Defence Conference (SSPD)",

}

TY - GEN

T1 - Node Sampling by Partitioning on Graphs via Convex Optimization

AU - Rusu, C.

AU - Thompson, J.

PY - 2017/12/1

Y1 - 2017/12/1

N2 - 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.

AB - 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.

KW - graph theory

KW - mean square error methods

KW - optimisation

KW - signal reconstruction

KW - signal sampling

KW - complete graph signal reconstruction

KW - convex optimization techniques

KW - graph partitioning

KW - graph structure

KW - low mean squared error

KW - node sampling

KW - numerical simulation

KW - partially observed noisy measurements

KW - positioning problem

KW - real-world graphs

KW - sampling set construction approach

KW - selection problem

KW - sensor management

KW - synthetic graphs

KW - Convex functions

KW - Laplace equations

KW - Noise measurement

KW - Optimization

KW - Partitioning algorithms

KW - Signal processing

KW - Symmetric matrices

U2 - 10.1109/SSPD.2017.8233246

DO - 10.1109/SSPD.2017.8233246

M3 - Conference contribution

SP - 1

EP - 5

BT - 2017 Sensor Signal Processing for Defence Conference (SSPD)

ER -

Node Sampling by Partitioning on Graphs via Convex Optimization

Abstract / Description of output

Keywords / Materials (for Non-textual outputs)

Access to Document

Projects

Signal Processing in the Networked Battlespace

Cite this