# Rationally Extended Harmonic Oscillator potential, Isospectral Family and
the Uncertainity Relations

Rajesh Kumara111e-mail address: kr.rajesh.phy@gmail.com(R.K), Rajesh Kumar
Yadavb222e-mail address: rajeshastrophysics@gmail.com(R.K.Y) and Avinash
Kharec333e-mail address<EMAIL_ADDRESS>(A.K)

###### Abstract

We consider the rationally extended harmonic oscillator potential which is
isospectral to the conventional one and whose solutions are associated with
the exceptional, $X_{m}$\- Hermite polynomials and discuss its various
important properties for different even codimension of $m$. The uncertainty
relations are obtained for different $m$ and it is shown that for the ground
state, the uncertainity increases as $m$ increases. A one parameter
$(\lambda)$ family of exactly solvable isospectral potential corresponding to
this extended harmonic oscillator potential is obtained. Special cases
corresponding to the $\lambda=0$ and $\lambda=-1$, which give the Pursey and
the Abhram-Moses potentials respectively, are discussed. The uncertainty
relations for the entire isospectral family of potentials for different $m$
and $\lambda$ are also calculated.

$~{}^{a}$Department of Physics, Model College, Dumka-814101, India.
$~{}^{b}$Department of Physics, S. K. M. University, Dumka-814110, India.
$~{}^{c}$Department of Physics, Savitribai Phule Pune University, Pune-411007,
India.

##  1 Introduction

The idea of Supersymmetric Quantum Mechanics(SQM) [1] is not only useful in
solving the quantum mechanical potential problems but has also opened the
scope for discovering new exactly solvable potentials. These potentials have
applications in diverse areas like inverse scattering [2, 3], soliton theory
[4, 5], etc. This sparked a race among researchers to search for a family of
isospectral potentials [6, 7, 8, 9]. To accomplish this purpose, several
methods were developed like Darboux transformation [10], Darboux Crum Krein
Adler Transformation [11], SQM [12, 13], etc. Popular among them was the SQM
approach due to its simplicity and it was shown using this approach that for
any 1-D potential with atleast one bound state, one can always construct one
continuous parameter family of strictly isospectral potentials.

The discovery of the $X_{m}$-exceptional orthogonal polynomials (EOPs) [14,
15, 16] paved the path for discovering new rationally extended shape invariant
potentials whose eigenfunctions are in terms of these EOPs. Various properties
of these potentials have been studied in detail in [17, 18, 19, 20, 21, 22,
23, 24, 25, 26, 27, 28, 29] and the references therein. After the discovery of
the exceptional Hermite polynomials [30], Fellows and Smith [31] discovered
rationally extended one dimensional harmonic oscillator potentials. Their work
has been further extended using the SQM approach [32].

The one dimensional harmonic oscillator potential is one of the most important
potential having numerous applications. However, so far as we are aware off,
there has not been much progress in studying the various properties of the
rationally extended family of harmonic oscillator (REHO) potentials. The
purpose of this paper is to take a step in that direction. Firstly, we
calculate the Heisenberg uncertainty relation $\Delta x\Delta p$ for the REHO
potentials. Further, we follow the idea of SQM [1], and generate a one
parameter $(\lambda)$ family of rationally extended strictly isospectral
potentials including the corresponding Pursey and the Abrahm-Mosses potentials
and obtain their eigenfunctions explicitly in terms of the $X_{m}$-Hermite
EOPs. We calculate the Heisenberg uncertainty relations for the one parameter
family of rationally extended isospectral potentials (including the
corresponding Pursey and the Abrahm-Mosses potentials) for different $m$ and
$\lambda$.

The plan of the paper is as follows: In Sec. $2$, we briefly discuss the
formulation of SQM. In Sec. $3$, we summarise the known important results
related to the rationally extended harmonic oscillator potentials. A one
parameter $\lambda$ family of isospectral potentials (including the
corresponding Pursey and Abrahm-Mosses potentials) are obtained in Sec. $4$
for any even integral $m$. In Sec. $5$, we follow the results discussed in
Sec. $3$ and Sec. $4$ and calculate the Heisenberg uncertainty relations for
REHO and their isospectral family of potentials (including the corresponding
Pursey and Abrahm-Mosses potentials). Finally, we summarize our results and
mention some open possible problems in Sec. $6$.

##  2 SQM Formalism

In SQM approach, one considers the Hamiltonian (in the units $\hbar=2m=1$)

$H^{-}=-\frac{d^{2}}{dx^{2}}+V^{-}(x)-\epsilon\;$ (1)

where $\epsilon$ is the factorization energy. By assuming the ground state
energy of this Hamiltonian $E^{-}_{0}=0$, we factorize $H^{-}$ in terms of $A$
and $A^{\dagger}$ as

$H^{-}=A^{\dagger}A\;$ (2)

with

$A=\frac{d}{dx}+W(x),\qquad A^{\dagger}=-\frac{d}{dx}+W(x).$ (3)

Here $W(x)$ is known as superpotential which is expressed in term of the
ground state eigenfunction as $W(x)=-\ln[\psi^{-}_{0}(x)]^{\prime}$. In this
way, another set of Hamiltonian can easily be constructed by reversing the
order of the operators $A$ and $A^{\dagger}$ i.e.,

$H^{+}=AA^{\dagger}=-\frac{d^{2}}{dx^{2}}+V^{+}(x)-\epsilon\;.$ (4)

Thus, the partner potentials $V^{\mp}(x)$ in term of superpotential are given
by

$V^{\mp}(x)=W(x)^{2}\mp W(x)^{\prime}+\epsilon\;.$ (5)

Here a prime denotes a derivative with respect to $x$. The precise
relationship between the energies and the eigenfunctions of the partner
Hamiltonians are

$E^{-}_{n+1}=E^{+}_{n}\;>0,\qquad n=0,1,2,\cdots,$ (6)
$\psi^{-}_{n+1}(x)=\sqrt{\frac{1}{E^{+}_{n}}}A^{\dagger}\psi^{+}_{n}(x),\qquad\psi^{+}_{n}(x)=\sqrt{\frac{1}{E^{-}_{n+1}}}A\psi^{-}_{n+1}(x).$
(7)

The ground state eigenfunction $\psi^{-}_{0}(x)$ is obtained by solving the
differential equation,

$A\psi^{-}_{0}(x)=0.$ (8)

One parameter family of isospectral potentials are obtained by redefining the
form of the superpotential

$\hat{W}=W(x)+\phi(x),$ (9)

and by assuming the uniqueness of the partner potential $V^{+}(x)$ i.e.,

$V^{+}(x)=\hat{W}(x)^{2}+\hat{W}(x)^{\prime}+\epsilon=W(x)^{2}+W(x)^{\prime}+\epsilon,$

which gives

$\phi^{2}(x)+2W\phi+\phi^{\prime}(x)=0.$

We then find that on substituting $\phi(x)=y^{-1}(x)$, the above equation
satisfies the Bernoulli equation

$y^{\prime}(x)=1+2W(x)y(x),$

whose solution is

$\phi(x)=\frac{d}{dx}\ln\left[\mathcal{I}(x)+\lambda\right].$

Here
$\mathcal{I}(x)=\int^{x}_{\infty}\psi^{-}_{0}(x^{\prime})^{2}\;dx^{\prime}$
and $\lambda$ is an integration constant.

Therefore, the potential which is strictly isospectral to $V^{-}(x)$ is given
by

$\displaystyle\hat{V}^{-}(\lambda,x)$
$\displaystyle=\hat{W}(x)^{2}-\hat{W}(x)^{\prime}+\epsilon$
$\displaystyle=V^{-}(x)-2\frac{d^{2}}{dx^{2}}\ln\left[\mathcal{I}(x)+\lambda\right]\,,$
(10)

where either $\lambda>0$ or $\lambda<-1$ so as to avoid singularity (For
details, see[1, 33]). The normalized ground state eigenfunction for the entire
family of potentials is given by

$\hat{\psi}^{-}_{0}(\lambda,x)=\sqrt{\lambda(1+\lambda)}\;\frac{\psi^{-}_{0}(x)}{\mathcal{I}(x)+\lambda}\,.$
(11)

The normalized excited states eigenfunctions can be easily calculated similar
to (7) as

$\displaystyle\hat{\psi}^{-}_{n+1}(\lambda,\;x)$
$\displaystyle=\sqrt{\frac{1}{E^{+}_{n}}}\hat{A}^{\dagger}\psi^{+}_{n}(x)=\frac{1}{E^{-}_{n+1}}\hat{A}^{\dagger}A\psi^{-}_{n+1}(x),\qquad
n=0,1,2,\cdots,$ (12) $\displaystyle\hat{A}^{\dagger}$
$\displaystyle=-\frac{d}{dx}-\frac{d}{dx}\ln\left[\frac{\psi^{-}_{0}(x)}{\mathcal{I}(x)+\lambda}\right],\qquad
A=\frac{d}{dx}-\frac{d}{dx}\ln\left[\psi^{-}_{0}(x)\right]$

and the Hamiltonian is defined similar to (1) as

$\displaystyle\hat{H}^{-}$
$\displaystyle=\hat{A}^{\dagger}\hat{A}=-\frac{d^{2}}{dx^{2}}+\hat{V}^{-}(x)-\epsilon$
(13) $\displaystyle\hat{A}$
$\displaystyle=\frac{d}{dx}-\frac{d}{dx}\ln\left[\frac{\psi^{-}_{0}(x)}{\mathcal{I}(x)+\lambda}\right]$

It is worth reminding that all these strictly isospectral family of potentials
have same partner potential $V^{+}(x)$.

In the limit $\lambda=0$ there is a loss of a bound state and the
corresponding potential is called the Pursey potential $\hat{V}^{P}(x)$. An
analogous situation occurs in the limit $\lambda=-1$ and the potential is
called the Abraham-Moses potential $\hat{V}^{AM}(x)$. The normalized
eigenfunctions of $\hat{V}^{P}(x)$ are given by

$\hat{\psi}^{P}_{n}(x)=\frac{1}{E^{-}_{n+1}}\left(-\frac{d}{dx}-\frac{d}{dx}\ln\left[\frac{\psi^{-}_{0}(x)}{\mathcal{I}(x)}\right]\right)A\psi^{-}_{n+1}(x),\qquad
n=0,1,2,\cdots,.$ (14)

Similarly, the normalized eigenfunctions of $\hat{V}^{AM}(x)$ are given by

$\hat{\psi}^{AM}_{n}(x)=\frac{1}{E^{-}_{n+1}}\left(-\frac{d}{dx}-\frac{d}{dx}\ln\left[\frac{\psi^{-}_{0}(x)}{\mathcal{I}(x)-1}\right]\right)A\psi^{-}_{n+1}(x),\qquad
n=0,1,2,\cdots,.$ (15)

The energy eigenvalues of the Pursey and the Abraham-Moses Hamiltonians
obtained by substituting $\lambda$ equal to $0$ and $-1$ respectively in (13)
has the same expressions as that of $H^{+}(x)$, i.e.

$\hat{E}^{P}_{n}=\hat{E}^{AM}_{n}=E^{+}_{n},\qquad n=0,1,2,3,\cdots$ (16)

##  3 REHO Potential

In this section, we briefly review the results obtained in [31, 32] about the
REHO potentials. These authors extended the conventional one-dimensional
harmonic oscillator potential ($V(x)=x^{2}$) using the idea of SQM and
obtained the REHO potentials valid for even co-dimension of $m=0,2,4,....$ and
are given by

$V^{-}_{m}(x)=V(x)-2\left[\frac{\mathcal{H}_{m}^{\prime\prime}}{\mathcal{H}_{m}}-\left(\frac{\mathcal{H}_{m}^{\prime}}{\mathcal{H}_{m}}\right)^{2}+1\right],$
(17)

where $\mathcal{H}_{m}(x)=(-1)^{m}H_{m}(ix)$ is pseudo-hermite polynomials and
factorization energy used in the calculation was $\epsilon=-2m-1$. The
normalized ground state eigenfunction $\psi^{-}_{0,m}(x)$ having zero
eigenvalue and the excited states eigenfunction$\psi^{-}_{n+1,m}(x)$ for
different $m$ are

$\psi^{-}_{0,m}(x)=\left(\frac{2^{m}m!}{\sqrt{\pi}}\right)^{\frac{1}{2}}\frac{e^{-\frac{x^{2}}{2}}}{\mathcal{H}_{m}(x)},$
(18)

and

$\psi^{-}_{n+1,m}(x)=\frac{1}{\sqrt{E^{+}_{n,m}\;2^{n}n!\sqrt{\pi}}}\;\frac{e^{-\frac{x^{2}}{2}}}{\mathcal{H}_{m}(x)}y^{m}_{n+1}(x)\;,\qquad
n=0,1,2...,$ (19)

respectively. Here
$y^{m}_{n+1}(x)=\left[\mathcal{H}_{m}(x)H_{n+1}(x)+\mathcal{H}_{m}(x)^{\prime}H_{n}(x)\right]$
and $n=-1,\;0,\;1,\;2,\dots$ is the Exceptional Hermite Polynomial. Note that
$y^{m}_{0}(x)=1$. The whole system $\\{y^{m}_{n+1}(x)\\}$ is the exceptional
orthogonal polynomial system, $X_{m}$, of co-dimension $m$ and is orthogonal
and complete with respect to the positive-definite measure
$\frac{e^{-x^{2}}}{\mathcal{H}_{m}(x)^{2}}$. The Hamiltonian $H^{-}_{m}$
defined similar to (1) has the energy eigenvalues $E^{-}_{n,m}$ given by

$E^{-}_{n+1,m}=2(n+m+1),\quad n=0,1,2,\cdots,\quad\text{and }E^{-}_{0,m}=0.$
(20)

It is seen that the difference in energy eigenvalues is $2(m+1)$ units between
ground state and first excited state and 2 units between any successive
excited states. Therefore energy spectra is equidistant only for $m=0$. Note
that $V^{-}_{m}(x)$ is singular at $x=0$ for odd $m$ and therefore $m$ is
restricted to positive even integers only.

It is worth noting that the complete set of eigenfunctions for the $m=0$ case,
i.e. the one dimensional harmonic oscillator, can be reduced to a single
formula containing ground state eigenfunction and excited state eigenfunction
given by

$\Psi_{\nu}(x)=\frac{1}{\sqrt{2^{\nu}\nu!\sqrt{\pi}}}e^{-\frac{x^{2}}{2}}H_{\nu}(x),\qquad\nu=0,\;1,\;2,\cdots\,.$

The plot of the ground, first and the second excited state eigenfunctions as
well as the potential versus position for $m=0,\;m=2\text{ and }m=4$ are given
in Fig-1.a ,Fig-1.b and Fig-1.c respectively. It is interesting to note from
these figures that as $m$ increases, the eigenfunctions and the potential well
becomes sharper. In Table $1$ we have given expressions for the potential
$V^{-}_{m}(x)$ as well as the ground and the excited state eigenfunctions in
case $m=0,2,4$. Expressions for exceptional Hermite polynomials $y^{m}_{n+1}$
are given in Table $2$ in case $n=0,1,2$ and $m=0,2,4$.

The superpotential $W(x)$ corresponding to the REHO potential is easily
obtained from the ground state eigenfunctions $\psi^{-}_{0,m}(x)$ of
$V^{-}_{m}(x)$ as

$\displaystyle W(x)$ $\displaystyle=$
$\displaystyle-\ln[\psi^{-}_{0,m}(x)]^{\prime}$ (21) $\displaystyle=$
$\displaystyle x+\frac{\mathcal{H}_{m}(x)^{\prime}}{\mathcal{H}_{m}(x)}.$

The energy eigenvalues of the partner Hamiltonians $H^{\mp}(x)$, defined using
(1) and (4), are given by

