Search

MiS Preprint Repository

Delve into the future of research at MiS with our preprint repository. Our scientists are making groundbreaking discoveries and sharing their latest findings before they are published. Explore repository to stay up-to-date on the newest developments and breakthroughs.

MiS Preprint
103/2013

Superfast Wavelet Transform Using QTT Approximation. I: Haar Wavelets

Boris N. Khoromskij and Sentao Miao

Abstract

We propose a superfast discrete Haar wavelet transform (SFHWT) as well as its inverse, using the QTT representation for the Haar transform matrices and input-output vectors. Though the Haar matrix itself does not have a low QTT-rank approximation, we show that factor matrices used at each step of the traditional multilevel Haar wavelet transform algorithm have explicit QTT representations of low rank. The SFHWT applies to a vector representing a signal sampled on a uniform grid of size $N=2^{d}$. We develop two algorithms which roughly require square logarithmic time complexity with respect to the grid size, $O(\log^2 N)$, hence outperforming the traditional fast Haar wavelet transform (FHWT) of linear complexity, $O(N)$. Our approach also applies to the FHWT inverse as well as to the multidimensional wavelet transform. Numerical experiments demonstrate that the SFHWT algorithm is robust in keeping low rank of the resulting output vector and it outperforms the traditional FHWT for grid size larger than a certain value depending on the spacial dimension.

Received:
Nov 14, 2013
Published:
Nov 19, 2013
MSC Codes:
65F30, 65F50, 65N35, 65F10
Keywords:
tensor-structured methods, fast wavelet transform, canonical tensor decomposition, quantized tensor approximation (QTT), data compression, multilevel methods

Related publications

inJournal
2014 Repository Open Access
Boris N. Khoromskij and Sentao Miao

Superfast wavelet transform using quantics-TT approximation 1. : application to haar wavelets

In: Computational methods in applied mathematics, 14 (2014) 4, pp. 537-553