\documentclass[conference] {IEEEtran}
%\usepackage[all]{xy}
\usepackage[utf8]{inputenc}
\usepackage[reqno]{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{amscd}
\usepackage{enumerate}

\newcommand{\supp}{\operatorname{supp}}

\def\aa{{\mathcal A}}
\def\bb{{\mathcal B}}
\def\cc{{\mathcal C}}
\def\dd{{\mathcal D}}
\def\ee{{\mathcal E}}
\def\ff{{\mathcal F}}
%\def\gg{{\mathcal G}}
\def\hh{{\mathcal H}}
\def\jj{{\mathcal J}}
\def\kk{{\mathcal K}}
\def\lll{{\mathcal L}}
\def\mm{{\mathcal M}}
\def\nn{{\mathcal N}}
\def\pp{{\mathcal P}}
\def\qq{{\mathcal Q}}
\def\rr{{\mathcal R}}
\def\ss{{\mathcal S}}
\def\ttt{{\mathcal T}}
\def\uu{{\mathcal U}}
\def\ww{{\mathcal W}}
\def\xx{{\mathcal X}}
\def\yy{{\mathcal Y}}
\def\zzz{{\mathcal Z}}


% Calligraphic letters in math mode.
%

\def\ie{i.e.\ }
\def\tq{\ :\ }
\def\ffi{\varphi}
\def\eps{\varepsilon}
\def\dst{\displaystyle}
\def\scp{\scriptstyle}
\def\eg{{\it e.g.\ }}
\def\etc{{\it etc}}
\def\ovl{\overline}
\renewcommand{\Im}{\mathrm{Im}\,}

\DeclareMathOperator{\Tr}{Tr}
\DeclareMathOperator{\suppo}{supp}
\DeclareMathOperator{\vect}{span}
%
% Various abreviations
%

\def\A{{\mathbb{A}}}
\def\B{{\mathbb{B}}}
\def\C{{\mathbb{C}}}
\def\D{{\mathbb{D}}}
\def\F{{\mathbb{F}}}
\def\hil{{\mathbb{H}}}
\def\K{{\mathbb{K}}}
\def\M{{\mathbb{M}}}
\def\N{{\mathbb{N}}}
\def\P{{\mathbb{P}}}
\def\Q{{\mathbb{Q}}}
\def\R{{\mathbb{R}}}
\def\S{{\mathbb{S}}}
\def\T{{\mathbb{T}}}
\def\X{{\mathbb{X}}}
\def\Y{{\mathbb{Y}}}
\def\Z{{\mathbb{Z}}}

\def\fg{{\mathfrak{g}}}
\def\fz{{\mathfrak{z}}}


\def\d{\,{\mathrm{d}}}
%
%Mathematical sets of reals,... (with double bars)
%

\newcommand{\norm}[1]{{\left\|{#1}\right\|}}
\newcommand{\ent}[1]{{\left[{#1}\right]}}
\newcommand{\abs}[1]{{\left|{#1}\right|}}
\newcommand{\scal}[1]{{\left\langle{#1}\right\rangle}}
\newcommand{\set}[1]{{\left\{{#1}\right\}}}

%
%Respectively \norm{x}=||x||, \ent{x}=[x], \abs{x}=|x| \scal{x}=<x>
%



\newcommand{\vp}{\varphi^{(\alpha)}_{n,c}}

\newtheorem{problem}{Problem}

\theoremstyle{plain}

\newtheorem{lemma}{Lemma}[section]
\newtheorem{proposition}[lemma]{Proposition}
\newtheorem{theorem}[lemma]{Theorem}
\newtheorem{corollary}[lemma]{Corollary}

\theoremstyle{definition}
\newtheorem{definition}[lemma]{Definition}
\newtheorem{example}[lemma]{Example}

\theoremstyle{remark}
\newtheorem{remark}[lemma]{Remark}
\newtheorem{notation}[lemma]{Notation}

%
%These are the environments we will need : lemma Section.Number
%gives a lemma that looks like Bold lemma followed by slanted text
%same for prop and theo. The numbers follow so that, e.g. in Section 2,
%lemma 2.1 is followed by theorem 2.2 then lemma 2.3.
%
%The problems are numbered 1, 2, 3... (no section number)
%
%To use them, start with \begin{lemma} (or prop/theo).... text....
%\end{lemma}
%


%\renewcommand{\theequation}{\thesection.\arabic{equation}}

% \newtheorem{theorem}{Theorem}[section]
% \newtheorem{proposition}[theorem]{Proposition}
% \newtheorem{lemma}[theorem]{Lemma}
% \newtheorem{corollary}[theorem]{Corollary}
 
%\theoremstyle{definition}
% \newtheorem{definition}[theorem]{Definition}
 
\numberwithin{equation}{section}

\begin{document}

\title{A sampling theorem for functions in Besov spaces on the sphere}

\author{
\IEEEauthorblockN{Philippe {\sc Jaming} \& Felipe {\sc Negreira}}

\IEEEauthorblockA{Univ. Bordeaux, IMB, UMR 5251\\ F-33400 Talence, France\\\
CNRS, IMB, UMR 5251\\ F-33400 Talence, France\\
$\{${\tt Philippe.Jaming,Felipe.Negreira$\}$@math.u-bordeaux.fr}}


% \and \IEEEauthorblockN{Felipe {\sc Negreira}}
%
%\IEEEauthorblockA{Univ. Bordeaux, IMB, UMR 5251\\ F-33400 Talence\\ France\\\
%CNRS, IMB, UMR 5251\\ F-33400 Talence\\ France\\
%E-mail\,:Felipe.Negreira@math.u-bordeaux.fr}
}
\maketitle

\begin{abstract}
In this work we establish sampling theorems for functions in Besov spaces on the $d$-dimensional sphere $\mathbb{S}^d$ in the spirit of their
recent counterparts established by Jaming-Malinnikova in \cite{JM}.
The main tool are needlet decomposition given by Narcowich et al. in \cite{Naretal}.
\end{abstract}


\section{Introduction}

Representation and analysis of functions (signals, images or other data) on 
manifolds has become an ubiquitous task in many scientific fields. Indeed, 
high-dimensional data acquisition has become common but the meaningful data 
is often considered to belong to a high dimensional manifold in the ambiant 
space. Among the most commonly encountered manifolds one can find the euclidean $d$-dimensional sphere 
$$
\S^d=\{(x_1,\ldots,x_{d+1})\in\R^{d+1}\,:\ x_1^2+\cdots+x_{d+1}^2=1\}.
$$
This will be the only manifold considered in this paper.
Note that the dimension here refers to the dimension of the manifold,
not to that of the ambiant space.

Many good representing systems (orthonormal bases, frames,...) for functions on manifolds are known ({\it see e.g.} \cite{GP,MM,Naretal}).
To properly represent a function $f$ using such a system, one usually
needs to know the set of coefficients of $f$ in the representing system
(or its dual) $\{\scal{f,\psi_j}\}$.
However, many data acquisition systems do not provide such coefficients but
rather a sample of the values of the function: $\{f(\eta_j)\}$.

Sampling Theory precisely deals with the possibility to reconstruct a function from its samples. The most famous result in that direction is
the Shannon-Whittaker-Kotelnikov Theorem which states that a band-limited function on $\R$ can be reconstructed from its regular samples.
This theorem has been extended to band-limited functions oncompact homogeneous manifolds (thus including the sphere) by Geller-Peterson \cite{GP}. The general idea of a sampling theorem can be stated as follows:
if a function has moderate oscillation (usually the function is band-limited, that is, has no highly oscillating Fourier component), then
it is well approximated in the neighborhood of a point by its value
at that point. Thus, if the neighborhoods cover sufficiently well the space (the sampling rate is high enough), the sample allows to describe the function.

Recently, the first author and E. Malinnikova \cite{JM} showed that, in $R^d$ a sampling theorem holds when moderate oscillation is measured in the scale of Besov spaces $B^s_{p,q}$. Our aim here is to show that a similar result holds on the sphere:

\medskip

\noindent{\bf Main Theorem.} {\sl
Let $1\leqslant p\leqslant\infty$.
There exists finite sets of points $\{\eta_1,\dots,\eta_{N}\}$ on $\S^d$, constants $c_1,c_2$ depending only on $d$, and a constant $M$ depending on $d$, $p$ such that,
if $f\in B^{d/p}_{p,1}(\mathbb{S}^d)$ with
 $\|f\|_{B^{d/p}_{p,1}}\leqslant M^{-1}\|f\|_{L^p}$ then 
$$
c_1\|f\|_{L^p}
\leqslant\left(\sum_{l=1}^{N_\epsilon}|f(\eta_l)|^p\right)^{1/p}\leqslant c_2\|f\|_{L^p}.
$$
}

\medskip

The actual result is more precise, {\it see} below. The proof consists in replacing the wavelet representation of Besov functions in $\R^d$ by the needlet representation of Besov functions in $\S^d$ as established by Narkowich-Petrushev-Ward \cite{NW} and then adapting the computations to the spherical case.

\smallskip

In the next section, we introduce all material needed in the proofs
so as to keep this paper self-contained.
The remaining of the paper is then devoted to the proof of the main theorem.

\smallskip

Throughout this paper, we will adopt the following notation: on $\R^{d+1}$,
$\abs{\cdot}$ and $\scal{\cdot,\cdot}$ are the usual Euclidean norm and scalar product while $\S^d=\{x\in\R^{d+1}\,:\ \abs{x}=1\}$ is the unit sphere. We endow $\S^d$ with its usual geodesic distance $\d(\zeta,\xi)=\dst\frac{1}{\pi}\arccos\scal{\zeta,\xi}$ and with $\sigma$ the Lebesgue measure.

Throughout the paper, $C$ will be a constant that changes from line to line
and we add an index $C_d,C_p,C_{d,p},\ldots$ to stress the dependance on the parameters $d,p,\ldots$. 

However, the constants $c^*, c^{\ast\ast},c^\diamond,\kappa$ have specific meanings stemming from the geometry of $\S^d$ and are used to ease the reading of the arguments in the proof.
 
\section{Preliminaries.}


In this section, we will describe a set of functions on the sphere $\S^{d}$ that will serve as basis for various function spaces on $\S^{d}$. There are two choices that might be suitable for our needs.
One natural choice would be the wavelet type bases that can be constructed
on the sphere by following e.g. the general construction for on any space of homogeneous type ({\it see e.g.} \cite{FD}). This construction is rather evolved and only leads to a frame in $L^2(\S^{d})$. Note however that a wavelet orthonormal basis has been constructed in \cite{AH}, but this is technically even more involved.

We therefore make the choice to use a simpler basis, namely the needlet system introduced by Narcowich, Petrushev and Ward in \cite{Naretal}.
Let us now describe this system.

The starting point is the set of spherical harmonics. Recall that a spherical harmonic is an homogeneous polynomial that is harmonic (for the usual Laplace differential operator on $\R^{d+1}$). We denote by 
$\mathcal{H}_\nu$ the subspace of $L^2(\S^{d})$ of all spherical harmonics of degree $\nu$ and by $P_\nu$ the orthogonal projector onto this subspace.
This projection operator has an integral kernel given by a Gegenbauer polynomial, a fact that we will not need here. We refer to \cite{DD,SW} for details.


%TODO reference
This allows us to define the so-called \textit{reproducing kernels}.
\begin{definition}
For each $N\geqslant1$ we define the kernel $\mathcal{K}_N$ as 
\begin{equation}\label{kernel}
K_N(x):=\sum_{\nu=0}^\infty\hat{a}\left(\frac{\nu}{N}\right)P_\nu(x)
\end{equation}
where $\hat{a}$ is a smooth function on $[0,+\infty)$ satisfying:
\begin{enumerate}
\renewcommand{\theenumi}{\roman{enumi}}
\item $\supp\hat{a}\subset[1/2,2]$,
\item $|\hat{a}(t)|>c$ if $t\in[3/5,5/3]$,
\item $\hat{a}^2(t)+\hat{a}^2(2t)=1$ if $t\in[1/2,1]$.
\end{enumerate}
\end{definition}

Note that condition (i) of $\hat{a}$ implies that the sum in (\ref{kernel}) is finite. More precisely, $\nu$ in this sum runs over $N/2\leq \nu/leq 2N$
(in particular $\nu\geq 1$) and
$K_N$ is a polynomial of degree at most $2N$. Conditions (ii) and (iii) are not necessary for the previous definition to make sense, but they are needed in order to form the right building blocks.

%It is important to note that this kind of function are not hard to find. Since the third condition on $\hat{a}$ implies that  $\sum_{\nu=0}^\infty\hat{a}\left(\frac{v}{2^{j-1}}\right)\overline{\hat{a}\left(\frac{v}{2^{j-1}}\right)}=\sum_{\nu=0}^\infty\hat{a}^2\left(\frac{v}{2^{j-1}}\right)=1$ and $\bigoplus\mathcal{H}_v$ is dense in any $L^p(\mathbb{S}^d)$.

This kernels have a natural action over functions defined in $\mathbb{S}^d$
via the spherical convolution:

\begin{definition}
Let $\Phi\in L^\infty[-1,1]$ and $f\in L^p(\mathbb{S}^d)$, $1\leqslant p\leqslant\infty$. We write
$$
\Phi\ast f(\xi):=\int_{\mathbb{S}^d}\Phi(\scal{\xi,\theta})f(\delta)\,\mathrm{d}\sigma(\theta).
$$
\end{definition}

Next we define
\begin{equation}\label{reproducing}
\begin{split}
\Phi_0:=P_0&\\\Phi_j:=K_{2^{j-1}}&\text{ for }j>0.
\end{split}
\end{equation}
We then have the following result.

\begin{proposition}
For each $\ell\geqslant0$ set $\mathcal{K}_\ell:=\dst\sum_{j=0}^\ell\Phi_j$. 
Let $1\leqslant p\leqslant\infty$, then for every $f\in L^p(\mathbb{S}^d)$,  $$
\mathcal{K}_\ell\ast f\underset{\ell\rightarrow+\infty}{\longrightarrow}f
$$
in $L^p(\S^d)$.
\end{proposition}

\begin{proof}
It is straightforward from the fact that $\dst\sum_{\nu=0}^\infty\hat{a}(2^{-\nu}t)=1$ for all $t\in[1,+\infty)$ and $\dst
L^p(\mathbb{S}^d)\subset\bigoplus_{\nu=0}^\infty\mathcal{H}_\nu$ for any $1\leqslant p\leqslant\infty$.
\end{proof}

Next, in order to define our needlet system, we need to construct a particular type of partition of $\mathbb{S}^d$.

\begin{lemma}\label{epsilon-distributed}
For any $0<\epsilon\leqslant2\pi$ there exist a partition 
$\mathcal{R}_\epsilon=\{R_1,\dots,R_{N_\epsilon}\}$ of $\mathbb{S}^d$ together with a set of points $\mathcal{X}_\epsilon=\{\eta_1,\dots,\eta_{N_\epsilon}\}\subset\mathbb{S}^d$ with the proprieties:
\begin{enumerate}
\renewcommand{\theenumi}{\roman{enumi}}
\item $\mathbb{S}^d=R_1\cup\dots\cup R_{N_\epsilon}$ and the sets in $R_j$ do not overlap ($\overset{\circ}R_j\cap \overset{\circ}R_k=\emptyset$ if $j\neq k$),

\item there exist a constant $0<c^\ast< 1$ such that for every $j=1,\dots,N_{\epsilon}$ there it holds $B_{\eta_j}(c^\ast\epsilon)\subset R_j\subset B_{\eta_j}(\epsilon)$, where $B_\eta(r):=\{\xi\in\mathbb{S}^d:d(\xi,\eta)\leqslant r\}$,

\item there exist a constant $c^{\ast\ast}>0$ such that $\#\mathcal{X_\epsilon}=\#\mathcal{R}_\epsilon=N_\epsilon\leqslant c^{\ast\ast}\epsilon^{-d}$.
\end{enumerate}
The constants $c^\ast$ and $c^{\ast\ast}$ depend only on the dimension $d$.
\end{lemma}

For a proof of this lemma see \cite[Proposition 3.2, p. 1120]{Naretal2}.

\begin{definition}
A set $\mathcal{X}_\epsilon\subset\mathbb{S}^d$ which along with the associated partition $R_\epsilon$ of $\mathbb{S}^d$ has the proprieties given in Lemma \ref{epsilon-distributed} will be be called a \textit{set of almost uniformly }$\epsilon$\textit{-distributed points} on $\mathbb{S}^d$.
\end{definition}

These sets offer a useful formula in terms of decomposition of functions.

\begin{theorem}\label{curvature}
There is a constant $c^\diamond$ (depending only on the dimension $d$) such that for any $N\geqslant1$ and any set $\mathcal{X}_\epsilon\subset\mathbb{S}^d$ of almost uniformly $\epsilon$-distributed points with $\epsilon=c^\diamond/N$, there exists positive coefficients $\{c_\eta\}_{\eta\in\mathcal{X}_\epsilon}$ such that the curvature formula $$\int_{\mathbb{S}^d}p(\xi)d\xi\sim\sum_{\eta\in\mathcal{X}_\epsilon}c_\eta p(\eta)$$ is exact for all spherical polynomials $p(\xi)$ of degree $\leqslant N$.

In addition for all $\eta$, $c_\eta\approx N^{-n}$ with the equivalence constants only depending on $d$.
\end{theorem}

For the construction of the needlet system, we are going to denote for each $j\geqslant0$, $\epsilon_j:=c^\diamond/2^{j+2}$, $\mathcal{X}_j$ a fixed set of $\epsilon_j$-distributed points and $\{c_\eta\}_{\eta\in\mathcal{X}_j}$ its associated family of positive coefficients. Also, we put $\mathcal{X}:=\dst\bigcup_{j=0}^\infty\mathcal{X}_j$.

Then, from (\ref{reproducing}), we define our \textit{needlet system} for each $j\geqslant0$ as
\begin{equation}\label{needlet}
\varphi_\eta(\xi):=\sqrt{c_\eta}\Phi_j(\eta\cdot\xi),\quad\eta\in\mathcal{X}_j.
\end{equation}

Adding all up we have the following decomposition result.

\begin{theorem}
Let $f\in L^p(\mathbb{S}^d)$, $1\leqslant p\leqslant\infty$. Then 
\begin{equation}\label{decomposition}
f=\sum_{\eta\in\mathcal{X}}\langle f,\varphi_\eta\rangle\varphi_\eta\quad\text{in }L^p(\mathbb{S}^d).
\end{equation}
\end{theorem}

\begin{proof}[Sketch of proof]
Using the identity $f=\dst\sum_{j=0}^\infty\Phi_j\ast\overline{\Phi}_j\ast f$, we decompose $\Phi_j\ast\overline{\Phi}_j(\xi\cdot\bullet)$ for each $j$ with Theorem \ref{curvature} and then we sum all over $\mathcal{X}=\dst\bigcup_{j=0}^\infty\mathcal{X}_j$ to get (\ref{decomposition}). The details of the proof can be found in \cite[Proposition 3.2, p. 542]{Naretal}.
\end{proof}

The main difference that needlets have with respect to wavelets is that their localization is only measured in terms of a decay property and not by their support. 
More precisely, they satisfy the following condition: for every $k\geq0$, there exists a constant $c_k$
such thet
\begin{equation}\label{size}
|\varphi_\eta(\xi)|\leqslant\frac{c_k2^{jd/2}}{(1+2^j\d(\xi,\eta))^k},\quad\forall\xi\in\mathbb{S}^d.
\end{equation}
On the other hand, there exists $\kappa$ such that, for every $j\geq 0$,
if $\d(\xi,\theta)\leq \kappa 2^{-j}$ and $\eta\in\xx_j$
\begin{equation}\label{sizelip}
|\varphi_\eta(\xi)-\ffi_\eta(\theta)|\leqslant\frac{c_k2^{jd/2} 2^j\d(\xi,\theta)}{(1+2^j\d(\xi,\eta))^k}.
\end{equation}

We can now define the Besov spaces in $\mathbb{S}^d$. Again, we follow \cite{Naretal}.

\begin{definition}
Given $0<p,q\leqslant\infty$ and $s\in\mathbb{R}$, the Besov space $B^s_{p,q}(\mathbb{S}^d)$ is defined as the set of all $f\in\mathcal{S}'$ such that the norm 
\begin{multline}
	\|f\|_{B^s_{p,q}}\\:=\left(\sum_{j=0}^\infty\left[2^{j(s+d/2-d/p)}\left(\sum_{\eta\in\mathcal{X}_j}|\langle f,\varphi_\eta \rangle|^p\right)^{1/p}\right]^q\right)^{1/q}
\end{multline}
is finite.
As usual, the $\ell^p,\ell^q$ norms are replaced by the sup-norms when $p=\infty$ or $q=\infty$.
\end{definition}

Recall that 
\begin{enumerate}
	\item $B^{d/p}_{p,1}(\S^d)\subset\cc(\S^d)$ is a space of continuous functions;
	\item $B^{s'}_{p,q'}\subset B^s_{p,q}$ when $s'>s$;
	\item $B^s_{p,q'}\subset B^s_{p,q}$ when $q'>q$;
\end{enumerate}

\section{Sampling on the sphere.}

\begin{theorem}
\label{sampling}
Let $1\leqslant p\leqslant\infty$ and $s\geq d/p$.
Fix $\epsilon>0$ and
let $\{\eta_1,\dots,\eta_{N_\epsilon}\}$ be a set of almost uniformly $\epsilon$-distributed points. 
Then there exist constant $c_1,c_2$ depending only on $d$, and a constant $M$ depending on $d$, $p$ such that,
if $f\in B^{s}_{p,1}(\mathbb{S}^d)$ with
 $\|f\|_{B^{s}_{p,1}}\leqslant M^{-1}\min(\eps^{-1/p},\eps^{d/p-s})\|f\|_{L^p}$ then 
$$
\frac{c_1}{\eps^{d/p}}\|f\|_{L^p}
\leqslant\left(\sum_{l=1}^{N_\epsilon}|f(\eta_l)|^p\right)^{1/p}\leqslant\frac{c_2}{\eps^{d/p}}\|f\|_{L^p}.
$$
\end{theorem}

\begin{proof}
Let $\{R_1,\dots,R_{N_\epsilon}\}$ be the partition of $\S^d$  associated to $\{\eta_1,\dots,\eta_{N_\epsilon}\}$. 
As $B_{a_l}(c^*\eps)\subset R_l\subset B_{a_l}(c^{**}\eps)$,
$c_1\eps^d\leq\sigma(R_l)\leq c_2\eps^d$ so that it is enough to establish
that
$$
\frac{1}{2}\|f\|_{L^p}
\leqslant\left(\sum_{l=1}^{N_\epsilon}|f(\eta_l)|^p\sigma(R_l)\right)^{1/p}\leqslant\frac{3}{2}\|f\|_{L^p}.
$$

From (\ref{decomposition}) we may write $f\in B^{d/p}_{p,1}(\mathbb{S}^d)$ as
$$
f=\sum_{j=0}^\infty\sum_{\eta\in\mathcal{X}_j}\langle f,\varphi_\eta\rangle\varphi_\eta
$$
where $\varphi_\eta$ are the needlets defined in (\ref{needlet}). Write
$$
E_j(f)=\left(\sum_{\eta\in\mathcal{X}_j}|\langle f,\varphi_\eta \rangle|^p\right)^{1/p}
$$
Then, we have the estimate
\begin{multline}
\label{eq:III1}
|f(\zeta)-f(\eta_l)|\leqslant\sum_{j=0}^\infty\sum_{\eta\in\mathcal{X}_j}|\langle f,\varphi_\eta \rangle||\varphi_\eta(\zeta)-\varphi_\eta(\eta_l)|\\\leqslant\sum_{j=0}^\infty\left(\sum_{\eta\in\mathcal{X}_j}|\varphi_\eta(\zeta)-\varphi_\eta(\eta_l)|^{p'}\right)^{1/p'}E_j(f)
\end{multline}
for any given $x\in\mathbb{S}^d$. 

We will need two estimates for which we give the proof after showing that they imply the result.

\smallskip

\noindent{\bf Claim 1.} {\sl For every $j\geqslant0$, and every $\zeta\in S^d$,
\begin{equation}\label{brutal}
\left(\sum_{\eta\in\mathcal{X}_j}|\varphi_\eta(\zeta)|^{p'}\right)^{1/p'}\leqslant C_p2^{jd/2}
\end{equation}
where $C_p$ depends on $d$ and $p$.}

\smallskip

In particular,
\begin{multline}
\label{eq:est1}
\left(\sum_{\eta\in\mathcal{X}_j}|\varphi_\eta(\zeta)-\varphi_\eta(\eta_l)|^{p'}\right)^{1/p'}\\
\leqslant 2C_p2^{jd/2}\leqslant C_p2^{-j_0(s-d/p)}2^{j(s+d/2-d/p)}
\end{multline}
if $2^j\geq 2^{j_0}$ with $j_0$ to be chosen later.

Note also that Claim 1 implies
that $\|f\|_{L^\infty}\leqslant C_p\|f\|_{B^{d/p}_{p,1}}$
which is the inclusion $B^{d/p}_{p,1}(\S^d)\subset L^\infty(S^d)$.

\smallskip

\noindent{\bf Claim 2.} {\sl For every $j$, such that $2^j\leq\kappa\eps^{-1}$ and every $\zeta\in B_{\eta_l}(\eps)$
\begin{equation}\label{brutal2}
\left(\sum_{\eta\in\mathcal{X}_j}|\varphi_\eta(\zeta)-\varphi_\eta(\eta_l)|^{p'}\right)^{1/p'}\leqslant C_p2^{jd/2} 2^j\d(\zeta,\eta_l)
\end{equation}
where $C_p$ depends on $d$ and $p$.}

\smallskip

In particular, if $2^{j_0}\leq\kappa\eps^{-1}$, \eqref{eq:III1} reads
\begin{multline}
\label{eq:III5}
|f(\zeta)-f(\eta_l)|\leqslant C_p\sum_{j=0}^{j_0}2^{jd/2} 2^j\d(\zeta,\eta_l)E_j(f)\\
+C_p2^{-j_0(s-d/p)}\sum_{j=j_0+1}^\infty 2^{j(s+d/2-d/p)}E_j(f).
\end{multline}
Then, taking $L^p(R_l)$-norms and using the triangular inequality, we get
\begin{multline*}
\left(\int_{R_l}|f(\zeta)-f(\eta_l)|^p\d \sigma(\zeta)\right)^{1/p}\\
\leqslant
C_p\sum_{j=0}^{j_0}2^{jd/2} 2^j\left(\int_{R_l}\d(\zeta,\eta_l)^p\d\sigma)\zeta)\right)^{1/p}E_j(f)
\\
+C_p2^{-j_0(s-d/p)}\sigma(R_l)^{1/p}\sum_{j=j_0+1}^\infty 2^{j(s+d/2-d/p)}E_j(f)\\
\leqslant
C_p\sum_{j=0}^{j_0}2^{jd/2} 2^j c_d\eps^{\frac{d+p+1}{p}}E_j(f)
\\
+C_p2^{-j_0(s-d/p)}\eps^{d/p}\sum_{j=j_0+1}^\infty 2^{j(s+d/2-d/p)}E_j(f)\\
\end{multline*}
since $R_l\subset B_{\eta_l}(\eps)$. And finally, taking $2^{j_0}\sim\eps^{-1}$
\begin{multline}
\label{eq:III6}
\left(\int_{R_l}|f(\zeta)-f(\eta_l)|^p\d \sigma(\zeta)\right)^{1/p}\\
\leqslant
C_p2^{j_0}\eps^{1+1/p}\eps^{d/p}\sum_{j=0}^{j_0 }2^{j(s+d/2-d/p)}E_j(f)
\\
+C_p2^{-j_0(s-d/p)}\eps^{d/p}\sum_{j=j_0+1}^\infty 2^{j(s+d/2-d/p)}E_j(f)\\
\leqslant
C_p\max(\eps^{1/p},\eps^{s-d/p})\eps^{d/p}\|f\|_{B^{s}_{p,1}}
\end{multline}
From the triangular inequality,
\begin{multline*}
\left|\left(\int_{R_l}|f(\zeta)|^p\d \sigma(\zeta)\right)^{1/p}-|f(a_l)|\sigma(R_l)^{1/p}\right|\\
\leqslant  C_p\max(\eps^{1/p},\eps^{s-d/p})\epsilon^{d/p}\|f\|_{B^{s}_{p,1}}.
\end{multline*}


Next, taking $\ell^p$-norms over $l=1,\ldots,N_\eps$ and using the triangular inequality
\begin{multline*}
\left|\|f\|_{L^p}-\left(\sum_{l=1}^{N_\epsilon}|f(\eta_l)|^p\sigma(R_l)\right)^{1/p}\right|\\
=\left|\norm{\left(\int_{R_l}|f(\zeta)|^p\d \sigma(\zeta)\right)^{1/p}}_{\ell^p_{N_\eps}}\right.\\
\qquad-\left.\norm{|f(\eta_l)|\sigma(R_l)^{1/p}}_{\ell^p_{N_\eps}}\right|\\
\leqslant \norm{\left(\int_{R_l}|f(\zeta)|^p\d \sigma(\zeta)\right)^{1/p}-|f(\eta_l)|\sigma(R_l)^{1/p}}_{\ell^p_{N_\eps}}\\
\leqslant C_p\max(\eps^{1/p},\eps^{s-d/p})\epsilon^{d/p}\|f\|_{B^{s}_{p,1}}N_\eps^{1/p}\\
\leq C_p(c^{**})^{1/p}\max(\eps^{1/p},\eps^{s-d/p})\|f\|_{B^{s}_{p,1}}
\end{multline*}
with Property (iii) of Lemma \ref{epsilon-distributed}. 

Then, from Lemma \ref{epsilon-distributed} we get
\begin{multline*}
\left(\sum_{l=1}^{N_\epsilon}|f(\eta_l)|^p\sigma(R_l)\right)^{1/p}\\
\leqslant
C_p(c^{**})^{1/p}\max(\eps^{1/p},\eps^{s-d/p})\|f\|_{B^{s}_{p,1}}+\|f\|_{L^p}
\end{multline*}
while
\begin{multline*}
\left(\sum_{l=1}^{N_\epsilon}|f(\eta_l)|^p\sigma(R_l)\right)^{1/p}\\\geqslant\|f\|_{L^p}-C_p(c^{**})^{1/p}\max(\eps^{1/p},\eps^{s-d/p})\|f\|_{B^{s}_{p,1}}.
\end{multline*}
Therefore, if $\|f\|_{B^{s}_{p,1}}\leqslant M^{-1}\min(\eps^{-1/p},\eps^{d/p-s})\|f\|_{L^p}$
with $M=2C_p(c^{**})^{1/p}$,
we get
$$
\frac{1}{2}\|f\|_{L^p}
\leqslant\left(\sum_{l=1}^{N_\epsilon}|f(\eta_l)|^p\sigma(R_l)\right)^{1/p}
\leqslant\frac{3}{2}\|f\|_{L^p}.
$$
Finally, as $c_1\eps^d\leq\sigma(R_l)\leq c_2\eps^d$ we obtain the theorem,
once the claims are proved.
\end{proof}

\begin{proof}[Proof of the Claims]
Let us first prove  (\ref{brutal}). Using the size condition (\ref{size}) for $\varphi_\eta$  with $k=d+1$ we have that
\begin{multline*}
\left(\sum_{\eta\in\mathcal{X}_j}|\varphi_\eta(\zeta)|^{p'}\right)^{1/p'}\\
\leqslant c_{d+1}2^{jd/2}\left(\sum_{\eta\in\mathcal{X}_j}\frac{1}{(1+2^j\d(\zeta,\eta))^{(d+1)p'}}\right)^{1/p'}.
\end{multline*}

The proof of the second claim is then exactly the same with \eqref{sizelip}
replacing \eqref{size}

So, in order to get (\ref{brutal}), it is enough to prove that the sum on the right hand side is bounded by a constant depending only $d$ and $p$. To that end, define for each $\eta\in\mathcal{X}_j$, $G_\eta:=B_\eta(c^\ast2^{-j})$ the ball in (ii) of Lemma \ref{epsilon-distributed}. 
The triangular inequality shows that
$$
1+2^j\d(\zeta,\eta)\geqslant (1-c^*)\max_{\theta\in G_\eta}(1+2^j\d(\zeta,\theta)).
$$
And then, as $\{G_\eta\}_{\eta\in\mathcal{X}_j}$ is a family of disjoint sets of measure $(c^\ast)^d2^{-jd}$, summing over all $\mathcal{X}_j$ gives us
\begin{multline*}
\sum_{\eta\in\mathcal{X}_j}\frac{1}{(1+2^j\d(\zeta,\eta))^{(d+1)p'}}\\
\leqslant 
\sum_{\eta\in\mathcal{X}_j}\frac{(1-c^*)^{-(d+1)p'}}{\sigma(G_\eta)}\int_{G_\eta}
\frac{1}{(1+2^j\d(\zeta,\theta))^{(d+1)p'}}\d\sigma(\theta)\\
\\
\leqslant (1-c^*)^{-(d+1)p'}\int_{\mathbb{S}^d}\frac{2^{jd}}{(1+2^j\d(\zeta,\theta))^{(d+1)p'}}\,\mathrm{d}\sigma(\theta)\\
\leqslant c_p(1-c^*)^{-(d+1)p'}
\end{multline*}
by standard calculus. This completes the proof of the claim and thus of the theorem.
\end{proof}



Taking $\ell^p$-norms over $l=1,\ldots,N_\eps$ in \eqref{eq:III6},
we obtain the following result:

\begin{corollary}
Let $1\leqslant p\leqslant\infty$ and $s\geq d/p$.
Fix $\epsilon>0$ and
let $\{\eta_1,\dots,\eta_{N_\epsilon}\}$ be a set of almost uniformly $\epsilon$-distributed points and let $\{R_1,\dots,R_{N_\epsilon}\}$ be the associated partition of $\S^d$. 
Then there exists a constant $C_p$ only on $d$ and $p$, and a constant $M$ depending on $d$, $p$ such that,
if $f\in B^{s}_{p,1}(\mathbb{S}^d)$ 
\begin{multline}
\int_{\S^d}\abs{f(\zeta)-\sum_{l=1}^{N_\eps}f(\eta_l)\mathbf{1}_{R_l}(\zeta)}^p\d\sigma(\zeta)\\
\leqslant
C_p\max(\eps,\eps^{sp-d})\|f\|_{B^{s}_{p,1}}
\end{multline}
\end{corollary}

%A trivial observation is that we can reduce the factors on which $N$ depends to just $d$ by simply choosing $\epsilon=1$. 

%We should now explain why putting $d$ as the exponent in the Besov space instead of $n/p$ or any other does not mean asking more regularity.

As the needlets $\varphi_\eta$ are continuous functions (moreover they are polynomials) the same computations above and the fact the $\mathbb{S}^d$ is compact show that every $f\in B^{d/p}_{p,1}(\mathbb{S}^d)$ is continuous.

\section{Conclusion and future work}

In this paper, we have used the needlet decomposition of Besov spaces to establish a sampling theorem in $B_{p,1}^s$ when the smootheness index is large enough. This opens the path to future work in two directions:

-- establish efficient algorithms for reconstructions of function on a sphere from their samples;

-- extend this work to more general compact Riemannian manifolds for which needlet like decompositions have been established in \cite{GP,MM} and
then to more general homogeneous spaces using wavelet decompositions like those given in \cite{FH}.


\begin{thebibliography}{11}

\bibitem{FD}
\textsc{P. Auscher \& T. Hytonen}
\newblock{\em Orthonormal bases of regular wavelets in spaces of homogeneous type.}
{Applied and Computational Harmonic Analysis} {\bf 34} (2013), 266--296.

\bibitem{DH}
\textsc{D. Deng \& D. Dai},
\newblock{\em 
Approximation Theory and Harmonic Analysis on Spheres and Balls.} Springer Monographs in Math, 2013, Springer, New York.

\bibitem{FH}
\textsc{F. Feng \& Y. Han},
\newblock{\em Harmonic Analysis on Spaces of Homogeneous Type.}
Springer Lecture Notes in Math {\bf 1966}, 2009, Springer, New York.

\bibitem{GP}
\textsc{D. Geller \& I. Pesenson},
\newblock{\em Band-limited localized Parseval frames and Besov spaces on compact homogeneous manifolds.}
{Journal of Geometric Analysis} {\bf 21} (2011), 334--371.

\bibitem{JM}
\textsc{Ph. Jaming \& E. Malinnikova},
\newblock{\em An uncertainty principle and sampling inequalities in Besov spaces.}
{Journal of Fourier Analysis and Applications} {\bf 22} (2016), 768--786.

\bibitem{MM}
\textsc{M. Maggioni \& H.\,N. Mhaskar},
\newblock{\em Diffusion Polynomial Frames on measure metric spaces.}
{Applied and Computational Harmonic Analysis} {\bf 24} (2007),   329--353.

\bibitem{Naretal2}
\textsc{H. Mhaskar, F. Narcowich \& J. Ward},
\newblock{\em Spherical Marcinkiewicz-Zygmund inequalities and positive quadrature.}
{Journal of Mathematics of Computation} {\bf 70} (2001), 1113--1130.

\bibitem{Naretal}
\textsc{F. Narcowich, P. Petrushev \& J. Ward},
\newblock{\em Decomposition of Besov and Triebel–Lizorkin spaces on the sphere.}
{Journal of Functional Analysis} {\bf 238} (2006), 530--64.

\bibitem{SW}
\textsc{E.\,M. Stein \& G. Weiss},
\newblock{\em Introduction to Fourier Analysis on Euclidean spaces.}
Princeton University Press, 1971.
\end{thebibliography}
\end{document}
