Charles A. Micchelli, Yuesheng Xu, Bo Yu
Abstract: We develop a fast algorithm for computing the Hilbert transform of a function from a data set consisting of n function values and prove that the complexity of the proposed algorithm is O(n log n). Our point of view is fundamentally based on a B-spline series approximation constructed from available data. In this regard, we obtain new formulas for the Hilbert transform of a B-spline as a divided difference. For theoretical simplicity and computational efficiency we give a detailed description of our algorithm, as well as provided optimal approximation order, only in the case of quadratic splines. However, if higher accuracy is required, extensions of our method to spline approximation of any prescribed degree readily follows the pattern of the quadratic case. Numerical experiments have confirmed that our algorithm has superior performance than previously available methods which we briefly survey in Section 2.
Journal: Adv. Comput. Math. 38 (2013), no. 3, 623–646
DOI: 10.1007/s10444-011-9252-x