Prove Eckart–Young–Mirsky

ProofAdvanced⏱ 1 hourFine-Tuningsvdapproximationweyl

Problem

Prove that the best rank- $r$ approximation to $M$ in Frobenius norm is the truncated SVD, with error $\sum_{i>r}\sigma_i^2$ . Then compute the relative error for a matrix whose singular values decay as $\sigma_i = \sigma_1 i^{-\beta}$ , and determine the rank needed to capture 90% of the squared Frobenius norm for $\beta = 0.5$ and $\beta = 1.5$ .

Write a complete argument. Every inequality you use should be one you could state precisely.

Hints

Hints — 0 of 3 revealed

Solution

Opening this before you have a real attempt on paper is the fastest way to feel like you understand something you cannot reproduce.

Related problems

All problems

Problem	Field	Type	Difficulty	Time
Adapter parameter counts	Fine-Tuning	Numerical	Foundation	15 min
Ridge regression in the SVD basis	Classical ML	Proof	Intermediate	30 min
The operator norm on a net	High-Dim Probability	Proof	Intermediate	30 min
The α/r scaling	Fine-Tuning	Proof	Intermediate	30 min
Why exactly one factor starts at zero	Fine-Tuning	Proof	Intermediate	30 min