On the stability of the hyperbolic cross discrete Fourier transform (Q629898)

A straightforward discretisation of problems in \(d\) spatial dimensions with \(2^n\) grid points in each coordinate leads to an exponential growth \(2^{dn}\) in the number of degrees of freedom. For moderately high dimensional problems, sparse grid approximations allow for a severe decrease in the number of used Fourier coefficients to represent 1-periodic functions with bounded mixed derivatives. In this paper, the authors estimate the condition number of the modified Fourier matrix \[ F_n^d = (\exp(2\pi i \, k\cdot x))_{ x\in S_n^d,\, k \in H_n^d} \] for increasing refinement \(n\in \mathbb N\) and \(d\geq 2\). Here \(S_n^d\) denotes the sparse grid of \([0,1)^d\) and \(H_n^d\) is the hyperbolic cross in the frequency domain \( {\mathbb Z}^d\). Using a Boolean sum decomposition of \(( F_n^d )^{-1}\), lower and upper estimates of \(\| F_n^d \|_2\) and \(\|(F_n^d )^{-1}\|_2\) for fixed dimension \(d\) and variable \(n \geq d\) are presented such that the condition number of \(F_n^d \) scales approximately like \(|H_n^d|^{1/2}\). For fixed refinement \(n\) and variable \(d\geq n\), the spectral norms of \( F_n^d \) and \((F_n^d )^{-1}\) are estimated too. In this case, the condition number of \(F_n^d \) scales approximately like \(|H_n^d|^2\). These results are refined for \(d=2\) and \(n=1\), respectively. All results are illustrated by numerical experiments.