Solution for AX=B if A is not Square matrix!

Hi all,

I am stuck with a bit difficult problem. Let us consider the follwing
linear matrix Eq.
AX=B
If A is a square matrix then there are direct and indirect(LU/Cholesky
etc
depending on matrix property)  solutions by matrix
inversion. But My problem involves the following matrix dimensions:
A=147 x 5 (Hankel matrix )
X=5 x 1(Number of taps - One dim vector)
B=147 x 1 (Matched filter output.)

So inverse or any of the above solutions are not possible and in fact
there
is no unique solution for X. There might exist several solutions( More
Eqs than unknowns) - we need to pick up optimum one.

Can SVD(singular value decomposition) or some kind of pseudo inverse
help.

Please suggest me a solution which can be implemented in DSP processor
i.e
computation complexity should not grow high.

Thanks in advance.
Santosh

"santosh nath" <santosh.nath@ntlworld.com> wrote in message
news:6afd943a.0309251339.19a0e93b@posting.google.com...
> Hi all,
>
> I am stuck with a bit difficult problem. Let us consider the follwing
> linear matrix Eq.
> AX=B
> If A is a square matrix then there are direct and indirect(LU/Cholesky
> etc
> depending on matrix property)  solutions by matrix
> inversion. But My problem involves the following matrix dimensions:
> A=147 x 5 (Hankel matrix )
> X=5 x 1(Number of taps - One dim vector)
> B=147 x 1 (Matched filter output.)
>
> So inverse or any of the above solutions are not possible and in fact
> there
> is no unique solution for X. There might exist several solutions( More
> Eqs than unknowns) - we need to pick up optimum one.
>
> Can SVD(singular value decomposition) or some kind of pseudo inverse
> help.

I would look at SVD.  There is a description in "Numerical Recipes in C"
that isn't too bad.

-- glen

santosh nath wrote:
> Hi all,
> 
> I am stuck with a bit difficult problem. Let us consider the follwing
> linear matrix Eq.
> AX=B
> If A is a square matrix then there are direct and indirect(LU/Cholesky
> etc
> depending on matrix property)  solutions by matrix
> inversion. But My problem involves the following matrix dimensions:
> A=147 x 5 (Hankel matrix )
> X=5 x 1(Number of taps - One dim vector)
> B=147 x 1 (Matched filter output.)

Hi there.

This is indeed an optimization problem. The equation system is
overspecified - you have 147 equations and 5 variables. Usually, you
cannot satisfy the whole set of equations, you'll always get an error
(residue vector). Let's say you've found some x. Then

A x = r =/= b

and what you really want is that || b - r || is as small as possible,
where ||.|| is some kind of norm. There is a closed form solution if
you use the Euclidian norm, ie. what you commonly think of as the
length of a vector in space. It's called linear least squares fit. It
is the solution x to the equation

A^T A x = A^T b

where A^T is the transpose of A. C := A^T A, a square matrix, is often
badly conditioned, but has the advantage of being symmetric and
positve definite (if the row vectors of A are linearly independent) -
so you can use Cholesky decomposition on C and forwards-backwards
substitution to solve for x

From your comments I gather you know what that means. By the way:
(A^T A)^-1 A^T is the pseudo inverse you mentioned.

Regards,
Andor

Hello,

The problem you are trying to solve is called the "Least Squares"
(LS). Look up "Numerical Linear Algebra" by L.N.Trefethen and D. Bau
III, and you might find a pleathora of algorithms that solve this
specific problem. The solution methods attempt to find the value of X
that minimize the discrepancy between B and AX in the least-squares
(||B-AX||^2) sense.

You need to worry about 2 things... Computational Complexity AND
Numerical Stability for such problems. You were right about SVD, it is
ONE of the methods that are used for solving LS problems. But there
are others: QR factorization, Householder triangularization etc.,

Anyways, it looks like you are trying to solve some sort of spatial
filtering problem. Am I right ?!

Regards,
LL.

llabakudas@yahoo.com (Lord Labakudas) wrote in message news:<d632d29f.0309260513.65e67960@posting.google.com>...
> Hello,
> 
> The problem you are trying to solve is called the "Least Squares"
> (LS). Look up "Numerical Linear Algebra" by L.N.Trefethen and D. Bau
> III, and you might find a pleathora of algorithms that solve this
> specific problem. The solution methods attempt to find the value of X
> that minimize the discrepancy between B and AX in the least-squares
> (||B-AX||^2) sense.
> 
> You need to worry about 2 things... Computational Complexity AND
> Numerical Stability for such problems. You were right about SVD, it is
> ONE of the methods that are used for solving LS problems. But there
> are others: QR factorization, Householder triangularization etc.,
> 
> Anyways, it looks like you are trying to solve some sort of spatial
> filtering problem. Am I right ?!
> 
> Regards,
> LL.

Hi LL,

Probably the best book "Matrix computation" by Golub and Loan is what
I am
using since several years. The way you are looking at the problem is
quite strange to me -either you are new or did not follow my postings
or Andor's
thoughtful comments - which I actually agree and think of. The
methods(by many) what  you are talking about is nice when A is some
sort of square matrix!

