Compute the largest polynomial degree such that the number of coefficients is lower or equal to a proportion of the sample size

find_largest_degree.py

"""
Let d be the dimension of the input vector.
Let n be the sample size.
Let alpha in [0, 1] a proportion of the sample size.
Compute the largest polynomial degree p such that the 
number of coefficients of the polynomial chaos expansion is lower or 
equal to alpha * n.

For example, the next table presents the number of coefficients 
of the PCE of the Ishigami function, which has dimension 3.
With n = 100 and alpha = 0.5, we get the polynomial degree 4, which 
corresponds to 35 coefficients.
With n = 100 and alpha = 0.7, we get the polynomial degree 5,0 which 
corresponds to 56 coefficients.

| Degré | Nombre de coefficients |
| ----- | ---------------------- |
| 1     | 3                      |
| 2     | 10                     |
| 3     | 20                     |
| 4     | 35                     |
| 5     | 55                     |
| 6     | 83                     |
| 7     | 119                    |
| 8     | 165                    |
| 9     | 220                    |
| 10    | 285                    |
| 11    | 364                    |
| 12    | 455                    |
| 13    | 560                    |
| 14    | 680                    |
| 15    | 816                    |
| 16    | 969                    |
| 17    | 1139                   |
| 18    | 1330                   |
| 19    | 1539                   |
| 21    | 2024                   |
| 23    | 2600                   |
| 25    | 3275                   |
| 27    | 4060                   |
| 29    | 4960                   |
| 31    | 5984                   |
| 33    | 7140                   |
| 35    | 8435                   |
| 37    | 9879                   |
| 39    | 11479                  |

**Table 1.** Nombre de coefficients d'un polynôme du chaos plein en dimension 3.

"""
# %%
import math

# %%

def computeNumberOfCoefficientsPCE(dimension, degree):
    """
    Return the number of coefficients of a PCE
    
    This is the binomial coefficient of (dimension + degree, degree).

    Parameters
    ----------
    dimension : int
        The input dimension.
    degree : int
        The polynomial degree.

    Returns
    -------
    n : int
        The number of coefficients.

    """
    n = math.comb(dimension + degree, degree)
    return n

# %%
sample_size = 100
dimension = 3
proportion = 0.7
maximum_degree = 15

# %%
threshold = sample_size * proportion
degree = 0
while computeNumberOfCoefficientsPCE(dimension, degree) <= threshold:
    if degree == maximum_degree:
        break
    degree += 1

degree -= 1

# %%
print(f"Degree = {degree}")
nc = computeNumberOfCoefficientsPCE(dimension, degree)
print(f"Nb. Of Coeff. = {nc}")


# %%