Multiple rank-1 lattices as sampling schemes for multivariate trigonometric polynomials (Q1704862)

This paper deals with the evaluation of a multivariate trigonometric polynomial \[ p:\mathbb{T}^d\rightarrow \mathbb{C}, \mathbf x\mapsto \sum_{k\in I} \hat p_{\mathbf k} e^{2\pi i \mathbf k\cdot \mathbf x} \] using multiple rank-1 lattices. When \(\mathbf x\in \mathcal{X}\subset \mathbb{T}^d\) is in a rank-1 lattice \(\mathcal{X} = \{\frac{j}{M} z: j=0,\ldots, M-1\}\) for some \(z\in\mathbb{Z}^d\) and \(M\in \mathbb{N}\), the above evaluation of \(p(x), x\in \mathcal{X}\) can be simply computed by 1D-FFT. The main disvantage of using a single rank-1 lattice is the oversampling issue where \(M\) increases significantly with respect to the cardinality of the frequency index set \(I\). To overcome this problem, in this paper, the authors propose the use of multiple rank-1 lattices: \[ \mathcal{X} = \{\frac{j}{M_1}z_1 : j = 0,\ldots, M_1-1\}\cup \cdots\cup \{\frac{j}{M_s} z_s: j=0,\ldots, M_s-1\} \] for \(z_1,\ldots,z_s\in\mathbb{Z}^d\) and pairwise coprime integers \(M_1,\ldots,M_s\in\mathbb{N}\). The evaluation of \(p\) on such a \(\mathcal{X}\) is simply multiple applications of 1D-FFTs. The paper then studies the reconstruction properties of the multiple rank-1 lattices and propose an algorithm to determine the reconstructing multiple rank-1 lattices for arbitrary frequencey index set \(I\). Numerical experiments are conducted to demonstrate the proposed algorithm in comparison with the sparse grid method and single rank-1 lattice.