Approximating the product of two large matrices using singular value decomposition may be analogous to a Taylor series expansion where first order terms become more important. The cascade plots from genome-wide association studies for example look like genetic variants are being ranked by effect size.
I asked ChatGPT whether such a phenomenom is possible when multiplying very large matrices. Here, is what it says about complexity of the computations when doing ordinary matrix multiplications and when doing matrix multiplications with approximations using TSVD. If you have recommended readings please e-mail me as this is new to me.
ChatGPT interaction
If you want to multiple two matrices can you take SVD of the matrix and just multiply the first two components to get an approximation? What is complexity of that action compared to multiplying two matrices fully directly?
Yes, you can approximate the product of two matrices by leveraging the Singular Value Decomposition (SVD) of one of the matrices. Here’s a step-by-step explanation:
SVD and Matrix Multiplication Approximation
- SVD of Matrix \(A\):
Suppose you want to multiply matrices \(A\) and \(B\). First, take the SVD of \(A\):
$$ A = U \Sigma V^T$$
where:
- \(U\) is an \(m \times m\) orthogonal matrix,
- \(\Sigma\) is an \(m \times n\) diagonal matrix with singular values on the diagonal,
- \(V\) is an \(n \times n\) orthogonal matrix.
- Truncated SVD for Approximation:
If you only want an approximation, you can use a truncated SVD. Let \(k\) be the number of singular values you retain (with \(k \leq \min(m,n)\)). The truncated SVD of \(A\) can be written as:
$$A \approx U_k \Sigma_k V_k^T$$
where \(U_k\) contains the first \(k\) columns of \(U\), \(\Sigma_k\) is the \(k \times k\) leading principal submatrix of \(\Sigma\), and \(V_k\) contains the first \(k\) columns of \(V\). - Approximating the Product \(AB\):
Now, multiply the truncated components:
$$ AB \approx (U_k \Sigma_k V_k^T)B = U_k \Sigma_k (V_k^T B)$$
Here, \(V_k^T B\) involves an \(n \times k\) matrix \(V_k\) and an \(n \times p\) matrix \(B\). The product \(V_k^T B\) results in a \(k \times p\) matrix. Then, you multiply \(U_k \Sigma_k\) (which is \(m \times k\)) by the \(k \times p\) result from the previous step.
Complexity Analysis
Direct Matrix Multiplication
Complexity: \(O(mnp)\) for multiplying \(A\) (\(m \times n\)) with \(B\) (\(n \times p\)).
Approximate Matrix Multiplication Using Truncated SVD
- SVD Calculation:
- Full SVD has a complexity of \(O(mn \min(m,n))\).
- For truncated SVD to compute only the first \(k\) singular values and vectors, various efficient algorithms can reduce this to \(O(mnk)\).
- Matrix Multiplications:
- \(V_k^T B\): This involves multiplying \(V_k^T\) (\(k \times n\)) with \(B\) (\(n \times p\)), which has a complexity of \(O(knp)\).
- \(U_k \Sigma_k (V_k^T B)\): This involves multiplying \(U_k \Sigma_k\) (\(m \times k\)) with the \(k \times p\) result, which has a complexity of \(O(mkp)\).
Total Complexity
Truncated SVD: \(O(mnk)\)
Matrix Multiplications: \(O(knp) + O(mkp) = O(mkp + knp)\)
Total: \(O(mnk + mkp + knp)\)
When \(k\) is significantly smaller than \(\min(m,n)\), the total complexity \(O(mnk + mkp + knp)\) is much less than the direct multiplication complexity \(O(mnp)\). This makes the truncated SVD approach advantageous for large matrices where a lower-rank approximation is sufficient.
