Hi! I'm hoping here's someone who can help me with a "hairy" matrix equation. I stumbled upon this developing my lossless audio codec. I have this: e = r^T * (R^-1 - A^T * (A*R*A^T)^-1 * A) * r, where r is 1xk vector (lags 1 to k of autocorrelation), R is kxk matrix (autocorrelation matrix) and it's usually positive definite, A = [I 0]^T of size (k-1)xk, ie. (k-1)x(k-1) identity matrix padded with zero vector. Now, the task is to calculate or estimate e, without expensive operations such as matrix inversion. Perhaps I'm asking too much, but it would be useful. Even a rough estimate. I have pretty much nothing so far, but one intresting property seems to hold: matrix (R^-1 - A^T * (A*R*A^T)^-1 * A) has only one non-zero eigenvalue (note: this is based solely on experimentation). If someone is familiar with equations of this form or is otherwise intrested, please help. ---- Jani Huhtanen Tampere University of Technology, Pori

# Matrix equation

Started by ●November 8, 2005

Reply by ●November 8, 20052005-11-08

Hi Jani, first of all your matrix looks like a Schur complement, and is in a form that may be simplified by using the matrix inversion lemma. Google will help you with both of these. Also look for papers on MMSE equalisation by John Cioffi and Naofal Al-Dhahir. Secondly, it is quite possible that this quadratic form (term inside r^T (*) r) is positive definite and of full rank, in which case the value e is minimised by choosing r as the eigenvector corresponding to the minimum eigenvalue of the quadratic form. This might not help you since it appears that your r is fixed (up to a delay) but if you give the context of the problem, I might be able to give you some better insight. I've worked with equations of that form for years, as I expect have many of the comp.dsp crew. You could do worse than get yourself a book on linear algebra. Kailath covers everything but I find his text quite impenetrable. A softer introduction should suffice (suggestions anyone???) Porterboy

Reply by ●November 9, 20052005-11-09

Jani Huhtanen wrote:> Hi! > > I'm hoping here's someone who can help me with a "hairy" matrix equation. I > stumbled upon this developing my lossless audio codec. I have this: > > e = r^T * (R^-1 - A^T * (A*R*A^T)^-1 * A) * r, where > > r is 1xk vector (lags 1 to k of autocorrelation), > R is kxk matrix (autocorrelation matrix) and it's usually positive definite, > A = [I 0]^T of size (k-1)xk, ie. (k-1)x(k-1) identity matrix padded with > zero vector. > > Now, the task is to calculate or estimate e, without expensive operations > such as matrix inversion. Perhaps I'm asking too much, but it would be > useful. Even a rough estimate. > > I have pretty much nothing so far, but one intresting property seems to > hold: matrix (R^-1 - A^T * (A*R*A^T)^-1 * A) has only one non-zero > eigenvalue (note: this is based solely on experimentation). > > If someone is familiar with equations of this form or is otherwise > intrested, please help. > > ---- > Jani Huhtanen > Tampere University of Technology, PoriIf I'm not mistaken that equation, and a way to use it to reduce a problem to inverting a 1x1 matrix, can be found in "Adaptive Control" by Astrom -- I'd say for sure but it's up there and I'm down here and it's cold outside and late. -- Tim Wescott Wescott Design Services http://www.wescottdesign.com

Reply by ●November 9, 20052005-11-09

