Universal Approximation on the Hypersphere

Finite mixtures of distributions (McLachlan and Peel, 2000) are being widely used in various fields for modelling random phenomena. In a finite mixture model, the distribution of random observations is modelled as mixture of a finite number of component distributions with varying proportions. The finite mixture of normal distributions (Fraley and Raftery, 2002) is one of the most frequently used finite mixture models for continuous data taking values in the Euclidean space, because of their flexibility of representation of arbitrary distributions. Indeed, it has been shown that given sufficient number of mixture components, a finite mixture of normals can approximate any continuous probability density functions up to any desired level of accuracy (Bacharoglou, 2010; Nguyen and McLachlan, 2019).

Despite the success and popularity of finite mixture of normal distributions in a wide range of applications, frequently, data possess more structure and representing them using Euclidean vectors may be inappropriate. An important case is when data are normalized to have unit norm, which can be naturally represented as points on the unit hypersphere $S^{m}:=\{x\in\mathbb{R}^{m+1}:||x||_{2}=1\}$. For example, the direction of flight of a bird or the orientation of an animal can be represented as points on the circle $S^{1}$ or sphere $S^{2}$. Consequently, standard methods for analyzing univariate or multivariate data cannot be used, and distributions that take into account the directional nature of the data are required.

The von-Mises-Fisher distribution (Fisher et al., 1993) is one of the most commonly used distribution to describe directional data on $S^{m}$ which has properties analogous to those of the multivariate normal on $\mathbb{R}^{m+1}$. A unit norm vector $x\in S^{m}$ has a von-Mises-Fisher distribution if it has density

$$f_{m+1}(x;\mu,\kappa)=c_{m+1}(\kappa)\exp(\kappa\langle x,\mathbf{\mu}\rangle),\quad x\in S^{m},$$

where $\kappa>0$ is the concentration parameter and the mean direction $\mu\in S^{m}$ satisfies $||\mu||=1$. In particular, as $\kappa$ increases, the distribution becomes increasingly concentrated at $\mu$. The normalizing constant $c_{m+1}(\kappa)$ is given by

$$c_{m+1}(\kappa)=\frac{\kappa^{\frac{m+1}{2}-1}}{(2\pi)^{\frac{m+1}{2}}I_{\frac{m+1}{2}-1}(\kappa)},$$

where $I_{v}$ is the modified Bessel function at order $v$.

A finite mixture of von-Mises-Fisher distributions on $S^{m}$ with $H$ components has density

$\displaystyle f_{m+1}(x;\{\pi_{h},\mu_{h},\kappa_{h}\}_{h=1}^{H})=\sum_{h=1}^{H}\pi_{h}f_{m+1}(x;\mu_{h},\kappa_{h}).$

(1)

The mixing proportions $\{\pi_{h}\}_{h=1}^{H}$ are non-negative and sum to 1 (i.e. $0\leq\pi_{h}\leq 1,\sum_{h}\pi_{h}=1$), and $\{\mu_{h},\kappa_{h}\}_{h=1}^{H}$ are the parameters for the $H$ mixture components.

Finite mixtures of von-Mises-Fisher distributions have found numerous applications, including clustering of high dimensional text data and gene expression (Banerjee et al., 2005) and clustering of online user behavior (Qin et al., 2016). A natural question that arises is whether finite mixtures of von-Mises-Fisher distributions can approximate any continuous probability distribution on the hypersphere up to any desired level of accuracy.

In this paper, we provide an affirmative answer to this question. We prove that any continuous probability distribution on $S^{m}$ can be approximated by finite mixture of von-Mises-Fisher distributions in $\sup$ norm given enough mixture components, and each component is sufficiently concentrated at respective mean directions. Our proof utilizes the theory of approximation by spherical convolution (Menegatto, 1997).

The paper is structured as follows. Section 2 provides relevant background that are needed for the proof of the main result. The main result is stated in Section 3 and is proved in Section 4.

This section provides the definitions of kernel function, spherical convolution and eigenfunction expansion which are needed for the proof of the main result. We refer the interested reader to Menegatto (1997) for detailed expositions of the theory.

We denote the space of all continuous functions defined on the hypersphere $S^{m}$ by $C(S^{m})$. Let $d\omega_{m}$ be the surface measure on $S^{m}$, and define $\omega_{m}:=\int_{S^{m}}d\omega_{m}$. The uniform and the ${\cal L}^{p}$ norm on $S^{m}$ are defined as

$$||f||_{m,\infty}:=\sup_{x\in S^{m}}|f(x)|$$

and

$$||f||_{m,p}:=\bigg{(}\frac{1}{\omega_{m}}\int_{S^{m}}|f(x)|^{p}d\omega_{m}(x)\bigg{)}^{1/p},$$

respectively. In particular, the ${\cal L}^{p}$ space contains all functions defined on $S^{m}$ that are integrable with respect to $d\omega_{m}$. When no confusion arises, we let $V_{m}$ be any of the space above with corresponding norm $||\cdot||_{m}$ (i.e. $||\cdot||_{m}=||\cdot||_{m,p}$ for $1\leq p<\infty$ or $||\cdot||_{m}=\sup_{x\in S^{m}}|f(x)|$).

We define the space ${\cal L}^{1,m}$ which consists of all measurable functions $K$ on $[-1,1]$ with norm

$$||K||_{1,m}:=\frac{\omega_{m-1}}{\omega_{m}}\int_{-1}^{1}|K(t)|(1-t^{2})^{(m-2)/2}dt<\infty.$$

