text:
\begin{document}
\begin{abstract}
We present and prove a Newton-Kantorovitch method for solving decoupled forward-backward stochastic differential equations
(FBSDEs) involving smooth coefficients with uniformly bounded derivatives.
As Newton's method is required a suitable initial condition to converge, we show that such initial conditions are solutions of a linear backward stochastic differential equation.
In addition, we show that converges linearly to the solution.

\end{abstract}
\keywords{

Forward-Backward stochastic differential equations, \
Stochastic differential equations, \
Newton-Kantorovitch method, \
Rate of convergence}

\subjclass[2010]{
Primary {49M15}, \

Secondary {65C30}
}

\maketitle

\section{Introduction}
In this paper, we study a method of approximating non-Markovian and decoupled forward-backward stochastic differential equations (FBSDEs) of the following form for arbitrary $T > 0$:
\begin{equation}\label{fbsde1 decoupled}
\begin{split}
	X (t) &= X(0)+ \int_0^t  b (s,X(s))  \ds +\int_0^t \sigma (s, X (s))  \dBs, \\
	Y (t) &=  \varphi \left(X(T) \right) +\int_t^T f (s,X(s),Y(s),Z(s))  \ds - \int_t^T Z(s)\dBs,
\end{split}
\end{equation}
where the solution triples $(X,Y,Z)\equiv  \left(X(t), Y(t), Z(t) \right)_{t \in [0, T]}$
take values in $\mathbb{R}^\dimX \times \mathbb{R}^{\dimY} \times \mathbb{R}^{\dimZ}$,
$W$ is a $\dimB$-dimensional Wiener process, and $b, f$, $\sigma$, and $\varphi$ are measurable functions
that could in general be random and defined on a probability space.

We propose a scheme for approximating such FBSDEs with random coefficients based on applying the Newton-Kantorovitch theory.
Unlike a four-step scheme that relies on the Markov structure
(see e.g., Ma, Protter and Yong \cite{Ma1994fourstepscheme}, and Delarue \cite{Delarue2002209}),
this method allows us to find a non-Markovian approximation.
In addition, as our approach is a type of contraction mapping \cite{antonelli1993, PardouxTang1999},
the approximation works for arbitrary large durations with smooth random coefficients, and with monotonicity conditions;
for details,  see Hu and Peng \cite{HuPeng1995}, Peng and Wu \cite{PengWu1999Themethodofcontinuation}, and Yong \cite{Yong1997methodofcontinuation}.
We also refer readers to \cite{Zhang2017zbMATH06738088, MaZhang2012}
for more details about the uniqueness and the existence of FBSDE solutions.

Most numerical algorithms for FBSDEs are based on time-space discretization schemes \cite{delarue2006}
for quasi-linear parabolic partial differential equations
for coupled FBSDEs with monotonicity condition \cite{benderZhang2008}.
In contrast, to the best of our knowledge, very little has been published on state space discretization based approaches.
Vidossich proved that the Chaplygin and Newton methods are equivalent for ordinary differential equations \cite{Vidossich1978188},
and Kawabata and Yamada studied a state space discretization based on Newton-Kantorovitch approach
for stochastic differential equations (SDEs) \cite{KYnewton91zbMATH00019571}.
Ouknine \cite{Ouknine1993doi:10.1080/17442509308833863} showed that the coefficients can be relaxed by a linear growth condition.
Amano
obtained a probabilistic second-order error estimate \cite{Amano12zbMATH06028640}.
Wrzosek \cite{Monika2012MR2967195} extended to stochastic functional differential equations.

The aim of this paper is
to formulate Newton-Kantorovitch  approximation of the decoupled multi-dimensional FBSDEs with random coefficients  and
to show that it converges globally \eqref{Theorem: the linear convergence inequality FBSDE}
 as follows:
\begin{Thm}\label{Theorem: the convergence of the Newton-Kantorovitch approximation process3}
Suppose that
$b, \sigma, f$, and $\varphi$ are all $C^1$, their derivatives are uniformly bounded $(s,\omega)$-a.e.,
and $b, \sigma$, and  $f$ are square-integrable w.r.t. their time variables.
Then, there exists a positive constant $C>0$ such that
\begin{equation}\label{Theorem: the linear convergence inequality FBSDE}
\begin{split}
	\| (X -{X}_{n+1},Y - Y_{n+1}, Z - Z_{n+1} )\|
	\leq  C2^{-n}
	\quad n \in \mathbb{N} \cup \{0\}.
\end{split}
\end{equation}
\end{Thm}
As pointed out in \cite{KarouiPengel1997backward, BahlaliEddahbiandOuknine2017AOP},
solutions $(X,Y,Z)$ of decoupled FBSDEs can be viewed as fixed points of a mapping.
Here, we consider an alternative mapping $\NewtonF_{\varphi} : \mathbb{S}^{2}_{\dimX} \times \mathbb{S}^{2}_{\dimY} \times \mathbb{H}^2 \to \mathbb{S}^{2}_{\dimX} \times \mathbb{L}^2_T$ inspired by a one-dimensional analog of \cite{KYnewton91zbMATH00019571, Niwa2003}, as follows.
For given $\varphi$ and $u=(x, y, z)\in \mathbb{S}^{2}_{\dimX} \times \mathbb{S}^{2}_{\dimY} \times \mathbb{H}^2$,
we define
\begin{equation}
\begin{split}\label{Def: F in BSDEs}
	\NewtonF_{\varphi} (u)(t)
	=
	\begin{pmatrix}
	\displaystyle x(t) - x(0) -\int_0^t b(s, x(s)) \ds - \int_0^t  \sigma(s,x(s)) \dBs\\
	\displaystyle y (t) - \varphi(x(T))  -\int_t^T f (s, u(s)) \ds + \int_t^T  z (s) \dBs
	\end{pmatrix}^\top
	.
\end{split}
\end{equation}

Then, for any $(X_{0}, Y_{0}, Z_{0}) \in \mathbb{S}^{2}_{\dimX} \times \mathbb{S}^{2}_{\dimY} \times \mathbb{H}^2$ with $X_0(0)=X(0)$ and assuming that the driver $f$ is smooth, the Newton-Kantorovitch approximation process is given by
\begin{equation}
\begin{split}\label{equation: backward Newton-Kantorovitch def}
	\NewtonF_{\varphi}(X_{n},Y_{n},Z_{n}) +\NewtonF_{\varphi}' (X_{n},Y_{n},Z_{n}) (X_{n+1}-X_{n},Y_{n+1}-Y_{n},Z_{n+1}-Z_{n}) =0,
	\\ X_{n+1}(0)=X (0),
\end{split}
\end{equation}

for $n \in \mathbb{N} \cup \{0\}$,
where $\NewtonF'_{\varphi}$ stands for G\^ateaux derivative.
This sequence is well-posed iff a unique system of linear backward stochastic differential equations (BSDEs) formally by Theorem \ref{Theorem: linear BSES characerlization}.
Note that, if the given duration $T$ is arbitrarily, then, even for linear FBSDEs with constant coefficients,
the necessary and sufficient conditions become more complicated
when the diffusion coefficients also depend on $z$,
as was pointed out by Ma, Wu, Zhang and Zhang \cite{FBSDEMaWuZhangZhangzbMATH06464848}.

In this paper, we focus on decoupled FBSDEs and obtain the convergence result, Theorem \ref{Thm: Newton-Kantorovitch BSDE}.

The rest of this paper is structured as follows.
Section \ref{Preliminaries} introduces the notations and assumptions used.
Section \ref{Newton-Kantorovitch  scheme for BSDEs} is devoted to
formulating the Newton-Kantorovitch approximation process.
Finally,
Section \ref{Convergence of the Newton-Kantorovitch  approximation process for BSDEs}
proves the main theorem for the decoupled FBSDEs.

\section{Preliminaries}\label{Preliminaries}
For $x, y \in \mathbb{R}^\dimX$, $|x|$ denotes the Euclidian norm
and $\langle x, y \rangle$ denotes the inner product.
Matrixes size of $\dimZ$ will be represented as an element $y \in \mathbb{R}^{\dimZ}$,
whose Euclidean norms are also given by $|y| = \sqrt{y y^\top}$ and for which $\langle y, z\rangle = \mathrm{trace}(yz^\top)$
where $A^\top$ is the transpose matrix of $A$.
In this paper, we only consider the derivatives with respect to the space variable.

We also use the following notation, based on that in \cite{Pardoux2014zbMATH06276084}.
Let $(\Omega , \mathcal{F}, \mathbb{P})$ be a complete probability space and $\left( \mathcal{F}_t \right)_{t \geq 0 }$ be a Brownian filtration.
$\mathcal{P} =\mathcal{P}(\left( \mathcal{F}_t \right)_{t \geq 0 })$ is the $\sigma$-algebra of
the progressively measurable subset
$A \subset \Omega \times [0, \infty)$ such that, for all $t \geq 0$, $A \cap ( [0, t] \times \Omega) \in \mathcal{B} [0,t] \otimes  \mathcal{F}_t $.

Let $T>0$ be a fixed, and final, deterministic time.
For $\dimY, \dimB \in \mathbb{N}$, we define
\begin{align*}
	\mathbb{L}^{2}
	&=  \left\{ \xi : \Omega  \to \mathbb{R}^\dimY
	\text{ is $\mathcal{F}_T$-measurable and }
	\| \xi\|_{\mathbb{L}^2}= \left\{ \mathbb{E} \left[ |\xi |^2 \right] \right\}^{\frac{1}{2}}  <\infty \right\},\\
	\mathbb{L}^{2}_{T}
	&=  \left\{ Y : \Omega \times [0,T]  \to \mathbb{R}^\dimY
	\text{ continuous}
	:Y(t) \in m\mathcal{F}_T, \forall t \in [0,T],~

	\| Y \|_{\mathbb{L}_T^{2}}

		 <\infty \right\},\\
	\mathbb{S}^{2}_{\dimY}
	&=  \left\{ Y : \Omega \times [0,T]  \to \mathbb{R}^\dimY

	\text{ continuous, adapted}:

		\| Y \|_{\mathbb{S}^{2}_{\dimY}}<\infty

		 \right\},
\\ 	\mathbb{H}^{2}
	&=  \left\{ Z : \Omega \times [0,T]  \to \mathbb{R}^{\dimZ}
	\text{ continuous, adapted}:

	{\| Z \|}_{\mathbb{H}^2}

	<\infty  \right\},
\end{align*}
where the norms $\|\cdot\|_{\mathbb{L}_T^{2}}$, $\|\cdot\|_{\mathbb{S}^{2}_{\dimY}}$, and ${\| \cdot \|}_{\mathbb{H}^2}$ are defined by
\begin{align*}
	\| Y \|_{\mathbb{L}_T^{2}}
	=\| Y \|_{\mathbb{S}^{2}_{\dimY}}
	=\left\{ \mathbb{E} \left[  \sup_{0 \leq s \leq T} |Y(s)|^2 \right] \right\}^{\frac{1}{2}},
	\quad
	{\| Z \|}_{\mathbb{H}^2}
	= \left\{  \mathbb{E} \left[ \int_0^T  |Z(s)|^2 \ds   \right] \right\}^{\frac{1}{2}}.
\end{align*}
For the sake of simplicity, we also write the operator norm of the operator $A$ as $\| A \|$.
The Banach spaces $\mathbb{S}^{2}_{\dimY} \times \mathbb{H}^{2}$ and $\mathbb{S}^{2}_{\dimX}$ are defined by
\[
	\| (Y,Z)\|^2 = \|Y\|_{\mathbb{S}^{2}_{\dimY}}^2+\| Z\|_{\mathbb{H}^2}^2, \quad
	\| X\|^2 = \|X\|_{\mathbb{S}^{2}_{\dimX}}^2.
\]
For $\alpha \in \mathbb{R}$,
we introduce the weighted norm
\[
	\| (Y,Z)\|_{\alpha}^2 =

	\mathbb{E} \left[  \sup_{0 \leq s \leq T}e^{\alpha s} |Y(s)|^2 \right]
	+ \mathbb{E} \left[ \int_0^T  e^{\alpha s}|Z(s)|^2 \ds   \right].
\]
For $p,q \in \mathbb{N}$, $C^k (\mathbb{R}^p, \mathbb{R}^q)$ is the set of functions of class $C^k$ from $\mathbb{R}^p$ to $\mathbb{R}^q$,
and $C^k_b (\mathbb{R}^p, \mathbb{R}^q)$ is the subset of these functions whose partial derivatives of order at most of the $k$ values are bounded.
When the domain and range dimensions are clear based on context and
when there is no risk of confusion, we often eliminate the spaces to simplify the notation.

For a smooth $g$ such that $g(\cdot,\cdot, \cdot) \in C^1 (\mathbb{R}^p \times \mathbb{R}^q \times \mathbb{R}^r , \mathbb{R}^q)$, it is convenient to obtain a concrete representation of ${g}' : \mathbb{R}^{p} \times \mathbb{R}^{q} \times \mathbb{R}^{r} \to \mathbb{R}^{q}$.
The Fr\'echet derivative  at $u\in \mathbb{R}^{p} \times \mathbb{R}^{q} \times \mathbb{R}^{q}$ is the matrix representation of $g'(u)$ \cite[page 60]{Ortega1970MR0273810}
and it can be obtained using the Jacobian matrix:
\begin{equation}
\begin{split}\label{notation: The Mean value theorem in the Banach space}
	g(u+\Delta u )-g(u)={g}'  (u)\Delta u +\mathrm{R}_{g}\left(u \right)\Delta u , \quad \Delta u  \in \mathbb{R}^{p} \times \mathbb{R}^{q} \times \mathbb{R}^{r}
\end{split}
\end{equation}
where the Lagrange remainder is given by
\begin{align*}
\mathrm{R}_{g} (u)\Delta u  =
	\left( \int_0^1  \left\{ {g}'  \left(u+ \theta \Delta u \right) - {g}'  (u) \right\}\mathrm{d}\theta \right)\Delta u.
\end{align*}
Notice that, for all $u=(x,y,z)^\top , \ \Delta u = (\Delta x,\Delta y ,\Delta z )^\top\in\mathbb{R}^p \times \mathbb{R}^q \times \mathbb{R}^{r}$,
\begin{equation}\label{notation: linearity of the Jacobian matrix}
	{g}' (u)\Delta u= {g}'_x (u) \Delta x +{g}'_y (u) \Delta y  +{g}'_z (u) \Delta z,
\end{equation}
where we obtain set ${g}'_x (u):\mathbb{R}^p \to \mathbb{R}^p \times \mathbb{R}^p$ such that ${g}'_x (u) \Delta x =\left( \frac{\partial}{\partial x_j} g^{(i)} (x,y,z) \Delta x^{(i)}   \right)_{i \leq p, \ j \leq p}$ where $\Delta x^{(i)}$ stands for the $i$th component for $i \leq p$.
We define ${g}'_y$ and ${g}'_z$, similarly.
Finally, for all $s \in [0,T]$, we define
\begin{equation*}
	 \| {g}'  \|_{\infty}
	  = \sup_{(s,x,y,z) \in [0,T] \times \mathbb{R}^{p} \times \mathbb{R}^{q} \times \mathbb{R}^{r} } | {g}'(s,x,y,z) |,
\end{equation*}
for $g(s, \cdot, \cdot, \cdot) \in C^1_b (\mathbb{R}^p \times \mathbb{R}^q \times \mathbb{R}^r, \mathbb{R}^q)$.

\section{Newton-Kantorovitch scheme for FBSDEs}\label{Newton-Kantorovitch  scheme for BSDEs}
In this section, we formulate the Newton-Kantorovitch scheme of the following system of FBSDEs:
\begin{equation}\label{bsde0}
\begin{split}
X (t) &= X(0)+ \int_0^t  b (s,X(s))  \ds +\int_0^t \sigma (s, X (s))  \dBs, \\
Y (t) &=  \varphi \left(X(T) \right) +\int_t^T f (s,X(s),Y(s),Z(s))  \ds - \int_t^T Z(s)\dBs, \\
\end{split}
\end{equation}
where the solutions $(X,Y,Z) = \left(X(t),Y(t), Z(t) \right)_{t \in [0, T]}$ take values in $\mathbb{R}^{\dimX} \times \mathbb{R}^{\dimY} \times \mathbb{R}^{\dimZ}$, $W$ is the $\dimB$-dimensional Wiener process, and the (progressively) measurable functions $b$, $f$, $\sigma$ and $\varphi$ are defined on the probability space $(\Omega, \mathcal{F}, \left(\mathcal{F}_t\right)_{t \geq 0}, \mathbb{P})$.

In this paper, we also assume the following.
\begin{itemize}
\item $X(0): \Omega \to \mathbb{R}^\dimX$ is an $\mathcal{F}_0$-measurable and square-integrable random vector.
\item $b : [0,T] \times \Omega \times \mathbb{R}^{\dimX}  \to  \mathbb{R}^{\dimX}$
	is $\mathcal{P} \otimes \mathcal{B} (\mathbb{R}^{\dimX})$-measurable.
\item $\sigma: [0,T]  \times \Omega  \times \mathbb{R}^{\dimX}  \to  \mathbb{R}^{\dimX \times \dimB} $
	is
	$\mathcal{P} \otimes \mathcal{B} (\mathbb{R}^{\dimX})$-measurable.
\item There exists a constant $C>0$ such that, for any $x \in \mathbb{R}^{\dimX}$,
\begin{align*}
	| b (s,x) | &\leq |b (s,0) |+ C |x|, \quad \text{$(s,\omega)$-a.e., }  \\
	| \sigma (s,x) | &\leq |\sigma (s,0)|+C|x|, \quad \text{$(s,\omega)$-a.e. }