$\displaystyle E^{-}_{n+1,m}$ $\displaystyle=2(n+m+1),\quad
n=0,1,2,\cdots,\quad\text{with}\quad E^{-}_{0,m}=0.$ (22) $\displaystyle
E^{+}_{n,m}$ $\displaystyle=2(n+m+1),\quad n=0,1,2,\cdots$ (23)

m |  $V^{-}_{m}(x)$ |  $\psi^{-}_{0,m}(x)$ | $\psi^{-}_{n+1,m}(x),\quad n=0,1,2\cdots\quad$
---|---|---|---
0 |  $x^{2}-2$ |  $\frac{1}{\sqrt[4]{\pi}}e^{-\frac{x^{2}}{2}}$ | $\frac{1}{\sqrt{2(n+1)2^{n}n!\sqrt{\pi}}}e^{-\frac{x^{2}}{2}}y^{0}_{n+1}(x)$
2 |  $x^{2}-2+\frac{8\left(2x^{2}-1\right)}{\left(2x^{2}+1\right)^{2}}$ |  $\frac{2\sqrt{2}}{\sqrt[4]{\pi}}\frac{e^{-\frac{x^{2}}{2}}}{4x^{2}+2}$ | $\frac{1}{\sqrt{2(n+3)2^{n}n!\sqrt{\pi}}}\frac{e^{-\frac{x^{2}}{2}}}{4x^{2}+2}y^{2}_{n+1}(x)$
4 |  $x^{2}-2+\frac{16\left(8x^{6}+12x^{4}+18x^{2}-9\right)}{\left(4\left(x^{2}+3\right)x^{2}+3\right)^{2}}$ |  $\frac{8\sqrt{6}}{\sqrt[4]{\pi}}\frac{e^{-\frac{x^{2}}{2}}}{16x^{4}+48x^{2}+12}$ | $\frac{1}{\sqrt{2(n+5)2^{n}n!\sqrt{\pi}}}\frac{e^{-\frac{x^{2}}{2}}}{16x^{4}+48x^{2}+12}y^{4}_{n+1}(x)$
Table 1: Rationally extended harmonic oscillator potential $V^{-}_{m}(x)$, its
ground and excited state wavefunctions for $m=0,2$ and $4$.

(a) m=0

(b) m=2

(c) m=4

Figure 1: Plots of potentials $V^{-}_{m}(x)$ and eigenfunction
$\psi^{-}_{n+1,m}(x)$ as a function of $x$ for $m=0,\;2\text{ and }4$.
Potentials are shown in black color.

(a) Plot of $\hat{V}^{-}_{0}(\lambda,x)$ as a function of $x$ for positive
$\lambda$.

(b) Plot of $\hat{V}^{-}_{0}(\lambda,x)$ as a function of $x$ for negative
$\lambda$.

(c) Plot of Pursey $\hat{V}^{-}_{0}(0,x)$, AM $\hat{V}^{-}_{0}(-1,x)$ and
$V^{+}(x)$ potential as a function of $x$

(d) Plot of Ground-state wavefunction $\hat{\psi}^{-}_{0,0}(\lambda,x)$ as a
function of $x$ for various positive $\lambda$.

Figure 2: Plot of isospectral potential $\hat{V}^{-}_{0}(\lambda,x)$ and its
ground state eigenfunction $\hat{\psi}^{-}_{0,0}(\lambda,x)$ as a function of
$x$ for various $\lambda$ when $m=0$.

(a) Plot of $\hat{V}^{-}_{2}(\lambda,x)$ as a function of $x$ for positive
$\lambda$.

(b) Plot of $\hat{V}^{-}_{2}(\lambda,x)$ as a function of $x$ for negative
$\lambda$.

(c) Plot of Pursey $\hat{V}^{-}_{2}(0,x)$, AM $\hat{V}^{-}_{2}(-1,x)$ and
$V^{+}(x)$ potential as a function of $x$

(d) Plot of Ground-state wavefunction $\hat{\psi}^{-}_{0,2}(\lambda,x)$ as a
function of $x$ for various positive $\lambda$.

Figure 3: Plot of isospectral potential $\hat{V}^{-}_{2}(\lambda,x)$ and its
ground state eigenfunction $\hat{\psi}^{-}_{0,2}(\lambda,x)$ as a function of
$x$ for various $\lambda$ when $m=2$.

(a) Plot of $\hat{V}^{-}_{4}(\lambda,x)$ as a function of $x$ for positive
$\lambda$.

(b) Plot of $\hat{V}^{-}_{4}(\lambda,x)$ as a function of $x$ for negative
$\lambda$.

(c) Plot of Pursey $\hat{V}^{-}_{4}(0,x)$, AM $\hat{V}^{-}_{4}(-1,x)$ and
$V^{+}(x)$ potential as a function of $x$

(d) Plot of Ground-state wavefunction $\hat{\psi}^{-}_{0,4}(\lambda,x)$ as a
function of $x$ for various positive $\lambda$.

Figure 4: Plot of isospectral potential $\hat{V}^{-}_{4}(\lambda,x)$ and its
ground state eigenfunction $\hat{\psi}^{-}_{0,4}(\lambda,x)$ as a function of
$x$ for various $\lambda$ when $m=4$.

##  4 One parameter family of REHO potentials

The One parameter ($\lambda$) family of strictly isospectral potentials
corresponding to $V^{-}_{m}(x)$ are easily obtained using (11-12) as

$\hat{V}^{-}_{m}(\lambda,x)=V^{-}_{m}(x)-2\frac{d^{2}}{dx^{2}}\ln\left[\mathcal{I}_{m}(x)+\lambda\right],$
(24)

where the integral $\mathcal{I}_{m}(x)$ is calculated using (18) as

$\mathcal{I}_{m}(x)=\left(\frac{2^{m}m!}{\sqrt{\pi}}\right)\int^{x}_{-\infty}\left[\frac{e^{-\frac{{x^{\prime}}^{2}}{2}}}{\mathcal{H}_{m}(x^{\prime})}\right]^{2}dx^{\prime}.$
(25)

The expressions for $\mathcal{I}_{m}(x)$ and $\hat{V}^{-}_{m}(\lambda,x)$ for
$m$ equal to $0,\;2\text{ and }4$ are given in table-2 and table-3
respectively in terms of the error function $\text{erf}(x)$ defined as

$\text{erf}(x)=1-\text{erfc}(x),\qquad\text{erfc}(x)=\frac{2}{\sqrt{\pi}}\int^{\infty}_{x}e^{-t^{2}}dt\,.$

The normalized ground state wave function $\hat{\psi}^{-}_{0,m}(\lambda,x)$ is
obtained using (11), (18) and (25) as

$\hat{\psi}^{-}_{0,m}(\lambda,x)=\sqrt{\lambda(1+\lambda)}\;\frac{\psi^{-}_{0,m}(x)}{\mathcal{I}_{m}(x)+\lambda}\,.$
(26)

m |  $y^{m}_{n+1}(x),\qquad n=0,1,2\cdots$ |  $\mathcal{I}_{m}(x)$
---|---|---
0 |  $H_{n+1}(x)$ |  $\frac{1}{2}(\text{erf}(x)+1)$
2 |  $2\left(2x^{2}+1\right)H_{n+1}(x)+8xH_{n}(x)$ |  $\frac{1}{2}\left(\text{erf}(x)+\frac{2e^{-x^{2}}x}{\sqrt{\pi}\left(2x^{2}+1\right)}+1\right)$
4 |  $4\left(4x^{4}+12x^{2}+3\right)H_{n+1}(x)+\left(64x^{3}+96x\right)H_{n}(x)$ |  $\frac{1}{2}\left(\text{erf}(x)+\frac{2e^{-x^{2}}x\left(2x^{2}+5\right)}{\sqrt{\pi}\left(4\left(x^{2}+3\right)x^{2}+3\right)}+1\right)$
Table 2:  Exceptional Hermite polynomials $y^{m}_{n+1}$ and $\mathcal{I}_{m}(x)$ for different $m$. m |  $\hat{V}^{-}_{m}(\lambda,x)$
---|---
0 |  $x^{2}-2+\frac{e^{-2x^{2}}\left(8\sqrt{\pi}e^{x^{2}}x(\text{erf}(x)+2\lambda+1)+8\right)}{\pi(\text{erf}(x)+2\lambda+1)^{2}}$
2 |  $x^{2}-2+\frac{8\left(\pi e^{2x^{2}}\left(2x^{2}-1\right)(\text{erf}(x)+2\lambda+1)^{2}+6\sqrt{\pi}e^{x^{2}}x(\text{erf}(x)+2\lambda+1)+4\right)}{\pi e^{2x^{2}}\left(2x^{2}+1\right)^{2}(\text{erf}(x)+2\lambda+1)^{2}+4\sqrt{\pi}e^{x^{2}}\left(2x^{3}+x\right)(\text{erf}(x)+2\lambda+1)+4x^{2}}$
4 |  $x^{2}-2+\frac{16\left(\pi e^{2x^{2}}\left(8x^{6}+12x^{4}+18x^{2}-9\right)(\text{erf}(x)+2\lambda+1)^{2}+16\sqrt{\pi}e^{x^{2}}x\left(x^{4}+x^{2}+3\right)(\text{erf}(x)+2\lambda+1)+4\left(2x^{4}+x^{2}+8\right)\right)}{\left(\sqrt{\pi}e^{x^{2}}\left(4\left(x^{2}+3\right)x^{2}+3\right)(\text{erf}(x)+2\lambda+1)+2x\left(2x^{2}+5\right)\right)^{2}}$
Table 3: Expression of isospectral potential $\hat{V}^{-}_{m}(x)$ for
different $m$.

The normalized excited states eigenfunction of $\hat{V}^{-}_{m}(\lambda,x)$,
using (12) are given by

$\displaystyle\hat{\psi}^{-}_{n+1,m}(\lambda,x)$
$\displaystyle=\frac{1}{E^{-}_{n+1,m}}\hat{A}^{\dagger}A\psi^{-}_{n+1,m}(x),\qquad
n=0,1,2,\cdots,$ (27)
$\displaystyle=\frac{e^{-\frac{x^{2}}{2}}}{\sqrt{2(n+m+1)2^{n}n!\sqrt{\pi}}}\left(\frac{y^{m}_{n+1}(x)}{\mathcal{H}_{m}(x)}+H_{n}(x)\frac{d}{dx}\ln\left[\mathcal{I}_{m}(x)+\lambda\right]\right)$

and

$\hat{A}^{\dagger}=-\frac{d}{dx}-\frac{d}{dx}\ln\left[\frac{\psi^{-}_{0,m}(x)}{\mathcal{I}_{m}(x)+\lambda}\right],\qquad
A=\frac{d}{dx}-\frac{d}{dx}\ln[\psi^{-}_{0,m}(x)].$

The expression of $\hat{\psi}^{-}_{n+1,m}(x)$ for $m$ equal to $0,\;2\text{
and }4$ are tabulated in table-4 . As mentioned above, the spectra of
$\hat{H}^{-}_{m}$, defined using (13), is strictly isospectral to $H^{-}_{m}$
spectra and is given by Eq. (20).

m | $\hat{\psi}^{-}_{n+1,m}(\lambda,x),\qquad n=0,1,2,\cdots$
---|---
0 | $\frac{e^{-\frac{x^{2}}{2}}}{\sqrt{2(n+1)2^{n}n!\sqrt{\pi}}}\left(\frac{y^{0}_{n+1}(x)}{1}+\frac{2H_{n}(x)}{e^{x^{2}}\sqrt{\pi}(\text{erf}(x)+2\lambda+1)}\right)$
2 | $\frac{e^{-\frac{x^{2}}{2}}}{\sqrt{2(n+3)2^{n}n!\sqrt{\pi}}}\left(\frac{y^{2}_{n+1}(x)}{4x^{2}+2}+\frac{4H_{n}(x)}{\left(2x^{2}+1\right)\left(\sqrt{\pi}e^{x^{2}}\left(2x^{2}+1\right)(\text{erf}(x)+2\lambda+1)+2x\right)}\right)$
4 | $\frac{e^{-\frac{x^{2}}{2}}}{\sqrt{2(n+5)2^{n}n!\sqrt{\pi}}}\left(\frac{y^{4}_{n+1}(x)}{16x^{4}+48x^{2}+12}+\frac{48H_{n}(x)}{\sqrt{\pi}e^{x^{2}}\left(4\left(x^{2}+3\right)x^{2}+3\right)^{2}(\text{erf}(x)+2\lambda+1)+2x\left(8x^{6}+44x^{4}+66x^{2}+15\right)}\right)$
Table 4: Expression of excited state wavefunction $\hat{\psi}^{-}_{n+1,m}(x)$
for different $m$.

For $m$ equal to $0,\;2\text{ and }4$, the plots of the strictly isospectral
potentials for positive and negative $\lambda$ as a function of $x$ are shown
in Fig-(2.a, 3.a, 4.a) and Fig-(2.b, 3.b, 4.b) respectively. Pursey and
Abraham-Moses potential plots as a function of $x$ are shown in Fig-(2.c, 3.c,
4.c). The ground-state wavefunction plots as a function of $x$ for various
$\lambda$ are shown in Fig-(2.d, 3.d, 4.d). From the figures one observes that
the eigen functions and the strictly isospectral potentials become sharper
with increasing $m$. In the limit $\lambda$ approaching to $\pm\infty$ the
potential $\hat{V}^{-}_{m}(\lambda,\;x)$ approaches to $V^{-}_{m}(x)$. Also
notice that the potential starts developing a minimum when $\lambda$ decreases
from $\infty$ to zero and the attractive potential well shifts towards
$-\infty$ and finally vanishes when $\lambda$ equals zero. There is a loss of
bound state and the corresponding potential is called the Pursey potential
$V^{P}_{m}(x)$. An analogous situation occurs in the limit $\lambda=-1$ and
the potential is called the Abraham-Moses potential $V^{AM}_{m}(x)$.

###  4.1 The Pursey and The Abraham-Moses Potentials

The Pursey and The Abraham-Moses Potentials are obtained from (27) by
substituting $\lambda=0$ and $\lambda=-1$ respectively. In this case as
mentioned above, one looses a bound state and the spectrum is identical to
that of $H^{+}$, i.e.

$\hat{E}^{P}_{n,m}=\hat{E}^{AM}_{n,m}=E^{+}_{n,m}\,,$

where

$E^{+}_{n,m}=2(n+m+1),\qquad n=0,1,2,3,\cdots$

The normalized eigenfunctions of $\hat{V}^{P}_{m}(x)$ are given by

$\displaystyle\hat{\psi}^{P}_{n,m}(x)$
$\displaystyle=\frac{1}{E^{-}_{n+1,m}}\left(-\frac{d}{dx}-\frac{d}{dx}\ln\left[\frac{\psi^{-}_{0,m}(x)}{\mathcal{I}_{m}(x)}\right]\right)A\psi^{-}_{n+1,m}(x),\qquad
n=0,1,2,\cdots,.$ (28)

Similarly, the normalized eigenfunctions of $\hat{V}^{AM}_{m}(x)$ is given by

$\displaystyle\hat{\psi}^{AM}_{n,m}(x)$
$\displaystyle=\frac{1}{E^{-}_{n+1,m}}\left(-\frac{d}{dx}-\frac{d}{dx}\ln\left[\frac{\psi^{-}_{0,m}(x)}{\mathcal{I}_{m}(x)-1}\right]\right)A\psi^{-}_{n+1,m}(x),\qquad
n=0,1,2,\cdots,.$ (29)

The expression of $\hat{\psi}^{P}_{n,m}(x)$ and $\hat{\psi}^{AM}_{n,m}(x)$ for
$m$ equal to $0,\;2\text{ and }4$ are obtained from table-4 by substituting
$\lambda$ equal to $0$ and $-1$ respectively.
The ground state wavefunction plot for Pursey and AM potentials for various
$m$ are shown in figure-5.b and transition in wavefunction shape as $\lambda$
approaches zero is shown in figure-5.a.

