As a theory talk, all points here should be considered suspect until verified as I’m not used to these sorts of talks and may misunderstand
- JL Lemma: Every set of n points in euclidian space can be embedded into O(eps^-2 logn) dim eucildian space so that all pairwise distances are preserved to a 1+eps factor (original dim is arbitrary – this only matters on number of points)
- Speeds geom algs by reducing dim of input
- Low mem streaming algs for lin algebra
- Similar to RIP matrices from compressed sensing
- Given an eps and delta, you can find a matrix that does a dim reduction while maintaining distances ? Can show how large the matrix has to be.
- The embedding is normally expensive, this talk is about how to do it more efficiently
- The speedups are much better, O(eps^-2 logn log^4 d) but slow to embed sparse vectors
- Speaker’s approach got costs down to O(eps^-1 log(1/delta)) for sparse vectors
- Recovery procedure isn’t applicable in all settings
- …lost