Strictly Positive Definite Functions on Compact Two-Point Homogeneous Spaces

Strictly Positive Definite Functions
on Compact Two-Point Homogeneous Spaces:
the Product Alternative

Rafaela N. BONFIM †, Jean C. GUELLA ‡ and Valdir A. MENEGATTO ‡

R.N. Bonfim, J.C. Guella and V.A. Menegatto

† DEMAT-Universidade Federal de São João Del Rei, Praça Frei Orlando, 170,
Centro,
† 36307-352 São João del Rei - MG, Brazil<EMAIL_ADDRESS>
‡ Instituto de Ciências Matemáticas e de Computação, Universidade de São
Paulo,
‡ Caixa Postal 668, 13560-970, São Carlos - SP, Brazil<EMAIL_ADDRESS><EMAIL_ADDRESS>
Received March 08, 2018, in final form October 10, 2018; Published online
October 16, 2018

For two continuous and isotropic positive definite kernels on the same compact
two-point homogeneous space, we determine necessary and sufficient conditions
in order that their product be strictly positive definite. We also provide a
similar characterization for kernels on the space-time setting $G\times
S^{d}$, where $G$ is a locally compact group and $S^{d}$ is the unit sphere in
$\mathbb{R}^{d+1}$, keeping isotropy of the kernels with respect to the
$S^{d}$ component. Among other things, these results provide new procedures
for the construction of valid models for interpolation and approximation on
compact two-point homogeneous spaces.

strict positive definiteness; spheres; product kernels; linearization
formulas; isotropy

33C45; 42A82; 42C10; 43A35

##  1 Introduction

Positive definite functions and kernels on manifolds have special importance
for probability theory, approximation theory, spatial statistics and
stochastic processes. In applications, the case in which the manifold is a
2-dimensional sphere is the most common one, once the sphere plays the surface
of the Earth in many mathematical models. Originally, positive definite
functions were studied within the scope of harmonic analysis, distance
geometry and the theory of integral equations by Bochner, Schoenberg and
Young, among others. The most relevant contributions which are related to this
paper are Schoenberg’s characterization of positive definite functions on
spheres given in [25] and Gangolli’s extension to all the compact two-point
homogeneous spaces described in [11]. Some other references will be quoted at
the opportune time.

Let $\mathbb{M}^{d}$ denote a $d$-dimensional compact two-point homogeneous
space. As pointed by Wang [27], $\mathbb{M}^{d}$ belongs to one of the
following classes: the unit circle $S^{1}$, higher dimensional unit spheres
$S^{d}$, $d=2,3\ldots$, the real projective spaces
$\mathbb{P}^{d}(\mathbb{R})$, $d=2,3,\ldots$, the complex projective spaces
$\mathbb{P}^{d}(\mathbb{C})$, $d=4,6,\ldots$, the quaternionic projective
spaces $\mathbb{P}^{d}(\mathbb{H})$, $d=8,12,\ldots$, and the Cayley
projective plane $\mathbb{P}^{d}({\rm Cay})$, $d=16$. These manifolds are
metric spaces when endowed with their usual Riemannian (geodesic) distance.
Additional properties of compact two-point homogeneous spaces can be found in
the textbooks [18, 28]. If $x$ and $y$ are two elements of $\mathbb{M}^{d}$,
we will write $|xy|$ to indicate the distance between them. In order to make
the treatment uniform, the distance will be normalized so that $|xy|$ is at
most $2\pi$, no matter what $x$, $y$ and $\mathbb{M}^{d}$ are. That being
said, the positive definite kernels on $\mathbb{M}^{d}$ to be considered here
are of the form

$\displaystyle K(x,y)=f(\cos{(|xy|/2)}),\qquad x,y\in\mathbb{M}^{d},$ (1.1)

in which $f$ is a continuous function with domain $[-1,1]$. It is not uncommon
to call $f$ the isotropic part of the kernel $K$. Indeed, the manifolds
$\mathbb{M}^{d}$ possess a group of motions $G_{d}$ which takes
$(x,y)\in\mathbb{M}^{d}\times\mathbb{M}^{d}$ to
$(z,w)\in\mathbb{M}^{d}\times\mathbb{M}^{d}$ when $|xy|=|zw|$. In particular,
a kernel as above is isotropic in the sense that

$\displaystyle K(x,y)=K(Ax,Ay),\qquad x,y\in\mathbb{M}^{d},\qquad A\in G_{d}.$

The positive definiteness of $K$ demands that for any positive integer $n$ and
any distinct points $x_{1},x_{2},\ldots,x_{n}$ on $\mathbb{M}^{d}$, the
$n\times n$ matrix with entries $K(x_{i},x_{j})$ is nonnegative definite. That
corresponds to

$\displaystyle\sum_{i,j=1}^{n}c_{i}c_{j}K(x_{i},x_{j})\geq 0,$ (1.2)

for any real numbers $c_{1},c_{2},\ldots,c_{n}$.

According to [11, 25], a kernel $K$ as in (1.1) is positive definite if, and
only if, its isotropic part $f$ has a Fourier–Jacobi series representation in
the form

$\displaystyle
f(t)=\sum_{k=0}^{\infty}a_{k}(f)P_{k}^{(\alpha,\beta)}(t),\qquad t\in[-1,1],$
(1.3)

in which all the coefficients $a_{k}(f)$ are nonnegative,
$P_{k}^{(\alpha,\beta)}$ is the usual Jacobi polynomial of degree $k$
associated with the pair $(\alpha,\beta)$ [26], and the series is convergent
at $t=1$. The first upper exponent $\alpha$ depends only on the dimension $d$
of $\mathbb{M}^{d}$ in the sense that $\alpha:=(d-2)/2$, whereas $\beta$ can
take the values $(d-2)/2$, $-1/2$, $0$, $1$, $3$, depending on the respective
category $\mathbb{M}^{d}$ belongs to, among those stressed by Wang. The
coefficients $a_{k}(f)$ depend upon $\alpha$ and $\beta$ but that will not be
emphasized in our notation. Obviously, the series representation mentioned
above does not depend upon the particular normalization adopted for the Jacobi
polynomials.

The strict positive definiteness of a positive definite kernel as above
deserves attention when interpolation procedures need to be solved. It demands
strict inequalities in (1.2) when the scalars $c_{i}$ are nonzero. In
statistical language, the strict positive definiteness of a covariance
function (positive definite kernel) provides invertible kriging coefficient
matrices and, therefore, the existence of a unique solution for the associated
kriging system. The characterization of strictly positive definite kernels and
the construction of strictly positive definite kernels featuring special needs
is of practical relevance not only in statistics but also in approximation
theory.

The characterization for strict positive definiteness within Gangolli’s class
was achieved in recent years. It begins with the observation that strict
positive definiteness depends upon the set $\\{k\colon a_{k}(f)>0\\}$ attached
to the isotropic part of the positive definite kernel and not on the actual
values of $a_{k}(f)$ themselves. Precisely, the following result holds (see
[2, 6, 23]).

######  Theorem 1.1.

Let $f$ possess a Fourier–Jacobi series representation as in (1.3). It is the
isotropic part of a strictly positive definite kernel on $\mathbb{M}^{d}$ if,
and only if, the respective conditions given below hold:

  1. $(i)$

$\mathbb{M}^{d}=S^{1}$: the set $\\{k\colon a_{|k|}(f)>0\\}$ intersects every
full arithmetic progression in $\mathbb{Z}$, that is, all the sets
$n\mathbb{Z}+j=\\{nl+j\colon l\in\mathbb{Z}\\}$, where $n,j\in\mathbb{N}$ and
$n\geq 2$.

  2. $(ii)$

$\mathbb{M}^{d}=S^{d}$, $d\geq 2$: the set $\\{k\colon a_{k}(f)>0\\}$ contains
infinitely many even and infinitely many odd integers.

  3. $(iii)$

$\mathbb{M}^{d}\neq S^{d}$, $d\geq 1$: the set $\\{k\colon a_{k}(f)>0\\}$
contains infinitely many integers, that is, $f$ is not a polynomial.

The classes of positive definite kernels introduced so far are closed under
linear combinations with nonnegative coefficients and finite products. The
first assertion follows from the definition of positive definiteness while the
other one follows from the Schur product theorem [19, p. 455]. Regarding
strict positive definiteness with respect to linear combinations, if $f$ and
$g$ are functions possessing a Fourier–Jacobi series representation as in
(1.3), for the same $\mathbb{M}^{d}$ and $a$ and $b$ are nonnegative real
numbers, then the function $af+bg$ is the isotropic part of a strictly
positive definite kernel on $\mathbb{M}^{d}$ if, and only if, the sets
$\\{k\colon aa_{|k|}(f)+ba_{|k|}(g)>0\\}$ and $\\{k\colon
aa_{k}(f)+ba_{k}(g)>0\\}$ satisfy the corresponding conditions in Theorem 1.1,
that is, if, and only if, the sets $\\{k\colon aa_{|k|}(f)>0\\}\cup\\{l\colon
ba_{|l|}(g)>0\\}$ and $\\{k\colon aa_{k}(f)>0\\}\cup\\{l\colon ba_{l}(g)>0\\}$
satisfy the respective conditions in Theorem 1.1.

Having said that, the focus in the first half of this paper will be the
analysis of strict positive definiteness of product covariance models on these
same spaces. For a fixed space $\mathbb{M}^{d}$ and two continuous functions
$f,g\colon[-1,1]\to\mathbb{R}$ which are isotropic parts of two positive
definite kernels on $\mathbb{M}^{d}$, we will find necessary and sufficient
conditions on them in order that the product $fg$ be the isotropic part of a
strictly positive definite kernel on $\mathbb{M}^{d}$. The problem can be seen
as a particular formulation of what was called $DC$-strict positive
definiteness in a product space in [3, 14].

Oppenheim’s inequality [19, p. 480] is all that is needed in order to see that
if one of the functions is nonzero and the other is the isotropic part of a
strictly positive definite kernel on $\mathbb{M}^{d}$, then $fg$ is the
isotropic part of a strictly positive definite kernel on $\mathbb{M}^{d}$.
However, the product of two non strictly positive definite kernels on
$\mathbb{M}^{d}$ may be strictly positive definite, as the example
$\mathbb{M}^{d}=S^{d}$, $d\geq 2$, and the coefficients

$\displaystyle a_{0}(f)=a_{1}(f)=1,\qquad a_{k}(f)=0,\qquad k\neq 0,1,$

and

$\displaystyle a_{2k+1}(g)=3^{-2k-1},\qquad a_{2k}(g)=0,\qquad k=0,1,\ldots,$

show. Indeed, it is a direct consequence of the theorems to be proved in
Section 2 that $\\{k\colon a_{k}(fg)>0\\}$ contains infinitely many even and
infinitely many odd integers. In particular, the question to be analized in
this paper is, indeed, nontrivial. As a bypass, in the second half of the
paper, we will also consider the very same problem adapted to other manifolds:
a group cross a high-dimensional sphere, keeping isotropy of the kernel with
respect to the spherical component and the unit sphere in $\mathbb{C}^{q}$.

The other sections in the paper are organized as follows. In Section 2, we
will solve the problem proposed above in the case of a compact two-point
homogeneous space $\mathbb{M}^{d}$. In Section 3, we extend the results from
Section 2 for intersection classes of positive definite kernels taking into
account original characterizations for the classes in [22, 25]. In Section 4,
we extrapolate the problem to space-time kernels, that is, complex kernels on
$G\times S^{d}$, in which $G$ is a locally compact group, adopting the context
for positive definiteness presented in [4, 17]. In particular, isotropy for
the $S^{d}$ component of the kernel will be kept in the analysis. Finally, in
Section 5, we consider the very same problem now adapted to complex kernels on
the unit sphere in $\mathbb{C}^{q}$.

##  2 The main results for homogeneous spaces

We begin recalling a general linearization formula for Jacobi polynomials [1,
p. 41]. For a fixed $\mathbb{M}^{d}$ and two functions with Fourier–Jacobi
series representation as in (1.3), it implies a linearization in the series
expansion of the product of the functions.

######  Lemma 2.1.

If $\alpha\geq\beta>-1$ and

$\displaystyle(\alpha+\beta+1)(\alpha+\beta+4)^{2}(\alpha+\beta+6)\geq(\alpha-\beta)^{2}\big{[}(\alpha+\beta+1)^{2}-7(\alpha+\beta+1)-24\big{]},$

then

$\displaystyle
P_{k}^{(\alpha,\beta)}(t)P_{l}^{(\alpha,\beta)}(t)=\sum_{\mu=|k-l|}^{k+l}b_{k,l}^{\alpha,\beta}(\mu)P_{\mu}^{(\alpha,\beta)}(t),\qquad
t\in[-1,1],$

in which all the coefficients $b_{k,l}^{\alpha,\beta}(\mu)$ are nonnegative.
The coefficient $b_{k,l}^{\alpha,\beta}(k+l)$ is, in fact, positive.

###### Proof.

The recurrence relation for the product was set up by Hylleraas in [20] while
the nonnegativity of the coefficients was obtained by Gasper in [12, 13]. The
last statement in the lemma is implicit in the proof of Theorem 1 in [12]. ∎

It is an easy matter to see that the nonnegativity of the coefficients is
granted in the cases in which $\alpha\geq\beta>-1$ and $\alpha+\beta\geq-1$.
In particular, it is also granted in the cases in which $\alpha=(d-2)/2$ and
$\beta=-1/2,0,1,3$ covered by Wang’s classification. Therefore, for all the
compact two-point homogeneous spaces, the class of functions possessing a
representation as in (1.3) is a semigroup under pointwise multiplication.

The Jacobi polynomial $P_{k}^{(-1/2,-1/2)}$ is a positive multiple of the
Chebyshev polynomial $T_{k}$ of the first kind. Normalizing the Chebyshev
polynomials by $T_{k}(1)=1$, $k=0,1,\ldots$, we have that

$\displaystyle T_{k}(t)=\cos(k\arccos t),\qquad t\in[-1,1],\qquad
k=0,1,\ldots,$

and the linearization formula described in Lemma 2.1 reduces itself to the
cosine addition formula

$\displaystyle T_{k}(t)T_{l}(t)=\frac{1}{2}[T_{k+l}(t)+T_{|k-l|}(t)],\qquad
t\in[-1,1],\qquad k,l\in\mathbb{Z}_{+}.$

