Linear algebra problem

classic Classic list List threaded Threaded
3 messages Options
Reply | Threaded
Open this post in threaded view
|

Linear algebra problem

federico vaggi-2
Hi,

I have a standard system, of type:

AX = B

Where:

X is a nxm matrix.

B is a mxn matrix.

A is a nxn matrix.

I have B and X, and I am trying to calculate A - however, B, is null matrix.

Using the default numpy solvers (http://docs.scipy.org/doc/numpy/reference/generated/numpy.linalg.lstsq.html#numpy.linalg.lstsq) I obtain the trivial correct solution of A being a null matrix.

What's the most robust way to search for the solution which minimizes the residuals, while still not returning a null matrix of A?  X, is usually rank deficient, so I know I won't have an exact solution.

Thanks for all the help,

Federico

_______________________________________________
SciPy-User mailing list
[hidden email]
http://mail.scipy.org/mailman/listinfo/scipy-user
Reply | Threaded
Open this post in threaded view
|

Re: Linear algebra problem

Pauli Virtanen-3
23.05.2012 19:47, federico vaggi kirjoitti:
[clip]
> AX = B
[clip]
> I have B and X, and I am trying to calculate A - however, B, is
> null matrix.
>
> What's the most robust way to search for the solution which minimizes
> the residuals, while still not returning a null matrix of A?  X, is
> usually rank deficient, so I know I won't have an exact solution.

This problem is equivalent to looking for the subspace of zero
eigenvalue. You can do an eigenvalue or SVD decomposition of X, and then
grab the solution from the eigen-/singular vectors corresponding to zero
or small eigen/singular values.

--
Pauli Virtanen

_______________________________________________
SciPy-User mailing list
[hidden email]
http://mail.scipy.org/mailman/listinfo/scipy-user
Reply | Threaded
Open this post in threaded view
|

Re: Linear algebra problem

Warren Weckesser-3


On Wed, May 23, 2012 at 3:12 PM, Pauli Virtanen <[hidden email]> wrote:
23.05.2012 19:47, federico vaggi kirjoitti:
[clip]
> AX = B
[clip]
> I have B and X, and I am trying to calculate A - however, B, is
> null matrix.
>
> What's the most robust way to search for the solution which minimizes
> the residuals, while still not returning a null matrix of A?  X, is
> usually rank deficient, so I know I won't have an exact solution.

This problem is equivalent to looking for the subspace of zero
eigenvalue. You can do an eigenvalue or SVD decomposition of X, and then
grab the solution from the eigen-/singular vectors corresponding to zero
or small eigen/singular values.



Another way to say this is you want the nullspace of X.T.  See the SciPy Cookbook entry http://www.scipy.org/Cookbook/RankNullspace for an example of a function that computes the nullspace using the singular value decomposition.

For example, in the following, X is 4 by 2:

In [57]: import rank_nullspace as rn

In [58]: X = array([[1,2],[3,4],[5,6],[7,8]])

In [59]: X
Out[59]:
array([[1, 2],
       [3, 4],
       [5, 6],
       [7, 8]])

In [60]: A = rn.nullspace(X.T).T

In [61]: A
Out[61]:
array([[-0.39450102,  0.24279655,  0.69790998, -0.5462055 ],
       [-0.37995913,  0.80065588, -0.46143436,  0.04073761]])


We get a 2 by 4 result; we can add trivial rows of zeros to make A 4 by 4:


In [62]: A = vstack((A, zeros((2,4))))

In [63]: A
Out[63]:
array([[-0.39450102,  0.24279655,  0.69790998, -0.5462055 ],
       [-0.37995913,  0.80065588, -0.46143436,  0.04073761],
       [ 0.        ,  0.        ,  0.        ,  0.        ],
       [ 0.        ,  0.        ,  0.        ,  0.        ]])


Verify that we have solved AX = B, where B is the 4 by 2 array of zeros:

In [64]: dot(A, X)

Out[64]:
array([[ -1.33226763e-15,   0.00000000e+00],
       [  0.00000000e+00,   3.33066907e-16],
       [  0.00000000e+00,   0.00000000e+00],
       [  0.00000000e+00,   0.00000000e+00]])


Warren


_______________________________________________
SciPy-User mailing list
[hidden email]
http://mail.scipy.org/mailman/listinfo/scipy-user