Estimation of Small Norms in Data Streams
Presenter
December 5, 2011
Keywords:
- geometric algorithms
- graph theory algorithms
- combinatorial optimization
- online algorithms
- high dimensional data analysis
- ell_p space
MSC:
- 05Cxx
- 05-xx
- 68W25
- 68W40
- 68Wxx
- 68W27
Abstract
In the data stream model one receives coordinate-wise updates to a high-dimensional vector and must process all the updates using very small memory while still being able to approximate functions of the underlying vector. I will discuss the case where the function we wish to approximate is the p-norm for p