2020/04/07 by Vincent Coppé, Coppé, Vincent, Daan Huybrechs +1
Computer Science · Engineering · #65D15 #65T60 #65Y20 #Digital Filter Design and Implementation #FOS: Mathematics #Image and Signal Denoising Methods #Numerical Analysis (math.NA) #Numerical Methods and Algorithms #Reservoir Engineering and Simulation Methods
paper · pdf · doi:10.48550/arxiv.2004.03537
openalex publication_date 2020/04/07 · openalex created_date 2022/07/26 · openalex updated_date 2026/07/28
Fourier extension is an approximation method that alleviates the periodicity\nrequirements of Fourier series and avoids the Gibbs phenomenon when\napproximating functions. We describe a similar extension approach using regular\nwavelet bases on a hypercube to approximate functions on subsets of that cube.\nThese subsets may have a general shape. This construction is inherently\nassociated with redundancy which leads to severe ill-conditioning, but recent\ntheory shows that nevertheless high accuracy and numerical stability can be\nachieved using regularization and oversampling. Regularized least squares\nsolvers, such as the truncated singular value decomposition, that are suited to\nsolve the resulting ill-conditioned and skinny linear system generally have\ncubic computational cost. We compare several algorithms that improve on this\ncomplexity. The improvements benefit from the sparsity in and the structure of\nthe discrete wavelet transform. We present a method that requires mathcal\nO(N) operations in 1-D and mathcal O(N3(d-1)/d) in d-D, d>1. We\nexperimentally show that direct sparse QR solvers appear to be more\ntime-efficient, but yield larger expansion coefficients.\n