MultiIndices#

Background#

A multiindex is simply a length $D$ vector of nonnegative integers $p = [p_{1}, p_{2}, \dots, p_{D}]$ . Multiindices are commonly employed for defining multivariate polynomial expansions and other function parameterizations. In these cases, sets of multiindices define the form of the expansion.

Example: Multivariate Polynomial

A multivariate polynomial $Φ_{p} (x) : R^{D} \to R$ can be defined as the product of $D$ univariate polynomials. Using monomials for example,

Φ_{p} (x) = \prod_{i = 1}^{D} x_{i}^{p_{i}}

A multivariate polynomial expansion can then be written succinctly as

f (x) = \sum_{p \in S} c_{p} Φ_{p} (x)

where $S$ is a set of multiindices and $c_{p}$ are scalar coefficients.

Example: Wavelets

Multivariate polynomials are constructed from a tensor product of one-dimensional functions and each one-dimensional function depends on a single integer: the degree of the one-dimensional polynomial. This is a common way to define multivariate functions from indexed families of one-dimensional basis functions. In a general setting, however, the one-dimensional family does not need to be index by a single integer. Families of one-dimensional functions indexed with multiple integers can also be “tensorized” into multivariate functions. Wavelets are a prime example of this.

A one dimensional wavelet basis contains functions of the form

ψ_{j, k} (x) = 2^{j / 2} ψ (2^{j} x - k)

where $j$ and $k$ are integers and $ψ : R \to R$ is an orthogonal wavelet. Unlike polynomials, two integers are required to index the one-dimensional family. Nevertheless, a multivariate wavelet basis can be defined through the tensor product of components in this family:

Ψ_{p} (x) = \prod_{i = 1}^{D / 2} ψ_{p_{2 i}, p_{2 i + 1}} (x_{i})

where $Ψ_{p} : R^{D / 2} \to R$ is a multivariate wavelet basis function in $D / 2$ dimensions and $p$ is a multiindex with $D$ components.

C++ Objects#

Definitions#

Neighbors

In most parameterization applications, there is additional structure in the multiindex set that can be represented through edges on a graph. Each multiindex can be treated as a node in directed graph. Outgoing edges connect to other multiindices, which we call “forward neighbors”, that represent higher order basis functions. Incoming edges come from multiindices, which we call “backward neighbors”, that represent lower order basis functions.

In the multivariate polynomial example above, the backward neighbors of a multiindex $j$ are the multiindices that only differ from $j$ in one component, and in that component, the difference is -1. More precisely, the set of backward neighbors is

B_{j} = {i : ‖ i - j ‖_{1} = 1 and i_{k} \leq j_{k} for all k} .

The set of forward neighbors is similarly defined as

F_{j} = {i : ‖ i - j ‖_{1} = 1 and i_{k} \geq j_{k} for all k}

The neighborhood structure of a multindex set is defined through a child of the abstract MultiIndexNeighborhood class.