THEOREM 4.5 (Best Low-rank Approximation). Let Y e Rnixn2, and consider the following optimization problem min [X - YIF ; (4.2.10) subject to rank(X) Er. Every optimal solution X to the above problem has the form X = >_, stuiv;, where Y = Zi=1 min(m1,n2) osu;v; is a (full) singular value decomposition of Y. In fact, the same solution (truncating the SVD) also solves the low-rank ap- proximation problem when the error is measured in the operator norm, or any other orthogonal-invariant matrix norm (see Appendix A). Please see Exercise 4.3 for guidance on how to prove Theorem 4.5.| 4.3 (Best Rank-r Approximation). We prove Theorem 4.5. First, consider the special case in which Y = > = diag(01, . .., On) with 01 > 02 > .. . > On. An arbitrary rank-r matrix X can be expressed as X = FG* with F E Rnixr, F*F = I and G E Rn2XT. 1 Argue that for any fixed F, the solution to the optimization problem min GERn2Xr (4.7.2) is given by G = E*F, and the optimal cost is . 13(dd - I)Il (4.7.3) 2 Let P = I - FF*, and write vi = ||Pei|13. Argue that Et_ vi = n1 - T and vi E [0, 1]. Conclude that (4.7.4) 1= 1 i=r+l with equality if and only if v1 = v2 = . . . = vr = 0 and Vr+1 = .. . = Un. Conclude that Theorem 4.5 holds in the special case Y = E. 3 Extend your argument to the situation in which the of are not distinct fi.e., oi = 0itl for some i)