Nonlinear Estimators and Tail Bounds for Dimension Reduction in $l_1$
  Using Cauchy Random Projections
  For dimension reduction in $l_1$, the method of {\em Cauchy random
projections} multiplies the original data matrix $\mathbf{A}
\in\mathbb{R}^{n\times D}$ with a random matrix $\mathbf{R} \in
\mathbb{R}^{D\times k}$ ($k\ll\min(n,D)$) whose entries are i.i.d. samples of
the standard Cauchy C(0,1). Because of the impossibility results, one can not
hope to recover the pairwise $l_1$ distances in $\mathbf{A}$ from $\mathbf{B} =
\mathbf{AR} \in \mathbb{R}^{n\times k}$, using linear estimators without
incurring large errors. However, nonlinear estimators are still useful for
certain applications in data stream computation, 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. The sample median estimator and
the geometric mean estimator are asymptotically (as $k\to \infty$) equivalent
but the latter is more accurate at small $k$. We derive explicit tail bounds
for the geometric mean estimator and establish an analog of the
Johnson-Lindenstrauss (JL) lemma for dimension reduction in $l_1$, which is
weaker than the classical JL lemma for dimension reduction in $l_2$.
  Asymptotically, both the sample median estimator and the geometric mean
estimators 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.
