对称矩阵分解：Cholesky与SVD孰优？稀疏病态矩阵LDL优于SVD原因？

Great questions! Let's break them down clearly, since these are common points of confusion when working with symmetric matrices and linear solvers.

The short answer: It depends on your goals and the matrix properties. Here's the breakdown:

• When Cholesky is better:

  • If your symmetric matrix is positive definite (all eigenvalues positive), Cholesky decomposition (which factors the matrix as (A = LL^T) where (L) is lower triangular) is far more efficient. It runs in (O(n^3)) time but with a much smaller constant factor than SVD, uses less memory, and fully leverages the matrix's symmetry (only half the matrix needs to be processed). For well-conditioned positive definite matrices, it's the go-to choice for solving linear systems or computing inverses.
  • It's also simpler to implement for symmetric structures, especially in sparse contexts where preserving sparsity is critical.

• When SVD is better:

  • If your symmetric matrix is not positive definite (e.g., indefinite, singular, or ill-conditioned), Cholesky will fail outright (or produce unstable results if you force it). SVD, on the other hand, works for any matrix—symmetric or not, singular or well-conditioned. It factors (A = U\Sigma V^T), where (\Sigma) contains singular values, and it's extremely robust to numerical errors, making it ideal for ill-conditioned systems where you need a stable pseudo-inverse.
  • SVD also gives you more insight into the matrix's structure (eigenvalues for symmetric matrices are just the singular values, up to sign), which can be useful for tasks like dimensionality reduction or regularization.

So Cholesky isn't universally "better"—it's a specialized tool that outperforms SVD in its niche (positive definite, well-behaved symmetric matrices), while SVD is the general-purpose, robust workhorse for all other cases.

This is a fantastic observation, and the advantage comes down to three core reasons that play to LDL's strengths with your specific matrix type:

1. Sparsity preservation
   SVD is a dense algorithm by nature—even if your input matrix is sparse, most SVD implementations will convert it to a dense format to compute the decomposition. This blows up memory usage and computation time drastically for large sparse matrices. LDL decomposition, however, is designed to work with sparse symmetric matrices. It only processes non-zero elements and preserves the sparse structure of the original matrix throughout the computation, leading to massive savings in both memory and runtime (often (O(n)) or (O(n^{1.5})) instead of (O(n^3)) for dense SVD).

2. Symmetry exploitation reduces numerical error
   LDL factors (A = LDL^T) where (L) is unit lower triangular and (D) is diagonal. Because it's tailored to symmetric matrices, it avoids redundant computations that SVD (a general-purpose method) has to perform. For ill-conditioned symmetric matrices, this focused computation means numerical errors propagate more predictably and can be better controlled—especially if you use a pivoted LDL decomposition (like the Bunch-Kaufman algorithm), which reorders rows/columns to minimize fill-in and improve stability for indefinite or ill-conditioned matrices.

3. Direct inverse computation vs. pseudo-inverse overhead
   When you invert a matrix using LDL, you're essentially solving a series of linear systems (Ax = e_i) (where (e_i) are standard basis vectors) using forward/back substitution on the triangular factors (L) and (L^T). This is a direct, efficient process. For SVD, computing the pseudo-inverse requires handling small singular values (which are the source of ill-conditioning)—you have to decide whether to truncate them (which introduces approximation error) or keep them (which amplifies numerical noise). This extra step adds overhead and uncertainty, whereas LDL (with pivoting) can handle ill-conditioned symmetric matrices directly without needing to adjust for singular values.

In short, LDL is a specialized tool that speaks the "language" of your sparse symmetric matrix, while SVD is a one-size-fits-all tool that wastes resources on unnecessary computations and struggles with the sparsity of your problem.

内容的提问来源于stack exchange，提问作者rhombidodecahedron