Very Sparse Stable Random Projections, Estimators and Tail Bounds for
  Stable Random Projections
  This paper will focus on three different aspects in improving the current
practice of stable random projections.
  Firstly, we propose {\em very sparse stable random projections} to
significantly reduce the processing and storage cost, by replacing the
$\alpha$-stable distribution with a mixture of a symmetric $\alpha$-Pareto
distribution (with probability $\beta$, $0<\beta\leq1$) and a point mass at the
origin (with a probability $1-\beta$). This leads to a significant
$\frac{1}{\beta}$-fold speedup for small $\beta$.
  Secondly, we provide an improved estimator for recovering the original
$l_\alpha$ norms from the projected data. The standard estimator is based on
the (absolute) sample median, while we suggest using the geometric mean. The
geometric mean estimator we propose is strictly unbiased and is easier to
study. Moreover, the geometric mean estimator is more accurate, especially
non-asymptotically.
  Thirdly, we provide an adequate answer to the basic question of how many
projections (samples) are needed for achieving some pre-specified level of
accuracy. \cite{Proc:Indyk_FOCS00,Article:Indyk_TKDE03} did not provide a
criterion that can be used in practice. The geometric mean estimator we propose
allows us to derive sharp tail bounds which can be expressed in exponential
forms with constants explicitly given.
