Drexel dragonThe Math ForumDonate to the Math Forum



Search All of the Math Forum:

Views expressed in these public forums are not endorsed by Drexel University or The Math Forum.


Math Forum » Discussions » sci.math.* » sci.math.num-analysis.independent

Topic: Solve linear equation with matrix multiplies only
Replies: 4   Last Post: Oct 5, 2012 6:39 AM

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]
Peter Spellucci

Posts: 221
Registered: 11/9/09
Re: Solve linear equation with matrix multiplies only
Posted: Oct 4, 2012 8:34 AM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

spasmous <spasmous@gmail.com> writes:
>For a general matrix (rectangular, non-symmetric) is there an iterative met=
>hod for solving J*x=3Db that only uses multiplies J*v and no transpose mult=
>iples J'*u? I know there are many methods based on J'*J.
>
>The problem I'm facing is a nonlinear optimization over thousands of variab=
>les with hundreds of thousands of measurements. It is well behaved, but eac=
>h step requires the Jacobian which can barely be held in memory. Plus, it s=
>eems wasteful to calculate the entire Jacobian (thousands of function evalu=
>ations) when probably only a few principal directions are needed on each st=
>ep of the optimization.
>
>The Jacobian is formed numerically by adding small "h" to each element in t=
>urn so it costs thousands of evaluations. A cheaper alternative I have trie=
>d is to approximate J using a few (small norm) random vectors Y=3D[y1 y2 y3=
>...] such that Q =3D J*Y. Then solve Q*(pinv(Y)*x)=3Db to recover something=
> resembling x.
>
>This kind of works but I hate to use a kludge if there is something better =
>available. It seems to me that I would need an approximate way to solve J*x=
>=3Db with only multiplications.


since in your case the system will be incompatible and you obviously
want the least squares solution, where is no hope for this: necessarily
somehow J' will come into play, and indeed the two standard solvers
for your problem, lsqr and svdpack both need multiplication with J'.
But what if you would switch to the max-norm?
then you could use lp technology and J' wouldn't appear.
hth
peter




Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© Drexel University 1994-2014. All Rights Reserved.
The Math Forum is a research and educational enterprise of the Drexel University School of Education.