\end{align*}
\item $\varphi : \Omega \times \mathbb{R}^{\dimX} \to \mathbb{R}^{\dimY}$ is $\mathcal{F}_T \otimes \mathcal{B} (\mathbb{R}^{\dimX})$-measurable.
\item $f: [0,T] \times \Omega \times \mathbb{R}^{\dimX} \times  \mathbb{R}^{\dimY} \times \mathbb{R}^{\dimZ} \to  \mathbb{R}^{\dimY}$
	is $\mathcal{P} \otimes \mathcal{B} (\mathbb{R}^{\dimY}) \otimes \mathcal{B} ( \mathbb{R}^{\dimZ} )$-measurable.
\item
There exists a constant $C>0$ such that for any $(x,y,z) \in \mathbb{R}^{\dimX} \times \mathbb{R}^{\dimY} \times \mathbb{R}^{\dimZ}$,
\begin{align*}
	| f (s,x,y,z) | &\leq |f (s,0,0,0) |+ C \left( |x|+|y|+ |z| \right),\quad \text{$(s,\omega)$-a.e. }\\
	| \varphi(x)| &\leq |\varphi(0)| + C|x|,\quad \text{$\omega$-a.e. }
\end{align*}
\end{itemize}
In addition, in the BSDE,
\begin{equation*}
\begin{split}
Y (t) &=  \xi +\int_t^T f (s,Y(s),Z(s))  \ds - \int_t^T Z(s)\dBs,
\end{split}
\end{equation*}
we replace the above assumption on $\varphi$ with the following condition:
\begin{itemize}
\item $\xi: \Omega \to \mathbb{R}^\dimY$ is an $\mathcal{F}_T$-measurable and square integrable random vector;
$\xi \in \mathbb{L}^2$.
\end{itemize}

We also introduce the following assumptions.
\begin{Ass}\label{ass0}
	$b(\cdot,0),
	\sigma(\cdot,0),
	f(\cdot ,0,0,0) \in \mathbb{H}^2$, i.e.,
\begin{align*}
	\mathbb{E} \left[ \int_0^T \left\{ | b (s,0) |^2 + | \sigma (s,0) |+| f (s,0,0,0) |^2 \right\}\ds \right] <\infty
\end{align*}
and $\varphi(0) \in \mathbb{L}^2$.
\end{Ass}

\begin{Ass}\label{ass0+1}
$b (s, \cdot) \in C^1_b (\mathbb{R}^\dimX , \mathbb{R}^\dimX  )$,
$\sigma (s,\cdot )  \in C^1_b (\mathbb{R}^\dimX , \mathbb{R}^{\dimX \times \dimB}  )$, $f(s, \cdot, \cdot, \cdot) \in C^1_b (\mathbb{R}^\dimX \times \mathbb{R}^\dimY \times \mathbb{R}^\dimZ, \mathbb{R}^\dimY  ) , \

\text{$(s,\omega)$-a.e.}$
and $\varphi \in C^{1}_{b}(\mathbb{R}^{\dimX}, \mathbb{R}^{\dimY})$, $\omega$-a.e.
\end{Ass}

For given $\varphi$, we consider the operator $\NewtonF_{\varphi}$ (defined by \eqref{Def: F in BSDEs}), namely,
\begin{equation*}
\begin{split}
	\NewtonF_{\varphi} (u)(t)
	=
	\begin{pmatrix}
	\displaystyle x(t) - x(0) -\int_0^t b(s, x(s)) \ds - \int_0^t  \sigma(s,x(s)) \dBs\\
	\displaystyle y (t) - \varphi(x(T))  -\int_t^T f (s, u(s)) \ds + \int_t^T  z (s) \dBs
	\end{pmatrix}^\top,
\end{split}
\end{equation*}
for $u=(x,y, z)\in \mathbb{S}^{2}_{\dimX} \times \mathbb{S}^{2}_{\dimY} \times \mathbb{H}^2$.
As an immediate consequence of the result given Lemma 3.1 of \cite{KYnewton91zbMATH00019571},
we obtain the following corresponding result for FBSDEs.

\begin{Lem}\label{op_F}
If Assumption \ref{ass0} holds, then the operator $\NewtonF_{\varphi}$ defined by \eqref{Def: F in BSDEs} maps the space $ \mathbb{S}^{2}_{\dimX} \times \mathbb{S}^{2}_{\dimY} \times \mathbb{H}^2$ into $ \mathbb{S}^{2}_{\dimX} \times \mathbb{L}_T^{2}$ and $t \mapsto \NewtonF_{\varphi}(u) (t)$ is a continuous modification for $u \in \mathbb{S}^{2}_{\dimX} \times \mathbb{S}^{2}_{\dimY} \times \mathbb{H}^2$.
\end{Lem}
\begin{proof}
For any $u=(x,y,z) \in \mathbb{S}^{2}_{\dimX} \times \mathbb{S}^{2}_{\dimY} \times \mathbb{H}^2$, it follows, from $\|x\|_{\mathbb{S}_{\dimX}^2}<\infty$ and $\| z \|^2_{\mathbb{H}^2}<\infty$, that the It\^o integrals $t \mapsto \int_0^t \sigma(s,x(s)) \dBs$ and $t \mapsto \int_t^T z(s)  \dBs$, respectively, are continuous modifications.
By the Jensen inequality, we obtain
\begin{align*}
	&\mathbb{E} \left[  \int_0^t \left| b (s, x(s))\right|^2  \ds \right]
	\leq 2^{}\mathbb{E} \left[  \int_0^t | b (s, 0) |^2 \ds \right]+2^{}C^2T  \|x\|^2_{\mathbb{S}^{2}_{\dimX}}<\infty
\end{align*}
and
\begin{align*}
	&\mathbb{E} \left[  \int_t^T \left| f (s, x(s), y(s), z(s))\right|^2  \ds \right]
	\\&\leq 4^{}\mathbb{E} \left[  \int_t^T | f (s, 0, 0, 0) |^2 \ds \right]+4^{}C^2  \left( T  \{\|x\|^2_{\mathbb{S}^{2}_{\dimX}}+\|y\|^2_{\mathbb{S}^{2}_{\dimY}}\}+ \| z\|^2_{\mathbb{H}^2} \right)
	<\infty.
\end{align*}
By Doob's inequality and It\^o's isometry property,  there exists a $c>0$ such that
\begin{align*}
	&\mathbb{E} \left[ \sup_{0 \leq t \leq T} \left| \int_0^t \sigma(s,x(s))  \dBs \right|^2  \right] \\
	&\leq c \mathbb{E} \left[ \left| \int_0^T \sigma(s,x(s))  \dBs \right|^2  \right]\leq 2c \mathbb{E} \left[ \int_0^T | \sigma(s,0)|^2 \ds \right]+2c C^2 T\|x\|^2_{\mathbb{S}_{\dimX}}< \infty
\end{align*}
and
\begin{align*}
	&\mathbb{E} \left[ \sup_{0 \leq t \leq T} \left| \int_t^T z(s)  \dBs \right|^2  \right]
	\\&\leq c \mathbb{E} \left[ \left| \int_0^T z(s)  \dBs \right|^2  \right]
	= c  \mathbb{E} \left[ \int_0^T | z(s) |^2 \ds \right]< \infty.
\end{align*}
Using the Jensen inequality, we further obtain that
\begin{align*}
&\frac{1}{9}
 \mathbb{E} \left[ \sup_{0\leq t \leq T}| \NewtonF_{\varphi}(u)(t)|^2 \right]
\\&\leq
\|x\|^2_{\mathbb{S}^{2}_{\dimX}}
+\mathbb{E}[|x(0)|^2]
+\mathbb{E} \left[  \int_0^t \left| b (s, x(s))\right|^2  \ds \right]
+\mathbb{E} \left[ \sup_{0 \leq t \leq T} \left| \int_0^t \sigma(s,x(s))  \dBs \right|^2  \right] \\
&+\|y\|^2_{\mathbb{S}^{2}_{\dimY}}
+\mathbb{E}\left|[\varphi(0)|^2 + C|x(T)|^2 \right]
\\&+\mathbb{E}\left[ \left| \int_t^T f (s, x(s), y(s), z(s)) \ds \right|^2 \right]
+ \mathbb{E}\left[\sup_{0 \leq t \leq T} \left| \int_t^T z(s)  \dBs \right|^2  \right],
\end{align*}
which is bounded by the above estimates.
This completes the proof.
\end{proof}

The following lemma shows that the operator $\NewtonF_{\varphi}: \mathbb{S}^{2}_{\dimX} \times \mathbb{S}^{2}_{\dimY} \times \mathbb{H}^2 \to \mathbb{S}_{\dimX}^2 \times \mathbb{L}_T^{2}$ has a G\^ateaux derivative.
\begin{Lem}\label{Lem: the Gateaux derivative on BSDEs}
If Assumptions \ref{ass0} and \ref{ass0+1} hold, then, for all $u=(x,y,z) \in \mathbb{S}^{2}_{\dimX} \times \mathbb{S}^{2}_{\dimY} \times \mathbb{H}^2$,
the G\^ateaux derivative $\NewtonF_{\varphi}'(u): \mathbb{S}^{2}_{\dimX} \times \mathbb{S}^{2}_{\dimY} \times \mathbb{H}^2 \to \mathbb{S}_{\dimX}^2 \times \mathbb{L}_T^2$ of $\NewtonF_{\varphi}$ at $u \in \mathbb{S}^{2}_{\dimX} \times \mathbb{S}^{2}_{\dimY} \times \mathbb{H}^2$ in the direction $\overline{u}=(\overline{x},\overline{y},\overline{z})\in \mathbb{S}^{2}_{\dimY} \times \mathbb{H}^2$ exists and is given for any $t \in [0,T]$, by
\begin{align}\label{G_derivative}
	\NewtonF_{\varphi}'(u) \overline{u}(t)
	=
	\begin{pmatrix}
	\displaystyle
	\overline{x} (t)-\overline{x}(0)
	-\int_0^t b'_{x}  (s,x(s)) \overline{x} (s) \ds - \int_0^t \sigma'_{x} (s,x(s)) \overline{x} (s)  \dBs \\
	\displaystyle \overline{y}(t)
	-\varphi'(x(T)) \overline{x}(T)
	-\int_t^T {f}'  (s,u(s)) h (s) \ds + \int_t^T  \overline{z}(s)  \dBs
	\end{pmatrix}^{\top}.
\end{align}

