Approximate Eigenvalue Decompositions of Linear Transformations with a Few Householder Reflectors
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.
Code (1)
Similar Papers 제목 키워드 기반
DeltaProduct: Improving State-Tracking in Linear RNNs via Householder Products
Linear Recurrent Neural Networks (linear RNNs) have emerged as competitive alternatives to Transformers for sequence modeling, offering efficient training and linear-time inference. However, existing architectures face a…
Language ModelingLanguage ModellingMambaFaster proximal algorithms for matrix optimization using Jacobi-based eigenvalue methods
We consider proximal splitting algorithms for convex optimization problems over matrices. A significant computational bottleneck in many of these algorithms is the need to compute a full eigenvalue or singular value deco…
CPUGPUHousE: Knowledge Graph Embedding with Householder Parameterization
The effectiveness of knowledge graph embedding (KGE) largely depends on the ability to model intrinsic relation patterns and mapping properties. However, existing approaches can only capture some of them with insufficien…
Graph EmbeddingKnowledge Graph EmbeddingRelationRelation MappingA New Approach to Multilinear Dynamical Systems and Control
The current paper presents a new approach to multilinear dynamical systems analysis and control. The approach is based upon recent developments in tensor decompositions and a newly defined algebra of circulants. In parti…
Model Approximation Using Cascade of Tree Decompositions
In this paper, we present a general, multistage framework for graphical model approximation using a cascade of models such as trees. In particular, we look at the problem of covariance matrix approximation for Gaussian d…
model