Thread Subject:

Improve Condition Number of Matrix

Hi,

I am trying to invert a 8x8 matrix with a poor condition number. The equation I am trying to solve is X=inv(A)Y where A is my poorly conditioned matrix. I managed to improve the condition number to 1.7559e+16 with some techniques mentioned below (but is still too high):

-Diagonal Balance- inv(DA)DY=X

-Using pinv instead of inv (which solves X to within 10% of the values I was expecting, I need <1%)

- Left division- X=A\Y

Are there any other ways to improve the condition of the matrix so it inverts better? or methods to estimate the inverse?

"Michael " <chmihimabb@gmail.com> wrote in message <jvun9u$pef$1@newscl01ah.mathworks.com>...
>
>
> Are there any other ways to improve the condition of the matrix so it inverts better? or methods to estimate the inverse?
=================

Isn't it possible that you simply have an (approximately) under-determined system? Give the system more information by including more equations...

"Michael " <chmihimabb@gmail.com> wrote in message <jvun9u$pef$1@newscl01ah.mathworks.com>...
> Hi,
>
> I am trying to invert a 8x8 matrix with a poor condition number. The equation I am trying to solve is X=inv(A)Y where A is my poorly conditioned matrix. I managed to improve the condition number to 1.7559e+16 with some techniques mentioned below (but is still too high):
>
> -Diagonal Balance- inv(DA)DY=X
>
> -Using pinv instead of inv (which solves X to within 10% of the values I was expecting, I need <1%)
>
> - Left division- X=A\Y
>
> Are there any other ways to improve the condition of the matrix so it inverts better? or methods to estimate the inverse?

The matrix is numerically singular. You can get an
infinite number of solutions. Take your pick.

Wanting 1% accuracy is a foolish expectation from
a singular matrix when you can choose infinitely
many solutions.

John

"Matt J" wrote in message <jvunso$r4r$1@newscl01ah.mathworks.com>...
> "Michael " <chmihimabb@gmail.com> wrote in message <jvun9u$pef$1@newscl01ah.mathworks.com>...
> >
> >
> > Are there any other ways to improve the condition of the matrix so it inverts better? or methods to estimate the inverse?
> =================
>
> Isn't it possible that you simply have an (approximately) under-determined system? Give the system more information by including more equations...

I have more data so I could use a least squares approach and use more equations.
However I know before hand that the 8 Y values should follow the relationship dictated by the 8 linear equations exactly (and by exactly i mean ~11 significant digits), so I would like 8 equations to be sufficient.

The problem is that the condition of the matrix is so poor that the very insignificant error associated in Y gets exploded when solving for X.

What I would like is recommendations to improve the condition value of the A matrix through scaling or similar means.

"John D'Errico" <woodchips@rochester.rr.com> wrote in message <jvuo7v$s54$1@newscl01ah.mathworks.com>...
> "Michael " <chmihimabb@gmail.com> wrote in message <jvun9u$pef$1@newscl01ah.mathworks.com>...
> > Hi,
> >
> > I am trying to invert a 8x8 matrix with a poor condition number. The equation I am trying to solve is X=inv(A)Y where A is my poorly conditioned matrix. I managed to improve the condition number to 1.7559e+16 with some techniques mentioned below (but is still too high):
> >
> > -Diagonal Balance- inv(DA)DY=X
> >
> > -Using pinv instead of inv (which solves X to within 10% of the values I was expecting, I need <1%)
> >
> > - Left division- X=A\Y
> >
> > Are there any other ways to improve the condition of the matrix so it inverts better? or methods to estimate the inverse?
>
> The matrix is numerically singular. You can get an
> infinite number of solutions. Take your pick.
>
> Wanting 1% accuracy is a foolish expectation from
> a singular matrix when you can choose infinitely
> many solutions.
>
> John

The matrix is almost singular yes. There should be methods by scaling, that could improve the matrix condition number, and make it more invertible.

"Michael Himmelfarb" wrote in message <jvupmt$32c$1@newscl01ah.mathworks.com>...
>
>
> The matrix is almost singular yes. There should be methods by scaling, that could improve the matrix condition number, and make it more invertible.
===========