Now, if $f$ and $g$ are the isotropic parts of positive definite kernels on
$S^{1}$ with Fourier–Jacobi series as in (1.3), we can replace
$P_{k}^{(-1/2,-1/2)}$ with $T_{k}$ and write

$\displaystyle f(t)g(t)=\sum_{k,l=0}^{\infty}a_{k}(f)a_{l}(g)T_{k}(t)T_{l}(t)$
$\displaystyle\hphantom{f(t)g(t)}{}=\sum_{k,l=0}^{\infty}a_{k}(f)a_{l}(g)\left\\{\frac{1}{2}\cos[(k+l)\arccos
t]+\frac{1}{2}\cos[|k-l|\arccos t]\right\\},\\!\\!\qquad t\in[-1,1].$

Since the series above is absolute convergent at $t=1$, we can rearrange it in
order to obtain

$\displaystyle
f(t)g(t)=\frac{1}{2}\sum_{\mu=0}^{\infty}\bigg{(}\sum_{k+l=\mu}a_{k}(f)a_{l}(g)\bigg{)}T_{\mu}(t)$
$\displaystyle\hphantom{f(t)g(t)=}{}+\frac{1}{2}\sum_{\nu=0}^{\infty}\bigg{(}\sum_{|k-l|=\nu}a_{k}(f)a_{l}(g)\bigg{)}T_{\nu}(t),\qquad
t\in[-1,1].$

That is,

$\displaystyle f(t)g(t)=\sum_{m=0}^{\infty}a_{m}(fg)T_{m}(t),\qquad
t\in[-1,1],$

in which

$\displaystyle
a_{0}(fg)=a_{0}(f)a_{0}(g)+\frac{1}{2}\sum_{\mu=1}^{\infty}a_{\mu}(f)a_{\mu}(g)$

and

$\displaystyle
a_{m}(fg)=\frac{1}{2}\sum_{\nu=0}^{m}a_{\nu}(f)a_{m-\nu}(g)+\frac{1}{2}\sum_{\mu=0}^{\infty}a_{\mu}(f)a_{\mu+m}(g)+a_{\mu+m}(f)a_{\mu}(g),\qquad
m\geq 1.$

It is very easy to see that, for a fixed integer $m$, $a_{|m|}(fg)>0$ if, and
only if, $m$ belongs to the set $\\{\pm k\pm l\colon a_{k}(f)a_{l}(g)>0\\}$.
In view of Theorem 1.1$(i)$, we have proved the following result.

######  Theorem 2.2.

Let $f$ and $g$ be the isotropic parts of positive definite kernels on $S^{1}$
and consider their Fourier–Jacobi series representations according to (1.3).
Then, $fg$ is the isotropic part of a strictly positive definite kernel on
$S^{1}$ if, and only if, the set

$\displaystyle\\{\pm k\pm l\colon a_{k}(f)a_{l}(g)>0\\}$

intersects every full arithmetic progression in $\mathbb{Z}$.

Next, we will extend Theorem 2.2 to all the other compact two-point
homogeneous spaces appearing in Wang’s classification. We find convenient to
prove and use the following technical result, a direct consequence of Lemma
2.1.

######  Lemma 2.3.

Let $\alpha$ and $\beta$ be real numbers with $\alpha\geq\beta>-1$ and
$\alpha+\beta\geq-1$. Define $h\colon[-1,1]\to\mathbb{R}$ by the formula

$\displaystyle
h(t)=\sum_{k,l=0}^{\infty}b_{k,l}P_{k}^{(\alpha,\beta)}(t)P_{l}^{(\alpha,\beta)}(t),\qquad
t\in[-1,1],$

where all the coefficients $b_{k,l}$ are nonnegative and
$\sum\limits_{k,l=0}^{\infty}b_{k,l}P_{k}^{(\alpha,\beta)}(1)P_{l}^{(\alpha,\beta)}(1)<\infty$.
The following assertions are equivalent:

  1. $(i)$

the function $h$ is a polynomial;

  2. $(ii)$

the set $\\{k+l\colon b_{k,l}>0\\}$ is finite.

###### Proof.

The function $h$ is obviously well defined due to the inequality
$\big{|}P_{k}^{(\alpha,\beta)}(t)\big{|}\leq P_{k}^{(\alpha,\beta)}(1)$,
$t\in[-1,1]$. By Lemma 2.1, we can put $h$ into the form

$\displaystyle
h(t)=\sum_{k,l=0}^{\infty}b_{k,l}\sum_{\mu=0}^{k+l}b_{k,l}^{\alpha,\beta}(\mu)P_{\mu}^{(\alpha,\beta)}(t)=\sum_{\mu=0}^{\infty}\bigg{[}\sum_{k+l\geq\mu}b_{k,l}b_{k,l}^{\alpha,\beta}(\mu)\bigg{]}P_{\mu}^{(\alpha,\beta)}(t),\qquad
t\in[-1,1],$

where we are setting $b_{k,l}^{\alpha,\beta}(\mu)=0$ for $\mu\leq|k-l|-1$. If
$h$ is a polynomial of degree $n$, then

$\displaystyle
0=\sum_{k+l\geq\mu}b_{k,l}b_{k,l}^{\alpha,\beta}(\mu)\geq\sum_{k+l=\mu}b_{k,l}b_{k,l}^{\alpha,\beta}(\mu)\geq
0,\qquad\mu>n.$

In particular, $b_{k,l}=0$ when $k+l>n$. This shows that $(i)$ implies $(ii)$.
The other implication is obvious. ∎

We are about ready for an extension of Theorem 2.2 to those compact two-point
homogeneous spaces which are not spheres.

######  Theorem 2.4.

Let $f$ and $g$ be isotropic parts of positive definite kernels on
$\mathbb{M}^{d}$ and consider their Fourier–Jacobi series representations
according to (1.3). Assume $\mathbb{M}^{d}$ is not a sphere. The function $fg$
is the isotropic part of a strictly positive definite kernel on
$\mathbb{M}^{d}$ if, and only if, the set $\\{k+l\colon a_{k}(f)a_{l}(g)>0\\}$
is infinite.

###### Proof.

The starting point of the proof is the formula

$\displaystyle
f(t)g(t)=\sum_{k,l=0}^{\infty}a_{k}(f)a_{l}(g)P_{k}^{((d-2)/2,\beta)}(t)P_{l}^{((d-2)/2,\beta)}(t),\qquad
t\in[-1,1],$

with $\beta$ depending upon the manifold $\mathbb{M}^{d}$. An application of
Theorem 1.1$(iii)$ reveals that $fg$ is the isotropic part of a positive
definite kernel on $\mathbb{M}^{d}$ which is not strictly positive definite
if, and only if, $fg$ is a polynomial. However, by Lemma 2.3, this is the case
if, and only if, the set $\\{k+l\colon a_{k}(f)a_{l}(g)>0\\}$ is finite. ∎

The previous theorem allows the following reformulation.

######  Theorem 2.5.

Let $f$ and $g$ be nonzero isotropic parts of positive definite kernels on
$\mathbb{M}^{d}$. Assume $\mathbb{M}^{d}$ is not a sphere. The following
assertions are equivalent:

  1. $(i)$

$fg$ is the isotropic part of a strictly positive definite kernel on
$\mathbb{M}^{d}$;

  2. $(ii)$

either $f$ or $g$ is the isotropic part of a strictly positive definite kernel
on $\mathbb{M}^{d}$;

  3. $(iii)$

either $f$ or $g$ is not a polynomial.

We close the section handling the case in which $\mathbb{M}^{d}$ is a high-
dimensional sphere.

######  Theorem 2.6.

$(d\geq 2)$. Let $f$ and $g$ be the isotropic parts of positive definite
kernels on $S^{d}$ and consider their Fourier–Jacobi series representations
according to (1.3). The product $fg$ is the isotropic part of a strictly
positive definite kernel on $S^{d}$ if, and only if, the set

$\displaystyle\\{k+l\colon a_{k}(f)a_{l}(g)>0\\}$

contains infinitely many even and infinitely many odd integers.

###### Proof.

In the case in which $\alpha=\beta$, the Jacobi polynomials
$P_{k}^{(\alpha,\beta)}$ are positive multiples of the Gegenbauer polynomials
$C_{k}^{\alpha}$:

$\displaystyle
P_{k}^{(\alpha-1/2,\alpha-1/2)}(t)=\frac{(\alpha+1/2)_{k}}{(2\alpha)_{k}}C_{k}^{\alpha}(t),\qquad
t\in[-1,1],\qquad k=0,1,\ldots.$

So, we can think of the expansions (1.3) of $f$ and $g$ in terms of the
Gegenbauer polynomials $C_{k}^{(d-1)/2}$. In particular, we may write

$\displaystyle
f(t)g(t)=\sum_{k,l=0}^{\infty}a_{k}(f)a_{l}(g)C_{k}^{(d-1)/2}(t)C_{l}^{(d-1)/2}(t),\qquad
t\in[-1,1].$

By Theorem 1.1$(ii)$, the function $fg$ is the isotropic part of a positive
definite kernel on $S^{d}$ which is not strictly positive definite if, and
only if, either $\\{k\colon a_{2k}(fg)>0\\}$ or $\\{k\colon a_{2k+1}(fg)>0\\}$
is finite. Since $C_{k}^{(d-1)/2}(-t)=(-1)^{k}C_{k}^{(d-1)/2}(t)$,
$t\in[-1,1]$, we have that

$\displaystyle
f(t)g(t)-f(-t)g(-t)=2\sum_{k=0}^{\infty}a_{2k+1}(fg)C_{2k+1}^{(d-1)/2}(t),\qquad
t\in[-1,1],$

and

$\displaystyle
f(t)g(t)+f(-t)g(-t)=2\sum_{k=0}^{\infty}a_{2k}(fg)C_{2k}^{(d-1)/2}(t),\qquad
t\in[-1,1].$

Hence, the previous assertion corresponds to either one of the functions above
being a polynomial. However, since we have the alternative representations

$\displaystyle f(t)g(t)-f(-t)g(-t)=2\sum_{k+l\in
2\mathbb{Z}_{+}+1}a_{k}(f)a_{l}(g)C_{k}^{(d-1)/2}(t)C_{l}^{(d-1)/2}(t),\qquad
t\in[-1,1],$

and

$\displaystyle f(t)g(t)+f(-t)g(-t)=2\sum_{k+l\in
2\mathbb{Z}_{+}}a_{k}(f)a_{l}(g)C_{k}^{(d-1)/2}(t)C_{l}^{(d-1)/2}(t),\qquad
t\in[-1,1],$

we conclude from Lemma 2.3, that $fg$ is the isotropic part of a positive
definite kernel on $S^{d}$ which is not strictly positive definite if, and
only if, either $\\{k+l\in 2\mathbb{Z}_{+}+1\colon a_{k}(f)a_{l}(g)>0\\}$ or
$\\{k+l\in 2\mathbb{Z}_{+}\colon a_{k}(f)a_{l}(g)>0\\}$ is finite. That is,
the set

$\displaystyle\\{k+l\colon a_{k}(f)a_{l}(g)>0\\}$

contains either finitely many even or finitely many odd integers. ∎

##  3 Extensions to intersection classes

The setting here is still aligned with that adopted in the previous section.
We will assume the isotropic part of the kernels have either one of the forms

$\displaystyle f(t)=\sum_{k=0}^{\infty}a_{k}(f)t^{k},\qquad t\in[-1,1],$ (3.1)

or

$\displaystyle
f(t)=\sum_{k=0}^{\infty}a_{k}(f)\left(\frac{1+t}{2}\right)^{k},\qquad
t\in[-1,1],$ (3.2)

where the coefficients $a_{k}(f)$ are all nonnegative and the series is
convergent at $t=1$.

According to Schoenberg, a continuous function $f\colon[-1,1]\to\mathbb{R}$
admits the representation (3.1) if, and only if, it is the isotropic part of a
positive definite kernel on $S^{d}$, for $d=1,2,\ldots$. On the other hand, a
theorem proved in [15] shows that a continuous function $f$ has the
representation (3.2) if, and only if, each one of the following three
equivalent assertions hold:

  1. –

$f$ is the isotropic part of a positive definite kernel on
$P^{d}(\mathbb{R})$, for $d=2,3,\ldots$;

  2. –

$f$ is the isotropic part of a positive definite kernel on
$P^{d}(\mathbb{C})$, for $d=4,8,\ldots$;

  3. –

$f$ is the isotropic part of a positive definite kernel on
$P^{d}(\mathbb{H})$, for $d=8,12,\ldots$.

For coherence, we will say that $f$ is the isotropic part of a positive
definite kernel on $S^{\infty}$ in the first case and on $P^{\infty}$ in the
second case. In the first case, the notation makes perfect sense if we
interpret $S^{\infty}$ as the unit sphere in the usual real space $\ell_{2}$
endowed with its usual distance defined by

$\displaystyle|xy|:=2\arccos x\cdot y,\qquad x,y\in S^{\infty},$

where $\cdot$ denotes the standard inner product of $\ell_{2}$. Indeed, as
explained in [5, 10, 25], if $f$ is continuous in $[-1,1]$, the kernel
$K(x,y)=f(\cos(|xy|/2))$, $x,y\in S^{\infty}$, is positive definite if, and
only if, $f$ admits the representation (3.1).

Regarding strict positive definiteness for kernels generated by functions in
the two classes above, the result detached below holds. The proof of the first
assertion can be found in [22] while the proof of the other one can be
obtained similarly.

######  Theorem 3.1.

Let $f$ be the isotropic part of a positive definite kernel $K$ on
$S^{\infty}$ $($respectively, $P^{\infty})$. The kernel $K$ is strictly
positive definite if, and only if, the set $\\{k\colon a_{k}(f)>0\\}$ defined
from (3.1) $($respectively, (3.2)$)$ contains infinitely many even and
infinitely many odd integers $($respectively, infinitely many integers$)$.

The reader will easily verify that Lemma 2.3 still holds true when we replace
$P_{k}^{(\alpha,\beta)}(t)$ with either $t^{k}$ or $2^{-k}(1+t)^{k}$. Indeed,
the proofs are a lot easier in these cases due to the simpler structure of the
linearization formulas

$\displaystyle t^{k}t^{l}=t^{k+l},\qquad t\in[-1,1,],\qquad
k,l\in\mathbb{Z}_{+},$

and

$\displaystyle\left(\frac{1+t}{2}\right)^{k}\left(\frac{1+t}{2}\right)^{l}=\left(\frac{1+t}{2}\right)^{k+l},\qquad
t\in[-1,1],\qquad k,l\in\mathbb{Z}_{+}.$

