# When to use SVD and when to use Eigendecomposition for PCA?

**URL:** <https://discourse.julialang.org/t/when-to-use-svd-and-when-to-use-eigendecomposition-for-pca/19689>\
**Category:** Statistics\
**Created:** [January 16, 2019, 10:29am UTC](https://discourse.julialang.org/t/when-to-use-svd-and-when-to-use-eigendecomposition-for-pca/19689 "2019-01-16T10:29:54Z")\
**Posts on this page:** 6\
**Page:** 1

<div class="post-metadata">

**Author:** ![gdkrmr](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/gdkrmr/32/2791_2.png) [@gdkrmr](https://discourse.julialang.org/u/gdkrmr)\
**Post date:** [January 16, 2019, 10:29am UTC](https://discourse.julialang.org/t/when-to-use-svd-and-when-to-use-eigendecomposition-for-pca/19689/1 "2019-01-16T10:29:54Z")

</div>

As a long time `R` user I was always under the impression that SVD is superior to and eigenvalue decomposition of the correlation matrix (see the documentation for `prcomp` and `princomp`) in terms of numerical accuracy and computational speed. The implementation of `PCA` in `MultivariateStats.jl` uses SVD if the the number of dimensions is smaller than the number of observations.

What are the computational trade-offs of SVD and eigenvalue decomposition of the covariance matrix?

edit: the question was unclear, rephrased it.

---

<div class="post-metadata">

**Author:** ![zgornel](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/zgornel/32/217487_2.png) [@zgornel](https://discourse.julialang.org/u/zgornel)\
**Post date:** [January 16, 2019, 11:14am UTC](https://discourse.julialang.org/t/when-to-use-svd-and-when-to-use-eigendecomposition-for-pca/19689/2 "2019-01-16T11:14:28Z")

</div>

A reasonible answer can be found on this page [linear algebra - What is the intuitive relationship between SVD and PCA? - Mathematics Stack Exchange](https://math.stackexchange.com/questions/3869/what-is-the-intuitive-relationship-between-svd-and-pca). The differences should not be significant (unless there are some implementation hacks…) In practice, you can try both and see what works, as there are matrices where calculating the covariances causes loss of precision…

---

<div class="post-metadata">

**Author:** ![Tamas\_Papp](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tamas_papp/32/25949_2.png) [@Tamas\_Papp](https://discourse.julialang.org/u/Tamas_Papp)\
**Post date:** [January 16, 2019, 11:36am UTC](https://discourse.julialang.org/t/when-to-use-svd-and-when-to-use-eigendecomposition-for-pca/19689/3 "2019-01-16T11:36:54Z")

</div>

I don’t think this is a Julia-specific question. But note that when

A = U\Sigma V^\top

we get

A^\top A = V \Sigma^2 V^\top

so the two are very closely related, especially if A itself is symmetric.

> [@gdkrmr](#):
>
> they even have to manually add a large error in the unit tests for the SVD implementation

I am not sure what this means, can you be more specific, eg link the relevant section?

---

<div class="post-metadata">

**Author:** ![gdkrmr](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/gdkrmr/32/2791_2.png) [@gdkrmr](https://discourse.julialang.org/u/gdkrmr)\
**Post date:** [January 16, 2019, 1:54pm UTC](https://discourse.julialang.org/t/when-to-use-svd-and-when-to-use-eigendecomposition-for-pca/19689/4 "2019-01-16T13:54:36Z")

</div>

I put the question the wrong way, sorry.

I am well aware about the relation between the two of them. My question was about the computational aspects, i.e. numerical accuracy and computation time.

In `R`:

```R
?prcomp

```

says:

> …  
> Details:  
> The calculation is done by a singular value decomposition of the  
> (centered and possibly scaled) data matrix, not by using ‘eigen’  
> on the covariance matrix. This is generally the preferred method  
> for numerical accuracy.  
> …

SVD also gives the predictions of the training values for free. So I was always under the impression, that SVD is superior. Except for very large data, because it is easy to construct a covariance matrix incrementally.

---

<div class="post-metadata">

**Author:** ![stevengj](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stevengj/32/71_2.png) [@stevengj](https://discourse.julialang.org/u/stevengj)\
**Post date:** [January 16, 2019, 1:57pm UTC](https://discourse.julialang.org/t/when-to-use-svd-and-when-to-use-eigendecomposition-for-pca/19689/5 "2019-01-16T13:57:48Z")

</div>

In exact arithmetic (no rounding errors etc), the SVD of A is equivalent to computing the eigenvalues and eigenvectors of AᵀA. However, computing the “covariance” matrix AᵀA squares the condition number, i.e. it _doubles_ the number of digits that you lose to roundoff errors. Of course, if you start with 15 digits and your matrix has a condition number of 10², so that you are only losing about 2 digits, then squaring the condition number to 10⁴ still leaves you with 10+ digits. But if your matrix is badly conditioned then you could have a big problem, especially if you have inaccurate data to start with. That’s why SVD methods typically work by bidiagonalization or similar methods that avoid forming AᵀA explicitly.

However, for PCA my understanding is that there is a saving grace, because in PCA you are usually only interested in a few _largest_ singular values. In particular (covered in e.g. lecture 31 of Trefethen and Bau _Numerical Linear Algebra_), computing the k-th singular value σₖ via AᵀA increases the errors (compared to bidiagonalization-based SVD) by a factor of ≈ σ₁/σₖ where σ₁ is the largest singular value. In consequence, as long as you are only interested in singular values and vectors close in magnitude to σ₁, as is typical in PCA, then working with the covariance matrix is not so bad.

See also the discussion in [Use A'A instead of [0 A;A' 0] in svds. by andreasnoack · Pull Request #21701 · JuliaLang/julia · GitHub](https://github.com/JuliaLang/julia/pull/21701) regarding the `svds` function, which is typically used to compute only a few largest singular values (like for PCA) and hence the AᵀA method is attractive for computational efficiency despite the potential accuracy loss.

---

<div class="post-metadata">

**Author:** ![zgornel](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/zgornel/32/217487_2.png) [@zgornel](https://discourse.julialang.org/u/zgornel)\
**Post date:** [January 16, 2019, 2:14pm UTC](https://discourse.julialang.org/t/when-to-use-svd-and-when-to-use-eigendecomposition-for-pca/19689/6 "2019-01-16T14:14:07Z")

</div>

I used [TSVD.jl](https://github.com/JuliaLinearAlgebra/TSVD.jl) for [text analysis](https://zgornel.github.io/StringAnalysis.jl/dev/examples/#Semantic-Analysis-1) and seems to be working well …

```julia
julia> using SparseArrays, Arpack, TSVD
       using BenchmarkTools
       dims = 15
       A = sprand(1000,1000,0.1)
       @btime svds(A, nsv=dims);
       @btime tsvd(A, dims);
  59.119 ms (1096 allocations: 922.22 KiB)
  245.278 ms (4002 allocations: 42.94 MiB)

```

`svds` seems quite performant so a good choice however `Arpack` does not build on julia 1.0 (tests above are done on 1.2-DEV.166)