Deducing the Sphere Packing Bound from the Shannon Coding theorem

In the following analysis, we derive the Hamming Bound under the Hamming Metric via the Shannon Coding theorem. Assuming the equivalence of norms, this has a natural interpretation as a Sphere Packing Bound on the metric space of all possible codewords.

Introduction:

It is known that the K-Nearest Neighbors problem may be understood as a local version of the high-dimensional Sphere Packing problem. Motivated by this insight, we shall explore this connection from an information-theoretic perspective which will allow us to demystify more complex Manifold Learning algorithms.

In particular, we find a normalised volume constraint in terms of the number of bits required to identify the nearest neighbor of an arbitrary sphere \(X\) sampled from a finite collection of closely-packed spheres.

The Sphere Packing Bound:

Let’s suppose we have a d-dimensional space and we want to pick non-overlapping spheres of radius \(r\) in this Euclidean space. Without loss of generality, the centre of each sphere defines a binary codeword which may deviate in at most \(r\) locations relative to the centre.

Now, let \(V_s\) be the volume of a single sphere and \(V_d\) be the volume of the d-dimensional space. We find that the maximum number of non-overlapping spheres that may be packed into the space must satisfy:

\[\begin{equation} N \leq \frac{V_d}{V_s} \tag{1} \end{equation}\]

Meanwhile, if we sample a particular sphere \(X\) from the Maximum Entropy distribution:

\[\begin{equation} H(X) = \log_2 N \tag{2} \end{equation}\]

and any particular codeword for \(X\), \(C(X)\), has length \(\mathcal{L}\) bounded as follows:

\[\begin{equation} \mathcal{L} \geq H(X) \tag{3} \end{equation}\]

due to Shannon’s Source Coding theorem.

It follows that through sampling with replacement under the Maximum Entropy distribution, the typical probability that we identify a particular sphere of interest such as the nearest neighbor of \(X\) among the collection of \(N\) spheres is bounded as follows:

\[\begin{equation} 2^{-H(X)} \geq \frac{V_s}{V_d} \tag{4} \end{equation}\]

which may be understood as a normalised volume constraint:

\[\begin{equation} -\log_2 \big(\frac{V_s}{V_d} \big) \geq \log_2 N \tag{5} \end{equation}\]

Moreover, the uncertainty concerning \(X\) along a single dimension is given by \(-\log_2 \big(\frac{r}{V_d}\big)\). Hence, due to the fact that these bits are drawn from \(d\) independent dimensions within the finite volume \(V_d\) we may derive the constraint:

\[\begin{equation} -\log_2 \big(\frac{r}{V_d}\big)^d \leq \mathcal{L}\tag{6} \end{equation}\]

which allows us to reason about the Sphere-Packing bound.

Naturally, the last inequality implies:

\[\begin{equation} \frac{V_d}{r} \leq 2^{\frac{\mathcal{L}}{d}} \tag{7} \end{equation}\]

and for fixed radius \(r\) the volume of the d-dimensional sphere is monotonically increasing as a function of \(d \in \mathbb{N}\) so we may derive the lower-bound on \(V_d\):

\[\begin{equation} V_d \geq N \cdot V_s \geq N \cdot \frac{4}{3} \cdot \pi \cdot r^3 \sim 4 \cdot N \cdot r^3 \tag{8} \end{equation}\]

where we assume that \(d \geq 3\).

By combining fomulas (7) and (8), we may deduce the Sphere Packing Bound:

\[\begin{equation} r \lesssim 3 \cdot \sqrt{2^{\frac{\mathcal{L}}{d}-H(X)}} \tag{9} \end{equation}\]

and we find that as \(d \rightarrow \infty\):

\[\begin{equation} r \lesssim \sqrt{2^{-H(X)}} \leq 1 \tag{10} \end{equation}\]

Hence, solving k-NN in high-dimensional spaces converges to a needle in a haystack problem.

Discussion:

We may refine this argument by noting that the average number of queries required to identify the nearest neighbor of a particular sphere \(X\) is enclosed within the entropy of a special ball of probabilities:

\[\begin{equation} -\log_2 r \gtrsim \frac{H(X)}{2} \tag{11} \end{equation}\]

Upon closer inspection of formulas (10) and (11), a Quantum Probability theorist will recognise that the radius of this ball equals the modulus of a Quantum Amplitude and that the squared modulus of this amplitude naturally encloses a Bloch Sphere.

This local analysis suggests that the Information Geometry of high-dimensional Sphere Packings may be elucidated using tools from Quantum Probability theory.

References:

1. David De Laat & Frank Valentin. A breakthrough in sphere packing: the search for magic functions. 2016.

2. J.H. Conway, N.J.A. Sloane, Sphere packings, lattices and groups, Springer-Verlag, 3rd edition, 1998.

3. G. Szpiro, Kepler’s conjecture: How some of the greatest minds in history helped solve one of the oldest math problems in the world, John Wiley & Sons, 2003

4. Kepler, Johannes. The six-cornered snowflake. 1611.

5. Aaron Slipper. MODULAR MAGIC: The Theory of Modular Forms and the Sphere Packing Problem in Dimensions 8 and 24. 2018.