Fast scattered data approximation with Neumann and other boundary conditions
Fast scattered data approximation with Neumann and other boundary conditions
复制标题
使用诺依曼和其他边界条件进行快速离散数据近似
DOI：
10.1016/j.laa.2003.09.017
复制
发表时间：
2004
影响因子：
1.1
通讯作者：
T. Strohmer
中科院分区：
文献类型：
--
作者：
D. Grishin;T. Strohmer
信号和图像处理等应用中的一个重要问题是从随机分散数据的有限集合f（xj）中逼近函数f。一种常见且强大的方法是基于指数集{e2πikx}构造三角最小二乘近似。这导致了快速的数值算法，但由于在实践中很少满足的数据上的潜在周期性假设而受到干扰边界效应的影响。为了克服这个缺点，我们施加诺依曼边界条件的数据。这意味着使用余弦多项式cos（πkx）作为基函数。我们表明，使用余弦多项式导致涉及某些Toeplitz加汉克尔矩阵的最小二乘问题，并得出这些矩阵的条件数的估计。与其他Toeplitz-plus-Hankel矩阵不同，这些矩阵不能通过离散余弦变换（DCT）对角化，但它们仍然允许通过DCT进行快速矩阵向量相乘，从而产生快速共轭梯度型算法。我们展示了如何将结果推广到更高的维度。我们还考虑反对称边界条件，导致正弦多项式作为适当的三角基。最后，我们证明了所提出的方法的性能的应用程序的二维地球物理散射数据问题。
An important problem in applications, such as signal and image procesing, is the approximation of a function f from a finite set of randomly scattered data f(xj). A common and powerful approach is to construct a trigonometric least squares approximation based on the set of exponentials {e2πikx}. This leads to fast numerical algorithms, but suffers from disturbing boundary effects due to the underlying periodicity assumption on the data which is rarely satisfied in practice. To overcome this drawback we impose Neumann boundary conditions on the data. This implies the use of cosine polynomials cos(πkx) as basis functions. We show that using cosine polynomials leads to a least squares problem involving certain Toeplitz-plus-Hankel matrices and derive estimates on the condition number of these matrices. Unlike other Toeplitz-plus-Hankel matrices, these matrices cannot be diagonalized by the discrete cosine transform (DCT), but they still allow a fast matrix–vector multiplication via DCT which gives rise to fast conjugate gradient type algorithms. We show how the results can be generalized to higher dimensions. We also consider anti-symmetric boundary conditions, leading to sine polynomials as proper trigonometric basis. Finally we demonstrate the performance of the proposed methods by an application to a two-dimensional geophysical scattered data problem.