(a) Plot of first excited state eigenfunction
$\hat{\psi}^{-}_{1,2}(\lambda,\;x)$ corresponding to potential
$\hat{V}^{-}_{2}(\lambda,x)$ as a function of $x$ when $\lambda$ approaches 0.

(b) Plot of ground state wavefunction of Pursey and AM potentials as a
function of $x$ when $m=0$ (Black curve), $m=2$(Red curve) and $m=4$(Blue
curve).

Figure 5: Dashing curve represents Pursey eigenfunction and dashed curve
represents the AM eigenfunction.

##  5 Calculation of Uncertainty $\Delta x\Delta p$

The Heisenberg Uncertainty relation for position, $x$, and momentum, $p$, is
defined as

$\Delta x\Delta
p=\sqrt{\left(<x^{2}>\;-\;<x>^{2}\right)\;\left(<p^{2}>\;-\;<p>^{2}\right)},$
(30)

where, the angle bracket, $<>$, represents expectation value in a given
wavefunction basis.

###  5.1 Uncertainty relation for REHO potential

For the REHO potentials the expectation value of the position, $x$, and the
momentum, $p$, in the ground as well as the excited states is zero as the
integrand is an odd function in the calculation of $<x>$ while the expectation
value of $<p>$ is zero since the eigenfunctions are real. The uncertainty
relation therefore takes the simpler form $\Delta x\Delta
p=\sqrt{<x^{2}><p^{2}>}$

The expectation values and hence the uncertainty values can be calculated by
using Eqs. (18). It is observed that $\Delta x=\Delta p$ for $m=0$ but the
same is not true for $m\neq 0$. The uncertainty values for $m=0,1,2$ and
$n=-1,0,1$ (i.e. ground, first and second excited states) are shown in
table-5.

m |  $n=-1$ |  $n=0$ | $n=1$
---|---|---|---
0 |  $0.5$ |  $1.5$ | $2.5$
2 |  $\approx 0.5172$ |  $\approx 1.554$ | $\approx 2.3412$
4 |  $\approx 0.5212$ |  $\approx 1.6152$ | $\approx 2.2102$
Table 5:  Uncertainty relation $\Delta x\Delta p$ for potential $V^{-}_{m}(x)$
in ground state, first excited state and second excited state for $m$ equal to
$0,\;2,\text{ and }4$.

It can be seen from figure-6.a that for the ground state, the uncertainty
value increases as $m$ increases from $0$ and then flattens out around $m=10$.
On the other hand, in the different excited states the Uncertainty values show
peculair behaviour. In particular, while it decreases with increasing $m$ for
any given even excited states but it increases with increasing $m$ for any
given odd excited states. This peculiar behaviour in the uncertainty may be
attributed to the even and odd degree of exceptional Hermite polynomials for a
given $n$. The figure-6.b shows the variation of uncertainty with different
excite states for $m$ equal to 0, 8 and 52.

(a) Uncertainty at ground state for versus $m$.

(b) Uncertainty at different excited state for $m$ equal to 0, 8 and 52.

Figure 6: Uncertainty trends with increasing $m$ and $n$.

###  5.2 Uncertainty relation for one parameter family of REHO potential

The expectation value of momentum, $<p>$, is again zero as the eigenfunctions
are real. The uncertainty in $\Delta p$ is, therefore, $\sqrt{<p^{2}>}$. The
expectation values of $x$, $x^{2}$ for various values of $m$ and $\lambda$ are
given in Appendix A. The uncertainty relation at ground-state for various
values of $m$ and $\lambda$ is given in table-6.

m/ $\lambda=$ |  $1\times 10^{-12}$ |  $1\times 10^{-8}$ |  $1\times 10^{-5}$ |  $1\times 10^{-3}$ |  $1\times 10^{-1}$ | $1\times 10^{2}$
---|---|---|---|---|---|---
0 |  $\approx 0.5202$ |  $\approx 0.5281$ |  $\approx 0.5367$ |  $\approx 0.5590$ |  $\approx 0.5455$ | $\approx 0.5000$
2 |  $\approx 0.5223$ |  $\approx 0.5270$ |  $\approx 0.5285$ |  $\approx 0.5266$ |  $\approx 0.5193$ | $\approx 0.5172$
4 |  $\approx 0.5228$ |  $\approx 0.5252$ |  $\approx 0.5246$ |  $\approx 0.5232$ |  $\approx 0.5215$ | $\approx 0.5212$
Table 6:  Uncertainty relation $\Delta x\Delta p$ for potential
$\hat{V}^{-}_{m}(\lambda,x)$ in ground state for $m$ equal to $0,\;2,\text{
and }4$.

When the values of $\lambda(>0)$ in the table-6 are replaced by $-|\lambda+1|$
the uncertainty relation $\Delta x\Delta p$ remains unchanged and it
corresponds to the Abraham Moses potential. The plot of uncertainty versus
$\lambda$ for $m=0$ and $m=2$ is shown in figure-7.a and 7.b respectively. The
peak of uncertainty curve rapidly moves towards origin with increasing $m$.

(a) m=0 case.

(b) m=2 case.

Figure 7: Uncertainty versus positive $\lambda$ graph for $m=0$ and $m=2$.

####  5.2.1 Uncertainty relations for Pursey and Abraham Moses Potentials

The expectation value of $x$ and $x^{2}$ are calculated in Appendix C for
various values of $m$. It is interesting to note that the expectation value of
$x$ is equal and opposite in the case of the Pursey and the AM Potentials
while the expectation value of $x^{2}$ and $p^{2}$ is the same in both the
cases.

m/n |  0 |  1 |  2 |  3 | 10
---|---|---|---|---|---
0 |  $\approx 0.50184$ |  $\approx 1.4879$ |  $\approx 2.4894$ |  $\approx 3.4905$ | $\approx 10.4947$
2 |  $\approx 0.50015$ |  $\approx 1.4990$ |  $\approx 2.4984$ |  $\approx 3.4980$ | $\approx 10.4977$
4 |  $\approx 0.50004$ |  $\approx 1.4997$ |  $\approx 2.4994$ |  $\approx 3.4992$ | $\approx 10.4987$
Table 7:  Uncertainty relation $\Delta x\Delta p$ for potential
$\hat{V}^{P}_{m}(x)$ or $\hat{V}^{AM}_{m}(x)$ for various $n$ and for $m$
equal to $0,\;2,\text{ and }4$.

As a result the uncertainty value corresponding to a given $m$ is the same for
the Pursey and the AM potentials. The uncertainty value for the Pursey and the
AM potentials at the ground and the different excited-states is given in
table-7. The uncertainty decreases at ground state with increasing $m$ and
becomes asymptotic to $0.5$. On contrast it is seen that uncertainty is lesser
than QHO ($m=0$) uncertainty for excited states.

##  6 Summary and discussion

In this manuscript, we consider the rationally extended one dimensional
harmonic oscillator potential associated with exceptional $X_{m}$-Hermite
polynomials. Unlike the one dimensional oscillator, for nonzero $m$, while the
energy gap between the excited states is $2$ units, the energy gap between the
groundstate and first excited state is $m+1$. Using the idea of SQM, we
obtained one parameter ($\lambda$) family of strictly isospectral potentials
corresponding to the REHO potential as well as the corresponding
eigenfunctions. As a special case, as $\lambda$ approaches $0$ or $-1$, we
obtained the rationally extended Pursey and the AM potentials respectively as
well as their eigenfunctions. Further, we calculated the Heisenberg
uncertainty relations $\Delta x\Delta p$ for the REHO and as well as the
corresponding strictly isopectral one parameter ($\lambda$) family of
potentials. In addition, we also calculated the uncertainity relation for the
corresponding Pursey and AM potentials. In the case of the REHO, we showed
that the ground state uncertainity increases as $m$ increases. In the case of
the strictly isospectral one parameter family of potentials, one finds that
the uncertainty relation depends on $m$ as well as $\lambda$. Remarkably, we
find that for any $m$, the uncertainty relation is the same for the Pursey and
the AM potentials.

There are several open problems. For example, In this paper we have only
studied the potentials with even codimension $m$ and obtained the
corresponding strictly isospectral one parameter family. Can one similarly
obtain the corresponding one parameter family of potentials in case the
codimension $m$ is odd. Further, apart from the one dimensional oscillator,
are there other rationally extended potentials for which the eigenfunctions
can be expressed in terms of exceptional Hermite polynomials? Another obvious
question is whether there are exceptional Legendre polynomials and if yes can
one discover new potentials whose eigenfunctions can be expressed in terms of
exceptional Legendre polynomials? We hope to study some of these problems in
coming days.

Acknowledgements
AK is gratefel to Indian National Science Academy (INSA) for awarding INSA
Honarary Scientist position at Savitribai Phule Pune University. One of us
(RK) is grateful to Ian Marquette for useful comments.

Appendix A. Expectation value of $x$ and $x^{2}$ for one parameter family of
REHO
The expectation value of $x$ and $x^{2}$ for various values of positive
$\lambda$ are calculated using (26) as:

$<x>=\begin{cases}\approx-3.0028\|_{m=0}\;\approx-2.2259\|_{m=2}\;\approx-1.8057\|_{m=4}&\text{,
when $\lambda=0.00001$}\\\
\approx-2.1553\|_{m=0}\;\approx-1.4304\|_{m=2}\;\approx-1.1187\|_{m=4}&\text{,
when $\lambda=0.001$}\\\
\approx-0.9133\|_{m=0}\;\approx-0.5202\|_{m=2}\;\approx-0.3955\|_{m=4}&\text{,
when $\lambda=0.1$}\\\
\approx-0.0039\|_{m=0}\;\approx-0.0022\|_{m=2}\;\approx-0.0016\|_{m=4}&\text{,
when $\lambda=100$}\\\
\approx-0.0004\|_{m=0}\;\approx-0.0002\|_{m=2}\;\approx-0.0002\|_{m=4}&\text{,
when $\lambda=1000$}\\\ \end{cases}$

When the values of $\lambda(>0)$ in the above table are replaced by
$-|\lambda+1|$ the magnitude of the values of $x$ remain unchanged but the
sign reverses.

$<x^{2}>=\begin{cases}\approx 9.1024\|_{m=0}\;\approx 5.0384\|_{m=2}\;\approx
3.3276\|_{m=4}&\text{, when $\lambda=0.00001$}\\\ \approx
4.8071\|_{m=0}\;\approx 2.1621\|_{m=2}\;\approx 1.3309\|_{m=4}&\text{, when
$\lambda=0.001$}\\\ \approx 1.2338\|_{m=0}\;\approx 0.4198\|_{m=2}\;\approx
0.2446\|_{m=4}&\text{, when $\lambda=0.1$}\\\ \approx 0.5000\|_{m=0}\;\approx
0.1556\|_{m=2}\;\approx 0.0896\|_{m=4}&\text{, when $\lambda=100$}\\\ \approx
0.5\|_{m=0}\;\approx 0.1556\|_{m=2}\;\approx 0.0896\|_{m=4}&\text{, when
$\lambda=1000$}\\\ \end{cases}$

When the values of $\lambda(>0)$ in the above table are replaced by
$-|\lambda+1|$ the expectation values of $x^{2}$ remains unchanged. Similarly,
the expectation value of $p^{2}$ can be calculated.

Appendix B. Expectation value of $x$ and $x^{2}$ for Puresey and Abraham Moses
Potentials
The expectation value and uncertainty relation can be calculated from (28) and
(29).

The expectation value of $x$ and $x^{2}$ for various values of $m$ are as
follows:

$<x>=\begin{cases}\approx
0.6386\|_{\text{Pursey}}\;\approx-0.6386\|_{\text{AM}}&\text{, when $m=0$}\\\
\approx 0.3928\|_{\text{Pursey}}\;\approx-0.3928\|_{\text{AM}}&\text{, when
$m=2$}\\\ \approx
0.3087\|_{\text{Pursey}}\;\approx-0.3087\|_{\text{AM}}&\text{, when $m=4$}\\\
\end{cases}$

$<x^{2}>=\begin{cases}\approx 0.9043\|_{\text{Pursey}}\;\approx
0.9043\|_{\text{AM}}&\text{, when $m=0$}\\\ \approx
0.6539\|_{\text{Pursey}}\;\approx 0.6539\|_{\text{AM}}&\text{, when $m=2$}\\\
\approx 0.5952\|_{\text{Pursey}}\;\approx 0.5952\|_{\text{AM}}&\text{, when
$m=4$}\\\ \end{cases}$

## References

  * [1] Fred Cooper, Avinash Khare, and Uday Sukhatme.  Supersymmetry and quantum mechanics.  Physics Reports, 251(5-6):267–385, 1995.
  * [2] ZS Agranovich and Vladimir Aleksandrovich Marchenko.  The inverse problem of scattering theory.  Courier Dover Publications, 2020.
  * [3] Khosrow Chadan and Pierre C Sabatier.  Inverse problems in quantum scattering theory.  Springer Science & Business Media, 2012.
  * [4] George L Lamb Jr.  Elements of soliton theory.  New York, page 29, 1980.
  * [5] Philip G Drazin and Robin Stanley Johnson.  Solitons: an introduction, volume 2.  Cambridge university press, 1989.
  * [6] Michael Martin Nieto.  Relationship between supersymmetry and the inverse method in quantum mechanics.  Physics Letters B, 145(3-4):208–210, 1984.
  * [7] RD Amado.  Phase-equivalent supersymmetric quantum-mechanical partners of the coulomb potential.  Physical Review A, 37(7):2277, 1988.
  * [8] DL Pursey.  Isometric operators, isospectral hamiltonians, and supersymmetric quantum mechanics.  Physical Review D, 33(8):2267, 1986.
  * [9] PB Abraham and HE Moses.  Changes in potentials due to changes in the point spectrum: anharmonic oscillators with exact solutions.  Physical Review A, 22(4):1333, 1980.
  * [10] G Darboux.  On a proposition relative to linear equations.  arXiv preprint physics/9908003, 1999.
  * [11] Satoru Odake and Ryu Sasaki.  Krein–adler transformations for shape-invariant potentials and pseudo virtual states.  Journal of Physics A: Mathematical and Theoretical, 46(24):245201, 2013.
  * [12] Avinash Khare and Uday Sukhatme.  Phase-equivalent potentials obtained from supersymmetry.  Journal of Physics A: Mathematical and General, 22(14):2847, 1989\.
  * [13] Wai-Yee Keung, Uday P Sukhatme, Qinmou Wang, and Tom D Imbo.  Families of strictly isospectral potentials.  Journal of Physics A: Mathematical and General, 22(21):L987, 1989\.
  * [14] David Gómez-Ullate, Niky Kamran, and Robert Milson.  An extended class of orthogonal polynomials defined by a sturm–liouville problem.  Journal of Mathematical Analysis and Applications, 359(1):352–367, 2009.
  * [15] David Gomez-Ullate, Niky Kamran, and Robert Milson.  Exceptional orthogonal polynomials and the darboux transformation.  Journal of Physics A: Mathematical and Theoretical, 43(43):434016, 2010.
  * [16] David Gomez-Ullate, Niky Kamran, and Robert Milson.  On orthogonal polynomials spanning a non-standard flag.  Contemp. Math, 563:51–71, 2012.
  * [17] Bikashkali Midya and Barnana Roy.  Exceptional orthogonal polynomials and exactly solvable potentials in position dependent mass schrödinger hamiltonians.  Physics Letters A, 373(45):4117–4122, 2009.
  * [18] Choon-Lin Ho.  Dirac (-pauli), fokker–planck equations and exceptional laguerre polynomials.  Annals of Physics, 326(4):797–807, 2011.
  * [19] Rajesh Kumar Yadav, Avinash Khare, and Bhabani Prasad Mandal.  The scattering amplitude for a newly found exactly solvable potential.  Annals of Physics, 331:313–316, 2013.
  * [20] Rajesh Kumar Yadav, Avinash Khare, and Bhabani Prasad Mandal.  The scattering amplitude for rationally extended shape invariant eckart potentials.  Physics Letters A, 379(3):67–70, 2015.
  * [21] C-L Ho, J-C Lee, and R Sasaki.  Scattering amplitudes for multi-indexed extensions of solvable potentials.  Annals of Physics, 343:115–131, 2014.
  * [22] Rajesh Kumar Yadav, Nisha Kumari, Avinash Khare, and Bhabani Prasad Mandal.  Group theoretic approach to rationally extended shape invariant potentials.  Annals of Physics, 359:46–54, 2015.
  * [23] Nisha Kumari, Rajesh Kumar Yadav, Avinash Khare, Bijan Bagchi, and Bhabani Prasad Mandal.  Scattering amplitudes for the rationally extended pt symmetric complex potentials.  Annals of Physics, 373:163–177, 2016.
  * [24] Rajesh Kumar Yadav, Avinash Khare, Bijan Bagchi, Nisha Kumari, and Bhabani Prasad Mandal.  Parametric symmetries in exactly solvable real and pt symmetric complex potentials.  Journal of Mathematical Physics, 57(6):062106, 2016.
  * [25] Nisha Kumari, Rajesh Kumar Yadav, Avinash Khare, and Bhabani Prasad Mandal.  A class of exactly solvable rationally extended calogero–wolfes type 3-body problems.  Annals of Physics, 385:57–69, 2017.
  * [26] Rajesh Kumar Yadav, Avinash Khare, Nisha Kumari, and Bhabani Prasad Mandal.  Rationally extended many-body truncated calogero–sutherland model.  Annals of Physics, 400:189–197, 2019.
  * [27] B Basu-Mallick, Bhabani Prasad Mandal, and Pinaki Roy.  Quasi exactly solvable extension of calogero model associated with exceptional orthogonal polynomials.  Annals of Physics, 380:206–212, 2017.
  * [28] Suman Banerjee, Rajesh Kumar Yadav, Avinash Khare, Nisha Kumari, and Bhabani Prasad Mandal.  Solutions of (1+ 1)-dimensional dirac equation associated with exceptional orthogonal polynomials and the parametric symmetry.  arXiv preprint arXiv:2211.02557, 2022.
  * [29] Arturo Ramos, Bijan Bagchi, Avinash Khare, Nisha Kumari, Bhabani Prasad Mandal, and Rajesh Kumar Yadav.  A short note on “group theoretic approach to rationally extended shape invariant potentials”[ann. phys. 359 (2015) 46–54].  Annals of Physics, 382:143–149, 2017.
  * [30] David Gómez-Ullate, Yves Grandati, and Robert Milson.  Rational extensions of the quantum harmonic oscillator and exceptional hermite polynomials.  Journal of Physics A: Mathematical and Theoretical, 47(1):015203, 2013.
  * [31] Jonathan M Fellows and Robert A Smith.  Factorization solution of a family of quantum nonlinear oscillators.  Journal of Physics A: Mathematical and Theoretical, 42(33):335303, 2009.
  * [32] Ian Marquette and Christiane Quesne.  Two-step rational extensions of the harmonic oscillator: exceptional orthogonal polynomials and ladder operators.  Journal of Physics A: Mathematical and Theoretical, 46(15):155201, 2013.
  * [33] Rajesh Kumar Yadav, Suman Banerjee, Nisha Kumari, Avinash Khare, and Bhabani Prasad Mandal.  One parameter family of rationally extended isospectral potentials.  Annals of Physics, 436:168679, 2022.


