geometric_kernels.utils.special_functions

Special mathematical functions used in the library.

Module Contents

geometric_kernels.utils.special_functions.generalized_kravchuk_normalized(d, j, m, q, kravchuk_normalized_j_minus_1=None, kravchuk_normalized_j_minus_2=None)

This function returns \(\widetilde{G}_{d, q, j}(m)\) where \(\widetilde{G}_{d, q, j}(m)\) is the normalized generalized Kravchuk polynomial defined below.

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

\[\begin{split}G_{d, q, j}(m) = \sum_{\substack{T \subseteq \{0, .., d-1\} \\ |T| = j}} \sum_{\alpha \in \{1,..,q-1\}^T} \psi_{T,\alpha}(x) \overline{\psi_{T,\alpha}(y)}.\end{split}\]

Here \(\psi_{T,\alpha}\) are the Vilenkin functions on the q-ary Hamming graph \(H(d,q)\) and \(x, y \in \{0, 1, ..., q-1\}^d\) are arbitrary categorical vectors at Hamming distance \(m\) (the right-hand side does not depend on the choice of particular vectors of the kind).

The normalized polynomial is \(\widetilde{G}_{d, q, j}(m) = G_{d, q, j}(m) / G_{d, q, j}(0)\).

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 parameter \(\gamma\) from MacWilliams and Sloane [1977] is set to \(\gamma = q - 1\).

Note

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

Note

For \(q = 2\), this reduces to the classical Kravchuk polynomials.

Parameters:

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

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

• m (lab.Int) – The independent variable (Hamming distance), an integer or array with \(0 \leq m \leq d\). Maps to \(x\) in MacWilliams and Sloane [1977].

• q (int) – The alphabet size of the q-ary Hamming graph, an integer \(q \geq 2\).

• kravchuk_normalized_j_minus_1 (beartype.typing.Optional[lab.Float]) – The optional precomputed value of \(\widetilde{G}_{d, q, j-1}(m)\), 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 \(\widetilde{G}_{d, q, j-2}(m)\), helps to avoid exponential complexity growth due to the recursion.

Returns:

\(\widetilde{G}_{d, q, j}(m) = G_{d, q, j}(m) / G_{d, q, j}(0)\) where \(G_{d, q, j}(m)\) is the generalized Kravchuk polynomial.

Return type:

lab.Float

geometric_kernels.utils.special_functions.walsh_function(d, combination, x)

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