Approximate Eigenvalue Decompositions of Linear Transformations with a Few Householder Reflectors
This work addresses the computational inefficiency of general orthonormal transformations in signal processing, offering a method to approximate them with low complexity, which is incremental as it builds on existing Householder reflector techniques.
The paper tackles the problem of approximating orthonormal or symmetric linear transformations with numerically efficient structures using Householder reflectors, achieving controlled complexity in matrix-vector multiplications and demonstrating accuracy through analyses and applications like fast Mahanalobis distance metric learning.
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.