Equally simple adaptations in the proofs of Theorems 2.4 and 2.6 justify the
following two extensions of the main results proved in Section 2.

######  Theorem 3.2.

Let $f$ and $g$ be the isotropic parts of positive definite kernels on
$S^{\infty}$ and consider their series representations according (3.1). The
product $fg$ is the isotropic part of a strictly positive definite kernel on
$S^{\infty}$ if, and only if, the set

$\displaystyle\\{k+l\colon a_{k}(f)a_{l}(g)>0\\}$

contains infinitely many even and infinitely many odd integers.

######  Theorem 3.3.

Let $f$ and $g$ be nonzero isotropic parts of positive definite kernels on
$P^{\infty}$. The following assertions are equivalent:

  1. $(i)$

$fg$ is the isotropic part of a strictly positive definite kernel on
$P^{\infty}$;

  2. $(ii)$

either $f$ or $g$ is the isotropic part of a strictly positive definite kernel
on the space;

  3. $(iii)$

either $f$ or $g$ is not a polynomial.

##  4 The case of a locally compact group cross $\boldsymbol{S^{d}}$

In this section, we expand a little bit the setting considered in the previous
sections by analyzing the very same question in a case that includes space-
time positive definite kernels. The setting here is the one in [4, 17], a
brief description of which is as follows.

If $G$ is a locally compact group with operation $*$ and neutral element $e$,
we intend to consider positive definite kernels $K\colon G\times
S^{d}\to\mathbb{C}$ that have the form

$\displaystyle((u,x),(v,y))\in\big{(}G\times S^{d}\big{)}^{2}\to
K((u,x),(v,y))=f\big{(}u^{-1}*v,\cos(|xy|/2)\big{)}$

in which $f$ is a complex continuous function with domain $G\times[-1,1]$. In
this setting, we need to use the definition of positive definiteness in its
full strength, that is, the left hand side of (1.2) needs to be of the form
$\sum\limits_{i,j=1}^{n}c_{i}\overline{c_{j}}K(y_{i},y_{j})$, with complex
$c_{i}$ and the $y_{i}$ in $G\times S^{d}$. A similar remark holds for strict
positive definiteness. In analogy with the previous sections, we will call the
function $f\colon G\times[-1,1]\to\mathbb{C}$, the isotropic part of the
kernel. According to [4], the positive definiteness of $K$ corresponds to the
following series representation for $f$

$\displaystyle
f(u,t)=\sum_{k=0}^{\infty}a_{k}^{d}(f;u)C_{k}^{(d-1)/2}(t),\qquad(u,t)\in
G\times[-1,1],$

in which $\\{a_{k}^{d}(f;\cdot)\\}$ is a sequence of continuous functions on
$G$ defining positive definite kernels $(u,v)\in G^{2}\to
a_{k}^{d}\big{(}f;u^{-1}*v\big{)}$ and
$\sum\limits_{k}a_{k}^{d}(f;e)C_{k}^{(d-1)/2}(1)<\infty$. The functions
$a_{k}^{d}(f;\cdot)$ appearing above have a closed integral form given by

$\displaystyle
a_{k}^{d}(f;u)=c(k,d)\int_{-1}^{1}f(u,s)C_{k}^{(d-1)/2}(s)\big{(}1-s^{2}\big{)}^{(d-2)/2}{\rm
d}s,\qquad u\in G,$

in which $c(k,d)$ is an appropriate normalization constant depending upon $k$
and $d$.

The following result concerning the strict positive definiteness of a kernel
fitting the description presented in the previous paragraph is a consequence
of a quite general result proved in [17]. It boils down to strict positive
definiteness on $S^{d}$ of a large class of positive definite functions
indexed over $G$.

######  Theorem 4.1 ($d\geq 2$).

Let $f$ be the isotropic part of a positive definite kernel on $G\times
S^{d}$. The following assertions are equivalent:

  1. $(i)$

the kernel $((u,x),(v,y))\in\big{(}G\times S^{d}\big{)}^{2}\to
f\big{(}u^{-1}*v,\cos(|xy|/2)\big{)}$ is strictly positive definite;

  2. $(ii)$

if $p$ is a positive integer at most the cardinality of $G$,
$u_{1},u_{2},\ldots,u_{p}$ are distinct points in $G$ and $c$ is a nonzero
vector in $\mathbb{C}^{p}$, then the function

$\displaystyle
t\in[-1,1]\to\sum_{\mu,\nu=1}^{p}c_{\mu}\overline{c_{\nu}}f\big{(}u_{\mu}^{-1}*v_{\nu},t\big{)},$

is the isotropic part of a strictly positive definite kernel on $S^{d}$.

The main result in this section is as follows.

######  Theorem 4.2 ($d\geq 2$).

Let $f$ and $g$ be isotropic parts of positive definite kernels on $G\times
S^{d}$. The following assertions are equivalent:

  1. $(i)$

the product $fg$ is the isotropic part of a strictly positive definite kernel
on $G\times S^{d}$;

  2. $(ii)$

the set

$\displaystyle\big{\\{}k+l\colon
c^{t}\big{[}a_{k}^{d}\big{(}f;u_{\mu}^{-1}*u_{\nu}\big{)}a_{l}^{d}\big{(}g;u_{\mu}^{-1}*u_{\nu}\big{)}\big{]}_{\mu,\nu=1}^{p}\overline{c}>0\big{\\}}$

contains infinitely many even and infinitely many odd integers, whenever
$p\geq 1$, $u_{1},u_{2},$ $\ldots,u_{p}$ are distinct points in $G$ and $c$ is
a nonzero vector in $\mathbb{C}^{p}$.

###### Proof.

By Theorem 4.1, the function $fg$ is the isotropic part of a strictly positive
definite kernel on $G\times S^{d}$ if, and only if, for every $p\geq 1$,
distinct points $u_{1},u_{2},\ldots,u_{p}$ in $G$ and a nonzero vector $c$ in
$\mathbb{C}^{p}$, the function $h\colon[-1,1]\to\mathbb{C}$ defined by

$\displaystyle
h(t)=\sum_{\mu,\nu=1}^{p}c_{\mu}\overline{c_{\nu}}f\big{(}u_{\mu}^{-1}*v_{\nu},t\big{)}g\big{(}u_{\mu}^{-1}*v_{\nu},t\big{)}$

is the isotropic part of a strictly positive definite kernel on $S^{d}$.
Introducing series representations, we can re-write the expression above as

$\displaystyle
h(t)=\\!\sum_{k,l=0}^{\infty}\\!\left[\sum_{\mu,\nu=1}^{p}c_{\mu}\overline{c_{\nu}}a_{k}^{d}\big{(}f,u_{\mu}^{-1}*v_{\nu}\big{)}a_{l}^{d}\big{(}g,u_{\mu}^{-1}*v_{\nu}\big{)}\right]\\!C_{k}^{(d-1)/2}(t)C_{l}^{(d-1)/2}(t),\\!\\!\\!\qquad
t\in[-1,1].$

In other words,

$\displaystyle
h(t)=\\!\sum_{k,l=0}^{\infty}\\!\big{\\{}c^{t}\big{[}a_{k}^{d}\big{(}f;u_{\mu}^{-1}*u_{\nu}\big{)}a_{l}^{d}\big{(}g;u_{\mu}^{-1}*u_{\nu}\big{)}\big{]}_{\mu,\nu=1}^{p}\overline{c}\big{\\}}C_{k}^{(d-1)/2}(t)C_{l}^{(d-1)/2}(t),\\!\\!\\!\\!\qquad
t\in[-1,1],$

in which $c$ is the vector with entries $c_{1},c_{2},\ldots,c_{p}$. We now can
repeat the arguments used in Section 3 in order to see that $h$ is the
isotropic part of a strictly positive definite kernel on $S^{d}$ if, and only
if,

$\displaystyle\big{\\{}k+l\colon
c^{t}\big{[}a_{k}^{d}\big{(}f;u_{\mu}^{-1}*u_{\nu}\big{)}a_{l}^{d}\big{(}g;u_{\mu}^{-1}*u_{\nu}\big{)}\big{]}_{\mu,\nu=1}^{p}\overline{c}>0\big{\\}}$

contains infinitely many even and infinitely many odd integers. ∎

The previous theorem can be put in a more general form, following the setting
adopted in [17]. Details will be not included here.

The strict positive definiteness of product covariance functions on
$\mathbb{R}^{d}$ alone was considered in [7, 8, 9], where the reader can also
find explanations regarding the practicability and the computational
advantages and simplifications implied by the use of such separable covariance
functions in the geostatistical literature. However, a self-contained
characterization for the strict positive definiteness of a product of positive
definite kernels on $\mathbb{R}^{d}$ is still elusive.

We close the section presenting an explicit construction in the case in which
$G$ is the usual group $(\mathbb{R},+)$.

######  Example 4.3.

Let $f$ and $g$ be the isotropic parts of strictly positive definite kernels
on $S^{\infty}$. If $\lambda$ and $\theta$ are real numbers, then the
functions $F$ and $G$ given by

$\displaystyle F(u,t)=f(t\cos\lambda
u)=\sum_{k=0}^{\infty}\big{[}a_{k}(f)\cos^{k}\lambda
u\big{]}t^{k},\qquad(t,u)\in[-1,1]\times\mathbb{R},$

and

$\displaystyle G(u,t)=g(t\cos\theta
u)=\sum_{k=0}^{\infty}\big{[}a_{l}(g)\cos^{l}\theta
u\big{]}t^{l},\qquad(t,u)\in[-1,1]\times\mathbb{R},$

are isotropic parts of positive definite kernels on $\mathbb{R}\times
S^{\infty}$ and these kernels are not strictly positive definite. However, if
$\lambda$ and $\theta$ are nonzero and $\lambda/\theta$ is not a rational
number, then $FG$ is the isotropic part of a strictly positive definite kernel
on $\mathbb{R}\times S^{\infty}$. Indeed, if $p\geq 1$, $u_{1},u_{2}$,
$\ldots,u_{p}$ are distinct points in $\mathbb{R}$ and $c$ is a nonzero vector
in $\mathbb{C}^{p}$, then

$\displaystyle\lim_{\min(k,l)\to\infty}\cos(\lambda(x_{\mu}-x_{\nu}))^{k}\cos(\theta(x_{\mu}-x_{\nu}))^{l}=\delta_{\mu\nu}.$

In particular, the set

$\displaystyle\big{\\{}k+l\colon
c^{t}\big{[}a_{k}(f)\cos(\lambda(x_{\mu}-x_{\nu}))^{k}a_{l}(g)\cos(\theta(x_{\mu}-x_{\nu}))^{l}\big{]}_{\mu,\nu=1}^{p}\overline{c}>0\big{\\}}$

contains infinitely many even and infinitely many odd integers, as required by
Theorem 4.2$(ii)$.

##  5 The complex spherical case

In this section, we revisit Section 2 and the complex counterpart of the
spherical case.

We write $\Omega_{2q}$ to denote the unit sphere in $\mathbb{C}^{q}$ and
$\cdot$ to denote the usual inner product of $\mathbb{C}$. The positive
definite kernels to be considered here are of the form

$\displaystyle K(x,y)=f(x\cdot y),\qquad x,y\in\Omega_{2q},$

in which $f$ is a complex continuous function on
$\mathbb{D}:=\\{z\in\mathbb{C}\colon|z|\leq 1\\}$ if $q\geq 2$ and on
$\Omega_{2}$ if $q=1$. Once again, we observe that the scalars in the
definition of positive definiteness according to (1.2) needs to be complex
ones. A positive definite kernel on $\Omega_{2q}$ is invariant with respect to
unitary transformations of $\mathbb{C}^{q}$, the reason why we will call $f$
the isotropic part of $K$.

According to [24], in the case $q\geq 2$, a kernel $K$ as above is positive
definite if, and only if, its isotropic part $f$ is representable in the form

$\displaystyle f(z)=\sum_{m,n=0}^{\infty}a_{m,n}(f)R_{m,n}^{q-2}(z),\qquad
z\in\mathbb{D},$ (5.1)

in which all the coefficients $a_{m,n}$ are nonnegative, $R_{m,n}^{q-2}$ is
the disk (or Zernike) polynomial of bi-degree $(m,n)$ associated with the
integer $q-2$ and the series is convergent at $z=1$. The disk polynomials are
discussed in [29]. In the case $q=1$, the representation for $f$ becomes

$\displaystyle f(z)=\sum_{m\in\mathbb{Z}}a_{m}(f)z^{m},\qquad z\in\Omega_{2},$

in which all the coefficients $a_{m}(f)$ are nonnegative and the series is
convergent at $z=1$. The strict positive definiteness of the kernel in each
case is equivalent to $\\{m-n\colon a_{m,n}(f)>0\\}$ (respectively,
$\\{m\colon a_{m}(f)>0\\}$) intersecting every full arithmetic progression of
$\mathbb{Z}$. Details on that can be found in [16, 23].

If $f$ and $g$ are the isotropic parts of two positive definite kernels on
$\Omega_{2}$, a procedure very close to that used at the beginning in Section
3 leads to the following criterion: $fg$ is the isotropic part of a strictly
positive definite kernel on $\Omega_{2}$ if, and only if, $\\{m+n\colon
a_{m}(f)a_{n}(g)>0\\}$ intersects every full arithmetic progression of
$\mathbb{Z}$. The details will be not included.

In order to handle the case $q\geq 2$, it is relevant to recall a
linearization formula for disk polynomials proved by Koornwinder [21], a
generalization of the one described in Lemma 2.1: for nonnegative integers
$m_{1}$, $m_{2}$, $n_{1}$, $n_{2}$, it reads

$\displaystyle
R_{m_{1},n_{1}}^{q-2}(z)R_{m_{2},n_{2}}^{q-2}(z)=\sum_{m,n}a_{m_{1},n_{1};m_{2},n_{2}}^{q;m,n}R_{m,n}^{q-2}(z),\qquad
z\in\mathbb{D},$ (5.2)

in which all the coefficients $a_{m_{1},n_{1};m_{2},n_{2}}^{q;m,n}$ are
nonnegative. The sum takes into account just the pairs $(m,n)$ satisfying

$\displaystyle m_{1}+m_{2}+n=n_{1}+n_{2}+m,\qquad|m_{1}+n_{1}-m_{2}-n_{2}|\leq
m+n\leq m_{1}+n_{1}+m_{2}+n_{2}.$

