Optimality of codes with respect to error probability in Gaussian noise
Alexey Balitskiy Roman Karasev Alexander Tsigler






alexey_m39@mail.ru



r_n_karasev@mail.ru
http://www.rkarasev.ru/en/



sasha-cigler@mail.ru

^^^Supported by the Russian Foundation for Basic Research grant 15-31-20403 (mol_a_ved)

^^^Supported by the Russian Foundation for Basic Research grant 15-01-99563 A

^^^Moscow Institute of Physics and Technology, Institutskiy per. 9, Dolgoprudny, Russia 141700

^^^Institute for Information Transmission Problems RAS, Bolshoy Karetny per. 19, Moscow, Russia 127994


We consider geometrical optimization problems related to optimizing the error probability in the presence of a Gaussian noise. One famous questions in the field is the “weak simplex conjecture”. We discuss possible approaches to it, and state related conjectures about the Gaussian measure, in particular, the conjecture about minimizing of the Gaussian measure of a simplex. We also consider antipodal codes, apply the Šidák inequality and establish some theoretical and some numerical results about their optimality.


Optimality of codes with respect to error probability in Gaussian noise
    Alexander Tsigler^
    Jan 15 2017
=======================================================================





§ INTRODUCTION


Assume a code is represented by a finite set of vectors {v_i} in ℝ^n and the decoding procedure is by taking the (Euclidean distance) closest point of {v_i} (which is optimal subject to likelihood maximization).

If we want to calculate the probability that a vector is transmitted correctly in the presence of a normalized Gaussian noise then we obtain a value proportional to

    P(v_1,…, v_N) = ∫_ℝ^nmax_i e^-|x - v_i|^2  dx.



If the probability to choose any of v_i in the code is the same then the actual probability of transmitting the signal correctly is the above value P multiplied by a constant and divided by N. In most if this text the constant in front of the integral is not relevant, but if someone want to interpret the practical meaning of the data given in Section <ref> (where we allow N to vary) then this factor has to be taken into account.


 Here we normalize the exponent as e^-x^2 and do not use the leading factor (π)^-n/2 to shorten the formulas. Again, in the numerical results of Section <ref> we will use the more common normalization with density (2π)^-n/2 e^-|x|^2/2.


It was conjectured that in the case N=n+1 with fixed total energy |v_1|^2+… + |v_N|^2 the maximum of this functional is attained at regular simplices centered at the origin, see <cit.>. In <cit.> it was shown that the regular simplex is optimal for energy tending to infinity and locally optimal for every energy. Eventually, this conjecture turned out to be false; in <cit.> it was shown that for m≥ 7 the configuration with m-2 zero vectors and 2 antipodal vectors is better than the regular simplex with m vertices and the same energy. Now it is conjectured that



For N=n+1 and fixed |v_1|=… = |v_N|=r the maximum of P(v_1,…, v_N) is attained at any configuration forming a regular simplex inscribed into the ball of radius r.


The case of energy tending to zero or to infinity in this conjecture was considered in <cit.>; its validity for n=3 was established in <cit.>.

Our plan is as follows: In Sections <ref> and <ref> we explain how the problems of maximizing P may be reduced to problems of optimal covering of a sphere by caps and to minimizing Gaussian measure of an outscribed simplex. In Theorem <ref> of Section <ref> and in Section <ref> we prove some optimality results for antipodal configurations, inspired by such a configuration in the example of Steiner <cit.>. In Section <ref> we give some numerical results for antipodal configurations.

The paper is organized as follows: In Section <ref> we overview the techniques that prove Conjecture <ref> in dimensions ≤ 3. In Section <ref> we provide another approach that would reduce the problem to another conjecture about the Gaussian measure of a (generalized) simplex (Conjecture <ref>) and we show that this approach does give some information for “antipodal” configurations of points, where, for every point x present in the configuration, the point -x is also present, here we recall and use Šidák's lemma about the Gaussian measure. In Section <ref> we study the optimality of antipodal configurations with varying lengths of vectors keeping the total energy, establish the optimality of the equal length configuration for 4-point antipodal configurations, and make numeric tests showing that for larger number of vectors the optimal lengths have more complex behavior.



 §.§ Acknowledgments.