Regards,
Santosh

> Probably the best book "Matrix computation" by Golub and Loan is what

I have to agree with you on this one. Golub's book is the best one for
general numerical linear and matrix algebra, but Treffethen's book
concentrates more on LS problems like the one that you posted.

> I am
> using since several years. The way you are looking at the problem is
> quite strange to me -either you are new or did not follow my postings
> or Andor's
> thoughtful comments - which I actually agree and think of. 

I don't understand what you find "strange" about my way of looking at
the problem. The problem you are trying to solve IS a least squares
(LS) problem AND QR factorization, Householder triagularization ARE
few methods to solve LS problems, AND Treffethen's book deals with
such problems.

>The
> methods(by many) what  you are talking about is nice when A is some
> sort of square matrix!

NO, check out the following MATLAB examples. The matrix A in the
following examples are NOT square matrices.

A = randn(147, 5);
b = randn(147, 1);

% Solution using MATLAB mldivide.
% I believe QR factorization is used internally.
x = A\b;

% Solution using pseudoinverse inv(A'*A)*A'
x1 = pinv(A)*b;

% Solution using QR factorization.
[Q, R] = qr(A, 0);
x2 = inv(R)*(Q'*b);

% Solution using SVD.
[U, S, V] = svd(A);
w = pinv(S)*(U'*b);
x3 = V*w;

Hope this helps...

-LL.

llabakudas@yahoo.com (Lord Labakudas) wrote in message news:<d632d29f.0309301124.322aa5c7@posting.google.com>...
> > Probably the best book "Matrix computation" by Golub and Loan is what
> 
> I have to agree with you on this one. Golub's book is the best one for
> general numerical linear and matrix algebra, but Treffethen's book
> concentrates more on LS problems like the one that you posted.
> 
> > I am
> > using since several years. The way you are looking at the problem is
> > quite strange to me -either you are new or did not follow my postings
> > or Andor's
> > thoughtful comments - which I actually agree and think of. 
> 
> I don't understand what you find "strange" about my way of looking at
> the problem. The problem you are trying to solve IS a least squares
> (LS) problem AND QR factorization, Householder triagularization ARE
> few methods to solve LS problems, AND Treffethen's book deals with
> such problems.
> 
> >The
> > methods(by many) what  you are talking about is nice when A is some
> > sort of square matrix!
> 
> NO, check out the following MATLAB examples. The matrix A in the
> following examples are NOT square matrices.
> 
> A = randn(147, 5);
> b = randn(147, 1);
> 
> % Solution using MATLAB mldivide.
> % I believe QR factorization is used internally.
> x = A\b;
> 
> % Solution using pseudoinverse inv(A'*A)*A'
> x1 = pinv(A)*b;
> 
> % Solution using QR factorization.
> [Q, R] = qr(A, 0);
> x2 = inv(R)*(Q'*b);
> 
> % Solution using SVD.
> [U, S, V] = svd(A);
> w = pinv(S)*(U'*b);
> x3 = V*w;
> 
> Hope this helps...
> 
> -LL.

Just to be clear... an earlier post mentioned various metrics for
doing the approximation.  Least squares (L2) is just one of many. 
There are good reasons for using L2 so there are lots of methods and
code for doing it.  So, this doesn't *have* to be a least squares
problem - but is likely best pursued that way.

Years ago for fun I constructed a price matrix for PCs that showed
what was included: memory in MB, hard drive capacity, drives, etc. the
typical things.  If one wanted to solve for the value of a MB of
delivered memory there were two things to consider:
1) the "equations" would be inconsistent to begin with because there
would be no single value represented from each of many manufacturers.
2) it was possible to have many more manufacturers' offerings than
there were "ingredients" of a computer.  So, an analytical approach
would be overdetermined.
This suggested that a least squares fit to the unit prices was
appropriate.  Same kind of problem that you're dealing with here it
appears.  The MFR/Component matrix was certainly not square!

The result was that one could determine the "apparent average price"
of a particular configuration and could subtract these values from a
actual offering of the same configuration to determine if that
offering were high or low.
It was kinda fun just to do it.
In some cases the values of components came out negative..... thought
provoking and an interesting way to look at a commodity market.

Fred

llabakudas@yahoo.com (Lord Labakudas) wrote in message news:<d632d29f.0309301124.322aa5c7@posting.google.com>...
> > Probably the best book "Matrix computation" by Golub and Loan is what
> 
> I have to agree with you on this one. Golub's book is the best one for
> general numerical linear and matrix algebra, but Treffethen's book
> concentrates more on LS problems like the one that you posted.
> 
> > I am
> > using since several years. The way you are looking at the problem is
> > quite strange to me -either you are new or did not follow my postings
> > or Andor's
> > thoughtful comments - which I actually agree and think of. 
> 
> I don't understand what you find "strange" about my way of looking at
> the problem. The problem you are trying to solve IS a least squares
> (LS) problem AND QR factorization, Householder triagularization ARE
> few methods to solve LS problems, AND Treffethen's book deals with
> such problems.
> 
> >The
> > methods(by many) what  you are talking about is nice when A is some
> > sort of square matrix!
> 
> NO, check out the following MATLAB examples. The matrix A in the
> following examples are NOT square matrices.
> 
> A = randn(147, 5);
> b = randn(147, 1);
> 
> % Solution using MATLAB mldivide.
> % I believe QR factorization is used internally.
> x = A\b;
> 
> % Solution using pseudoinverse inv(A'*A)*A'
> x1 = pinv(A)*b;
> 
> % Solution using QR factorization.
> [Q, R] = qr(A, 0);
> x2 = inv(R)*(Q'*b);
> 
> % Solution using SVD.
> [U, S, V] = svd(A);
> w = pinv(S)*(U'*b);
> x3 = V*w;
> 
> Hope this helps...
> 
> -LL.

Hi there,

It is difficult to convince you by logic since you probably did not agree
that a non-square matrix based Eq. does not have any unique solution so 
it is badly optimized in most of the methods and in some cases you have to
pay the prize. Let me present the kind of Eq from a real problem we dealt with.

X1h=X1h1+X1h2 ---(1)

The Eq. is equivalent to AX=b

where h is to be estimated i.e h=X, X1 is hankel matrix of size 147 x 5 i.e
A and h1,h2 are known row vector of size 5 x 1 and b=X1h1+X2h2.

The least square solution one can write as follows,
h = h1 + INV(X1'X1)(X1'X2)h2  --(2)
where X1' is Hermitian of X1. Matrix multiplication is assumed in general.

The Eq. should work fine at high C/I (carrier to interference ratio)
but perform very badly at low C/I.

To support my view I would request you to check the following,
Calculate z=X1h using  Eq. (2)
and also Z= X1h1+X2h2
Develop the MATLAB code accordingly and you will see Z=!z,

Send me a MATLAB code  and  find a better
estimate for h which proves Z=z!!

Conditions:
-X1 should be Hankel Matrix,
-X1h1,X1h2,X1h means matrix multiplication.

If X1 is square matrix we  can analytically prove Z=z very easily.

Interestingly,  X1'z=X1'Z is always true for any matrix and I guess
you know why?.

Santosh

> It is difficult to convince you by logic since you probably did not agree
> that a non-square matrix based Eq. does not have any unique solution so 

Which part of, "These solution methods attempt to find the value of X
that minimize the discrepancy between B and AX in the least-squares
(||B-AX||^2) sense", did you not understand ? 

> 
> X1h=X1h1+X1h2 ---(1)
> 

Did you mean X1h = X1h1 + X2h2 ?

> where h is to be estimated i.e h=X, X1 is hankel matrix of size 147 x 5 i.e
> A and h1,h2 are known row vector of size 5 x 1 and b=X1h1+X2h2.

Hmm ! A Hankel matrix by definition is a square matrix. A matrix of
dimensions 147 x 5 is not a square matrix !! Take a look at the
following website for reference:

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

> The Eq. should work fine at high C/I (carrier to interference ratio)
> but perform very badly at low C/I.

What is your context ? You haven't mentioned what is "carrier" and
what is "interference" ? Please fill in the missing information and
I'll see if I can help ...

-LL.

llabakudas@yahoo.com (Lord Labakudas) wrote in message news:<d632d29f.0310021253.1ee4eb3b@posting.google.com>...
> > It is difficult to convince you by logic since you probably did not agree
> > that a non-square matrix based Eq. does not have any unique solution so 
> 
> Which part of, "These solution methods attempt to find the value of X
> that minimize the discrepancy between B and AX in the least-squares
> (||B-AX||^2) sense", did you not understand ? 
> 
> > 
> > X1h=X1h1+X1h2 ---(1)
> > 
> 
> Did you mean X1h = X1h1 + X2h2 ?
> 
> > where h is to be estimated i.e h=X, X1 is hankel matrix of size 147 x 5 i.e
> > A and h1,h2 are known row vector of size 5 x 1 and b=X1h1+X2h2.
> 
> Hmm ! A Hankel matrix by definition is a square matrix. A matrix of
> dimensions 147 x 5 is not a square matrix !! Take a look at the
> following website for reference:
> 
> http://mathworld.wolfram.com/HankelMatrix.html
I guess I have to give you with the following MATLAB:

 h1=randn(5,1);
 h2=randn(5,1);

 x=randn(152,1);
 c=x(1:147);
 r=x(147:151);
 X1=Hankel(c,r);
 y=randn(152,1);
 c=y(1:147);
 r=y(147:151);
 X2=Hankel(c,r);

find h=h1+(inv(X1'X1)(X1'X2)h2
and then let me know what you can prove
with X1h and X1h1+X1h2.

Try the above and see the general definition - and do not hide to solve the
Eq. I have given - constructing like the above.
Santosh


> 
> > The Eq. should work fine at high C/I (carrier to interference ratio)
> > but perform very badly at low C/I.
> 
> What is your context ? You haven't mentioned what is "carrier" and
> what is "interference" ? Please fill in the missing information and
> I'll see if I can help ...
> 
> -LL.