Its structure is not as good as the other ones we have used so far in this
paper, once the disk polynomials are double-indexed functions. However, a
counterpart of Lemma 2.3 can be enunciated and proved as follows.

######  Lemma 5.1.

Let $f$ be a function as in (5.1). For each $k\in\mathbb{Z}$, define

$\displaystyle f_{k}(z)=\sum_{m-n=k}a_{m,n}(f)R_{m,n}^{q-2}(z),\qquad
z\in\mathbb{D}.$

The following assertions are equivalent:

  1. $(i)$

the function $f$ is the isotropic part of a strictly positive definite kernel
on $\Omega_{2q}$;

  2. $(ii)$

the set $\\{k\colon f_{k}\not\equiv 0\\}$ intersects every full arithmetic
progression in $\mathbb{Z}$.

###### Proof.

Since the series expansion for $f$ is convergent at $z=1$, and
$\big{|}R_{m,n}^{q-2}(z)\big{|}\leq R_{m,n}^{q-2}(1)$, we can write the
equality

$\displaystyle f(z)=\sum_{k\in\mathbb{Z}}f_{k}(z),\qquad z\in\mathbb{D}.$

Obviously, each $f_{k}$ is continuous in $\mathbb{D}$ and, in addition, it is
the isotropic part of a positive definite kernel on $\Omega_{2q}$. Since

$\displaystyle\\{m-n\colon a_{m,n}(f)>0\\}=\\{k\colon f_{k}\not\equiv 0\\},$

the assertion in the statement of the lemma follows. ∎

We can now state and prove the main result in this section.

######  Theorem 5.2 ($q\geq 2$).

Let $f$ and $g$ be the isotropic parts of two positive definite kernels on
$\Omega_{2q}$ and consider their series representation according to (5.1).
Then, $fg$ is the isotropic part of a strictly positive definite kernel on
$\Omega_{2q}$ if, and only if, the set

$\displaystyle\\{(m-n)+(m^{\prime}-n^{\prime})\colon
a_{m,n}(f)a_{m^{\prime},n^{\prime}}(g)>0\\}$

intersects every full arithmetic progression in $\mathbb{Z}$.

###### Proof.

The first step in the proof is to write

$\displaystyle
f(z)g(z)=\sum_{k,l\in\mathbb{Z}}f_{k}(z)g_{l}(z)=\sum_{\mu\in\mathbb{Z}}\sum_{k+l=\mu}f_{k}(z)g_{l}(z),\qquad
z\in\mathbb{D}.$

The second equality above is supported by the inequality

$\displaystyle\sum_{k,l\in\mathbb{Z}}|f_{k}(z)g_{l}(z)|\leq\sum_{k,l\in\mathbb{Z}}f_{k}(1)g_{l}(1)=f(1)g(1).$

Since the indices in (5.2) satisfy

$\displaystyle m-n=(m_{1}-n_{1})+(m_{2}-n_{2}),$

for each pair $((m_{1},n_{1}),(m_{2},n_{2}))$, we can write

$\displaystyle
f_{k}(z)g_{l}(z)=\sum_{m-n=k+l}b^{k,l}_{m,n}R_{m,n}^{q-2}(z),\qquad
z\in\mathbb{D},$

where all the coefficients $b^{k,l}_{m,n}$ are nonnegative. Consequently,

$\displaystyle\sum_{k+l=\mu}f_{k}(z)g_{l}(z)=\sum_{m-n=\mu}b_{m,n}R_{m,n}^{q-2}(z),\qquad
z\in\mathbb{D},$

and, in particular,

$\displaystyle(fg)_{\mu}(z)=\sum_{k+l=\mu}f_{k}(z)g_{l}(z),\qquad
z\in\mathbb{D}.$

Thus, by Lemma 5.1, it remains to show that

$\displaystyle\\{\mu\colon(fg)_{\mu}\not\equiv
0\\}=\\{m-n+m^{\prime}-n^{\prime}\colon
a_{m,n}(f)a_{m^{\prime},n^{\prime}}(g)>0\\}.$

If $(fg)_{\mu}$ is not the zero function for some $\mu$, then there exists a
pair $(k,l)$ with $k+l=\mu$ so that neither $f_{k}$ nor $g_{l}$ is the zero
function. Hence, there are pairs $(m,n)$ with $m-n=k$ and
$(m^{\prime},n^{\prime})$ with $m^{\prime}-n^{\prime}=l$ so that
$a_{m,n}(f)>0$ and $a_{m^{\prime},n^{\prime}}(g)>0$. In other words,
$\mu\in\\{m-n+m^{\prime}-n^{\prime}\colon
a_{m,n}(f)a_{m^{\prime},n^{\prime}}(g)>0\\}$. Conversely, if
$\mu\in\\{m-n+m^{\prime}-n^{\prime}\colon
a_{m,n}(f)a_{m^{\prime},n^{\prime}}(g)>0\\}$, then
$\mu=m-n+m^{\prime}-n^{\prime}$ for pairs $(m,n)$ and
$(m^{\prime},n^{\prime})$ for which
$a_{m,n}(f)a_{m^{\prime},n^{\prime}}(g)>0$. Defining, $k=m-n$ and
$l=m^{\prime}-n^{\prime}$, it follows that both $f_{k}$ and $g_{l}$ are not
identically 0. In particular, $f_{k}(1)>0$ and $g_{l}(1)>0$, whence
$(fg)_{\mu}(1)=(fg)_{m-n+m^{\prime}-n^{\prime}}(1)>0$. Thus, $(fg)_{\mu}$ is
not identically zero. ∎

### Acknowledgements

The first and third authors acknowledge partial financial support from FAPESP,
grants $\\#$ 2014/14380-2 and 2016/09906-0. Likewise, the second one
acknowledges partial financial support from PROEX-CAPES. The authors would
like to express their gratitude to the anonymous referees for their valuable
suggestions on the original manuscript.

## References

  * [1] Askey R., Orthogonal polynomials and special functions, Society for Industrial and Applied Mathematics, Philadelphia, Pa., 1975.
  * [2] Barbosa V.S., Menegatto V.A., Strictly positive definite kernels on compact two-point homogeneous spaces, Math. Inequal. Appl. 19 (2016), 743–756, arXiv:1505.00591.
  * [3] Barbosa V.S., Menegatto V.A., Strict positive definiteness on products of compact two-point homogeneous spaces, Integral Transforms Spec. Funct. 28 (2017), 56–73, arXiv:1605.07071.
  * [4] Berg C., Porcu E., From Schoenberg coefficients to Schoenberg functions, Constr. Approx. 45 (2017), 217–241, arXiv:1505.05682.
  * [5] Bingham N.H., Positive definite functions on spheres, Proc. Cambridge Philos. Soc. 73 (1973), 145–156.
  * [6] Chen D., Menegatto V.A., Sun X., A necessary and sufficient condition for strictly positive definite functions on spheres, Proc. Amer. Math. Soc. 131 (2003), 2733–2740.
  * [7] De Iaco S., Myers D.E., Posa D., On strict positive definiteness of product and product-sum covariance models, J. Statist. Plann. Inference 141 (2011), 1132–1140.
  * [8] De Iaco S., Myers D.E., Posa D., Strict positive definiteness of a product of covariance functions, Comm. Statist. Theory Methods 40 (2011), 4400–4408.
  * [9] De Iaco S., Posa D., Strict positive definiteness in geostatistics, Stoch. Environ. Res. Risk Assess. 32 (2018), 577–590.
  * [10] Faraut J., Fonction brownienne sur une variété riemannienne, in Séminaire de Probabilités, VII (Univ. Strasbourg, année universitaire 1971–1972), Lecture Notes in Math., Vol. 321, Springer, Berlin, 1973, 61–76.
  * [11] Gangolli R., Positive definite kernels on homogeneous spaces and certain stochastic processes related to Lévy’s Brownian motion of several parameters, Ann. Inst. H. Poincaré Sect. B 3 (1967), 121–226.
  * [12] Gasper G., Linearization of the product of Jacobi polynomials. I, Canad. J. Math. 22 (1970), 171–175.
  * [13] Gasper G., Linearization of the product of Jacobi polynomials. II, Canad. J. Math. 22 (1970), 582–593.
  * [14] Guella J.C., Menegatto V.A., Strictly positive definite kernels on a product of spheres, J. Math. Anal. Appl. 435 (2016), 286–301, arXiv:1505.03695.
  * [15] Guella J.C., Menegatto V.A., A limit formula for semigroups defined by Fourier–Jacobi series, Proc. Amer. Math. Soc. 146 (2018), 2027–2038.
  * [16] Guella J.C., Menegatto V.A., Unitarily invariant strictly positive definite kernels on spheres, Positivity 22 (2018), 91–103.
  * [17] Guella J.C., Menegatto V.A., Schoenberg’s theorem for positive definite functions on products: a unifying framework, J. Fourier Anal. Appl., to appear.
  * [18] Helgason S., Groups and geometric analysis. Integral geometry, invariant differential operators, and spherical functions, Mathematical Surveys and Monographs, Vol. 83, Amer. Math. Soc., Providence, RI, 2000.
  * [19] Horn R.A., Johnson C.R., Matrix analysis, Cambridge University Press, Cambridge, 1990.
  * [20] Hylleraas E.A., Linearization of products of Jacobi polynomials, Math. Scand. 10 (1962), 189–200.
  * [21] Koornwinder T., Positivity proofs for linearization and connection coefficients of orthogonal polynomials satisfying an addition formula, J. London Math. Soc. 18 (1978), 101–114.
  * [22] Menegatto V.A., Strictly positive definite kernels on the Hilbert sphere, Appl. Anal. 55 (1994), 91–101.
  * [23] Menegatto V.A., Oliveira C.P., Peron A.P., Strictly positive definite kernels on subsets of the complex plane, Comput. Math. Appl. 51 (2006), 1233–1250.
  * [24] Menegatto V.A., Peron A.P., Positive definite kernels on complex spheres, J. Math. Anal. Appl. 254 (2001), 219–232.
  * [25] Schoenberg I.J., Positive definite functions on spheres, Duke Math. J. 9 (1942), 96–108.
  * [26] Szegő G., Orthogonal polynomials, American Mathematical Society, Colloquium Publications, Vol. 23, 4th ed., Amer. Math. Soc., Providence, R.I., 1975.
  * [27] Wang H.-C., Two-point homogeneous spaces, Ann. of Math. 55 (1952), 177–191.
  * [28] Wolf J.A., Spaces of constant curvature, 6th ed., AMS Chelsea Publishing, Providence, RI, 2011.
  * [29] Wünsche A., Generalized Zernike or disc polynomials, J. Comput. Appl. Math. 174 (2005), 135–163.


$\mathcal{E}_{\mathrm{test}}^{\text{SGF}}(t)=\mathcal{E}_{\mathrm{test}}^{\text{GF}}(t)+\frac{\gamma}{2}\mathbb{E}_{\mathcal{A};\bm{X},\bm{y}}\left[\Tr{\boldsymbol{\mathscr{C}}(t)}\right]\;.$
(C.57)

Evaluation of the first term was done in Section C.4. To complete it for the
second term, we refer to Eq. (22a). In our setting,
$\mathscr{L}\bigl{(}\hat{\bm{\beta}};\bm{X},\bm{y};\mathcal{A}\bigl{)}=\frac{1}{2n}\|\bm{y}-\bm{X}_{\mathcal{A}}\hat{\bm{\beta}}_{\mathcal{A}}\|^{2}$,
and its Hessian is

$\bm{{\cal
H}}_{\mathscr{L}}\bigl{(}\hat{\bm{\beta}};\bm{X},\bm{y};\mathcal{A}\bigl{)}=\bm{\nabla}_{\hat{\bm{\beta}}_{\mathcal{A}}}\otimes\bm{\nabla}_{\hat{\bm{\beta}}_{\mathcal{A}}}\mathscr{L}\bigl{(}\hat{\bm{\beta}};\bm{X},\bm{y};\mathcal{A}\bigl{)}=\frac{1}{n}\bm{X}^{\top}_{\mathcal{A}}\bm{X}_{\mathcal{A}}\in\mathbb{R}^{p\times
p}\;.$ (C.58)

Then, the term in Eq. (22b) in our model becomes:

$\displaystyle\bm{U}^{\text{GF}}\left(t,\tau;\bm{X},\bm{y};\mathcal{A}\right)\equiv\mathcal{T}\left\\{e^{-\int_{\tau}^{t}\differential
s\bm{{\cal
H}}_{\mathscr{L}}\bigl{(}\hat{\bm{\beta}}_{\mathcal{A}}^{\text{GF}}(t);\bm{X},\bm{y};\mathcal{A}\bigl{)}}\right\\}=\mathcal{T}\left\\{e^{-\frac{1}{n}\int_{\tau}^{t}\differential
s\bm{X}^{\top}_{\mathcal{A}}\bm{X}_{\mathcal{A}}}\right\\}=e^{-\frac{1}{n}\bm{X}^{\top}_{\mathcal{A}}\bm{X}_{\mathcal{A}}(t-\tau)}\;.$
(C.59)

On the other hand, the diffusion matrix is, as stated in Eq. (23):

$\bm{\Sigma}\bigl{(}\hat{\bm{\beta}}(t);\bm{X},\bm{y};\mathcal{A}\bigl{)}\approx\frac{1}{n^{2}}\bm{X}^{\top}_{\mathcal{A}}\bm{X}_{\mathcal{A}}\cdot\|\bm{y}-\bm{X}_{\mathcal{A}}\hat{\bm{\beta}}_{\mathcal{A}}(t)\|^{2}\;.$
(C.60)

This results in the following covariance matrix of the process:

$\displaystyle\boldsymbol{\mathscr{C}}(t)$
$\displaystyle=\int_{0}^{t}\differential\tau\;\bm{U}^{\text{GF}}\left(t,\tau;\bm{X},\bm{y};\mathcal{A}\right)\;\bm{\Sigma}\bigl{(}\hat{\bm{\beta}}_{\mathcal{A}}^{\text{GF}}(\tau);\bm{X},\bm{y};\mathcal{A}\bigl{)}\;\bm{U}^{\text{GF}}\left(t,\tau;\bm{X},\bm{y};\mathcal{A}\right)^{\top}$
(C.61)
$\displaystyle=\frac{1}{n^{2}}\int_{0}^{t}\differential\tau\;e^{-\frac{1}{n}\bm{X}^{\top}_{\mathcal{A}}\bm{X}_{\mathcal{A}}(t-\tau)}\cdot\bm{X}^{\top}_{\mathcal{A}}\bm{X}_{\mathcal{A}}\cdot\|\bm{y}-\bm{X}_{\mathcal{A}}\hat{\bm{\beta}}_{\mathcal{A}}^{\text{GF}}(\tau)\|^{2}\cdot
e^{-\frac{1}{n}\bm{X}^{\top}_{\mathcal{A}}\bm{X}_{\mathcal{A}}(t-\tau)}$
$\displaystyle=\frac{1}{n^{2}}\int_{0}^{t}\differential\tau\;\|\bm{y}-\bm{X}_{\mathcal{A}}\hat{\bm{\beta}}_{\mathcal{A}}^{\text{GF}}(\tau)\|^{2}\cdot\bm{X}^{\top}_{\mathcal{A}}\bm{X}_{\mathcal{A}}\;e^{-\frac{2}{n}\bm{X}^{\top}_{\mathcal{A}}\bm{X}_{\mathcal{A}}(t-\tau)}\;.$

As
$\|\bm{y}-\bm{X}_{\mathcal{A}}\hat{\bm{\beta}}_{\mathcal{A}}^{\text{GF}}(\tau)\|^{2}$
is scalar and with Eq. (C.3),

$\Tr{\bm{X}^{\top}_{\mathcal{A}}\bm{X}_{\mathcal{A}}\;e^{-\frac{2}{n}\bm{X}^{\top}_{\mathcal{A}}\bm{X}_{\mathcal{A}}(t-\tau)}}=\Tr{\bm{V}\bm{\Lambda}^{\top}\bm{U}^{\top}\bm{U}\bm{\Lambda}\bm{V}^{\top}\bm{V}e^{-\frac{2}{n}\bm{\Lambda}^{\top}\bm{\Lambda}(t-\tau)}\bm{V}^{\top}}=\\\
=\Tr{\bm{\Lambda}^{\top}\bm{\Lambda}e^{-\frac{2}{n}\bm{\Lambda}^{\top}\bm{\Lambda}(t-\tau)}}=\Tr{\bm{\Lambda}^{2}_{r}e^{-\frac{2}{n}\bm{\Lambda}^{2}_{r}(t-\tau)}}\;,$
(C.62)

we obtain the following expression for a trace of the covariance matrix:

$\Tr{\boldsymbol{\mathscr{C}}(t)}=\frac{1}{n^{2}}\int_{0}^{t}\differential\tau\;\|\bm{y}-\bm{X}_{\mathcal{A}}\hat{\bm{\beta}}_{\mathcal{A}}^{\text{GF}}(\tau)\|^{2}\cdot\Tr{\bm{\Lambda}^{2}_{r}e^{-\frac{2}{n}\bm{\Lambda}^{2}_{r}(t-\tau)}}\;.$
(C.63)

Now, we would like to compute
$\mathbb{E}_{\mathcal{A};\bm{X},\bm{y}}\left[\Tr{\boldsymbol{\mathscr{C}}(t)}\right]$.
Expectation over $\bm{X},\bm{y}$ is the same as expectation over
$\bm{U},\bm{\Lambda},\bm{V},\bm{X}_{{\mathcal{A}^{c}}},\bm{\epsilon}$, and
thus, following Eq. (C.52),

$\displaystyle\mathbb{E}_{\bm{X},\bm{y}}\left[\Tr{\boldsymbol{\mathscr{C}}(t)}\right]$
$\displaystyle=\frac{1}{n^{2}}\mathbb{E}_{\bm{\Lambda}}\left[\int_{0}^{t}\differential\tau\;\mathbb{E}_{\bm{U},\bm{V};\bm{X}_{{\mathcal{A}^{c}}},\bm{\epsilon}}\left[\|\bm{y}-\bm{X}_{\mathcal{A}}\hat{\bm{\beta}}_{\mathcal{A}}^{\text{GF}}(\tau)\|^{2}\right]\cdot\Tr{\bm{\Lambda}^{2}_{r}e^{-\frac{2}{n}\bm{\Lambda}^{2}_{r}(t-\tau)}}\right]$
(C.64)
$\displaystyle=\frac{1}{n^{2}}\mathbb{E}_{\bm{\Lambda}}\Bigg{[}\int_{0}^{t}\differential\tau\;\Big{(}\|\bm{\beta}_{\mathcal{A}}-\hat{\bm{\beta}}_{\mathcal{A}}(0)\|^{2}\frac{1}{p}\Tr{\bm{\Lambda}^{2}_{r}e^{-\frac{2}{n}\bm{\Lambda}^{2}_{r}\tau}}+$
$\displaystyle+\left(\|\bm{\beta}_{{\mathcal{A}^{c}}}\|^{2}+\mu^{2}\right)\left(\Tr{e^{-\frac{2}{n}\bm{\Lambda}^{2}_{r}\tau}}+n-r\right)\Big{)}\cdot\Tr{\bm{\Lambda}^{2}_{r}e^{-\frac{2}{n}\bm{\Lambda}^{2}_{r}(t-\tau)}}\Bigg{]}$
$\displaystyle=\frac{1}{n^{2}}\int_{0}^{t}\differential\tau\;\Bigg{[}\|\bm{\beta}_{\mathcal{A}}-\hat{\bm{\beta}}_{\mathcal{A}}(0)\|^{2}\frac{1}{p}\mathbb{E}_{\bm{\Lambda}}\left[\Tr{\bm{\Lambda}^{2}_{r}e^{-\frac{2}{n}\bm{\Lambda}^{2}_{r}\tau}}\Tr{\bm{\Lambda}^{2}_{r}e^{-\frac{2}{n}\bm{\Lambda}^{2}_{r}(t-\tau)}}\right]+\left(\|\bm{\beta}_{{\mathcal{A}^{c}}}\|^{2}+\mu^{2}\right)\cdot$
$\displaystyle\cdot\left(\mathbb{E}_{\bm{\Lambda}}\left[\Tr{e^{-\frac{2}{n}\bm{\Lambda}^{2}_{r}\tau}}\Tr{\bm{\Lambda}^{2}_{r}e^{-\frac{2}{n}\bm{\Lambda}^{2}_{r}(t-\tau)}}\right]+\max\left(0,n-p\right)\mathbb{E}_{\bm{\Lambda}}\left[\Tr{\bm{\Lambda}^{2}_{r}e^{-\frac{2}{n}\bm{\Lambda}^{2}_{r}(t-\tau)}}\right]\right)\Bigg{]}\;.$

We avoid taking the integral of time over a product of traces right now as it
makes further approximation complicated; however, the term below is easy to
simplify:

$\int_{0}^{t}\differential\tau\;\mathbb{E}_{\bm{\Lambda}}\left[\Tr{\frac{1}{n}\bm{\Lambda}^{2}_{r}e^{-\frac{2}{n}\bm{\Lambda}^{2}_{r}(t-\tau)}}\right]=\mathbb{E}_{\bm{\Lambda}}\left[\sum^{r}_{i=1}\frac{1}{n}\lambda^{2}_{i}\int_{0}^{t}\differential\tau\;e^{\frac{2}{n}\lambda^{2}_{i}(\tau-t)}\right]=\\\
=\mathbb{E}_{\bm{\Lambda}}\left[\sum^{r}_{i=1}\frac{1}{n}\lambda^{2}_{i}\cdot\frac{n}{2\lambda^{2}_{i}}\left(1-e^{-\frac{2}{n}\lambda^{2}_{i}t}\right)\right]=\frac{1}{2}\mathbb{E}_{\bm{\Lambda}}\left[\sum^{r}_{i=1}\left(1-e^{-\frac{2}{n}\lambda^{2}_{i}t}\right)\right]=\frac{1}{2}\mathbb{E}_{\bm{\Lambda}}\left[\Tr{\mathbb{I}_{r}-e^{-\frac{2}{n}\bm{\Lambda}^{2}_{r}t}}\right]\;.$
(C.65)

With averaging over feature set $\mathcal{A}$ sampling as in Eq. (C.38) and
substituting as above, we get the expression:

$\displaystyle\mathbb{E}_{\mathcal{A};\bm{X},\bm{y}}\left[\Tr{\boldsymbol{\mathscr{C}}(t)}\right]$
$\displaystyle=\frac{1}{d}\|\bm{\beta}-\hat{\bm{\beta}}^{0}\|^{2}\cdot\int_{0}^{t}\differential\tau\;\mathbb{E}_{\bm{\Lambda}}\left[\Tr{\frac{1}{n}\bm{\Lambda}^{2}_{r}\cdot
e^{-\frac{2}{n}\bm{\Lambda}^{2}_{r}\tau}}\Tr{\frac{1}{n}\bm{\Lambda}^{2}_{r}\cdot
e^{-\frac{2}{n}\bm{\Lambda}^{2}_{r}(t-\tau)}}\right]+$ (C.66)
$\displaystyle+\left(\left(1-\frac{p}{d}\right)\|\bm{\beta}\|^{2}+\mu^{2}\right)\cdot\Bigg{(}\frac{1}{n}\int_{0}^{t}\differential\tau\;\mathbb{E}_{\bm{\Lambda}}\left[\Tr{e^{-\frac{2}{n}\bm{\Lambda}^{2}_{r}\tau}}\Tr{\frac{1}{n}\bm{\Lambda}^{2}_{r}\cdot
e^{-\frac{2}{n}\bm{\Lambda}^{2}_{r}(t-\tau)}}\right]+$
$\displaystyle+\frac{1}{2}\max\left(0,1-\frac{p}{n}\right)\mathbb{E}_{\bm{\Lambda}}\left[\Tr{\mathbb{I}_{r}-e^{-\frac{2}{n}\bm{\Lambda}^{2}_{r}t}}\right]\Bigg{)}\;,$

which matches Eq. (29).

##  Appendix D Asymptotic generalization error

In Appendix C, we derived precise formulas for generalization errors of GF and
SGF solutions. However, to analyze these results, we need to find expectations
for several functions of $\bm{\Lambda}$.

###  D.1 Reformulation with empirical distribution of eigenvalues

We consider $p\times p$ matrix
$\frac{1}{n}\bm{X}^{\top}_{\mathcal{A}}\bm{X}_{\mathcal{A}}$. As elements of
$\bm{X}_{\mathcal{A}}$ are i.i.d. standard normal, the former matrix follows
the Wishart distribution $W_{p}\left(n,\>\frac{1}{n}\mathbb{I}_{p}\right)$
with $n$ degrees of freedom. Let $\nu_{(p\times n)}$ be empirical distribution
of eigenvalues of
$\frac{1}{n}\bm{X}^{\top}_{\mathcal{A}}\bm{X}_{\mathcal{A}}$. As
$\bm{X}_{\mathcal{A}}=\bm{U}\bm{\Lambda}\bm{V}^{\top}$, the spectral
decomposition is

$\frac{1}{n}\bm{X}^{\top}_{\mathcal{A}}\bm{X}_{\mathcal{A}}=\bm{V}\left(\frac{1}{n}\bm{\Lambda}^{\top}\bm{\Lambda}\right)\bm{V}^{\top}\;,$
(D.1)

i.e., eigenvalues are values on the diagonal of
$\bm{\Lambda}^{\top}\bm{\Lambda}$. Following that, the measure $\nu_{(p\times
n)}$ can be defined as:

$\nu_{(p\times
n)}\left(A\right)=\frac{1}{p}\\#\left\\{\frac{1}{n}\lambda^{2}_{i}\in A\mid
i\in\overline{1,p}\right\\}\;,\;A\subset\mathbb{R}\;.$ (D.2)

If $p\leq n$, with probability 1, all eigenvalues are positive; $\\{0\\}$ is a
set of measure 0, and $\nu_{(p\times n)}$ is an absolutely continuous
distribution. Otherwise, it has measure $1-\nicefrac{{n}}{{p}}$.

Let $\varphi:\mathbb{R}\mapsto\mathbb{R}$ be a pointwise function. For
arbitrary diagonal $m\times m$ matrix
$\bm{D}=\operatorname{diag}(d_{11},\dots,d_{mm})$, we define
$\varphi(\bm{D}):=\operatorname{diag}\left(\varphi(d_{11}),\dots,\varphi(d_{mm})\right)\in\mathbb{R}^{m\times
m}$. Then,

$\mathbb{E}_{\sigma\sim\nu_{(p\times
n)}}\left[\varphi(\sigma)\right]=\frac{1}{p}\sum^{p}_{i=1}\mathbb{E}_{\lambda_{i}}\left[\varphi\left(\frac{1}{n}\lambda^{2}_{i}\right)\right]=\frac{1}{p}\mathbb{E}_{\bm{\Lambda}}\left[\Tr{\varphi\left(\frac{1}{n}\bm{\Lambda}^{\top}\bm{\Lambda}\right)}\right]=\\\
=\frac{1}{p}\>\mathbb{E}_{\bm{\Lambda}}\left[\Tr{\varphi\left(\frac{1}{n}\bm{\Lambda}^{2}_{r}\right)}+(p-r)\;\varphi(0)\right]=\max\left(0,1-\frac{n}{p}\right)\varphi(0)+\frac{1}{p}\>\mathbb{E}_{\bm{\Lambda}}\left[\Tr{\varphi\left(\frac{1}{n}\bm{\Lambda}^{2}_{r}\right)}\right]\;.$
(D.3)

Thus, when $p\leq n$, we can express
$\frac{1}{p}\>\mathbb{E}_{\bm{\Lambda}}\left[\Tr{\varphi\left(\frac{1}{n}\bm{\Lambda}^{2}_{r}\right)}\right]$
in terms of expected value of absolutely continuous measure. When $p>n$, we
can repeat our line of thought for $\nu_{(n\times p)}$, which is an empirical
distribution of eigenvalues of $n\times n$ matrix
$\frac{1}{p}\bm{X}_{\mathcal{A}}\bm{X}^{\top}_{\mathcal{A}}$.
$\frac{1}{p}\bm{X}_{\mathcal{A}}\bm{X}^{\top}_{\mathcal{A}}$ also has Wishart
distribution – $W_{n}\left(p,\>\frac{1}{p}\mathbb{I}_{n}\right)$, – and
spectral decomposition

$\frac{1}{p}\bm{X}_{\mathcal{A}}\bm{X}^{\top}_{\mathcal{A}}=\bm{U}\left(\frac{1}{p}\bm{\Lambda}\bm{\Lambda}^{\top}\right)\bm{U}^{\top}\;,$
(D.4)

and obtain:

$\mathbb{E}_{\sigma\sim\nu_{(n\times
p)}}\left[\varphi(\sigma)\right]=\max\left(0,1-\frac{p}{n}\right)\varphi(0)+\frac{1}{n}\>\mathbb{E}_{\bm{\Lambda}}\left[\Tr{\varphi\left(\frac{1}{p}\bm{\Lambda}^{2}_{r}\right)}\right]\;.$
(D.5)

Now, let $\varphi^{\prime}:\mathbb{R}\mapsto\mathbb{R}$ be such function that
$\forall x\in\mathbb{R}:\varphi^{\prime}(x)=\varphi\left(\frac{n}{p}x\right)$.
Then,
$\varphi^{\prime}\left(\frac{1}{n}\bm{\Lambda}^{2}_{r}\right)=\varphi\left(\frac{1}{p}\bm{\Lambda}^{2}_{r}\right)$,
and we can write:

$\displaystyle\frac{1}{p}\>\mathbb{E}_{\bm{\Lambda}}\left[\Tr{\varphi^{\prime}\left(\frac{1}{n}\bm{\Lambda}^{2}_{r}\right)}\right]$
$\displaystyle=\frac{n}{p}\cdot\frac{1}{n}\>\mathbb{E}_{\bm{\Lambda}}\left[\Tr{\varphi\left(\frac{1}{p}\bm{\Lambda}^{2}_{r}\right)}\right]$
(D.6) $\displaystyle=\frac{n}{p}\left(\mathbb{E}_{\sigma\sim\nu_{(n\times
p)}}\left[\varphi(\sigma)\right]-\max\left(0,1-\frac{p}{n}\right)\varphi(0)\right)$
$\displaystyle=\frac{n}{p}\>\mathbb{E}_{\sigma\sim\nu_{(n\times
p)}}\left[\varphi^{\prime}\left(\frac{p}{n}\sigma\right)\right]-\max\left(0,\frac{n}{p}-1\right)\varphi(0)\;.$

To sum up, for $\varphi:\mathbb{R}\mapsto\mathbb{R}$, we can use the following
representations:

$\frac{1}{p}\>\mathbb{E}_{\bm{\Lambda}}\left[\Tr{\varphi\left(\frac{1}{n}\bm{\Lambda}^{2}_{r}\right)}\right]=\begin{cases}\mathbb{E}_{\sigma\sim\nu_{(p\times
n)}}\left[\varphi(\sigma)\right]&\text{for }\;p\leq n\;;\\\
\frac{n}{p}\>\mathbb{E}_{\sigma\sim\nu_{(n\times
p)}}\left[\varphi\left(\frac{p}{n}\sigma\right)\right]&\text{for
}\;p>n\;.\end{cases}$ (D.7)

###  D.2 Asymptotic approximation with Marchenko-Pastur distribution

Unfortunately, to our knowledge, there is no explicit expression for
probability density of $\nu_{(n\times p)}$ which would be convenient to use
for analysis of generalization error of solutions for finite sizes. However,
for high enough values of $n,d,p$ we can approximate the results
asymptotically.

More precisely, as mentioned in Section 4.2, we consider $n,d,p\to\infty$ such
that $\nicefrac{{p}}{{n}}\to\alpha$, $\nicefrac{{d}}{{n}}\to\psi$, where
$\alpha$ and $\psi$ are fixed positive values. As $p$ must be less or equal
than $d$, $\alpha\leq\psi$. Under these conditions, as $\bm{X}_{\mathcal{A}}$
has i.i.d. standard normal elements, empirical distribution $\nu_{(p\times
n)}$ of eigenvalues of
$\frac{1}{n}\bm{X}^{\top}_{\mathcal{A}}\bm{X}_{\mathcal{A}}$ weakly converges
to well-known Marchenko-Pastur law $\nu_{\alpha}$. Its measure can be written
as

$\nu_{\alpha}(A)=\begin{cases}\left(1-\frac{1}{\alpha}\right)\mathbbm{1}\left(0\in
A\right)+\rho_{\alpha}(A)\;,&\alpha>1\\\ \rho_{\alpha}(A)\;,&0\leq\alpha\leq
1\end{cases};\;\;A\subset\mathbb{R},$ (D.8)

where $\rho_{\alpha}$ is the following measure:

$\rho_{\alpha}(\differential\sigma)=\frac{\sqrt{({\alpha_{+}}-\sigma)(\sigma-{\alpha_{-}})}}{2\pi\alpha\sigma}\mathbbm{1}(\sigma\in[\alpha_{-},\alpha_{+}])\>\differential\sigma\;,\;\;\text{where}\;\alpha_{\pm}=(1\pm\sqrt{\alpha})^{2}\;.$
(D.9)

We remark that $\rho_{\alpha}$ is not a probability measure when $\alpha>1$ as
$\rho_{\alpha}(\mathbb{R})\neq 1$. Likewise to $\nu_{(p\times n)}$,
$\nu_{(n\times p)}$ converges to $\nu_{\nicefrac{{1}}{{\alpha}}}$.

Then, we derive from Eq. (D.7) that if $\varphi:\mathbb{R}\mapsto\mathbb{R}$
is a pointwise function,

$\frac{1}{p}\>\mathbb{E}_{\bm{\Lambda}}\left[\Tr{\varphi\left(\frac{1}{n}\bm{\Lambda}^{2}_{r}\right)}\right]\xrightarrow{n,p\to\infty,\;p/n\to\alpha}\begin{cases}\mathbb{E}_{\sigma\sim\nu_{\alpha}}\left[\varphi(\sigma)\right]\;,&\alpha\leq
1;\\\
\frac{1}{\alpha}\>\mathbb{E}_{\sigma\sim\nu_{\nicefrac{{1}}{{\alpha}}}}\left[\varphi\left(\alpha\sigma\right)\right]\;,&\alpha>1.\end{cases}$
(D.10)

Now, when $\alpha\leq 1$,

$\mathbb{E}_{\sigma\sim\nu_{\alpha}}\left[\varphi(\sigma)\right]=\int\varphi(\sigma)\>\rho_{\alpha}(\differential\sigma),$
(D.11)

and when $\alpha>1$,

$\frac{1}{\alpha}\>\mathbb{E}_{\sigma\sim\nu_{\nicefrac{{1}}{{\alpha}}}}\left[\varphi\left(\alpha\sigma\right)\right]=\frac{1}{\alpha}\int\varphi(\alpha\sigma)\>\rho_{\nicefrac{{1}}{{\alpha}}}(\differential\sigma)=\frac{1}{\alpha}\int^{\left(\nicefrac{{1}}{{\alpha}}\right)_{+}}_{\left(\nicefrac{{1}}{{\alpha}}\right)_{-}}\varphi(\alpha\sigma)\frac{\sqrt{\left(\left(\nicefrac{{1}}{{\alpha}}\right)_{+}-\sigma\right)\left(\sigma-\left(\nicefrac{{1}}{{\alpha}}\right)_{-}\right)}}{2\pi\sigma/\alpha}\differential\sigma\;.$
(D.12)

We can transform the latter expression; as

$\left(\frac{1}{\alpha}\right)_{\pm}=\left(1\pm\frac{1}{\sqrt{\alpha}}\right)^{2}=\frac{1}{\alpha}(1\pm\sqrt{\alpha})^{2}=\frac{1}{\alpha}\cdot\alpha_{\pm}\;,$
(D.13)

we continue

$\frac{1}{\alpha}\>\mathbb{E}_{\sigma\sim\nu_{\nicefrac{{1}}{{\alpha}}}}\left[\varphi\left(\alpha\sigma\right)\right]=\int^{\nicefrac{{\alpha_{+}}}{{\alpha}}}_{\nicefrac{{\alpha_{-}}}{{\alpha}}}\varphi(\alpha\sigma)\frac{\sqrt{\left(\alpha_{+}-\alpha\sigma\right)\left(\alpha\sigma-\alpha_{-}\right)}}{2\pi\alpha(\alpha\sigma)}\>\alpha\,\differential\sigma=\left|\begin{array}[]{l}\zeta:=\alpha\sigma;\\\
\differential\zeta=\alpha\differential\sigma\end{array}\right|=\\\
=\int^{\alpha_{+}}_{\alpha_{-}}\varphi(\zeta)\frac{\sqrt{\left(\alpha_{+}-\zeta\right)\left(\zeta-\alpha_{-}\right)}}{2\pi\alpha\zeta}\>\differential\zeta=\int\varphi(\zeta)\>\rho_{\alpha}(\differential\zeta)\;.$
(D.14)

Combining results from Eqs. (D.11) and (D.14) with Eq. (D.10), we can state
for any $\alpha\in(0,\psi]$ that

$\frac{1}{p}\>\mathbb{E}_{\bm{\Lambda}}\left[\Tr{\varphi\left(\frac{1}{n}\bm{\Lambda}^{2}_{r}\right)}\right]\xrightarrow{n,p\to\infty,\;p/n\to\alpha}\int\varphi(\sigma)\>\rho_{\alpha}(\differential\sigma)\;.$
(D.15)

####  D.2.1 Gradient flow test error

With the findings above, we can give an approximate estimate for GF and SGF
generalization error. Starting with the former, i.e., Eq. (C.39), we can
provide asymptotic limits:

$\frac{1}{d}\Tr{\mathbb{E}_{\bm{\Lambda}}\left[e^{-\frac{2}{n}\bm{\Lambda}^{2}_{r}t}\right]}=\Big{|}\varphi(\sigma):=e^{-2\sigma
t}\Big{|}=\frac{p/n}{d/n}\cdot\frac{1}{p}\mathbb{E}_{\bm{\Lambda}}\left[\Tr{\varphi\left(\frac{\bm{\Lambda}^{2}_{r}}{n}\right)}\right]\;\underset{p/n\to\alpha\;}{\xrightarrow{n,p\to\infty}}\;\frac{\alpha}{\psi}\int
e^{-2\sigma t}\>\rho_{\alpha}(\differential\sigma)$ (D.16)

and

$\Tr{\mathbb{E}_{\bm{\Lambda}}\left[\bm{\Lambda}^{-2}_{r}\left(\mathbb{I}_{r}-e^{-\frac{1}{n}\bm{\Lambda}^{2}_{r}t}\right)^{2}\right]}=\Big{|}\varphi(\sigma):=\frac{\left(1-e^{-\sigma
t}\right)^{2}}{\sigma}\Big{|}=\\\
=\frac{p}{n}\cdot\frac{1}{p}\mathbb{E}_{\bm{\Lambda}}\left[\Tr{\varphi\left(\frac{\bm{\Lambda}^{2}_{r}}{n}\right)}\right]\underset{p/n\to\alpha\;}{\xrightarrow{n,p\to\infty}}\;\alpha\int\frac{\left(1-e^{-\sigma
t}\right)^{2}}{\sigma}\>\rho_{\alpha}(\differential\sigma)\;,$ (D.17)

which results in

$\displaystyle\lim_{\begin{subarray}{c}n,d,p\to\infty\\\
d/n\to\psi,\>p/n\to\alpha\end{subarray}}\mathcal{E}_{\mathrm{test}}^{\text{GF}}(t)$
$\displaystyle=\frac{1}{2}\Bigg{(}\frac{1}{\psi}\|\bm{\beta}-\hat{\bm{\beta}}^{0}\|^{2}\left(\max\left(0,\;\alpha-1\right)+\alpha\int
e^{-2\sigma t}\>\rho_{\alpha}(\differential\sigma)\right)+$ (D.18)
$\displaystyle+\left(\left(1-\frac{\alpha}{\psi}\right)\|\bm{\beta}\|^{2}+\mu^{2}\right)\left[1+\alpha\int\frac{\left(1-e^{-\sigma
t}\right)^{2}}{\sigma}\>\rho_{\alpha}(\differential\sigma)\right]\Bigg{)}\;;$

this coincides with Eq. (30) when $\|\bm{\beta}\|=1$ and
$\|\bm{\beta}-\hat{\bm{\beta}}^{0}\|^{2}\to 2$.

To obtain an infinite-time limit for the test error, we can see that for
$\alpha\neq 1$,

$\displaystyle\int e^{-2\sigma t}\>\rho_{\alpha}(\differential\sigma)$
$\displaystyle\leq
e^{-2{\alpha_{-}}t}\left(\int\rho_{\alpha}(\differential\sigma)\right)\xrightarrow{t\to+\infty}0\;;$
(D.19) $\displaystyle\int\frac{e^{-k\sigma
t}}{\sigma}\>\rho_{\alpha}(\differential\sigma)$ $\displaystyle\leq
e^{-k{\alpha_{-}}t}\left(\int\frac{\rho_{\alpha}(\differential\sigma)}{\sigma}\right)\xrightarrow{t\to+\infty}0\;,\;k\in\mathbb{N}\;.$

Therefore, the first integral term of Eq. (D.18) will go away, and in the
integral second term, we can set aside a part independent of $t$:

$\alpha\int\frac{\left(1-e^{-\sigma
t}\right)^{2}}{\sigma}\>\rho_{\alpha}(\differential\sigma)=\alpha\int\frac{1}{\sigma}\>\rho_{\alpha}(\differential\sigma)+\alpha\int\frac{e^{-2\sigma
t}-2e^{-\sigma t}}{\sigma}\>\rho_{\alpha}(\differential\sigma)\;,$ (D.20)

which will be the only one remaining when $t\to+\infty$ and can be simplified
as

$\alpha\int\frac{1}{\sigma}\>\rho_{\alpha}(\differential\sigma)=\alpha\cdot\int_{{\alpha_{-}}}^{{\alpha_{+}}}\frac{\sqrt{({\alpha_{+}}-\sigma)(\sigma-{\alpha_{-}})}}{2\pi\alpha\sigma^{2}}\differential\sigma=\alpha\cdot\begin{cases}\frac{1}{1-\alpha}\;,&\alpha\leq
1\;,\\\
\frac{1}{\alpha-1}-\frac{1}{\alpha}\;,&\alpha>1\;.\end{cases}=\begin{cases}\frac{1}{1-\alpha}-1\;,&\alpha\leq
1\;,\\\ \frac{1}{\alpha-1}\;,&\alpha>1\;.\end{cases}$ (D.21)

Now, as

$1+\alpha\int\frac{1}{\sigma}\>\rho_{\alpha}(\differential\sigma)=\begin{cases}\frac{1}{1-\alpha}\;,&\alpha\leq
1\;,\\\
\frac{\alpha}{\alpha-1}\;,&\alpha>1\end{cases}=\frac{1}{1-\min\left(\alpha,\nicefrac{{1}}{{\alpha}}\right)}\;,$
(D.22)

