Re: [music-dsp] Time Varying BIBO Stability Analysis of Trapezoidal integrated optimised SVF v2

2013-11-13 Thread Andrew Simper
Thanks very much Ross for taking the time to look at this! There is a lot
of reading and theory so until I get some more time I personally can't
really take on board any of it to provide you with any useful comments, but
I appreciate your time.

All the best,

Andy
--
cytomic - sound music software


On 10 November 2013 23:58, Ross Bencina rossb-li...@audiomulch.com wrote:

 Hi Everyone,

 I took a stab at converting Andrew's SVF derivation [1] to a state space
 representation and followed Laroche's paper to perform a time varying BIBO
 stability analysis [2]. Please feel free to review and give feedback. I
 only started learning Linear Algebra recently.

 Here's a slightly formatted html file:

 http://www.rossbencina.com/static/junk/SimperSVF_BIBO_Analysis.html

 And the corresponding Maxima worksheet:

 http://www.rossbencina.com/static/junk/SimperSVF_BIBO_Analysis.wxm

 I had to prove a number of the inequalities by cut and paste to Wolfram
 Alpha, if anyone knows how to coax Maxima into proving the inequalities I'm
 all ears. Perhaps there are some shortcuts to inequalities on rational
 functions that I'm not aware of. Anyway...

 The state matrix X:

 [ic1eq]
 [ic2eq]

 The state transition matrix P:

 [-(g*k+g^2-1)/(g*k+g^2+1), -(2*g)/(g*k+g^2+1) ]
 [(2*g)/(g*k+g^2+1),(g*k-g^2+1)/(g*k+g^2+1)]

 (g  0, k  0 = 2)

 Laroche's method proposes two time varying stability criteria both using
 the induced Euclidian (p2?) norm of the state transition matrix:

 Either:

 Criterion 1: norm(P)  1 for all possible state transition matrices.

 Or:

 Criterion 2: norm(TPT^-1)  1 for all possible state transition matrices,
 for some fixed constant change of basis matrix T.

 norm(P) can be computed as the maximum singular value or the positive
 square root of the maximum eigenvalue of P.transpose(P). I've taken a
 shortcut and not taken square roots since we're testing for norm(P)
 strictly less than 1 and the square root doesn't change that.

 From what I can tell norm(P) is 1, so the trapezoidal SVF filter fails to
 meet Criterion 1.

 The problem with Criterion 2 is that Laroche doesn't tell you how to find
 the change of basis matrix T. I don't know enough about SVD, induced p2
 norm or eigenvalues of P.P' to know whether it would even be possible to
 cook up a T that will reduce norm(P) for all possible transition matrices.
 Is it even possible to reduce the norm of a unit-norm matrix by changing
 basis?

 From reading Laroche's paper it's not really clear whether there is any
 way to prove Criterion 2 for a norm-1 matrix. He kind-of side steps the
 issue with the norm=1 Normalized Ladder and ends up proving that
 norm(P^2)1. This means that the Normalized Ladder is time-varying BIBO
 stable for parameter update every second sample.

 Using Laroche's method I was able to show that Andrew's trapezoidal SVF
 (state transition matrix P above) is also BIBO stable for parameter update
 every second sample. This is the final second of the linked file above.

 If anyone has any further insights on Criterion 2 (is it possible that T
 could exist?) I'd be really interested to hear about it.

 Constructive feedback welcome :)

 Thanks,

 Ross


 [1] Andrew Simper trapazoidal integrated SVF v2
 http://www.cytomic.com/files/dsp/SvfLinearTrapOptimised2.pdf

 [2] On the Stability of Time-Varying Recursive Filters
 http://www.aes.org/e-lib/browse.cfm?elib=14168
 --
 dupswapdrop -- the music-dsp mailing list and website:
 subscription info, FAQ, source code archive, list archive, book reviews,
 dsp links
 http://music.columbia.edu/cmc/music-dsp
 http://music.columbia.edu/mailman/listinfo/music-dsp

--
dupswapdrop -- the music-dsp mailing list and website:
subscription info, FAQ, source code archive, list archive, book reviews, dsp 
links
http://music.columbia.edu/cmc/music-dsp
http://music.columbia.edu/mailman/listinfo/music-dsp


Re: [music-dsp] Time Varying BIBO Stability Analysis of Trapezoidal integrated optimised SVF v2

2013-11-11 Thread Vadim Zavalishin

Hi Ross,

since you opened this topic, I thought I'd try to share the intermediate 
results my findings, as much as I can remember them (that was a few 
years back). Most of them concern the continuous time case.


First note regarding the continuous time case is that cutoff modulations 
do not affect the BIBO stability at all. More rigorously:
- if the cutoff modulation is done by varying the gains *in front* 
(rather than behind) of *all* integrators in the system

