geometric_kernels.utils.special_functions

Special mathematical functions used in the library.

Module Contents

geometric_kernels.utils.special_functions.kravchuk_normalized(d, j, m, kravchuk_normalized_j_minus_1=None, kravchuk_normalized_j_minus_2=None)[source]

This function returns \(G_{d, j, m}/G_{d, j, 0}\) where \(G_{d, j, m}\) is the Kravchuk polynomial defined below.

Define the Kravchuk polynomial of degree d > 0 and order 0 <= j <= d as the function \(G_{d, j, m}\) of the independent variable 0 <= m <= d given by

\[G_{d, j, m} = \sum_{T \subseteq \{0, .., d-1\}, |T| = j} w_T(x).\]

Here \(w_T\) are the Walsh functions on the hypercube graph \(C^d\) and \(x \in C^d\) is an arbitrary binary vector with \(m\) ones (the right-hand side does not depend on the choice of a particular vector of the kind).

Note

We are using the three term recurrence relation to compute the Kravchuk polynomials. Cf. Equation (60) of Chapter 5 in MacWilliams and Sloane “The Theory of Error-Correcting Codes”, 1977. The parameters q and \(\gamma\) from MacWilliams and Sloane [1977] are set to be q = 2; \(\gamma = q - 1 = 1\).

Note

We use the fact that \(G_{d, j, 0} = \binom{d}{j}\).

Parameters:

  • d (int) – The degree of Kravhuk polynomial, an integer d > 0. Maps to n in MacWilliams and Sloane [1977].

  • j (int) – d The order of Kravhuk polynomial, an integer 0 <= j <= d. Maps to k in MacWilliams and Sloane [1977].

  • m (lab.Int) – The independent variable, an integer 0 <= m <= d. Maps to x in MacWilliams and Sloane [1977].

  • kravchuk_normalized_j_minus_1 (beartype.typing.Optional[lab.Float]) – The optional precomputed value of \(G_{d, j-1, m}/G_{d, j-1, 0}\), helps to avoid exponential complexity growth due to the recursion.

  • kravchuk_normalized_j_minus_2 (beartype.typing.Optional[lab.Float]) – The optional precomputed value of \(G_{d, j-2, m}/G_{d, j-2, 0}\), helps to avoid exponential complexity growth due to the recursion.

Returns:

\(G_{d, j, m}/G_{d, j, 0}\) where \(G_{d, j, m}\) is the Kravchuk polynomial.

Return type:

lab.Float

geometric_kernels.utils.special_functions.walsh_function(d, combination, x)[source]

This function returns the value of the Walsh function

\[w_T(x_0, .., x_{d-1}) = (-1)^{\sum_{j \in T} x_j}\]

where \(d\) is d, \(T\) is combination, and \(x = (x_0, .., x_{d-1})\) is x.

Parameters:

  • d (int) – The degree of the Walsh function and the dimension of its inputs. An integer d > 0.

  • combination (beartype.typing.List[int]) – A subset of the set \(\{0, .., d-1\}\) determining the particular Walsh function. A list of integers.

  • x (lab.Bool) – A batch of binary vectors \(x = (x_0, .., x_{d-1})\) of shape [N, d].

Returns:

The value of the Walsh function \(w_T(x)\) evaluated for every \(x\) in the batch. An array of shape [N].

Return type:

lab.Float