we retrieve a GF test error limit when $t\to+\infty$:

$\displaystyle\lim_{t\to+\infty}\lim_{\begin{subarray}{c}n,d,p\to\infty\\\
d/n\to\psi,\>p/n\to\alpha\end{subarray}}\mathcal{E}_{\mathrm{test}}^{\text{GF}}(t)$
$\displaystyle=\frac{1}{2}\Bigg{(}\frac{1}{\psi}\|\bm{\beta}-\hat{\bm{\beta}}^{0}\|^{2}\max\left(0,\;\alpha-1\right)+\left(\left(1-\frac{\alpha}{\psi}\right)\|\bm{\beta}\|^{2}+\mu^{2}\right)\frac{1}{1-\min\left(\alpha,\nicefrac{{1}}{{\alpha}}\right)}\Bigg{)}\;.$
(D.23)

####  D.2.2 Stochastic gradient flow test error

Now, we are going to SGF, i.e., the stochastic component additive to GF error
from Eq. (C.66). There, however, we have to deal with expressions of form
$\mathbb{E}_{\bm{\Lambda}}\left[\Tr{\varphi_{1}\left(\frac{1}{n}\bm{\Lambda}^{2}_{r}\right)}\Tr{\varphi_{2}\left(\frac{1}{n}\bm{\Lambda}^{2}_{r}\right)}\right]$
for $\varphi_{1},\varphi_{2}:\mathbb{R}\mapsto\mathbb{R}$. However, for large
$n,p$, we can assume that the (normalized) traces concentrate so that:

$\mathbb{E}_{\bm{\Lambda}}\left[\Tr{\varphi_{1}\left(\frac{1}{n}\bm{\Lambda}^{2}_{r}\right)}\Tr{\varphi_{2}\left(\frac{1}{n}\bm{\Lambda}^{2}_{r}\right)}\right]\approx\mathbb{E}_{\bm{\Lambda}}\left[\Tr{\varphi_{1}\left(\frac{1}{n}\bm{\Lambda}^{2}_{r}\right)}\right]\mathbb{E}_{\bm{\Lambda}}\left[\Tr{\varphi_{2}\left(\frac{1}{n}\bm{\Lambda}^{2}_{r}\right)}\right]\;.$
(D.24)

Then

$\displaystyle\frac{1}{p^{2}}\mathbb{E}_{\bm{\Lambda}}$
$\displaystyle\left[\Tr{\frac{1}{n}\bm{\Lambda}^{2}_{r}\cdot
e^{-\frac{2}{n}\bm{\Lambda}^{2}_{r}\tau}}\Tr{\frac{1}{n}\bm{\Lambda}^{2}_{r}\cdot
e^{-\frac{2}{n}\bm{\Lambda}^{2}_{r}(t-\tau)}}\right]$ (D.25)
$\displaystyle=\left|\varphi_{1}(\sigma):=\sigma
e^{-2\sigma\tau},\varphi_{2}(\sigma):=\sigma e^{-2\sigma(t-\tau)}\right|$
$\displaystyle\approx\frac{1}{p}\mathbb{E}_{\bm{\Lambda}}\left[\Tr{\varphi_{1}\left(\frac{1}{n}\bm{\Lambda}^{2}_{r}\right)}\right]\cdot\frac{1}{p}\mathbb{E}_{\bm{\Lambda}}\left[\Tr{\varphi_{2}\left(\frac{1}{n}\bm{\Lambda}^{2}_{r}\right)}\right]$
$\displaystyle\underset{p/n\to\alpha\;}{\xrightarrow{n,p\to\infty}}\int\sigma_{1}e^{-2\sigma_{1}\tau}\>\rho_{\alpha}(\differential\sigma_{1})\cdot\int\sigma_{2}e^{-2\sigma_{2}(t-\tau)}\>\rho_{\alpha}(\differential\sigma_{2})\;.$

Similarly, by taking
$\varphi_{1}(\sigma):=e^{-2\sigma\tau},\varphi_{2}(\sigma):=\sigma
e^{-2\sigma(t-\tau)}$, we get:

$\displaystyle\frac{1}{p^{2}}\mathbb{E}_{\bm{\Lambda}}$
$\displaystyle\left[\Tr{e^{-\frac{2}{n}\bm{\Lambda}^{2}_{r}\tau}}\Tr{\frac{1}{n}\bm{\Lambda}^{2}_{r}\cdot
e^{-\frac{2}{n}\bm{\Lambda}^{2}_{r}(t-\tau)}}\right]\underset{p/n\to\alpha\;}{\xrightarrow{n,p\to\infty}}\int
e^{-2\sigma_{1}\tau}\rho_{\alpha}(\differential\sigma_{1})\cdot\int\sigma_{2}e^{-2\sigma_{2}(t-\tau)}\rho_{\alpha}(\differential\sigma_{2})\;.$
(D.26)

We can now integrate over $\tau$ by changing the order of integration:

$\displaystyle\frac{1}{p^{2}}$
$\displaystyle\int^{t}_{0}\differential\tau\;\mathbb{E}_{\bm{\Lambda}}\left[\Tr{e^{-\frac{2}{n}\bm{\Lambda}^{2}_{r}\tau}}\Tr{\frac{1}{n}\bm{\Lambda}^{2}_{r}\cdot
e^{-\frac{2}{n}\bm{\Lambda}^{2}_{r}(t-\tau)}}\right]$ (D.27)
$\displaystyle\underset{p/n\to\alpha\;}{\xrightarrow{n,p\to\infty}}\int^{t}_{0}\differential\tau\int\sigma_{1}e^{-2\sigma_{1}\tau}\rho_{\alpha}(\differential\sigma_{1})\int\sigma_{2}e^{-2\sigma_{2}(t-\tau)}\rho_{\alpha}(\differential\sigma_{2})$
$\displaystyle=\int\sigma_{1}\>\rho_{\alpha}(\differential\sigma_{1})\int
e^{-2\sigma_{2}t}\sigma_{2}\rho_{\alpha}(\differential\sigma_{2})\int^{t}_{0}\differential\tau\>e^{-2(\sigma_{1}-\sigma_{2})\tau}$
$\displaystyle=\int\sigma_{1}\>\rho_{\alpha}(\differential\sigma_{1})\int
e^{-2\sigma_{2}t}\sigma_{2}\rho_{\alpha}(\differential\sigma_{2})\;\frac{e^{-2(\sigma_{1}-\sigma_{2})t}-1}{-2(\sigma_{1}-\sigma_{2})}$
$\displaystyle=\int\int\rho_{\alpha}(\differential\sigma_{1})\>\rho_{\alpha}(\differential\sigma_{2})\>\sigma_{1}\sigma_{2}\frac{e^{-2\sigma_{1}t}-e^{-2\sigma_{2}t}}{2(\sigma_{2}-\sigma_{1})}\;,$

In the same way:

$\displaystyle\frac{1}{p^{2}}$
$\displaystyle\int^{t}_{0}\differential\tau\;\mathbb{E}_{\bm{\Lambda}}\left[\Tr{\frac{1}{n}\bm{\Lambda}^{2}_{r}\cdot
e^{-\frac{2}{n}\bm{\Lambda}^{2}_{r}\tau}}\Tr{\frac{1}{n}\bm{\Lambda}^{2}_{r}\cdot
e^{-\frac{2}{n}\bm{\Lambda}^{2}_{r}(t-\tau)}}\right]$ (D.28)
$\displaystyle\underset{p/n\to\alpha\;}{\xrightarrow{n,p\to\infty}}\int^{t}_{0}\differential\tau\int
e^{-2\sigma_{1}\tau}\rho_{\alpha}(\differential\sigma_{1})\cdot\int\sigma_{2}e^{-2\sigma_{2}(t-\tau)}\rho_{\alpha}(\differential\sigma_{2})$
$\displaystyle=\int\>\rho_{\alpha}(\differential\sigma_{1})\int
e^{-2\sigma_{2}t}\sigma_{2}\rho_{\alpha}(\differential\sigma_{2})\int^{t}_{0}\differential\tau\>e^{-2(\sigma_{1}-\sigma_{2})\tau}$
$\displaystyle=\int\>\rho_{\alpha}(\differential\sigma_{1})\int
e^{-2\sigma_{2}t}\sigma_{2}\rho_{\alpha}(\differential\sigma_{2})\;\frac{e^{-2(\sigma_{1}-\sigma_{2})t}-1}{-2(\sigma_{1}-\sigma_{2})}$
$\displaystyle=\int\int\rho_{\alpha}(\differential\sigma_{1})\>\rho_{\alpha}(\differential\sigma_{2})\>\sigma_{2}\frac{e^{-2\sigma_{1}t}-e^{-2\sigma_{2}t}}{2(\sigma_{2}-\sigma_{1})}\;.$

Finally,
$\mathbb{E}_{\bm{\Lambda}}\left[\Tr{\mathbb{I}_{r}-e^{-\frac{2}{n}\bm{\Lambda}^{2}_{r}t}}\right]$
can be treated as seen before in Eq. (D.15):

$\frac{1}{p}\mathbb{E}_{\bm{\Lambda}}\left[\Tr{\mathbb{I}_{r}-e^{-\frac{2}{n}\bm{\Lambda}^{2}_{r}t}}\right]=\Big{|}\varphi(\sigma):=1-e^{-2\sigma
t}\Big{|}=\frac{1}{p}\mathbb{E}_{\bm{\Lambda}}\left[\Tr{\varphi\left(\frac{\bm{\Lambda}^{2}_{r}}{n}\right)}\right]\;\underset{p/n\to\alpha\;}{\xrightarrow{n,p\to\infty}}\;\int\left(1-e^{-2\sigma
t}\right)\>\rho_{\alpha}(\differential\sigma)\;.$ (D.29)

Then, if we denote

$\displaystyle F_{1}(\alpha,t)$
$\displaystyle\equiv\int\int\rho_{\alpha}(\differential\sigma_{1})\rho_{\alpha}(\differential\sigma_{2})\sigma_{1}\sigma_{2}K(t,\sigma_{1},\sigma_{2})\;,$
(D.30) $\displaystyle F_{2}(\alpha,t)$
$\displaystyle\equiv\int\int\rho_{\alpha}(\differential\sigma_{1})\rho_{\alpha}(\differential\sigma_{2})\sigma_{2}K(t,\sigma_{1},\sigma_{2})$
$\displaystyle=\frac{1}{2}\int\int\rho_{\alpha}(\differential\sigma_{1})\rho_{\alpha}(\differential\sigma_{2})(\sigma_{1}+\sigma_{2})K(t,\sigma_{1},\sigma_{2})\;,$
(D.31) $\displaystyle K(t,\sigma_{1},\sigma_{2})$
$\displaystyle\equiv\frac{e^{-2\sigma_{1}t}-e^{-2\sigma_{2}t}}{2(\sigma_{2}-\sigma_{1})}\;,$
(D.32)

we obtain an asymptotic result for the stochastic component of SGF error:

$\displaystyle\lim_{\begin{subarray}{c}n,d,p\to\infty\\\
d/n\to\psi,\>p/n\to\alpha\end{subarray}}$
$\displaystyle\frac{1}{n}\mathbb{E}_{\mathcal{A};\bm{X},\bm{y}}\left[\Tr{\boldsymbol{\mathscr{C}}(t)}\right]=\lim_{\begin{subarray}{c}n,d,p\to\infty\\\
d/n\to\psi,\>p/n\to\alpha\end{subarray}}\Bigg{\\{}\frac{p^{2}}{dn}\cdot\|\bm{\beta}-\hat{\bm{\beta}}^{0}\|^{2}\cdot
F_{1}(\alpha,t)+$ (D.33)
$\displaystyle+\left(\left(1-\frac{p}{d}\right)\|\bm{\beta}\|^{2}+\mu^{2}\right)\cdot\left(\frac{p^{2}}{n^{2}}F_{2}(\alpha,t)+\frac{1}{2}\max\left(0,1-\frac{p}{n}\right)\cdot\frac{p}{n}\int\left(1-e^{-2\sigma
t}\right)\>\rho_{\alpha}(\differential\sigma)\right)\Bigg{\\}}$
$\displaystyle=\alpha\Bigg{[}\frac{\alpha}{\psi}\cdot\|\bm{\beta}-\hat{\bm{\beta}}^{0}\|^{2}\cdot
F_{1}(\alpha,t)+\left(\left(1-\frac{\alpha}{\psi}\right)\|\bm{\beta}\|^{2}+\mu^{2}\right)\cdot$
$\displaystyle\qquad\cdot\left(\alpha\cdot
F_{2}(\alpha,t)+\max\left(0,1-\alpha\right)\cdot\int\frac{\left(1-e^{-2\sigma
t}\right)}{2}\>\rho_{\alpha}(\differential\sigma)\right)\Bigg{]}\;,$

or, with scaling

$\frac{\gamma}{2}=\frac{\gamma^{\prime}}{2d}=\frac{\gamma^{\prime}}{2\psi
n}\;,$ (D.34)

the expression is

$\displaystyle\lim_{\begin{subarray}{c}n,d,p\to\infty\\\
d/n\to\psi,\>p/n\to\alpha\end{subarray}}\frac{\gamma}{2}\mathbb{E}_{\mathcal{A};\bm{X},\bm{y}}\left[\Tr{\boldsymbol{\mathscr{C}}(t)}\right]$
$\displaystyle=\frac{\gamma^{\prime}}{2}\cdot\frac{\alpha}{\psi}\Bigg{[}\frac{\alpha}{\psi}\cdot\|\bm{\beta}-\hat{\bm{\beta}}^{0}\|^{2}\cdot
F_{1}(\alpha,t)+\left(\left(1-\frac{\alpha}{\psi}\right)\|\bm{\beta}\|^{2}+\mu^{2}\right)\cdot$
(D.35) $\displaystyle\cdot\left(\alpha\cdot
F_{2}(\alpha,t)+\max\left(0,1-\alpha\right)\cdot\int\frac{\left(1-e^{-2\sigma
t}\right)}{2}\>\rho_{\alpha}(\differential\sigma)\right)\Bigg{]}\;,$

which matches Eq. (31) when $\|\bm{\beta}\|=1$ and
$\|\bm{\beta}-\hat{\bm{\beta}}^{0}\|^{2}\to 2$.

Now, we obtain an infinite time limit. With argument similar to Eq. (D.19), we
can write for $\alpha\neq 1$:

