Ax-b, additional constraint

Hello,

Considering that I have Ax-b, A is a matrix of size 2*10, b is a vector of size 2*1, and x is a vector of size 10*1

A = [5.714e-13, 0, 1.426e-14, 0, -2.809e-07, 0, 4.734e-45, 0, 1.100, 0 ; 0, 5.655e-13, 0, 9.946e-15, 0, -2.809e-07, 0, 4.725e-45, 0, 1.100];
b = [-2.15321484499282e-13; -2.15327804546236e-13];

I want to solve for x, but I know that the entires in x are redunant, in which I have more equations than unknowns. In particular, the exact known solution of x is:

x = [0 ; 0 ; 0 ; 0 ; 7.664e-07 ; 7.664e-07 ; 0 ; 0 ; 7.412e-18 ; 7.412e-18];

Which means that I have 5 knowns not 10, how can I make use from this fact when utilizing a least square solution? I suppose that when using A\y, the MATLAB looks at the problem as it has 10 knowns and generates significantly different results than x.

Thanks for your help in advance.

Answer 1

[John D'Errico]

Why is it that you even think you have now 5 unknowns, not 10? Are you hoping that you can decde to fix 5 of those coefficients as 0? And why 5? You can choose to fix some set of EIGHT of them to zero. You should spend some time going back to those old linear algebra notes. And spend some time reading about floating point computations.

A = [5.714e-13, 0, 1.426e-14, 0, -2.809e-07, 0, 4.734e-45, 0, 1.100, 0 ;
    0, 5.655e-13, 0, 9.946e-15, 0, -2.809e-07, 0, 4.725e-45, 0, 1.100];

The elements of A vary by dozens of powers of 10. The worst case is A(2,8), 4.725e-45, so 45 powers of 10 smaller than some of the other coefficients in the matrix.

Anyway, there are infinitely many solutions possible. Pick a subset of 8 of them, set them to zero. Then in theory, you can solve for the two that remain. Even then, this will fail with some pairs. That is, in theory, IF you choose ANY element from the set of elements numbered [1 3 5 7 9], then pair that with ANY element from the set [2 4 6 8 10]. THROW ALL THE OTHERS AWAY. Just set them to zero.

spy(A)

The two members of that pair will always result in a valid solution. It may be a really ugly solution. But it will be theoretically valid.

[Alice Faisal]

Thanks for your reply.

No I don't mean that I want to set 5 of them to zeros, but as we can observe from the exact solution:

x = [0 ; 0 ; 0 ; 0 ; 7.664e-07 ; 7.664e-07 ; 0 ; 0 ; 7.412e-18 ; 7.412e-18];

is that each two entries have the same value. In other words, we are solving for 5 variables not 10. So, is there is a way to make use of this fact?

I only need in my approximated solution to get zeros whenever we have zeros in x, and non-zero entries for the rest.

[John D'Errico]

What 5 variables? Do you want to set those SIX variables to zero? Last time I checked, 10-4 = 6, not 5. There are 6 zero elements in the vector you show.

Ok. You maybe thinking that in the quasi-"solution" you have, each consecutive pair of two numbers are equal. In turn, you can view this as a reduction of the problem to a 5 variable one, with 5 unknowns.

That is nothing special though. In fact, you would still have then 2 equations, with 5 unknowns. OOPS. Still too many unknowns, and too few equations. The problem is underdetermined. IT HAS NO UNIQUE SOLIUTION, EVEN IF YOU MAKE THE ASSUMPTION YOU WANT TO MAKE.

Your original problem left you in a 10 dimensional dark forest, with only a 2 dimensional map to guide your way. This leaves you now in a 5 dimensional forest, just as dark, and still only that 2 dimensional map. It is not enough to solve the problem. Are you now slightly less lost in this 5-dimensional forest? Does it matter? Lost is lost.

Now, as far as the solution you claim to be exact goes, it is not so.

A = [5.714e-13, 0, 1.426e-14, 0, -2.809e-07, 0, 4.734e-45, 0, 1.100, 0 ; 0, 5.655e-13, 0, 9.946e-15, 0, -2.809e-07, 0, 4.725e-45, 0, 1.100];
b = [-2.15321484499282e-13; -2.15327804546236e-13];
x = [0 ; 0 ; 0 ; 0 ; 7.664e-07 ; 7.664e-07 ; 0 ; 0 ; 7.412e-18 ; 7.412e-18];

A*x
ans =
          -2.152736068e-13
          -2.152736068e-13
          
b
b =
     -2.15321484499282e-13
     -2.15327804546236e-13

Do you see that A*X is not truly b? Or, for example, suppose we try to solve this problem?

A\b
ans =
                         0
                         0
                         0
                         0
                         0
                         0
                         0
                         0
     -1.95746804090256e-13
     -1.95752549587487e-13

Do you see the two non-zero elements that do get chosen are not even the same? Close. But not identical. And for your target, that each consecutive pair be the same, that will fail.

Just to humor you, lets see what happens when we try to enforece the requirement that consecutive elements must be identical.

Effectively, we can write that in matrix form, as:

Ahat = blkdiag([1 -1],[1 -1],[1 -1],[1 -1],[1 -1])
Ahat =
     1    -1     0     0     0     0     0     0     0     0
     0     0     1    -1     0     0     0     0     0     0
     0     0     0     0     1    -1     0     0     0     0
     0     0     0     0     0     0     1    -1     0     0
     0     0     0     0     0     0     0     0     1    -1
bhat = zeros(5,1);

Xsol = [A;Ahat]\[b;bhat]
Xsol =
      1.12500773499336e-30
                         0
                         0
     -1.95823012476987e-32
     -5.53053330030018e-25
                         0
                         0
                         0
     -1.95748593964783e-13
     -1.95750759712961e-13
     
Ahat*Xsol
ans =
      1.12500773499336e-30
      1.95823012476987e-32
     -5.53053330030018e-25
                         0
        2.165748177425e-18        

As far as the linear algebra is concerned, this is a perfectly valid solution.

X0 = [0 ; 0 ; 0 ; 0 ; 7.664e-07 ; 7.664e-07 ; 0 ; 0 ; 7.412e-18 ; 7.412e-18];
norm(A*X0 - b)
ans =
      7.23164558424098e-17
      
norm(A*Xsol - b)
ans =
      2.78439131374286e-18      

In fact, it seems to be a more accurate solution than the one you claim to represent "truth".

I'm sorry, but this idea of yours simply does not work. It does not work in terms of your data. And it still leaves you lost with no solution. You need more information to solve the problem.