(31) $\displaystyle\leq\beta+\log(2).$ (32)

This confirms Assumption 1 with $b=\beta+\log(2)$. Furthermore,

$\displaystyle\mathcal{L}_{\text{kl}}(a,y)$
$\displaystyle=y\log\frac{y}{\pi(a)}+(1-y)\log\frac{1-y}{1-\pi(a)}=-[ya-\log(1+\exp(a))]$
(33) $\displaystyle=\log(1+\exp(-(2y-1)a))$ (34)

so the first derivative is bounded as $|\frac{\partial}{\partial
a}\mathcal{L}_{\text{kl}}(a,y)|=|y-\frac{\exp(a)}{1+\exp(a)}|\leq 1$. By the
mean value theorem, this confirms Assumption 2 with $\Lambda_{\mathrm{Lip}}=1$
w.r.t. the standard metric on $[-\beta,\beta]$.

∎

###  A.2 Quasi-convex loss functions

######  Lemma 24.

Examples 1-3 satisfy Assumption 3 for any distribution $P$:

  1. 1.

The zero-one loss $\mathcal{L}_{\text{0,1}}$ satisfies Assumption 3 with
$\Lambda_{\mathrm{qc}}=2$, and Ens equal to the modal average:
$\textbf{Ens}(\\{\phi_{i}(x)\\}_{i\in[m]})=\text{sgn}(\sum_{i\in[m]}\phi_{i}(x))$;

  2. 2.

The squared loss $\mathcal{L}_{\text{sqr}}$ satisfies Assumption 3 with
$\Lambda_{\mathrm{qc}}=1$, and Ens equal to the arithmetic average of the
bounded-linear outputs;

  3. 3.

The Kullback Leibler loss $\mathcal{L}_{\text{kl}}$ satisfies Assumption 3
with $\Lambda_{\mathrm{qc}}=1$, and Ens equal to the arithmetic average of the
bounded-linear outputs.

###### Proof.

To prove the first claim we take $\eta(x)=\mathbb{P}[Y=1|X=x]$ and
$P_{X}(A)=\mathbb{P}(X\in A)$. So, $\phi^{*}(x)=\mathbf{1}(\eta(x)\geq
1/2)\cdot 2-1$ and we can write

$\displaystyle\mathcal{R}_{\mathcal{L},P}\left(h\right)-\mathcal{R}_{\mathcal{L},P}\left(\phi^{*}\right)$
$\displaystyle=\int|\eta(x)-1/2|\cdot\mathbf{1}\left\\{{h(x)\neq\phi^{*}(x)}\right\\}dP_{X}(x).$
(35)

Given $\\{\phi_{i}\\}_{i\in[m]}\in\mathcal{M}(\mathcal{X},\mathcal{V})^{m}$,
if for some $x\in\mathcal{X}$,
$\textbf{Ens}\left(\\{\phi_{i}\\}_{i\in[m]}\right)(x)\neq\phi^{*}(x)$, where
Ens denotes the modal average, then we have $\phi_{i}(x)\neq\phi^{*}(x)$ for
at least $m/2$ values of $i\in[m]$. Thus,

$\displaystyle\mathbf{1}\left\\{{\textbf{Ens}\left(\\{\phi_{i}\\}_{i\in[m]}\right)(x)\neq\phi^{*}(x)}\right\\}\leq\frac{2}{m}\cdot\sum_{i\in[m]}\mathbf{1}\left\\{{\phi_{i}}(x)\neq\phi^{*}\right\\}.$

Integrating over $P_{X}$ and substituting into (35) proves the claim.

Since $\mathcal{L}_{\text{sqr}}$ is convex the second result is a consequence
of Lemma 1. Similarly, the function
$\mathcal{L}_{\text{kl}}(a,y)=\text{kl}(\pi(a),y)$ is convex in $a$. Hence the
result again follows from Lemma 1. ∎

We note that for the $\mathcal{L}_{\text{kl}}$, the arithmetic average is
equivalent to the product-of-experts combination of the nonlinear
probabilistic outputs.

###  A.3 Covering number assumptions

Let us recall some useful terminology and foundational results on _psuedo-
dimension_ which may be found in Anthony and Bartlett, (2009).

######  Definition 3 (Pseudo-shattering).

Take $\mathcal{F}\subseteq\mathcal{M}(\mathcal{X},\mathbb{R})$. A set
${\bm{x}}_{1:n}=\\{x_{j}\\}_{j\in[n]}\in\mathcal{X}^{n}$ is said to be
_pseudo-shattered_ by $\mathcal{F}$ if there exists real numbers
$\bm{r}_{1:n}=\\{r_{j}\\}_{j\in[n]}$ such that for every
${\bm{\sigma}}_{1:n}=\\{\sigma_{j}\\}_{j\in[n]}\in\\{-1,1\\}^{n}$ there exists
$f_{{\bm{\sigma}}_{1:n}}\in\mathcal{F}$ with
$\text{sgn}\left(f_{{\bm{\sigma}}_{1:n}}(x_{j})-r_{j}\right)=\sigma_{j}$ for
every $j\in[n]$.

The pseudo-dimension is the natural analogue of the VC dimension for real-
valued functions.

######  Definition 4 (Pseudo-dimension).

Take $\mathcal{F}\subseteq\mathcal{M}(\mathcal{X},\mathbb{R})$. The _pseudo-
dimension_ of $\mathcal{F}$, denoted by $\text{PDim}(\mathcal{F})$, refers to
the maximum cardinality $n\in\mathbb{N}$ of a set
${\bm{x}}_{1:n}\in\mathcal{X}^{n}$ which is pseudo-shattered by $\mathcal{F}$.
If there are sets of arbitrarily large cardinality which are pseudo-shattered
by $\mathcal{F}$ then we say that $\mathcal{F}$ has infinite pseudo-dimension
$\text{PDim}(\mathcal{F})=\infty$.

We use the following well known results.

######  Theorem 25.

Let
$\mathcal{F}_{\text{linear}}\subseteq\mathcal{M}\left(\mathbb{R}^{k},\mathbb{R}\right)$
be the set of affine functions

$\displaystyle\mathcal{F}_{\text{linear}}:=\left\\{\bm{u}\mapsto\bm{w}\cdot\bm{u}-t:\hskip
5.69054pt\bm{w}\in\mathbb{R}^{k},\hskip 2.84526ptt\in\mathbb{R}\right\\}.$

Then $\mathcal{F}_{\text{linear}}$ has pseudo-dimension
$\text{PDim}\left(\mathcal{F}_{\text{linear}}\right)=k+1$.

###### Proof.

See (Anthony and Bartlett,, 2009, Theorem 11.6). ∎

######  Theorem 26.

Suppose that
$\mathcal{F}\subseteq\mathcal{M}\left(\mathcal{X},\mathbb{R}\right)$ and let
$g\in\mathcal{M}\left(\mathbb{R},\mathbb{R}\right)$ be a non-decreasing
function. Then the set $g\left(\mathcal{F}\right):=\left\\{g\circ
f:f\in\mathcal{F}\right\\}$ has pseudo-dimension
$\text{PDim}\left(g\left(\mathcal{F}\right)\right)\leq\text{PDim}\left(\mathcal{F}\right)$.

###### Proof.

See (Anthony and Bartlett,, 2009, Theorem 11.3). ∎

Given any function class
$\mathcal{F}\subseteq\mathcal{M}(\mathcal{X},\mathbb{R})$ and any
${\bm{x}}_{1:n}=\\{x_{j}\\}_{j\in[n]}\in\mathcal{X}^{n}$, the empirical
$\ell_{\infty}$ metric ${d}_{{\bm{x}}_{1:n}}^{\infty}$ on $\mathcal{F}$ is
defined for $f_{0}$, $f_{1}\in\mathcal{F}$ by

$\displaystyle{d}_{{\bm{x}}_{1:n}}^{\infty}(f_{0},f_{1}):=\max_{j\in[n]}\left\\{\left|f_{0}(x_{j})-f_{1}(x_{j})\right|\right\\}.$

######  Theorem 27.

Suppose $\beta>0$, $d\in\mathbb{N}$ and
$\mathcal{F}\subseteq\mathcal{M}_{\beta}\left(\mathcal{X}\right)$ has pseudo-
dimension $\text{PDim}\left(\mathcal{F}\right)\leq d$. Then for all $n\geq d$,
${\bm{x}}_{1:n}\in\mathcal{X}^{n}$ and $\epsilon>0$,

$\displaystyle\log\left(\mathcal{N}\left(\mathcal{F},{d}_{{\bm{x}}_{1:n}}^{\infty},\epsilon\right)\right)\leq
d\cdot\left({\log}_{+}\left(\frac{\beta n}{\epsilon\cdot d}\right)+2\right).$

###### Proof.

By (Anthony and Bartlett,, 2009, Theorem 12.2) for $\epsilon\in[0,2\beta)$ we
have

$\displaystyle\log\left(\mathcal{N}\left(\mathcal{F},{d}_{{\bm{x}}_{1:n}}^{\infty},\epsilon\right)\right)\leq
d\cdot\log\left(\frac{2e\beta n}{\epsilon\cdot d}\right)\leq
d\cdot\left({\log}_{+}\left(\frac{\beta n}{\epsilon\cdot d}\right)+2\right).$

For $\epsilon\geq 2\beta$ the claim follows immediately from
$\mathcal{F}\subseteq\mathcal{M}_{\beta}(\mathcal{X})$ so
$\mathcal{N}\left(\mathcal{F},{d}_{{\bm{x}}_{1:n}}^{\infty},\epsilon\right)\leq
1$. ∎

We now verify Assumption 4 for the function classes used in our examples,
$\mathcal{F}_{k}^{\text{0,1}}$ (as in Example 1) and $\mathcal{F}_{k}^{{bl}}$
(as in Examples 2-3). We note that other nonlinear transformations of the
linear function class may also satisfy this assumption provided that the
nonlinearity only changes the log covering number by a constant factor.

######  Proposition 5.

Examples 1-3 satisfy Assumption 4. More precisely:

  1. 1.

The class
$\mathcal{F}_{k}^{\text{0,1}}=\left\\{\bm{u}\mapsto\text{sgn}\left(\bm{w}\cdot\bm{u}-t\right):\hskip
5.69054pt\bm{w}\in\mathbb{R}^{k},\hskip
2.84526ptt\in\mathbb{R}\right\\}\subseteq\mathcal{M}\left(\mathbb{R}^{k},\\{-1,+1\\}\right)$
satisfies Assumption 4 with constant $C_{\mathrm{cn}}=4$ and bound $\beta=1$.

  2. 2.

The class
$\mathcal{F}_{k}^{{bl}}=\left\\{\bm{u}\mapsto\max\left\\{\min\left\\{\bm{w}\cdot\bm{u}-t,\beta\right\\},-\beta\right\\}:\hskip
5.69054pt\bm{w}\in\mathbb{R}^{k},\hskip
2.84526ptt\in\mathbb{R}\right\\}\subseteq\mathcal{M}_{\beta}\left(\mathbb{R}^{k}\right)$
satisfies Assumption 4 with constant $C_{\mathrm{cn}}=4$ and bound $\beta$.

###### Proof of Proposition 5.

  1. 1.

By Theorem 25, $\text{PDim}\left(\mathcal{F}_{\text{linear}}\right)=k+1$.
Moreover, the mapping $t\mapsto\text{sgn}(t)$ is non-decreasing, so by Theorem
26, $\text{PDim}\left(\mathcal{F}_{k}^{\text{0,1}}\right)\leq k+1$. Note that
for all ${\bm{u}}_{1:n}$, and any $f_{0},f_{1}$ we have
${d}_{{\bm{u}}_{1:n}}^{\mathcal{V}}(f_{0},f_{1})\leq{d}_{{\bm{u}}_{1:n}}^{\infty}(f_{0},f_{1})$,
where ${d}_{{\bm{u}}_{1:n}}^{\mathcal{V}}$ is the empirical $\ell_{2}$ metric.
By Theorem 27, for every $n,k\in\mathbb{N}$ with $n>k$,
${\bm{u}}_{1:n}\in(\mathbb{R}^{k})^{n}$, and $\epsilon>0$,

$\displaystyle\log\left(\mathcal{N}\left(\mathcal{F}_{k}^{\text{0,1}},{d}_{{\bm{u}}_{1:n}}^{\mathcal{V}},\epsilon\right)\right)$
$\displaystyle\leq\log\left(\mathcal{N}\left(\mathcal{F}_{k}^{\text{0,1}},{d}_{{\bm{u}}_{1:n}}^{\infty},\epsilon\right)\right)$
$\displaystyle\leq(k+1)\cdot\left({\log}_{+}\left(\frac{n}{\epsilon\cdot(k+1)}\right)+2\right)\leq
4k\cdot{\log}_{+}\left(\frac{n}{\epsilon\cdot k}\right).$

  2. 2.

