---- > [!theorem] Theorem. ([[Eckart-Young-Mirsky theorem]]) > Let $A \in \mathbb{F}^{M \times N}$ have [[rank]] $r \leq \min(M,N)$. For $K \leq r$, the solution to the [[convex set|nonconvex]] [[optimization problem]] $\arg \min_{B \in \mathbb{F}^{M \times N}: \rank B \leq K} \|B - A\|_{\text{UI}}^{2}$ > is given by the $K$-[[truncated svd]] of $A$: $\hat{A}_{K}= \sum_{k=1}^{K} \sigma_{k}u_{k}v_{k}', \text{ where } A=U\Sigma V' = \sum_{k=1}^{\min(M,N)} \sigma_{k}u_{k}v_{k}'.$ > The [[ERM error decomposition|approximation error]] depends on the [[singular values]] of the discarded terms: $\|\hat{A}_{K} - A\|_{F} = \sqrt{ \sum_{k=K+1}^{\min(M,N)} \sigma_{k}^{2} } \leq \|B-A\|_{F}, \ \forall B \text{ with } \rank B \leq K.$ > \ > Here, $\|\cdot\|_{\text{UI}}$ denotes any [[unitarily invariant vector norm]] [[Frobenius norm]] and we took an [[Singular Value Decomposition of a Matrix|svd]] of $A$ when writing $A=U \Sigma V'$. > \ > If $\sigma_{K}>\sigma_{K+1}$ then $\hat{A}_{K}$ is unique. Else $\sigma_{K}=\sigma_{K+1}$ and it is not. > [!proof]- Proof. ([[Eckart-Young-Mirsky theorem]]) > ~ ---- #### ----- #### References > [!backlink] > ```dataview TABLE rows.file.link as "Further Reading" FROM [[]] FLATTEN file.tags GROUP BY file.tags as Tag > [!frontlink] > ```dataview > TABLE rows.file.link as "Further Reading" > FROM outgoing([[]]) > FLATTEN file.tags as Tag > WHERE Tag = "#definition" OR Tag = "#theorem" OR Tag = "#MOC" OR Tag = "#proposition" OR Tag = "#axiom" > GROUP BY Tag > ```