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. We apply our general findings on the $d$-dimensional torus to subsample rank-1 lattices, where it is known that full rank-1 lattices loose 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 higher dimensions support our findings.
翻译:本文涉及从样本中重建功能。 几个方法中使用的抽样点是:(1) 结构化点,与快速算法或(2) 结构化点相关联, 结构化点来自快速算法或(2) 结构化点, 例如, 初步随机抽取, 以达到更好的信息复杂性。 我们将两种方法连接起来, 并在离线步骤中提出结构化点的子抽样。 特别是, 我们从结构化的二次点( QMC) 开始, 提供稳定的 $_ 2美元重建属性。 次级抽取程序包括计算成本低廉的随机步骤, 辅之以一种确定程序, 以进一步减少点数量, 并保存信息。 在这些点( 与受约束功能的 RKHS 相连接的) 函数中, 将抽样和重新构建。 我们把关于美元面对结构化点的一般调查结果应用到亚模1 级 级的子点( QMC ), 在那里, 众所周知, 整级 1 低级半 最优化的顺序( 以拉蒂斯大小表示 ) 。 与此相反, 我们的次抽样版本将恢复了 最优化的 水平 。