# Solving a huge least squares system of equations when I can only evaluate Ax

I have a situation where I can generate a system of $$M$$ linear equations for $$N$$ variables ($$N \ne M$$). Implicitly this is of the form $$Ax=b$$ with $$A \in \mathbb{R}^{M \times N}$$, although I never explicitly construct $$A$$ (even as a sparse matrix), but I can evaluate $$Ax$$ implicitly for any vector $$x \in \mathbb{R}^N$$ and calculate $$b$$ (but this is quite a non-trivial process to do this). I wanted to use LSMR or LSQR (https://docs.scipy.org/doc/scipy-0.14.0/reference/generated/scipy.sparse.linalg.lsqr.html#scipy.sparse.linalg.lsqr), however they require definining a linear operator that can evaluate both $$Ax$$ and $$A^Ty$$ for any $$x \in \mathbb{R}^N$$, $$y \in \mathbb{R}^M$$. Evaluating $$A^T y$$ in my case is not that easy I don't think, so are there any approaches I can use that don't require doing this? It feels like it should be possible as I am still fully evaluating all of the equations that I want to approximately hold, but perhaps it isn't!

• Your question isn't clear. You realize that you can't use LSQR or LSMR without being able to multiply $A^{T}y$. Are you looking for alternative methods that don't require $A^{T}y$? Are you asking about ways in which you might be able to compute $A^{T}y$? That would require you to provide more details of how you compute $Ax$. – Brian Borchers Feb 5 at 19:01
• I think the question asks if transpose-free methods for solving this problem exist when only matrix-vector product $Ay$ is available. – Anton Menshov Feb 5 at 21:14
• I'm a bit confused here... So based on your question it seems you have just vector $b$ for whatever the result of $Ax$ might be, but you don't have $A$ explicitly and obviously you don't have $x$. I think it's not possible to use scipy.lsqr in this situation. Is it possible a bit elaborate why you never explicitly constructed $A$? Is it too large or can't be calculated in your framework or something else? – Alone Programmer Feb 5 at 23:22
• Transpose-free methods for linear systems of equations are a thing, but I'm not aware of (even after searching online) any transpose-free method for linear least squares problems. You could try a simple coordinate descent method or approximating the gradient of the objective by finite differencing, but these approaches are probably impractical for a large scale problem. It's likely that if you provided more information about your underlying problem we might be able to suggest some approaches to doing the $A^{T}y$ multiplication. – Brian Borchers Feb 6 at 2:11
• OK actually I think it was easier than I initially thought to calculate $A^Ty$, just had to play around with the indices a bit! Hopefully this will work now! – Henry Feb 6 at 11:45