Definition and basic properties¶
(Note that this definition differs from the one in the linked article by the placement of the factor .) By unique continuation, the bounded FT operator can be extended to for , yielding a mapping
where is the conjugate exponent of (for one sets ). Finite exponents larger than 2 also allow the extension of the operator but require the notion of Distributions to characterize its range. See [SW1971] for further details.
The inverse of on its range is given by the formula
For , the conjugate exponent is , and the FT is a unitary operator on according to Parseval’s Identity
which implies that its adjoint is its inverse, .
The first identity implies in particular that for real-valued , it is , i.e. the FT is completely known already from the its values in a half-space only. This property is later exploited to reduce storage.
In dimensions, the FT is defined as
with the usual inner product in . The identities (3) also hold in this case with obvious modifications.
Discretized Fourier Transform¶
The approach taken in ODL for the discretization of the FT follows immediately from the way Discretizations are defined, but the original inspiration for it came from the book [Pre+2007], Section 13.9 “Computing Fourier Integrals Using the FFT”.
Discretization of the Fourier transform operator means evaluating the Fourier integral (1) on a discretized function
with coefficients and functions . This approach follows from the way , but can be We consider in particular functions generated from a single kernel via
where are sampling points and scaling factors. Using the shift and scaling properties in (3) yields
There exist methods for the fast approximation of such sums for a general choice of frequency samples , e.g. NFFT.
For regular grids
Hence, the Fourier integral evaluation can be built around established libraries with simple pre- and post-processing steps.
With regular grids, the discretized integral (5) evaluated at , can be expanded to
To reach the form (7), the factor depending on both indices and must agree with the corresponding factor in the FFT sum. This is achieved by setting
finally yielding the representation
Choice of ¶
There is a certain degree of freedom in the choice of the most negative frequency . Usually one wants to center the Fourier space grid around zero since most information is typically concentrated there. Point-symmetric grids are the standard choice, however sometimes one explicitly wants to include (for even ) or exclude (for odd ) the zero frequency from the grid, which is achieved by shifting the frequency by . This results in two possible choices
For the shifted frequency, the pre-processing factor in the sum in (9) can be simplified to
which is favorable for real-valued input since this first operation preserves this property. For half-complex transforms, shifting is required.
The factor ¶
In (9), the FT of the kernel appears as post-processing factor. We give the explicit formulas for the two standard discretizations currently used in ODL, which are nearest neighbor interpolation
and linear interpolation
Their Fourier transforms are given by
Since their arguments lie between and , these functions introduce only a slight taper towards higher frequencies given the fact that the first zeros lie at .
According to (2), the inverse of the continuous Fourier transform is given by
the same formula as the forward transform (1), except for a switched sign in the
complex exponential. Hence, this operator can rather be viewed as a variation of the forward FT,
and it is implemented via a
sign parameter in
The inverse of the discretized formula (9) is instead gained directly using the identity
By dividing (9) with the factor
before the sum, multiplying with the exponential factor and summing over , the coefficients can be recovered:
Hence, the inversion formula for the discretized FT reads as
which can be calculated in the same manner as the forward FT, basically by switching the roles of pre- and post-processing steps and flipping the sign in the complex exponentials.
If the FT is defined between the complex Hilbert spaces , one can easily show that the operator is unitary, and therefore its adjoint is equal to the inverse.
However, if the domain is a real space, , one cannot even speak of a linear operator since the property
cannot be tested for all as required by the right-hand side, since on the left-hand side, needs to be real. This issue can be remedied by identifying the real and imaginary parts in the range with components of a product space element:
where and are the sine and cosine transforms, respectively. Those two operators are self-adjoint between real Hilbert spaces, and thus the adjoint of the above defined transform is given by
If we compare this result to the “naive” approach of taking the real part of the inverse of the complex inverse transform, we get
Hence, by identifying and , we see that the result is the same. Therefore, using the naive approach for the adjoint operator is justified by this argument.