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

# getting freqz from fft (complex numbers)

Started by ●January 4, 2006

Reply by ●January 4, 20062006-01-04

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.

Reply by ●January 4, 20062006-01-04

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. �����������������������������������������������������������������������

Reply by ●January 4, 20062006-01-04

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.htmJerry, thank you for this link and for advice, too.

Reply by ●January 4, 20062006-01-04

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.

Reply by ●January 5, 20062006-01-05

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

Reply by ●January 5, 20062006-01-05

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||_L1Ouch. 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

Reply by ●January 5, 20062006-01-05

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

Reply by ●January 5, 20062006-01-05

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

Reply by ●January 5, 20062006-01-05

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