1
$\begingroup$

I have inherited code that solves Eigen::Matrix problems using the code shown on this page:

(A.transpose() * A).ldlt().solve(A.transpose() * b)

This works, but often my matrix size can be $[200 \times 5]$. The $A^T.A$ expression gives me a huge square matrix with 400 times as much data, so I suspect that the solver wastes a lot of time handling that extra data.

Is there a "better" solver that avoids creating a square matrix, or can the problem be approached by a "divide and conquer strategy, where perhaps I could solve 40 50x5 problems, then solve the 40x5 results?

UPDATE: For further information, my problem is I have a point cloud from after doing a disparity check on a stereo image, and according to the function name, it is trying to detect a road surface. We solve the matrix, then use the calculated coefficients to weed out noise in each group of points.

It also strikes me that trying to accurately solve for all 2000 points seems like a lot of effort; perhaps picking each 10th point would give a roughly similar answer?

Furthermore, the 5 row values are something like (IIRC, I'm away from my computer for a week!) $X$, $Y$, $Z$, $X^2$ and $Y^2$

Finally, note that one operation in itself is not that inefficient, it's that I have over 300 groups of points for a grand total of over 100,000 points per frame.

|cite|improve this question
$\endgroup$
  • $\begingroup$ What problem do you want to solve? $\endgroup$ – Rodrigo de Azevedo Apr 26 '18 at 9:48
  • 5
    $\begingroup$ Is this the solution of a least squares problem min_x II Ax-b II ? I suspect that it is. In that case, there is a large number of solvers that can solve that straight-up, without multiplication with A transpose. This is called Linear Least-Squares, and wiki has methods for this, e.g. using QR decomposition. (Q,R) = qr(A), then x = R^(-1) * transpose(Q) * b. Of course, R^(-1) should be done with a triangular matrix solve, since R is upper triangular. $\endgroup$ – OscarB Apr 26 '18 at 10:05
  • 2
    $\begingroup$ hm, if A is 2000x5, then you end up with a tiny 5x5 matrix. $\endgroup$ – ggael Apr 26 '18 at 10:44
  • 2
    $\begingroup$ hmm, even if you have $A\in \mathbb R^{5\times 2000}$ - resulting in a $2000 \times 2000$ matrix after $A^T A$, in general, I don't see how it will be mostly zeroes. There is something special about $A$, I suspect. $\endgroup$ – Anton Menshov Apr 26 '18 at 11:32
  • 2
    $\begingroup$ ...and the resulting matrix won't be invertible anyway. $\endgroup$ – ggael Apr 26 '18 at 13:06

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.