Since $\text{PDim}\left(\mathcal{F}_{\text{linear}}\right)=k+1$ and the
mapping $t\mapsto\max\\{\min\\{t,\beta\\},-\beta\\}$ is non-decreasing,
Theorem 26 implies $\text{PDim}\left(\mathcal{F}_{k}^{{bl}}\right)\leq k+1$.
By Theorem 27 for every $n,k\in\mathbb{N}$ with $n>k$,
${\bm{u}}_{1:n}\in\left(\mathbb{R}^{k}\right)^{n}$ and $\epsilon>0$,

$\displaystyle\log\left(\mathcal{N}\left(\mathcal{F}_{k}^{{bl}},{d}_{{\bm{u}}_{1:n}}^{\infty},\epsilon\right)\right)$
$\displaystyle\leq(k+1)\cdot\left({\log}_{+}\left(\frac{\beta
n}{\epsilon\cdot(k+1)}\right)+2\right)\leq 4k\cdot{\log}_{+}\left(\frac{\beta
n}{\epsilon\cdot k}\right).$ (36)

Hence, since
${d}_{{\bm{u}}_{1:n}}^{\mathcal{V}}\leq{d}_{{\bm{u}}_{1:n}}^{\infty}$ we have
$\log\left(\mathcal{N}\left(\mathcal{F}_{k}^{{bl}},{d}_{{\bm{u}}_{1:n}}^{\mathcal{V}},\epsilon\right)\right)\leq
4k\cdot{\log}_{+}\left(\frac{\beta n}{\epsilon\cdot k}\right)$.

∎

###  A.4 Bernstein-Tsybakov condition

We now consider Assumption 5. For example 1, the 0-1 loss
$\mathcal{L}_{\text{0,1}}$ (example 1), the Tsybakov noise condition implies
the Bernstein condition (Tsybakov, 2004b, , Proposition 1). For the squared
loss and the Kullback-Leibler loss we utilise the following lemma.

######  Lemma 28.

Suppose that $\mathcal{L}:[-\beta,\beta]\times\mathcal{Y}\rightarrow[0,b]$
satisfies Assumptions 2 and 10. Then satisfy the Bernstein-Tsybakov condition
with exponent $\alpha=1$ and constant
$C_{\mathrm{B}}={4\Lambda_{\mathrm{Lip}}^{2}}/{\mathrm{H}}$.

###### Proof.

Choose $\phi\in\mathcal{M}(\mathcal{X},\mathcal{V})$ and define
$\phi_{1/2}\in\mathcal{M}(\mathcal{X},\mathcal{V})$ by
$\phi_{1/2}(x)=(\phi(x)+\phi^{*}(x))/2$ for $x\in\mathcal{X}$. By Assumption
10 we have

$\displaystyle\left(\phi(x)-\phi^{*}(x)\right)^{2}\leq\frac{4}{\mathrm{H}}\left(\left\\{\mathcal{L}(\phi(x),y)-\mathcal{L}(\phi^{*}(x),y)\right\\}+2\left\\{\mathcal{L}\left(\phi_{1/2}(x),y\right)-\mathcal{L}(\phi^{*}(x),y)\right\\}\right)$

for all $x\in\mathcal{X}$ and $y\in\mathcal{Y}$. Hence, by applying Assumption
2 we have

$\displaystyle\int\left\\{\mathcal{L}\left(\phi(x),y\right)-\mathcal{L}\left(\phi^{*}(x),y\right)\right\\}^{2}dP(x,y)$
$\displaystyle\leq\Lambda_{\mathrm{Lip}}^{2}\int\left(\phi(x)-\phi^{*}(x)\right)^{2}dP_{X}(x)$
$\displaystyle\leq\frac{4\Lambda_{\mathrm{Lip}}^{2}}{\mathrm{H}}\left(\mathcal{E}_{\mathcal{L},P}(\phi)-2\mathcal{E}_{\mathcal{L},P}(\phi_{1/2})\right)$
$\displaystyle\leq\frac{4\Lambda_{\mathrm{Lip}}^{2}}{\mathrm{H}}\mathcal{E}_{\mathcal{L},P}(\phi),$

as required. ∎

######  Lemma 29.

A twice differentiable function $\varphi:[a,b]\rightarrow\mathbb{R}$ with
second derivative $\varphi^{\prime\prime}\geq\mathrm{H}$ is
$\mathrm{H}$-strongly convex on $[a,b]$.

###### Proof.

Take $v_{0}$, $v_{1}\in[a,b]$ with $v_{0}\leq v_{1}$, let
$v_{t}:=tv_{0}+(1-t)v_{1}$ and $\Delta:=v_{1}-v_{0}$. By a second order Taylor
expansion we have at $x_{t}$ we have

$\displaystyle\varphi(v_{0})$
$\displaystyle\geq\varphi(v_{t})+\varphi^{\prime}(v_{t})(v_{0}-v_{t})+\frac{\mathrm{H}}{2}(v_{0}-v_{t})^{2}=\varphi(v_{t})-\varphi^{\prime}(v_{t})\Delta
t+\frac{\mathrm{H}}{2}\Delta^{2}t^{2}$ $\displaystyle\varphi(v_{1})$
$\displaystyle\geq\varphi(v_{t})+\varphi^{\prime}(v_{t})(v_{1}-v_{t})+\frac{\mathrm{H}}{2}(v_{1}-v_{t})^{2}=\varphi(v_{t})+\varphi^{\prime}(v_{t})\Delta(1-t)+\frac{\mathrm{H}}{2}\Delta^{2}(1-t)^{2}.$

By rearranging we have
$\varphi(v_{t})\leq(1-t)\varphi(v_{0})+t\varphi(v_{1})-({\mathrm{H}}/{2})\cdot
t(1-t)\cdot\Delta^{2}$, as required. ∎

######  Corollary 30.

The square loss $\mathcal{L}_{\text{sqr}}$ and the Kullback Leibler loss
$\mathcal{L}_{\text{kl}}$ satisfy Assumption 5 with exponent $\alpha=1$.

###### Proof.

By Lemmas 28 and 29 it suffices to show that both
$u\mapsto\mathcal{L}_{\text{sqr}}(u,y)$ and $\mathcal{L}_{\text{kl}}(u,y)$ are
twice differentiable with a uniform lower bound of $\mathrm{H}$. For the
square loss we have $\frac{\partial^{2}}{\partial
u^{2}}\\{\mathcal{L}_{\text{sqr}}(u,y)\\}\equiv 2$ and for the Kullback-
Leibler loss we have

$\frac{\partial^{2}}{\partial
u^{2}}\\{\mathcal{L}_{\text{kl}}(u,y)\\}=\frac{\exp(u)}{(1+\exp(u))^{2}}\geq\frac{\exp(\beta)}{(1+\exp(\beta))^{2}},$

for all $u\in[-\beta,\beta]$ and $y\in\\{0,1\\}$, as required. ∎

##  Appendix B Local Rademacher concentration inequality

In this section we give a local Rademacher concentration inequality for the
deviation of an empirical process from its expectation (Theorem 34), which is
used in the proof of Theorem 9. In our context, it corresponds to the special
case of Theorem 9 where $\Omega$ consists of a single point. We note that
several similar results are available in the literature Massart, (2000);
Massart et al., (2006); Koltchinskii, (2006); Bartlett et al., (2005);
Boucheron et al., (2013) which highlight the role of variance in obtaining
tight concentration guarantees. However, we for completeness we provide a
proof Theorem 34 which is well-suited to our setting. We shall begin by
recalling several useful results required for the proof. The first is Bartlett
et al’s variance dependent Rademacher bound.

######  Theorem 31 (Bartlett et al., (2005)).

Suppose we have a class of functions
$\mathcal{G}\subseteq\mathcal{M}_{1}(\mathcal{Z})$. Suppose $Z$ is a random
variable taking values in $\mathcal{Z}$ with distribution $P$ and take
$v:=\sup_{g\in\mathcal{G}}\\{\int(g-\int gdP)^{2}dP\\}$. Given
$n\in\mathbb{N}$ we let $\mathcal{D}=\\{Z_{j}\\}_{j\in[n]}$ be a sequence of
independent random variables with distribution $P$. Given any
$\delta\in(0,1)$, the following holds with probability at least $1-\delta$
over $\mathcal{D}$ we have

$\displaystyle\sup_{{g}\in{\mathcal{G}}}\left\\{\left|\hat{P}_{\mathcal{D}}(g)-P(g)\right|\right\\}\leq
6\cdot\hat{\mathfrak{R}}\left(\mathcal{G},\mathcal{D}\right)+2\sqrt{\frac{v\log(1/\delta)}{n}}+\frac{11\log(1/\delta)}{n}.$

We shall also use a variant of Dudley’s inequality which allows us to control
the Rademacher complexity of a function class in terms of its covering numbers
Dudley, (1967). Given a function class
$\mathcal{G}\subseteq\mathcal{M}(\mathcal{Z},\mathbb{R})$ and a sequence
${\bm{z}}_{1:n}=\\{z_{j}\\}_{j\in[n]}\in\mathcal{Z}^{n}$ we define a data
dependent metric ${d}_{{\bm{z}}_{1:n}}$ on $\mathcal{G}$ by
${d}_{{\bm{z}}_{1:n}}(g_{0},g_{1})=\sqrt{\hat{P}_{{\bm{z}}_{1:n}}\left\\{\left(g_{0}-g_{1}\right)^{2}\right\\}}$,
for $g_{0}$, $g_{1}\in\mathcal{G}$. The following refinement of Dudley’s
inequality due to Srebro and Sridharan Srebro and Sridharan, (2010).

######  Theorem 32 (Dudley, (1967); Srebro and Sridharan, (2010)).

Suppose we have a function class
$\mathcal{G}\subseteq\mathcal{M}(\mathcal{Z},\mathbb{R})$ and a sequence
${\bm{z}}_{1:n}=\\{z_{j}\\}_{j\in[n]}\in\mathcal{Z}^{n}$, we have the
following bound,

$\displaystyle\hat{\mathfrak{R}}\left(\mathcal{G},{\bm{z}}_{1:n}\right)\leq\inf_{\epsilon>0}\left\\{4\epsilon+\int_{\epsilon}^{\sup_{g\in\mathcal{G}}\left\\{\sqrt{\hat{P}_{{\bm{z}}_{1:n}}\left(g^{2}\right)}\right\\}}\sqrt{\frac{\log\mathcal{N}\left(\mathcal{G},{d}_{{\bm{z}}_{1:n}},\epsilon\right)}{n}}\right\\}.$

We also utilize Talagrand’s contraction inequality Ledoux and Talagrand,
(2013).

######  Lemma 33 (Ledoux and Talagrand, (2013)).

Suppose that $\varphi:\mathbb{R}\rightarrow\mathbb{R}$ is a $L$-Lipschitz
function and $\mathcal{G}\subseteq\mathcal{M}(\mathcal{Z})$ is a function
class. Then for any ${\bm{z}}_{1:n}\in\mathcal{Z}^{n}$ we have
$\hat{\mathfrak{R}}\left(\left\\{\varphi\circ
g:g\in\mathcal{G}\right\\},{\bm{z}}_{1:n}\right)\leq
L\cdot\hat{\mathfrak{R}}\left(\mathcal{G},{\bm{z}}_{1:n}\right)$.

With these results in hand we give the following concentration inequality
which adapts ideas from Massart, (2000); Massart et al., (2006); Koltchinskii,
(2006); Bartlett et al., (2005); Boucheron et al., (2013) to our setting.

######  Theorem 34 (Local Rademacher concentration inequality).

Suppose we have a countable class of functions
$\mathcal{G}\subseteq\mathcal{M}_{1}(\mathcal{Z})$ and a function
$\phi:\mathcal{Z}^{n}\times(0,\infty)\rightarrow(0,\infty)$ such that for each
${\bm{z}}_{1:n}\in\mathcal{Z}^{n}$, $r\mapsto\phi({\bm{z}}_{1:n},r)$ is a non-
decreasing function such that $r\mapsto\phi({\bm{z}}_{1:n},r)/\sqrt{r}$ is
non-increasing and for all $r>0$ and
${\bm{z}}_{1:n}=\\{z_{j}\\}_{j\in[n]}\in\mathcal{Z}^{n}$,

$\displaystyle\hat{\mathfrak{R}}\left(\left\\{g\in\mathcal{G}:{\frac{1}{n}\sum_{j\in[n]}g^{2}(z_{j})}\leq
r\right\\},{\bm{z}}_{1:n}\right)\leq\phi({\bm{z}}_{1:n},r).$

For each ${\bm{z}}_{1:n}\in\mathcal{Z}^{n}$ we choose
$\rho^{*}({\bm{z}}_{1:n})\in(0,\infty)$ so that
$\phi({\bm{z}}_{1:n},\rho^{*}({\bm{z}}_{1:n})))={\rho^{*}({\bm{z}}_{1:n})}$.
Suppose we have a sequence of independent random variables
$\mathcal{D}=\\{Z_{j}\\}_{j\in[n]}$ with common distribution $P$. Given any
$\delta\in(0,1)$, the following holds with probability at least $1-\delta$
over $\mathcal{D}$ for all $g\in\mathcal{G}$,

$\displaystyle\left|\hat{P}_{\mathcal{D}}(g)-P(g)\right|$ $\displaystyle\leq
2\cdot\sqrt{P(g^{2})\cdot\left(72\cdot\rho^{*}(\mathcal{D})+\frac{2\log(4\log(n)/\delta)}{n}\right)}+\left(132\cdot\rho^{*}(\mathcal{D})+\frac{30\log(4\log(n)/\delta)}{n}\right).$

Before the proof we recall the following elementary lemma.

######  Lemma 35.

Suppose that $x$, $A$, $B$ $>0$ satisfy $x\leq A\sqrt{x}+B$. Then $x\leq
A^{2}+2B$.

###### Proof of Theorem 34.

For each $k\in\\{1,\cdots,\lfloor\log_{2}(n)\rfloor\\}$ we let
$v_{k}=2^{k+1}/n$. We let $\mathcal{G}_{1}=\\{g\in\mathcal{G}:P(g^{2})\leq
v_{1}\\}$ and for each $k\in\\{2,\cdots,\lfloor\log_{2}(n)\rfloor\\}$ we let
$\mathcal{G}_{k}=\\{g\in\mathcal{G}:v_{k-1}<P(g^{2})\leq v_{k}\\}$. Observe
that $v_{\lfloor\log_{2}(n)\rfloor}\geq 1$ and since
$\mathcal{G}\subseteq\mathcal{M}_{1}(\mathcal{Z})$ we have $P(g^{2})\leq 1$
for all $g\in\mathcal{G}$, so
$\mathcal{G}\subseteq\bigcup_{k=1}^{\lfloor\log_{2}(n)\rfloor}\mathcal{G}_{k}$.
Fix $k\in\\{1,\cdots,{\lfloor\log_{2}(n)\rfloor}\\}$. By Theorem 31 we see
that with probability at least $1-\delta$, for all $g\in\mathcal{G}_{k}$ we
have

$\displaystyle\left|\hat{P}_{\mathcal{D}}(g)-P(g)\right|$ $\displaystyle\leq
6\cdot\hat{\mathfrak{R}}\left(\mathcal{G}_{k},\mathcal{D}\right)+2\sqrt{\frac{v_{k}\log(1/\delta)}{n}}+\frac{11\log(1/\delta)}{n}.$
(37)