I doubt it. Not when the 1./cond(A) is so close to the numerical precision threshold, eps. And even if the condition number were more manageable, it seems like nondiagonal scaling is required here, which would be more computationally demanding than simply adding more equations to the system. You would have to start taking QR decompositions or SVDs, probably, to find the principal axes that need to be scaled...

"Matt J" wrote in message <k00542$5as$1@newscl01ah.mathworks.com>...
> "Michael Himmelfarb" wrote in message You would have to start taking QR decompositions or SVDs, probably, to find the principal axes that need to be scaled...

But SVD is what PINV command does.

Just a quick note to stop people to believe into miracle: If the problem is ill-conditioned there is no thing one can do about it. One can transform the problem by another parametrization in which the matrix _looks_ better conditioned. But the ill-conditioned characteristic of the original problem is not going away.

As John said, hopping 1% error on a singular matrix (CDN ~1e16) is foolish. The condition number must be at most (0.01/eps) = 4.5036e+13 for such precision.

Bruno

"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <k0060b$7to$1@newscl01ah.mathworks.com>...
>
> One can transform the problem by another parametrization in which the matrix _looks_ better conditioned. But the ill-conditioned characteristic of the original problem is not going away.
=============

OK, but it's more than just that it _looks_ better conditioned, right? As long as you're willing to stick to the new space of parameters, you should get well-conditioned results there, no?

"Michael " <chmihimabb@gmail.com> wrote in message
news:jvupfa$2dm$1@newscl01ah.mathworks.com...
> "Matt J" wrote in message <jvunso$r4r$1@newscl01ah.mathworks.com>...
>> "Michael " <chmihimabb@gmail.com> wrote in message
>> <jvun9u$pef$1@newscl01ah.mathworks.com>...
>> >
>> >
>> > Are there any other ways to improve the condition of the matrix so it
>> > inverts better? or methods to estimate the inverse?
>> =================
>>
>> Isn't it possible that you simply have an (approximately)
>> under-determined system? Give the system more information by including
>> more equations...
>
> I have more data so I could use a least squares approach and use more
> equations.
> However I know before hand that the 8 Y values should follow the
> relationship dictated by the 8 linear equations exactly (and by exactly i
> mean ~11 significant digits), so I would like 8 equations to be
> sufficient.

Is this data something that you collected via physical processes (measuring
length, weight, time, angles, etc.)? If so, are the processes you used to
collect the data that accurate?

Theoretically your data may allow such an exact fitting. In theory there is
no difference between theory and practice. In practice there is.

> The problem is that the condition of the matrix is so poor that the very
> insignificant error associated in Y gets exploded when solving for X.
>
> What I would like is recommendations to improve the condition value of the
> A matrix through scaling or similar means.

--
Steve Lord
slord@mathworks.com
To contact Technical Support use the Contact Us link on
http://www.mathworks.com

"Matt J" wrote in message <k00fv5$9mu$1@newscl01ah.mathworks.com>...

>
> OK, but it's more than just that it _looks_ better conditioned, right? As long as you're willing to stick to the new space of parameters, you should get well-conditioned results there, no?

If such thing was true, Heisenberg's uncertainty principe would never exist.

Bruno

"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <k00jui$plf$1@newscl01ah.mathworks.com>...
> "Matt J" wrote in message <k00fv5$9mu$1@newscl01ah.mathworks.com>...
>
> >
> > OK, but it's more than just that it _looks_ better conditioned, right? As long as you're willing to stick to the new space of parameters, you should get well-conditioned results there, no?
>
> If such thing was true, Heisenberg's uncertainty principe would never exist.
==============

I need a clearer example than Heisenberg, I'm afraid. How can the new condition number not describe the error sensitivity of the _new_ parameters?

Who care about the new parameters?

One can define the new parameters as the observers, the condition number is then 1. How does it helps?

Bruno

"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <k0110f$dab$1@newscl01ah.mathworks.com>...
> Who care about the new parameters?
>
> One can define the new parameters as the observers, the condition number is then 1. How does it helps?
============