The authors thank Grigori Kabatianski for explaining this problem to us.



§ SLICING WITH THE UNIFORM MEASURE



The first thing that comes to mind is to represent the integral as “the volume under the graph”, that is

    P(v_1,…, v_N) = {(x, y)∈ℝ^n+1 : ∃ i 0≤ y ≤ e^-|x-v_i|^2}.


Then we can fix a value y∈ [0,1] and try to maximize the n-dimensional volume of the corresponding slice of the set in the right hand side of (<ref>). If the maximum of the volume of the section will be obtained at the same configuration for every value of y then the maximum of the total volume P(v_1,…, v_N) will also be there.

The corresponding slice is the set ⋃_i { |x - v_i|^2 ≤ -ln y }, that is a union of balls of the same radius. So Conjecture <ref> would follow from the following stronger



For N=n+1 and fixed |v_1|=… = |v_N|=r and R>0 the maximal volume of the union of balls ⋃_i B_v_i (R) is attained at any configuration forming a regular simplex inscribed into the ball of radius r.


By further slicing with the distance to the origin this conjecture would follow from an even stronger



For N=n+1 and R>0 the maximal area of the union of N spherical caps of radius R in the unit sphere 𝕊^n-1 is attained when the centers of the caps form a regular simplex inscribed into the unit sphere.


In fact, the case n=3 of the latter conjecture (when the sphere is 2-dimensional) was resolved positively in <cit.>, this was noted in <cit.> and resulted in



Conjecture <ref> holds true for n=3 and N=4.


Moreover, in <cit.> other regular configurations (corresponding to the vertices of a regular solid body) were proved to maximize the area of the union of equal caps, resulting in optimality of the corresponding spherical codes. This was also noted in <cit.>.

After that, in <cit.> two analytical-geometrical lemmas about the caps on a two-dimensional sphere were shown to hold in larger dimensions and it was concluded that Conjecture <ref> was therefore established for arbitrary n. However, the proof of Conjecture <ref> for n=3 in <cit.> does not generalize to larger dimensions because the argument only work for the case when in the presumably optimal configuration the caps only intersect pairwise and no point is covered by three of them. This is not a problem in 𝕊^2, since when three caps intersect in the regular configuration then those caps cover the whole 𝕊^2 and the assertion holds trivially.

In the thesis <cit.> we see that this problem in the argument of <cit.> was evident to the experts.



§ SLICING WITH THE GAUSSIAN MEASURE



Here we propose a different approach reducing the problem to estimates for Gaussian measures instead of spherical measures. Let us rewrite the value to optimize differently:


    P(v_1,…, v_N) = ∫_ℝ^nmax_i e^2 x· v_i  - |v_i|^2  e^-|x|^2dx.
    = μ̅{(x, y)∈ℝ^n+1 : ∃ i 0≤ y ≤ e^2 x· v_i  - |v_i|^2},

here μ̅ is the measure with density e^-|x|^2 dx dy. Again, we can fix y now and maximize the measure μ of any section, where μ is the Gaussian measure with density e^-|x|^2dx. The set whose measure is maximized will be a union of halfspaces:

    C_y(v_1,…, v_N) = ⋃_i { 2 x· v_i - |v_i|^2 ≥ln y}.


Taking the complement, we obtain



The value P(v_1,…, v_N) is maximized at a given configuration if the Gaussian measure of

    S_y(v_1,…, v_N) = ⋂_i { 2 x· v_i - |v_i|^2 ≤ln y}

is minimized at the same point set (v_1,…, v_N) for any value of y.


An advantage of this approach is that the set S_y(v_1,…, v_N) is a (possibly unbounded) convex polyhedron. From the inequality in <cit.> we readily obtain:



