getting freqz from fft (complex numbers)

After FFT is done, result is array filled with complex numbers.
What is the best way to obtain maximum signal amplitudes at
corresponding frequencies, maybe even (if possible?) without
calculating  roots (complex modules) in order to use as less
computational resources as possible?

thanx in advance,
    Zlatko

zlatko wrote:
> After FFT is done, result is array filled with complex numbers.
> What is the best way to obtain maximum signal amplitudes at
> corresponding frequencies, maybe even (if possible?) without
> calculating  roots (complex modules) in order to use as less
> computational resources as possible?

If you are searcing for a small number of peaks in the spectrum X(w),
I would use a search criterium like [*]

 z = abs(re(X(w)))+abs(im(X(w)))

to find the peak, and then maybe use the usual magnitude formula
to compute the actual magnitude for that peak.

Rune

* This is the L0 or L1 norm of the spectrum, I never remember the
  correct term. The nice thing about norms is that if
||x|+|y||>||x|+|z||
  in one norm, it is also true in all other norms. So the
computationally
  cheap norms can be used to find the extrema, and the usual
  L2 norm can be used only where one wants to know the details.

zlatko wrote:
> After FFT is done, result is array filled with complex numbers.
> What is the best way to obtain maximum signal amplitudes at
> corresponding frequencies, maybe even (if possible?) without
> calculating  roots (complex modules) in order to use as less
> computational resources as possible?

What is the use of a root? Instead of looking for the maximum magnitude, 
look for the maximum squared magnitude. If the square is not suitable as 
a result, you have only one root to extract.

If a rough approximation is adequate, convert both arguments to absolute 
values, add half the smaller to the larger, and settle for that. More 
approximations: http://www.dspguru.com/comp.dsp/tricks/alg/mag_est.htm

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

Jerry Avins wrote:
> What is the use of a root? Instead of looking for the maximum magnitude, 
> look for the maximum squared magnitude. If the square is not suitable as a 
> result, you have only one root to extract.
>
> If a rough approximation is adequate, convert both arguments to absolute 
> values, add half the smaller to the larger, and settle for that. More 
> approximations: http://www.dspguru.com/comp.dsp/tricks/alg/mag_est.htm

Jerry, thank you for this link and for advice, too.

Rune Allnor wrote
> If you are searcing for a small number of peaks in the spectrum X(w),
> I would use a search criterium like [*]
>
> z = abs(re(X(w)))+abs(im(X(w)))
>
> to find the peak, and then maybe use the usual magnitude formula
> to compute the actual magnitude for that peak.
>
> Rune
>
> * This is the L0 or L1 norm of the spectrum, I never remember the
>  correct term. The nice thing about norms is that if
> ||x|+|y||>||x|+|z||
>  in one norm, it is also true in all other norms. So the
> computationally
>  cheap norms can be used to find the extrema, and the usual
>  L2 norm can be used only where one wants to know the details.
>

Thank you, this might be very good solution for my problem.

Rune Allnor wrote:
> * This is the L0 or L1 norm of the spectrum, I never remember the
>   correct term.

It should be easy to remember the correct term because an L0 norm
doesn't exist.

> The nice thing about norms is that if
> ||x|+|y||>||x|+|z||
>   in one norm, it is also true in all other norms. So the
> computationally
>   cheap norms can be used to find the extrema, and the usual
>   L2 norm can be used only where one wants to know the details.

That won't work, Rune. Consider the two numbers z1=1.0, z2=.9 exp(i
pi/4). Then

||z1||_L2 >  ||z2||_L2

but

||z1||_L1 <  ||z2||_L1

Regards,
Andor

Andor wrote:
> Rune Allnor wrote:
> > * This is the L0 or L1 norm of the spectrum, I never remember the
> >   correct term.
>
> It should be easy to remember the correct term because an L0 norm
> doesn't exist.

OK. It's been a while since I read about these kinds of things.
The L2 norm was the intersting one, anyway.

> > The nice thing about norms is that if
> > ||x|+|y||>||x|+|z||
> >   in one norm, it is also true in all other norms. So the
> > computationally
> >   cheap norms can be used to find the extrema, and the usual
> >   L2 norm can be used only where one wants to know the details.
>
> That won't work, Rune. Consider the two numbers z1=1.0, z2=.9 exp(i
> pi/4). Then
>
> ||z1||_L2 >  ||z2||_L2
>
> but
>
> ||z1||_L1 <  ||z2||_L1

Ouch. It seems you are right. If so, it means the choise of norm
changes the topology of a normed space? At frist glance I find that
very hard to believe... but then, maybe not.

If I was right in my statement yesterday, it would mean that all
optimization problems needed to be solved only in the least squares
sense, since that solution would be optimal in all other senses, too.
That's clearly not the case, so I was wrong yesterday.

