Recursive Nearest Agglomeration (ReNA): Fast Clustering for Approximation of Structured Signals

In this work, we revisit fast dimension reduction approaches, as with random projections and random sampling. Our goal is to summarize the data to decrease computational costs and memory footprint of subsequent analysis. Such dimension reduction can be very efficient when the signals of interest hav...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on pattern analysis and machine intelligence 2019-03, Vol.41 (3), p.669-681
Main Authors: Hoyos-Idrobo, Andres, Varoquaux, Gael, Kahn, Jonas, Thirion, Bertrand
Format: Article
Language:English
Subjects:
Agglomeration
Approximation
Approximation algorithms
classification
Clustering
Clustering algorithms
Complexity theory
Computer memory
Computer Science
Computing time
Cost analysis
Data reduction
Dimensionality reduction
Feature extraction
Image Processing
Kernel
Machine Learning
Mathematical analysis
matrix sketching
Medical Imaging
neuroimaging
Noise reduction
Random sampling
Regression analysis
Signal and Image Processing
Signal processing algorithms
Statistics
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In this work, we revisit fast dimension reduction approaches, as with random projections and random sampling. Our goal is to summarize the data to decrease computational costs and memory footprint of subsequent analysis. Such dimension reduction can be very efficient when the signals of interest have a strong structure, such as with images. We focus on this setting and investigate feature clustering schemes for data reductions that capture this structure. An impediment to fast dimension reduction is then that good clustering comes with large algorithmic costs. We address it by contributing a linear-time agglomerative clustering scheme, Recursive Nearest Agglomeration (ReNA). Unlike existing fast agglomerative schemes, it avoids the creation of giant clusters. We empirically validate that it approximates the data as well as traditional variance-minimizing clustering schemes that have a quadratic complexity. In addition, we analyze signal approximation with feature clustering and show that it can remove noise, improving subsequent analysis steps. As a consequence, data reduction by clustering features with ReNA yields very fast and accurate models, enabling to process large datasets on budget. Our theoretical analysis is backed by extensive experiments on publicly-available data that illustrate the computation efficiency and the denoising properties of the resulting dimension reduction scheme.
ISSN:0162-8828
1939-3539
2160-9292
DOI:10.1109/TPAMI.2018.2815524