If we consider sets of 2N points (N≤ n) in ℝ^n of the form {v_i}_i=1^N with prescribed |v_i| =r_i then P(v_1, - v_1, …, v_N, - v_N) is maximized when all the vectors v_i are orthogonal to each other.



In this case, the set S_y is an intersection of several symmetric planks

    P_i = {|(x, v_i)| ≤|v_i|^2 - ln y/2},

and the Gaussian measure of this intersection is minimized when all the stripes are perpendicular. This follows from the Šidák inequality <cit.>

    μ(P_1∩…∩ P_N) ≥μ(P_1)·…·μ(P_N),

which becomes an equality in case when all the planks are perpendicular to each other. This perpendicularity is only possible when N≤ n.


We continue the discussion of such antipodal configurations in Section <ref>. Similarly, Conjecture <ref> is therefore reduced to:



The Gaussian measure of a simplex S containing a given ball B_0(r) is minimized at the regular simplex with inscribed ball B_0(r).


Of course, by slicing and using the result <cit.> about spherical caps we conclude that this conjecture holds true for n=3.


In order to make such a reduction we have to establish that unbounded generalized simplices, that is sets determined by n+1 linear equations in ℝ^n, are ruled out.

Call a generalized simplex essentially unbounded if it contains an open cone. Equivalently, its outer normals of facets do not contain the origin in their convex hull. In Conjecture <ref> this corresponds to the case when the convex hull of {v_i} does not contain the origin. Let p be the closest to the origin point in this convex hull.

Assume that p points to the “north” and let E be the corresponding “equator” of 𝕊^n-1. The point p is a convex combination of some of v_i's, without loss of generality let them be v_1, …, v_k. Note that these v_1,…, v_k are at the same distance from E and if we move them uniformly to E (and keep other v_i's fixed) then the pairwise distances between them increase. Moreover, any distance |v_i - v_j| for i≤ k and j > k also increases, in order to see this it is sufficient to consider the three-dimensional space spanned by v_i, p, v_j and apply the elementary geometry.

Now we use the reduction of Conjecture <ref> to Conjecture <ref> and analyze the volume of the union ⋃_i=1^n+1 B_v_i (r) for every radius r>0. The continuous case of the Kneser–Poulsen conjecture established in <cit.> asserts that for every r>0 the volume of such a union does not decrease when we move v_1,…, v_k to the equator. Hence the total value P(v_1,…, v_n+1) does not decrease either. Now observe that at the end the origin will be in the convex hull of v_i's.

Call a generalized simplex degenerate if it is not essentially unbounded, but is still unbounded. Every degenerate simplex is a limit (in the topology given by the family of metrics _R(X, Y) = _Haus( X∩ B_0(R), Y∩ B_0(R) ), (R>0) of honest simplices; and it is easy to see that the Gaussian measure of a degenerate simplex will be the limit of the Gaussian measures of those honest simplices. So the inequality would follow, since we do not want it to be strict.


After this, one may try to establish Conjecture <ref> by taking the minimal example and studying its structure. There may be some difficulty: this minimal example may turn out to be degenerate. This could be avoided if we manage to prove the stronger version of Conjecture <ref>:



Let μ be a radially symmetric measure with monotone decreasing positive density ρ(r).
The value μ(S) over all simplices S containing a given ball B_0(r) is minimized at the regular simplex with inscribed ball B_0(r).


This conjecture can be attacked by the analysis of the minimizer because of



If the integral ∫_0^+∞ρ(r)  dr diverges then the minimum in Conjecture <ref> is attained at an honest simplex.



Obviously, degenerate simplices have infinite measure in this case.




Let S_0 be the regular simplex outscribed about B_0(r). If for any measure μ, satisfying the assumptions of Conjecture <ref>, and any non-degenerate local minimizer (among honest simplices) S of μ(S) under the constraint S⊃ B_0(r) we have μ(S) ≥μ(S_0) then Conjecture <ref> holds.



First, the assertion follows from Lemma <ref> if the integral ∫_0^+∞ρ(r)  dr diverges.

Let us consider the general case. Assume the contrary: suppose that μ(S) is minimized (over S⊃ B_0(r), of course) at a degenerate simplex S. If we have μ(S) < μ(S_0), then we can approximate S by an honest simplex S' and still have μ(S') < μ(S_0). Now we can change the density of μ so that it remains the same around S_0 and S', and the integral ∫_0^+∞ρ(r)  dr diverges. But for the modified measure we have already shown that μ(S') ≥μ(S_0).




