FPGA Central - World's 1st FPGA / CPLD Portal

FPGA Central

World's 1st FPGA Portal

 

Go Back   FPGA Groups > NewsGroup > DSP

DSP comp.dsp newsgroup, mailing list

Reply
 
LinkBack Thread Tools Display Modes
  #1 (permalink)  
Old 12-04-2007, 05:02 AM
Chris Maryan
Guest
 
Posts: n/a
Default Nearest IIR System to FIR?

Roughly: I have a model in an FIR form that I would like to change to
an IIR form (for various reasons that I'll spare you from). I'm
interested in finding the "nearest" IIR filter of order N to some
given FIR filter ("nearest" meaning in some reasonable metric). Are
there any standard approaches to this or should I just clobber away
and see what happens if I try this in some minimization formulation
under some aptly chosen norm?

i.e. given y_t = h * x_t (where h is the FIR impulse response)
I'd like to approximate as closely as possibly this with
y_t = a*y_(t-1) + b*x_t
where the length of b is substantially smaller than the length of h,
perhaps 1, perhaps arbitrarily specified by me
and the length of a is specified by me.

Any thoughts?

Thanks,

Chris
Reply With Quote
  #2 (permalink)  
Old 12-04-2007, 05:06 AM
Randy Yates
Guest
 
Posts: n/a
Default Re: Nearest IIR System to FIR?

Chris Maryan <[email protected]> writes:

> Roughly: I have a model in an FIR form that I would like to change to
> an IIR form (for various reasons that I'll spare you from). I'm
> interested in finding the "nearest" IIR filter of order N to some
> given FIR filter ("nearest" meaning in some reasonable metric). Are
> there any standard approaches to this or should I just clobber away
> and see what happens if I try this in some minimization formulation
> under some aptly chosen norm?
>
> i.e. given y_t = h * x_t (where h is the FIR impulse response)
> I'd like to approximate as closely as possibly this with
> y_t = a*y_(t-1) + b*x_t
> where the length of b is substantially smaller than the length of h,
> perhaps 1, perhaps arbitrarily specified by me
> and the length of a is specified by me.
>
> Any thoughts?
>
> Thanks,
>
> Chris


You might try applying the FDLS algorithm (frequency domain least squares).
--
% Randy Yates % "...the answer lies within your soul
%% Fuquay-Varina, NC % 'cause no one knows which side
%%% 919-577-9882 % the coin will fall."
%%%% <[email protected]> % 'Big Wheels', *Out of the Blue*, ELO
http://www.digitalsignallabs.com
Reply With Quote
  #3 (permalink)  
Old 12-04-2007, 05:17 AM
Rune Allnor
Guest
 
Posts: n/a
Default Re: Nearest IIR System to FIR?

On 4 Des, 06:02, Chris Maryan <[email protected]> wrote:
> Roughly: I have a model in an FIR form that I would like to change to
> an IIR form (for various reasons that I'll spare you from). I'm
> interested in finding the "nearest" IIR filter of order N to some
> given FIR filter ("nearest" meaning in some reasonable metric). Are
> there any standard approaches to this or should I just clobber away
> and see what happens if I try this in some minimization formulation
> under some aptly chosen norm?
>
> i.e. given y_t = h * x_t (where h is the FIR impulse response)
> I'd like to approximate as closely as possibly this with
> y_t = a*y_(t-1) + b*x_t
> where the length of b is substantially smaller than the length of h,
> perhaps 1, perhaps arbitrarily specified by me
> and the length of a is specified by me.


I don't know how to approximate a given FIR by an IIR.
However, if the FIR was designed based on some specification
I would go back and design an IIR from the same spec.

If the FIR is based on some empirical data (like some measured
signal) the prolem becomes a lot harder.

Rune
Reply With Quote
  #4 (permalink)  
Old 12-04-2007, 05:35 AM
Darol Klawetter
Guest
 
Posts: n/a
Default Re: Nearest IIR System to FIR?

On Dec 3, 11:02 pm, Chris Maryan <[email protected]> wrote:
> Roughly: I have a model in an FIR form that I would like to change to
> an IIR form (for various reasons that I'll spare you from). I'm
> interested in finding the "nearest" IIR filter of order N to some
> given FIR filter ("nearest" meaning in some reasonable metric). Are
> there any standard approaches to this or should I just clobber away
> and see what happens if I try this in some minimization formulation
> under some aptly chosen norm?
>
> i.e. given y_t = h * x_t (where h is the FIR impulse response)
> I'd like to approximate as closely as possibly this with
> y_t = a*y_(t-1) + b*x_t
> where the length of b is substantially smaller than the length of h,
> perhaps 1, perhaps arbitrarily specified by me
> and the length of a is specified by me.
>
> Any thoughts?
>
> Thanks,
>
> Chris


Chris,

Do you need to have the linear phase response that a FIR filter
provides?

Darol Klawetter
Reply With Quote
  #5 (permalink)  
Old 12-04-2007, 06:12 AM
Chris Maryan
Guest
 
Posts: n/a
Default Re: Nearest IIR System to FIR?

No linear phase requirement, or any other stringent system requirement
for that matter, except model order which I would like as a parameter
to play with. The issue is that I have empirically measured FIRs, and
for reasons of ease of modeling, need an IIR equivalent, so to answer
Rune's question, yes, it's harder.

Chris

On Dec 4, 12:35 am, Darol Klawetter <[email protected]>
wrote:
> On Dec 3, 11:02 pm, Chris Maryan <[email protected]> wrote:
>
>
>
> > Roughly: I have a model in an FIR form that I would like to change to
> > an IIR form (for various reasons that I'll spare you from). I'm
> > interested in finding the "nearest" IIR filter of order N to some
> > given FIR filter ("nearest" meaning in some reasonable metric). Are
> > there any standard approaches to this or should I just clobber away
> > and see what happens if I try this in some minimization formulation
> > under some aptly chosen norm?

>
> > i.e. given y_t = h * x_t (where h is the FIR impulse response)
> > I'd like to approximate as closely as possibly this with
> > y_t = a*y_(t-1) + b*x_t
> > where the length of b is substantially smaller than the length of h,
> > perhaps 1, perhaps arbitrarily specified by me
> > and the length of a is specified by me.

>
> > Any thoughts?

>
> > Thanks,

>
> > Chris

>
> Chris,
>
> Do you need to have the linear phase response that a FIR filter
> provides?
>
> Darol Klawetter


Reply With Quote
  #6 (permalink)  
Old 12-04-2007, 06:16 AM
Chris Maryan
Guest
 
Posts: n/a
Default Re: Nearest IIR System to FIR?

On Dec 4, 12:17 am, Rune Allnor <[email protected]> wrote:
> On 4 Des, 06:02, Chris Maryan <[email protected]> wrote:
>
> > Roughly: I have a model in an FIR form that I would like to change to
> > an IIR form (for various reasons that I'll spare you from). I'm
> > interested in finding the "nearest" IIR filter of order N to some
> > given FIR filter ("nearest" meaning in some reasonable metric). Are
> > there any standard approaches to this or should I just clobber away
> > and see what happens if I try this in some minimization formulation
> > under some aptly chosen norm?

>
> > i.e. given y_t = h * x_t (where h is the FIR impulse response)
> > I'd like to approximate as closely as possibly this with
> > y_t = a*y_(t-1) + b*x_t
> > where the length of b is substantially smaller than the length of h,
> > perhaps 1, perhaps arbitrarily specified by me
> > and the length of a is specified by me.

>
> I don't know how to approximate a given FIR by an IIR.
> However, if the FIR was designed based on some specification
> I would go back and design an IIR from the same spec.
>
> If the FIR is based on some empirical data (like some measured
> signal) the prolem becomes a lot harder.
>
> Rune


Thanks, but to put it in your terms, it's harder (empirically measured
responses). For "historical reasons" I have them in an FIR form, but I
would like to try modeling the system as an IIR.

Chris

Reply With Quote
  #7 (permalink)  
Old 12-04-2007, 06:19 AM
Rune Allnor
Guest
 
Posts: n/a
Default Re: Nearest IIR System to FIR?

On 4 Des, 07:12, Chris Maryan <[email protected]> wrote:
> No linear phase requirement, or any other stringent system requirement
> for that matter, except model order which I would like as a parameter
> to play with. The issue is that I have empirically measured FIRs, and
> for reasons of ease of modeling, need an IIR equivalent, so to answer
> Rune's question, yes, it's harder.


What kind of modeling would this be? Do you have to do the
modeling in time domain? Could you save some FLOPs by
doing the modeling in frequency domain?

Rune
Reply With Quote
  #8 (permalink)  
Old 12-04-2007, 06:19 AM
Chris Maryan
Guest
 
Posts: n/a
Default Re: Nearest IIR System to FIR?


Thanks for the tip on FDLS, I'll have a look at that. Do you have any
favourite papers on FDLS?

Chris

On Dec 4, 12:06 am, Randy Yates <[email protected]> wrote:
> Chris Maryan <[email protected]> writes:
> > Roughly: I have a model in an FIR form that I would like to change to
> > an IIR form (for various reasons that I'll spare you from). I'm
> > interested in finding the "nearest" IIR filter of order N to some
> > given FIR filter ("nearest" meaning in some reasonable metric). Are
> > there any standard approaches to this or should I just clobber away
> > and see what happens if I try this in some minimization formulation
> > under some aptly chosen norm?

>
> > i.e. given y_t = h * x_t (where h is the FIR impulse response)
> > I'd like to approximate as closely as possibly this with
> > y_t = a*y_(t-1) + b*x_t
> > where the length of b is substantially smaller than the length of h,
> > perhaps 1, perhaps arbitrarily specified by me
> > and the length of a is specified by me.

>
> > Any thoughts?

>
> > Thanks,

>
> > Chris

>
> You might try applying the FDLS algorithm (frequency domain least squares).
> --
> % Randy Yates % "...the answer lies within your soul
> %% Fuquay-Varina, NC % 'cause no one knows which side
> %%% 919-577-9882 % the coin will fall."
> %%%% <[email protected]> % 'Big Wheels', *Out of the Blue*, ELOhttp://www.digitalsignallabs.com


Reply With Quote
  #9 (permalink)  
Old 12-04-2007, 06:33 AM
Randy Yates
Guest
 
Posts: n/a
Default Re: Nearest IIR System to FIR?

Chris Maryan <[email protected]> writes:

> Thanks for the tip on FDLS, I'll have a look at that. Do you have any
> favourite papers on FDLS?


Greg Berchin is the acknowledged expert on it - he sticks his head in
here often so you can probably ask him questions directly. But here
is what I've used:

@article{berchin,
title = "{Precise Filter Design}",
author = "Greg Berchin",
journal = "IEEE Signal Processing Magazine",
month = "January",
year = "2007"}

--Randy

>
> Chris
>
> On Dec 4, 12:06 am, Randy Yates <[email protected]> wrote:
>> Chris Maryan <[email protected]> writes:
>> > Roughly: I have a model in an FIR form that I would like to change to
>> > an IIR form (for various reasons that I'll spare you from). I'm
>> > interested in finding the "nearest" IIR filter of order N to some
>> > given FIR filter ("nearest" meaning in some reasonable metric). Are
>> > there any standard approaches to this or should I just clobber away
>> > and see what happens if I try this in some minimization formulation
>> > under some aptly chosen norm?

>>
>> > i.e. given y_t = h * x_t (where h is the FIR impulse response)
>> > I'd like to approximate as closely as possibly this with
>> > y_t = a*y_(t-1) + b*x_t
>> > where the length of b is substantially smaller than the length of h,
>> > perhaps 1, perhaps arbitrarily specified by me
>> > and the length of a is specified by me.

>>
>> > Any thoughts?

>>
>> > Thanks,

>>
>> > Chris

>>
>> You might try applying the FDLS algorithm (frequency domain least squares).
>> --
>> % Randy Yates % "...the answer lies within your soul
>> %% Fuquay-Varina, NC % 'cause no one knows which side
>> %%% 919-577-9882 % the coin will fall."
>> %%%% <[email protected]> % 'Big Wheels', *Out of the Blue*, ELOhttp://www.digitalsignallabs.com

>


--
% Randy Yates % "...the answer lies within your soul
%% Fuquay-Varina, NC % 'cause no one knows which side
%%% 919-577-9882 % the coin will fall."
%%%% <[email protected]> % 'Big Wheels', *Out of the Blue*, ELO
http://www.digitalsignallabs.com
Reply With Quote
  #10 (permalink)  
Old 12-04-2007, 06:56 AM
Chris Maryan
Guest
 
Posts: n/a
Default Re: Nearest IIR System to FIR?

No need to save flops, this is off line. That said, the FDLS approach
mentioned looks promising, I think in general this is turning out to
be a job for a generic fit a filter to an arbitrary frequency response
kind of thing. I had perhaps hoped that there was something out there
to turn my numerator into a denominator in a more 'direct' way.

Thanks,

Chris

On Dec 4, 1:19 am, Rune Allnor <[email protected]> wrote:
> On 4 Des, 07:12, Chris Maryan <[email protected]> wrote:
>
> > No linear phase requirement, or any other stringent system requirement
> > for that matter, except model order which I would like as a parameter
> > to play with. The issue is that I have empirically measured FIRs, and
> > for reasons of ease of modeling, need an IIR equivalent, so to answer
> > Rune's question, yes, it's harder.

>
> What kind of modeling would this be? Do you have to do the
> modeling in time domain? Could you save some FLOPs by
> doing the modeling in frequency domain?
>
> Rune


Reply With Quote
  #11 (permalink)  
Old 12-04-2007, 12:06 PM
Greg Berchin
Guest
 
Posts: n/a
Default Re: Nearest IIR System to FIR?

Chris Maryan wrote:

> Roughly: I have a model in an FIR form that I would like to change to
> an IIR form


Prony's Method (or Padé-Prony Method) fits an IIR filter to a desired
impulse response. Since the coefficients of an FIR filter are its
impulse response, this might be worth looking at.

FDLS is also a viable candidate, but if your prototype FIR filter is
linear phase then you'll have to convert it to something reasonably
close to minimum phase before FDLS will work well. Otherwise FDLS
will have to add a whole bunch of delay to the numerator, and you'll
end up with an IIR filter that is not much smaller than the FIR that
you started with.

Matlab code for FDLS is available at "http://apollo.ee.columbia.edu/
spm/external/tipsandtricks/files/TandT_Jan2007.zip", or directly from
me at "gberchin {at} comcast {dot} net".

Greg Berchin
Reply With Quote
  #12 (permalink)  
Old 12-04-2007, 12:43 PM
Peter K.
Guest
 
Posts: n/a
Default Re: Nearest IIR System to FIR?

Chris Maryan <[email protected]> writes:

> Roughly: I have a model in an FIR form that I would like to change to
> an IIR form (for various reasons that I'll spare you from). I'm
> interested in finding the "nearest" IIR filter of order N to some
> given FIR filter ("nearest" meaning in some reasonable metric). Are
> there any standard approaches to this or should I just clobber away
> and see what happens if I try this in some minimization formulation
> under some aptly chosen norm?
>
> i.e. given y_t = h * x_t (where h is the FIR impulse response)
> I'd like to approximate as closely as possibly this with
> y_t = a*y_(t-1) + b*x_t
> where the length of b is substantially smaller than the length of h,
> perhaps 1, perhaps arbitrarily specified by me
> and the length of a is specified by me.



Chris,

This sort of problem ("model order reduction") shows up lots in
control problems. The sorts of things I'd look at are:

* Balanced truncations
* Hankel Norm approximation

In the case of balanced truncations, the "nearest" criterion is like
principal component analysis (B.C. Moore, "Principal Component
Analysis in Linear Systems: Controlibility, Observibility, and Model
Reduction" IEEE Trans. On Automatic Control, Vol AC-26, No 1, pp17-32,
Feb 1981.)

In the case of the hankel norm, "nearest" is an infinity norm
criterion (but probably not like you've seen before; K.Glover, "All
optimal Hankel-norm approximations of linear multivariable systems and
their error bounds." Int.J.Control, 1984, VOL 39, NO.6,pp 1115-1193.)

Ciao,

Peter K.

--
"And he sees the vision splendid
of the sunlit plains extended
And at night the wondrous glory of the everlasting stars."


Reply With Quote
  #13 (permalink)  
Old 12-04-2007, 02:04 PM
Vladimir Vassilevsky
Guest
 
Posts: n/a
Default Re: Nearest IIR System to FIR?


"Chris Maryan" <[email protected]> wrote in message
news:[email protected]m...
> Roughly: I have a model in an FIR form that I would like to change to
> an IIR form (for various reasons that I'll spare you from).


Dark secrets, huh. This is a very common problem. It is simple enough to
design FIR to an arbitrary spec by Parks-Mcclellan or by windowed FFT. It
would be attractive to convert it to IIR then.

FDLS can hardly be used for that because, as the least squares method, it
approximates peaks but not the values of the response. There will be some
other problems with FDLS also.

There is no good universal solution. Generally, this task is equvalent to
designing of IIR filter to an arbitrary spec, which is a minimization task.

Vladimir Vassilevsky
DSP and Mixed Signal Consultant
www.abvolt.com



Reply With Quote
  #14 (permalink)  
Old 12-04-2007, 03:12 PM
Andor
Guest
 
Posts: n/a
Default Re: Nearest IIR System to FIR?

His Berchiness speaks ... :-)

Greg Berchin wrote:
> Chris Maryan wrote:
> > Roughly: I have a model in an FIR form that I would like to change to
> > an IIR form

>
> Prony's Method (or Padé-Prony Method) fits an IIR filter to a desired
> impulse response. Since the coefficients of an FIR filter are its
> impulse response, this might be worth looking at.


I guess I don't have to tell you that your method is a neat
generalization of Shanks's, which is a neat generalization of Prony's.
In fact, your method is a fully linear alternative to Steiglitz-
McBride's non-linear iterative system identification method for
arbitrary input/output pairs. I don't know why it is not more commonly
known as Berchin's. I disagree with Vladimir and find it very
applicable to the problem of order reduction (just don't use frequency
domain coefficients).

>
> FDLS is also a viable candidate, but if your prototype FIR filter is
> linear phase then you'll have to convert it to something reasonably
> close to minimum phase before FDLS will work well. Otherwise FDLS
> will have to add a whole bunch of delay to the numerator, and you'll
> end up with an IIR filter that is not much smaller than the FIR that
> you started with.


By the way, for the published application of your method (frequency
domain filter design), I would have used the infinity (Chebyshev) norm
instead of the 2-norm. Since your problem is stated in the simple
linear regression format, this allows frequency domain infinity norm
filter design (which is usually more desirable than 2-norm design)
using the fast and proven algorithms of linear programming (simplex,
interior point, barrier). Good implementations of those algorithms are
just as fast or faster than standard SVD-based 2-norm minimizers.
Another thing to publish? As a spin-off, you get Chebyshev-optimized
linear-phase FIR design for free, without tedious convergence problems
of the PM-algorithm. I do agree with Vladimir that you should at least
stand next to Parks in the DSP pantheon :-).

>
> Matlab code for FDLS is available at "http://apollo.ee.columbia.edu/
> spm/external/tipsandtricks/files/TandT_Jan2007.zip", or directly from
> me at "gberchin {at} comcast {dot} net".
>
> Greg Berchin


Regards,
Andor
Reply With Quote
  #15 (permalink)  
Old 12-04-2007, 03:54 PM
Greg Berchin
Guest
 
Posts: n/a
Default Re: Nearest IIR System to FIR?

On Dec 4, 10:12 am, Andor <[email protected]> wrote:

> His Berchiness speaks ... :-)


Hahahahahaha ... if you only knew ... ;-)

> I guess I don't have to tell you that your method is a neat
> generalization of Shanks's, which is a neat generalization of
> Prony's.


I have to admit that it's been literally more than two decades since I
studied any of these approximation techniques. Even to resurrect FDLS
after all this time I had to dust-off a lot of forgotten knowledge.

>I don't know why it is not more commonly known as Berchin's.


Well, until the Tips and Tricks article, it had been completely lost
to history. I do appreciate the attribution. In case it ever does
become known as "Berchin's", I should acknowledge the contribution of
Randy Roberts, a fellow graduate student at UCDavis who one day made
an off-hand comment about implementation of difference equations ...
that triggered the "aha moment" ... that led to my development of the
algorithm.

> By the way, for the published application of your method (frequency
> domain filter design), I would have used the infinity (Chebyshev)
> norm instead of the 2-norm.


At the time FDLS was developed, I had just taken a graduate course in
adaptive systems that included a basic tutorial on system
identification techniques, and I had just learned about time domain
least-squares identification (white noise in; colored noise out; find
pseudoinverse of resulting Toeplitz matrix). FDLS was quite literally
just a reformulation of that problem, using sinewaves instead of white
noise. The matrix became Vandermonde instead of Toeplitz, but
otherwise the technique remained the same.

If you have ideas about how to reformulate using the infinity-norm, I
encourage you to pursue them! I have always maintained that the
technique had a lot of untapped potential.

Thanks for your kind words.

Greg
Reply With Quote
  #16 (permalink)  
Old 12-04-2007, 06:47 PM
Ron N.
Guest
 
Posts: n/a
Default Re: Nearest IIR System to FIR?

On Dec 3, 10:33 pm, Randy Yates <[email protected]> wrote:
> Chris Maryan <[email protected]> writes:
> > Thanks for the tip on FDLS, I'll have a look at that. Do you have any
> > favourite papers on FDLS?

>
> Greg Berchin is the acknowledged expert on it - he sticks his head in
> here often so you can probably ask him questions directly. But here
> is what I've used:
>
> @article{berchin,
> title = "{Precise Filter Design}",
> author = "Greg Berchin",
> journal = "IEEE Signal Processing Magazine",
> month = "January",
> year = "2007"}


It looks like a version of this article is also in
the book "Streamlining Digital Signal Processing"
by Richard G. Lyons. Wiley ISBN: 978-0-470-13157-2

Very clever use of the matrix pseudoinverse.

The book also contains a brief exposition of the
differential evolution genetic algorithm, if you
more like trial and error minimization methods.


IMHO. YMMV.
--
rhn A.T nicholson d.0.t C-o-M
Reply With Quote
  #17 (permalink)  
Old 12-04-2007, 07:13 PM
Randy Yates
Guest
 
Posts: n/a
Default Re: Nearest IIR System to FIR?

"Ron N." <[email protected]> writes:

> On Dec 3, 10:33 pm, Randy Yates <[email protected]> wrote:
>> Chris Maryan <[email protected]> writes:
>> > Thanks for the tip on FDLS, I'll have a look at that. Do you have any
>> > favourite papers on FDLS?

>>
>> Greg Berchin is the acknowledged expert on it - he sticks his head in
>> here often so you can probably ask him questions directly. But here
>> is what I've used:
>>
>> @article{berchin,
>> title = "{Precise Filter Design}",
>> author = "Greg Berchin",
>> journal = "IEEE Signal Processing Magazine",
>> month = "January",
>> year = "2007"}

>
> It looks like a version of this article is also in
> the book "Streamlining Digital Signal Processing"
> by Richard G. Lyons. Wiley ISBN: 978-0-470-13157-2


Yes, and that's probably a better place to look since I think the
presentation there was expanded.

I've gotta get a copy soon.
--
% Randy Yates % "Though you ride on the wheels of tomorrow,
%% Fuquay-Varina, NC % you still wander the fields of your
%%% 919-577-9882 % sorrow."
%%%% <[email protected]> % '21st Century Man', *Time*, ELO
http://www.digitalsignallabs.com
Reply With Quote
  #18 (permalink)  
Old 12-04-2007, 07:36 PM
Greg Berchin
Guest
 
Posts: n/a
Default Re: Nearest IIR System to FIR?

On Dec 4, 2:13 pm, Randy Yates <[email protected]> wrote:

> Yes, and that's probably a better place to look since I think the
> presentation there was expanded.


Actually it was the other way around; Rick Lyons and I had to do some
trimming to fit within the page requirements of the magazine article.
But I don't think that any significant information was left out.

Some extra (albeit 10-20 year old) information can be found in:

1. (1986) G. Berchin, R. Roberts, and M. A. Soderstrand. NEW MODEL-
BASED PARAMETER ESTIMATION TECHNIQUE FOR US IN DECONVOLUTION.
Proceedings of the Asilomar Conference on Circuits, Systems, and
Computers.

2. (1987) G. Berchin, M. A. Soderstrand, and R. Roberts. DECONVOLUTION
USING MODEL-BASED PARAMETER ESTIMATION. IEEE Midwest Symposium on
Circuits and Systems, pp. 402-406.

3. (1989) G. Berchin and M. A. Soderstrand. A TOTAL LEAST SQUARES
APPROACH TO FREQUENCY DOMAIN SYSTEM IDENTIFICATION. IEEE Midwest
Symposium on Circuits and Systems, pp. 709-711.

4. (1990) G. Berchin and M. A. Soderstrand. COHERENT-INPUT,
MICROPROCESSOR BASED, FDLS SYSTEM IDENTIFICATION. Proceedings of the
21st ISA Pittsburgh Conference on Modeling and Simulation, pp.
2337-2341.

5. (1990) M. A. Soderstrand, K. V. Rangarao and G. Berchin. ENHANCED
FDLS ALGORITHM FOR PARAMETER-BASED SYSTEM IDENTIFICATION FOR AUTOMATIC
TESTING. Proceedings of the 1990 IEEE Midwest Symposium on Circuits
and Systems, pp. 96-99.

6. (1990) G. Berchin and M. A. Soderstrand. A TRANSFORM DOMAIN LEAST
SQUARES BEAMFORMING TECHNIQUE. Proceedings of the IEEE Oceans '90
Conference, pp. 481-485.

7. (1995) M. A. Soderstrand, G. Berchin and R. S. Roberts. FREQUENCY
DOMAIN LEAST-SQUARES SYSTEM IDENTIFICATION. International Journal of
Electronics, Vol. 78, No. 1, pp. 25-35.

I actually contributed to only 1, 2, 3, and 6; the others are really
attributions. Article 3 is especially interesting.

Greg
Reply With Quote
  #19 (permalink)  
Old 12-04-2007, 07:55 PM
Andor
Guest
 
Posts: n/a
Default Re: Nearest IIR System to FIR?

On 4 Dez., 16:54, Greg Berchin <[email protected]> wrote:
> On Dec 4, 10:12 am, Andor <[email protected]> wrote:
>
> > His Berchiness speaks ... :-)

>
> Hahahahahaha ... if you only knew ... ;-)


I'm all ears!

>
> > I guess I don't have to tell you that your method is a neat
> > generalization of Shanks's, which is a neat generalization of
> > Prony's.

>
> I have to admit that it's been literally more than two decades since I
> studied any of these approximation techniques. Even to resurrect FDLS
> after all this time I had to dust-off a lot of forgotten knowledge.
>
> >I don't know why it is not more commonly known as Berchin's.

>
> Well, until the Tips and Tricks article, it had been completely lost
> to history. I do appreciate the attribution. In case it ever does
> become known as "Berchin's", I should acknowledge the contribution of
> Randy Roberts, a fellow graduate student at UCDavis who one day made
> an off-hand comment about implementation of difference equations ...
> that triggered the "aha moment" ... that led to my development of the
> algorithm.
>
> > By the way, for the published application of your method (frequency
> > domain filter design), I would have used the infinity (Chebyshev)
> > norm instead of the 2-norm.

>
> At the time FDLS was developed, I had just taken a graduate course in
> adaptive systems that included a basic tutorial on system
> identification techniques, and I had just learned about time domain
> least-squares identification (white noise in; colored noise out; find
> pseudoinverse of resulting Toeplitz matrix). FDLS was quite literally
> just a reformulation of that problem, using sinewaves instead of white
> noise. The matrix became Vandermonde instead of Toeplitz, but
> otherwise the technique remained the same.
>
> If you have ideas about how to reformulate using the infinity-norm, I
> encourage you to pursue them!


I have. Just recently, I used your method and (superficially) compared
it to SMcB system identification. And I used the infinity norm for
minimization, just to show that it was superior to 2-norm minimization
if the additive noise is uniform and not Gaussian (in the uniform
case, 2-norm minimization is biased!). I sort of did that by hand (re-
formulating the linear equation as a linear programming problem), just
to see if I could still do it. It was an entertaining afternoon!

> I have always maintained that the
> technique had a lot of untapped potential.


I agree.

>
> Thanks for your kind words.
>
> Greg


Regards,
Andor
Reply With Quote
  #20 (permalink)  
Old 12-04-2007, 08:13 PM
Greg Berchin
Guest
 
Posts: n/a
Default Re: Nearest IIR System to FIR?

Andor wrote:

> > Hahahahahaha ... if you only knew ... ;-)

>
> I'm all ears!


I'm really an artificial intelligence program running on an IBM PC XT.

> > If you have ideas about how to reformulate using the infinity-norm, I
> > encourage you to pursue them!

>
> I have. Just recently, I used your method and (superficially) compared
> it to SMcB system identification. And I used the infinity norm for
> minimization, just to show that it was superior to 2-norm minimization
> if the additive noise is uniform and not Gaussian (in the uniform
> case, 2-norm minimization is biased!).


Take a look at:
(1989) G. Berchin and M. A. Soderstrand. A TOTAL LEAST SQUARES
APPROACH TO FREQUENCY DOMAIN SYSTEM IDENTIFICATION. IEEE Midwest
Symposium on Circuits and Systems, pp. 709-711.

This article shows how all errors can be confined to a single diagonal
submatrix. I wonder if more modern optimization techniques might be
applied to good effect.

> I sort of did that by hand (re-
> formulating the linear equation as a linear programming problem), just
> to see if I could still do it. It was an entertaining afternoon!


I'm excited about alternate formulations using different error
criteria. Hey; I'm excited just to see the technique being put to use
after all this time.

Greg
Reply With Quote
  #21 (permalink)  
Old 12-04-2007, 10:25 PM
Guest
 
Posts: n/a
Default Re: Nearest IIR System to FIR?

Try Prony's method!

http://cnx.org/content/m12762/latest/


On Dec 3, 9:02 pm, Chris Maryan <[email protected]> wrote:
> Roughly: I have a model in an FIR form that I would like to change to
> an IIR form (for various reasons that I'll spare you from). I'm
> interested in finding the "nearest" IIR filter of order N to some
> given FIR filter ("nearest" meaning in some reasonable metric). Are
> there any standard approaches to this or should I just clobber away
> and see what happens if I try this in some minimization formulation
> under some aptly chosen norm?
>
> i.e. given y_t = h * x_t (where h is the FIR impulse response)
> I'd like to approximate as closely as possibly this with
> y_t = a*y_(t-1) + b*x_t
> where the length of b is substantially smaller than the length of h,
> perhaps 1, perhaps arbitrarily specified by me
> and the length of a is specified by me.
>
> Any thoughts?
>
> Thanks,
>
> Chris


Reply With Quote
  #22 (permalink)  
Old 12-04-2007, 11:51 PM
Vladimir Vassilevsky
Guest
 
Posts: n/a
Default Re: Nearest IIR System to FIR?



Andor wrote:

> By the way, for the published application of your method (frequency
> domain filter design), I would have used the infinity (Chebyshev) norm
> instead of the 2-norm.


Your Andorness knows a deterministic way to compute a pseudoinverse
using a Chebyshev norm? This is a multimodal problem; how do you find
the global optimum?


Vladimir Vassilevsky
DSP and Mixed Signal Design Consultant
http://www.abvolt.com
Reply With Quote
  #23 (permalink)  
Old 12-05-2007, 02:31 AM
Peter K.
Guest
 
Posts: n/a
Default Re: Nearest IIR System to FIR?

Vladimir Vassilevsky <[email protected]> writes:

> Andor wrote:
>
> > By the way, for the published application of your method (frequency
> > domain filter design), I would have used the infinity (Chebyshev) norm
> > instead of the 2-norm.

>
> Your Andorness knows a deterministic way to compute a pseudoinverse
> using a Chebyshev norm? This is a multimodal problem; how do you find
> the global optimum?


I agree. The general Chebyshev norm problem is a hard problem.

The Hankel norm does allow closed-form solution and is _like_ the
Chebyshev norm, but that's not quite the same thing.

Ciao,

Peter K.

--
"And he sees the vision splendid
of the sunlit plains extended
And at night the wondrous glory of the everlasting stars."


Reply With Quote
  #24 (permalink)  
Old 12-05-2007, 02:22 PM
Rick Lyons
Guest
 
Posts: n/a
Default Re: Nearest IIR System to FIR?

On Mon, 3 Dec 2007 21:02:39 -0800 (PST), Chris Maryan
<[email protected]> wrote:

(snipped)

>and the length of a is specified by me.
>
>Any thoughts?
>
>Thanks,
>Chris


Hi Chris,
as you can tell, you're problem is not
particularly easy to solve.
You might take a look at the article
"Designing Nonstandard Digital Filters With
Differential Evolution" (by Rainer Storn)
on page 103 of the January 2005 issue of the
IEEE Signal Processing magazine.

That article discusses *another* method of
designing IIR filters based on some
"desired frequency response".

Good Luck,
[-Rick-]

Reply With Quote
  #25 (permalink)  
Old 12-12-2007, 10:56 AM
Andor
Guest
 
Posts: n/a
Default Re: Nearest IIR System to FIR?

Vladimir Vassilevsky wrote:
> Andor wrote:
> > By the way, for the published application of your method (frequency
> > domain filter design), I would have used the infinity (Chebyshev) norm
> > instead of the 2-norm.

>
> Your Andorness knows a deterministic way to compute a pseudoinverse
> using a Chebyshev norm? This is a multimodal problem; how do you find
> the global optimum?


Well Count Vladimir, we are just applying the tools of the trade.
Let's say we have an overdetermined linear equation system
characterzied by the nxm matrix A (n>m) and an nx1 vector y. We want
to find an mx1 vector x such that

r = A x - y

satisfies some optimimality criterion. To find x such that

max |r_i|, 1<=i<=n,

is minimized (minimax problem), we restate the problem by adding two
new unknowns, u and v. What we want is to

minimize (u + v)

under the constraints

A x - y <= u
y - A x <= v
u > 0
v > 0.

Plug these into your next linear programming solver, and out pops the
minimax solution.

Regards,
Andor
Reply With Quote
Reply

Bookmarks

Thread Tools
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are On


Similar Threads
Thread Thread Starter Forum Replies Last Post
using system ACE for generic app data storage - file system intelligencerequired? Jeff Cunningham FPGA 1 03-13-2007 06:47 PM
System Ace Eli Hughes FPGA 0 04-04-2006 03:44 PM
nearest neighbour [email protected] DSP 0 06-16-2005 02:59 PM
LTI system and Non LTI system Abdul DSP 11 02-16-2005 04:59 PM
Re: nearest spectrum Raymond Toy DSP 1 09-26-2003 12:23 PM


All times are GMT +1. The time now is 05:52 PM.


Powered by vBulletin® Version 3.8.0
Copyright ©2000 - 2019, Jelsoft Enterprises Ltd.
Search Engine Friendly URLs by vBSEO 3.2.0
Copyright 2008 @ FPGA Central. All rights reserved