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