Layered-givens transforms: Tunable complexity, high-performance approximation of optimal non-separable transforms

We introduce layered-Givens transforms (LGTs) which are arbitrary-dimensional, tunable-complexity, orthonormal transforms of data. LGTs are formed by layers of data permutations and Givens rotations with the number of layers controlling the overall transform's computational complexity. We propo...

Full description

Saved in:
Bibliographic Details
Main Authors: Li, Bohan, Guleryuz, Onur G., Ehmann, Jana, Vosoughi, Arash
Format: Conference Proceeding
Language:English
Subjects:
Annealing
Approximation algorithms
Blossom algorithm
Computational complexity
Hardware
Hungarian method
layered-Givens transforms
Optimization
row-column transforms
Transforms
video compression
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We introduce layered-Givens transforms (LGTs) which are arbitrary-dimensional, tunable-complexity, orthonormal transforms of data. LGTs are formed by layers of data permutations and Givens rotations with the number of layers controlling the overall transform's computational complexity. We propose a novel method for the design of layered-Givens transforms that approximate desired complex transforms (such as KLTs, SOTs, etc.) so that most of the performance of the approximated transform is retained at significantly reduced complexity. Key to the LGT performance is the choice of the permutations that arrange the data prior to the Givens rotations. Despite the very highly combinatorial nature of the LGT design problem, we provide an algorithm that finds the optimal parameters (permutation and Givens rotations) for each layer. Our results show that designed LGTs closely approximate desired non-separable transforms at significantly reduced complexity.
ISSN:2381-8549
DOI:10.1109/ICIP.2017.8296569