Let $\mathcal{G}_{k}^{2}=\\{g^{2}:g\in\mathcal{G}_{k}\\}$. Note also that
$z\mapsto z^{2}$ is $2$-Lipschitz so by Lemma 33 we have
$\hat{\mathfrak{R}}\left(\mathcal{G}_{k}^{2},\mathcal{D}\right)\leq
2\hat{\mathfrak{R}}\left(\mathcal{G}_{k},\mathcal{D}\right)$. Note also that
for $g\in\mathcal{G}_{k}$, $P((g^{2})^{2})\leq P(g^{2})\leq v_{k}$, since $g$
is bounded by 1, so applying Theorem 31 once again, we see that with
probability at least $1-\delta$, for all $g\in\mathcal{G}_{k}$ we have

$\displaystyle\left|\hat{P}_{\mathcal{D}}(g^{2})-P(g^{2})\right|$
$\displaystyle\leq
12\cdot\hat{\mathfrak{R}}\left(\mathcal{G}_{k},\mathcal{D}\right)+2\sqrt{\frac{v_{k}\log(1/\delta)}{n}}+\frac{11\log(1/\delta)}{n}.$
(38)

Thus, by the union bound (37) and (38) both hold for all
$k\in\\{1,\cdots,{\lfloor\log_{2}(n)\rfloor}\\}$ with probability at least
$1-2\log_{2}(n)\cdot\delta\geq 1-4\log(n)\cdot\delta$. Observe that for all
$k\in\\{1,\cdots,{\lfloor\log_{2}(n)\rfloor}\\}$ and $g\in\mathcal{G}_{k}$,
$P(g^{2})\leq v_{k}$, so given (38) we have

$\displaystyle\hat{P}_{\mathcal{D}}(g^{2})$ $\displaystyle\leq
v_{k}+12\cdot\hat{\mathfrak{R}}\left(\mathcal{G}_{k},\mathcal{D}\right)+2\sqrt{\frac{v_{k}\log(1/\delta)}{n}}+\frac{11\log(1/\delta)}{n}.$

Let
$u_{k}:=v_{k}+12\cdot\hat{\mathfrak{R}}\left(\mathcal{G}_{k},\mathcal{D}\right)+2\sqrt{{v_{k}\log(1/\delta)}/{n}}+{11\log(1/\delta)}/{n}$.
We deduce that
$\mathcal{G}_{k}\subseteq\\{g\in\mathcal{G}:\hat{P}_{\mathcal{D}}(g^{2})\leq
u_{k}\\}$ and so

$\displaystyle\hat{\mathfrak{R}}(\mathcal{G}_{k},\mathcal{D})\leq\hat{\mathfrak{R}}\left(\left\\{g\in\mathcal{G}:{\frac{1}{n}\sum_{j\in[n]}g^{2}(z_{j})}\leq
u_{k}\right\\},{\bm{z}}_{1:n}\right)\leq\phi\left(\mathcal{D},u_{k}\right).$
(39)

Plugging back into the previous inequality gives

$\displaystyle u_{k}\leq
v_{k}+12\cdot\phi({\mathcal{D}},u_{k})+2\sqrt{\frac{v_{k}\log(1/\delta)}{n}}+\frac{11\log(1/\delta)}{n}.$

We claim that

$\displaystyle u_{k}\leq v_{k}+12\cdot\sqrt{\rho^{*}(\mathcal{D})\cdot
u_{k}}+2\sqrt{\frac{v_{k}\log(1/\delta)}{n}}+\frac{11\log(1/\delta)}{n}.$ (40)

Indeed, either $u_{k}\leq\rho^{*}(\mathcal{D})$, in which case the claim (40)
holds, or $u_{k}>\rho^{*}(\mathcal{D})$. If the latter holds we combine
$\phi(\mathcal{D},\rho^{*}(\mathcal{D}))=\rho^{*}(\mathcal{D})$ with the fact
that $\phi(\mathcal{D},r)/\sqrt{r}$ is non-increasing implies
$\sqrt{\rho^{*}(\mathcal{D})}=\phi({\mathcal{D}},\rho^{*}(\mathcal{D}))/\sqrt{\rho^{*}(\mathcal{D})}\geq\phi({\mathcal{D}},u_{k})/\sqrt{u_{k}}$,
which by (39) yields the claim (40). Hence, in either case (40) holds. Now by
plugging in the definition for $u_{k}$ and subtracting
$v_{k}+2\sqrt{{v_{k}\log(1/\delta)}/{n}}+{11\log(1/\delta)}/{n}$ from both
sides we obtain

$\displaystyle\hat{\mathfrak{R}}\left(\mathcal{G}_{k},\mathcal{D}\right)$
$\displaystyle\leq\sqrt{\rho^{*}(\mathcal{D})\cdot\left(v_{k}+12\cdot\hat{\mathfrak{R}}\left(\mathcal{G}_{k},\mathcal{D}\right)+2\sqrt{\frac{v_{k}\log(1/\delta)}{n}}+\frac{11\log(1/\delta)}{n}\right)}$
$\displaystyle\leq\sqrt{(12\rho^{*}(\mathcal{D}))\cdot\hat{\mathfrak{R}}\left(\mathcal{G}_{k},\mathcal{D}\right)}+\sqrt{\rho^{*}(\mathcal{D})\cdot\left(2v_{k}+\frac{12\log(1/\delta)}{n}\right)}.$

By Lemma 35 this implies

$\displaystyle\hat{\mathfrak{R}}\left(\mathcal{G}_{k},\mathcal{D}\right)\leq
12\cdot\rho^{*}(\mathcal{D})+2\sqrt{\rho^{*}(\mathcal{D})\cdot\left(2v_{k}+\frac{12\log(1/\delta)}{n}\right)}.$

Hence, by (37) with probability at least $1-4\log(n)\cdot\delta$ the following
holds for all $k\in\\{0,\cdot\lfloor\log_{2}(n)\rfloor-1\\}$ and
$g\in\mathcal{G}_{k}$ we have

$\displaystyle\left|\hat{P}_{\mathcal{D}}(g)-P(g)\right|$ $\displaystyle\leq
6\cdot\hat{\mathfrak{R}}\left(\mathcal{G}_{k},\mathcal{D}\right)+2\sqrt{\frac{v_{k}\log(1/\delta)}{n}}+\frac{11\log(1/\delta)}{n}$
$\displaystyle\leq
72\cdot\rho^{*}(\mathcal{D})+12\sqrt{\rho^{*}(\mathcal{D})\cdot\left(2v_{k}+\frac{12\log(1/\delta)}{n}\right)}+2\sqrt{\frac{v_{k}\log(1/\delta)}{n}}+\frac{11\log(1/\delta)}{n}$
$\displaystyle\leq
72\cdot\rho^{*}(\mathcal{D})+12\sqrt{\rho^{*}(\mathcal{D})\cdot\left(\max\left\\{\frac{8}{n},4P(g^{2})\right\\}+\frac{12\log(1/\delta)}{n}\right)}$
$\displaystyle\hskip
56.9055pt+2\sqrt{\frac{\max\left\\{\frac{8}{n},4P(g^{2})\right\\}\cdot\log(1/\delta)}{n}}+\frac{11\log(1/\delta)}{n}$
$\displaystyle\leq
72\cdot\rho^{*}(\mathcal{D})+24\sqrt{\rho^{*}(\mathcal{D})\cdot\left(P(g^{2})+\frac{5\log(1/\delta)}{n}\right)}+4\sqrt{\frac{P(g^{2})\cdot\log(1/\delta)}{n}}+\frac{17\log(1/\delta)}{n}$
$\displaystyle\leq
2\cdot\sqrt{P(g^{2})\cdot\left(72\cdot\rho^{*}(\mathcal{D})+\frac{2\log(1/\delta)}{n}\right)}+132\cdot\rho^{*}(\mathcal{D})+\frac{30\log(1/\delta)}{n}.$

By noting that
$\mathcal{G}\subseteq\bigcup_{k=0}^{\lfloor\log_{2}(n)\rfloor-1}\mathcal{G}_{k}$
and taking $\delta/4\log(n)$ in place of $\delta$ in the above bound, the
conclusion of the theorem follows. ∎

##  Appendix C The existence of the Bayes optimal predictor

In this section we consider the existence of Bayes optimal predictor. Recall
that, given a loss function
$\mathcal{L}:\mathcal{V}\times\mathcal{Y}\rightarrow[0,b]$ and a Borel
probability distribution $P$ on $X\times\mathcal{Y}$, a function
$\phi^{*}\equiv\phi^{*}_{\mathcal{L},P}\in\mathcal{M}(\mathcal{X},\mathcal{V})$
is said to be a Bayes optimal predictor if it satisfies

$\displaystyle\mathcal{R}_{\mathcal{L},P}(\phi^{*})=\inf_{{\phi}\in\mathcal{M}(\mathcal{X},\mathcal{V})}\left\\{\mathcal{R}_{\mathcal{L},P}({\phi})\right\\}.$
(41)

In this section we shall show that a Bayes optimal predictor exists under mild
conditions (see Proposition 6). We require the measurable maximum theorem.

######  Definition 5 (Carathéodory function).

A function $g:\mathcal{X}\times\mathcal{V}\rightarrow\mathbb{R}$ is said to be
a Carathéodory function if:

  * •

For all $x\in\mathcal{X}$, the map $u\mapsto g(x,u)$ is a continuous function
of $u\in\mathcal{V}$,

  * •

For all $u\in\mathcal{V}$, the map $x\mapsto g(x,u)$ is a measurable function
of $x\in\mathcal{X}$.

We shall utilise the following simplified version of the measurable maximum
theorem.

######  Lemma 36 (Measurable maximum theorem).

Suppose that $\mathcal{X}$ is a measurable space and $\mathcal{V}$ is a
compact metric space. Let
$g:\mathcal{X}\times\mathcal{V}\rightarrow\mathbb{R}$ be a Carathéodory
function. Define $m:\mathcal{X}\rightarrow\mathbb{R}$ by
$m(x):=\sup_{u\in\mathcal{V}}\left\\{g(x,u)\right\\}$. Then $m_{g}$ is a
measurable function and there exists a measurable function
$h:\mathcal{X}\rightarrow\mathcal{V}$ with the property that $g(x,h(x))=m(x)$
for all $x\in\mathcal{X}$.

###### Proof.

This is a special case of (Aliprantis and Border,, 2013, Theorem 18.19). ∎

We also utilise regular conditional distributions.

######  Lemma 37 (Regular conditional distributions).

Let $P$ be a Borel probability measure on the product space
$\mathcal{X}\times\mathcal{Y}$, where $\mathcal{X}$ and $\mathcal{Y}$ are
complete separable metric spaces. Then there exists a family
$(P^{x})_{x\in\mathcal{X}}$ is a family of Borel probability measures on
$\mathcal{Y}$ such that for all measurable functions
$h:\mathcal{X}\times\mathcal{Y}\rightarrow\mathbb{R}$ with
$\int|h(x,y)|dP(x,y)<\infty$, the mapping
$x\mapsto\int_{\mathcal{Y}}h(x,y)dP^{x}(y)$ is measurable and satisfies

$\displaystyle\int_{\mathcal{X}\times\mathcal{Y}}h(x,y)dP(x,y)=\int_{\mathcal{X}}\left(\int_{\mathcal{Y}}h(x,y)dP^{x}(y)\right)dP_{X}(x).$
(42)

###### Proof.

Apply (Klenke,, 2013, Theorem 8.37) combined with the fact that both
$\mathcal{X}$ and $\mathcal{Y}$ are complete separable metric spaces, and so
$\mathcal{X}\times\mathcal{Y}$ is separable and completely meterizable, and
hence Borel. ∎

We shall refer to $(P^{x})_{x\in\mathcal{X}}$ as the regular conditional
distribution with respect to $X$. We can now give a proposition which gives
sufficient conditions for the existence of a Bayes optimal predictor
$\phi^{*}$.

######  Proposition 6.

Suppose that $\mathcal{V}$ is a compact metric space, $P$ is a Borel
probability distribution on $\mathcal{X}\times\mathcal{Y}$ and
$\mathcal{L}:\mathcal{V}\times\mathcal{Y}\rightarrow[0,b]$ is a bounded loss
function which is continuous in its first argument. Then there exists a Bayes
optimal predictor $\phi^{*}\in\mathcal{M}(\mathcal{X},\mathcal{V})$. Moreover,
any Bayes optimal predictor $\phi^{*}\in\mathcal{M}(\mathcal{X},\mathcal{V})$
satisfies

$\displaystyle\phi^{*}(x)\in\text{argmin}_{u\in\mathcal{V}}\left\\{\int_{\mathcal{Y}}\mathcal{L}(u,y)dP^{x}(y)\right\\}$
(43)

for $P_{X}$ almost every $x\in\mathcal{X}$.

###### Proof.

We begin by applying Theorem 37 to obtain a regular conditional distribution
$(P^{x})_{x\in\mathcal{X}}$ such that given any
$h:\mathcal{X}\times\mathcal{Y}\rightarrow\mathbb{R}$ with
$\int|h(x,y)|dP(x,y)<\infty$ the map
$x\mapsto\int_{\mathcal{Y}}h(x,y)dP^{x}(y)$ is measurable and satisfies (42).
In particular, given any $\phi\in\mathcal{M}(\mathcal{X},\mathcal{V})$ the map
$(x,y)\mapsto\mathcal{L}(\phi(x),y)$ is a bounded measurable map and so
$x\mapsto\int_{\mathcal{Y}}\mathcal{L}(\phi(x),y)dP^{x}(y)$ is a measurable
map satisfying,

$\displaystyle\mathcal{R}_{\mathcal{L},P}(\phi)=\int_{\mathcal{X}\times\mathcal{Y}}\mathcal{L}(\phi(x),y)dP(x,y)=\int_{\mathcal{X}}\left(\int_{\mathcal{Y}}\mathcal{L}(\phi(x),y)dP^{x}(y)\right)dP_{X}(x).$
(44)

Now define a function $g:\mathcal{X}\times\mathcal{V}\rightarrow\mathbb{R}$ by
$g(x,u):=-\int_{\mathcal{Y}}\mathcal{L}(u,y)dP^{x}(y)$. Observe that for each
$u\in\mathcal{V}$, $x\mapsto g(x,u)$ is measurable. Moreover, for each
$y\in\mathcal{Y}$, the function $u\mapsto-\mathcal{L}(u,y)$ is continuous and
so by the dominated convergence theorem it follows that $u\mapsto g(x,u)$ is
continuous for each $x\in\mathcal{X}$. Hence, we have confirmed that $g$ is a
Carathéodory function. Since $\mathcal{V}$ is compact we can apply Theorem 36
to see that there exists a function
$\phi^{*}:\mathcal{X}\rightarrow\mathcal{V}$ with the property that
$g(x,\phi^{*}(x))=\sup_{u\in\mathcal{V}}\\{g(x,u)\\}$ for all
$x\in\mathcal{X}$. Hence, for all $x\in\mathcal{X}$, we have
$\int_{\mathcal{Y}}\mathcal{L}(\phi^{*}(x),y)dP^{x}(y)\leq\inf_{u\in\mathcal{V}}\\{\int_{\mathcal{Y}}\mathcal{L}(u,y)dP^{x}(y)\\}$
so (43) holds. By (44) it follows that $\phi^{*}$ satisfies (41) and so is a
Bayes optimal predictor. Suppose on the other hand that
$\tilde{\phi}\in\mathcal{M}(\mathcal{X},\mathcal{V})$ is such that
$\tilde{\phi}(x)\notin\operatorname*{arg\,inf}_{u\in\mathcal{V}}\left\\{\int_{\mathcal{Y}}\mathcal{L}(u,y)dP^{x}(y)\right\\}$
on a set $A\subseteq\mathcal{X}$ of positive $P_{X}$ measure. Then by (44) it
follows that
$\mathcal{R}_{\mathcal{L},P}(\tilde{\phi})>\mathcal{R}_{\mathcal{L},P}(\phi^{*})$
and so $\tilde{\phi}$ is not a Bayes optimal predictor. ∎

##  Appendix D Proof of Lemma 12

To prove Lemma 12 we require the following elementary lemma.

######  Lemma 38.

Given any $\Delta$, $T>0$ we have

