Estimating time domain peakedness from frequency domain information

I have a unique problem where I need to predict the "peakedness" of the
time domain signal just by looking at the frequency transform of the
signal.
Let us call this as y1[n]<--> Y1[f]

I.e, I have Y1[f] and would like to have an indicator on how sharp a peak
is there in y1[n](closer to a delta is better).
I cannot afford to do a IFFT. The reason being I need to do this operation
on many of these Y[f]'s, name Y1[f], Y2[f], Y3[f], etc. etc.

What I need to do is is to make a good estimation of how peaky the y1[t],
y2[t] ...etc are, and choose the one that is the "most" peaky, i.e, has a
dominant peak!

So, is there any way by which the frequency domain info can help us
estimate the time domain peak sharpness without doing IFFT?
Note that I dont really need to know where the peak is..
I may or may not have multiple peaks in y[n]'s, but all I care is a
"dominant" peak in the time domain signal.

Ksen wrote:
...
> What I need to do is is to make a good estimation of how peaky the y1[t],
> y2[t] ...etc are, and choose the one that is the "most" peaky, i.e, has a
> dominant peak!

You have to exactly define what you mean. Given two vectors y1 and y2,
how exactly do you determine which one is "more peaky" than the other
(in time domain)? Once you have described your procedure in time
domain, there might be something similar in the frequency domain.

For example: y1 = [ 0 1 -1 0 ] and y2 = [0 1 3 0]. Which one is "more
peaky"?

>
>Ksen wrote:
>...
>> What I need to do is is to make a good estimation of how peaky the
y1[t],
>> y2[t] ...etc are, and choose the one that is the "most" peaky, i.e, has
a
>> dominant peak!
>
>You have to exactly define what you mean. Given two vectors y1 and y2,
>how exactly do you determine which one is "more peaky" than the other
>(in time domain)? Once you have described your procedure in time
>domain, there might be something similar in the frequency domain.
>
>For example: y1 = [ 0 1 -1 0 ] and y2 = [0 1 3 0]. Which one is "more
>peaky"?
>
>


I would say y2 is more peaky. 
In general, the problem I am solving is a matching problem of a query
signal, vs. say, 10 template signals.

y1, y2,y3.....y10 are outputs of matching the query signal with template
1, template 2, etc., respectively. All my operations are however in the
frequency domain, Y1, Y2,...Y10.

Only one of them in time domain (1 thru 10) will have a sharp peak, all
others will look like noise (garbage). I have no "time" to do 10 IFFTs, as
this will work on a very very low end platform. Would rather look at
Y1[f]...Y10[f} and make a judgement on which one will be most peaky while
I do an IFFT.. I dont care where the peak is!!!

Ksen wrote:

> I have a unique problem where I need to predict the "peakedness" of the
> time domain signal just by looking at the frequency transform of the
> signal.

In the general case, there is no way to estimate the time domain 
peakedness from the spectrum. You will have to do the IFT or solve the 
system of equations for max x(t). May be your signal has some special 
properties which you can use to find the peaks.

Vladimir Vassilevsky

DSP and Mixed Signal Design Consultant

http://www.abvolt.com

> y1, y2,y3.....y10 are outputs of matching the query signal with template
> 1, template 2, etc., respectively. All my operations are however in the
> frequency domain, Y1, Y2,...Y10.
>
> Only one of them in time domain (1 thru 10) will have a sharp peak, all
> others will look like noise (garbage). I have no "time" to do 10 IFFTs, as
> this will work on a very very low end platform. Would rather look at
> Y1[f]...Y10[f} and make a judgement on which one will be most peaky while
> I do an IFFT.. I dont care where the peak is!!!

Seems like you want to do a cross-corelation.

So you can just multiply the FFT of your signals with your template and
pick the one with the biggest magnitude.

Ksen wrote:
>> Ksen wrote:
>> ...
>>> What I need to do is is to make a good estimation of how peaky the
> y1[t],
>>> y2[t] ...etc are, and choose the one that is the "most" peaky, i.e, has
> a
>>> dominant peak!
>> You have to exactly define what you mean. Given two vectors y1 and y2,
>> how exactly do you determine which one is "more peaky" than the other
>> (in time domain)? Once you have described your procedure in time
>> domain, there might be something similar in the frequency domain.
>>
>> For example: y1 = [ 0 1 -1 0 ] and y2 = [0 1 3 0]. Which one is "more
>> peaky"?
>>
>>
> 
> 
> I would say y2 is more peaky. 
> In general, the problem I am solving is a matching problem of a query
> signal, vs. say, 10 template signals.
> 
> y1, y2,y3.....y10 are outputs of matching the query signal with template
> 1, template 2, etc., respectively. All my operations are however in the
> frequency domain, Y1, Y2,...Y10.
> 
> Only one of them in time domain (1 thru 10) will have a sharp peak, all
> others will look like noise (garbage). I have no "time" to do 10 IFFTs, as
> this will work on a very very low end platform. Would rather look at
> Y1[f]...Y10[f} and make a judgement on which one will be most peaky while
> I do an IFFT.. I dont care where the peak is!!!

The only difference between the spectra of uniformly distributed noise 
and a single sharp impulse lies in the phases. The amplitudes of the 
frequency components are the same. Figuring out what the phases tell you 
is as much work as an IFFT.

Jerry
-- 
Engineering is the art of making what you want from things you can get.
�����������������������������������������������������������������������

Jerry Avins wrote:
> Ksen wrote:

(snip)

>>> You have to exactly define what you mean. Given two vectors y1 and y2,
>>> how exactly do you determine which one is "more peaky" than the other
>>> (in time domain)? Once you have described your procedure in time
>>> domain, there might be something similar in the frequency domain.

