Hi ! Sorry if I am asking questions with obvious answers, but I went through some linear algebra course about SVD, just to recall what is going on in order to understand better the course on week 12 about PCA. A few very general questions :
p.s Modified the question since yesterday
When we use the tricks of solving X^T X instead of X X^T to get the eigenvectors v_j , I am wondering if we expect to have as many eigenvectors in V than in U ? In my mind, I thought U could have from 1 to D eigenvectors and V from 1 to N. So if D >> N , I would think that the number of eigenvectors we can get from resolving X^T X is smaller than what we could obtain by solving X X^T ? Am I missing something ?
Am I right by saying that in practice, resolving det(XX^T - lambda * I) = 0 involves solving a polynomial with as many degree as there are singular values ? How is this resolved in practice by standard libraries ? Also, once we found all singular values, am I right saying that we still have many linear systems to solve in order to get the eigenvectors u ? I know that usually libraries that solve PCA even with large N and D are fast. I am curious about the tricks being used.
Hi Im just going to answer the first part of the question. So if you have a DxN matrix the rank of the matrix will be maximum min(D,N) which means that the X^T X matrix will have the same rank as XX^T and therefore have the amount of eigenvectors. Which implies that V and U has the same rank. For reading I honestly recomend the SVD wikipedia page its really good!
Few generalities about SVD
Hi ! Sorry if I am asking questions with obvious answers, but I went through some linear algebra course about SVD, just to recall what is going on in order to understand better the course on week 12 about PCA. A few very general questions :
p.s Modified the question since yesterday
When we use the tricks of solving X^T X instead of X X^T to get the eigenvectors v_j , I am wondering if we expect to have as many eigenvectors in V than in U ? In my mind, I thought U could have from 1 to D eigenvectors and V from 1 to N. So if D >> N , I would think that the number of eigenvectors we can get from resolving X^T X is smaller than what we could obtain by solving X X^T ? Am I missing something ?
Am I right by saying that in practice, resolving det(XX^T - lambda * I) = 0 involves solving a polynomial with as many degree as there are singular values ? How is this resolved in practice by standard libraries ? Also, once we found all singular values, am I right saying that we still have many linear systems to solve in order to get the eigenvectors u ? I know that usually libraries that solve PCA even with large N and D are fast. I am curious about the tricks being used.
Thanks a lot in advance .
Hi Im just going to answer the first part of the question. So if you have a DxN matrix the rank of the matrix will be maximum min(D,N) which means that the X^T X matrix will have the same rank as XX^T and therefore have the amount of eigenvectors. Which implies that V and U has the same rank. For reading I honestly recomend the SVD wikipedia page its really good!
2
On question 2:
Yes, it does amount to finding the roots of a specific high-order polynomial. Analytically, this is a very hard problem, but there are efficient numerical algorithms for it. You can check https://en.wikipedia.org/wiki/Singular_value_decomposition#Numerical_approach for that.
Add comment