numpy linear algebra basic help

Question

This is what I need to do-

I have this equation-

Ax = y

Where A is a rational m*n matrix (m<=n), and x and y are vectors of the right size. I know A and y, I don't know what x is equal to. I also know that there is no x where Ax equals exactly y. I want to find the vector x' such that Ax' is as close as possible to y. Meaning that (Ax' - y) is as close as possible to (0,0,0,...0).

I know that I need to use either the lstsq function: http://www.scipy.org/doc/numpy_api_docs/numpy.linalg.linalg.html#lstsq

or the svd function: http://www.scipy.org/doc/numpy_api_docs/numpy.linalg.linalg.html#svd

I don't understand the documentation at all. Can someone please show me how to use these functions to solve my problem.

Thanks a lot!!!

Answer 1

SVD is for the case of m < n, because you don't really have enough degrees of freedom.

The docs for lstsq don't look very helpful. I believe that's least square fitting, for the case where m > n.

If m < n, you'll want SVD.

Answer 2

The updated documentation may be a bit more helpful... looks like you want

numpy.linalg.lstsq(A, y)

Answer 3

The SVD of matrix A gives you orthogonal matrices U and V and diagonal matrix Σ such that

A = U Σ V ^T

where U U^T = I ; V V^T = I

Hence, if

x A = y

then

x U Σ V ^T = y

x U Σ V ^T V = y V

x U Σ = y V

U ^T x Σ = y V

x Σ = U y V

x = Σ ^-1 U ^T y V

x = V ^T Σ ^-1 U ^T y

So given SVD of A you can get x.

---

Although for general matrices A B != B A, it is true for vector x that x U == U ^T x.

For example, consider x = ( x, y ), U = ( a, b ; c, d ):

x U = ( x, y ) ( a, b ; c, d )

= ( xa+yc, xb+yd )

= ( ax+cy, bx+dy )

= ( a, c; b, d ) ( x; y )

= U ^T x

It's fairly obvious when you look at the values in x U being the dot products of x and the columns of U, and the values in U^Tx being the dot products of the x and the rows of U^T, and the relation of rows and columns in transposition