tag:blogger.com,1999:blog-6555947.post7696856316448295652..comments2014-01-12T10:46:48.153-07:00Comments on The Geomblog: An intuitive argument for the JL lemma ?Suresh Venkatasubramaniannoreply@blogger.comBlogger4125tag:blogger.com,1999:blog-6555947.post-77408437864196667252011-11-16T16:39:29.982-07:002011-11-16T16:39:29.982-07:00(Note you can also prove things like the Chernoff ...(Note you can also prove things like the Chernoff bound by this sort of approach: rather than use the moment generating function, just bound a high-order moment from first principles. Personally this is how I usually end proving it since I tend to forget which clever Taylor-approximation tricks to use.)Jelani Nelsonhttp://www.blogger.com/profile/00216475103758212305noreply@blogger.comtag:blogger.com,1999:blog-6555947.post-11413187110958133932011-11-16T16:28:17.546-07:002011-11-16T16:28:17.546-07:00The basic idea is to write |Sx|_2^2 = |x|_2^2 + Z,...The basic idea is to write |Sx|_2^2 = |x|_2^2 + Z, where S is your sign matrix and Z is the error term. Then Z = (1/k)*sum_{r=1}^k Z_r where Z_r = sum_{i!=j}S_{r,i}*S_{r,j}*x_i*x_j. Then Pr[|Z| > eps] < eps^{-t}*E[Z^t] for t even. Take t = log(1/delta) and bound E[Z^t] by (eps/2)^t and you're done. To bound E[Z^t], expand it out into monomials and observe things boil down to bounding E[Z_r^p] for p <= t. This can be done by expanding out Z_r^p, associating a graph to every monomial, grouping monomials with isomorphic graphs, then doing a bunch of computations.<br /><br />It's basically the approach Daniel and I used to analyze sparse JL (not the version with codes, but with random hashing). The proof is (only slightly) simpler in this case because there's no hashing. Nothing in the proof requires more than undergrad knowledge (basically, stirling's formula), but overall it is not a short computation.Jelani Nelsonhttp://www.blogger.com/profile/00216475103758212305noreply@blogger.comtag:blogger.com,1999:blog-6555947.post-55468024596412114532011-11-15T09:04:23.505-07:002011-11-15T09:04:23.505-07:00is it something you can summarize here ?is it something you can summarize here ?Suresh Venkatasubramanianhttp://www.blogger.com/profile/15898357513326041822noreply@blogger.comtag:blogger.com,1999:blog-6555947.post-10145506415770117032011-11-15T04:32:26.715-07:002011-11-15T04:32:26.715-07:00At least for the Achlioptas construction with rand...At least for the Achlioptas construction with random signs, there is an "undergrad" proof that bounds the log(1/delta)th moment via some counting. It's more "grungy" than "intuitive" though.Jelani Nelsonhttp://www.blogger.com/profile/00216475103758212305noreply@blogger.com