\end{Lem}
\begin{proof}
We denote the right-hand side of \eqref{G_derivative} by $A(u) \overline{u}(t)$ for $\overline{u}=(\overline{x}, \overline{y},\overline{z})\in \mathbb{S}^{2}_{\dimX} \times \mathbb{S}^{2}_{\dimY} \times \mathbb{H}^2$.
We note that because
\begin{align*}
	&\mathbb{E}\left[  \int_t^T
	\left\{
		\left|  {b}'_{x}   (s,x(s)) \overline{x}(s)  \right|^2
		+\left|  {\sigma}'_{x}   (s,x(s)) \overline{x}(s)  \right|^2
		+\left|  {f}'   (s,u(s)) h(s)  \right|^2
	\right\}
	\ds \right]\\
	&\leq (1\vee T)\{\|{b}'  \|_{\infty}^2+\|{\sigma}'  \|_{\infty}^2+\|{f}'  \|_{\infty}^2\} \| h\|^2,
\end{align*}
we obtain that $A(u) \overline{u} \in \mathbb{L}_T^{2}$ by the same argument of Lemma \ref{op_F}.
It follows from \eqref{notation: The Mean value theorem in the Banach space} that, for all $s \in [0,T]$,
\begin{align*}
	b(s,x(s)+ \delta \overline{x}(s))-b(s, x(s))
	&=\delta {b}'_{x} \left(s, x(s) \right) \overline{x}(s)
	+\mathrm{R}_{b} \left(x(s) \right) (\delta \overline{x})(s), \\
	\sigma (s,x(s)+ \delta \overline{x}(s))-\sigma(s, x(s))
	&=\delta {\sigma}_x'\left(s, x(s) \right) \overline{x}(s)
	+\mathrm{R}_{\sigma} \left(x(s) \right) (\delta \overline{x})(s), \\
	f(s,u(s)+ \delta \overline{u}(s))-f(s, u(s))
	&=\delta {f}'\left(s, u(s) \right) \overline{u}(s)
	+\mathrm{R}_{f} \left(u(s) \right) (\delta \overline{u})(s),
\end{align*}
and
\begin{align*}
	\varphi(x(T)+ \delta \overline{x} (T))-\varphi(x(T))
	= \delta {\varphi}'\left(x(T) \right) \overline{x}(T)
	+\mathrm{R}_{\varphi} \left(x(T) \right)(\delta \overline{x})(T).
\end{align*}
Hence, for all $\delta>0$ and $t \in [0,T]$,
\begin{align*}
	&
	\frac{\NewtonF_{\varphi} \left( u+  \delta \overline{u} \right) (t) - \NewtonF_{\varphi}(u)(t)}{\delta}
	\\&
	=A(u)\overline{u}(t)
	+
	\frac{1}{\delta}
	\begin{pmatrix}
		\displaystyle
		-\int_{0}^{t} \mathrm{R}_{b} \left(x(s) \right) (\delta \overline{x})(s) \ds
		-\int_{0}^{t} \mathrm{R}_{\sigma} \left(x(s) \right) (\delta \overline{x})(s) \dBs\\
		\displaystyle
		-\mathrm{R}_{\varphi} \left(x(T) \right)(\delta \overline{x})(T)
		-\int_{t}^{T}\mathrm{R}_{f} \left(u(s) \right) (\delta \overline{u})(s) \ds.
	\end{pmatrix}^{\top}.
\end{align*}
Since $b'_x(s,\cdot)$, $\sigma'_x(s,\cdot)$, $f'(s,\cdot)$ and $\varphi'$ are bounded and continuous $(s,\omega)$-a.e., by using the dominated convergence theorem, we obtain
\begin{align*}
	\lim_{\delta \to 0}
	\left\|\frac{\NewtonF_{\varphi} \left( u+  \delta \overline{u} \right) - \NewtonF_{\varphi}(u)}{\delta}-A(u)\overline{u} \right\|_{ \mathbb{S}_{\dimX}^2 \times \mathbb{L}_T^2}=0,
\end{align*}
thus completing the proof.
\end{proof}

The following lemma is a key in order to define the Newton-Kantorovitch approximation process.

\begin{Lem}\label{lem: derivative F's inverse estimation}
	Suppose that Assumptions \ref{ass0} and \ref{ass0+1} hold
	and let $u=(x,y,z) \in \mathbb{S}^{2}_{\dimX} \times \mathbb{S}^{2}_{\dimY} \times \mathbb{H}^2$.
	Then, there exists a unique $\widetilde{u}=(\widetilde{x}, \widetilde{y},\widetilde{z}) \in \mathbb{S}^{2}_{\dimX} \times \mathbb{S}^{2}_{\dimY} \times \mathbb{H}^2$ such that $\NewtonF_{\varphi}(u)+\NewtonF_{\varphi}'(u) (\widetilde{u}-u)=0$ with initial condtion $\widetilde{x}(0)=x(0)$.
\end{Lem}
\begin{proof}
	Let $u=(x,y,z)$ be in $\mathbb{S}^{2}_{\dimX} \times \mathbb{S}^{2}_{\dimY} \times \mathbb{H}^2$.
	We show that there exists a unique $\widetilde{u}=(\widetilde{x}, \widetilde{y},\widetilde{z}) \in \mathbb{S}^{2}_{\dimX} \times \mathbb{S}^{2}_{\dimY} \times \mathbb{H}^2$ such that $\NewtonF_{\varphi}(u)+\NewtonF_{\varphi}'(u)(\widetilde{u}-u)=0$ with $\widetilde{x}(0)=x(0)$, i.e.,
	\begin{equation}\label{eq:linear BSDEs}
	\begin{split}
	\widetilde{x}(t)
	&=x(0)+\int_0^t  \left\{ b(s,x(s))+b'_{x}  (s,x(s))(\widetilde{x}(s)-x(s)) \right\}  \ds\\
	&\quad+\int_0^t \left\{ \sigma(s,x(s))+\sigma'_{x}  (s,x(s))(\widetilde{x}(s)-x(s)) \right\} \dBs,\\
	\widetilde{y}(t)
	&=\varphi  (x(T)) +\varphi'(x(T)) (\widetilde{x}(T)-x(T))\\
	&\quad+ \int_t^T \left\{ f(s,u(s))+{f}'  (s,u(s))(\widetilde{u}(s)-u(s)) \right\}  \ds
	-\int_t^T \widetilde{z}(s) \dBs,
	\end{split}
	\end{equation}
	Because the above equation is a linear decoupled FBSDE with uniformly bounded coefficients,
	there exists a unique $\widetilde{u} \in \mathbb{S}^{2}_{\dimX} \times \mathbb{S}^{2}_{\dimY} \times \mathbb{H}^2$ as required.
\end{proof}

From Lemma \ref{lem: derivative F's inverse estimation}, we can conclude that,
for any initial condition $(X_{0}, Y_{0}, Z_{0}) \in \mathbb{S}^{2}_{\dimX} \times \mathbb{S}^{2}_{\dimY} \times \mathbb{H}^2$, we can define the Newton-Kantorovitch approximation process $(X_{n+1}, Y_{n+1}, Z_{n+1}) \in \mathbb{S}^{2}_{\dimX} \times \mathbb{S}^{2}_{\dimY} \times \mathbb{H}^2$ as solving the equation
\begin{equation}
\begin{split}\label{equation: backward Newton-Kantorovitch def_n}
\NewtonF_{\varphi}(X_{n},Y_{n},Z_{n}) +\NewtonF_{\varphi}' (X_{n},Y_{n},Z_{n}) (X_{n+1}-X_{n},Y_{n+1}-Y_{n},Z_{n+1}-Z_{n}) =0,
\\ X_{n+1}(0)=X (0),
\end{split}
\end{equation}
for $n \in \mathbb{N} \cup \{0\}$, which is equivalent to
\begin{align*}
(X_{n+1}, Y_{n+1},Z_{n+1})=
(X_{n}, Y_{n},Z_{n}) - {\NewtonF'_{\varphi} (X_{n}, Y_{n},Z_{n})}^{-1} \NewtonF_{\varphi}(X_{n}, Y_{n},Z_{n}).
\end{align*}

The following theorem shows that \eqref{equation: backward Newton-Kantorovitch def_n} has a unique solution that satisfies
a linear decoupled FBSDE with uniformly bounded coefficients.

\begin{Thm}\label{Theorem: linear BSES characerlization}
If Assumptions \ref{ass0} and \ref{ass0+1} hold.

Then $(X_{n+1}, Y_{n+1},Z_{n+1})$ satisfies the following linear decoupled FBSDE for $0\leq t \leq T$:
\begin{equation}\label{bsde1+Newton}
\begin{split}
	X_{n+1}(t)&=X_{n+1}(0)+\int_0^t b_n(s,X_{n+1}(s))\ds +\int_0^t \sigma_n(s,X_{n+1} (s)) \dBs,\\
	Y_{n+1}(t)&=\varphi_n(X_{n+1}(T))+ \int_t^T f_n (s, X_{n+1}(s),  Y_{n+1}(s), Z_{n+1}(s))  \ds - \int_t^T Z_{n+1}(s) \dBs,
\end{split}
\end{equation}
where we define for $0 \leq s \leq T$ and $(x,y,z) \in \mathbb{R}^\dimX \times \mathbb{R}^\dimY \times \mathbb{R}^{\dimZ}$,
\begin{align*}
	b_n(s,x)&=b(s,X_n (s))+b'_{x}  (s,X_n (s)) (x - X_{n}(s)),\\
	\sigma_n(s,x)&=\sigma(s,X_n (s))+\sigma'_{x}  (s,X_n (s)) (x - X_{n}(s)),\\
	f_n (s, x, y, z) &=f (s, X_{n}(s), Y_{n}(s),Z_{n}(s)),\\
	&\quad+ {f}'   (X_{n}(s), Y_{n}(s), Z_{n}(s)) (x-X_{n}(s), y-Y_{n}(s) ,z-Z_{n}(s)),\\
	\varphi_n(x)&=\varphi(X_n(T))+\varphi'_{x}  (X_n (T)) (x - X_{n}(T)).
\end{align*}
In particular, if $X_0(0)=X(0)$, then $X_{n+1}(0)=X(0)$ for all $n \in \mathbb{N} \cup \{0\}$.
\end{Thm}

\begin{proof}
The existence and uniqueness of $(X_{n+1} (t), Y_{n+1} (t), Z_{n+1}(t))_{t \in [0,T]}$ follows from Lemma \ref{lem: derivative F's inverse estimation}, where, for all $n \in \mathbb{N} \cup \{0\}$.
The equation \eqref{eq:linear BSDEs} can be re-expressed as the desired FBSDE for $0\leq t \leq T$.
Finally, by the initial condition $X_{n+1}(0)=X_{n}(0)$, if $X_0(0)=X(0)$, then $X_{n+1}(0)=X(0)$, for all $n \in \mathbb{N} \cup \{0\}$.

\end{proof}

\section{Convergence of the Newton-Kantorovitch approximation process for FBSDEs}\label{Convergence of the Newton-Kantorovitch approximation process for BSDEs}
In this section, we investigate the convergence of the Newton-Kantorovitch approximation processes defined by \eqref{equation: backward Newton-Kantorovitch def_n}.

\subsection{Convergence of the Newton-Kantorovitch approximation process for SDEs}\label{Convergence of the Newton-Kantorovitch approximation process for SDEs}
In this subsection, we consider the Newton-Kantorovitch scheme for the forward process $X$
and extend earlier studies of Newton-Kantorovitch methods for SDEs,
\begin{equation}\label{SDE1}
	X(t)=X(0) + \int_0^t b(s,X(s))\ds +\int_0^t \sigma(s,X(s))\dBs.
\end{equation}

\begin{Thm}\label{convergence_SDE}
	Let $X$ be a solution of \eqref{SDE1}.
	If Assumptions \ref{ass0} and \ref{ass0+1} hold, then, for any $X_{0} \in \mathbb{S}^{2}_{\dimX}$ where $X_0(0)=X(0)$, we obtain that,
	for all $ n \in \mathbb{N}\cup\{0\}$ and $\epsilon \in (0,1)$,
	\begin{equation}\label{convergence_SDE_1}
	\begin{split}
	\| X - X_{n+1}  \|^2
	&\leq \frac{C_0^{n+1}}{(n+1)!} \| X - X_{0}  \|^2
	\leq \epsilon^{n+1}  e^{C_0T/\epsilon}\| X - X_{0}  \|^2,
	\end{split}
	\end{equation}
	where the constant $C_0$ is given by
	\begin{align*}
	&C_0 =8  c_{b,\sigma} T \exp(4 c_{b,\sigma} T),
	\quad c_{b,\sigma}=\| b' \|_{\infty}+18\|\sigma' \|_{\infty }+\| \sigma' \|^2_{\infty }.
	\end{align*}
\end{Thm}

\begin{Rem}
An estimate was initially given by \cite{KYnewton91zbMATH00019571} for one-dimensional SDEs with uniformly bounded coefficients
and an alternative estimation was proposed by \cite{Amano09zbMATH05574278}.
\end{Rem}

\begin{proof}[Proof of Theorem \ref{convergence_SDE}]
		The proof is based on \cite{Amano09zbMATH05574278}.
		By a fundamental result in \cite{Ito1942}, $X$ exists and is unique.
		For $0\leq s \leq T$ and $n \in \mathbb{N}$, define
		\[
		\overline{X}_{n}(s) = X(s)-X_{n}(s),
		\]
		we obtain for all $s \in [0,T]$ and $n \in \mathbb{N}$, $\mathbb{P}$-a.s.
		By the mean value theorem, for $s \in [0,T]$ and $n \in \mathbb{N}$, we obtain
		\begin{align*}
		&b (s, X(s))  - b_n(s, X_{n+1}(s))
		\\&=\left\{ b (s, X(s)) -b (s, X_{n}(s)) -b'_{x}  (s,X_{n}(s)) \overline{X}_{n}(s)\right\}
		+b'_{x}  (s,X_{n}(s)) \overline{X}_{n+1}(s)
		\\&=
		\mathrm{R}_{b}\left(X_{n}(s) \right) \overline{X}_{n}(s)
		+b'_{x}  (s,X_{n}(s)) \overline{X}_{n+1}(s)
		\end{align*}
		and
		\begin{align*}
		&\sigma (s, X(s))  - \sigma_n(s, X_{n+1}(s))
		\\&=\left\{ \sigma (s, X(s)) -\sigma (s, X_{n}(s)) -\sigma'_{x}  (s,X_{n}(s))\overline{X}_{n}(s)\right\}
		+\sigma'_{x}  (s,X_{n}(s))\overline{X}_{n+1}(s)
		\\&=
		\mathrm{R}_{\sigma}\left(X_{n}(s) \right) \overline{X}_{n}(s)+\sigma'_{x}  (s,X_{n}(s)) \overline{X}_{n+1}(s).
		\end{align*}
		Recall \eqref{notation: The Mean value theorem in the Banach space} and
		we have, for $s \in [0,T]$, $n \in \mathbb{N}$ and $h \in \mathbb{S}^{2}_{\dimX}$,
		\begin{align*}
		\mathrm{R}_{b}\left(X_{n}(s) \right) h(s)&=
		\left\{ \int_0^1   b'_{x} \left(s,( X_{n}(s) )+ \theta h(s) \right) \mathrm{d}\theta -  b'_{x} (s, X_{n}(s) ) \right\} h(s),
		\\ \mathrm{R}_{\sigma}\left(X_{n}(s) \right) h(s)&=
		\left\{ \int_0^1  \sigma'_{x}  \left(s,( X_{n}(s) )+ \theta h(s) \right) \mathrm{d}\theta -  \sigma'_{x} (s, X_{n}(s) ) \right\} h(s).
		\end{align*}
		This allows us to obtain
		\begin{equation*}
		\begin{split}
		\overline{X}_{n+1}(t)
		&= \int_0^t  \left\{ b'_{x} (s,X_{n}(s)) \overline{X}_{n+1}(s)
		+\mathrm{R}_{b}\left(X_{n}(s) \right)\overline{X}_{n}(s)\right\} \ds
		\\&+ \int_0^t  \left\{ \sigma'_{x}(s,X_{n}(s)) \overline{X}_{n+1}(s)
		+\mathrm{R}_{\sigma}\left(X_{n}(s) \right)\overline{X}_{n}(s) \right\} \dBs,
		\end{split}
		\end{equation*}
				which, by applying It\^o's formula yields
				\begin{equation*}
				\begin{split}
				|\overline{X}_{n+1}(t)|^2
				&= 2\int_0^t  \langle \overline{X}_{n+1}(s), b'_{x} (s,X_{n}(s)) \overline{X}_{n+1}(s)
				+\mathrm{R}_{b}\left(X_{n}(s) \right)\overline{X}_{n}(s) \rangle \ds
				\\&+ 2\int_0^t  \langle \overline{X}_{n+1}(s), \sigma'_{x}(s,X_{n}(s)) \overline{X}_{n+1}(s)
				+\mathrm{R}_{\sigma}\left(X_{n}(s) \right)\overline{X}_{n}(s) \dBs \rangle
				\\&+\int_0^t  \left| \sigma'_{x}(s,X_{n}(s)) \overline{X}_{n+1}(s)
				+\mathrm{R}_{\sigma}\left(X_{n}(s) \right)\overline{X}_{n}(s) \right|^2 \ds.
				\end{split}
				\end{equation*}
		Note that we obtain
		\begin{align*}
		2\langle \overline{X}_{n+1}(s), b'_{x} (s,X_{n}(s)) \overline{X}_{n+1}(s)
				+\mathrm{R}_{b}\left(X_{n}(s) \right)\overline{X}_{n}(s) \rangle
				\\ \leq 2 \|b' \| |\overline{X}_{n+1}(t)|^2 +4 \|b' \||\overline{X}_{n}(t)|^2
		\end{align*}
		and
		\begin{align*}
		 \left| \sigma'_{x}(s,X_{n}(s)) \overline{X}_{n+1}(s)
				+\mathrm{R}_{\sigma}\left(X_{n}(s) \right)\overline{X}_{n}(s) \right|^2
				\\ \leq 2 \|\sigma' \|^{2} |\overline{X}_{n+1}(t)|^2 +4 \|\sigma' \|^{2}|\overline{X}_{n}(t)|^2.
		\end{align*}
		The Burkholder-Davis-Gundy's inequality implies that there exists a $c_0$ such that
		\begin{align*}
			&\mathbb{E}\left[ \left| 2\int_0^t  \langle \overline{X}_{n+1}(t), \sigma'_{x}(s,X_{n}(s)) \overline{X}_{n+1}(s) \dBs \rangle\right| \right]
			\\&\leq  \mathbb{E}\left[
			2\left( \frac{1}{4}\sup_{0\leq s \leq t}|\overline{X}_{n+1}(s)|^2 \right)^{1/2}
			 \left(  4 c_0^2 \|\sigma' \| \int_0^t |X_{n+1}(s) |^2 \ds
			 \right)^{1/2}\right]
			\\ &\leq
			\frac{1}{4}\mathbb{E}\left[\sup_{0\leq s \leq t}|\overline{X}_{n+1}(s)|^2\right]
			 +
			 4 c_0^2 \|\sigma' \| \mathbb{E}\left[ \int_0^t |X_{n+1}(s) |^2 \ds \right],
		\end{align*}
		where we obtain the last inequality by applying the inequality $ab \leq (a^2/2)+(b^2/2)$ for all $a,b \in \mathbb{R}$. Similarly, we have
		\begin{align*}
			&\mathbb{E}\left[ \left| 2\int_0^t  \langle \overline{X}_{n+1}(t), \mathrm{R}_{\sigma}\left(X_{n}(s) \right)\overline{X}_{n}(s) \dBs \rangle\right| \right]
			\\&\leq  \mathbb{E}\left[
			2\left( \frac{1}{4}\sup_{0\leq s \leq t}|\overline{X}_{n+1}(s)|^2 \right)^{1/2}
			 \left(  8 c_0^2 \|\sigma' \| \int_0^t |X_{n}(s) |^2 \ds
			 \right)^{1/2}\right]
			\\ &\leq
			\frac{1}{4}\mathbb{E}\left[\sup_{0\leq s \leq t}|\overline{X}_{n+1}(s)|^2\right]
			 +
			 8 c_0^2\|\sigma' \| \mathbb{E}\left[ \int_0^t |X_{n}(s) |^2 \ds \right],
		\end{align*}
 		where we note that an explicit upper bounded of $3$ can be obtained for the constant $c_0$; see Theorem 3.28 in \cite{Karatzasbook}.
		By setting
		$
			c_{b,\sigma}=\|b' \|_{ \infty }+2 c_0^2\|\sigma' \|_{\infty }+\|\sigma' \|^2_{\infty },
		$
		 we obtain, for any $t' \in [0,T]$,
		\begin{equation*}
		\begin{split}
		\mathbb{E}\left[\sup_{0\leq t \leq t'}|\overline{X}_{n+1}(t)|^2\right]
		&\leq
		4c_{b,\sigma} \int_0^{t'}
			\mathbb{E}\left[\sup_{0\leq t \leq s}|\overline{X}_{n+1}(t)|^2\right]
		\ds
		\\&+8c_{b,\sigma}\int_0^{t'}
			\mathbb{E}\left[\sup_{0\leq t \leq s}|\overline{X}_{n}(t)|^2\right]
		\ds.
		\end{split}
		\end{equation*}
		Gronwall's inequality further implies that
		\begin{equation}\label{convergence_SDE_2}
		\begin{split}
		\mathbb{E}\left[\sup_{0\leq t \leq t'}|\overline{X}_{n+1}(t)|^2\right]
		&\leq
		C_0\int_0^{t'} \mathbb{E}\left[\sup_{0\leq t \leq s}|\overline{X}_{n}(t)|^2\right]
		\ds,
		\end{split}
		\end{equation}
		where
		$C_{0}
		=8c_{b,\sigma} \exp(4c_{b,\sigma}T)$.
		Iterating \eqref{convergence_SDE_2} yields
		\begin{equation*}
		\begin{split}
		\mathbb{E}\left[\sup_{0\leq t \leq T}|\overline{X}_{n+1}(t)|^2\right]
		&\leq
		C_{0}
		^2 \int_0^{T}\ds_1 \int_0^{s_1}\ds_2
		\mathbb{E}\left[\sup_{0\leq t \leq s_2}|\overline{X}_{n-1}(t)|^2\right]
		\\&\leq
		C_{0}
		^{n+1} \mathbb{E}\left[\sup_{0\leq t \leq T}|\overline{X}_{0}(t)|^2\right]
		\int_0^{T}\ds_1 \int_0^{s_1}\ds_2 \cdots \int_0^{s_{n}}\ds_{n+1}
		\\&=
		\frac{(TC_{0}
		)^{n+1}}{(n+1)!} \mathbb{E}\left[\sup_{0\leq t \leq T}|\overline{X}_{0}(t)|^2\right].
		\end{split}
		\end{equation*}
		In  addition,  we obtain that
		\[
		\epsilon^{ -(n+1)}\frac{(TC_{0})^{n+1}}{(n+1)!}  \leq \sum_{k=0}^{\infty}\frac{(TC_{0}/\epsilon)^{k}}{k!} =e^{C_0T/\epsilon},
		\]
		thus completing the proof.
\end{proof}
\begin{Rem}
We can also sue the same argument to show that the approximation process is a Cauchy sequence in $\mathbb{S}^{2}_{\dimX} $.
\end{Rem}

\subsection{Toward decoupled forward-backward stochastic differential equations}\label{Toward decoupled forward-backward stochastic differential equations}
The inequality in Theorem \ref{convergence_BSDE} below indicates that approximating the terminal condition is the key to estimating the error between the solution and the Newton-Kantorovitch approximation process.
In this section, we consider the Newton-Kantorovitch approximation with respect to the terminal condition.
First, we show that it
converges with respect to the weighted norm $\|\cdot \|_{\alpha}$.

\begin{Thm}\label{convergence_BSDE}
	Let $(X,Y,Z)$ be a solution of the FBSDE \eqref{fbsde1 decoupled}.
	If Assumptions \ref{ass0} and \ref{ass0+1} hold and $(X_{0}, Y_{0}, Z_{0}) \in {\mathbb{S}^{2}_{\dimX} \times } \mathbb{S}^{2}_{\dimY} \times \mathbb{H}^2$ such that $X_{0}(0)=X(0)$, then, for all $ n \in \mathbb{N}\cup\{0\}$, $\epsilon \in (0,1)$ and $T>0$, we obtain
	\begin{equation}\label{Theorem: the linear convergence inequality}
	\begin{split}
	\| (
	Y - Y_{n+1}, Z - Z_{n+1} ) \|_{\alpha}^2
	\leq  \epsilon^{n+1}
	\left\{ C_1 \| X - X_{0} \|_{{\mathbb{S}^2_{\dimX}}}^2 +\| (Y - Y_{0}, Z - Z_{0} ) \|_{\alpha}^2 \right\}
	\end{split}
	\end{equation}
where
$C_1 \equiv C_1(\epsilon)=\epsilon^{-1} \{1+\left( 1+4(2+TC_0) \| \varphi' \|_{\infty}^2 \right) \left(1+4c_{0}^2 \right)\} e^{\alpha T+C_0/\epsilon}$,
$c_0=3$ and $C_0$ is given by Theorem \ref{convergence_SDE} and $\alpha =2 \| {f}' \|_{\infty}+4 \| {f}' \|_{\infty}^2+12 \| {f}' \|_{\infty} \left(1+ 4 c_0^2 \right) (1 \vee T) \epsilon^{-1}$.
\end{Thm}
\begin{proof}
\begin{subequations}
By the fundamental result in \cite{pardouxpen1990adapted},
the solution $(X,Y,Z)$ exists and is unique.
For $s \in [0,T]$ and $n \in \mathbb{N}$, we define
\begin{align*}
	h_n (s)
	=(\overline{X}_{n}(s),\overline{Y}_{n}(s),\overline{Z}_n(s))
	=(X(s)-X_{n}(s), Y(s)-Y_{n}(s), Z (s)-Z_{n}(s)),
\end{align*}
and apply the mean value theorem, yielding
\begin{align*}
&f (s, X(s), Y(s), Z(s))  - f_n (s, X_{n+1}(s), Y_{n+1}(s), Z_{n+1}(s))
	\\&={f}'  (s, X_{n}(s), Y_{n}(s),  Z_{n}(s) )h_{n+1} (s)
	\\&+\left\{ f (s, X(s), Y(s), Z(s)) - f (s, X_{n}(s), Y_{n}(s), Z_{n}(s)) -{f}'  (s, X_{n}(s), Y_{n}(s),  Z_{n}(s) )h_n (s)\right\}
	\\&={f}'  (s, X_{n}(s), Y_{n}(s),  Z_{n}(s) ) h_{n+1}(s)+\mathrm{R}_{f}\left(X_{n}(s), Y_{n}(s),  Z_{n}(s) \right) h_{n}(s).

\end{align*}
Recall \eqref{notation: The Mean value theorem in the Banach space} and
we have, for $s \in [0,T]$, $n \in \mathbb{N}$ and $h \in \mathbb{S}^{2}_{\dimX} \times \mathbb{S}^{2}_{\dimY} \times \mathbb{H}^2$,
\begin{align*}
	&\mathrm{R}_{f}\left(X_{n}(s), Y_{n}(s),  Z_{n}(s) \right) h(s)
	\\ &=
	\left\{ \int_0^1  {f}'\left(s, (X_{n}(s), Y_{n}(s),  Z_{n}(s) )+ \theta h(s) \right) \mathrm{d}\theta - {f}'  (s, X_{n}(s), Y_{n}(s),  Z_{n}(s) ) \right\} h(s).
\end{align*}
This allows us to show that $(\overline{Y}_{n+1},\overline{Z}_{n+1})$ satisfies the following linear BSDE
\begin{equation*}
\begin{split}
	&\overline{Y}_{n+1}(t) - \overline{Y}_{n+1}(T)+\int_t^T  \overline{Z}_{n+1}(s)  \dBs
	\\&=\int_t^T
		\left\{ {f}' (s, X_{n}(s), Y_{n}(s), Z_{n}(s) ) h_{n+1} (s)  +\mathrm{R}_{f}\left(X_{n}(s), Y_{n}(s), Z_{n}(s) \right)h_n(s)  \right\} \ds.
\end{split}
\end{equation*}
Applying It\^o's formula to $e^{\alpha  t} \left| \overline{Y}_{n+1}(t) \right|^2$ for all $\alpha \in \mathbb{R}$, we obtain
\begin{equation}\label{L two times exponential alpha from t to T}
\begin{split}
	&e^{\alpha  t} \left| \overline{Y}_{n+1}(t) \right|^2 -e^{\alpha  T} \left| \overline{Y}_{n+1}(T) \right|^2
	+  \int_t^T  e^{\alpha  s} \left| \overline{Z}_{n+1}(s) \right|^2   \ds
	\\&= \int_t^T e^{\alpha  s} (-\alpha)  \left| \overline{Y}_{n+1}(s) \right|^2   \ds
	-2 \int_t^T   e^{\alpha s} \langle {\overline{Y}_{n+1}(s)}, \overline{Z}_{n+1}(s)  \dBs \rangle
	\\&+2\int_t^T e^{\alpha  s} \langle  \overline{Y}_{n+1}(s), {f}' (s, X_{n}(s),  Y_{n}(s), Z_{n}(s) ) h_{n+1} (s)
	+\mathrm{R}_{f} \left(X_{n}(s), Y_{n}(s), Z_{n}(s) \right) h_n(s) \rangle  \ds.
\end{split}
\end{equation}
From the Cauchy-Schwarz inequality and the inequality $2a b \leq \delta^{-1} |a|^2 +\delta |b|^2$ for all $\delta>0$, we have
\begin{align}
	 &
	 2 \left| \langle \overline{Y}_{n+1}(s), f'_{x} (s, X_{n}(s), Y_{n}(s), Z_{n}(s) )\overline{X}_{n+1}(s) \rangle\right|
	 \leq
	 2 \| {f}' \|_{\infty}^2  \left| \overline{Y}_{n+1}(s) \right|^2+\frac{1}{2} \left| \overline{X}_{n+1}(s)  \right|^2,
	 \notag
	\\&
	2 \left|\langle \overline{Y}_{n+1}(s) ,  f'_{y} (s, X_{n}(s), Y_{n}(s), Z_{n}(s) )\overline{Y}_{n+1}(s) \rangle\right|
	\leq 2 \| {f}' \|_{\infty} \left| \overline{Y}_{n+1}(s) \right|^2, \notag
	 \\&
	 2 \left| \langle \overline{Y}_{n+1}(s), f'_{z} (s, X_{n}(s), Y_{n}(s), Z_{n}(s) )\overline{Z}_{n+1}(s) \rangle\right|
	 \leq
	 2 \| {f}' \|_{\infty}^2  \left| \overline{Y}_{n+1}(s) \right|^2+\frac{1}{2} \left| \overline{Z}_{n+1}(s)  \right|^2,
	 \notag
	 \\ &
	  2 \left| \langle \overline{Y}_{n+1}(s),  \mathrm{R}_{f}\left( X_{n}(s),
	  Y_{n}(s),  Z_{n}(s) \right) h_{n}(s) \rangle \right|
	  \leq  \delta^{-1}  \left| \overline{Y}_{n+1}(s) \right|^2+ \delta\left| \mathrm{R}_{f}\left(X_{n}(s), Y_{n}(s),  Z_{n}(s) \right) h_{n}(s)\right|^2 \notag,
\end{align}
and
\begin{align}
	\left| \mathrm{R}_{f}\left(X_{n}(s), Y_{n}(s),  Z_{n}(s) \right) h_{n}(s) \right|
	 \leq  2 \| {f}' \|_{\infty} \left| h_n(s) \right|.
	  \label{Rf estimation}
\end{align}
The right-hand side of \eqref{L two times exponential alpha from t to T} is therefore less than or equal to
\begin{align*}
	&\int_t^T e^{\alpha  s} \cdot
	\left\{
		(-\alpha)
		+ 2 \| {f}' \|_{\infty}
		+4 \| {f}' \|_{\infty}^2
		+\delta^{-1}
	\right\}
	\left|
		\overline{Y}_{n+1}(s)
	\right|^2
	\ds
	\\&+\int_t^T
		e^{\alpha  s}
		\left\{
			\frac{1}{2} \left|\overline{Z}_{n+1}(s)\right|^2
			+
			\frac{1}{2} \left|\overline{X}_{n+1}(s)\right|^2
			+ \delta
				\left|
					\mathrm{R}_{f}\left(X_{n}(s), Y_{n}(s), Z_{n}(s) \right) h_{n}(s)
				\right|^2
		\right\} \ds\\
	&-2 \int_t^T   e^{\alpha s} \langle {\overline{Y}_{n+1}(s)}, \overline{Z}_{n+1}(s)  \dBs \rangle.
\end{align*}
Setting $\alpha \equiv \alpha(\delta)=  2 \| {f}' \|_{\infty}+4 \| {f}' \|_{\infty}^2+\delta^{-1} $, we obtain
\begin{equation}
\begin{split}
	&e^{\alpha  t} \left| \overline{Y}_{n+1}(t) \right|^2 -e^{\alpha  T} \left| \overline{Y}_{n+1}(T) \right|^2
	+\frac{1}{2}  \int_t^T  e^{\alpha  s}
	 \left\{ \left| \overline{Z}_{n+1}(s) \right|^2   -  \left| \overline{X}_{n+1}(s) \right|^2 \right\}
	  \ds
	\\&
	\leq  \delta \int_t^T e^{\alpha  s}  \left| \mathrm{R}_{f}\left(X_{n}(s), Y_{n}(s),  Z_{n}(s) \right) h_{n}(s) \right|^2 \ds
	- 2\int_t^T   e^{\alpha  s}   \langle {\overline{Y}_{n+1}(s)}, \overline{Z}_{n+1}(s)  \dBs \rangle.  \label{an inequality before applying the BDG inequality}
\end{split}
\end{equation}
As $(Y,Z),  (Y_{n}, Z_{n}) \in \mathbb{S}^{2}_{\dimY} \times \mathbb{H}^2$,
the local martingale
\[
	 \left\{ \int_0^t   e^{\alpha  s}   \langle {\overline{Y}_{n+1}(s)}, \overline{Z}_{n+1}(s)  \dBs \rangle \right\}_{t \in [0,T]}
\]
vanishes at $0$.
Thus, in particular, by setting $t=0$,  we obtain
\begin{equation}
\begin{split}
	&\mathbb{E} \left[ \int_0^T  e^{\alpha  s}
		\left\{ \left| \overline{Z}_{n+1}(s) \right|^2   -  \left| \overline{X}_{n+1}(s) \right|^2 \right\}
		\ds \right]
	 \\ &\leq 2 \delta \mathbb{E} \left[ \int_0^T e^{\alpha  s}  \left| \mathrm{R}_{f}\left(X_{n}(s), Y_{n}(s),  Z_{n}(s) \right) h_{n}(s) \right|^2 \ds \right]
	  +2 \mathbb{E} \left[ e^{\alpha  T} \left| \overline{Y}_{n+1}(T) \right|^2  \right]
	  \label{Z bounded by Repsilon}.
\end{split}
\end{equation}
Note that
\begin{align*}
	\int_t^T   e^{\alpha  s}   \langle {\overline{Y}_{n+1}(s)}, \overline{Z}_{n+1}(s)  \dBs \rangle
	= \int_0^T   1_{[t,T]}(s) e^{\alpha  s}   \langle {\overline{Y}_{n+1}(s)}, \overline{Z}_{n+1}(s)  \dBs \rangle.
\end{align*}
Applying the Burkholder-Davis-Gundy inequality indicates that there is a universal $c_{0}$ such that
\begin{align*}
&2 \mathbb{E} \left[\sup_{0 \leq t \leq T}\left|   \int_t^T   e^{\alpha  s}   \langle {\overline{Y}_{n+1}(s)}, \overline{Z}_{n+1}(s)  \dBs \rangle \right| \right]
	\\&\leq 2 c_{0} \mathbb{E} \left[\left( \int_0^T 1_{[t,T]}(s)  e^{2 \alpha  s}   \left| \overline{Y}_{n+1}(s) \right|^2 \left|  \overline{Z}_{n+1}(s) \right|^2 \ds \right)^{\frac{1}{2}} \right]
\\	&\leq \mathbb{E} \left[ \sup_{0 \leq t \leq T} e^{ \alpha  t/2}   \left| \overline{Y}_{n+1}(t) \right| \left( 4c_{0}^2 \int_0^T   e^{ \alpha  s}    \left|  \overline{Z}_{n+1}(s) \right|^2 \ds \right)^{\frac{1}{2}}\right],
\end{align*}
 	where we note that an explicit upper bounded of $3$ can be obtained on the constant;
	refer to Theorem 3.28 in \cite{Karatzasbook}.
	Hence, by considering the supremum of \eqref{an inequality before applying the BDG inequality} and using the inequality $ab \leq (a^2/2)+(b^2/2)$ for all $a,b \in \mathbb{R}$, we obtain
\begin{align*}
&	\mathbb{E} \left[ \sup_{0 \leq t \leq T} e^{\alpha  t} \left| \overline{Y}_{n+1}(t)\right|^2
	-e^{\alpha  T} \left| \overline{Y}_{n+1}(T) \right|^2
	+\frac{1}{2}  \int_0^T  e^{\alpha  s}
	\left\{ \left| \overline{Z}_{n+1}(s) \right|^2   -  \left| \overline{X}_{n+1}(s) \right|^2 \right\}
	  \ds \right]
	\\&\leq
	\delta \int_0^T e^{\alpha  s}  \mathbb{E} \left[ \left| \mathrm{R}_{f}\left(X_{n}(s), Y_{n}(s),  Z_{n}(s) \right) h_{n}(s) \right|^2 \right] \ds
	\\&+
	 \frac{1}{2}\mathbb{E} \left[ \sup_{0 \leq t \leq T} e^{ \alpha  t}   \left| \overline{Y}_{n+1}(t) \right|^2 \right]
	+2 c_{0}^2
	 \mathbb{E} \left[\int_0^T   e^{ \alpha  s} \left| \overline{Z}_{n+1}(s) \right|^2 \ds \right],
\end{align*}
which implies that
\begin{align*}
&	\mathbb{E} \left[ \sup_{0 \leq t \leq T} e^{\alpha  t} \left| \overline{Y}_{n+1}(t)\right|^2
	-2e^{\alpha  T} \left| \overline{Y}_{n+1}(T) \right|^2
	+\int_0^T  e^{\alpha  s} \left\{ \left| \overline{Z}_{n+1}(s) \right|^2   -  \left| \overline{X}_{n+1}(s) \right|^2 \right\}
	   \ds \right]
	\\&\leq
	2\delta \int_0^T e^{\alpha  s}  \mathbb{E} \left[ \left| \mathrm{R}_{f}\left(X_{n}(s), Y_{n}(s),  Z_{n}(s) \right) h_{n}(s) \right|^2 \right] \ds
	+4 c_{0}^2
	 \mathbb{E} \left[\int_0^T   e^{ \alpha  s} \left| \overline{Z}_{n+1}(s) \right|^2 \ds \right].
\end{align*}
By then taking the inequality \eqref{Z bounded by Repsilon} into consideration, we observe
\begin{equation*}
\begin{split}
&\mathbb{E} \left[ \sup_{0 \leq t \leq T} e^{\alpha  t} \left| \overline{Y}_{n+1}(t) \right|^2 +  \int_0^T  e^{\alpha  s} \left\{ \left| \overline{Z}_{n+1}(s) \right|^2   -  \left| \overline{X}_{n+1}(s) \right|^2 \right\}
  \ds  \right]
	\\&
	\leq
	2\delta\left( 1+4 c_0^2
	 \right) \int_0^T e^{\alpha  s}   \mathbb{E} \left[ \left| \mathrm{R}_{f}\left(X_{n}(s), Y_{n}(s),  Z_{n}(s) \right) h_{n}(s)\right|^2\right] \ds\\
	&\quad+2\left(1+4 c_0^2
	\right)e^{\alpha  T} \mathbb{E} \left[ \left| \overline{Y}_{n+1}(T) \right|^2  \right]
	+
	4 c_0^2 \mathbb{E} \left[\int_0^T   e^{ \alpha  s} \left| \overline{X}_{n+1}(s) \right|^2 \ds \right]
	.
\end{split}
\end{equation*}
If we also consider the inequality \eqref{Rf estimation}, we find
\begin{align*}
	&\int_0^T e^{\alpha  s}   \mathbb{E} \left[ \left| \mathrm{R}_{f}\left(X_{n}(s), Y_{n}(s),  Z_{n}(s) \right) h_{n}(s) \right|^2\right] \ds
	\\&\leq  6\| {f}' \|_{\infty} (1 \vee T)
	\left\{ \mathbb{E} \left[ \sup_{0 \leq t \leq T} e^{\alpha  t} \left| \overline{X}_{n}(t) \right|^2+\sup_{0 \leq t \leq T} e^{\alpha  t} \left| \overline{Y}_{n}(t) \right|^2 +  \int_0^T  e^{\alpha  s} \left| \overline{Z}_{n}(s) \right|^2  \ds  \right]\right\}.
\end{align*}
Selecting $\delta$ such that $  12 \| {f}' \|_{\infty} \left(1+ 4 c_0^2
	 \right) (1 \vee T)  \delta=\epsilon$,
we obtain
\[
	\alpha
	\equiv \alpha(\delta)=2 \| {f}' \|_{\infty}+4 \| {f}' \|_{\infty}^2+12 \| {f}' \|_{\infty} \left(1+4 c_0^2\right) (1 \vee T) \epsilon^{-1}.
\]
This leads to
\begin{align*}
\begin{split}
	&\| (\overline{Y}_{n+1}, \overline{Z}_{n+1} ) \|_{\alpha}^2
	\\& \leq  \epsilon \| ( \overline{X}_{n}, \overline{Y}_{n}, \overline{Z}_{n})\|_{\alpha}^2
	+2\left(1+4c_{0}^2 \right)e^{\alpha  T} \|  \overline{Y}_{n+1}(T)   \|_{\mathbb{L}^2}^2
	+ \left(1+4c_{0}^2 \right)\|  \overline{X}_{n+1}   \|_{\alpha}^2.
\end{split}
\end{align*}
Hence, using \eqref{convergence_SDE_2},
\begin{align*}
	\mathbb{E} \left[ \left| \overline{Y}_{n+1}(T) \right|^2  \right]
	&\leq \| \varphi' \|_{\infty}^2 \left\{ 4\mathbb{E} \left[ \left| \overline{X}_{n}(T) \right|^2  \right]+2\mathbb{E} \left[ \left| \overline{X}_{n+1}(T) \right|^2  \right]\right\}\\
	&\leq 2(2+TC_0)\| \varphi' \|_{\infty}^2 \mathbb{E} \left[ \left| \overline{X}_{n}(T) \right|^2  \right].
\end{align*}
Thus, we obtain
\[
	2\left(1+4c_{0}^2 \right)e^{\alpha  T} \|  \overline{Y}_{n+1}(T)   \|_{\mathbb{L}^2}^2
	\leq 4(2+TC_0) \| \varphi' \|_{\infty}^2 \left(1+4c_{0}^2 \right)e^{\alpha  T} \|  \overline{X}_{n}   \|_{\mathbb{S}^2_{\dimX}}^2.
\]
Applying inequality \eqref{convergence_SDE_1} then yields  for $c_1 = e^{\alpha  T}+\left( 1+4(2+TC_0) \| \varphi' \|_{\infty}^2 \right) \left(1+4c_{0}^2 \right)e^{\alpha  T}$,
\begin{align*}
\begin{split}
	&\| (\overline{Y}_{n+1}, \overline{Z}_{n+1} ) \|_{\alpha}^2
	 \leq  \epsilon \| (\overline{Y}_{n}, \overline{Z}_{n})\|_{\alpha}^2
	 +c_1 \| X - X_{0}  \|^2  \frac{C_0^{n}}{n!}.
\end{split}
\end{align*}
For any positive sequence $\{ a_n \}$, $\{ b_n\}$ and $\epsilon >0$
such that $a_{n+1} \leq b_{n} + \epsilon a_{n}$ for all $n \in \mathbb{N} \cup \{0\}$, we obtain
\begin{align*}
	a_{n+1}
	&\leq b_{n}+ \epsilon ( \epsilon a_{n-1} + b_{n-1} )
	= \epsilon^{2} \left( \epsilon^{-2}  b_{n} + \epsilon^{-1} b_{n-1}  +  a_{n-1} \right)
	\\ & \leq \cdots \leq  \epsilon^{n+1} \left\{ \sum_{k=0}^{n}  \epsilon^{k-(n+1)}  b_{n-k} +  a_{0} \right\} .
\end{align*}
Replacing  $b_n =c_1 \| X - X_{0}  \|^2 \frac{C_0^{n}}{n!} $ for all $n \in \mathbb{N}$,
we obtain
\begin{align*}
	 \sum_{k=0}^{n}  \epsilon^{k-(n+1)} b_{n-k}

	\leq	 \epsilon^{-1} c_1 \| X - X_{0}  \|^2  \sum_{k=0}^{n} \frac{(C_0/\epsilon)^{k}}{k!}
	\leq  \epsilon^{-1} c_1 \| X - X_{0}  \|^2  e^{C_0/\epsilon}, \quad n \in \mathbb{N}\cup \{ 0 \} .
\end{align*}
Thus, we obtain
\begin{align*}
\begin{split}
	&\| (\overline{Y}_{n+1}, \overline{Z}_{n+1} ) \|_{\alpha}^2
	 \leq  \epsilon^{n+1} \left( C_1  \| X - X_{0}  \|^2 +\| (\overline{Y}_{0}, \overline{Z}_{0} ) \|_{\alpha}^2  \right),
\end{split}
\end{align*}
where we define
$
C_1
=\epsilon^{-1} c_1 e^{C_0/\epsilon}
=\epsilon^{-1} \{1+\left( 1+4(2+TC_0) \| \varphi' \|_{\infty}^2 \right) \left(1+4c_{0}^2 \right)\} e^{\alpha T+C_0/\epsilon}
$.
This conclude the proof.
\end{subequations}
\end{proof}

\begin{Rem}
We can also prove the so called ``semilocal theorem," which states
that  the approximation process is a Cauchy sequence in $\mathbb{S}^{2}_{\dimY} \times \mathbb{H}^2$ by the same argument. For the definition of "semilocal,"
refer to \cite{Yamamoto2001}.
\end{Rem}

We can now prove our main result based on the following theorem.

\begin{Thm}\label{Thm: Newton-Kantorovitch BSDE}
Let $(X,Y,Z)$ be a solution of the FBSDE \eqref{fbsde1 decoupled}.
If Assumptions \ref{ass0} and \ref{ass0+1} hold and $(X_{0}, Y_{0}, Z_{0}) \in \mathbb{S}^{2}_{\dimX} \times
\mathbb{S}^{2}_{\dimY} \times \mathbb{H}^2$ with $X_{0}(0)=X(0)$,
then, there exists a $C_3>0$ such that, for all $n \in \mathbb{N} \cup \{ 0\}$, we obtain
\begin{equation}\label{Theorem: the linear convergence inequality BSDE}
\begin{split}
	&\| (X - X_{n+1}, Y - Y_{n+1}, Z - Z_{n+1} )\|^2
	\\ &\leq  \epsilon^{n+1} C_3 \| (X - X_{0}, Y - Y_{0}, Z - Z_{0} ) \|^2,
\end{split}
\end{equation}
where the constant $C_3 \equiv C_3 (\epsilon)$ is bounded by the coefficients and independent of $n$.
\end{Thm}
\begin{proof}
By inequality \eqref{convergence_SDE_1} in Theorem \ref{convergence_SDE}
and by inequality \eqref{Theorem: the linear convergence inequality} in Theorem \ref{convergence_BSDE}, we obtain
	\begin{equation*}
	\begin{split}
	\| X - X_{n+1}  \|^2 \leq \epsilon^{n+1}  e^{C_0T/\epsilon}\| X - X_{0}  \|^2,
	\end{split}
	\end{equation*}
	and
	\begin{equation*}
	\begin{split}
	\| (Y - Y_{n+1}, Z - Z_{n+1} ) \|^2
	&\leq \| (Y - Y_{n+1}, Z - Z_{n+1} ) \|_{\alpha}^2
	\\& \leq  \epsilon^{n+1}
	\left\{ C_1 \| X - X_{0} \|_{{\mathbb{S}^2_{\dimX}}}^2 +\| (Y - Y_{0}, Z - Z_{0} ) \|_{\alpha}^2 \right\},
	\end{split}
	\end{equation*}
respectively, where
	\begin{align*}
	&C_0 =8  c_{b,\sigma} T \exp(4 c_{b,\sigma} T),
		\quad c_{b,\sigma}=\| b' \|_{\infty}+18\|\sigma' \|_{\infty}+\| \sigma' \|^2_{\infty},
	\\ &C_1 \equiv C_1(\epsilon)=\epsilon^{-1} \{1+\left( 1+4(2+TC_0) \| \varphi' \|_{\infty}^2 \right) \left(1+4c_{0}^2 \right)\} e^{\alpha T+C_0/\epsilon}, \quad  c_0=3,
	\\&\alpha =2 \| {f}' \|_{\infty}+4 \| {f}' \|_{\infty}^2+12 \| {f}' \|_{\infty} \left(1+4 c_0^2
 \right) (1 \vee T) \epsilon^{-1}.
	\end{align*}
Defining
\[
	C_3 =  \left\{ (C_1 + e^{C_0T/\epsilon}) \vee e^{\alpha T} \right\},
\]
concludes the proof.
\end{proof}

This finally allows us to prove our main theorem, Theorem \ref{Theorem: the convergence of the Newton-Kantorovitch approximation process3}.
\begin{proof}[Proof of Theorem \ref{Theorem: the convergence of the Newton-Kantorovitch approximation process3}]
By setting $\epsilon =1/2$, the desired result can be obtained from Theorem \ref{Thm: Newton-Kantorovitch BSDE}.
\end{proof}

\section*{Acknowledgements}
We would like to express our sincere appreciation to T.~Yamada for suggesting
a formulation of the Newton-Kantorovitch method for BSDEs.
This work was supported by
JSPS KAKENHI Grant Numbers 16J00894 and 17H06833.

\section*{References}
\bibliographystyle{amsplain}

\providecommand{\bysame}{\leavevmode\hbox to3em{\hrulefill}\thinspace}
\providecommand{\MR}{\relax\ifhmode\unskip\space\fi MR }

\providecommand{\MRhref}[2]{
  \href{http://www.ams.org/mathscinet-getitem?mr=#1}{#2}
}
\providecommand{\href}[2]{#2}

config: arxiv


text:
\section{Seventeen Horses/General Problem 1}
Tags: Seventeen Horses, Unit Fractions

\begin{theorem}
A man dies, leaving $n$ indivisible and indistinguishable objects to be divided among $3$ heirs.
They are to be distributed in the [[Definition:Ratio|ratio]] $\dfrac 1 a : \dfrac 1 b : \dfrac 1 c$.
Let $\dfrac 1 a + \dfrac 1 b + \dfrac 1 c < 1$.
Then there are $7$ possible values of $\tuple {n, a, b, c}$ such that the required shares are:
:$\dfrac {n + 1} a, \dfrac {n + 1} b, \dfrac {n + 1} c$
These values are:
:$\tuple {7, 2, 4, 8}, \tuple {11, 2, 4, 6}, \tuple {11, 2, 3, 12}, \tuple {17, 2, 3, 9}, \tuple {19, 2, 4, 5}, \tuple {23, 2, 3, 8}, \tuple {41, 2, 3, 7}$
leading to shares, respectively, of:
:$\tuple {4, 2, 1}, \tuple {6, 3, 2}, \tuple {6, 4, 1}, \tuple {9, 6, 2}, \tuple {10, 5, 4}, \tuple {12, 8, 3}, \tuple {21, 14, 6}$
\end{theorem}

\begin{proof}
It is taken as a condition that $a \ne b \ne c \ne a$.
We have that:
:$\dfrac 1 a + \dfrac 1 b + \dfrac 1 c + \dfrac 1 n = 1$
and so we need to investigate the solutions to the above equations.
From [[Sum of 4 Unit Fractions that equals 1]], we have that the only possible solutions are:
{{begin-eqn}}
{{eqn | l = \dfrac 1 2 + \dfrac 1 3 + \dfrac 1 7 + \dfrac 1 {42}
      | r = 1
}}
{{eqn | l = \dfrac 1 2 + \dfrac 1 3 + \dfrac 1 8 + \dfrac 1 {24}
      | r = 1
}}
{{eqn | l = \dfrac 1 2 + \dfrac 1 3 + \dfrac 1 9 + \dfrac 1 {18}
      | r = 1
}}
{{eqn | l = \dfrac 1 2 + \dfrac 1 3 + \dfrac 1 {10} + \dfrac 1 {15}
      | r = 1
}}
{{eqn | l = \dfrac 1 2 + \dfrac 1 3 + \dfrac 1 {12} + \dfrac 1 {12}
      | r = 1
}}
{{eqn | l = \dfrac 1 2 + \dfrac 1 4 + \dfrac 1 5 + \dfrac 1 {20}
      | r = 1
}}
{{eqn | l = \dfrac 1 2 + \dfrac 1 4 + \dfrac 1 6 + \dfrac 1 {12}
      | r = 1
}}
{{eqn | l = \dfrac 1 2 + \dfrac 1 4 + \dfrac 1 8 + \dfrac 1 8
      | r = 1
}}
{{eqn | l = \dfrac 1 2 + \dfrac 1 5 + \dfrac 1 5 + \dfrac 1 {10}
      | r = 1
}}
{{eqn | l = \dfrac 1 2 + \dfrac 1 6 + \dfrac 1 6 + \dfrac 1 6
      | r = 1
}}
{{eqn | l = \dfrac 1 3 + \dfrac 1 3 + \dfrac 1 4 + \dfrac 1 {12}
      | r = 1
}}
{{eqn | l = \dfrac 1 3 + \dfrac 1 3 + \dfrac 1 6 + \dfrac 1 {6}
      | r = 1
}}
{{eqn | l = \dfrac 1 3 + \dfrac 1 4 + \dfrac 1 4 + \dfrac 1 6
      | r = 1
}}
{{eqn | l = \dfrac 1 4 + \dfrac 1 4 + \dfrac 1 4 + \dfrac 1 4
      | r = 1
}}
{{end-eqn}}
From these, we can eliminate the following, because it is not the case that $a \ne b \ne c \ne a$:
{{begin-eqn}}
{{eqn | l = \dfrac 1 2 + \dfrac 1 5 + \dfrac 1 5 + \dfrac 1 {10}
      | r = 1
}}
{{eqn | l = \dfrac 1 2 + \dfrac 1 6 + \dfrac 1 6 + \dfrac 1 6
      | r = 1
}}
{{eqn | l = \dfrac 1 3 + \dfrac 1 3 + \dfrac 1 4 + \dfrac 1 {12}
      | r = 1
}}
{{eqn | l = \dfrac 1 3 + \dfrac 1 3 + \dfrac 1 6 + \dfrac 1 {6}
      | r = 1
}}
{{eqn | l = \dfrac 1 3 + \dfrac 1 4 + \dfrac 1 4 + \dfrac 1 6
      | r = 1
}}
{{eqn | l = \dfrac 1 4 + \dfrac 1 4 + \dfrac 1 4 + \dfrac 1 4
      | r = 1
}}
{{end-eqn}}
Then we can see by inspection that the following are indeed solutions to the problem:
{{begin-eqn}}
{{eqn | l = \dfrac 1 2 + \dfrac 1 3 + \dfrac 1 7 + \dfrac 1 {42}
      | r = 1
}}
{{eqn | l = \dfrac 1 2 + \dfrac 1 3 + \dfrac 1 8 + \dfrac 1 {24}
      | r = 1
}}
{{eqn | l = \dfrac 1 2 + \dfrac 1 3 + \dfrac 1 9 + \dfrac 1 {18}
      | r = 1
}}
{{eqn | l = \dfrac 1 2 + \dfrac 1 3 + \dfrac 1 {12} + \dfrac 1 {12}
      | r = 1
}}
{{eqn | l = \dfrac 1 2 + \dfrac 1 4 + \dfrac 1 5 + \dfrac 1 {20}
      | r = 1
}}
{{eqn | l = \dfrac 1 2 + \dfrac 1 4 + \dfrac 1 6 + \dfrac 1 {12}
      | r = 1
}}
{{eqn | l = \dfrac 1 2 + \dfrac 1 4 + \dfrac 1 8 + \dfrac 1 8
      | r = 1
}}
{{end-eqn}}
The remaining tuple we have is:
:$\dfrac 1 2 + \dfrac 1 3 + \dfrac 1 {10} + \dfrac 1 {15} = 1$
But we note that:
:$\dfrac 1 2 + \dfrac 1 3 + \dfrac 1 {10} = \dfrac {28} {30}$
which is not in the correct form.
Hence the $7$ possible solutions given.
{{qed}}
\end{proof}

config: wiki


TITLE: Any neighbourhood of a closed decreasing sequence in a compact space must contain one of the sets: why is the space required also to be Hausdorff?
QUESTION [1 upvotes]: $\newcommand{\o}{\mathcal{O}}$Apologies for the perhaps strangely phrased title - the character limit can be a pain.

Let $X$ be a compact Hausdorff space and $\{F_n\subseteq X:n\in\Bbb N\}$ a decreasing sequence of nonempty closed sets in $X$. For any neighbourhood $\o$ of their intersection $\bigcap_{n\in\Bbb N}F_n$, show that there must exist an $N\in\Bbb N$ such that for all $n\ge N$, $F_n\subseteq\o$.

I have done this exercise - but my proof nowhere used the Hausdorff property. I ask: why is it needed?
My solution:

As the $F_n$ have the finite intersection property, and the space is compact, their intersection is nonempty. $\o$ is then nonempty, and wlog may be considered open. Consider then the family of sets $G_n=F_n\cap X\setminus\o$. For all $n$, $G_n$ is the intersection of two closed sets and thus closed. As $F_{n+1}\subseteq F_n,\,G_{n+1}\subseteq G_n$ for all $n$. Assume for the sake of contradiction that $F_n$ is not a subset of $\o$ for any $n$; this is equivalent to the assumption that $G_n$ is nonempty for all $n$.
If none of the $G_n$ are empty, then $\{G_n:n\in\Bbb N\}$ is a decreasing sequence of closed nonempty sets and thus has the finite intersection property, and thus has nonempty intersection due to the compactness of $X$. Then $\bigcap_{n\in\Bbb N}F_n\cap X\setminus\o\neq\varnothing$, which implies the existence of $x\in\bigcap_{n\in\Bbb N}F_n$ such that $x\notin\o$, which contradicts the assertion that $\o$ is a neighbourhood of $\bigcap_{n\in\Bbb N}$. Since $\{G_n\}$ will always have nonempty intersection unless there is an $N\in\Bbb N$ such that $G_N=\varnothing$, this shows that such an $N$ must exist and that $F_N\cap X\setminus\o=\varnothing,\,F_N\subseteq\o$. It follows from the decreasing property that $\forall n\ge N,\,F_n\subseteq\o\quad\blacksquare$

This exercise was left by Royden in the fourth edition of their text "Real Analysis". My proof nowhere requires the Hausdorff assertion (as far as I can tell) so I'm left wondering if Royden made an oversight. Is this the case?

REPLY [0 votes]: I think you're right. The statement

Let $F_n$ be a FIP family of non-empty closed sets of $X$. If $O$ is open and $\bigcap_n F_n \subseteq O$ then for some $N$: $F_N \subseteq O$.

only needs $X$ to be compact (to apply the FIP criterion for compactness) and doesn't need separation axioms. (and if $n \ge N$ by decreasingness $F_n \subseteq O$ as well etc).
Indeed, if the conclusion failed, $\{F_n\setminus O\mid n \in \Bbb N\}$ would be a FIP family of non-empty closed subsets of $X$ with empty intersection, which cannot be.


text:
\begin{document}
\title{\vspace{-7mm} Time-Domain to Delay-Doppler Domain Conversion of OTFS Signals in Very High Mobility Scenarios}
\author{\IEEEauthorblockN{Saif Khan Mohammed}
\IEEEauthorblockA{ \thanks{Saif Khan Mohammed is with the Department of Electrical Engineering, Indian Institute of Technology Delhi (IITD), New Delhi, India. Email: saifkmohammed@gmail.com. This work is supported by the Prof. Kishan Gupta and Pramila Gupta Chair at IIT Delhi.}}
}
\maketitle

\vspace{-17mm}
\begin{abstract}
In Orthogonal Time Frequency Space (OTFS) modulation, information symbols are embedded in the delay-Doppler (DD) domain instead of the time-frequency (TF) domain.

In order to ensure compatibility with existing OFDM systems (e.g. 4G LTE), most prior work on OTFS receivers consider a two-step conversion, where the received time-domain (TD) signal is firstly converted to a time-frequency (TF) signal (using an OFDM demodulator) followed by post-processing of this TF signal into a DD domain signal.
In this paper, we show that the spectral efficiency (SE) performance of a two-step conversion based receiver degrades in very high mobility scenarios where the Doppler shift is a significant fraction of the communication bandwidth (e.g., control and non-payload communication (CNPC) in Unmanned Aircraft Systems (UAS)).
We therefore consider an {\em alternate} conversion, where the received TD signal is directly converted to the DD domain. The resulting received DD domain signal is shown to be not the same
as that obtained in the two-step conversion considered in prior works.
The alternate conversion does not require an OFDM demodulator
and is shown to have lower complexity than the two-step conversion.
Analysis and simulations reveal that even in very high mobility scenarios, the SE achieved
with the alternate conversion is {\em invariant} of Doppler shift and is significantly higher than the SE achieved with two-step conversion (which degrades with increasing Doppler shift).
\end{abstract}

\begin{IEEEkeywords}

	OTFS, Doppler Spread, Very High Mobility.
\end{IEEEkeywords}
\section{Introduction}
Recently, Orthogonal Time Frequency Space (OTFS) modulation has been introduced, which has been shown to be more robust towards channel induced
Doppler shift when compared to multi-carrier systems (e.g., Orthogonal Frequency Division Multiplexing (OFDM)) \cite{HadaniOTFS1, HadaniOTFS2, HadaniOTFS3}.
This is because, in OTFS modulation, information is embedded in the delay-Doppler (DD) domain instead of the time-frequency (TF) domain.

Due to the sparseness of the effective channel in the DD domain \cite{HadaniOTFS1, HadaniOTFS2, HadaniOTFS3}, most OTFS receivers first convert the received time-domain (TD) OTFS signal to the DD domain and then perform detection in the DD domain \cite{channel, Emanuele2, mimootfs}.\footnote{\footnotesize{In \cite{lmmse}, a time-domain based Linear Minimum Mean Squared Estimation (LMMSE) detector has been proposed. This detector considers the channel path delay and Doppler shifts to be integer multiples of the delay and Doppler domain resolution which results in a sparse banded structure of the inverse LMMSE equalizer matrix, due to which the equalizer matrix can be computed at low complexity. In the very high Doppler spread scenarios considered here,
the sparse banded structure is not valid and therefore this LMMSE detector will have very high complexity in such scenarios.}}

In order to ensure compatibility with existing OFDM based receivers, most prior work on OTFS consider a two-step TD to DD domain conversion, where, i) the received TD signal is converted to a TF signal using the OFDM demodulator, and ii) this TF signal is then converted
to the DD domain \cite{HadaniOTFS1, channel, Emanuele2, mimootfs}. Although the two-step conversion based OTFS receiver is significantly more robust to Doppler shift when compared to OFDM \cite{HadaniOTFS1, HadaniOTFS2, HadaniOTFS3}, in this paper we show that for very high mobility scenarios where the Doppler shift is a significant fraction of the communication bandwidth, the performance of the two-step conversion based OTFS receiver {\em degrades} with increasing Doppler shift.\footnote{\footnotesize{In \cite{chocks2020}, a low-complexity TD based OTFS equalizer has been proposed. The effective channel matrix for which equalization is performed, is exactly same as the effective DD domain channel in a two-step receiver, and therefore just like the two-step receiver, the performance of this equalizer will also degrade in very high mobility scenarios.}}

In this paper, we therefore consider an {\em alternate} conversion, where the received TD signal is directly converted to the DD domain using its ZAK representation. There are possibly several variants of the ZAK representation \cite{Zak1}, but in this paper we use the one considered by A. J. E. M. Janssen in \cite{Janssen}. Subsequently, we refer to an OTFS receiver based on this alternate conversion as the ``ZAK receiver" and that based on the two-step conversion as the ``two-step receiver".
The {\em novel} contributions of this paper are:
\begin{itemize}
\item In Section \ref{seczakotfsig} we derive an expression for the ZAK representation of the transmitted TD OTFS signal in terms of the continuous delay and Doppler variables, $\tau$ and $\nu$ respectively.
\item In Section \ref{seczakrx} we consider an alternate TD to DD domain conversion where the ZAK representation of the received TD signal is sampled at discrete
points in the DD domain. The resulting expression for the sampled DD domain signal is not the same
as that obtained in the two-step conversion considered in prior works.
\item We show that the ZAK representation based alternate conversion has a smaller complexity
when compared to the two-step conversion.

\item Through analysis and simulations we show that in {\em very high} mobility scenarios, the spectral efficiency (SE) achieved by the ZAK receiver is almost {\em invariant}
of the Doppler shift and is greater than the SE achieved by the two-step receiver (which degrades with increasing
mobile speed). One such scenario is the control and non-payload communication (CNPC) between
an Unmanned Aircraft System (UAS) and a Ground Station (GS). This involves low bandwidth communication ($30$ KHz) over a wireless channel where the
Doppler shift can be very high due to high UAS speed \cite{ICTCPaper, Haas}.

\end{itemize}
{\em Notations}: For $x \in {\mathbb R}$, $\lfloor x \rfloor$ is the greatest integer smaller than or equal to $x$.
${\mathbb E}[\cdot]$ denotes the expectation operator. ${\mathcal C}{\mathcal N}(0, \sigma^2)$ denotes
the circular symmetric complex Gaussian distribution with variance $\sigma^2$. For any
matrix ${\bf A}$, $\vert {\bf A} \vert$ denotes its determinant and ${ A}[p,q]$ denotes the
element in its $p$-th row and $q$-th column.

\section{OTFS Modulation}
In OTFS modulation, the delay-Doppler (DD) domain information symbols $x[k,l] \,,\, k=0,1,\cdots, N-1 \,,\, l=0,1,\cdots, M-1$ are firstly converted to Time-Frequency (TF) symbols $X[n,m]\,,\, m=0,1,\cdots, M-1\,,\, n=0,1,\cdots, N-1$
through the inverse Symplectic Finite Fourier Transform (ISFFT) \cite{HadaniOTFS1}, i.e.

{\vspace{-4mm}
\small
\begin{eqnarray}
\label{otfs1}
X[n,m] & \hspace{-3mm} = \hspace{-3mm} & \frac{1}{{MN}}  \sum\limits_{k=0}^{N-1}\sum\limits_{l=0}^{M-1}  x[k,l] \, e^{-j 2 \pi \left(\frac{m l}{M} - \frac{n k}{N}   \right)}.
\end{eqnarray}
\normalsize}
For a given $T > 0 $ and $\Delta f = 1/T$, these TF symbols are then used to generate the time-domain (TD) transmit signal which is given by the Heisenberg transform \cite{HadaniOTFS1}, i.e.

{\vspace{-4mm}
\small
\begin{eqnarray}
\label{otfs2}
x(t) & = &  \sum\limits_{m=0}^{M-1}\sum\limits_{n=0}^{N-1} X[n,m] \, g(t - nT)  \, e^{j 2 \pi m \Delta f (t - nT)}
\end{eqnarray}
\normalsize}
where $g(\cdot)$ is the transmit pulse. When $g(t)$ is approximately time-limited to $[0 \,,\, T]$, the Heisenberg transform in (\ref{otfs2}) is similar to OFDM
where $X[n,m]$ is the symbol transmitted on the $m$-th sub-carrier ($m=0,1,\cdots, M-1$) of the $n$-th OFDM symbol ($n =0,1,\cdots, N-1$). Each OFDM symbol is of duration $T$ and the sub-carrier spacing is $\Delta f$, i.e., each OTFS frame has duration $NT$ and occupies bandwidth $M \Delta f$.

Let us consider a channel consisting of $L$ paths, where the $i$-th path has gain
$h_i$, induces a delay $\tau_i$ ($0 < \tau_i < T$) and a Doppler shift $\nu_i \,,\, i=1,2,\cdots,L$.
Then, with $x(t)$ as the transmitted signal,
the received signal is given by \cite{Bello}

{\vspace{-4mm}
\small
\begin{eqnarray}
\label{zse1}
y(t) & =  & \sum\limits_{i=1}^L h_i  \, x(t - \tau_i) \, e^{j 2 \pi \nu_i (t - \tau_i)} \, + \, n(t)
\end{eqnarray}
\normalsize}
where $n(t)$ is the additive white Gaussian noise (AWGN) with power spectral density $N_0$.
Most prior work
consider a two-step OTFS receiver which is compatible with OFDM receivers and where the received TD signal $y(t)$ is first converted to a discrete TF signal
through the Wigner transform i.e., ${\Tilde Y}[n,m] \Define \int_{-\infty}^{\infty} g(t - nT) y(t) e^{-j 2 \pi m \Delta f t} dt \,,\, m=0,1,\cdots, M-1, n=0,1,\cdots, N-1$.
This discrete TF signal is then converted to a DD domain signal through the Symplectic Finite Fourier Transform (SFFT) i.e.,
${\widehat x}[k',l'] \Define \sum\limits_{m=0}^{M-1}\sum\limits_{n=0}^{N-1} {\Tilde Y}[n,m] e^{j 2 \pi \left( \frac{m l'}{M} - \frac{n k'}{N}\right)}  \,,\, k'=0,1,\cdots,N-1 , l'=0,1,\cdots,M-1$ \cite{HadaniOTFS1, channel, Emanuele2, mimootfs}. With $g(t)=1/\sqrt{T}, 0 \leq t < T$ and zero otherwise, from (\ref{otfs1}), (\ref{otfs2}), (\ref{zse1}) and the two-step receiver operations (i.e., Wigner transform and SFFT), it follows that

{\vspace{-4mm}
\small
\begin{eqnarray}
\label{xhattwostep}
{\widehat x}[k',l'] & = & \sum\limits_{k=0}^{N-1}\sum\limits_{l=0}^{M-1} x[k,l] \, {\widehat h}[k',l',k,l]  \,\, + \,\, {\widehat n}[k',l']
\end{eqnarray}
\normalsize}
where ${\widehat n}[k',l']$ are the DD domain noise samples and ${\widehat h}[k',l',k,l]$ is given by (\ref{hklotfs}) (see top of next page).
\begin{figure*}
{\vspace{-11mm}
\small
\begin{eqnarray}
\label{hklotfs}
{\widehat h}[k',l',k,l] & \hspace{-3mm} =  &  \hspace{-3mm} \sum\limits_{i=1}^L h_i e^{-j 2 \pi \frac{\nu_i}{\Delta f} \frac{\tau_i}{T}} \left(  {\Bigg [} \frac{1}{N} \sum\limits_{n=0}^{N-1} \hspace{-1mm} e^{-j 2 \pi n \left( \frac{k' - k}{N} - \frac{\nu_i}{\Delta f}  \right)} {\Bigg ]} {\widehat h}_{i,1}[l',l]   \,  +   \,   e^{j 2 \pi \left(  \frac{\nu_i}{\Delta f}  -  \frac{k'}{N} \right)}   {\Bigg [} \frac{1}{N} \sum\limits_{n=0}^{N-2} \hspace{-1mm} e^{-j 2 \pi n \left( \frac{k' - k}{N} - \frac{\nu_i}{\Delta f}  \right)} {\Bigg ]} {\widehat h}_{i,2}[l',l] \right), \nonumber \\
{\widehat h}_{i,1}[l',l]  & \hspace{-3mm} \Define  &  \hspace{-3mm}   \frac{ \left( 1 - \frac{\tau_i}{T} \right) }{M} \sum\limits_{m=0}^{M-1} \sum\limits_{m'=0}^{M-1}  \hspace{-1mm} e^{j 2 \pi \left(\frac{m'l'}{M}  - \frac{m l}{M} - \frac{m \tau_i}{T} \right)} e^{j \pi \left( 1 + \frac{\tau_i}{T}  \right) \left( \frac{\nu_i}{\Delta f} - (m' - m) \right)}   \sinc\left( \left(1 - \frac{\tau_i}{T} \right) \left(\frac{\nu_i}{\Delta f} - (m' - m) \right) \right), \nonumber \\
{\widehat h}_{i,2}[l',l]  & \hspace{-3mm}  \Define  &  \hspace{-3mm}   \frac{ \left( \frac{\tau_i}{T} \right) }{M} \sum\limits_{m=0}^{M-1} \sum\limits_{m'=0}^{M-1}  \hspace{-1mm} e^{j 2 \pi \left(\frac{m'l'}{M}  - \frac{m l}{M} - \frac{m \tau_i}{T} \right)} e^{j \pi \frac{\tau_i}{T} \left( \frac{\nu_i}{\Delta f} - (m' - m) \right)}   \sinc\left( \frac{\tau_i}{T}  \left(\frac{\nu_i}{\Delta f} - (m' - m) \right) \right).
\end{eqnarray}
\normalsize}
\end{figure*}

\section{The ZAK Representation of OTFS Signal}
\label{seczakotfsig}

The ZAK transform of $x(t)$ is given by \cite{Janssen}

{\vspace{-4mm}
\small
\begin{eqnarray}
\label{zdef1}
{\mathcal Z}_x(\tau, \nu) & \Define & \sqrt{T} \, \sum\limits_{k=-\infty}^{\infty} \, x(\tau + kT) \, e^{-j 2 \pi k \nu T } \,,\, \nonumber \\
& & -\infty < \tau < \infty \,,\, -\infty < \nu < \infty.
\end{eqnarray}
\normalsize}
Due to the following result, the $\tau-$ and $\nu-$ domains are called
the ``delay" and ``Doppler" domain respectively, i.e., collectively we refer to them as the delay-Doppler (DD) domain.
\begin{theorem}
\label{zlem52}
Let $x(t)$ be the transmitted signal and let there be only one channel path with
a delay of $\tau_0$ and a Doppler shift of $\nu_0$. The ZAK transform of the noise-free received signal
$y(t) = x(t - \tau_0) e^{j 2 \pi \nu_0 (t - \tau_0)}$ is then given by
\begin{eqnarray}
\label{zakmod2}
{\mathcal Z}_y(\tau, \nu) & = & e^{j 2 \pi \nu_0 (\tau - \tau_0)} {\mathcal Z}_x(\tau - \tau_0 , \nu - \nu_0)
\end{eqnarray}
i.e., delay and Doppler shift in time-domain results in a shift along the $\tau-$ and $\nu-$ domains by
$\tau_0$ and $\nu_0$ respectively.
\end{theorem}
\begin{IEEEproof}
From (\ref{zdef1}), the ZAK transform of $y(t)$ is given by
{\vspace{-2mm}
\small
\begin{eqnarray}
\label{zakmod1}
{\mathcal Z}_y(\tau , \nu) & \hspace{-3mm}  = & \hspace{-3mm} \sqrt{T} \sum\limits_{k=-\infty}^{\infty} y(\tau + kT) \, e^{-j 2 \pi \nu k T} \nonumber \\
& \hspace{-8mm} = & \hspace{-5mm} \sqrt{T} \sum\limits_{k=-\infty}^{\infty}  \hspace{-1mm} x(\tau - \tau_0 + kT) \, e^{j 2 \pi \nu_0 (\tau + kT - \tau_0)} \, e^{-j 2 \pi \nu k T} \nonumber \\
& \hspace{-8mm}  = & \hspace{-5mm} e^{j 2 \pi \nu_0 (\tau - \tau_0)} \sqrt{T} \sum\limits_{k=-\infty}^{\infty} \hspace{-1mm}  x(\tau - \tau_0 + kT) \, e^{-j 2 \pi (\nu - \nu_0) k T} \nonumber \\
& \hspace{-8mm} \mya & \hspace{-5mm} e^{j 2 \pi \nu_0 (\tau - \tau_0)} {\mathcal Z}_x(\tau - \tau_0 , \nu - \nu_0)
\end{eqnarray}
\normalsize}
where step (a) follows from (\ref{zdef1}).
\end{IEEEproof}

Let us consider $g(t)$ to be

{\vspace{-4mm}
\small
\begin{eqnarray}
\label{zprf7}
g(t) & =
\begin{cases}
\frac{1}{\sqrt{T}} &, 0 \leq t < T \\
0 &, \mbox{\small{otherwise}} \\
\end{cases}.
\end{eqnarray}
\normalsize}
From (\ref{zdef1}) it follows that in the interval ${\mathcal S} \Define \{ (\tau,\nu) \, | \, 0 \leq \tau < T \,,\, 0 \leq \nu < \Delta f \}$, the ZAK transform of $g(t)$ in (\ref{zprf7}) is

{\vspace{-4mm}
\small
\begin{eqnarray}
\label{zprf88}
{\mathcal Z}_g(\tau , \nu) & = & 1 \,,\, 0 \leq \tau < T \,,\, 0 \leq \nu < \Delta f.
\end{eqnarray}
\normalsize}
From (\ref{zdef1}) it follows that for any $n \in {\mathbb Z}$

{\vspace{-4mm}
\small
\begin{eqnarray}
\label{zprf89}
{\mathcal Z}_g(\tau - nT , \nu) & \hspace{-3mm}  = &  \hspace{-3mm} \sqrt{T} \sum\limits_{k=-\infty}^{\infty} \hspace{-2mm} g(\tau - nT + kT) \, e^{-j 2 \pi k \nu T} \nonumber \\
& \hspace{-25mm}  = & \hspace{-14mm} e^{-j 2 \pi \nu n T} \sqrt{T} \hspace{-1mm} \sum\limits_{k=-\infty}^{\infty} \hspace{-2mm} g(\tau +(k - n)T) \, e^{-j 2 \pi (k-n) \nu T} \nonumber \\
& \hspace{-25mm} =  & \hspace{-14mm}  e^{-j 2 \pi \nu n T} \, {\mathcal Z}_g(\tau, \nu)
\end{eqnarray}
\normalsize}
i.e., ${\mathcal Z}_g(\tau,\nu)$ is {\em quasi-periodic} along the delay domain \cite{Janssen}.
From the above derivation it is clear that quasi-periodicity
holds not just for ${\mathcal Z}_g(\tau,\nu)$ but is valid for the ZAK transform of any finite energy time-domain signal. Also,
for any $m \in {\mathbb Z}$, ${\mathcal Z}_g(\tau , \nu + m\Delta f) = {\mathcal Z}_g(\tau , \nu)$ (see $(2.20)$ and $(2.21)$ in \cite{Janssen}).
Using these facts along with (\ref{zprf88}) it follows that
\begin{eqnarray}
\label{zprf8}
\hspace{-3mm} {\mathcal Z}_g(\tau , \nu) & \hspace{-3mm}  = &  \hspace{-3mm} e^{j 2 \pi \nu \left\lfloor \frac{\tau}{T}\right\rfloor T} \,,\, -\infty < \tau < \infty \,,\, -\infty < \nu < \infty.
\end{eqnarray}
The following theorem gives the expression for the ZAK transform of the transmit OTFS signal $x(t)$.
\begin{theorem}
\label{zthm2}

The ZAK transform of $x(t)$ in (\ref{otfs2}) is

{\vspace{-4mm}
\small
\begin{eqnarray}
\label{zprf6}
\hspace{-4mm} {\mathcal Z}_x(\tau, \nu) & \hspace{-3mm}  = & \hspace{-3mm} \sum\limits_{k=0}^{N-1}\sum\limits_{l=0}^{M-1} x[k,l] \, \Phi_{k,l}(\tau,\nu) \,,\,  \nonumber \\
\hspace{-4mm} \Phi_{k,l}(\tau,\nu) & \hspace{-3mm}  \Define & \hspace{-3mm} \frac{{\mathcal Z}_g(\tau,\nu)}{MN}  \sum\limits_{m=0}^{M-1}\sum\limits_{n=0}^{N-1} {\Bigg [}  e^{-j 2 \pi n T \left( \nu - k \frac{\Delta f}{N} \right)} \nonumber \\
& & \hspace{30mm}  e^{j 2 \pi m \Delta f \left( \tau - \frac{lT}{M} \right)} {\Bigg]},

\end{eqnarray}
where ${\mathcal Z}_g(\tau,\nu)$ is given by (\ref{zprf8}).
\normalsize}
\end{theorem}
\begin{IEEEproof}
See Appendix \ref{appendix_thm2}.
\end{IEEEproof}

From Theorem \ref{zthm2}, it is clear that $\Phi_{k,l}(\tau,\nu)$ are the basis signals in the DD domain.
Taking the expression of ${\mathcal Z}_g(\tau , \nu)$ from (\ref{zprf8}) into (\ref{zprf6}), and using the fact that $T \Delta f = 1$, we get

{
\vspace{-4mm}
\small
\begin{eqnarray}
\label{zprf9}
\hspace{-3mm} \Phi_{k,l}(\tau, \nu) & \hspace{-3mm} = &  \hspace{-3mm} e^{j 2 \pi \frac{\nu}{\Delta f}  \left\lfloor \frac{\tau}{T}\right\rfloor } w_{1}\left(\nu - \frac{k \Delta f}{N}\right) \, w_{2}\left(\tau - \frac{lT}{M}\right) \,,\,  \nonumber \\
\hspace{-4mm} w_{1}(\nu)  & \hspace{-3.5mm}  \Define  &  \hspace{-3.5mm}  \frac{1}{N} \hspace{-1mm} \sum\limits_{n=0}^{N-1}  \hspace{-1mm} e^{-j 2 \pi n \nu T }   =  e^{-j \pi (N-1) \frac{\nu}{\Delta f}}  \frac{\sin\left( \pi N \frac{\nu}{\Delta f} \right)}{N\sin\left( \pi \frac{\nu}{ \Delta f} \right)} \nonumber \\
\hspace{-4mm} w_{2}(\tau)  & \hspace{-3.5mm}  \Define & \hspace{-3.5mm}  \frac{1}{M} \hspace{-1mm} \sum\limits_{m=0}^{M-1}  \hspace{-1mm} e^{j 2 \pi m \Delta f \tau }  =  e^{j \pi (M-1) \frac{\tau}{T} } \frac{\sin\left( \pi M  \frac{\tau}{T}  \right)}{M\sin\left(\pi \frac{\tau}{T} \right)}.
\end{eqnarray}
\normalsize}
\section{An Alternate TD to DD Domain Conversion}
\label{seczakrx}
In (\ref{zprf9}), apart from the quasi-periodicity term $e^{j 2 \pi \frac{\nu}{\Delta f} \left\lfloor \frac{\tau}{T}\right\rfloor }$, the $(k,l)$-th basis signal $\Phi_{k,l}(\tau,\nu)$ is a {\em product} of two signals, $w_{1}\left(\nu - \frac{k \Delta f}{N}\right)$ and $w_{2}\left(\tau - \frac{lT}{M}\right)$, which are shifted versions of the basic pulses $w_1(\nu)$ and $w_2(\tau)$ along the Doppler and delay domain respectively.
From (\ref{zprf9}) it is clear that $w_{2}\left(\tau - \frac{lT}{M}\right)$ and $w_{1}\left(\nu - \frac{k \Delta f}{N}\right)$ are localized around $\tau =  l T/M$ along the delay domain and around $\nu = k \Delta f/N$ along the Doppler domain, respectively.

From (\ref{zprf9}) it is also clear that the basic pulses have a null at the centre location of all other shifted versions, i.e., $w_{1}(\nu = k \Delta f/N) = 0 \,,\, k = 1,\cdots, N-1$ and
$w_{2}(\tau = l T/M) = 0 \,,\, l = 1,\cdots, M-1$. This suggests a receiver where the received TD signal $y(t)$ is directly transformed to its ZAK representation ${\mathcal Z}_y(\tau, \nu)$, followed by
sampling ${\mathcal Z}_y(\tau, \nu)$
at integer multiples of $T/M$ along the delay domain and at integer multiples of $\Delta f/N$ along the Doppler domain.

In this paper, we therefore consider an alternate conversion of the TD signal $y(t)$ in (\ref{zse1}) to a DD domain signal, by sampling the ZAK transform of $y(t)$ (i.e., ${\mathcal Z}_y(\tau,\nu)$) at discrete points $(\tau = l'T/M, \nu = k'\Delta f/N)$, $l'=0,1,\cdots,M-1, k'=0,1,\cdots,N-1,$ in the DD domain.
Subsequently, we refer to a OTFS receiver using this alternate conversion, as the ``ZAK receiver".
The sampled DD domain signal in the ZAK receiver is then given by

{\vspace{-4mm}
\small
\begin{eqnarray}
\label{zprf11}
Y[k',l'] & \Define & {\mathcal Z}_y\left(\tau = \frac{l'T}{M} \,,\, \nu = \frac{k' \Delta f}{N} \right) \,,\, \nonumber \\

& \mya &   \sqrt{T} \sum\limits_{n=0}^{N} y\left(nT + \frac{l'T}{M}  \right) e^{-j 2 \pi n \frac{k'}{N}} \nonumber \\
\hspace{-12mm} & \hspace{-8mm}  & \hspace{-4mm} k' = 0,1,\cdots, N-1 \,,\, l' = 0,1,\cdots, M-1
\end{eqnarray}
\normalsize}
where step (a) follows from (\ref{zdef1}) and the fact that the received signal $y(t)$ is time-limited to the interval $0 < t < (N+1)T$. This is because, the channel path delays are less than $T$ ($0 < \tau_i < T, i=1,2,\cdots,L$) and the transmit signal $x(t)$ is limited to the time interval $0 \leq t < NT$ as $g(t)$ is time-limited
to $0 \leq t < T$ (see the expression for $x(t)$ in (\ref{otfs2})). We also note that the discrete time-domain samples $y\left(nT + \frac{l'T}{M}  \right) \,,\, n=0,1,\cdots, N, l'=0,1,\cdots, M-1$
are obtained by sampling $y(t)$ at integer multiples of $1/(M \Delta f) = T/M$.

The ZAK transform of $y(t)$ in (\ref{zse1}) is given by

{\vspace{-4mm}
\small
\begin{eqnarray}
\label{zprf12}
{\mathcal Z}_y(\tau,\nu) &  \hspace{-2mm}  \mya &  \hspace{-2mm} \sum\limits_{i=1}^L h_i  \, e^{j 2 \pi \nu_i (\tau - \tau_i)} {\mathcal Z}_x(\tau - \tau_i,\nu - \nu_i)  \, + \,  {\mathcal Z}_{n}(\tau,\nu) \nonumber \\
& \hspace{-25mm}  \myb & \hspace{-15mm} \sum\limits_{k=0}^{N-1}\sum\limits_{l=0}^{M-1} \hspace{-1mm} x[k,l] {\Bigg [} \sum\limits_{i=1}^L  h_i  \, e^{j 2 \pi \nu_i (\tau - \tau_i)} e^{j 2 \pi \frac{(\nu - \nu_i)}{\Delta f} \left\lfloor \frac{\tau - \tau_i}{T}  \right\rfloor }  \nonumber \\
& & \hspace{-10mm}   w_{1}\hspace{-1mm}\left(\nu - \nu_i - \frac{k \Delta f}{N} \right) w_{2}\hspace{-1mm}\left(\tau - \tau_i - \frac{lT}{M}\right)  {\Bigg ]} + {\mathcal Z}_{n}(\tau,\nu)
\end{eqnarray}
\normalsize}
where step (a) follows from Theorem \ref{zlem52} and step (b) follows from Theorem \ref{zthm2} and (\ref{zprf9}).
In (\ref{zprf12}), ${\mathcal Z}_{n}(\tau,\nu)$ is the ZAK transform of the AWGN $n(t)$.
Using (\ref{zprf12}) in (\ref{zprf11}), we get

{\vspace{-4mm}
\small
\begin{eqnarray}
\label{zprf13}
\hspace{-1mm} Y[k',l'] & \hspace{-4.5mm} = &  \hspace{-4.5mm}   \sum\limits_{k=0}^{N-1}\sum\limits_{l=0}^{M-1}  x[k,l] \, {\Tilde h}[k',l',k,l]  \,  + \,  Z[k',l'] \nonumber \\
{\Tilde h}[k',l',k,l]  & \Define & \sum\limits_{i=1}^L  h_i[k',l']  \,  {\Bigg [} w_{1}\hspace{-1mm}\left(\frac{(k' - k) \Delta f}{N} - \nu_i  \right) \nonumber \\
& & \hspace{21mm} w_{2}\hspace{-1mm}\left( \frac{(l' - l)T}{M} - \tau_i \right)  {\Bigg ]} \nonumber \\
Z[k',l'] & \Define & {\mathcal Z}_{n}\left({l'T}/{M},{k' \Delta f}/{N}\right) \nonumber \\
h_i[k',l'] & \hspace{-3mm}  \Define &  \hspace{-3mm} h_i  \, e^{j 2 \pi \frac{\nu_i}{\Delta f} \left(\frac{l'}{M} - \frac{\tau_i}{T}\right)} e^{j 2 \pi \left(\frac{k' }{N} -  \frac{\nu_i}{\Delta f} \right) \left\lfloor \left(\frac{l'}{M} - \frac{\tau_i}{T}\right)  \right\rfloor } \nonumber \\
& & \hspace{-8mm} k'=0,1,\cdots, N -1 \,,\, l' =0,1,\cdots, M-1.
\end{eqnarray}
\normalsize}
The noise samples in the DD domain are given by

{\vspace{-4mm}
\small
\begin{eqnarray}
\label{zprf73}
\hspace{-1mm} Z[k',l'] & \hspace{-3mm}  = & \hspace{-3mm} {\mathcal Z}_{n}\left(\frac{l'T}{M},\frac{k' \Delta f}{N}\right)  \mya  \sqrt{T} \sum\limits_{k=0}^{N}  n\left(\frac{l' T}{M} + kT\right) e^{-j 2 \pi k \frac{k'}{N}} \nonumber \\
& \hspace{-12mm} = &  \hspace{-8mm} \sqrt{T} \sum\limits_{k=0}^{N-1} n\left(\frac{l' T}{M} + kT\right) e^{-j 2 \pi k \frac{k'}{N}} \, + \, \sqrt{T} \, n \left(\frac{l'T}{M} + NT  \right)\nonumber \\
& & k'=0,1,\cdots, N -1 \,,\, l' =0,1,\cdots, M-1
\end{eqnarray}
\normalsize}
where step (a) follows from (\ref{zdef1}) and the fact that the received signal $y(t)$ is time-limited to $0 < t < NT$.
By comparing the expression for ${\widehat h}[k',l',k,l]$ in (\ref{hklotfs}) and ${\Tilde h}[k',l',k,l]$ in (\ref{zprf13}) it is clear that the received discrete DD domain signal
for the two-step receiver (i.e. ${\widehat x}[k',l']$ in (\ref{xhattwostep})) is not the same as that for the ZAK receiver (see $Y[k',l']$ in (\ref{zprf13})).

From (\ref{zprf11}) it is clear that for a given $l'$, $Y[k',l']$
can be computed for all $k' = 0, 1, \cdots, N-1$ using a N-point Discrete Fourier Transform (DFT) whose complexity is $O(N \log N)$. Therefore the complexity of the alternate conversion, i.e., computing
$Y[k',l']$ from $y(t)$ for all $k'=0,1,\cdots, N-1 \,,\, l'=0,1,\cdots, M-1$ is $O(MN \log N)$.
For the two-step conversion, the complexity of computing SFFT is $O(MN \log (MN))$ which is greater than $O(MN\log (N))$.
Further, the alternate conversion does not require an OFDM demodulator.

With information symbols $x[k,l] \sim \, \mbox{i.i.d.} \, {\mathcal C}{\mathcal N}(0, E)$, ${\mathbb E}\left[ \int_{-\infty}^{\infty} \hspace{-1mm} \vert x(t) \vert^2 dt \right]   =  E$
(follows from (\ref{zprf61}) in Appendix \ref{appendix_thm2}).
Since $x(t)$ is time-limited to $NT$ seconds, the average transmit power is $E/NT$. With a communication bandwidth of
$M \Delta f$, the AWGN power at the receiver is $M \Delta f N_0$ and therefore the ratio of the transmit power to the receiver noise
power is

{\vspace{-4mm}
\small
\begin{eqnarray}
\label{eqnrho}
\rho & \Define & \frac{E/NT}{M \Delta f N_0} = \frac{E}{MN N_0}.
\end{eqnarray}
\normalsize}

Let the received DD domain samples $Y[k',l']$ and the transmitted information symbols $x[k,l]$ be arranged into vectors ${\bf y}$ and ${\bf x}$
respectively as given by (\ref{zprf14}) (see top of next page).
\begin{figure*}
{\vspace{-11mm}
\small
\begin{eqnarray}
\label{zprf14}
{\bf y}  &  \Define  & (Y[0,0], Y[0,1], \cdots, Y[0, M-1], Y[1,0], \cdots, Y[1,M-1], \cdots, Y[N-1, 0], \cdots, Y[N-1,M-1])^T \nonumber \\
{\bf x}  &  \Define  & (x[0,0], x[0,1], \cdots, x[0, M-1], x[1,0], \cdots, x[1,M-1], \cdots, x[N-1, 0], \cdots, x[N-1,M-1])^T \nonumber \\
{\bf z}  &  \Define  & (Z[0,0], Z[0,1], \cdots, Z[0, M-1], Z[1,0], \cdots, Z[1,M-1], \cdots, Z[N-1, 0], \cdots, Z[N-1,M-1])^T.
\end{eqnarray}
\normalsize}
\end{figure*}
From (\ref{zprf13}) it then follows that
\begin{eqnarray}
\label{zprf15}
{\bf y} & = & {\bf H} \, {\bf x} \, + \, {\bf z}
\end{eqnarray}
where ${\bf z}$ is the vector of noise samples in the DD domain (see (\ref{zprf14})) and ${\bf H} \in {\mathbb C}^{MN \times MN}$
is the equivalent DD domain channel matrix. The element of ${\bf H}$ in its $(l' + k'M +1)$-th row and $(l + kM +1)$-th column is
${\Tilde h}[k',l',k,l]$ (see (\ref{zprf13})). Let ${\bf K}_{{\bf z}} \Define {\mathbb E}[{\bf z} \, {\bf z}^H]$ denote the covariance matrix of ${\bf z}$. In (\ref{zprf73}), the AWGN samples $n\left(\frac{l' T}{M} + kT\right) \,,\, l' = 0,1,\cdots, M-1, k =0,1,\cdots, N$ are i.i.d. ${\mathcal C}{\mathcal N}(0, M \Delta f N_0)$,\footnote{\footnotesize{As the communication bandwidth is $M \Delta f = M/T$, the received time-domain signal is
filtered with a low-pass filter having bandwidth $M/T$ due to which noise samples taken at integer multiples of $T/M$ are i.i.d. ${\mathcal C}{\mathcal N}(0, M \Delta f N_0)$.}} and therefore the element of ${\bf K}_{{\bf z}}$ in its $(k_1M + l_1 +1)$-th row and
$(k_2M + l_2 +1)$-th column is given by

{\vspace{-4mm}
\small
\begin{eqnarray}
\label{kzeqn}
{K}_{{\bf z}}[{k_1M + l_1 +1,k_2M + l_2 +1}] & =  {\mathbb E}[ Z[k_1,l_1] Z^*[k_2, l_2]] \nonumber \\
& \hspace{-30mm} = \begin{cases}
M N N_0 \left(1 + \frac{1}{N} \right) &, k_1 = k_2 \,,\, l_1 = l_2 \\
M N N_0  \left( \frac{1}{N} \right) &, k_1 \ne k_2 \,,\, l_1 = l_2 \\
0  &, l_1 \ne l_2 \\
\end{cases}.
\end{eqnarray}
\normalsize}
From (\ref{kzeqn}) it is also clear that
\begin{eqnarray}
\label{largeNeqn}
\lim\limits_{N \rightarrow \infty} \frac{{\bf K}_{{\bf z}}}{MNN_0} & = & {\bf I}
\end{eqnarray}
where ${\bf I}$ denotes the $MN \times MN$ identity matrix.
With perfect knowledge of ${\bf H}$ at the receiver and joint equalization of all $MN$ information symbols in the DD domain, the achievable spectral efficiency (SE) of the ZAK receiver is given by \cite{DTse}

{\vspace{-4mm}
\small
\begin{eqnarray}
\label{zprfcap}

C_{\mbox{\tiny{Zak}}}  & \mya & \frac{1}{MN} \log_2 \left\vert {\bf I} + \rho \, {\bf H}^{\bf H} \left(\frac{{\bf K}_{{\bf z}}}{MNN_0}\right)^{-1} {\bf H} \right\vert \nonumber \\
& \approx & \frac{1}{MN} \log_2 \left\vert {\bf I} + \rho \, {\bf H}^{\bf H} {\bf H} \right\vert  \,\,\,\, (\mbox{\small{Large $N$}})
\end{eqnarray}
\normalsize}
where step (a) follows from (\ref{eqnrho}) and (\ref{zprf15}), and the approximation follows from (\ref{largeNeqn}).

{\em Example}: In the following we compare the ZAK receiver and the two-step receiver for a
single-path channel (i.e., $L=1$) with zero delay and a Doppler shift equal to an integer multiple of $\Delta f$ i.e., $\nu_1 = q \Delta f, q \in \{ 0,1,\cdots, M-1\}$.
From (\ref{hklotfs}) and (\ref{zprf13}) we then have

{\vspace{-4mm}
\small
\begin{eqnarray}
\label{cmpotfs}
{\widehat h}[k',l',k,l]  & \hspace{-3mm}  = &  \hspace{-3mm} h_1 e^{j 2 \pi \frac{ql'}{M}} \delta[k - k'] \,  {\Bigg [}  \frac{1}{M} \hspace{-1mm} \sum\limits_{m=0}^{M-1-q} e^{j 2 \pi m \frac{(l' -l)}{M}}  {\Bigg ]}  \nonumber \\
{\Tilde h}[k',l',k,l]  & \hspace{-3mm} = & \hspace{-3mm}  h_1 e^{j 2 \pi \frac{ql'}{M}} \delta[k - k'] \,   \delta[l - l']
\end{eqnarray}
\normalsize}
where $\delta[k], k \in {\mathbb Z}$ is one when $k=0$ and is zero for all other $k \ne 0$. Just as in (\ref{zprf15}) for the ZAK receiver, for the two-step receiver also, let ${\widehat {\bf H}} \in {\mathcal C}^{MN \times MN}$ denote the effective DD domain channel matrix whose element in its $(k'M + l'+1)$-th row and $(kM + l +1)$-th column is ${\widehat h}[k',l',k,l]$.
The spectral efficiency achieved by the two-step receiver is $C \Define \left(\log_2 \left\vert {\bf I} + \rho {\widehat {\bf H}}^H {\widehat {\bf H}}  \right\vert\right)/(MN)$. Let ${\widehat I}[k_1, k_2, l_1, l_2]$ denote the element of ${\widehat {\bf H}}^H{\widehat {\bf H}}$ in its $(k_1M + l_1 + 1)$-th row and $(k_2M + l_2 + 1)$-th column. From (\ref{cmpotfs}) it then follows that
\begin{eqnarray}
\label{cmpotfs1}
\hspace{-1mm} {\widehat I}[k_1, k_2, l_1, l_2] & \hspace{-3mm}  = & \hspace{-3mm} \delta[ k_1 - k_2] \vert h_1 \vert^2 \, \frac{1}{M} \hspace{-1mm} \sum\limits_{m=0}^{M - q - 1} \hspace{-2mm} e^{j 2 \pi \frac{m (l_1 - l_2)}{M}}.
\end{eqnarray}
For the ZAK receiver, from (\ref{cmpotfs}) it follows that ${\bf H}^H{\bf H} = {\bf H}{\bf H}^H = \vert h_1 \vert^2 {\bf I}$, and therefore from (\ref{zprfcap}) it follows that for large $N$, $C_{\mbox{\tiny{Zak}}} \approx \log_2(1 + \rho \vert h_1 \vert^2)$ which is {\em same} as the capacity of an ideal single-path channel without any Doppler shift. Further, from (\ref{cmpotfs1})

it follows that ${\widehat {\bf H}}^H {\widehat {\bf H}}$ is a block diagonal matrix where each block along the diagonal is a $M \times M$ matrix ${\bf A}$ whose
element in the $(l_1+1)$-th row and $(l_2+1)$-th column is $\vert h_1 \vert^2 \, \frac{1}{M} \hspace{-1mm} \sum\limits_{m=0}^{M - q - 1} \hspace{-2mm} e^{j 2 \pi \frac{m (l_1 - l_2)}{M}}, l_1=0,1,\cdots,M-1\,,\, l_2=0,1,\cdots,M-1$. The spectral efficiency achieved by the two-step receiver is therefore $C = \frac{1}{M} \log_2 \left\vert  {\bf I} + \rho {\bf A} \right\vert$. One can check that ${\bf A}$ is a positive semi-definite matrix and the DFT vectors ${\bf u}_p =  \frac{1}{\sqrt{M}}\left( 1, e^{\frac{j 2 \pi p}{M}}, \cdots, e^{\frac{j 2 \pi p (M-1)}{M}}  \right)^T, p=0,1,\cdots, M-1$ are a set of $M$ orthonormal eigen-vectors of ${\bf A}$ with corresponding eigen-values
$\lambda_p = \vert h_1 \vert^2 \,,\, p=0,1,\cdots,(M-q-1)$ and $\lambda_p = 0 \,,\, p=(M-q), \cdots, M-1$. From this it follows that $C = \frac{1}{M} \log_2 \left\vert  {\bf I} + \rho {\bf A} \right\vert = \left(1 - \frac{q}{M} \right) \log_2(1 + \rho \vert h_1 \vert^2) = \left(1 - \frac{\nu_1}{M \Delta f} \right) \log_2(1 + \rho \vert h_1 \vert^2)$ which is clearly less than $C_{\mbox{\tiny{Zak}}}$.
Therefore, if the ratio of the Doppler shift to the communication bandwidth (i.e., $\nu_1/(M \Delta f)$) is high, the spectral efficiency of the two-step receiver
will be {\em significantly} less than $C_{\mbox{\tiny{Zak}}}$.

\begin{figure}[t]
\vspace{-0.7 cm}
\hspace{-0.2 in}
\centering

\includegraphics[width= 3.0 in, height= 2.2 in]{otfsuaspeed.eps}
\vspace{-0.2 cm}
\caption{Spectral Efficiency versus UAS speed (m/s).}
\vspace{-0.2cm}
\label{Zakrxfig1}
\end{figure}

\begin{figure}[t]
\vspace{-0.2 cm}
\hspace{-0.2 in}
\centering

\includegraphics[width= 3.0 in, height= 2.2 in]{sevsrho.eps}
\vspace{-0.2 cm}
\caption{Spectral Efficiency (bps/Hz) versus $\rho$ (dB).}
\vspace{-0.4cm}
\label{Zakrxfig2}
\end{figure}

\section{Numerical Simulations}
In this section we compare the average spectral efficiency (SE) achieved by the two-step OTFS receiver and the
ZAK receiver for control and non-payload communication (CNPC) between an Unmanned Aircraft System (UAS)
and a Ground Station (GS) when the aircraft is en-route at an altitude of about $10$ Km \cite{ICTCPaper}. For the en-route scenario a widely
accepted model is the two-path model, with the direct path having a deterministic gain and the reflected path having a Rayleigh faded gain, i.e., $h_1 = \sqrt{K/(K+1)}$, $h_2 \sim {\mathcal C}{\mathcal N}(0, 1/(K+1))$
\cite{Haas}. In \cite{Haas} it is mentioned that $K$ is typically $15$ dB and is usually not below $2$ dB. The delay between these two paths
is $33 \, \mu s$ (i.e., $\tau_1=0, \tau_2 = 33 \, \mu s$).
The Doppler shift for the two paths is $\nu_1 = v f_c/c, \nu_2 = (v f_c/c) \cos\left(\pi - \omega U \right)$ where $v$ is the speed of the aircraft, $c$ is the speed of light, $f_c$ is the carrier frequency,
$U$ is uniformly distributed in $[0 \,,\, 1]$ and $\omega = 3.5^{\circ}$ is the Doppler beamwidth \cite{Haas}.
The total time duration for a downlink CNPC frame is $23$ ms, the channel bandwidth is $30$ KHz and $f_c = 5.06$ GHz \cite{ICTCPaper}. We therefore choose $M = 15, N = 46$ and $\Delta f = 2 $ KHz.

In Fig.~\ref{Zakrxfig1} we plot the average SE achieved by the two-step receiver (i.e., ${\mathbb E}[C] = (1/MN){\mathbb E}\left[\log_2 \left\vert {\bf I} + \rho {\widehat {\bf H}}^H {\widehat {\bf H}}  \right\vert \right]$) and that achieved by the ZAK receiver (i.e., ${\mathbb E}[C_{\mbox{\tiny{Zak}}}]$, see (\ref{zprfcap})), as a function of increasing UAS speed for a fixed $\rho = 10$ dB. The averaging of the SE is w.r.t. $h_2$ and $\nu_2$. It is observed that the
SE of the two-step receiver decreases with increasing UAS speed whereas that of the ZAK receiver is almost {\em invariant} of the Doppler shift.

At high UAS speed of $400$ m/s (ratio of the maximum Doppler shift to the bandwidth is $0.225$) and a typical $K=15$ dB, the SE achieved by the ZAK receiver is roughly $0.7$ bits/s/Hz higher than that achieved by a two-step receiver.
In Fig.~\ref{Zakrxfig2}, we study the SE comparison as a function of increasing $\rho$ for a fixed UAS speed of $400$ m/s. To achieve a desired high SE, the two-step receiver needs a significantly higher transmit power when compared to
the ZAK receiver.

\appendices

\section{Proof of Theorem \ref{zthm2}}
\label{appendix_thm2}
From (\ref{otfs1}) and (\ref{otfs2}) it follows that

{\vspace{-4mm}
\small
\begin{eqnarray}
\label{zprf61}
x(t) & \hspace{-2mm}  = & \hspace{-2mm} \sum\limits_{k=0}^{N-1}\sum\limits_{l=0}^{M-1} x[k,l] \, \phi_{k,l}(t) \nonumber \\
\phi_{k,l}(t) & \hspace{-2mm} \Define &  \hspace{-2mm} \sum\limits_{m=0}^{M-1}\sum\limits_{n=0}^{N-1} \hspace{-1mm} \frac{g(t - nT)}{MN}  e^{j 2 \pi n \frac{k}{N}} e^{j 2 \pi m \Delta f \left(t - \frac{lT}{M} \right)}.
\end{eqnarray}
\normalsize}
Taking the ZAK transform of the expression for $x(t)$ in (\ref{zprf61}), from (\ref{zdef1}) we have

{\vspace{-4mm}
\small
\begin{eqnarray}
\label{zprf62}
{\mathcal Z}_x(\tau,\nu) & = & \sum\limits_{k=0}^{N-1}\sum\limits_{l=0}^{M-1} x[k,l] \, \Phi_{k,l}(\tau,\nu) \,,\, \mbox{\small{where}}\nonumber \\
 \Phi_{k,l}(\tau,\nu) & \mya & \sqrt{T} \sum\limits_{k' = -\infty}^{\infty} \phi_{k,l}(\tau+k' T) e^{-j 2 \pi \nu k' T} \nonumber \\
& \hspace{-39mm}  \myb &  \hspace{-22mm} \sum\limits_{m=0}^{M-1}\sum\limits_{n=0}^{N-1} \hspace{-1mm} \frac{1}{MN} e^{j 2 \pi \left( \frac{nk}{N} - \frac{m l}{M} \right)}  {\Bigg [} \sqrt{T} \hspace{-2mm} \sum\limits_{k' = -\infty}^{\infty} \hspace{-2mm} e^{j 2 \pi m \Delta f (\tau + k'T) } \nonumber \\
 & &   \hspace{16.5mm} g(\tau + k'T - nT) e^{-j 2 \pi \nu k' T} {\Bigg ]}
\end{eqnarray}
\normalsize}
where step (a) follows from (\ref{zdef1}) and step (b) follows from substituting the expression
for $\phi_{k,l}(t)$ from (\ref{zprf61}) into the R.H.S. of step (a).
The ZAK transform of $g(t - nT)$ is

{\vspace{-4mm}
\label{zprf63}
\begin{eqnarray}
\label{gtmnt}
\sqrt{T} \hspace{-1mm} \sum\limits_{k' = -\infty}^{\infty} \hspace{-2mm} g(\tau + k'T - nT) e^{-j 2 \pi k' \nu T}  \mya e^{- j 2 \pi \nu n T} {\mathcal Z}_g(\tau,\nu)
\end{eqnarray}
\normalsize}
where ${\mathcal Z}_g(\tau,\nu)$ is the ZAK transform of $g(t)$ and step (a) follows from the first and third equality in (\ref{zprf89}).
Using (\ref{gtmnt}) in (\ref{zprf62}) along with the fact that $e^{j 2 \pi m \Delta f (\tau + k' T)} = e^{j 2 \pi m \Delta f \tau}$ (since $ T \Delta f = 1$)
completes the proof.


TITLE: Proving Specific Quotient Group is Torsion-Free
QUESTION [0 upvotes]: I am trying to prove that the quotient group $(\mathbb{Z} \oplus \mathbb{Z})/(\mathbb{Z} \cdot (11,13))$ is torsion-free.
I know how I have to show that the only element in the group that has finite order is the identity, but I do not know where to start. I was trying to do contradiction, but did not make much progress.
I was also wondering if this can be generalized to other primes in $\mathbb{Z}$ other than 11,13?

REPLY [2 votes]: @Lord Shark's argument goes through for $(u,v)$ with $u$ and $v$ coprime.   See this.  Thus, the quotient is isomorphic to $\mathbb Z$...


TITLE: What do people mean by a "smooth but not analytic" function?
QUESTION [0 upvotes]: Can you give any examples? How does this relate to the Taylor series? Is it trye that all analytic functions are smooth, but not all smooth functions are analytic?

REPLY [1 votes]: This has been asked and answered before. Here's the link:
What is the difference between the terms smooth, analytical and continuous?
But anyway, smooth functions are infinitely differentiable. That is, all of their higher order derivates exist.
A function is analytic at a point if it has a power series expansion that converges in some disk about this point.
Analytic functions are also smooth functuins, but the converse is not true.
Below is a link to an example of a function that is smooth but not analytic:
https://en.m.wikipedia.org/wiki/Non-analytic_smooth_function


TITLE: Help on this surface integral?
QUESTION [1 upvotes]: Calculate the following:
$$\int_S z \, dS$$
where S is the surface $$ z = x^2 + y^2 , x^2 + y^2 \le 1$$

REPLY [1 votes]: It is a paraboloide of revolution defined in cylindrical coordinates by $$r=\sqrt {x^2+y^2}=\sqrt {z} $$
with $$0\le z \le 1.$$
the element of surface is
$$2\pi r dz =2\pi\sqrt {z}dz $$
the integrale is
$$2\pi\int_0^1z\sqrt {z}dz=$$
$$2\pi\frac {2}{5}=\frac {4\pi}{5} $$