Re: Re: Generalized Fourier localization theorem?
- To: mathgroup at smc.vnet.net
- Subject: [mg102557] Re: [mg102528] Re: Generalized Fourier localization theorem?
- From: danl at wolfram.com
- Date: Thu, 13 Aug 2009 03:23:11 -0400 (EDT)
- References: <200908092219.SAA09118@smc.vnet.net> <h5r8fk$l9g$1@smc.vnet.net>
> In article <h5r8fk$l9g$1 at smc.vnet.net>, danl at wolfram.com wrote:
>
>> > Suppose a complex-valued function f[x] with x real, has a region
>> of
>> > finite width within the range -Infinity < x < +Infinity where the
>> > function f[x] is identically zero.
>> >
>> > Does this imply that its Fourier transform g[s] with s real can
>> > _not_ have any such region of finite width where g[s] is identically
>> > zero within its similar domain?
>> >
>> > Similar theorem for the Fourier series of a periodic function?
>> >
>> > Thanks for any pointers.
>>
>> No to the first. A Dirac comb has infinitely many such regions, and it's
>> FT is also a Dirac comb.
>>
>> In[1]:= FourierTransform[DiracComb[x], x, t]
>> Out[1]= DiracComb[-(t/(2 \[Pi]))]/Sqrt[2 \[Pi]]
>
> Good point!! -- although I should have realized that "I already knew
> that!" This is what Ron Bracewell used to call the "shah function".
> Thank you, Daniel.
[Right, because it resembles the markings on the older Persion rulers...]
> In case you have any interest in the DFT version of the original
> question, appended below is part of the Introduction to a notebook I
> wrote some years ago and recently revisited. The key content from a
> mathematical viewpoint is in the first three paragraphs. This was done
> mostly for curiosity-driven reasons, as an offshoot from some work on
> rigorous uncertainty principles for periodic functions. If there is
> some more serious mathematics associated with this topic, I'd be glad to
> hear about it -- even though if it gets too serious, it will be over my
> head.
Nothing worse than linear algebra.
> ====================================================
>
> "Brad Osgood once raised the question with me as to whether some close
> analog of this localization principle also applies to Discrete Fourier
> Transforms (DFTs) specifically if an N-term periodic sequence f_n
> has two or more contiguous zero elements, is its DFT g_m barred from
> also having two or more contiguous zeros?
>
> This notebook shows that this is not the case: One can find N-term DFT
> pairs both of which have a string of contiguous zero values over
> approximately half of their widths. To demonstrate this point
> experimentally, this notebook presents three methods of obtaining such
> sequences:
>
> 1) In the first method, a discrete sequence f_n of periodic length N
> is assumed to have the uppermost (N/2) - 1 of its contiguous elements
> set equal to zero. The remaining (N/2) + 1 elements are then used to
> set up N coupled linear equations which express the uppermost N
> elements of the DFT sequence g_m = DFT[f_n] as a linear superposition
> of the (N/2) + 1 lower elements of f . Setting these N equations to
> zero then allows one to solve for the elements of the f array from
> f[1] up to f[N/2] in terms of f[0].
>
> Carrying through on this procedure indeed leads to a unique, finite,
> more or less gaussian-like "maximum localization" result as shown below,
> yielding a gaussian-like sequence f with (N/2) -1 contiguous zero
> elements and a gaussian-like sequence g with N/2 contiguous elements
> that are both bounded and are DFTs of each other. Ergo, discrete
> sequences can be simultaneously bounded, or "localized", at least to the
> extent demonstrated here. This calculation method slows down rapidly
> for N larger than about 16.
>
> 2) Examining the results of this approach shows that they can be
> shifted into a simple form, in which the sequence g_m can be made
> purely real and symmetric about the "m = -1/2" element of the array, and
> the sequence f_n then consists of complex conjugate values centered
> about the DC or n=0 value, with a small and apparently totally linear
> phase shift associated with the half-period offset of the g_m array.
>
> This leads to a somewhat simpler approach in which the same array
> coefficients can be solved by inverting an N/4-th order real matrix,
> although this matrix apparently becomes seriously ill-conditioned as the
> order N increases.
>
> 3) Motivated by the Fox and Li approach to optical resonator modes, I
> also implement an ad hoc approach in which an iterative process of
> transforming between the sequences and then filtering them is used to
> try to force the sequences to converge to minimum localization.
> Experimentally this approach also converges, at least for not too large
> values of N , although it seems to fail to converge (perhaps as a
> result of numerical underflow) at values of N greater than 64 or so.
>
> Each of these approaches is demonstrated below, using a common set of
> display modules for the results (For simplicity these are all programmed
> only for values of N = integer multiples of 4.). These calculations
> were initially carried out by AES during May-June 2003; updated and
> extended in June 2004; and cleaned up a bit for the latest version 7 of
> Mathematica in August 2009."
>
Say we want to consider a sequence of length n. You can specify up to n-1
components of signal and its discrete Fourier transform, in total, to be
zero. It does not matter where you put the zeros, and in particular they
can be contiguous.
This is just a matter of linear algebra, more or less as noticed above. If
we attempt to fix n zeros total, we get the trivial solution where signal
and FT are identically 0. No surprise here, because then we have, in
effect, a homogeneous linear system with a square matrix of full rank.
Here is a bit of code to work out solution sets numerically.
dftMatrix[n_] :=
Table[Exp[2*Pi*I*j*k/n], {k, 0, n - 1}, {j, 0, n - 1}]
fixZeros[in_List, ft_List, n_Integer] := Module[
{ftmat = N[dftMatrix[n]], x, w, xvars, wvars},
xvars = Array[x, n];
wvars = Array[w, n];
Map[(x[#] = 0) &, in];
Map[(w[#] = 0) &, ft];
Quiet[Chop[{xvars, wvars} /.
Solve[ftmat.xvars == wvars, Variables[Join[xvars, wvars]]]]]
]
Example: we will look for signal/FT pairs of length 12, where the first
seven elements of signal, and middle four of the FT, are all specified as
zero.
In[20]:= fixZeros[Range[7], Range[5, 8], 12]
Out[20]= {{{0, 0, 0, 0, 0, 0,
0, (0.5 - 0.866025 I) x$545[12], (2.36603 - 2.36603 I) x$545[
12], (4.09808 - 2.36603 I) x$545[
12], (3.23205 - 0.866025 I) x$545[12],
x$545[12]}, {(11.1962 - 6.4641 I) x$545[
12], (-4.73205 - 8.19615 I) x$545[
12], (-4.09808 + 2.36603 I) x$545[
12], (0.633975 + 1.09808 I) x$545[12], 0, 0, 0,
0, (1.09808 - 0.633975 I) x$545[12], (-2.36603 - 4.09808 I) x$545[
12], (-8.19615 + 4.73205 I) x$545[
12], (6.4641 + 11.1962 I) x$545[12]}}}
Obviously this idea generalizes to nonzero values. The code above can be
altered without much fuss to pin down up to n-1 elements at values other
than zero.
Daniel Lichtblau
Wolfram Research
- References:
- Generalized Fourier localization theorem?
- From: AES <siegman@stanford.edu>
- Generalized Fourier localization theorem?