### Information Theory &

### Graph Signal Processing

#### Winston Ching

follow the slides at winston-ching.com

## Overview

- Crash courses on graph signal processing
- ... and on information theory
- Graph entropy as a global
*and* local measure
- GRAPH UNCERTAINTY PRINCIPLE!
- Applications and future work

### What is Graph Signal Processing?

What's wrong with discrete time signal processing?

- Only works on regular domains
- Dichotomy: functional vs probabilistic
- Understand jokes like "Fourier only plays with his imaginary friend." "Don't worry - it's just a phase."

## GSP 101

Graph Fourier transform

== Jordan decomposition?

Classical discrete time signal

Cycle graph

## IT 101

We are running short on time

Uniform distribution → high entropy

Gaussian distribution → lower entropy

## Graph Entropy (Motivation)

- A relaxed prefix-free coding problem
- Each vertex represents a symbol in the alphabet
- Two vertices are distinguishable iff there exists a path from one to another
- (Signal persepctive: whether or not one node can influence another)

## Graph Entropy (Definition 2)

NP to compute!

## Graph Entropy (Definition 3)

- X is over vertices of G
- Y is over power set of the vertices of G
- X ~
**p**
- P(X ∈ Y) = 1

## Key Results

## PTIME Graph Entropy

- Separate graph into connected components
- For each connected component, find strongly connected components.
- Take the determinant of the cofactor of each vertex of the root strongly connected component.
- Compute entropy of each connected component
- Sum to get overall entropy

## PTIME Graph Entropy

## Graph Uncertainty Principle

## Potential Applications

- Better network design
- Better filter bank design
- Signal recovery from nodal frequency observation
- Finding the counterpart of Gaussian distribution in other graphs
- Generalizing the connection between Hilbert space and signal processing

That was a lot of information at a time.

Here's a fluffy dog.

Good luck with finals :)