1. Sparse sequence model Consider the sub-Gaussian sequence model Y = 6'\" + c, where Y is the vector of observations in R\" for n 2 2, {9* is the parameter vector to be estimated, and c is the vector of random noise such that IE3[] = I] and 5' N subGn(02). Assume that 9* is ksparse1 i.e., Tl. ||9*||n = Z 11{93% 0} = F?- i=1 Define the hard thresholding estimator 6'\" of 6'\" with threshold 21' > 0, by A a := Y;-1{|1';-| > 21"} for each 1' E [n] := {1, . . .,n}, where 7' :2 U./210g(2n/6) for a xed 5 > 0. (a) Consider the event 8 :2 {maxiew let-I S 1"}. Use Problem 1 of Homework 5 to show that IP{8} Z 1 6. (b) Conditioning on the event 8, show that li WI 5 111111093: T) for i E [n], and conclude that n 2 N n r where fr hides a constant factor. (c) Consider the linear regression model Y = X [3* + a, where n = d, X is an orthogonal matrix in Rm\" (i.e., XTX = ,1), 3\" is k-sparse, and E N subGn(a2). Show that there exists an estimator 13 such that 1 A kl . (5 -||.3 erg s erg\"gm\" } '72. n with probability at least 1 (5