§ ANTIPODAL CONFIGURATIONS IN THE PLANE



Let us focus on the case when the configuration is antipodal, that is containing the vector -v for every its vector v. Theorem <ref> thus asserts that such a configuration becomes better if we make all the pairs ± v_i in it orthogonal to each other keeping their lengths.

But what about the lenghts? Let us analyze how the value P(± v_1, …, ± v_N) behaves when the vectors v_i are kept orthogonal to each other, but their lengths are allowed to vary. It would be nice if the maximization if P(± v_1, …, ± v_N) for fixed |v_1|^2+… + |v_N|^2 happened at equal lengths |v_1|= … = |v_N|; but the example in <cit.> is actually a counterexample to this naive conjecture. There only one pair of ± v_i was given the maximal possible length while all other pairs ± v_i were put to zero.

Fortunately, the naive conjecture holds in dimension 2:



Under fixed |v_1|^2 + |v_2|^2 the maximum of P(± v_1, ± v_2) is given at equal and orthogonal to each other v_1 and v_2.



It will be clear from the proof that the conclusion remains true if consider, instead of the Gaussian measure, any measure with radially symmetric density.



Of course, the picture is essentially planar. Let a and b be the lengths of v_1 and v_2 respectively, and let a≤ b without loss of generality. Consider the Voronoi regions of the the four points in the plane. Let us move every Voronoi regions so that the center of it gets to the origin, see Figure <ref>.



The numbers in the picture show how many times every area gets covered after the overlap of the moved Voronoi regions. Now all the measures in each of the Voronoi regions become the same Gaussian measure centered at the origin and we count it taking the overlap into account. This turns out to be the measure of the whole plane, plus two centrally symmetric strips of width c = √(a^2 + b^2) each, plus the measure of the hexagon in the picture. Since the width of the strips c does not depend on the choice of a and b, their measure is also constant in fact.

Hence, for fixed a^2 + b^2, we maximize P(± v_1, ± v_2) if and only if we maximize the Gaussian measure of the hexagon. Let us look at the hexagon closer: It is obtained from the rhombus, which is the intersection of two strips of width c, by cutting off two corners. Let us give a geometric description of the cutting: Let  O be the center of the hexagon and let A, B, C (see Figure <ref>) be its vertices. Since every two points of the configuration are symmetric with respect to the wall between their respective Voronoi regions, the point N, defined as symmetric to O about BC is on the straight line AB. Let M be the base of the perpendicular from O to BC.



Since AB and OC are parallel, we obtain ∠ BNM = ∠ MOC. As was mentioned, OM = MN, ∠ BMN = ∠ CMO. Hence the triangles BMN and CMO are equal. Therefore OM is the perpendicular bisector of BC and OB = CO.

We conclude that the hexagon is characterized by the following properties: All its vertices are at equal distances from the origin; two antipodal pairs of its sides are at distance c/2 from the origin. In other words, the four sides touch the circle of radius  c/2 centered at O at their respective midpoints.

Let us fix a direction in the plane and parameterize the hexagon by six parameters: Four angles for the sides that are c/2 from the origin and two shifts along the given direction for the remaining two sides, see Figure <ref>.



Let F(φ_1, φ_2, …, x_2) be the Gaussian measure of such a hexagon; the center of the measure is also O.

