Fast 'tail-greedy' bottom-up decomposition algorithms for signals on graphs and network adjacency matrices 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.