Need help with parts
1. Basis Functions for Density Estimation Suppose that we are trying to estimate the density p : [O, l] d H IR, p E 2([0, l] d ), given a dataset {x(i)}b 1 p. We will build an estimate j5 using the cosine basis functions cpk : [O, 1] H R cp1(x) = 1, cpk(x) = \\12cos((k - l)1rx) V k > 1. ( 1) In this problem we will show a impactful result, an upper-bound to the risk of our estimator p: lE [IIP - f511] = 0 ( n- 2;d) (note the big-oh notation). This result illustrates the rate at which the estimator converges in terms of the number of samples and dimensionality of the dataset. (a) (4 points) Multiple dimensions. (1) specifies basis functions for a ld domain. First, write the basis function cp a (x) indexed by the vector a E Nd , a = (a 1 , ... , ad ) using ld basis functions cp 'j (note abuse of notation). (Hint: we discussed this in class.) Second, prove that if ld basis are orthonormal ( (cpj,cp) = fro,i]d cpk(x)cpj(x)dx = IT{j = k}) then the multiple dimension basis functions are orthonormal as well ( (cp a ,cp13) = IT{a= ,8}). (b) ( 1 point) Projection Coefficients. Write out the ground truth density p in terms of pro jection coefficients aa (P) = (cp a ,P) = fro,i]d cp a (x)p(x)dx. (c) ( 1 point) Estimated Projection Coefficients. Write out the estimate of aa (p), aa (p), using the samples. (d) (4 points) Projection Coefficient Error. Show that lE [(aa (P) - aa (f5))2 ] :::; for some constant C. (Hint: decompose the error into bias and variance terms. The bias term is easy. Bound the variance term using the fact that that maximum value of cp ' is bounded.) (e) (4 points) Risk Terms. We will build our estimate using a limited number of basis func tions. In particular p(x) = where Mt= {a E Nd L a (f5)cp (x), a EMt a (2) a I llall 2:::; t} for some hypeparameter t > lE [IIP - f511] = lE [ (a (P) - a L EMt a a 2 a (f5)) ] + 0. Show that L a;(p), (3) a EM{ where M[ is the set complement. (Hint: think about what (3) implies for aa (f5) for a E M[, and use the orthonormality of the basis functions). (f) (4 points) Sobolev Tails. We will also assume that p is in an a Sobolev-type functional space. That is, suppose that the projection coefficients a(p) = {aa (P)} a ENd E 8(A) where: (4) for some A> 0. Using (4), show that L a EMf a;(p) :::; t2 ) t2 Page 2 of 7 i. (Hint: multiply L EMf a;(p) by a (g) (4 points) Initial Bound. First, Using parts (d) and (f), show that lE [IIP - fill] Citl + i, for appropriate constants C1, C2. Then, argue that IMtl = O(td) (big-oh notation) and so: lE [IIP - fill] C d t : + ;. (5) (h) (4 points) Total bound. Show that if we choose t appropriately, then lE [IIP - fill] = 0 ( n-2!d). (6) (Hint: take the derivative of (5) wrt t.) Using this upper bound: What occurs as n gets large? What occurs as d gets larger? How does the rate depend on d (e.g. is it linear?)? Page 3 of 7
