Search All of the Math Forum:

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

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

 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

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

Date Subject Author
10/3/12 spasmous
10/3/12 Robin Vowels
10/4/12 Peter Spellucci
10/4/12 Rui Maciel
10/5/12 Michael Lehn