$\displaystyle\int_{0}^{\Delta}{\log}_{+}^{\frac{1}{2}}\left(\frac{{T}}{\epsilon}\right)d\epsilon\leq\Delta\cdot\left({\log}_{+}^{\frac{1}{2}}\left(\frac{{T}}{\Delta}\right)+\frac{\sqrt{\pi}}{2}\right).$

###### Proof.

First assume that ${T}/\Delta\geq e$, so we have

$\displaystyle\int_{0}^{\Delta}{\log}_{+}^{\frac{1}{2}}\left(\frac{{T}}{\epsilon}\right)d\epsilon$
$\displaystyle=\int_{0}^{\Delta}\log^{\frac{1}{2}}\left(\frac{{T}}{\epsilon}\right)d\epsilon=\Delta\cdot\int_{0}^{1}\log^{\frac{1}{2}}\left(\frac{{T}}{\Delta\cdot
z}\right)dz$
$\displaystyle\leq\Delta\cdot\left(\log^{\frac{1}{2}}\left(\frac{{T}}{\Delta}\right)+\int_{0}^{1}\log^{\frac{1}{2}}(1/z)dz\right)=\Delta\cdot\left(\log^{\frac{1}{2}}\left(\frac{{T}}{\Delta}\right)+\frac{\sqrt{\pi}}{2}\right),$

where we use the fact that
$\int_{0}^{1}{\log^{\frac{1}{2}}(1/z)}dz=\sqrt{\pi}/2$ by a change of
variables. On the other hand, if ${T}/\Delta<e$ we have

$\displaystyle\int_{0}^{\Delta}{\log}_{+}^{\frac{1}{2}}\left(\frac{{T}}{\epsilon}\right)d\epsilon$
$\displaystyle=\int_{0}^{\frac{{T}}{e}}\log^{\frac{1}{2}}\left(\frac{{T}}{\epsilon}\right)d\epsilon+\left(\Delta-\frac{{T}}{e}\right)$
$\displaystyle=\frac{{T}}{e}\cdot\left(\log^{\frac{1}{2}}\left(\frac{{T}}{{T}/e}\right)+\frac{\sqrt{\pi}}{2}\right)+\left(\Delta-\frac{{T}}{e}\right)=\Delta+\frac{{T}}{e}\cdot\frac{\sqrt{\pi}}{2}$
$\displaystyle<\Delta\cdot\left(1+\frac{\sqrt{\pi}}{2}\right)=\Delta\cdot\left({\log}_{+}^{\frac{1}{2}}\left(\frac{{T}}{\Delta}\right)+\frac{\sqrt{\pi}}{2}\right),$

where we have applied the previous inequality with ${T}/e$ in place of
$\Delta$.

∎

###### Proof Lemma 12.

For the purpose of the proof define
$\mathcal{G}_{A}(r):=\\{g\in\mathcal{G}_{A}:\hat{P}_{{\bm{z}}_{1:n}}(g^{2})\leq
r\\}$ and
${\bm{u}}_{1:n}=\\{u_{j}\\}_{j\in[n]}\in\left(\mathbb{R}^{k}\right)^{n}$ where
$u_{j}=A(x_{j})\in\mathbb{R}^{k}$. Given any $g_{0}$,
$g_{1}\in\mathcal{G}_{A}$ we may choose $f_{0}$, $f_{1}\in\mathcal{F}_{k}$
such that $g_{0}(z)=\mathcal{L}(f_{0}(A(x)),y)-\mathcal{L}(\phi^{*}(x),y)$ and
$g_{1}(z)=\mathcal{L}(f_{1}(A(x)),y)-\mathcal{L}(\phi^{*}(x),y)$ for all
$z=(x,y)\in\mathcal{X}\times\mathcal{Y}$. By Assumption 2 we have

$\displaystyle{d}_{{\bm{z}}_{1:n}}(g_{0},g_{1})$
$\displaystyle:=\sqrt{\hat{P}_{{\bm{z}}_{1:n}}\left((g_{0}-g_{1})^{2}\right)}=\sqrt{\frac{1}{n}\sum_{j\in[n]}\left(\mathcal{L}\left(f_{0}(u_{j}),y_{j}\right)-\mathcal{L}\left(f_{0}(u_{j}),y_{j}\right)\right)^{2}}$
$\displaystyle\leq\Lambda_{\mathrm{Lip}}\cdot\sqrt{\frac{1}{n}\sum_{j\in[n]}{d}_{\mathcal{V}}\left(f_{0}(u_{j}),f_{1}(u_{j})\right)^{2}}=\Lambda_{\mathrm{Lip}}\cdot{{d}_{{\bm{u}}_{1:n}}^{\mathcal{V}}}(f_{0},f_{1}).$

Hence, by Assumption 4 for all $\epsilon>0$ we have

$\displaystyle\log\left(\mathcal{N}\left(\mathcal{G}_{A}(r),{d}_{{\bm{z}}_{1:n}},{\epsilon}\right)\right)$
$\displaystyle\leq\log\left(\mathcal{N}\left(\mathcal{G}_{A},{d}_{{\bm{z}}_{1:n}},{\epsilon}\right)\right)\leq\log\left(\mathcal{N}\left(\mathcal{F}_{k},{{d}_{{\bm{u}}_{1:n}}^{\mathcal{V}}},\frac{\epsilon}{\Lambda_{\mathrm{Lip}}}\right)\right)$
$\displaystyle\leq C_{\mathrm{cn}}\cdot
k\cdot{\log}_{+}\left(\frac{\Lambda_{\mathrm{Lip}}\beta n}{\epsilon
k}\right).$

Note also that
$\sup_{g\in\mathcal{G}_{A}(r)}\\{\sqrt{\hat{P}_{{\bm{z}}_{1:n}}\left(g^{2}\right)}\\}\leq\sqrt{r}$.
Hence, by Dudley’s inequality (Theorem 32) we have

$\displaystyle\hat{\mathfrak{R}}\left(\mathcal{G}_{A}(A),{\bm{z}}_{1:n}\right)$
$\displaystyle\leq\int_{0}^{\sqrt{r}}\sqrt{\frac{\log\mathcal{N}\left(\mathcal{G},{d}_{{\bm{z}}_{1:n}},\epsilon\right)}{n}}d\epsilon\leq\sqrt{\frac{C_{\mathrm{cn}}\cdot
k}{n}}\cdot\int_{0}^{\sqrt{r}}{{\log}_{+}^{\frac{1}{2}}\left(\frac{\Lambda_{\mathrm{Lip}}\beta
n}{\epsilon k}\right)}d\epsilon$
$\displaystyle\leq\sqrt{\frac{C_{\mathrm{cn}}\cdot k\cdot
r}{n}}\cdot\left({\log}_{+}^{\frac{1}{2}}\left(\frac{\Lambda_{\mathrm{Lip}}\beta
n}{k\sqrt{r}}\right)+\frac{\sqrt{\pi}}{2}\right)\leq
2\sqrt{\frac{C_{\mathrm{cn}}\cdot k\cdot
r}{n}}\cdot{\log}_{+}^{\frac{1}{2}}\left(\frac{\Lambda_{\mathrm{Lip}}\beta
n}{k\sqrt{r}}\right),$

where the penultimate inequality follows from Lemma 38.

∎

##  Appendix E Proof of Lemma 7

Before proving Lemma 7 we recall the following useful result due to Baraniuk
et al., (2009).

######  Lemma 39.

(Baraniuk et al.,, 2008, Lemma 5.1) Let $A\in\mathbb{R}^{k\times d}$ be a
matrix that satisfies Assumption 6 with constant $C_{\mathrm{JL}}\geq 1$.
There exists a constant ${c}_{\mathrm{B}}>0$ depending only on
$C_{\mathrm{JL}}$ such that for any $r$-dimensional linear subspace
$\mathcal{U}\subset\mathbb{R}^{d}$ with $r<k$ and $\epsilon\in(0,1)$, the
following holds with probability at least
$1-(12/\epsilon)^{r}e^{-{c}_{\mathrm{B}}\epsilon k}$,

$\displaystyle(1-\epsilon)\|x\|_{2}\leq\|Ax\|_{2}\leq(1+\epsilon)\|x\|_{2},$
(45)

for all $x\in\mathcal{U}$.

###### Proof of Lemma 7.

Let $m\leq\min\\{q,d\\}$ denote be the rank of $\mathbb{X}$ and take a
singular value decomposition $\mathbb{X}=U\Lambda V^{T}$ so that
$U\in\mathbb{R}^{d\times m}$, $\Lambda\in\mathbb{R}^{m\times m}$ and
$V\in\mathbb{R}^{q\times m}$ with $\Lambda$ diagonal and
$U^{\top}U=V^{\top}V=I_{m}$. Next let ${r_{\circ}}:=\min\\{r,m\\}$ and
partition $U=[u_{1},\ldots,u_{m}]$ column-wise into matrix
$U_{r}\in\mathbb{R}^{d\times{r_{\circ}}}$, consisting of the first
${r_{\circ}}$ columns of $U$ and
$\tilde{U}_{r}\in\mathbb{R}^{d\times(m-{r_{\circ}})}$ consisting of the
remaining $m-{r_{\circ}}$ columns (so $\tilde{U}_{r}$ may be empty).
Similarly, let $\Lambda_{r}\in\mathbb{R}^{{r_{\circ}}\times{r_{\circ}}}$ be
the upper diagonal block of $\Lambda$ containing the top ${r_{\circ}}$
singular values, and
$\tilde{\Lambda}_{r}\in\mathbb{R}^{(m-{r_{\circ}})\times(m-{r_{\circ}})}$ the
lower (possibly empty) diagonal block. In particular, we have
$U\Lambda=[U_{r}\Lambda_{r},\tilde{U}_{r}\tilde{\Lambda}_{r}]$. Next we define
a pair of events $E_{\mathrm{sp}}$ and $E_{\mathrm{ta}}$ by

$\displaystyle E_{\mathrm{sp}}$ $\displaystyle:=\left\\{\|U_{r}z\|_{2}\leq
2\|AU_{r}z\|_{2}\text{ for all }z\in\mathbb{R}^{{r_{\circ}}}\right\\},$
$\displaystyle E_{\mathrm{ta}}$
$\displaystyle:=\left\\{\|Au_{\ell}\|_{2}\leq\sqrt{2}\text{ for
}\ell\in\\{{r_{\circ}}+1,\ldots,m\\}\right\\}.$

By Lemma 39 $E_{\mathrm{sp}}$ holds with probability at least
$1-24^{r}e^{-{c}_{\mathrm{B}}k/2}$. Moreover, by Assumption 6
$E_{\mathrm{ta}}$ holds with probability at least
$1-(q-r+1)e^{-k/4C_{\mathrm{JL}}}$. Hence, by the union bound it suffices to
work on the event $E_{\mathrm{sp}}\cap E_{\mathrm{ta}}$ and show that (9)
holds. Now on the event $E_{\mathrm{sp}}$ the $k\times{r_{\circ}}$ matrix
$AU_{r}$ is of rank $r_{\circ}$ with singular values at least $1/2$, so
$\|(AU_{r})^{+}\|_{\text{spec}}\leq 2$ and
$(AU_{r})^{+}(AU_{r})=I_{r_{\circ}}$ is the ${r_{\circ}}\times{r_{\circ}}$
identity matrix ($M^{+}$ denotes the Moore-Penrose inverse of $M$). In
addition, on the event $E_{\mathrm{ta}}$ writing
$(\tilde{\Lambda}_{r,j})_{j\in[m-r_{\circ}]}$ diagonal elements of
$\tilde{\Lambda}_{r}$, given any
$z=(z_{j})_{j\in[m-r_{\circ}]}\in\mathbb{R}^{m-r_{\circ}}$ we have

$\displaystyle\|A\tilde{U}_{r}\tilde{\Lambda}_{r}z\|_{2}$
$\displaystyle=\Bigl{\|}A\bigl{(}\sum_{j=r_{\circ}+1}^{m}\tilde{\Lambda}_{r,j}z_{j}u_{j}\bigr{)}\Bigr{\|}_{2}=\Bigl{\|}\sum_{j=r_{\circ}+1}^{m}\tilde{\Lambda}_{r,j}z_{j}Au_{j}\Bigr{\|}_{2}\leq\sqrt{2}\sqrt{\sum_{j=r_{\circ}+1}^{m}\tilde{\Lambda}^{2}_{r,j}z_{j}^{2}}$
$\displaystyle\leq\sqrt{2}\|z\|_{2}\sqrt{\sum_{j=r_{\circ}+1}^{m}\tilde{\Lambda}_{r,j}^{2}}\leq\sqrt{2}\|z\|\sqrt{\sum_{j\geq
r+1}\lambda_{j}(\mathbb{X}\mathbb{X}^{\top})},$

so
$\|A\tilde{U}_{r}\tilde{\Lambda}_{r}\|_{\mathrm{spec}}^{2}\leq\sqrt{2}\sum_{j=r+1}^{m}\lambda_{j}(\mathbb{X}\mathbb{X}^{\top})$.
Hence, choosing $w\equiv
w(A,r):=\\{w_{\diamond}^{\top}U_{r}(AU_{r})^{+}\\}^{\top}$,

$\displaystyle\inf_{\tilde{w}\in\mathbb{R}^{k}}\|\tilde{w}^{\top}A\mathbb{X}-w_{\diamond}^{\top}\mathbb{X}\|_{2}^{2}$
$\displaystyle\leq\|(w^{\top}A-w_{\diamond}^{\top})\mathbb{X}\|_{2}^{2}=\|(w^{\top}A-w_{\diamond}^{\top})U\Lambda\|_{2}^{2}$
$\displaystyle\leq\|(w^{\top}A-w_{\diamond}^{\top})U_{r}\Lambda_{r}\|_{2}^{2}+\|(w^{\top}A-w_{\diamond}^{\top})\tilde{U}_{r}\tilde{\Lambda}_{r}\|_{2}^{2}$
$\displaystyle=\|w_{\diamond}^{\top}U_{r}(AU_{r})^{+}(AU_{r})\Lambda_{r}-w_{\diamond}^{\top}U_{r}\Lambda_{r}\|_{2}^{2}+\|(w^{\top}A-w_{\diamond}^{\top})\tilde{U}_{r}\tilde{\Lambda}_{r}\|_{2}^{2}$
$\displaystyle=\|w_{\diamond}^{\top}(U_{r}(AU_{r})^{+}A-I_{d})\tilde{U}_{r}\tilde{\Lambda}_{r}\|_{2}^{2}$
$\displaystyle\leq\|w_{\diamond}\|_{2}^{2}\cdot\|(U_{r}(AU_{r})^{+}A-I_{d})\tilde{U}_{r}\tilde{\Lambda}_{r}\|_{\mathrm{spec}}^{2}$
$\displaystyle\leq
2\|w_{\diamond}\|_{2}^{2}\cdot\left(\|U_{r}(AU_{r})^{+}A\tilde{U}_{r}\tilde{\Lambda}_{r}\|_{\mathrm{spec}}^{2}+\lambda_{r+1}(\mathbb{X}\mathbb{X}^{\top})\right)$
$\displaystyle\leq
2\|w_{\diamond}\|_{2}^{2}\cdot\left(\|(AU_{r})^{+}\|_{\mathrm{spec}}^{2}\cdot\|A\tilde{U}_{r}\tilde{\Lambda}_{r}\|_{\mathrm{spec}}^{2}+\lambda_{r+1}(\mathbb{X}\mathbb{X}^{\top})\right)$
$\displaystyle\leq
18\|w_{\diamond}\|_{2}^{2}~{}\sum_{j=r+1}^{m}\lambda_{j}(\mathbb{X}\mathbb{X}^{\top}),$

as required. ∎

