Confidence-Optimal Random Embeddings
  The seminal result of Johnson and Lindenstrauss on random embeddings has been
intensively studied in applied and theoretical computer science. Despite that
vast body of literature, we still lack of complete understanding of statistical
properties of random projections; a particularly intriguing question is: why
are the theoretical bounds that far behind the empirically observed
performance? Motivated by this question, this work develops
Johnson-Lindenstrauss distributions with optimal, data-oblivious, statistical
confidence bounds. These bounds are numerically best possible, for any given
data dimension, embedding dimension, and distortion tolerance. They improve
upon prior works in terms of statistical accuracy, as well as exactly determine
the no-go regimes for data-oblivious approaches. Furthermore, the corresponding
projection matrices are efficiently samplable. The construction relies on
orthogonal matrices, and the proof uses certain elegant properties of the unit
sphere. The following techniques introduced in this work are of independent
interest: a) a compact expression for distortion in terms of singular
eigenvalues of the projection matrix, b) a parametrization linking the unit
sphere and the Dirichlet distribution and c) anti-concentration bounds for the
Dirichlet distribution.
  Besides the technical contribution, the paper presents applications and
numerical evaluation along with working implementation in Python.
