Solve $ A x = b $ with Surrogate Function which Implements Multiplication by $ A $

Question

I have an overdetermined linear system $Ax = b$. I need to choose an $x$. $x$ has about 100 elements in it.

If I had the matrix $A$, I would set x equal $A^\dagger b$, the pseudoinverse of $A$ times $b$. I'm using matlab, and so I could do this easily with the backslash operator.

My problem is that I don't have the matrix $A$, instead I have a function that returns $Ax$ given a vector $x$. If I were to construct $A$ from the transformation of basis vectors, it would take a long time, it would be very large, and it would be data dependent. Thus, this is not a great solution.

Is there a better way? Any suggestions?

Thanks for your help.

Answer 1

Is $A$ symmetric, or do you have a function that can also compute $A^Tx$? If so, you can run iterative algorithms like the method of conjugate gradients on the linear system $$A^TAx = A^Tb.$$

Otherwise, in the worst case, you can recover the matrix by querying $Ae_i$ for all basis vectors $e_i$.

Answer 2

Since you have $ f \left( x \right) = A x $ you can easily have a numerical approximation of its Jacobain which is $ {A}^{T} $.

Then you can employ Gradient Descent for solving the Least Squares problem by:

$$ {x}^{k + 1} = {x}^{k} - \alpha {A}^{T} \left( A x - b \right) $$

Where $ \alpha $ is the step size.