Well, not in a big way. Maybe just to find a more natural scaling for your variables, so that your errors are always <<1 unit.

"Matt J" wrote in message <k012ue$kcl$1@newscl01ah.mathworks.com>...
> "Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <k0110f$dab$1@newscl01ah.mathworks.com>...
> > Who care about the new parameters?
> >
> > One can define the new parameters as the observers, the condition number is then 1. How does it helps?
> ============
>
> Well, not in a big way. Maybe just to find a more natural scaling for your variables, so that your errors are always <<1 unit.

Yes that is exactly what I needed because the error sensitivity was too high. I managed to improve the condition number enough to solve within 0.1% of the actual values using SVD to precondition my matrix for inverse (essentially pinv). Unfortunately now I need to reproduce this with a similar matrix that is 24x24 with a condition number of ~1e19.

"Michael Himmelfarb" wrote in message <k017q8$7sc$1@newscl01ah.mathworks.com>...
> "Matt J" wrote in message <k012ue$kcl$1@newscl01ah.mathworks.com>...
> > "Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <k0110f$dab$1@newscl01ah.mathworks.com>...
> > > Who care about the new parameters?
> > >
> > > One can define the new parameters as the observers, the condition number is then 1. How does it helps?
> > ============
> >
> > Well, not in a big way. Maybe just to find a more natural scaling for your variables, so that your errors are always <<1 unit.
>
> Yes that is exactly what I needed because the error sensitivity was too high. I managed to improve the condition number enough to solve within 0.1% of the actual values using SVD to precondition my matrix for inverse (essentially pinv). Unfortunately now I need to reproduce this with a similar matrix that is 24x24 with a condition number of ~1e19.
=============

No, I don't think we're talking about the same thing. I was saying that reparametrizing could be helpful if you want the _absolute errors_ (not the percent errors) to be much less than 1 unit. If your variables fluctuate by miles, you might not want to be measuring them in millimeters.

It's not clear to us, though, how you think you've helped yourself by transforming the matrix. You've achieved lower percent error in a set of transformed variables, yes, but not in the original variables of interest.

Hi,

This is Will. My research topic is to solve ill-conditioned matrix. Could you please email me your matrix and then I will try to solve it using a new method I know?

Best wishes
Will

"Michael Himmelfarb" wrote in message <jvun9u$pef$1@newscl01ah.mathworks.com>...
> Hi,
>
> I am trying to invert a 8x8 matrix with a poor condition number. The equation I am trying to solve is X=inv(A)Y where A is my poorly conditioned matrix. I managed to improve the condition number to 1.7559e+16 with some techniques mentioned below (but is still too high):
>
> -Diagonal Balance- inv(DA)DY=X
>
> -Using pinv instead of inv (which solves X to within 10% of the values I was expecting, I need <1%)
>
> - Left division- X=A\Y
>
> Are there any other ways to improve the condition of the matrix so it inverts better? or methods to estimate the inverse?

"long zhang" <bbs10406105@126.com> wrote in message <k18sj7$n23$1@newscl01ah.mathworks.com>...
> Hi,
>
> This is Will. My research topic is to solve ill-conditioned matrix. Could you please email me your matrix and then I will try to solve it using a new method I know?
>
> Best wishes
> Will
>
> "Michael Himmelfarb" wrote in message <jvun9u$pef$1@newscl01ah.mathworks.com>...
> > Hi,
> >
> > I am trying to invert a 8x8 matrix with a poor condition number. The equation I am trying to solve is X=inv(A)Y where A is my poorly conditioned matrix. I managed to improve the condition number to 1.7559e+16 with some techniques mentioned below (but is still too high):
> >
> > -Diagonal Balance- inv(DA)DY=X
> >
> > -Using pinv instead of inv (which solves X to within 10% of the values I was expecting, I need <1%)
> >
> > - Left division- X=A\Y
> >
> > Are there any other ways to improve the condition of the matrix so it inverts better? or methods to estimate the inverse?

Ok, I emailed you my unconditioned matrix. This one is a little larger than the one I mentioned earlier but if you are up to the challenge I would appreciate help with solving this set of linear equations. Let me know what solution you get.