- if the cutoff function w(t) is always positive
- if the system is BIBO stable for some cutoff function w(t)
then the system is also BIBO stable for any other positive cutoff function

Particularly, if a linear system is BIBO-stable in time-invariant case 
(for the constant cutoff function), then it's also stable for varying 
cutoff.


This is very easy to obtain from the state-space equation:
du/dt=w*F(u,x)
where u(t) is the state vector, x(t) is the input vector, w(t) is the 
cutoff scalar function and F(u,x,t) is the nonlinear time-varying 
version of A*u+B*x. Without reduction of generality we can assume w(t)=1 
for the given stable case. Then, we simply rewrite the equation as

du/(w*dt)=F(u,x)
and substitute the time parameter:
d tau = w*dt
Now in tau time coordinates the modulated system is exactly the same 
as the unmodulated one in the t coordinates.


The same doesn't seem to hold for the TPT discrete-time version, though.


In a more general case for *linear* continuous time, IIRC, we have a 
sufficient (but it seems, not necessary) time-varying stability 
criterion: all eigenvalues of the matrix A+A^T must be uniformly 
negative, that is they must be bounded by some negative number from 
above. It is essential to require this uniform negativity, otherwise the 
eigenvalues can get arbitrarily close to the self-oscillation case. This 
condition is simply obtained from the fact that in the absence of the 
input signal you want the absolute value of the state to decay with a 
relative speed, which is uniformly less that 1. This will make sure, 
that, whatever the bound of the input signal is, a large enough state 
will decay sufficiently fast, to win over the input vector B(t)*x(t). 
Indeed, ignoring the B*x term, we have

(d/dt) |u|^2=(d/dt)(u^T*u)=u'^T*u+u^T*u'=
(A*u)^T*u+u^T*(A*u)=u^T*A^T*u+u^T*A*u=
u^T*(A+A^T)*u=|u|^2*max{lambda_i}
where lambda_i are the eigenvalues of A+A^T.
Now on the other hand
(d/dt) |u|^2=2*|u|*(d/dt)|u|
So
2*|u|*(d/dt)|u|=|u|^2*max{lambda_i}
and
2*(d/dt)|u|=|u|*max{lambda_i}

Obviously, you don't have to satisfy the condition in the original 
state-space coordinates. Instead, you can satisfy it in any other 
coordinates, which corresponds to using P^T*A*P instead of A for some 
nonsingular matrix P.


Now I didn't manage to get this condition satisfied for the 
continuous-time SVF. Reading your post, I admit, that I could have made 
a mistake there, but FWIW... First, I discarded the consideration of 
varying cutoff, as explained above and concentrated on the varying 
damping. Not managing to find a matrix P, I constructed an input signal, 
requiring the maximum possible growth of the state vector. The signal, 
IIRC was either sgn(s_1) or -sgn(s_1), where s_1 is the first of the 
state components (or it could have been s_2). Then I noticed that for 
low damping the state vector is moving in almost a circle, while for 
higher damping (but still with complex poles) is turns into an ellipse. 
This was exactly the problem: in principle the circle is having a 
bigger size, than the ellipse, but by switching the damping from low to 
high you could shoot the state point into a much higher orbit. Much 
worse, in certain cases the system state can increase even in the full 
absence of the input signal!!! However, IIRC, I managed to show, that 
for a sufficiently large elliptic orbit (with high damping), 
(d/dt)|u|^2=0 regardless of the current damping. Since we are already 
considering the worst possible input signal, the system state can't 
cross this boundary orbit to the outside.


For the discrete-time case the situation is more complicated, because we 
can't use the continuity of the state vector function. IIRC, I also 
didn't manage to build the worst-case signal, but there was the same 
problem of the state vector becoming larger in the absence of the input 
signal. That's why I was somewhat surprised that you simply managed to 
restrict the eigenvalues of the system matrix in some coordinates. 
Particularly suspicious is that your coordinate transformation matrix is 
built for the smallest damping, while the more problematic case seems 
to occur at the larger damping. But, as I said, I didn't finish that 
research and I could have been wrong. So just take my input FWIW.


Regards,
Vadim

--
Vadim Zavalishin
Reaktor Application Architect
Native Instruments GmbH
+49-30-611035-0

www.native-instruments.com
--
dupswapdrop -- the music-dsp mailing list and website:
subscription info, FAQ, source code archive, 

Re: [music-dsp] Time Varying BIBO Stability Analysis of Trapezoidal integrated optimised SVF v2

2013-11-11 Thread Ross Bencina

Hi Vadim,

Thanks for your feedback...

On 11/11/2013 9:52 PM, Vadim Zavalishin wrote:
[snip on the analog stuff]


For the discrete-time case the situation is more complicated, because we
can't use the continuity of the state vector function. IIRC, I also
didn't manage to build the worst-case signal, but there was the same
problem of the state vector becoming larger in the absence of the input
signal.


