Ask Your Question
1

How quickly minimizing $M*x-v$ (numerically) ?

asked 2013-10-21 20:03:37 +0100

updated 2013-10-22 11:51:20 +0100

Let $v$ in $R^m$ and let $M$ be a matrix from $R^n$ to $R^m$, with $m>n$ big numbers.
I want to compute a vector $x$ in $R^n$ such that the norm of $M*x-v$ is minimal.

One way is to compute the projection $w$ of $v$ on the image of $M$.
For so, we can compute the projection $p$ on the image of $M$, as follows :

MTGS=M.transpose().gram_schmidt()[0]  # it's orthogonalization, not orthonormalization
l=MTGS.rank()
U=[]
for i in range(l):
   v=MTGS[i]
   u=v/(v.norm())
   L=list(u)
   U.append(L)
N=matrix(m,l,U)  
p=N.transpose()*N

Then:

w=p*v  
x=M.solve_right(w)

This vector $x$ minimizes the norm of $M*x-v$, but this method is very expensive in time, because it computes $p$ and $w$, while I just need $x$.

Is there another method, less expensive in time, for computing $x$ ?

Remark : I'm ok with numerical methods.

edit retag flag offensive close merge delete

1 Answer

Sort by » oldest newest most voted
2

answered 2013-10-22 13:06:36 +0100

ppurka gravatar image

updated 2013-10-22 13:13:12 +0100

If I am understanding your question correctly - if you put the additional constraint of getting $x$ with the minimum norm, then you are asking for the Moore-Penrose pseudoinverse. In Sage you can explicitly call the pseudoinverse function of numpy

sage: MN = M.numpy()
sage: import numpy
sage: x = matrix(numpy.linalg.pinv(MN))*v

Edit: Even the command

sage: x = M \ v

works for a nonsquare matrix M. But I am not sure what this is actually doing for a nonsquare matrix. The documentation does not seem to explain. The solution obtained is not the same as obtained from the pseudoinverse.

edit flag offensive delete link more

Comments

Thank you very much ppurka ! Do you know if we can compute x directly, without computing the pseudo-inverse before ?

Sébastien Palcoux gravatar imageSébastien Palcoux ( 2013-10-22 16:26:26 +0100 )edit

Well, that's what the Sage command `M \ v` does - it does not compute the inverse or pseudoinverse. Except, I am not sure exactly what it is computing for nonsquare matrices. Maybe you can put up a question in the sage-support mailing list.

ppurka gravatar imageppurka ( 2013-10-22 22:27:10 +0100 )edit

Thank you ppurka. I see a difference between "x = matrix(numpy.linalg.pinv(MN))*v" and "x = M \ v" : if v is not in the image of M then the first proposes a pseudo-solution and the second gives "ValueError: matrix equation has no solutions".

Sébastien Palcoux gravatar imageSébastien Palcoux ( 2013-10-24 07:00:44 +0100 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

Stats

Asked: 2013-10-21 20:03:37 +0100

Seen: 938 times

Last updated: Oct 22 '13