Loading...
Please wait, while we are loading the content...
Lecture 3 Two applications of the Chernoff bound
| Content Provider | Semantic Scholar |
|---|---|
| Abstract | Two applications of the Chernoff bound In this lecture we see two applications of the Chernoff bound. The first one is to a geometric problem: reducing the dimension of high-dimensional data. It will require us to prove a variant of the bound that is adapted to Gaussian (instead of Bernoulli) random variables, and will prove very useful in future algorithmic applications. The second application is to a purely combinatorial problem: counting the maximum load of a bin when balls are allocated (almost) randomly. Suppose given a set of data points x 1 ,. .. , x n ∈ R d , where we think of d as being very large. For example, the x i are " feature vectors " : each of the d coordinates of x i contains a numerical value for an attribute associated to the i-th object in our dataset. Suppose we are only interested in the rough geometry of this set — that is, we care about pairwise distances x i − x j 2 , a good measure of similarity between elements of our dataset. We might also want to compute the distances y − x i 2 , where y is a new element. But d is very large. Is there a way to provide a " low-dimensional sketch " of our dataset that would capture its geometry, at least in an approximate sense. Note that we can already assume d ≤ n. This is because the linear span of n vectors has dimension at most n, so we don't need more than n dimensions to represent the vectors. The Johnson-Lindenstrauss (JL) lemma shows that, if we are willing to allow for a small approximation error in the distances, we can go much lower — essentially, log(n) dimensions. More generally, the JL dimensionality reduction lemma provides a powerful technique for solving high-dimensional problems such as: |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://users.cms.caltech.edu/~vidick/teaching/CS139_Winter17/notes/lecture03.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