>>> For example: y1 = [ 0 1 -1 0 ] and y2 = [0 1 3 0]. Which one is "more
>>> peaky"?

>> I would say y2 is more peaky. In general, the problem I am solving is 
>> a matching problem of a query
>> signal, vs. say, 10 template signals.

How about the absolute value or square of the second derivative
(or second difference for discrete data) as a peakiness measure?
Then you either want the maximum or mean over the whole signal.

(snip)

> The only difference between the spectra of uniformly distributed noise 
> and a single sharp impulse lies in the phases. The amplitudes of the 
> frequency components are the same. Figuring out what the phases tell you 
> is as much work as an IFFT.

This is what I thought, too.  Though given that he doesn't need to
know where the peaks are there might be some small simplifications.

For a not-so-obvious example, there is an O(n) algorithm for median,
though the usual implementation would be an O(n log n) sort.
I don't know at what n value the O(n) value is faster, but it
might be large.

So, say one wants to compute the second difference of the IFFT,
is there anything that can be done besides computing the whole IFFT
and then applying the second difference?

-- glen

I think glen shows  avery good example of median, where a "supposedly
mistaken" O(nlogn) operation is actually O(n).

My initial question was very similar...
Can the FT of a signal tell anything about its time domain peakedness..

Actually, in the limiting case, where x[n] = d[n-n0],
then you can do the math and see |X(f)| = 1, and Phase(X(f)) = straight
line, passing thru the origin.

Now, given a bunch of readings of Phase(X(f)) one can fit a line (or a
plane, in 2d case) and verify how "off" the readings are from a best
fitted plane. 

However, the real world will have many side-spikes...

BTW, fitting a plane is O(n), and certainly is not as much work as
O(nlogn).

Infact, one does not need to fit a plane, all we are interested is what is
the dispersion of the data from the best plane out there (hence all we care
is minimizing an error metric!!).

Would be interesing to see the application of this in real world...

>For a not-so-obvious example, there is an O(n) algorithm for median,
>though the usual implementation would be an O(n log n) sort.
>I don't know at what n value the O(n) value is faster, but it
>might be large.
>
>So, say one wants to compute the second difference of the IFFT,
>is there anything that can be done besides computing the whole IFFT
>and then applying the second difference?
>
>-- glen
>
>

glen herrmannsfeldt wrote:
> Jerry Avins wrote:
> > Ksen wrote:
>
> (snip)
>
> >>> You have to exactly define what you mean. Given two vectors y1 and y2,
> >>> how exactly do you determine which one is "more peaky" than the other
> >>> (in time domain)? Once you have described your procedure in time
> >>> domain, there might be something similar in the frequency domain.
>
> >>> For example: y1 = [ 0 1 -1 0 ] and y2 = [0 1 3 0]. Which one is "more
> >>> peaky"?
>
> >> I would say y2 is more peaky. In general, the problem I am solving is
> >> a matching problem of a query
> >> signal, vs. say, 10 template signals.
>
> How about the absolute value or square of the second derivative
> (or second difference for discrete data) as a peakiness measure?
> Then you either want the maximum or mean over the whole signal.

I thought of that too. There are some subtle and not so subtle problems
with this approach (see below).

>
> (snip)
>
> > The only difference between the spectra of uniformly distributed noise
> > and a single sharp impulse lies in the phases. The amplitudes of the
> > frequency components are the same. Figuring out what the phases tell you
> > is as much work as an IFFT.
>
> This is what I thought, too.  Though given that he doesn't need to
> know where the peaks are there might be some small simplifications.
>
> For a not-so-obvious example, there is an O(n) algorithm for median,
> though the usual implementation would be an O(n log n) sort.
> I don't know at what n value the O(n) value is faster, but it
> might be large.

This paragraph completely OT:
The QuickSelect O(n) median search should be faster for every value of
n than the obvious QuickSort based O(n log n) median search method. The
reason is that QuickSelect performs a genuine subset of the operations
that the QuickSort needs.

>
> So, say one wants to compute the second difference of the IFFT,
> is there anything that can be done besides computing the whole IFFT
> and then applying the second difference?

One has several vectors y_1, y_2, ..., y_m. The task is to rank these
vectors according to "peakedness", where "peakedness" can have some
arbitrary definition, given only the DFTs Y_1, Y_2, ...., Y_m. If
possible, using a O(n) algorithm.

Here is my solution:

1. Apply the first or second difference operator in frequency domain
via windowing (this is an O(n) operation).
2. Compute the energy of the differenced signal by computing the energy
in the frequency domain using Parseval's theorem (this again is an O(n)
operation).
3. Rank the vectors according to this energy.

As only a fixed number of O(n) operations are required, the whole
algorithm runs in linear time. The problems are:

1 (not so subtle): the OP specified that the y vectors contain some
background noise plus possibly one or several spikes. After
differencing, hopefully the signals containing spikes have more energy
than those without. However, if the spikey signal contains less general
noise than a non-spikey signal, this ranking might not reflect the true
"peakedness".

2 (subtle): since windowing in frequency domain applies circular
convolution in time domain, there is the possibility of creating
non-existant spikes due to edge effects (convolving around the borders)
- this is a problem if the noise in the signal has varying mean value.

Wether the solution works and the problems really are problems depends,
of course, as always, on the application. One possible cure might be to
IDFT only the top ranking vector and check for peaks in time domain.

Regards,
Andor

Vladimir Vassilevsky wrote:
> 
> 
> Ksen wrote:
> 
>> I have a unique problem where I need to predict the "peakedness" of the
>> time domain signal just by looking at the frequency transform of the
>> signal.
> 
> 
> In the general case, there is no way to estimate the time domain 
> peakedness from the spectrum. 

Seems a pretty bold statement.

What you really mean is you don't know of any way.


-- Mark Borgerding