Thanks, Andor, for the correction.

Rune

Rune Allnor wrote:
> Andor wrote:
> > Rune Allnor wrote:
> > > * This is the L0 or L1 norm of the spectrum, I never remember the
> > >   correct term.
> >
> > It should be easy to remember the correct term because an L0 norm
> > doesn't exist.
>
> OK. It's been a while since I read about these kinds of things.
> The L2 norm was the intersting one, anyway.

That depends on what you are doing. I admit that the only norms I have
seen used in practice are the 1, 2 and infinty norms.


> > > The nice thing about norms is that if
> > > ||x|+|y||>||x|+|z||
> > >   in one norm, it is also true in all other norms. So the
> > > computationally
> > >   cheap norms can be used to find the extrema, and the usual
> > >   L2 norm can be used only where one wants to know the details.
> >
> > That won't work, Rune. Consider the two numbers z1=1.0, z2=.9 exp(i
> > pi/4). Then
> >
> > ||z1||_L2 >  ||z2||_L2
> >
> > but
> >
> > ||z1||_L1 <  ||z2||_L1
>
> Ouch. It seems you are right. If so, it means the choise of norm
> changes the topology of a normed space? At frist glance I find that
> very hard to believe... but then, maybe not.

If by topology of a complete normed space (Banach space)  you mean the
topology induced by the metric induced by the norm, then yes (I love
maths :-). To see a difference you have to go to inifinte dimensional
spaces however. In finite dimensional vector spaces, all norms (and
therefore topologies induced by norms) are equivalent. I'm not sure if
this is what you had in mind by "topology". The geometry clearly is
different - look at the complex unit "circle" in different norms:
diamond (L1), circle (L2), square (infinity) ...

> If I was right in my statement yesterday, it would mean that all
> optimization problems needed to be solved only in the least squares
> sense, since that solution would be optimal in all other senses, too.
> That's clearly not the case, so I was wrong yesterday.

I think optimizations w.r.t arbitrary norms can be achieved by iterated
WLS, by updating the weights each iteration according to some rule
determined by the required norm. I think I read that somewhere, which
doesn't necessarily make it true.

>
> Thanks, Andor, for the correction.

For comparison, the square of the L2 norm suffices, and is very cheap
to compute (as Jerry has already mentioned), so I don't think any
elaboraty tricks are needed.

Regards,
Andor

Andor wrote:
> Rune Allnor wrote:
> > Andor wrote:
> > > Rune Allnor wrote:
> > > > * This is the L0 or L1 norm of the spectrum, I never remember the
> > > >   correct term.
> > >
> > > It should be easy to remember the correct term because an L0 norm
> > > doesn't exist.
> >
> > OK. It's been a while since I read about these kinds of things.
> > The L2 norm was the intersting one, anyway.
>
> That depends on what you are doing. I admit that the only norms I have
> seen used in practice are the 1, 2 and infinty norms.
>
>
> > > > The nice thing about norms is that if
> > > > ||x|+|y||>||x|+|z||
> > > >   in one norm, it is also true in all other norms. So the
> > > > computationally
> > > >   cheap norms can be used to find the extrema, and the usual
> > > >   L2 norm can be used only where one wants to know the details.
> > >
> > > That won't work, Rune. Consider the two numbers z1=1.0, z2=.9 exp(i
> > > pi/4). Then
> > >
> > > ||z1||_L2 >  ||z2||_L2
> > >
> > > but
> > >
> > > ||z1||_L1 <  ||z2||_L1
> >
> > Ouch. It seems you are right. If so, it means the choise of norm
> > changes the topology of a normed space? At frist glance I find that
> > very hard to believe... but then, maybe not.
>
> If by topology of a complete normed space (Banach space)  you mean the
> topology induced by the metric induced by the norm, then yes (I love
> maths :-). To see a difference you have to go to inifinte dimensional
> spaces however. In finite dimensional vector spaces, all norms (and
> therefore topologies induced by norms) are equivalent. I'm not sure if
> this is what you had in mind by "topology".

I have a rather naive impression of topology. It has to do with
ordering
and arrangements of elements, right? So if one normed space, say,
S1=(C^N, | |_a) is ordered such that |z1|_a>|z2|_a, and the other
space,
say S2=(C^N, | |_b), is ordered such that |z1|_b < |z2|_b for some
N-vectors z1, z2, the toplogies of the spaces S1 and S2 are different.
Right...?

> The geometry clearly is
> different - look at the complex unit "circle" in different norms:
> diamond (L1), circle (L2), square (infinity) ...

Yep, I remember that excercise from some course I took many years ago.

Rune

Rune Allnor wrote:
...
> I have a rather naive impression of topology. It has to do with
> ordering
> and arrangements of elements, right?

In a way. You can have a look here:

http://mathworld.wolfram.com/Topology.html