Interesting


That's why I was somewhat surprised that you simply managed to
restrict the eigenvalues of the system matrix in some coordinates.


To be clear: the eigenvalues of the transition matrix only cover 
time-invariant stability.


The constraint for time-varying BIBO stability is that all transition 
matrices P satisfy ||TPT^-1||  1 where ||.|| is the spectral norm and T 
is some constant non-singular change of base matrix.


The main reason I am suspicious is that Laroche does not even try to 
cook up a change of basis matrix, or to show when it might be achieved. 
It's kind of an orphan result in that paper that goes unused for showing 
BIBO stability.



Particularly suspicious is that your coordinate transformation matrix is
built for the smallest damping, while the more problematic case seems
to occur at the larger damping.


I'm not sure I follow you here. Smallest damping means most resonance, 
where the system decays most slowly. Don't you think this would be where 
the greatest problems would arise?


 But, as I said, I didn't finish that

research and I could have been wrong. So just take my input FWIW.


I have made a slightly cleaner cook-up of the change of basis matrix. 
This seems a lot like the uniformly negative criteria you mentioned. 
It could be read that k must be uniformly positive:


http://www.rossbencina.com/static/junk/2x2ChangedBasisNorm.html

In short, using change of basis matrix T:
[1 f]
[0 1]

We have the time-varying BIBO stability constraint:

0  f  2, g  0, f  k = 2

f provides the bound on k from below.

Ross.

--
dupswapdrop -- the music-dsp mailing list and website:
subscription info, FAQ, source code archive, list archive, book reviews, dsp 
links
http://music.columbia.edu/cmc/music-dsp
http://music.columbia.edu/mailman/listinfo/music-dsp


Re: [music-dsp] Time Varying BIBO Stability Analysis of Trapezoidal integrated optimised SVF v2

2013-11-11 Thread Vadim Zavalishin

On 11-Nov-13 15:32, Ross Bencina wrote:

That's why I was somewhat surprised that you simply managed to
restrict the eigenvalues of the system matrix in some coordinates.


To be clear: the eigenvalues of the transition matrix only cover
time-invariant stability.

The constraint for time-varying BIBO stability is that all transition
matrices P satisfy ||TPT^-1||  1 where ||.|| is the spectral norm and T
is some constant non-singular change of base matrix.


Okay, for the time-varying case it seems to be the eigenvalues of 
(P^T)*P in the discrete-time case, which according to Wikipedia define 
the spectral norm (while in the continuous time we have the eigenvalues 
of P^T+P). I'm currently a little short of time to take a precise look 
at all the details. Still, in both cases we are talking about some 
uniform property of eigenvalues of a symmetric matrix. In the discrete 
time they need to be smaller than one to kind of make sure the next 
state vector is smaller than the previous one (I think). In the 
continuous time case they need to be negative to kind of make sure that 
the time derivative of the state vector's length is negative.




The main reason I am suspicious is that Laroche does not even try to
cook up a change of basis matrix, or to show when it might be achieved.
It's kind of an orphan result in that paper that goes unused for showing
BIBO stability.


IIRC from briefly reading his paper, his sufficient criterion turned out 
to be not applicable for the DF filters (which by themselves also didn't 
seem to be time-variant BIBO-stable, IIRC), therefore he resorted to 
some other approaches. That (and my own SVF investigation) led me to 
consider this kind of criterion as a more or less useless one at that 
time. But I may be wrong, it was a while ago and only a brief look.





Particularly suspicious is that your coordinate transformation matrix is
built for the smallest damping, while the more problematic case seems
to occur at the larger damping.


I'm not sure I follow you here. Smallest damping means most resonance,
where the system decays most slowly. Don't you think this would be where
the greatest problems would arise?


Because of the shooting effect I described earlier. I discovered it by 
a numerical simulation of the system. For the low resonance the state 
vector moves in an ellipse (for the worst-case signal I described). 
The orientation and the amount of stretching of the ellipse depends on 
the resonance (the lower the resonance the more the stretch). You can 
suddenly switch to a lower resonance while your state vector is pointing 
at such angle, that the respective position on the new ellipse is within 
the increasing radius area. This will cause the state vector to grow.


Disclaimer: this all goes under the notice that I didn't double-check my 
results or may even have forgotten some important details or simply 
remember them wrong. I was posting them mostly because I thought they 
might be interesting and/or usable to some extent for you (and maybe 
others).




In short, using change of basis matrix T:
[1 f]
[0 1]

We have the time-varying BIBO stability constraint:

0  f  2, g  0, f  k = 2

f provides the bound on k from below.


