Problem Statement

Implement Principal Component Analysis (PCA) using Singular Value Decomposition (SVD). Return the top k principal components and their explained variance ratios.

Algorithm:

1. Center the data: X_c = X - mean(X, axis=0)
2. Compute the thin SVD: X_c = U S Vᵀ
3. The top k principal components are the first k rows of Vᵀ
4. The variance explained by each component is S_i² / Σ S_j²

Function signature:

def pca_svd(X: list, k: int) -> tuple:
    # returns (components, ratios)
    # components: k x d list of lists — principal component vectors
    # ratios: list of k floats — explained variance ratios

Input Format

Line 1: n d k — number of points, dimensions, components to return
Lines 2..n+1: space-separated floats — data matrix rows

Output Format

k lines: the principal component vectors (10 significant figures each)
k lines: one explained variance ratio per line (10 significant figures)

Example

Input:

4 2 2
2.0 0.0
0.0 2.0
-2.0 0.0
0.0 -2.0

Output:

-1 -0
-0 -1
0.5
0.5

Notes

• Use numpy.linalg.svd with full_matrices=False for the thin decomposition.
• Principal components are rows of Vᵀ; their signs may vary by implementation (both +v and -v are valid).
• The explained variance ratios sum to ≤ 1 for k < d, and exactly 1 for k = d.