$\lim_{t\to+\infty}F_{1}(\alpha,t)=0,\lim_{t\to+\infty}F_{2}(\alpha,t)=0\;;$
(D.36)

besides, from Eq. (D.8) we can see:

$\int\>\rho_{\alpha}(\differential\sigma)=\min\left(1,\frac{1}{\alpha}\right)\;,$
(D.37)

and as

$\max\left(0,1-\alpha\right)\cdot\min\left(1,\frac{1}{\alpha}\right)=\max\left(0,1-\alpha\right),$
(D.38)

the infinite time limit of difference between test errors of SGF and GF is:

$\displaystyle\lim_{t\to+\infty}\lim_{\begin{subarray}{c}n,d,p\to\infty\\\
d/n\to\psi,\>p/n\to\alpha\end{subarray}}\frac{\gamma}{2}\mathbb{E}_{\mathcal{A};\bm{X},\bm{y}}\left[\Tr{\boldsymbol{\mathscr{C}}(t)}\right]$
$\displaystyle=\frac{\gamma^{\prime}}{4}\cdot\frac{\alpha}{\psi}\left(\left(1-\frac{\alpha}{\psi}\right)\|\bm{\beta}\|^{2}+\mu^{2}\right)\cdot\max\left(0,1-\alpha\right)\;.$
(D.39)

##  Appendix E Additional numerics for the weak features model

##### Gradient flow –

Plots for the test risk of the deterministic gradient flow estimator are found
in Fig. 5. Fig. 5 focuses on the risk dependence on $\alpha$. One can see a
limiting double descent picture (with degenerate first descent) described in
[2]. Besides, our derivations, particularly Eq. (30), also allow to see the
emergence of the double descent with time. This is illustrated by Fig. 5 which
depicts the time evolution of the test risk for the GF estimator. We observe
that under our choice of model parameters early stopping is beneficial for
most values of $\alpha$. The gradient descent simulations come very close to
our prediction. The discrepancy between the theoretical and empirical
predictions is slightly more pronounced for values of $\alpha$ close to $1$,
which we hypothesize to be caused by a lower rate of convergence of the
empirical distribution of eigenvalues of $\bm{\Lambda}^{2}_{r}/n$ to
Marchenko-Pastur distribution for such $\alpha$’s.

Figure 5: Plots depicting $\mathcal{E}_{\mathrm{test}}^{\text{GF}}(t)$ for
$\psi=2.5$. Solid lines represent theoretical asymptotic estimation. Markers
on 5 represent the results of numerical simulations of GD (averaged over
$1000$ different random subsets $\mathcal{A}$). Simulation parameters:
$d=1000$, $\gamma=10^{-3}$; vectors $\bm{\beta}$, $\bm{\beta}_{0}$ are taken
at random on the unit $1000$-dimensional sphere and here
$\norm{\bm{\beta}-\bm{\beta}_{0}}^{2}\approx 2.11$

##### Difference between SGF and GF –

We illustrate the time-evolution of the difference
$\mathcal{E}_{\mathrm{test}}^{\text{SGF}}-\mathcal{E}_{\mathrm{test}}^{\text{GF}}$
and its numerical simulation counterpart
$\mathcal{E}_{\mathrm{test}}^{\text{SGD}}-\mathcal{E}_{\mathrm{test}}^{\text{GD}}$,
as well as finite-size effects. These differences are presented in Fig. 6 as a
function of $\nicefrac{{t}}{{\gamma}}$ for different values of $\alpha$, below
and above the interpolation threshold. Note that $t/\gamma$ can be interpreted
as the number of iterations in gradient descent. Fig. 6(a) depicts the
comparison with simulations for $d=100$ and Fig. 6(b) with simulations for
$d=1000$.

(a) Simulations with $d=100$

(b) Simulations with $d=1000$

Figure 6: Time-evolution of
$\mathcal{E}_{\mathrm{test}}^{\text{SGF}}-\mathcal{E}_{\mathrm{test}}^{\text{GF}}$
with $\psi=2.5$ for different values of $\alpha$. Markers represent
simulations while lines represent the theoretical predictions. The learning
rate is scaled as $\gamma=\nicefrac{{1}}{{d}}$. Vectors $\bm{\beta}$,
$\bm{\beta}_{0}$ are taken at random on the unit $d$-dimensional sphere. Here
$\norm{\bm{\beta}-\bm{\beta}_{0}}^{2}\approx 1.78$ for $d=100$ and
$\norm{\bm{\beta}-\bm{\beta}_{0}}^{2}\approx 2.11$ for $d=1000$.

We note pronounced finite-size effects when comparing Figs. 6(a) (with
$d=100$) and Figs. 6(b) (with $d=1000$), particularly below the interpolation
threshold and high values of $\nicefrac{{t}}{{\gamma}}$.

Additionally, for finite times, we observe that the theoretical results are
less accurate for times of order $t\sim 1$ (corresponding to roughly
$1/\gamma=d$ GD iterations). That is already apparent from the ‘red curve’ in
Fig. 3 in the main text. To further investigate this point, we define
$\Delta\mathcal{E}_{\mathrm{test}}^{\text{Theory}}\equiv\mathcal{E}_{\mathrm{test}}^{\text{SGF}}-\mathcal{E}_{\mathrm{test}}^{\text{GF}}$
and
$\Delta\mathcal{E}_{\mathrm{test}}^{\text{Simul}}\equiv\mathcal{E}_{\mathrm{test}}^{\text{SGD}}-\mathcal{E}_{\mathrm{test}}^{\text{GD}}$,
and compare the difference between
$\Delta\mathcal{E}_{\mathrm{test}}^{\text{Theory}}-\Delta\mathcal{E}_{\mathrm{test}}^{\text{Simul}}$
(for the same setting as that of Fig. 6). These differences are presented in
Fig. 7 for different values of $\alpha$, and with $d=100$, $d=1000$.

Figure 7: Time-evolution of the difference between the theory and simulation
($d=100,1000$ and $\psi=2.5$) results for
$\Delta\mathcal{E}_{\mathrm{test}}^{\text{Theory}}-\Delta\mathcal{E}_{\mathrm{test}}^{\text{Simul}}$
(defined in the text) for different values of $\alpha$, below and above the
interpolation threshold. The time scaling is adjusted according to the fine
size simulation: $\gamma_{d}=\nicefrac{{1}}{{d}}$.

For values of $\alpha$ well below the interpolation threshold, the finite size
effects are clearly visible in the whole time evolution and go away as $d$
increases. Above the threshold, the discrepancy is more pronounced around
$t\sim 1$ and there is no clear evidence that this is a finite size effect. It
remains to be seen if better continuous time modeling (for example second-
order SDE modeling) would be tractable and make the discrepancy disappear.

## References

  * [1] M. Belkin, D. Hsu, S. Ma, and S. Mandal, “Reconciling modern machine-learning practice and the classical bias-variance trade-off,” _Proceedings of the National Academy of Sciences_ , vol. 116, no. 32, pp. 15 849–15 854, 2019.
  * [2] M. Belkin, D. Hsu, and J. Xu, “Two models of double descent for weak features,” _SIAM Journal on Mathematics of Data Science_ , vol. 2, no. 4, pp. 1167–1180, 2020.
  * [3] M. Belkin, “Fit without fear: remarkable mathematical phenomena of deep learning through the prism of interpolation,” _Acta Numerica_ , vol. 30, p. 203–248, 2021.
  * [4] Q. Li, C. Tai, and W. E, “Stochastic modified equations and dynamics of stochastic gradient algorithms i: Mathematical foundations,” _Journal of Machine Learning Research_ , vol. 20, no. 40, pp. 1–47, 2019.
  * [5] L. Breiman and D. Freedman, “How many variables should be entered in a regression equation?” _Journal of the American Statistical Association_ , vol. 78, no. 381, pp. 131–136, 1983.
  * [6] H. J. Kushner and G. G. Yin, _Stochastic Approximation and Recursive Algorithms and Applications_ , 2nd ed., ser. tochastic Modelling and Applied Probability. Springer-Verlag, 2003.
  * [7] S. Mandt, M. Hoffman, and D. Blei, “A variational analysis of stochastic gradient algorithms,” in _Proceedings of The 33rd International Conference on Machine Learning_ , ser. Proceedings of Machine Learning Research, vol. 48. New York, New York, USA: PMLR, 20–22 Jun 2016, pp. 354–363.
  * [8] S. Mandt, t, M. D. Hoffman, and D. M. Blei, “Stochastic gradient descent as approximate Bayesian inference,” _Journal of Machine Learning Research_ , vol. 18, no. 134, pp. 1–35, 2017.
  * [9] S. Jastrzębski, Z. Kenton, D. Arpit, N. Ballas, A. Fischer, Y. Bengio, and A. Storkey, “Width of minima reached by stochastic gradient descent is influenced by learning rate to batch size ratio,” in _Artificial Neural Networks and Machine Learning – ICANN 2018_. Cham: Springer International Publishing, 2018, pp. 392–402.
  * [10] J. Fan, W. Gong, C. J. Li, and Q. Sun, “Statistical sparse online regression: A diffusion approximation perspective,” in _Proceedings of the Twenty-First International Conference on Artificial Intelligence and Statistics_ , ser. Proceedings of Machine Learning Research, vol. 84. PMLR, 09–11 Apr 2018, pp. 1017–1026.
  * [11] Y. Wang and S. Wu, “Asymptotic analysis via stochastic differential equations of gradient descent algorithms in statistical and computational paradigms,” _Journal of Machine Learning Research_ , vol. 21, no. 199, pp. 1–103, 2020.
  * [12] A. Ali, E. Dobriban, and R. Tibshirani, “The implicit regularization of stochastic gradient flow for least squares,” in _Proceedings of the 37th International Conference on Machine Learning_ , ser. Proceedings of Machine Learning Research, vol. 119. PMLR, 13–18 Jul 2020, pp. 233–244.
  * [13] S. Mandt and D. M. Blei, “Continuous-time limit of stochastic gradient descent revisited,” 2015.
  * [14] Q. Li, C. Tai, and W. E, “Dynamics of stochastic gradient algorithms,” 2015.
  * [15] R. Warming and B. Hyett, “The modified equation approach to the stability and accuracy analysis of finite-difference methods,” _Journal of Computational Physics_ , vol. 14, no. 2, pp. 159–179, 1974.
  * [16] Q. Li, C. Tai, and W. E, “Stochastic modified equations and adaptive stochastic gradient algorithms,” in _Proceedings of the 34th International Conference on Machine Learning_ , ser. Proceedings of Machine Learning Research, vol. 70. PMLR, 06–11 Aug 2017, pp. 2101–2110.
  * [17] C. Paquette, E. Paquette, B. Adlam, and J. Pennington, “Homogenization of SGD in high-dimensions: Exact dynamics and generalization properties,” 2022.
  * [18] ——, “Implicit regularization or implicit conditioning? Exact risk trajectories of SGD in high dimensions,” in _Advances in Neural Information Processing Systems_ , vol. 35, 2022, pp. 35 984–35 999.
  * [19] F. Mignacco, F. Krzakala, P. Urbani, and L. Zdeborová, “Dynamical mean-field theory for stochastic gradient descent in Gaussian mixture classification,” in _Advances in Neural Information Processing Systems_ , vol. 33. Curran Associates, Inc., 2020, pp. 9540–9550.
  * [20] F. Mignacco and P. Urbani, “The effective noise of stochastic gradient descent,” _Journal of Statistical Mechanics: Theory and Experiment_ , vol. 2022, no. 8, p. 083405, aug 2022.
  * [21] L. Arnaboldi, F. Krzakala, B. Loureiro, and L. Stephan, “Escaping mediocrity: how two-layer networks learn hard single-index models with SGD,” 2023.
  * [22] M. I. Freidlin and A. D. Wentzell, _Random Perturbations of Dynamical Systems_ , ser. Grundlehren der mathematischen Wissenschaften. Springer Berlin Heidelberg, 2012.
  * [23] A. Dembo and O. Zeitouni, _Large Deviations Techniques and Applications_. Springer Berlin Heidelberg, 2010.
  * [24] A. Bodin and N. Macris, “Model, sample, and epoch-wise descents: exact solution of gradient flow in the random feature model,” in _Advances in Neural Information Processing Systems_ , vol. 34, 2021, pp. 21 605–21 617.
  * [25] ——, “Gradient flow in the Gaussian covariate model: exact solution of learning curves and multiple descent structures,” 2022.
  * [26] S. Pesme, L. Pillaud-Vivien, and N. Flammarion, “Implicit bias of SGD for diagonal linear networks: a provable benefit of stochasticity,” in _Advances in Neural Information Processing Systems_ , vol. 34, 2021, pp. 29 218–29 230.
  * [27] S. Pesme and N. Flammarion, “Saddle-to-saddle dynamics in diagonal linear networks,” 2023.
  * [28] T. A. de Pirey, L. F. Cugliandolo, V. Lecomte, and F. van Wijland, “Path integrals and stochastic calculus,” _Advances in Physics_ , vol. 0, no. 0, pp. 1–85, 2023.
  * [29] F. Hildebrandt and S. Rœlly, “Pinned diffusions and Markov bridges,” _Journal of Theoretical Probability_ , vol. 33, no. 2, pp. 906–917, Jun 2020.
  * [30] R. Veiga, L. Stephan, B. Loureiro, F. Krzakala, and L. Zdeborová, “Phase diagram of stochastic gradient descent in high-dimensional two-layer neural networks,” in _Advances in Neural Information Processing Systems_ , vol. 35, 2022, pp. 23 244–23 255.
  * [31] G. Ben Arous, R. Gheissari, and A. Jagannath, “High-dimensional limit theorems for SGD: Effective dynamics and critical scaling,” in _Advances in Neural Information Processing Systems_ , vol. 35, 2022, pp. 25 349–25 362.
  * [32] A. L. Fetter and J. D. Walecka, _Theoretical Mechanics of Particles and Continua_ , ser. Dover Books on Physics. Mineola, NY: Dover Publications, dec 2003.
  * [33] S. Weinberg, _The Quantum Theory of Fields_. Cambridge University Press, 1995, vol. 1.
  * [34] J. J. Sakurai and J. Napolitano, _Modern Quantum Mechanics_ , 3rd ed. Cambridge University Press, 2020.
  * [35] F. J. Dyson, “The $s$ matrix in quantum electrodynamics,” _Phys. Rev._ , vol. 75, pp. 1736–1755, Jun 1949.