This is also the kind of the result which I would intuitively expect at 
the first thought. It's just contradicting the *unverified* results of 
my earlier research, that's why I expressed my suspiciousness. 
Hopefully, I'll find time to check your research in more detail.


Regards,
Vadim

--
Vadim Zavalishin
Reaktor Application Architect
Native Instruments GmbH
+49-30-611035-0

www.native-instruments.com
--
dupswapdrop -- the music-dsp mailing list and website:
subscription info, FAQ, source code archive, list archive, book reviews, dsp 
links
http://music.columbia.edu/cmc/music-dsp
http://music.columbia.edu/mailman/listinfo/music-dsp


Re: [music-dsp] Time Varying BIBO Stability Analysis of Trapezoidal integrated optimised SVF v2

2013-11-10 Thread Ross Bencina

With reference to my previous message:

It looks like there is a change of basis matrix T that can be used to 
satisfy Laroche's Criterion 2 (time varying BIBO stability at full audio 
rate), at least for k  0.


T:

[ 0, 1]
[ 1, -1/1 ]

This matrix requires k  1/1 but it seems that the lower bound on  k 
can approaches zero as the 2,2 entry approaches zero from below.


Hopefully I'm not imagining things.

Ross.



On 11/11/2013 2:58 AM, Ross Bencina wrote:

Hi Everyone,

I took a stab at converting Andrew's SVF derivation [1] to a state space
representation and followed Laroche's paper to perform a time varying
BIBO stability analysis [2]. Please feel free to review and give
feedback. I only started learning Linear Algebra recently.

Here's a slightly formatted html file:

http://www.rossbencina.com/static/junk/SimperSVF_BIBO_Analysis.html

And the corresponding Maxima worksheet:

http://www.rossbencina.com/static/junk/SimperSVF_BIBO_Analysis.wxm

I had to prove a number of the inequalities by cut and paste to Wolfram
Alpha, if anyone knows how to coax Maxima into proving the inequalities
I'm all ears. Perhaps there are some shortcuts to inequalities on
rational functions that I'm not aware of. Anyway...

The state matrix X:

[ic1eq]
[ic2eq]

The state transition matrix P:

[-(g*k+g^2-1)/(g*k+g^2+1), -(2*g)/(g*k+g^2+1) ]
[(2*g)/(g*k+g^2+1),(g*k-g^2+1)/(g*k+g^2+1)]

(g  0, k  0 = 2)

Laroche's method proposes two time varying stability criteria both using
the induced Euclidian (p2?) norm of the state transition matrix:

Either:

Criterion 1: norm(P)  1 for all possible state transition matrices.

Or:

Criterion 2: norm(TPT^-1)  1 for all possible state transition
matrices, for some fixed constant change of basis matrix T.

norm(P) can be computed as the maximum singular value or the positive
square root of the maximum eigenvalue of P.transpose(P). I've taken a
shortcut and not taken square roots since we're testing for norm(P)
strictly less than 1 and the square root doesn't change that.

 From what I can tell norm(P) is 1, so the trapezoidal SVF filter fails
to meet Criterion 1.

The problem with Criterion 2 is that Laroche doesn't tell you how to
find the change of basis matrix T. I don't know enough about SVD,
induced p2 norm or eigenvalues of P.P' to know whether it would even be
possible to cook up a T that will reduce norm(P) for all possible
transition matrices. Is it even possible to reduce the norm of a
unit-norm matrix by changing basis?

 From reading Laroche's paper it's not really clear whether there is any
way to prove Criterion 2 for a norm-1 matrix. He kind-of side steps the
issue with the norm=1 Normalized Ladder and ends up proving that
norm(P^2)1. This means that the Normalized Ladder is time-varying BIBO
stable for parameter update every second sample.

Using Laroche's method I was able to show that Andrew's trapezoidal SVF
(state transition matrix P above) is also BIBO stable for parameter
update every second sample. This is the final second of the linked file
above.

If anyone has any further insights on Criterion 2 (is it possible that T
could exist?) I'd be really interested to hear about it.

Constructive feedback welcome :)

Thanks,

Ross


[1] Andrew Simper trapazoidal integrated SVF v2
http://www.cytomic.com/files/dsp/SvfLinearTrapOptimised2.pdf

[2] On the Stability of Time-Varying Recursive Filters
http://www.aes.org/e-lib/browse.cfm?elib=14168
--
dupswapdrop -- the music-dsp mailing list and website:
subscription info, FAQ, source code archive, list archive, book reviews,
dsp links
http://music.columbia.edu/cmc/music-dsp
http://music.columbia.edu/mailman/listinfo/music-dsp


--
dupswapdrop -- the music-dsp mailing list and website:
subscription info, FAQ, source code archive, list archive, book reviews, dsp 
links
http://music.columbia.edu/cmc/music-dsp
http://music.columbia.edu/mailman/listinfo/music-dsp