---- > [!theorem] Theorem. ([[singular value hard thresholding]]) > Consider the low-[[rank]] [[matrix]] approximation problem $\hat{X}= \arg \min_{X \in \mathbb{F}^{M \times N}} \frac{1}{2} \|Y-X\|_{F}^{2} + \beta \rank (X).$ > Because the [[Frobenius norm]] is [[unitarily invariant norm of matrices|unitarily invariant]] and $\rank(\cdot)$ [[rank of matrix product|is as well]], we can apply the [[characterization of unitarily invariant unconstrained regularized low-rank approximations]] to ultimately obtain the solution $\begin{align} \hat{X} = & \sum_{k=1}^{r} h_{\text{hard}}(\sigma_{k}; \beta) u_{k}v_{k}' \\ h_{\text{hard}}(\sigma_{k}; \beta) := & \begin{cases} v & \frac{1}{2}|\sigma|^{2} > \beta \\ 0 & \text{otherwise.} \end{cases} \end{align},$ where $U_{r}\Sigma_{r}V_{r}'=\sum_{k=1}^{r} \sigma_{k}u_{k}v_{k}'$ is a [[compact svd]] of the observed data $Y$. > [!proof]- Proof. ([[singular value hard thresholding]]) > ~ Using the [[characterization of unitarily invariant unconstrained regularized low-rank approximations]] we know from the outset that our solution looks like $\begin{align} \hat{X} = & U_{r} \hat{\Sigma}_{r} V_{r}' \\ \hat{\Sigma}_{r} = & \arg \min_{S = \text{Diag}(s_{1},\dots,s_{r})} \frac{1}{2} \|\Sigma_{r}- S\| _{F}^{2} + \beta \rank (S). \end{align}$ $\Sigma_{r}-S$ is [[diagonal matrix|diagonal]], thus has [[singular values]] $\{ \sigma_{k}- s_{k}\}_{k=1}^{r}$. Using that [[Frobenius norm]] is sum of squares of [[singular values]], the [[objective function]] can be rewritten thus: $\frac{1}{2} \|\Sigma_{r}- S\|_{F}^{2} + \beta \rank (S) = \frac{1}{2}\sum_{k=1}^{r} [(\sigma_{r}-s_{r})^{2} + \mathbb{1}_{\{ s_{k} \neq 0 \}}].$ But this is just [[proximal operator|hard thresholding]], which has the solution given in the theorem statement. ---- #### ----- #### 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 > ```