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.

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.

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.

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.

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

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

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

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

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

For attribution, please cite this work as

Rocke (2023, April 17). Kepler Lounge: Deducing the Sphere Packing Bound from the Shannon Coding theorem. Retrieved from keplerlounge.com

BibTeX citation

@misc{rocke2023deducing, author = {Rocke, Aidan}, title = {Kepler Lounge: Deducing the Sphere Packing Bound from the Shannon Coding theorem}, url = {keplerlounge.com}, year = {2023} }