Functions in the space ${\cal L}^{1,m}$ are called kernels. Let $\langle\cdot,\cdot\rangle$ be the inner product in $\mathbb{R}^{m+1}$, it is straight forward to show that for all $x\in S^{m}$, the following equality holds:

$$||K||_{1,m}:=\frac{1}{\omega_{m}}\int_{S^{m}}|K(\langle x,y\rangle)|d\omega_{m}(y).$$

The spherical convolution $K*f$ of a kernel $K$ in ${\cal L}^{1,m}$ with a function $f$ in $V_{m}$ is defined by

$$(K*f)(x):=\frac{1}{\omega_{m}}\int_{S^{m}}K(\langle x,y\rangle)f(y)d\omega_{m}(y),\quad x\in S^{m}.$$

For a fixed kernel $K$, the mapping defined by the spherical convolution $f\rightarrow K*f$ for $f\in V_{m}$ has range in $V_{m}$.

A useful property of spherical convolution is the Funk and Hecke’s formula (Xu, 2000) for eigenfunction expansion of any kernel $K\in{\cal L}^{1,m}$. Let ${\cal H}_{k}^{m}$ be the space of all degree $k$ spherical harmonics in $m+1$ variables and let $N^{m}_{k}$ be its dimension (Reimer, 2012, Chapter 3). Let $Q_{k}^{(m-1)/2}$ be the Gegenbauer polynomial of degree $k$ normalized by $Q_{k}^{(m-1)/2}(1)=N_{k}^{m}$. The Gegenbauer polynomials are certain types of the Jacobi polynomials and are conveniently defined using generating functions (Reimer, 2012, Chapter 2).

The Funk and Hecke’s formula states that for a kernel $K\in{\cal L}^{1,m}$ the following expansion holds:

$$K*Y_{k}^{m}=a_{k}^{m}(K)Y_{k}^{m},\quad K\in{\cal L}^{1,m},Y_{k}^{m}\in{\cal H}_{k}^{m},k=0,1,\ldots$$

In particular, the spherical harmonics $Y_{k}^{m}$ for $k=0,1,\ldots$ are the eigenfunctions associated with the kernel $K$, and the eigenvalues in the series expansion can be expressed in terms of Gegenbauer polynomials:

$$a_{k}^{m}(K)=\frac{\omega_{m-1}}{\omega_{m}}\int_{-1}^{1}K(t)\frac{Q_{k}^{(m-1)/2}(t)}{Q_{k}^{(m-1)/2}(1)}(1-t^{2})^{((m-2)/2}dt,\quad k=0,1,\ldots$$

In particular, we have

$$a_{0}^{m}(K)=\frac{\omega_{m-1}}{\omega_{m}}\int_{-1}^{1}K(t)(1-t^{2})^{((m-2)/2}dt.$$

Menegatto (1997) has investigated necessary and sufficient conditions under which a sequence of kernels $\{K_{n}\}_{n}$ in ${\cal L}^{1,m}$ has the property

$$||K_{n}*f-f||_{m}\rightarrow 0,\quad\forall f\in V_{m}$$

as $n\rightarrow\infty$. For non-negative kernels $\{K_{n}\}_{n}$, Theorem 3.4 of Menegatto (1997) provides sufficient conditions for the convergence of spherical convolutions $K_{n}*f\rightarrow f$, and is stated below.

We state the main result concerning the approximating properties of the finite mixtures of von Mises-Fisher distributions in the form (1). Recall that the probability density function of the von Mises–Fisher distribution for the random $(m+1)$-dimensional unit vector $x$ is given by:

$$f_{m+1}(x;\mu,\kappa)=c_{m+1}(\kappa)\exp(\kappa\langle x,\mu\rangle),$$

where $\mu\in S^{m}$ is the mean direction and $\kappa>0$ is the concentration parameter. We define a sequence of kernels $\{K_{n}\}_{n}$ in ${\cal L}^{1,m}$ by

$\displaystyle K_{n}(t)=c_{m+1}(n)\exp(nt),\quad t\in[-1,1].$

(2)

In particular, for any fixed $y\in S^{m}$,

$$K_{n}(\langle x,y\rangle)=c_{m+1}(n)\exp(\kappa\langle x,y\rangle),\quad x\in S^{m}$$

is the density function of the von Mises-Fisher distribution with mean direction $y$ and concentration parameter $n$. For a fixed $y\in S^{m}$, $K_{n}(\langle\cdot,y\rangle)$ plays the role of a “bump function” and becomes increasingly concentrated on $y$ as $n$ increases.

We show that for any continuous probability density functions $f$ on $S^{m}$, we can construct a mixture of von Mises-Fisher distributions where each mixture component has the form $K_{n}(\langle\cdot,y_{k}\rangle)$ and $f$ can be approximated up to desired level of accuracy under the uniform norm.

In this section we first state and prove a few lemmas needed for the proof of Theorem 1. Recall that $V_{m}$ is the space of integrable functions on $S^{m}$ with respect to either the ${\cal L}^{p}$ norm or the uniform norm $||\cdot||_{m}$. We first show that for any function $f\in V_{m}$ the spherical convolution $K_{n}*f$ converges to $f$ in $||\cdot||_{m}$ norm.

The following lemma concerning uniform approximation on $S^{m}$ by Riemann sums is useful.

The following result shows that any continuous function on $S^{m}$ can be uniformly approximated by linear combinations of $\{K_{n}(\langle\cdot,y_{k}\rangle)\}_{k}$ for $y_{1},y_{2},\ldots$ in $S^{m}$.