5
$\begingroup$

I am inverting a sparse, symmetric, ill-conditioned matrix. I have used both SVD and the LDL decomposition. I find that my results are better with the latter. Why?

I understand that LDL decomposition works only on symmetric matrices. But that doesn't necessarily say why it works better than a "more general" algorithm.

$\endgroup$

closed as off-topic by usεr11852, Peter Flom Feb 12 '18 at 13:16

  • This question does not appear to be about statistics within the scope defined in the help center.
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 2
    $\begingroup$ What do you mean that your results are "better"? $\endgroup$ – Sycorax Feb 11 '18 at 14:15
  • 1
    $\begingroup$ @Sycorax I am using these decompositions to find the least squares solution to a system of linear equations. I can generate systems with known ground truth values and see which of the two methods is more reliable in recovering them. $\endgroup$ – rhombidodecahedron Feb 11 '18 at 14:26
  • $\begingroup$ I think it is important to note here that you are having sparse matrices. In general, Cholesky should be better in terms of time-complexity. Cholesky has time-complexity of order $\frac{1}{3}O(n^3)$ instead $\frac{8}{3}O(n^3)$ which is the case with the SVD. These go a bit out of the window now that you are talking about sparse matrices because the sparsity pattern changes the rules of the game. I strongly suspect you are using CHOLMOD for the sparse Cholesky and that is a great work-horse, but the sparse SVD, maybe ARPACK, maybe straight-up MKL? (cont.) $\endgroup$ – usεr11852 Feb 11 '18 at 19:40
  • $\begingroup$ What are dimensions of the matrices involved and what percentage of the entries are non-zero? Are you explicitly setting them as sparse matrices (the obvious thing)? Do you have any reproducible examples? $\endgroup$ – usεr11852 Feb 11 '18 at 19:43
  • 3
    $\begingroup$ I think that the question could be moved to the Computational Science SE scicomp.stackexchange.com $\endgroup$ – usεr11852 Feb 11 '18 at 19:44
3
$\begingroup$

There are trade-offs between computational speed, accuracy, and constraints. The Eigen library has a pretty good summary here https://eigen.tuxfamily.org/dox/group__TopicLinearAlgebraDecompositions.html

(And there's also a page comparing SVD and QR-decomposition for least-square solvers at https://eigen.tuxfamily.org/dox/group__LeastSquares.html )

From this second page:

"The three methods discussed on this page are the SVD decomposition, the QR decomposition and normal equations. Of these, the SVD decomposition is generally the most accurate but the slowest, normal equations is the fastest but least accurate, and the QR decomposition is in between."

$\endgroup$
  • 2
    $\begingroup$ Perhaps it would be helpful to OP if you clarified the relationship between the content of your answer and OP's question comparing SVD and Cholesky factors. $\endgroup$ – Sycorax Feb 11 '18 at 19:19

Not the answer you're looking for? Browse other questions tagged or ask your own question.