Sparse recovery using sparse matrices
Event details
| Date | 25.06.2009 |
| Hour | 15:15 |
| Speaker | Prof. Piotr Indyk, MIT |
| Location | |
| Category | Conferences - Seminars |
Over the recent years, a new *linear* method for compressing high-dimensional data has been discovered. For any high-dimensional vector x, its *sketch* is equal to Ax, where A is a carefully designed m x n matrix (possibly chosen at random). Although typically the sketch length m is much smaller than the number of dimensions n, the sketch often contains enough information to recover a *sparse approximation* to x. At the same time, the linearity of the sketching method is very convenient for many applications, such as data stream computing and compressed sensing. The major sketching approaches can be classified as either combinatorial (using sparse sketching matrices) or geometric (using dense sketching matrices). Traditionally they have achieved different trade-offs, notably between the compression rate and the running time. In this talk we show that, in a sense, the combinatorial and geometric approaches are based on different manifestations of the same phenomenon. This connection will enable us to obtain several novel algorithms and constructions, including the first known algorithm that provably achieves the optimal measurement bound and near-linear recovery time. Prof. Indyk's homepage
Practical information
- General public
- Free