When we change a and b keeping c = √(a^2 + b^2) the hexagon vary. We may assume that the six parameters of the hexagon are all functions of a:

    F(a) = F(φ_1(a), φ_2(a), …, x_2(a)).

Let us find the derivative:

    F'_a(a) = ∑∂/∂φ_iF(φ_1, φ_2, …, x_2)φ_i'(a) + ∑∂/∂ x_jF(φ_1, φ_2, …, x_2)x_j'(a).



If the parameters correspond the hexagon in question (are expressed in a) then

    ∀ i ∈{1,2,3,4}∀ a   ∂/φ_i F(φ_1, φ_2, …, x_2) = 0.



 When we change the angle φ_i the corresponding side is rotated about the origin keeping in touch with the circle of radius c. Since the vertices of the hexagon are at the same distance from the origin and the Gaussian density is radially symmetric, then the mass center of the side (in this Gaussian density) is in its midpoint, which is the same as the touching with the circle.

If the touching point is rotated, say, with angular velocity ω then at start the velocity at a point x of the side segment equals to ω|x| and is directed along Ox rotated by π/2. If we consider two such points symmetric to each other with respect to the midpoint of the side then we see that the densities are the same at those two points and the projections of their velocities onto the normal of the side sum to zero. Since in the linear term the measure changes by the integral over the side segment of the density multiplied by the normal component of the velocity, the total derivative of the measure with respect to the rotation turns out to be zero.


Now we see that the partial derivatives of F(φ_1, φ_2, …, x_2) in the angles are zero, and its partial derivatives in x_1 and x_2 are definitely non-negative and positive for a < b. Hence the measure increases when x_1 and x_2 increase. Since x_1(a) = x_2(a) = a we have to increase a until it becomes equal to b (at this moment the picture changes). So a = b is the optimal configuration.





§ NUMERICAL RESULTS FOR ANTIPODAL CONFIGURATIONS





 §.§ Formulas for the modified example of Steiner


In Steiner's example <cit.> one pair of antipodal vectors had nonzero length while the other pairs had length zero, that is all those vectors were the same at the origin. Let us generalize this as follows: k pairs of vectors have the same length, while all other vectors are in the origin and their set is not empty. Let us write down an explicit formula for the probability in this case.

In order to calculate the function P for the configuration we have to take every point in the configuration and its Voronoi region, integrate the Gaussian measure centered at this point over its Voronoi region, and then sum up the results over all the points.

The linear hull of our point is k-dimensional and their Voronoi regions in the ambient space are orthogonal products of k-dimensional Voronoi regions by the complementary linear subspace. The Gaussian measures also equal to the products of k-dimensional Gaussian measures by the Gaussian measure of the complement, which is 1. Therefore it is sufficient to work in the k-dimensional linear hull of the points.

Now choose the coordinate frame so that our nonzero vectors are ± the basis vectors multiplied by a. Of course, it does not matter how many points of the configuration are put to the origin; so we assume there is one point at the origin. The Voronoi region of the origin is therefore the cube [-a/2, a/2]^k. Other Voronoi regions are the cones on the facets of the cube minus the cube itself.

Here we start to use the standard version of the Gaussian measure with density 1/√(2π) e^-x^2/2 per dimension. This is needed to invoke the standard notation

    Φ(x) = 1/√(2π)∫_0^x e^-t^2/2  dt.

So the cube [-a/2, a/2]^k has the Gaussian measure

    (Φ(a/2) - Φ(-a/2))^n = (2Φ(a/2) - 1)^k.


Now consider the Voronoi region which is adjacent to the cube by its facet x_1 = a/2. When we intersect this region by the hyperplane x_1 = b,  b ≥a/2, we obtain the cube [-b, b]^k-1in this hyperplane. Now we have to integrate the induced Gaussian measure of this cube from x_1=a to +∞. The induced Gaussian measure has center at the center of the cube and the additional factor

    1/√(2π)e^-ρ^2/2,

