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!

  • 3
    $\begingroup$ 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$. $\endgroup$ – Brian Borchers Feb 5 '20 at 19:01
  • 2
    $\begingroup$ I think the question asks if transpose-free methods for solving this problem exist when only matrix-vector product $Ay$ is available. $\endgroup$ – Anton Menshov Feb 5 '20 at 21:14
  • $\begingroup$ 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? $\endgroup$ – Alone Programmer Feb 5 '20 at 23:22
  • 4
    $\begingroup$ 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. $\endgroup$ – Brian Borchers Feb 6 '20 at 2:11
  • 1
    $\begingroup$ 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! $\endgroup$ – Henry Feb 6 '20 at 11:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.