Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userButterfly-Net2: Simplified Butterfly-Net and Fourier Transform Initialization
66
0
0.0
(
0
)
Added by
Yingzhou Li
Publication date
2019
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Structured CNN designed using the prior information of problems potentially improves efficiency over conventional CNNs in various tasks in solving PDEs and inverse problems in signal processing. This paper introduces BNet2, a simplified Butterfly-Net and inline with the conventional CNN. Moreover, a Fourier transform initialization is proposed for both BNet2 and CNN with guaranteed approximation power to represent the Fourier transform operator. Experimentally, BNet2 and the Fourier transform initialization strategy are tested on various tasks, including approximating Fourier transform operator, end-to-end solvers of linear and nonlinear PDEs, and denoising and deblurring of 1D signals. On all tasks, under the same initialization, BNet2 achieves similar accuracy as CNN but has fewer parameters. And Fourier transform initialized BNet2 and CNN consistently improve the training and testing accuracy over the randomly initialized CNN.
rate research
Read More
We describe an algorithm for the application of the forward and inverse spherical harmonic transforms. It is based on a new method for rapidly computing the forward and inverse associated Legendre transforms by hierarchically applying the interpolative decomposition butterfly factorization (IDBF). Experimental evidence suggests that the total running time of our method -- including all necessary precomputations -- is $mathcal{O}(N^2 log^3(N))$, where $N$ is the order of the transform. This is nearly asymptotically optimal. Moreover, unlike existing algorithms which are asymptotically optimal or nearly so, the constant in the running time of our algorithm is small enough to make it competitive with state-of-the-art $mathcal{O}left(N^3right)$ methods at relatively small values of $N$. Numerical results are provided to demonstrate the effectiveness and numerical stability of the new framework.
Markov Chain Monte Carlo methods become increasingly popular in applied mathematics as a tool for numerical integration with respect to complex and high-dimensional distributions. However, application of MCMC methods to heavy tailed distributions and distributions with analytically intractable densities turns out to be rather problematic. In this paper, we propose a novel approach towards the use of MCMC algorithms for distributions with analytically known Fourier transforms and, in particular, heavy tailed distributions. The main idea of the proposed approach is to use MCMC methods in Fourier domain to sample from a density proportional to the absolute value of the underlying characteristic function. A subsequent application of the Parsevals formula leads to an efficient algorithm for the computation of integrals with respect to the underlying density. We show that the resulting Markov chain in Fourier domain may be geometrically ergodic even in the case of heavy tailed original distributions. We illustrate our approach by several numerical examples including multivariate elliptically contoured stable distributions.
This paper focuses on the fast evaluation of the matvec $g=Kf$ for $Kin mathbb{C}^{Ntimes N}$, which is the discretization of a multidimensional oscillatory integral transform $g(x) = int K(x,xi) f(xi)dxi$ with a kernel function $K(x,xi)=e^{2pii Phi(x,xi)}$, where $Phi(x,xi)$ is a piecewise smooth phase function with $x$ and $xi$ in $mathbb{R}^d$ for $d=2$ or $3$. A new framework is introduced to compute $Kf$ with $O(Nlog N)$ time and memory complexity in the case that only indirect access to the phase function $Phi$ is available. This framework consists of two main steps: 1) an $O(Nlog N)$ algorithm for recovering the multidimensional phase function $Phi$ from indirect access is proposed; 2) a multidimensional interpolative decomposition butterfly factorization (MIDBF) is designed to evaluate the matvec $Kf$ with an $O(Nlog N)$ complexity once $Phi$ is available. Numerical results are provided to demonstrate the effectiveness of the proposed framework.
Kernel methods are a highly effective and widely used collection of modern machine learning algorithms. A fundamental limitation of virtually all such methods are computations involving the kernel matrix that naively scale quadratically (e.g., constructing the kernel matrix and matrix-vector multiplication) or cubically (solving linear systems) with the size of the data set $N.$ We propose the Fast Kernel Transform (FKT), a general algorithm to compute matrix-vector multiplications (MVMs) for datasets in moderate dimensions with quasilinear complexity. Typically, analytically grounded fast multiplication methods require specialized development for specific kernels. In contrast, our scheme is based on auto-differentiation and automated symbolic computations that leverage the analytical structure of the underlying kernel. This allows the FKT to be easily applied to a broad class of kernels, including Gaussian, Matern, and Rational Quadratic covariance functions and physically motivated Greens functions, including those of the Laplace and Helmholtz equations. Furthermore, the FKT maintains a high, quantifiable, and controllable level of accuracy -- properties that many acceleration methods lack. We illustrate the efficacy and versatility of the FKT by providing timing and accuracy benchmarks and by applying it to scale the stochastic neighborhood embedding (t-SNE) and Gaussian processes to large real-world data sets.
The recent application of Fourier Based Iterative Reconstruction Method (FIRM) has made it possible to achieve high-quality 2D images from a fan beam Computed Tomography (CT) scan with a limited number of projections in a fast manner. The proposed methodology in this article is designed to provide 3D Radon space in linogram fashion to facilitate the use of FIRM with cone beam projections (CBP) for the reconstruction of 3D images in a low dose Cone Beam CT (CBCT).
suggested questions
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
