Problem Statement

Given a matrix A of shape n × m, compute the Frobenius norm error of the best rank-k approximation.

By the Eckart-Young theorem, the best rank-k approximation in the Frobenius norm is:

A_k = Σ_{i=1}^{k} σ_i u_i vᵢᵀ

and the approximation error is:

||A - A_k||_F = sqrt(Σ_{i=k+1}^{r} σ_i²)

where σ_i are the singular values in descending order and r = rank(A).

Function signature:

def svd_approx_error(A: np.ndarray, k: int) -> float:
    # returns the Frobenius error of the best rank-k approximation

Input Format

Line 1: n m k — matrix dimensions and target rank
Lines 2..n+1: m space-separated floats per row

Output Format

One line: the Frobenius approximation error (10 significant figures)

Example

Input:

3 3 1
1.0 2.0 3.0
4.0 5.0 6.0
7.0 8.0 9.0

Output:

1.068369515

Derivation

The Eckart-Young theorem states that among all rank-k matrices, A_k = U_k Σ_k Vᵀ_k minimizes both the Frobenius and spectral norms of the residual. The discarded singular values capture the residual:

||A - A_k||²_F = Σ_{i=k+1}^{r} σ_i²

For this 3×3 matrix (which has rank 2 since rows are arithmetic progressions), the singular values are approximately [16.88, 1.07, 0]. Keeping only the largest (k=1) discards σ₂ ≈ 1.068 and σ₃ ≈ 0, giving error ≈ 1.068.

Notes

• Use numpy.linalg.svd(A, full_matrices=False) to get singular values.
• Only the singular values (not U and V) are needed for computing the error.
• If k ≥ rank(A), the error is 0.