Waveformer: Linear-Time Attention with Forward and Backward Wavelet Transform. (arXiv:2210.01989v1 [cs.CL])

We propose Waveformer that learns attention mechanism in the wavelet
coefficient space, requires only linear time complexity, and enjoys universal
approximating power. Specifically, we first apply forward wavelet transform to
project the input sequences to multi-resolution orthogonal wavelet bases, then
conduct nonlinear transformations (in this case, a random feature kernel) in
the wavelet coefficient space, and finally reconstruct the representation in
input space via backward wavelet transform. We note that other non-linear
transformations may be used, hence we name the …

arxiv attention linear wavelet