In this talk we will give an introduction to random projections. Define the linear separability of data by a margin $\gamma$. Then we will see a simple algorithm to learn a linear separator and show that it will have error at most $\frac{1}{2} - \frac{\gamma}{4}$ with probability $\Omega(\gamma)$.