where ρ is the distance from the center of the original Gaussian measure to the hyperplane. Since the center is at the axis point with x_1 = a, the induced measure of the section is

    1/√(2π)e^-(b - a)^2/2(2Φ(b) - 1)^k-1.


Eventually, the Gaussian measure of the Voronoi region is

    ∫_a/2^+∞1/√(2π)e^-(b - a)^2/2(2Φ(b) - 1)^k-1  db.


And the total value is

    P(± ae_1,…,± ae_k, 0) =
    2k∫_a/2^+∞1/√(2π)e^-(b - a)^2/2(2Φ(b) - 1)^k-1  db + (2Φ(a/2) - 1)^k.


This formula is not very nice, but it allows us to make some numerical experiments.



 §.§ Numerical experiments with the modified example of Steiner


We give the table where the function P of the modified example of Steiner is calculated for different values of k (the number of nonzero pairs) and the total energy E in Table <ref>.



The graph of P as a function of k and E is given in Figure <ref>. We note again that in practice one may want to vary the number N of the code vectors. First, it makes sense to take N=2k+1 putting precisely one vector to the origin. Then one has to note that the actual amount of the transmitted information multiplied by the probability of correct transmission will be our number P with the factor of log_2 N/N.






 §.§ Formulas for arbitrary orthogonal antipodal configuration


In the more general case we have k pairs of vectors ± v_i, so that the lengths in ith pair are a_i. Again, we work in the linear hull of the configuration and consider the vectors of the configuration as proportional to the basis vectors.

Consider the hyperplane of x_k=0 and move it along the kth basis vector. Let the shifted hyperplane by {x_k=t}. In the intersection with this hyperplane, the Voronoi regions of the original points are the weighted Voronoi regions of their projections. The weights are t^2 for the first k-1 pairs, and the last pair is actually represented by one of the points projected to the origin in the hyperplane with weight (a_k - t)^2. When we subtract t^2 from all the weights then 2k-2 points remain without weights, while the last one gets weight a_k^2 - 2a_kt. The latter Voronoi region is a parallelotope:

    ∏_1^k-1[-a_i^2 + 2a_kt-a_k^2/2a_i, a_i^2 + 2a_kt-a_k^2/2a_i],

if a_i^2 + 2a_kt-a_k^2 > 0 for all i≠ k.

In particular, in order to this latter Voronoi region to be nonempty, we need

    t > a_k^2 - min_i≠ ka_i^2/2a_k,  t > 0,

that is t > a_k^2 - mina_i^2/2a_k.

Write down the induced measure of this parallelotope:

    ∏_1^k-1(2Φ(a_i^2 + 2a_kt-a_k^2/2a_i) - 1),

and integrate in t to obtain the Gaussian measure of one of the points in kth pair:

    ∫_a_k^2 - mina_i^2/2a_k^+∞1/√(2π)e^-(t - a_k)^2/2∏_1^k-1(2Φ(a_i^2 + 2a_kt-a_k^2/2a_i) - 1)  dt.


The sum of all such Gaussian measures equals:

    P(± a_1e_1, …, ± a_ke_k) = 2∑_j = 1^k∫_a_j^2 - mina_i^2/2a_j^+∞1/√(2π)e^-(t - a_j)^2/2∏_i ≠ j(2Φ(a_i^2 + 2a_jt-a_j^2/2a_i) - 1)  dt.

This is the function of (a_1,…,a_k) we want to maximize.




 §.§ Numerical experiments for arbitrary orthogonal antipodal configuration


Let us try to optimize the above function numerically. We are using the standard algorithm of Basin Hopping. The results are given in Tables <ref>, <ref>, <ref>, <ref>.









It seems that for arbitrary dimension k there exists a threshold of energy E_0(k) such that for energy E > E_0(k) the optimal configuration of k antipodal pairs is the configuration with all equal lengths of the vectors.


abbrv
