Answer Happy

This problem sheet asks you to prove some well known results. Although the algebra is easy the proofs are not entirely straightforward. There are marks assigned to the readability of the solution and also how well laid out and explained the steps you make are. (A good proof needs to be easy to follow you need not comment on trivial algebra, but there should not be steps that are difficult to follow). (3) = (4) 3 The p-norm of a matrix M, for p > 1 is defined to satisfy MI || Mx || = max 240 || 3 | max Mx 2:2n=1 where || ||is the p norm of a vector defined by 1/P || 20 | lail" Note that with this definition ||MX|L, 5. ||M||||||| (where the inequality is tight, i.e. there exists a vector where the inequality becomes an equality). (a) If U is an orthogonal matrix show that for any vector v that || Uv||2 = ||v||2. Use this to show |UA||2 = || A||2. (b) If V is an orthogonal matrix show that ||AV|||2 = ||A||2. (c) Use the SVD M = USVT and the results of part (a) and part (b) to show that ||M ||2 = $||2 (d) Compute ||S2| where x = (21,B2,...,In) and S = diag(81,82,..., Sn) is the diag- onal matrix of singular values, si. (e) Write down the Lagrangian, L, to maximise || SX || subject to || 20 || 3 = 1. Compute the extrumum conditions given by al/ax; = 0. Let (sala = 1,2,...) be the set of unique singular values and la the set of indices such that si = sa if I E I.. Using the extremum condition and the constraint, write down the set of extremum values for S. and hence show that M ||2 = Smax where Smax is the maximum singular value and M = USVT.