porterboy76@yahoo.com wrote:> Hi Jani, > > first of all your matrix looks like a Schur complement, and is in a > form that may be simplified by using the matrix inversion lemma. Google > will help you with both of these. Also look for papers on MMSE > equalisation > by John Cioffi and Naofal Al-Dhahir.OK, I'll look for these.> > Secondly, it is quite possible that this quadratic form (term inside > r^T (*) r) is positive definite and of full rank, in which case the > value e is minimised by choosing r as the eigenvector corresponding to > the minimum eigenvalue of the quadratic form. This might not help you > since it appears that your r is fixed (up to a delay) but if you give > the context of the problem, I might be able to give you some better > insight. I've worked with equations of that form for years, as I expect > have > many of the comp.dsp crew.OK, perhaps I should explain a little bit more. r is fixed as are R, and A. This equation gives difference of MSE of linear prediction between order k and order k-1. MSE of my linear predictor is given like this: mse = sum(x[n]^2) - r^T * R^-1 * r, where r is again 1xk and R is kxk This removes the last lag of an autocorr: r_(k-1) = A*r_k, where _n refers to the order and this gives the last principal leading submatrix of R: R_(k-1) = A*R_k*A', where _n again refers to order of the prediction Now MSE of order k-1 is given by mse_(k-1) = sum(x[n]^2) - r_(k-1)^T * R_(k-1)^-1 * r_(k-1) Now calculating the difference of these two MSE:s we get the equation I gave in my first post. Equation which is "easy" calculate, but requires way too much operations to be practical for order estimation (which is what I'm trying to do here). This> You could do worse than get yourself a book > on linear algebra. Kailath covers everything but I find his text quite > impenetrable. A softer introduction should suffice (suggestions > anyone???) >I have read my linear algebra in uni, altough there's always room for improvement. Yesterday I got Goldbergs "Matrix Theory with Applications" and it seem promising (at least the part with quadratic forms).> PorterboyThanks for your help! -- ---- Jani Huhtanen Tampere University of Technology, Pori

Reply by ●November 9, 20052005-11-09

"Jani Huhtanen" <jani.huhtanen@kolumbus.fi> wrote in message news:dkqn46$5hq$1@phys-news1.kolumbus.fi...> Hi! > > I'm hoping here's someone who can help me with a "hairy" matrix equation.I> stumbled upon this developing my lossless audio codec. I have this: > > e = r^T * (R^-1 - A^T * (A*R*A^T)^-1 * A) * r, where > > r is 1xk vector (lags 1 to k of autocorrelation), > R is kxk matrix (autocorrelation matrix) and it's usually positivedefinite,> A = [I 0]^T of size (k-1)xk, ie. (k-1)x(k-1) identity matrix padded with > zero vector. > > Now, the task is to calculate or estimate e, without expensive operations > such as matrix inversion. Perhaps I'm asking too much, but it would be > useful. Even a rough estimate. > > I have pretty much nothing so far, but one intresting property seems to > hold: matrix (R^-1 - A^T * (A*R*A^T)^-1 * A) has only one non-zero > eigenvalue (note: this is based solely on experimentation). > > If someone is familiar with equations of this form or is otherwise > intrested, please help. > > ---- > Jani Huhtanen > Tampere University of Technology, PoriHi Jani, maybe ppLinear could calculate this just write everything out using its syntax and stick values in for A ,R, and r....see www.pecos-place.com regards.... Bill

Reply by ●November 10, 20052005-11-10

Bill Shortall wrote:> > "Jani Huhtanen" <jani.huhtanen@kolumbus.fi> wrote in message > news:dkqn46$5hq$1@phys-news1.kolumbus.fi... >> Hi! >> >> I'm hoping here's someone who can help me with a "hairy" matrix equation. > I >> stumbled upon this developing my lossless audio codec. I have this: >> >> e = r^T * (R^-1 - A^T * (A*R*A^T)^-1 * A) * r, where >> >> r is 1xk vector (lags 1 to k of autocorrelation), >> R is kxk matrix (autocorrelation matrix) and it's usually positive > definite, >> A = [I 0]^T of size (k-1)xk, ie. (k-1)x(k-1) identity matrix padded with >> zero vector. >> >> Now, the task is to calculate or estimate e, without expensive operations >> such as matrix inversion. Perhaps I'm asking too much, but it would be >> useful. Even a rough estimate. >> >> I have pretty much nothing so far, but one intresting property seems to >> hold: matrix (R^-1 - A^T * (A*R*A^T)^-1 * A) has only one non-zero >> eigenvalue (note: this is based solely on experimentation). >> >> If someone is familiar with equations of this form or is otherwise >> intrested, please help. >> >> ---- >> Jani Huhtanen >> Tampere University of Technology, Pori > > Hi Jani, > maybe ppLinear could calculate this > just write everything out using its > syntax and stick values in for A ,R, > and r....see > > www.pecos-place.com > > regards.... BillI know how to calculate the e because both R and A*R*A^T are invertible and there's no unknowns (except e). This is not the problem. The problem is that the calculation of e is a way too expensive operation and I need a another way to do it faster, even with the expense of accurary. Thus some approximation of e would be great. -- Jani Huhtanen Tampere University of Technology, Pori

