Skip to main navigationSkip to main content
The University of Southampton
Southampton Statistical Sciences Research Institute

Fast 'tail-greedy' bottom-up decomposition algorithms for signals on graphs and network adjacency matrices Seminar

Time:
14:30
Date:
12 May 2016
Venue:
54/5027

Event details

S3RI seminar

Abstract: We propose a generic class of algorithms for decomposing data whose domain has a notion of neighbourhood: this includes 1-d signals, images and network adjacency matrices. Although they differ in details, all algorithms include the following components: in each consecutive pass through data, a fixed proportion of pairs of adjacent domain regions get fused. The suitably normalised difference in data values between each pair of fused regions gets recorded as a 'detail' coefficient, and each parent region obtains a new data value which is representative of those of its children. The pairs of regions selected for fusing are those whose absolute detail coefficients lie in the lower tail of their empirical distribution - hence the name 'tail-greedy'. The tail-greediness ensures computational efficiency, and the resulting decomposition is orthonormal conditionally on the order of fusings.

We show two applications of the new class of transforms: one to multiple change-point detection in 1-d, where the 'tail-greediness' is a key component of the method that ensures its consistency, and to obtaining decompositions of network adjacency matrices which help understand their community structure.

From a broader perspective, this talk will encourage 'object-oriented' thinking in data analytics, as well as the idea of viewing estimators as algorithms.

Speaker information

Piotr Fryzlewicz , London School of Economics. . Professor of Statistics in the Department of Statistics

Privacy Settings