## References

  * Achlioptas, (2003) Achlioptas, D. (2003).  Database-friendly random projections: Johnson-Lindenstrauss with binary coins.  Journal of Computer and System Sciences, 66(4):671–687.
  * Ailon and Chazelle, (2006) Ailon, N. and Chazelle, B. (2006).  Approximate nearest neighbors and the fast Johnson-Lindenstrauss transform.  In Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, pages 557–563.
  * Aliprantis and Border, (2013) Aliprantis, C. D. and Border, K. (2013).  Infinite Dimensional Analysis: A Hitchhiker’s Guide.  Springer-Verlag Berlin and Heidelberg GmbH & Company KG.
  * Anthony and Bartlett, (2009) Anthony, M. and Bartlett, P. L. (2009).  Neural network learning: Theoretical foundations.  Cambridge University Press.
  * Arriaga et al., (2015) Arriaga, R. I., Rutter, D., Cakmak, M., and Vempala, S. S. (2015).  Visual categorization with random projection.  Neural Computation, 27(10):2132–2147.
  * Arriaga and Vempala, (1999) Arriaga, R. I. and Vempala, S. (1999).  An algorithmic theory of learning: Robust concepts and random projection.  In 40th Annual Symposium on Foundations of Computer Science (FOCS), pages 616–623.
  * Baraniuk et al., (2008) Baraniuk, R., Davenport, M., DeVore, R., and Wakin, M. (2008).  A simple proof of the restricted isometry property for random matrices.  Constructive Approximations, 28:253–263.
  * Baraniuk et al., (2009) Baraniuk, R., Davenport, M., DeVore, R., and Wakin, M. (2009).  Random projections of smooth manifolds.  Foundations of computational mathematics, 9(1):51–77.
  * Bartlett et al., (2005) Bartlett, P. L., Bousquet, O., and Mendelson, S. (2005).  Local Rademacher complexities.  The Annals of Statistics, 33(4):1497–1537.
  * Bentley et al., (2019) Bentley, A., Rowe, J. E., and Dehghani, H. (2019).  Single pixel hyperspectral bioluminescence tomography based on compressive sensing.  Biomed. Opt. Express, 10(11):5549–5564.
  * Biau et al., (2008) Biau, G., Devroye, L., and Lugosi, G. (2008).  On the performance of clustering in Hilbert spaces.  IEEE Transactions on Information Theory, 54(2):781–790.
  * Boucheron et al., (2013) Boucheron, S., Lugosi, G., and Massart, P. (2013).  Concentration inequalities: A nonasymptotic theory of independence.  Oxford university press.
  * Boutsidis et al., (2015) Boutsidis, C., Zouzias, A., Mahoney, M. W., and Drineas, P. (2015).  Randomized dimensionality reduction for k-means clustering.  IEEE Trans. Inf. Theory, 61(2):1045–1062.
  * Bǎlcan et al., (2006) Bǎlcan, M. F., Blum, A., and Vempala, S. (2006).  Kernels as features: On kernels, margins, and low-dimensional mappings.  Machine Learning, 65:79–94.
  * Calderbank et al., (2009) Calderbank, R., Jafarpour, S., and Schapire, R. (2009).  Compressed learning: Universal sparse dimensionality reduction and learning in the measurement domain.  Technical Report, Rice University.
  * Candès and Tao, (2006) Candès, E. J. and Tao, T. (2006).  Near-optimal signal recovery from random projections: Universal encoding strategies?  IEEE Trans. Inf. Theory, 52(12):5406–5425.
  * Cannings, (2020) Cannings, T. I. (2020).  Random projections: Data perturbation for classification problems.  Wiley interdisciplinary reviews., pages 1–15.
  * Cannings and Samworth, (2017) Cannings, T. I. and Samworth, R. (2017).  Random-projection ensemble classification.  Royal Statistical Society B, 79:959–1035.
  * Chen and Li, (2014) Chen, D.-R. and Li, H. (2014).  Convergence rates of learning algorithms by random projection.  Applied and Computational Harmonic Analysis, 37(1):36 – 51.
  * Cormode, (2017) Cormode, G. (2017).  Data sketching.  Queue, 15(2):49–67.
  * Dasgupta and Gupta, (2003) Dasgupta, S. and Gupta, A. (2003).  An elementary proof of a theorem of Johnson and Lindenstrauss.  Random Structures & Algorithms, 22(1):60–65.
  * Derezinski et al., (2020) Derezinski, M., Liang, F. T., Liao, Z., and Mahoney, M. W. (2020).  Precise expressions for random projections: Low-rank approximation and randomized newton.  In Larochelle, H., Ranzato, M., Hadsell, R., Balcan, M. F., and Lin, H., editors, Advances in Neural Information Processing Systems, volume 33, pages 18272–18283. Curran Associates, Inc.
  * Donoho, (2006) Donoho, D. L. (2006).  Compressed sensing.  IEEE Transactions on Information Theory, 52(4):1289–1306.
  * Duarte et al., (2008) Duarte, M. F., Davenport, M. A., Takhar, D., Laska, J. N., Sun, T., Kelly, K. F., and Baraniuk, R. G. (2008).  Single-pixel imaging via compressive sampling.  IEEE Signal Processing Magazine, 25(2):83–91.
  * Dudley, (1967) Dudley, R. M. (1967).  The sizes of compact subsets of Hilbert space and continuity of Gaussian processes.  Journal of Functional Analysis, 1(3):290–330.
  * Durrant and Kabán, (2010) Durrant, R. J. and Kabán, A. (2010).  Compressed fisher linear discriminant analysis: Classification of randomly projected data.  In Proc. 16th ACM SIGKDD international conference on Knowledge Discovery and Data Mining (KDD), pages 1119–1128.
  * Durrant and Kabán, (2015) Durrant, R. J. and Kabán, A. (2015).  Random projections as regularizers: learning a linear discriminant from fewer observations than dimensions.  Machine Learning, 99(2):257–286.
  * Fard et al., (2012) Fard, M. M., Grinberg, Y., Pineau, J., and Precup, D. (2012).  Compressed least-squares regression on sparse spaces.  In AAAI.
  * Feldman et al., (2012) Feldman, V., Guruswami, V., Raghavendra, P., and Wu, Y. (2012).  Agnostic learning of monomials by halfspaces is hard.  SIAM Journal on Computing, 41(6):1558–1590.
  * Freksen and Larsen, (2020) Freksen, C. B. and Larsen, K. G. (2020).  On using Toeplitz and circulant matrices for Johnson–Lindenstrauss transforms.  Algorithmica, 82:338–354.
  * Gian-Andrea Thanei, (2017) Gian-Andrea Thanei, Christina Heinze, N. M. (2017).  Random projections for large-scale regression.  In S., S. A., editor, Big and Complex Data Analysis. Contributions to Statistics. Springer, Cham.
  * Gibson et al., (2020) Gibson, G. M., Johnson, S. D., and Padgett, M. J. (2020).  Single-pixel imaging 12 years on: a review.  Optics Express, 28(19):28190–28208.
  * Gupta et al., (2019) Gupta, S., Gribonval, R., Daudet, L., and Dokmanić, I. (2019).  Don't take it lightly: Phasing optical random projections with unknown operators.  In Wallach, H., Larochelle, H., Beygelzimer, A., d'Alché-Buc, F., Fox, E., and Garnett, R., editors, Advances in Neural Information Processing Systems 32, pages 14855–14865. Curran Associates, Inc.
  * Halko et al., (2011) Halko, N., Martinsson, P.-G., and Tropp, J. A. (2011).  Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions.  SIAM Rev, 53(2):217–288.
  * Heinze et al., (2016) Heinze, C., McWilliams, B., and Meinshausen, N. (2016).  Dual-loco: Distributing statistical estimation using random projections.  In Gretton, A. and Robert, C. C., editors, Proceedings of the 19th International Conference on Artificial Intelligence and Statistics, volume 51 of Proceedings of Machine Learning Research, pages 875–883, Cadiz, Spain. PMLR.
  * Hinton, (2002) Hinton, G. E. (2002).  Training products of experts by minimizing contrastive divergence.  Neural Computation, 14(8):1771–1800.
  * Ho, (1998) Ho, T. K. (1998).  The random subspace method for constructing decision forests.  IEEE Transactions on Pattern Analysis and Machine Intelligence, 20(8):832–844.
  * Jiao et al., (2019) Jiao, S., Feng, J., Gao, Y., Lei, T., Xie, Z., and Yuan, X. (2019).  Optical machine learning with incoherent light and a single-pixel detector.  Opt. Lett., 44(21):5186–5189.
  * Kabán, (2014) Kabán, A. (2014).  New bounds on compressive linear least squares regression.  In Kaski, S. and Corander, J., editors, Proceedings of Machine Learning Research, volume 33, pages 448–456, Reykjavik, Iceland. PMLR.
  * Kane and Nelson, (2014) Kane, D. M. and Nelson, J. (2014).  Sparser Johnson-Lindenstrauss transforms.  Journal of the ACM (JACM), 61(1):1–23.
  * Klenke, (2013) Klenke, A. (2013).  Probability theory: a comprehensive course.  Springer Science & Business Media.
  * Koltchinskii, (2006) Koltchinskii, V. (2006).  Local rademacher complexities and oracle inequalities in risk minimization.  The Annals of Statistics, 34(6):2593–2656.
  * Larsen and Nelson, (2017) Larsen, K. G. and Nelson, J. (2017).  Optimality of the Johnson-Lindenstrauss lemma.  In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 633–638.
  * Ledoux and Talagrand, (2013) Ledoux, M. and Talagrand, M. (2013).  Probability in Banach Spaces: isoperimetry and processes.  Springer Science & Business Media.
  * Lopes, (2020) Lopes, M. E. (2020).  Estimating a sharp convergence bound for randomized ensembles.  Journal of Statistical Planning and Inference, 204:35–44.
  * Lustig et al., (2007) Lustig, M., Donoho, D., and Pauly, J. (2007).  Sparse MRI: The application of compressed sensing for rapid mr imaging.  Magn. Reson. Med., 58(6):1182–95.
  * Maillard and Munos, (2012) Maillard, O.-A. and Munos, R. (2012).  Linear regression with random projections.  Journal of Machine Learning Research, 13(89):2735–2772.
  * Mammen and Tsybakov, (1999) Mammen, E. and Tsybakov, A. B. (1999).  Smooth discrimination analysis.  Ann. Statist., 27(6):1808–1829.
  * Massart, (2000) Massart, P. (2000).  Some applications of concentration inequalities to statistics.  In Annales de la Faculté des sciences de Toulouse: Mathématiques, volume 9, pages 245–303.
  * Massart et al., (2006) Massart, P., Nédélec, É., et al. (2006).  Risk bounds for statistical learning.  The Annals of Statistics, 34(5):2326–2366.
  * Matoušek, (2008) Matoušek, J. (2008).  On variants of the Johnson-Lindenstrauss lemma.  Random Structures & Algorithms, 33(2):142–156.
  * Meintrup et al., (2019) Meintrup, S., Munteanu, A., and Rohde, D. (2019).  Random projections and sampling algorithms for clustering of high-dimensional polygonal curves.  In Wallach, H., Larochelle, H., Beygelzimer, A., d'Alché-Buc, F., Fox, E., and Garnett, R., editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc.
  * Mohri et al., (2012) Mohri, M., Rostamizadeh, A., and Talwalkar, A. (2012).  Foundations of machine learning.  MIT press.
  * Nair et al., (2016) Nair, V., Menzies, T., and Chen, J. (2016).  An (accidental) exploration of alternatives to evolutionary algorithms for SBSE.  In Sarro, F. and Deb, K., editors, Search Based Software Engineering, pages 96–111, Cham. Springer International Publishing.
  * Palmer et al., (2015) Palmer, A. D., Bunch, J., and Styles, I. B. (2015).  The use of random projections for the analysis of mass spectrometry imaging data.  J. Am. Soc. Mass Spectrom., 26(2):315–322.
  * Peressutti et al., (2015) Peressutti, D., Bai, W., Jackson, T., Sohal, M., Rinaldi, A., Rueckert, D., and King, A. (2015).  Prospective identification of crt super responders using a motion atlas and random projection ensemble learning.  In Navab, N., Hornegger, J., Wells, W. M., and Frangi, A. F., editors, Medical Image Computing and Computer-Assisted Intervention – MICCAI 2015, pages 493–500, Cham. Springer International Publishing.
  * Pilanci and Wainwright, (2015) Pilanci, M. and Wainwright, M. J. (2015).  Randomized sketches of convex programs with sharp guarantees.  IEEE Transactions on Information Theory, 61(9):5096–5115.
  * Pilanci and Wainwright, (2016) Pilanci, M. and Wainwright, M. J. (2016).  Iterative Hessian sketch: Fast and accurate solution approximation for constrained least-squares.  Journal of Machine Learning Research, 17(53):1–38.
  * Pilanci and Wainwright, (2017) Pilanci, M. and Wainwright, M. J. (2017).  Newton sketch: A near linear-time optimization algorithm with linear quadratic convergence.  SIAM Journal on Optimization, 27:205–245.
  * Reboredo et al., (2013) Reboredo, H., Renna, F., Calderbank, A. R., and Rodrigues, M. R. D. (2013).  Compressive classification.  In 2013 IEEE International Symposium on Information Theory, pages 674–678.
  * Reboredo et al., (2016) Reboredo, H., Renna, F., Calderbank, A. R., and Rodrigues, M. R. D. (2016).  Bounds on the number of measurements for reliable compressive classification.  IEEE Trans. Signal Processing, 64(22):5778–5793.
  * Reeve and Brown, (2017) Reeve, H. W. J. and Brown, G. (2017).  Minimax rates for cost-sensitive learning on manifolds with approximate nearest neighbours.  In Hanneke, S. and Reyzin, L., editors, Proceedings of Machine Learning Research, volume 76, pages 11–56.
  * Renna et al., (2016) Renna, F., Wang, L., Yuan, X., Yang, J., Reeves, G., Calderbank, R., Carin, L., and Rodrigues, M. R. D. (2016).  Classification and reconstruction of high-dimensional signals from low-dimensional features in the presence of side information.  IEEE Transactions on Information Theory, 62(11):6459–6492.
  * Saade et al., (2016) Saade, A., Caltagirone, F., Carron, I., Daudet, L., Dremeau, A., Gigan, S., and Krzakala, F. (2016).  Random projections through multiple optical scattering: Approximating kernels at the speed of light.  In 2016 IEEE International Conference on Acoustics, Speech and Signal Processing, ICASSP 2016, Shanghai, China, March 20-25, 2016, pages 6215–6219. IEEE.
  * Sendler et al., (1975) Sendler, W. et al. (1975).  A note on the proof of the zero-one law of Blum and Pathak.  The Annals of Probability, 3(6):1055–1058.
  * Slawski, (2018) Slawski, M. (2018).  On principal components regression, random projections, and column subsampling.  Electron. J. Statist., 12(2):3673–3712.
  * Srebro and Sridharan, (2010) Srebro, N. and Sridharan, K. (2010).  Note on refined Dudley integral covering number bound.  Unpublished results. http://ttic. uchicago. edu/karthik/dudley. pdf.
  * Tian and Feng, (2021) Tian, Y. and Feng, Y. (2021).  RaSE: Random subspace ensemble classification.  Journal of Machine Learning Research, 22(45):1–93.
  * (69) Tsybakov, A. B. (2004a).  Introduction a l’estimation non-paramétrique (Introduction to nonparametric estimation). Mathématiques & Applications (paris). 41.
  * (70) Tsybakov, A. B. (2004b).  Optimal aggregation of classifiers in statistical learning.  Annals of Statistics, 32(1):135–166.
  * Wainwright, (2019) Wainwright, M. J. (2019).  High-dimensional statistics: A non-asymptotic viewpoint, volume 48.  Cambridge University Press.
  * Yang et al., (2017) Yang, Y., Pilanci, M., and Wainwright, M. J. (2017).  Randomized sketches for kernels: Fast and optimal nonparametric regression.  Ann. Statist., 45(3):991–1023.
  * Ye, (2019) Ye, J. C. (2019).  Compressed sensing MRI: a review from signal processing perspective.  BMC Biomedical Engineering, 1(8).