## Abstract

For dimension reduction in l_{1}, one can multiply a data matrix A ε ℝ^{n×D} by R ε ℝ^{D×k} (k ≪ D) whose entries are i.i.d. samples of Cauchy. The impossibility result says one can not recover the pairwise l_{1} distances in A from B = AR ε^{ℝn×k}, using linear estimators. However, nonlinear estimators are still useful for certain applications in data stream computations, information retrieval, learning, and data mining. We propose three types of nonlinear estimators: the bias-corrected sample median estimator, the bias-corrected geometric mean estimator, and the bias-corrected maximum likelihood estimator. We derive tail bounds for the geometric mean estimator and establish that k = O (&logn/ε^{2}) suffices with the constants explicitly given. Asymptotically (as k → ∞), both the sample median estimator and the geometric mean estimator are about 80% efficient compared to the maximum likelihood estimator (MLE). We analyze the moments of the MLE and propose approximating the distribution of the MLE by an inverse Gaussian.

Original language | English (US) |
---|---|

Title of host publication | Learning Theory - 20th Annual Conference on Learning Theory, COLT 2007, Proceedings |

Publisher | Springer Verlag |

Pages | 514-529 |

Number of pages | 16 |

ISBN (Print) | 9783540729259 |

DOIs | |

State | Published - 2007 |

Externally published | Yes |

Event | 20th Annual Conference on Learning Theory, COLT 2007 - San Diego, CA, United States Duration: Jun 13 2007 → Jun 15 2007 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 4539 LNAI |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Other

Other | 20th Annual Conference on Learning Theory, COLT 2007 |
---|---|

Country/Territory | United States |

City | San Diego, CA |

Period | 6/13/07 → 6/15/07 |

## All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- Computer Science(all)

## Fingerprint

Dive into the research topics of 'Nonlinear estimators and tail bounds for dimension reduction in l_{1}using cauchy random projections'. Together they form a unique fingerprint.