{
"metadata": {
"name": ""
},
"nbformat": 3,
"nbformat_minor": 0,
"worksheets": [
{
"cells": [
{
"cell_type": "heading",
"level": 1,
"metadata": {},
"source": [
"Testing a Quasi-Isometric Quantized Embedding"
]
},
{
"cell_type": "heading",
"level": 2,
"metadata": {},
"source": [
"Introduction:"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"$$\n",
"\\newcommand{\\bs}{\\boldsymbol}\n",
"\\newcommand{\\cl}{\\mathcal}\n",
"\\newcommand{\\bb}{\\mathbb}\n",
"$$ \n",
"This simple *python notebook* aims at estimating the validity of some of the results explained in the paper \n",
" \n",
"> \"*A Quantized Johnson Lindenstrauss Lemma: The Finding of Buffon's Needle*\"
\n",
"> by [Laurent Jacques](http://perso.uclouvain.be/laurent.jacques/) [(arXiv)](http://arxiv.org/abs/1309.1507)
\n",
"> \"In 1733, Georges-Louis Leclerc, Comte de Buffon in France, set the ground of geometric probability theory by defining an enlightening problem: What is the probability that a needle thrown randomly on a ground made of equispaced parallel strips lies on two of them? In this work, we show that the solution to this problem, and its generalization to N dimensions, allows us to discover a quantized form of the Johnson-Lindenstrauss (JL) Lemma, i.e., one that combines a linear dimensionality reduction procedure with a uniform quantization of precision $\\delta>0$. In particular, given a finite set $\\cl S \\in \\bb R^N$ of $S$ points and a distortion level $\\epsilon>0$, as soon as $M > M_0 = O(\\log |S|/\\epsilon^2)$, we can (randomly) construct a mapping from $(\\cl S, \\ell_2)$ to $((\\delta \\bb Z)^M, \\ell_1)$ that approximately preserves the pairwise distances between the points of $\\cl S$. Interestingly, compared to the common JL Lemma, the mapping is quasi-isometric and we observe both an additive and a multiplicative distortions on the embedded distances. These two distortions, however, decay as $O(\\sqrt{\\log |S|/M})$ when $M$ increases. Moreover, for coarse quantization, i.e., for high $\\delta$ compared to the set radius, the distortion is mainly additive, while for small $\\delta$ we tend to a Lipschitz isometric embedding. Finally, we show that there exists \"almost\" a quasi-isometric embedding of $(\\cl S, \\ell_2)$ in $((\\delta \\bb Z)^M, \\ell_2)$. This one involves a non-linear distortion of the $\\ell_2$-distance in $\\cl S$ that vanishes for distant points in this set. Noticeably, the additive distortion in this case decays slower as $O((\\log S/M)^{1/4})$.\" \n",
"\n",
"\n",
"In particular, our objective is to study the behavior of a nonlinear mapping from $\\bb R^N$ to $\\bb R^M$, for two specific dimensions $M,N \\in \\bb N$. This mapping is defined as follows. \n",
"\n",
"Let a random (sensing) matrix $\\bs \\Phi \\in \\bb R^{M \\times N}$ be such that each component $\\Phi_{ij} \\sim_{\\rm iid} \\cl N(0,1)$, or more shorthly $\\bs \\Phi \\sim \\cl N^{M\\times N}(0,1)$.\n",
"\n",
"We want to combine the common random projection realized by $\\bs \\Phi$ with the following non-linear operation, i.e., a uniform scalar quantizer of resolution $\\delta > 0$:\n",
"
\n",
"\n",
"$$\n",
"\\qquad\\cl Q_\\delta[\\lambda] = \\delta \\lfloor \\lambda /\u00a0\\delta \\rfloor. \n",
"$$\n",
"
\n",
"(remark: we could define instead a *midrise* quantizer by adding $\\delta/2$ to the definition above, and the rest of the development would be unchanged) \n",
"\n",
"This combination reads\n",
"
\n",
"\n",
"$$\n",
"\\qquad\\bs \\psi_\\delta(\\bs x) := \\cl Q_\\delta(\\bs\\Phi \\bs x + \\bs \\xi)\n",
"$$\n",
"
\n",
"with $\\bs \\xi \\sim \\cl U^M([0, \\delta])$ is a *dithering* vector, i.e., a random uniform vector in $\\bb R^M$ such that $u_i \\sim_{\\rm iid} \\cl U([0, \\delta])$, and $\\bs \\psi_\\delta:\\bb R^N \\to (\\delta \\bb Z)^M$ $ is our mapping of interest.\n",
"\n",
"In Proposition 13 (page 16) of the paper above, it shown that\n",
"\n",
"> **Proposition 13:** Fix $\\epsilon_0>0$, $0< \\epsilon\\leq \\epsilon_0$ and $\\delta>0$. There exist two values\n",
"$c,c'>0$ only depending on $\\epsilon_0$ such that, for\n",
"$\\bs\\Phi \\sim \\cl N^{M\\times N}(0,1)$ and $\\bs \\xi\\sim \\cl U^M([0, \\delta])$, both determining the mapping\n",
"$\\bs\\psi_\\delta$ above, and for $\\bs u, \\bs v\\in\\bb R^N$,\n",
"
\n",
"$$\\qquad(1 - c\\epsilon) \\|\\bs u - \\bs v\\| - c'\\epsilon\\delta\\ \\leq\\ \\tfrac\n",
"{\\sqrt\\pi}{\\sqrt 2 M} \\|\\bs\\psi_\\delta(\\bs u) - \\bs\\psi_\\delta(\\bs v)\\|_1\\ \\leq\\ \n",
"(1 + c\\epsilon)\\|\\bs u - \\bs v\\| + c'\\epsilon\\delta.\\tag{1}\n",
"$$\n",
"
\n",
"with a probability higher than $1 - 2 e^{-\\epsilon^2M}$.\n",
"\n",
"This proposition shows that the random quantity $c_\\psi M^{-1} \\|\\bs\\psi_\\delta(\\bs u) - \\bs\\psi_\\delta(\\bs v)\\|_1$ with $c_\\psi = \\sqrt{\\pi/2}$ *concentrates* around its mean $\\|\\bs u - \\bs v\\|$. However, conversely to linear random projections, this concentration phenomenon displays two kind of deviation: a standard multiplicative one (the $1\\pm c\\epsilon$ factor) and an *additive* one in $\\pm c'\\epsilon\\delta$. \n",
"\n",
"Moreover, forcing (1) to be valid at constant probability, we deduce also that $\\epsilon = O(1/\\sqrt M)$, i.e., showing that both the multiplicative and the additive distortion decay as $O(1/\\sqrt M)$ with respect to $M$.\n",
"\n",
"> *Remark:* From a standard union bound argument (see the paper), this result allows one to show the existence of a non-linear embedding from a set $\\cl S \\subset \\bb R^N$ to $(\\delta \\bb Z)^M$, as soon as $M \\geq M_0 = O( \\epsilon^{-2}\\,\\log |\\cl S|)$. Proposition 13 is thus central to reach this property. \n",
"\n",
"This notebook proposes to test the behavior of the two distortions displayed in (1). \n",
"\n",
"For that, arbitrarily fixing $\\|\\bs u - \\bs v\\|=1$ by normalizing conveniently $\\bs u$ and $\\bs v$ (e.g., after their random selection in $\\bb R^N$), we study the standard deviation of the random variable\n",
"
\n",
"$$\n",
"\\qquad V_\\psi = \\tfrac{\\sqrt\\pi}{\\sqrt 2 M} \\|\\bs\\psi_\\delta(\\bs u) - \\bs\\psi_\\delta(\\bs v)\\|_1.\n",
"$$\n",
"\n",
"> *Remark:* the concentration (1) is invariant under the coordinate change $\\bs u \\to \\lambda \\bs u$, $\\bs v \\to \\lambda \\bs v$ and $\\delta \\to |\\lambda| \\delta$ for any $\\lambda \\neq 0$, which allows us to set $\\|\\bs u - \\bs v\\|=1$ without any loss of generality (providing we study the variability of (1) in $\\delta$). \n",
"\n",
"Although this random variable displays a non-trivial distribution1, we expect anyway that, if Prop. 13 above is true, \n",
"
\n",
"$$\n",
"\\qquad (\\text{Var}\\ V_\\psi)^{1/2}\\quad \\simeq\\quad a\\ \\epsilon\\ +\\ b\\epsilon\\ \\delta,\\quad \\text{for some }a,b > 0,\n",
"$$\n",
"\n",
"and possibly find the constants $a, b>0$ by a simple linear fit.\n",
"\n",
"---\n",
"
1: Actually, a mixture of *Buffon* random variable and of a Chi distribution with $N$ degrees of freedom.
" ] }, { "cell_type": "heading", "level": 2, "metadata": {}, "source": [ "The simulations:\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "> *Remark:* launch ipython notebook with the pylab option, i.e.,Laurent Jacques, November 2013
" ] } ], "metadata": {} } ] }