论文标题
关于从子次采样点点的值重建函数
On the reconstruction of functions from values at subsampled quadrature points
论文作者
论文摘要
本文涉及样品重建功能。几种方法中使用的采样点是（1）与快速算法连接的结构化点，或（2）来自的非结构化点来自，例如，初始随机绘制以实现改进的信息复杂性。我们将两种方法连接起来，并在离线步骤中提出结构化点的子采样。特别是，我们从结构化正交点（QMC）开始，该点提供稳定的$ L_2 $重建属性。子采样过程由计算廉价的随机步骤组成，然后是确定性程序，以进一步减少点数，同时保留其信息。在这些点函数中（属于有界函数的RKHS）将从实现最新误差衰减状态的同时进行采样和重建。我们的方法是无关的，一旦我们知道一些初始正交点，就适用。我们将一般发现在$ d $维圆环上应用于子样本级别-1晶格，在那里众所周知，完整的Rank-1 Lattices失去了一半的最佳收敛顺序（以晶格的大小表示）。与此相反，由于不需要许多晶格点，因此我们的子采样版本恢复了最佳速度。此外，我们利用快速和内存有效的傅立叶算法来计算近似值。几个维度的数值实验支持我们的发现。
This paper is concerned with function reconstruction from samples. The sampling points used in several approaches are (1) structured points connected with fast algorithms or (2) unstructured points coming from, e.g., an initial random draw to achieve an improved information complexity. We connect both approaches and propose a subsampling of structured points in an offline step. In particular, we start with structured quadrature points (QMC), which provide stable $L_2$ reconstruction properties. The subsampling procedure consists of a computationally inexpensive random step followed by a deterministic procedure to further reduce the number of points while keeping its information. In these points functions (belonging to a RKHS of bounded functions) will be sampled and reconstructed from whilst achieving state of the art error decay. Our method is dimension-independent and is applicable as soon as we know some initial quadrature points. We apply our general findings on the $d$-dimensional torus to subsample rank-1 lattices, where it is known that full rank-1 lattices lose half the optimal order of convergence (expressed in terms of the size of the lattice). In contrast to that, our subsampled version regains the optimal rate since many of the lattice points are not needed. Moreover, we utilize fast and memory efficient Fourier algorithms in order to compute the approximation. Numerical experiments in several dimensions support our findings.
