  The ability to decompose a signal in an orthonormal basis (a set of
orthogonal components, each normalized to have unit length) using a fast
numerical procedure rests at the heart of many signal processing methods and
applications. The classic examples are the Fourier and wavelet transforms that
enjoy numerically efficient implementations (FFT and FWT, respectively).
Unfortunately, orthonormal transformations are in general unstructured, and
therefore they do not enjoy low computational complexity properties. In this
paper, based on Householder reflectors, we introduce a class of orthonormal
matrices that are numerically efficient to manipulate: we control the
complexity of matrix-vector multiplications with these matrices using a given
parameter. We provide numerical algorithms that approximate any orthonormal or
symmetric transform with a new orthonormal or symmetric structure made up of
products of a given number of Householder reflectors. We show analyses and
numerical evidence to highlight the accuracy of the proposed approximations and
provide an application to the case of learning fast Mahanalobis distance metric
transformations.