Reply by ●November 10, 20052005-11-10

Hi again, Can anyone explain the one non-zero eigenvalue i'm getting for the matrix (R^-1 - A^T * (A*R*A^T)^-1 * A)? It clearly has something to do with the way A modifies R and (A*R*A^T)^-1. If it wasn't clear what A does before let me explain a bit more: As I said earlier A = [I 0]^T of size (k-1)xk, ie. (k-1)x(k-1) identity matrix padded with zero vector. So multiplying R from left with A "removes" the last row of R (thus the size is (k-1)xk). And mult from right with A^T removes the last column (size (k-1)x(k-1)). This matrix now corresponds to the last principal leading submatrix of R. Now multiplying the inverse from left with A^T adds a row with zeros to the "end" and multiplying from right with A adds a zero column (final size kxk). This means that R^-1 last row and last column leaves intact in substraction. Also if I use different A, such that it leaves more zero columns and rows (and more cols and rows of R^-1 stay intact), I get more eigenvalues. To be specific the number of eigenvalues seem to correspond the number of columns or rows left intact in R^-1. This is still only based on experimentation, but I believe it can be proven with basic linear algebra. Can anyone help me with this? -- Jani Huhtanen Tampere University of Technology, Pori

Reply by ●November 10, 20052005-11-10

Jani Huhtanen wrote:> Hi again, > > > Can anyone explain the one non-zero eigenvalue i'm getting for the matrix > (R^-1 - A^T * (A*R*A^T)^-1 * A)?Here is an outline of how I would attempt to prove your conjecture (it might be wrong, I haven't worked out the details): 1. R_k and R_k^-1 are circulant kxk matrices (because R_k is one, and R_k is positive definite => invertible) => they are both diagonalized by the discrete k-point Fourier transform, their eigenvectors are the Fourier basis vectors (all circulant kxk matrices share a common eigenbasis), and their eigenvalues are the coordinates of the Fourier transform of the (one-sided) autocorrelation vector r_k (the generating vector for R_k). 2. R_{k-1} = (A*R*A^T) and R_{k-1}^-1 = (A*R*A^T)^-1 are circulant (k-1)x(k-1) matrices, so the above applies as well, with the (k-1)-point Fourier transform. 3. Show that for S_k := A^T * (A*R_k*A^T)^-1 * A, the kernel for R_k^-1 - S_k is a {k-1}-dimensional subspace. Use the eigendecompositions from above. You will most probably need the fact that the sum of the n unity roots equals to zero. 4. You're done by linearity. Presumably, point 3 needs some work. Regards, Andor

Reply by ●November 10, 20052005-11-10

I wrote:> 4. You're done by linearity.Sorry, that was from another recipe. It should rather say: 4. Show that the space spanned by the only non-kernel dimension is also an eigenspace of R_k^-1 - S_k. I think this should follow from your calculations under point 3. Regards, Andor

Reply by ●November 10, 20052005-11-10

abariska@student.ethz.ch wrote:> ... > 1. R_k and R_k^-1 are circulant kxk matrices (because R_k is one, and > R_k is positive definite => invertible)Unfortunately they are not. Altough I'm willing to do that approximation (because R is "almost circulant"), if it considerably helps in this situation. I calculate the matrix R as follows: Let X[n] = [x[n-1], x[n-2], ... , x[n-k]]^T a vector of size kx1 composed of k past samples of signal x. then R = sum(X[n]*X[n]^T) which is sum of outer products from n=0 to N-1. So R is symmetric and often with large enough N, also positive definite. Particularly with low order (ie small k) and large N, R is very close to circulant matrix.> ... > Regards, > Andor-- Jani Huhtanen Tampere University of Technology, Pori