TITLE: Is the Wave function a "Smooth" function of the Potential?
QUESTION [3 upvotes]: Consider the Schroedinger equation in a spherically symmetric system. In the unit system under which energy is measured in Hartree and length in Bohr radius $a_0$, the schroedinger equation can be written as
$$
-{d^2 R_{l,\epsilon}(r) \over dr^2} + \left( V_d(r) + {l(l+1)\over 2 r^2} \right)R_{l, \epsilon}(r) = \epsilon R_{l, \epsilon}(r)
$$
. In the above equation, $V_d(r)$ is an attractive potential that's dependent on $d$. Specifically, we will consider the following potential. $V_{0}(r) = -Z(r)/r$, where $\lim_{r \rightarrow 0}Z(r) = Z$ and $\lim_{r \rightarrow \infty} Z(r) = 1$. $V_d(r) = V_0(r) + {1 \over r} - {e^{-r/d} \over r}$ ($d>0$). Consider the wave function $R_{l, \epsilon}^{reg}(r)$ that is regular at the origin and which is normalised to unit magnitude at infinity. In other words,
$$
R_{l, \epsilon}^{reg}(r) \rightarrow \sin(k r + \phi)
$$,
as $r \rightarrow \infty$. $k = \sqrt{2 \epsilon}$. My question is, for at least $\epsilon>0$, is $R_{l, \epsilon}^{reg}(r)$ a "smooth" function of $d$?

REPLY [1 votes]: The radial Hydrogen equation is
$$
      \frac{1}{r^2}\frac{d}{dr}r^2\frac{dR}{dr} + \left[\frac{2\mu}{\hbar^2}\{E-V(r)\}-\frac{l(l+1)}{r^2}\right]R=0,
$$
where $V$ is the Coulomb potential
$$
          V(r) = -\frac{Ze^2}{4\pi\epsilon_{0}r}.
$$
This equation is considered on $L^2_{r^2}(0,\infty)$ because of the $r^2$ weight arising from the spherical coordinate volume element. Because this is a Math site, I'll get rid of the Physical constants:
$$
               \frac{1}{r^2}\frac{d}{dr}r^2\frac{dR}{dr}+\left[\lambda+\frac{a}{r}-\frac{l(l+1)}{r^2}\right]R=0,
$$
where $\lambda$ is an eigenvalue parameter, $a$ is a fixed constant, and $l$ is an integer coming from the eigenvalues of the (associated) Legendre equation. Of particular importance is the lowest energy solution with no angular momentum corresponding to $l=0$; the solution has the form $R(r)=Ce^{-\mu r}$ where $\mu$ is determined from the equation
$$
     \left[\frac{d^2}{dr^2}+\frac{2}{r}\frac{d}{dr}+\lambda+\frac{a}{r}\right]R=0 \\
         (\mu^2+\lambda)+\frac{1}{r}(-2\mu+a)=0,
$$
which gives a solution if $\mu=a/2$ and $\lambda=-\mu^2=-a^{2}/4$. The smallest eigenvalue is then $\lambda = -a^{2}/4$, with solution $R_1(r)=Ce^{-ar/2}$. The second solution of the equation with the same eigenvalue $\lambda$ is not square integrable with respect to weight function $r^2$. In fact, the second solution has an exponential growth, and is given by variation of parameters to be
$$
 R_2(r)=-\frac{e^{ar/2}}{r}+a\ln(r)e^{ar/2}-a^2e^{-ar/2}\int_{0}^{r}\ln(s)e^{as}ds
$$
Your equation: The functions $u_1(r)=rR_1(r)$, $u_2(r)=rR_2(r)$ are then solutions of
$$
          -\frac{d^2u}{dr^2}+\left(-\lambda-\frac{a}{r}+\frac{l(l+1)}{r^2}\right)u=0,\;\;\lambda = -a^2/4,\; l=0.
$$
This is very close to your equation, but there is no combination of the solutions $u_1$, $u_2$ that has the asymptotic behavior you are expecting, which makes me doubt your expected asymptotic behavior.
However, if $\lambda$ is positive instead, then the perturbation obtained by changing $d$ is integrable on $(0,\infty)$, which would make me think that you will have a nice regularity in $d$. $L^1$ perturbations are very tame.


TITLE: Is every direct product of (finite) cyclic groups abelian?
QUESTION [4 upvotes]: Long story short I'm halfway through a proof and have hit a step where I show that a group order $p^2$ is abelian. I did this by splitting into the $C_{p^2}$ case and the $C_p\times C_p$ case, the first being trivial as all cyclic groups are abelian. The second case I proved by using the definition of the direct product and showing it directly from the definition of the two $C_p$ groups.
However this feels odd. Something feels off - especially added to the fact that my proof seemingly holds for any two cyclic groups, implying the direct product of any two cyclic groups is abelian, and yet I can't find anything online talking about this. Is it just so trivial nobody mentions it? The only thing I consistently see brought up is that "every cyclic group is an abelian group" (trivial), and "every finitely generated abelian group is a direct product of cyclic groups", which is the converse of what I'm trying to show.

REPLY [2 votes]: If you look at the way the direct product is defined, in particular the group operation, it's pretty easy to see that the answer is yes.  For we have $(a,b)*(c,d)=(ac,bd)=(ca,db)=(c,d)*(a,b)$.
Thus every direct product of abelian groups is abelian.


TITLE: Chromatic Equivalence Requirements
QUESTION [0 upvotes]: I have searched and searched and am unable to find the answer that I am looking for. I am trying to determine the conditions required for two graphs to have the same chromatic polynomial.
On both Wikipedia and Wolfram MathWorld it states that two graphs are chromatically equivalent if they have the same chromatic polynomial. It then gives a few known chromatically equivalent graphs. But I don't believe this really answers my question as what I want to know is what conditions exist that make those graphs have the same chromatic polynomial. For example, must they have the same number of vertices, the same number of edges, etc.

REPLY [1 votes]: The book "Chromatic Polynomials and Chromaticity of Graphs" by F. M. Dong, Khee Meng Koh, and K. L. Teo has an entire chapter dedicated to results about chromatically equivalent graphs. See chapter 3, and particularly Theorem 3.2.1.
http://books.google.com/books?id=bvhpExuQcq8C&pg=PA55&dq=chromatically+equivalent+graphs&source=gbs_toc_r&cad=4#v=onepage&q=chromatically%20equivalent%20graphs&f=false


TITLE: Equation regarding Sylow subgroups of a group $G$ of order $pqr$.
QUESTION [2 upvotes]: I'm trying to prove the following result. I think I'm not understanding it correctly. Just to clarify, my knowledge extends to Sylow's theorem corollaries but I don't know about solvable groups.

Let $G$ be a group of order $pqr$, $p>q>r$. Prove that $|G| \geq 1 + n_p(p-1) + n_q(q-1) + n_r(r-1)$

Here's what I have thought.
What I understood is that equation tells me to prove that there are more elements of the group $G$ than elements that belong to any Sylow subgroup. Isn't this always valid? Which means that I'm looking at the case when the inequality is a strict one?. This confuses me. Anyways, in that case if I find an element of order, say $pq$, then that element will not be an element of any Sylow subgroup. So the equation will be valid with a strict inequality.
I know that in this group there is a normal group of order $p$ which means that $n_p = 1$. From this I can conclude that there is a normal subgroup of order $pq$. If I knew that $p \neq 1\mod{q}$ , then the subgroup would be a cyclic subgroup which means that I can find an element of order $pq$ and the equation will be valid. Bu there are no restrictions on either $p$ or $q$.
I would appreciate any hints. Sorry if it has been asked before.
Edit: Maybe the question could be rephrased as is there a cyclic subgroup of order bigger than $p$? If that's true then the problem is solved.

REPLY [3 votes]: Since all Sylow subgroups of $G$ are of prime order, the intersection of any two distinct Sylow subgroups is trivial. Hence there are $n_p (p − 1)$ elements of order $p$, $n_q (q − 1)$ elements of order $q$, $n_r(r − 1)$ elements of order $r$, and $1$ element of order $1$ in G. Therefore
the inequality follows.


TITLE: Motivation behind steps in proof of Hoeffding Inequality
QUESTION [3 upvotes]: The lemma that is proved for proving Hoeffding's inequality is:
If $a\leq X\leq b$ and $E[X]=0$, $E[e^{tX}] \leq e^{\frac{t^2(b-a)^2}{8}}$
Here's a link to the proof: http://www.stat.cmu.edu/~larry/=stat705/Lecture2.pdf
There's a particular step in the proof the motivation of which I don't understand. Equation (3) in the pdf is $$Ee^{tX} \leq \frac{-a}{b-a}e^{tb}+\frac{b}{b-a}e^{ta}=e^{g(u)}$$
where $u=t(b-a)$, $g(u)=-\gamma u+\log (1-\gamma+\gamma e^u)$ and $\gamma=\frac{-a}{b-a}$.
I can understand that somebody would try to get the inequality in the form $E[e^{tX}] \leq e^{g(u)}$, but I don't see why one would choose $u=t(b-a)$. Put another way, I don't think I would have tried the above step. Is there a motivation behind why someone would think of defining $u$ the above way and get the complicated expression of $g(u)$, and hope that this will lead to something useful?

REPLY [1 votes]: The definition $u:=t(b-a)$ naturally arises from the fact that $a\le X\le b$. $t$ is a reduced variable, independent of the interval length.
The unexpected form of $g(u)$ is a rewrite of $\log(\frac{-a}{b-a}e^{tb}+\frac{b}{b-a}e^{ta})=\log(e^{ta}(\frac{-a}{b-a}e^{t(b-a)}+\frac{b}{b-a}))$, with the intent to bound it from its Taylor's expansion.
The main "trick" in this derivation is the use of the convexity property. The rest is commonplace function approximation.


text:
\begin{document}
\maketitle

\begin{abstract}
This paper presents a new deep learning-based framework for robust nonlinear estimation and control using the concept of a \underline{N}eural \underline{C}ontraction \underline{M}etric (NCM). The NCM uses a deep long short-term memory recurrent neural network for a global approximation of an optimal contraction metric, the existence of which is a necessary and sufficient condition for exponential stability of nonlinear systems. The optimality stems from the fact that the contraction metrics sampled offline are the solutions of a convex optimization problem to minimize an upper bound of the steady-state Euclidean distance between perturbed and unperturbed system trajectories. We demonstrate how to exploit NCMs to design an online optimal estimator and controller for nonlinear systems with bounded disturbances utilizing their duality. The performance of our framework is illustrated through Lorenz oscillator state estimation and spacecraft optimal motion planning problems.
\end{abstract}
\begin{IEEEkeywords}
Machine learning, Observers for nonlinear systems, Optimal control.
\end{IEEEkeywords}

\section{Introduction}
\label{introduction}
\IEEEPARstart{P}{rovably} stable and optimal state estimation and control algorithms for a class of nonlinear dynamical systems with external disturbances are essential to develop autonomous robotic explorers operating remotely on land, in water, and in deep space. In these next generation missions, these robots are supposed to intelligently perform complex tasks with their limited computational resources, which are not necessarily powerful enough to run optimization algorithms in real-time.

Our main contribution is to introduce a Neural Contraction Metric (NCM), a global representation of optimal contraction metrics sampled offline by using a deep Long Short-Term Memory Recurrent Neural Network (LSTM-RNN) (see Fig.~\ref{ncmdrawing}), and thereby propose a new framework for provably stable and optimal online estimation and control of nonlinear systems with bounded disturbances, which only requires one function evaluation at each time step. A deep LSTM-RNN~\cite{doi:10.1162/neco.1997.9.8.1735,6638947} is a recurrent neural network with an improved memory structure proposed to circumvent gradient vanishing~\cite{279181} and is a universal approximator of continuous curves~\cite{FUNAHASHI1993801}. Contrary to previous works, the convex optimization-based sampling methodology in our framework allows us to obtain a large enough dataset of the optimal contraction metric without assuming any hypothesis function space. These sampled metrics, the existence of which is a necessary and sufficient condition for exponential convergence \cite{contraction}, can be approximated with arbitrary accuracy due to the high representational power of the deep LSTM-RNN.
We remark that this approach can be used with learned dynamics~\cite{8794351} as a nominal model is assumed to be given. Also, this is distinct from Lyapunov neural networks designed to estimate a largest safe region for deterministic systems \cite{spencer18lyapunovnn,NIPS2019_8587}: the NCM provides provably stable estimation and control policies, which have a duality in their differential dynamics and are optimal in terms of disturbance attenuation. The NCM construction is summarized as follows.

\begin{figure}
    \centering
    \setlength\belowcaptionskip{-0.6\baselineskip}
    \includegraphics[width=85mm]{ncmdrawing4.pdf}
    \caption{Illustration of the NCM: $M(x,t)$ denotes the optimal contraction metric; $x(t)$ and $x_d(t)$ denote perturbed and unperturbed system trajectories; $h_i$ and $c_i$ denote the hidden states of the deep LSTM-RNN, respectively.}
    \label{ncmdrawing}
\end{figure}
In the offline phase, we sample contraction metrics by solving an optimization problem with exponential stability constraints, the objective of which is to minimize an upper bound of the steady-state Euclidean distance between perturbed and unperturbed system trajectories. In this paper, we present a convex optimization problem equivalent to this problem, thereby exploiting the differential nature of contraction analysis that enables Linear Time-Varying (LTV) systems-type approaches to Lyapunov function construction. For the sake of practical use, the sampling methodology is reduced to a much simpler formulation than those of \cite{observer, mypaper, mypaperTAC} derived for It\^{o} stochastic nonlinear systems. These optimal contraction metrics are sampled using the computationally efficient numerical methods for convex programming~\cite{citeulike:163662,cvxpy,mosek} and then modeled by the deep LSTM-RNN as depicted in Fig.~\ref{ncmdrawing}. In the online phase, contraction metrics at each time instant are computed by the NCM to obtain the optimal feedback estimation and control gain or a bounded error tube for robust motion planning~\cite{chung2013phase,7989693}.

We illustrate how to design an optimal NCM-based estimator and controller for nonlinear systems with bounded disturbances, utilizing the estimation and control duality in differential dynamics analogous to the one of the Kalman filter and Linear Quadratic Regulator (LQR) in LTV systems. Their performance is demonstrated using Lorenz oscillator state estimation and spacecraft optimal motion planning problems.

\subsubsection*{Related Work}
Contraction analysis, as well as Lyapunov theory, is one of the most powerful tools in analyzing the stability of nonlinear systems~\cite{contraction}. It studies the differential (virtual) dynamics for the sake of incremental stability by means of a contraction metric, the existence of which leads to a necessary and sufficient characterization of exponential stability of nonlinear systems. Finding an optimal contraction metric for general nonlinear systems is, however, almost as difficult as finding an optimal Lyapunov function.

Several numerical methods have been developed for finding contraction metrics in a given hypothesis function space. A natural application of this concept is to represent their candidate as a linear combination of some basis functions~\cite{664157,JOHANSEN20001617,LyapunovRBF,1184414}. In ~\cite{AYLWARD20082163,ccm}, a tractable framework to construct contraction metrics for dynamics with polynomial vector fields is proposed by relaxing the stability conditions to the sum of squares conditions. Although it is ideal to use a larger number of basis functions seeking for a more optimal solution, the downside of this approach is that the problem size grows exponentially with the number of variables and basis functions \cite{sos_dissertation}.

We could thus alternatively rely on numerical schemes for sampling data points of a Lyapunov function without assuming any hypothesis function space. This includes the state-dependent Riccati equation method~\cite{sddre,CIMEN20083761} and it is proposed in~\cite{observer,mypaper,mypaperTAC} that this framework can be improved to obtain an optimal contraction metric, which minimizes an upper bound of the steady-state mean squared tracking error for nonlinear stochastic systems. However, solving a nonlinear system of equations or an optimization problem at each time instant is not suitable for systems with limited online computational capacity. The NCM addresses this issue by approximating the sampled solutions by the LSTM-RNN.

\section{Preliminaries}
\label{preliminaries}
We use the notation $\|x\|$ and $\|A\|$ for the Euclidean and induced 2-norm, and $A \succ 0$, $A \succeq 0$, $A \prec 0$, and $A \preceq 0$ for positive definite, positive semi-definite, negative definite, and negative semi-definite matrices, respectively. Also, $\sym(A) = A+A^T$ and $I$ denotes the identity matrix.
We first introduce some preliminaries that will be used to construct an NCM.

\subsection{Contraction Analysis for Incremental Stability}
Consider the following perturbed nonlinear system:
\begin{align}
    \label{nonlin_per}
    \dot{x}(t) = f(x(t),t)+d(t)
\end{align}
where $t\in \mathbb{R}_{\geq0}$, $x:\mathbb{R}_{\geq0} \to \mathbb{R}^{n}$, $f:\mathbb{R}^n\times\mathbb{R}_{\geq0} \to \mathbb{R}^{n}$, and $d:\mathbb{R}_{\geq0} \to \mathbb{R}^{n}$ with $\overline{d}=\sup_{t \geq 0}\|d(t)\| < +\infty$.
\begin{theorem}
\label{RobustCont}
Let $x_1(t)$ and $x_2(t)$ be the solution of (\ref{nonlin_per}) with $d(t) = 0$ and $d(t) \neq 0$, respectively. Suppose there exist $M(x,t) = \Theta (x,t)^T\Theta(x,t) \succ 0$, $\alpha > 0$, and $0 < \underline{\omega},\overline{\omega} < \infty$ \st{}
\begin{align}
\label{deterministic_contraction}
&\dot{M}(x,t)+\sym{\left(M(x,t)\frac{\partial f(x,t)}{\partial x}\right)} \preceq -2\alpha M(x,t),~\forall x,t \\
\label{Mcon}
& \left(\frac{1}{\overline{\omega}}\right)I \preceq M(x,t) \preceq \left(\frac{1}{\underline{\omega}}\right)I,~\forall x,t.
\end{align}
Then the smallest path integral is exponentially bounded, thereby yielding a bounded tube of states:
\begin{align}
    \label{dist_dist}
    \int^{x_2}_{x_1}\|\delta x\|-{R(0)}{\sqrt{\overline{\omega}}}e^{-\alpha t} \leq \frac{\overline{d}}{\alpha}\sqrt{\frac{\overline{\omega}}{\underline{\omega}}} \leq \frac{\overline{d}\overline{\omega}}{\alpha\underline{\omega}}
\end{align}
where $R(t) = \int_{x_1}^{x_2}\|\Theta(x,t) \delta x(t)\|, \forall t$.
\end{theorem}
\begin{IEEEproof}
Differentiating $R(t)$ yields $\dot{R}(t)+\alpha R(t) \leq \|\Theta(x(t),t)d(t)\|$ (see~\cite{contraction}). Since we have $\|\Theta(x(t),t)d(t)\| \leq \overline{d}/\sqrt{\underline{\omega}}$, applying the comparison lemma~\cite{Khalil:1173048} results in $R(t) \leq R(0)e^{-\alpha t}+\overline{d}/(\alpha\sqrt{\underline{\omega}})$. Rewriting this inequality using the relations $\sqrt{\overline{\omega}} R(t) \geq \int^{x_2}_{x_1}\|\delta x\|$ and  $1 \leq \sqrt{\overline{\omega}/\underline{\omega}} \leq \overline{\omega}/\underline{\omega}$ due to $0 < \underline{\omega} \leq \overline{\omega}$ completes the proof. Input-to-state stability and finite-gain $\mathcal{L}_p$ stability follow from (\ref{dist_dist}) (see~\cite{chung2013phase}).
\end{IEEEproof}

\subsection{Deep LSTM-RNN}
An LSTM-RNN is a neural network designed for processing sequential data with inputs $\{x_i\}_{i=0}^N$ and outputs $\{y_i\}_{i=0}^N$, and defined as $y_i = W_{hy}h_i+b_y$ where $h_i = \phi(x_i,h_{i-1},c_{i-1})$.
The activation function $\phi$ is given by the following relations: $h_{i} = o_{i}\tanh(c_{i})$, $o_{i} = \sigma(W_{xo}x_{i}+W_{ho}h_{i-1}+W_{co}c_{i}+b_o)$, $c_{i} = f_{i}c_{i-1}+\iota_{i}\tanh(W_{xc}x_{i}+W_{hc}h_{i-1}+b_c)$, $f_{i} = \sigma(W_{xf}x_{i}+W_{hf}h_{i-1}+W_{cf}c_{i-1}+b_f)$, and $\iota_{i} = \sigma(W_{xi}x_{i}+W_{hi}h_{i-1}+W_{ci}c_{i-1}+b_i)$, where $\sigma$ is the logistic sigmoid function and $W$ and $b$ terms represent weight matrices and bias vectors to be optimized, respectively. The deep LSTM-RNN can be constructed by stacking multiple of these layers~\cite{doi:10.1162/neco.1997.9.8.1735,6638947}.

Since contraction analysis for discrete-time systems leads to similar results~\cite{contraction,mypaperTAC}, we define the inputs $x_i$ as discretized states $\{x_i = x(t_i)\}_{t=0}^N$, and the outputs $y_i$ as non-zero components of the unique Cholesky decomposition of the optimal contraction metric, as will be discussed in Sec.~\ref{ncmsec}.

\section{Neural Contraction Metric (NCM)}
\label{ncmsec}

This section presents an algorithm to obtain an NCM depicted in Fig. \ref{ncmdrawing}.

\subsection{Convex Optimization-based Sampling of Contraction Metrics (CV-STEM)}
We derive one approach to sample contraction metrics by using the \underline{C}on\underline{V}ex optimization-based \underline{S}teady-state \underline{T}racking \underline{E}rror \underline{M}inimization (CV-STEM) method~\cite{mypaper,mypaperTAC}, which could handle the control design of It\^{o} stochastic nonlinear systems. In this section, we propose its simpler formulation for nonlinear systems with bounded disturbances in order to be of practical use in engineering applications.

By Theorem~\ref{RobustCont}, the problem to minimize an upper bound of the steady-state Euclidean distance between the trajectory $x_1(t)$ of the unperturbed system and $x_2(t)$ of the perturbed system (\ref{nonlin_per}) ((\ref{dist_dist}) as $t\to \infty$) can be formulated as follows:
\begin{align}
\label{nonlin_opt_ccm}
{J}_{NL}^* = \min_{\underline{\omega}>0,\overline{\omega}>0,W \succ 0} \frac{\overline{d}\overline{\omega}}{\alpha\underline{\omega}}\text{  \st{} }\text{(\ref{deterministic_contraction}) and (\ref{Mcon})}
\end{align}
where $W(x,t) = M(x,t)^{-1}$ is used as a decision variable instead of $M(x,t)$. We assume that the contraction rate $\alpha$ and disturbance bound $\overline{d}$ are given in (\ref{nonlin_opt_ccm}) (see Remark~\ref{howtochosealpha} on how to select $\alpha$).
We need the following lemma to convexify this nonlinear optimization problem.
\begin{lemma}
\label{equiv_constraints}
The inequalities (\ref{deterministic_contraction}) and (\ref{Mcon}) are equivalent to
\begin{align}
\label{deterministic_contraction_tilde}
&\dot{\tilde{W}}(x,t)-\sym{\left(\frac{\partial f(x,t)}{\partial x}\tilde{W}(x,t)\right)} \succeq 2\alpha \tilde{W}(x,t),~\forall x,t \\
\label{W_tilde}
&I \preceq \tilde{W}(x,t) \preceq \chi I,~\forall x,t
\end{align}
respectively, where $\chi = \overline{\omega}/\underline{\omega}$, $\tilde{W} = \nu W$, and $\nu = 1/\underline{\omega}$.
\end{lemma}
\begin{IEEEproof}
Since $\nu = 1/\underline{\omega} > 0$ and $W(x,t) \succ 0$, multiplying (\ref{deterministic_contraction}) by $\nu$ and then by $W(x,t)$ from both sides preserves matrix definiteness and the resultant inequalities are equivalent to the original ones~\cite[pp. 114]{lmi}. These operations yield (\ref{deterministic_contraction_tilde}). Next, since $M(x,t) \succ 0$, there exists a unique $\mu(x,t) \succ 0$ \st{} $M = \mu^2$. Multiplying (\ref{Mcon}) by $\mu^{-1}$ from both sides gives $\underline{\omega}I \preceq W(x,t) \preceq \overline{\omega}I$ as we have $\underline{\omega},\overline{\omega} > 0$ and $(\mu^{-1})^2 = W$. We get (\ref{W_tilde}) by multiplying this inequality by $\nu = 1/\underline{\omega}$.
\end{IEEEproof}
We are now ready to state and prove our main result on the convex optimization-based sampling.
\begin{theorem}
\label{conv_equiv_thm}
Consider the convex optimization problem:
\begin{align}
    \label{convex_opt_ccm}
    &{J}_{CV}^* = \min_{\chi \in \mathbb{R},\tilde{W}\succ 0} \frac{\overline{d}\chi}{\alpha} \text{~~\st{} (\ref{deterministic_contraction_tilde}) and (\ref{W_tilde})}
\end{align}
where $\chi$ and $\tilde{W}$ are defined in Lemma~\ref{equiv_constraints}, and $\alpha>0$ and $\overline{d}=\sup_{t \geq 0}\|d(t)\|$ are assumed to be given. Then ${J}_{NL}^*={J}_{CV}^*$.
\end{theorem}
\begin{IEEEproof}
By definition, we have ${\overline{d}\overline{\omega}}/{(\alpha\underline{\omega})}={\overline{d}\chi}/{\alpha}$.
Since (\ref{deterministic_contraction}) and (\ref{Mcon}) are equivalent to (\ref{deterministic_contraction_tilde}) and (\ref{W_tilde}) by Lemma~\ref{equiv_constraints}, rewriting the objective in the original problem (\ref{nonlin_opt_ccm}) using this equality completes the proof.
\end{IEEEproof}
\begin{remark}
\label{howtochosealpha}
Since (\ref{deterministic_contraction_tilde}) and (\ref{W_tilde}) are independent of $\nu=1/\underline{\omega}$, the choice of $\nu$ does not affect the optimal value of the minimization problem in Theorem~\ref{conv_equiv_thm}. In practice, as we have $\sup_{x,t}\|M(x,t)\|\leq1/\underline{\omega}=\nu$ by (\ref{Mcon}), it can be used as a penalty to optimally adjust the induced 2-norm of estimation and control gains when the problem explicitly depends on $\nu$ (see Sec.~\ref{example} for details). Also, although $\alpha$ is fixed in Theorem~\ref{conv_equiv_thm}, it can be found by a line search as will be demonstrated in Sec. \ref{simulation}.
\end{remark}
\begin{remark}
The problem (\ref{convex_opt_ccm}) can be solved as a finite-dimensional problem by using backward difference approximation, $\dot{\tilde{W}}(x(t_i),t_i) \simeq {({\tilde{W}}(x(t_i),t_i)-{\tilde{W}}(x(t_{i-1}),t_{i-1}))}/{\Delta t_i}$, where $\Delta t = t_i-t_{i-1}, \forall i$ with $\Delta t \gg \Delta t^2 > 0$, and by discretizing it along a pre-computed system trajectory $\{x(t_i)\}_{i=0}^N$.
\end{remark}

\subsection{Deep LSTM-RNN Training}
Instead of directly using sequential data of optimal contraction metrics $\{M(x(t_i),t_i)\}^{N}_{i=0}$ for neural network training, the positive definiteness of $M(x,t)$ is utilized to reduce the dimension of the target output $\{y_i\}_{i=0}^N$ defined in Sec. \ref{preliminaries}.
\begin{lemma}
\label{cholesky}
A matrix $A \succ 0$ has a unique Cholesky decomposition, \ie{}, there exists a unique upper triangular matrix $U\in\mathbb{R}^{n\times n}$ with strictly positive diagonal entries \st{} $A = U^TU$.
\end{lemma}
\begin{IEEEproof}
See~\cite[pp. 441]{10.5555/2422911}.
\end{IEEEproof}
As a result of Lemma~\ref{cholesky}, we can select $\Theta (x,t)$ defined in Theorem~\ref{RobustCont} as the unique Cholesky decomposition of $M(x,t)$ and train the deep LSTM-RNN using only the non-zero entries of the unique upper triangular matrices $\{\Theta(x(t_i),t_i)\}^{N}_{i=0}$. We denote these nonzero entries as $\theta (x,t) \in \mathbb{R}^{\frac{1}{2}n(n+1)}$.
As a result, the dimension of the target data $\theta (x,t)$ is reduced by $n(n-1)/2$ without losing any information on $M(x,t)$.

The pseudocode to obtain an NCM depicted in Fig. \ref{ncmdrawing} is presented in Algorithm~\ref{NCMalg}.
The deep LSTM-RNN in Sec. \ref{preliminaries} is trained with the sequential state data $\{x(t_i)\}_{i=0}^N$ and the target data $\{\theta (x(t_i),t_i)\}^{N}_{i=0}$ using Stochastic Gradient Descent (SGD). We note these pairs will be sampled for multiple trajectories to increase sample size and to avoid overfitting.
\begin{algorithm}
\SetKwInOut{Input}{Inputs}\SetKwInOut{Output}{Outputs}
\Input{Initial and terminal states $\{x_{s}(t_0),x_{s}(t_N)\}^{S}_{s=1}$}
\Output{NCM and steady-state bound $J_{CV}^*$ in  (\ref{convex_opt_ccm})}
\BlankLine
\textit{A. Sampling of Optimal Contraction Metrics} \\
\For{$s\leftarrow 1$ \KwTo $S$}{
Generate a trajectory $\{x_{s}(t_i)\}^{N}_{i=0}$ using $x_{s}(t_0)$ (could use $x_{s}(t_N)$ for  motion planning problems) \\
\For{$\alpha \in A_{\mathrm{linesearch}}$}{
Find $J_{CV}^*(\alpha,x_{s})$ and $\{\theta(x_{s}(t_i),t_i)\}^{N}_{i=0}$ by Th.~\ref{conv_equiv_thm}
}
Find $\alpha^*(x_{s}) = \text{arg}\min_{\alpha \in A_{\mathrm{linesearch}}}J_{CV}^*(\alpha,x_{s})$ \\
Save $\{\theta(x_{s}(t_i),t_i)\}^{N}_{i=0}$ for $\alpha = \alpha^*(x_{s})$
}
Obtain $J_{CV}^* = \max_{s}J_{CV}^*(\alpha^*(x_{s}),x_{s})$
\BlankLine
\textit{B. Deep LSTM-RNN Training} \\
Split data into a train set $\mathcal{S}_{\mathrm{train}}$ and test set $\mathcal{S}_{\mathrm{test}}$ \\
\For{$\mathrm{epoch} \leftarrow 1$ \KwTo $N_{\mathrm{epochs}}$}{
\For{$s \in \mathcal{S}_{\mathrm{train}}$}{Train the deep LSTM-RNN with $\{x_{s}(t_i)\}^{N}_{i=0}$, $\{\theta(x_{s}(t_i),t_i)\}^{N}_{i=0}$ using SGD}
Compute the test error for data in $\mathcal{S}_{\mathrm{test}}$ \\
\If{$\mathrm{test~error} < \epsilon$}{
\textbf{break}
}
}
\caption{NCM Algorithm}
\label{NCMalg}
\end{algorithm}

\section{NCM-Based Optimal Estimation and Control}
\label{example}
This section delineates how to construct an NCM offline and utilize it online for state estimation and feedback control.

\subsection{Problem Statement}
We apply an NCM to the state estimation problem for the following nonlinear system with bounded disturbances:
\begin{align}
    \label{orig_dynamics}
    \dot{x} = f(x,t)+B(x,t)d_1(t),~y(t) = h(x,t)+G(x,t)d_2(t)
\end{align}
where $d_1: \mathbb{R}_{\geq 0} \to \mathbb{R}^{k_1}$, $B:\mathbb{R}^n\times\mathbb{R}_{\geq 0} \to \mathbb{R}^{n\times k_1}$, $y: \mathbb{R}_{\geq 0} \to \mathbb{R}^m$, $d_2: \mathbb{R}_{\geq 0} \to \mathbb{R}^{k_2}$, $h:\mathbb{R}^n\times\mathbb{R}_{\geq 0} \to \mathbb{R}^{m}$, and $G:\mathbb{R}^n\times\mathbb{R}_{\geq 0} \to \mathbb{R}^{m\times k_2}$ with  $\overline{d}_1 = \sup_t\|d_1(t)\| < +\infty$ and $\overline{d}_2 = \sup_t\|d_2(t)\|  < +\infty$. Let $W = M(\hat{x},t)^{-1} \succ 0$, $A(x,t) = (\partial f/\partial x)$, and $C(x,t) = (\partial h/\partial x)$. We design an estimator as
\begin{align}
    \label{est_dynamics}
    &\dot{\hat{x}} = f(\hat{x},t)+M(\hat{x},t)C(\hat{x},t)^T(y-h(\hat{x},t))\\
    \label{ekf_con}
    &\dot{W}+W A(\hat{x},t)+A(\hat{x},t)^TW-2C(\hat{x},t)^TC(\hat{x},t) \preceq -2\alpha W
\end{align}
where $\alpha > 0$. The virtual system of (\ref{orig_dynamics}) and (\ref{est_dynamics})  is given as
\begin{align}
    \label{detvd}
    \dot{q} =& f(q,t)+M(\hat{x},t)C(\hat{x},t)^T(h(x,t)-h(q,t))+d_e(q,t)
\end{align}
where $d_e(q,t)$ is defined as $d_e(x,t) = B(x,t)d_1(t)$ and $d_e(\hat{x},t) = M(\hat{x},t)C(\hat{x},t)^TG(x,t)d_2(t)$. Note that (\ref{detvd}) has $q=x$ and $q=\hat{x}$ as its particular solutions. The differential dynamics of (\ref{detvd}) with $d_e = 0$ is given as
\begin{align}
    \label{detvd_dynamics}
    \delta \dot{q} =& (A(q,t)-M(\hat{x},t)C(\hat{x},t)^TC(q,t))\delta q.
\end{align}

\subsection{Nonlinear Stability Analysis}
We have the following lemma for deriving a condition to guarantee the local contraction of (\ref{detvd}) in Theorem~\ref{est_stability}.
\begin{lemma}
    \label{neighbor_lemma}
    If (\ref{ekf_con}) holds for $t\geq0$, there exists $r(t) > 0$ \st{}
    \begin{align}
    \label{ekf_virtual}
    2\gamma W+\dot{W}+\sym{}(W A(q,t))-\sym(C(\hat{x},t)^TC(q,t)) \preceq 0
    \end{align}
    for all $q(t)$ with $\|q(t)-\hat{x}(t)\| \leq r(t)$, where $0 < \gamma < \alpha$.
\end{lemma}
\begin{IEEEproof}
See~Lemma 2 of~\cite{6849943} or Theorem 1 of~\cite{observer}.
\end{IEEEproof}
The following theorem along with this lemma guarantees the exponential stability of the estimator (\ref{est_dynamics}).
\begin{theorem}
\label{est_stability}
Suppose that there exist positive constants $\underline{\omega}$, $\overline{\omega}$, $\overline{b}$, $\bar{c}$, $\bar{g}$, and $\rho$ \st{} $\underline{\omega}I \preceq W(\hat{x},t) \preceq \overline{\omega}I$, $\|B(x,t)\| \leq \overline{b}$, $\|C(\hat{x},t)\| \leq \bar{c}$, $\|G(x,t)\| \leq \bar{g}$, and $r(t) \geq \rho,~\forall \hat{x},x,t$, where $r(t)$ is defined in Lemma~\ref{neighbor_lemma}. If (\ref{ekf_con}) holds and $R_e(0)+\overline{D}_e/{\gamma} \leq \sqrt{\underline{\omega}} \rho$, where $R_e(t) = \int_{\hat{x}}^x\|\Theta(\hat{x},t)\delta q(t)\|$ with $W = \Theta^T \Theta$ and $\overline{D}_e = \overline{d}_1\overline{b}\sqrt{\overline{\omega}}+{\overline{d}_2\bar{c}\bar{g}}/{\sqrt{\underline{\omega}}}$, then the distance between the trajectory of (\ref{orig_dynamics}) and (\ref{est_dynamics}) is exponentially bounded as follows:
\begin{align}
    \label{est_ss}
    \int_{\hat{x}}^x\|\delta q\| \leq \frac{R_e(0)}{\sqrt{\underline{\omega}}}e^{-\gamma t}+ \frac{\overline{d}_1\overline{b}}{\gamma}\chi+\frac{{\overline{d}_2\bar{c}\bar{g}}}{\gamma}\nu
\end{align}
where $\chi = {\overline{\omega}}/{\underline{\omega}}$, $\nu = {1}/{\underline{\omega}}$, and $0 < \gamma < \alpha$.
\end{theorem}
\begin{IEEEproof}
Using (\ref{detvd_dynamics}), we have $d(\|\Theta \delta q\|^2)/dt = \delta q^T(\dot{W}+\sym(W A(q,t))-\sym(C(\hat{x},t)^TC(q,t)))\delta q$ when $d_e = 0$. This along with (\ref{ekf_virtual}) gives $\dot{R}_e(t) \leq -{\gamma} R_e(t)$ in the region where Lemma~\ref{neighbor_lemma} holds. Thus, using the bound $\|\Theta(\hat{x}(t),t)d_e(q,t)\| \leq \overline{D}_e$, we have $\sqrt{\underline{\omega}}\int_{\hat{x}}^{x}\|\delta q\| \leq {R_e(0)}e^{-\gamma t}+{\overline{D}_e}/\gamma$ by the same proof as for Theorem~\ref{RobustCont}. Rewriting this with $\chi$, $\nu$, and $1 \leq \sqrt{\chi} \leq \chi$ yields (\ref{est_ss}). This also implies that $\sqrt{\underline{\omega}}\|x-\hat{x}\| \leq R_e(0)+\overline{D}_e/{\gamma},~\forall t$. Hence, the sufficient condition for $\|q-\hat{x}\|$ in Lemma~\ref{neighbor_lemma} reduces to the one required in this theorem.
\end{IEEEproof}

\subsection{Convex Optimization-based Sampling (CV-STEM)}
We have the following proposition to sample optimal contraction metrics for the NCM-based state estimation.
\begin{proposition}
\label{est_prop}
$M(\hat{x},t)$ that minimizes an upper bound of $\lim_{t\to\infty} \int_{\hat{x}}^x\|\delta q\|$ is found by the convex optimization problem:
\begin{align}
    \label{convex_opt_estimator}
    &{J}_{CVe}^* = \min_{\nu>0,\chi \in \mathbb{R},\tilde{W} \succ 0} \frac{\overline{d}_1\overline{b}}{\gamma}\chi+\frac{{\overline{d}_2\bar{c}\bar{g}}}{\gamma}\nu\\
    &\text{\st{}}\text{  $\dot{\tilde{W}}+\tilde{W}A+A^T\tilde{W}-2\nu C^TC \preceq -{2\alpha} \tilde{W}$ and $I \preceq \tilde{W} \preceq \chi I$} \nonumber
\end{align}
where $\chi = {\overline{\omega}}/{\underline{\omega}}$, $\nu = {1}/{\underline{\omega}}$, $\tilde{W} = \nu W$, and $0 < \gamma < \alpha$. The arguments of $A(\hat{x},t)$, $C(\hat{x},t)$, and $\tilde{W}(\hat{x},t)$ are omitted for notational simplicity.
\end{proposition}
\begin{IEEEproof}
Multiplying (\ref{ekf_con}) and $\underline{\omega}I \preceq W(\hat{x},t) \preceq \overline{\omega}I,~\forall \hat{x},t$ by $\nu$ yields the constraints of (\ref{convex_opt_estimator}). Then Theorem~\ref{conv_equiv_thm} with the objective function given in (\ref{est_ss}) of Theorem~\ref{est_stability} as $t \to \infty$ yields (\ref{convex_opt_estimator}).
\end{IEEEproof}

We have an analogous result for state feedback control.
\begin{corollary}
\label{con_cor}
Consider the following system and a state feedback controller $u(t)$ with the bounded disturbance $d(t)$:
\begin{align}
    \label{control_dynamics}
    &\dot{x} = f(x,t)+B_1(x,t)u+B_2(x,t)d(t) \\
    \label{con_riccati}
    &\dot{W}-A(x,t)W-W A(x,t)^T+2B_1(x,t)B_1(x,t)^T \succeq 2\alpha W
\end{align}
where $u = -B_1(x,t)^TM(x,t)x$, $B_1:\mathbb{R}^n\times\mathbb{R}_{\geq0}\to\mathbb{R}^{n\times m}$, $B_2:\mathbb{R}^n\times\mathbb{R}_{\geq0}\to\mathbb{R}^{n\times k}$, $W=M^{-1}\succ 0$, $\alpha>0$, and $A$ is a matrix defined as $A(x,t)x = f(x,t)$, assuming that $f(x,t) = 0$ at $x = 0$ \cite{sddre,CIMEN20083761}. Suppose there exist positive constants $\underline{\omega}$, $\overline{\omega}$, and $\overline{b}_2$ \st{} $\underline{\omega}I \preceq W(x,t) \preceq \overline{\omega}I$ and $\|B_2(x,t)\| \leq \overline{b}_2,~\forall x,t$.
Then $M(x,t)$ that minimizes an upper bound of $\lim_{t\to\infty} \int_{0}^x\|\delta q\|$ can be found by the following convex optimization problem:
\begin{align}
    \label{convex_opt_controller}
    &{J}_{CVc}^* = \min_{\nu > 0,\chi \in \mathbb{R},\tilde{W} \succ 0} \frac{\overline{b}_2\overline{d}}{\alpha}\chi+\lambda\nu\\
    &\text{\st{}}\text{  $-\dot{\tilde{W}}+A\tilde{W}+\tilde{W}A^T-2\nu B_1B_1^T \preceq -{2\alpha}\tilde{W}$ and $I \preceq \tilde{W} \preceq \chi I$} \nonumber
\end{align}
where $\chi = {\overline{\omega}}/{\underline{\omega}}$, $\nu = {1}/{\underline{\omega}}$, $\tilde{W} = \nu W$, and $\lambda>0$ is a user-defined constant. The arguments of $A(x,t)$, $B_1(x,t)$, and $\tilde{W}(x,t)$ are omitted for notational simplicity.
\end{corollary}
\begin{IEEEproof}
The system with $q=x,0$ as its particular solutions is given by $\dot{q} = (A(x,t)-B_1(x,t)B_1(x,t)^TM(x,t))q+d_c(q,t)$, where $d_c(x,t) = B_2(x,t)d(t)$ and $d_c(0,t) = 0$. Since we have $\|d_c(q,t)\| \leq \overline{b}_2\overline{d}$ and the differential dynamics is
\begin{align}
\label{differential_con}
    \delta \dot{q} = (A(x,t)-B_1(x,t)B_1(x,t)^TM(x,t))\delta q
\end{align}
when $d_c = 0$, we get $\lim_{t\to \infty}\int_{0}^x\|\delta q\| \leq \overline{b}_2\overline{d}\chi/\alpha$ by the same proof as for Theorem~\ref{est_stability} with (\ref{detvd_dynamics}) replaced by (\ref{differential_con}), (\ref{ekf_virtual}) by (\ref{con_riccati}), and $R_e(t)$ by $R_c(t)=\int_{0}^x\|\Theta(x,t )\delta q(t)\|$, where $M = \Theta^T\Theta$. (\ref{convex_opt_controller}) then follows as in the proof of Proposition~\ref{est_prop}, where $\lambda \geq 0$ is for penalizing excessively large control inputs through $\nu \geq \sup_{x,t}\|M(x,t)\|$ (see Remark~\ref{howtochosealpha}).
\end{IEEEproof}

\subsection{NCM Construction and Interpretation} Algorithm~\ref{NCMalg} along with Proposition~\ref{est_prop} and Corollary~\ref{con_cor} returns NCMs to compute $\hat{x}(t)$ of (\ref{est_dynamics}) and $u(t)$ of (\ref{control_dynamics}) for state estimation and control in real-time. They also provide the bounded error tube (see Theorem~\ref{RobustCont}, \cite{chung2013phase,7989693}) for robust motion planning problems as will be seen in Sec.~\ref{simulation}.

The similarity of Corollary~\ref{con_cor} to Proposition~\ref{est_prop} stems from the estimation and control duality due to the differential nature of contraction analysis as is evident from (\ref{detvd_dynamics}) and (\ref{differential_con}). Analogously to the discussion of the Kalman filter and LQR duality in LTV systems, this leads to two different interpretations on the weight of $\nu$ ($\overline{d}_2\bar{c}\bar{g}/\gamma$ in (\ref{convex_opt_estimator}) and $\lambda$ in (\ref{convex_opt_controller})). As discussed in Remark~\ref{howtochosealpha}, one way is to see it as a penalty on the induced 2-norm of feedback gains. Since $\overline{d}_2=0$ in (\ref{convex_opt_estimator}) means no noise acts on $y(t)$, it can also be viewed as an indicator of how much we trust the measurement $y(t)$: the larger the weight of $\nu$, the less confident we are in $y(t)$. These agree with our intuition as smaller feedback gains are suitable for systems with larger measurement uncertainty.

\section{Simulation}
\label{simulation}

\renewcommand\UrlFont{\rm}
The NCM framework is demonstrated using Lorentz oscillator state estimation and spacecraft motion planning and control problems. CVXPY~\cite{cvxpy} with the MOSEK solver~\cite{mosek} is used to solve convex optimization problems. A Python implementation is available at {\color{caltechgreen}\underline{\url{https://github.com/astrohiro/ncm}}}.

\subsection{State Estimation of Lorenz Oscillator}
We first consider state estimation of the Lorentz oscillator with bounded disturbances described as $\dot{x}=f(x)+d_1(t)$ and $y = Cx+d_2(t)$, where $f(x) =[\sigma(x_2-x_1),x_1(\rho-x_3)-x_2,x_1 x_2-\beta x_3]^T$, $x = [x_1,x_2,x_3]^T$, $\sigma = 10$, $\beta = 8/3$, $\rho = 28$, $C = [1~0~0]$, $\sup_t\|d_1(t)\| = \sqrt{3}$, and $\sup_t\|d_2(t)\| = 1$. We use $dt = 0.1$ for integration, with one measurement $y$ per $dt$.

\subsubsection{Sampling of Optimal Contraction Metrics}
Using Proposition~\ref{est_prop}, we sample the optimal contraction metric along $100$ trajectories with uniformly distributed initial conditions ($-10 \leq x_i \leq 10,~i = 1,2,3$). Figure~\ref{lorenz_micro} plots ${J}_{CVe}^*$ in (\ref{convex_opt_estimator}) for $100$ different trajectories and the optimal $\alpha$ is found to be $\alpha = 3.4970$. The optimal estimator parameters averaged over $100$ trajectories for $\alpha = 3.4970$ are summarized in Table~\ref{lorenz_optvals}.
\begin{figure}
    \centering
    \includegraphics[width=70mm]{lorenz_micro.pdf}
    \caption{Upper bound of steady-state errors as a function of $\alpha$: each curve with a different color corresponds to a trajectory with a different initial condition.}
    \label{lorenz_micro}
\end{figure}
\begin{table}
\caption{NCM Estimator Parameters for $\alpha = 3.4970$ with ${J}_{CVe}^*$ and MSE Averaged over $100$ Trajectories}
\label{lorenz_optvals}
\centering

\begin{tabular}{|c|c|c|c|c|}
 \hline
 parameters & $\nu$ & $\chi$ & ${J}_{CVe}^*$ & MSE \\
 \hline
 values & $1.3375 \times 10^2$ & $9.2977$ & $42.852$ & $1.0190 \times 10^{-3}$ \rule[0mm]{0mm}{2.7mm}\\
 \hline
\end{tabular}
\end{table}

\subsubsection{Deep LSTM-RNN Training}
A deep LSTM-RNN is trained using Algorithm~\ref{NCMalg} and Proposition~\ref{est_prop} with the sequential data $\{\{(x_{s}(t_i),\theta_{s}(x(t_i))\}_{i=0}^N\}_{s=1}^S$ sampled over the $100$ different trajectories ($S = 100$). Note that $\theta_{s}(x(t_i))$ are standardized and normalized to make the SGD-based learning process stable. Figure~\ref{model_selection} shows the test loss of the LSTM-RNN models with different number of layers and hidden units. We can see that the models with more than $2$ layers overfit and those with less than $32$ hidden units underfit to the training samples. Thus, the number of layers and hidden units are selected as $2$ and $64$, respectively. The resultant MSE of the trained LSTM-RNN is shown in Table~\ref{lorenz_optvals}.
\begin{figure}
    \centering
    \includegraphics[width=87mm]{rnn_errors_for_cdc.pdf}
    \caption{LSTM-RNN test loss with 2 layers (left) and 32 hidden units (right).}
    \label{model_selection}
\end{figure}

\subsubsection{State Estimation with an NCM}
The estimation problem is solved using the NCM, sampling-based CV-STEM~\cite{mypaper,mypaperTAC}, and Extended Kalman Filter (EKF) with $\sup_t\|d_1(t)\| = 20\sqrt{3}$, and $\sup_t\|d_2(t)\| = 20$. We use $x(0) = [-1.0,2.0,3.0]^T$ and $\hat{x}(0) = [150.1,-1.5,-6]^T$ for the actual and estimated initial conditions, respectively. The EKF weight matrices are selected as $R = 20I$ and $Q = 10I$.

Figure~\ref{lorenz_plot} shows the smoothed estimation error $\|x(t)-\hat{x}(t)\|$ using a $15$-point moving average filter. The errors of the NCM and CV-STEM estimators are below the optimal upper bound while the EKF has a larger error compared to the other two.
As expected from the small MSE of Table~\ref{lorenz_optvals}, the estimation error of the NCM estimator shows a trend similar to that of the sampling-based CV-STEM estimator without losing its estimation performance.
\begin{figure}
    \centering

    \includegraphics[width=70mm]{lorenz.pdf}
    \caption{Lorentz oscillator state estimation error smoothed using a $15$-point moving average filter.}
    \label{lorenz_plot}
\end{figure}

\subsection{Spacecraft Optimal Motion Planning}
We consider an optimal motion planning problem of the planar spacecraft dynamical system, given as $\dot{x} = Ax+B(x)u+d(t)$, where $u \in \mathbb{R}^8$, $\sup_t\|d(t)\| = 0.15$, and $x = [p_x,p_y,\phi,\dot{p}_x,\dot{p}_y,\dot{\phi}]^T$ with $p_x$, $p_y$, and $\phi$ being the horizontal coordinate, vertical coordinate, and yaw angle of the spacecraft, respectively. The constant matrix $A$ and the state-dependent actuation matrix $B(x)$ are defined in \cite{SCsimulator}. All the parameters of the spacecraft are normalized to $1$.

\subsubsection{Problem Formulation}
In the planar field, we have $6$ circular obstacles with radius $3$ located at $(p_x,p_y) = (0,11)$, $(5,3)$, $(8,11)$, $(13,3)$, $(16,11)$, and $(21,3)$. The goal of the motion planning problem is to find an optimal trajectory that avoids these obstacles and minimize $\int_0^{50}\|u(t)\|^2dt$ subject to input constraints $0 \leq u_i(t) \leq 1,\forall i,\forall t$ and the dynamics constraints. The initial and terminal condition are selected as $x(0) =[0,0,\pi/12,0,0,0]^T$ and $x(t_N) =[20,18,0,0,0,0]^T$. Following the same procedure described in the state estimation problem, the optimal control parameters and the MSE of the LSTM-RNN trained using Algorithm~\ref{NCMalg} with Corollary~\ref{con_cor} are determined as shown in Table~\ref{sc_optvals}.
\begin{table}
\caption{NCM Control Parameters for $\alpha = 0.58$ with ${J}_{CVc}^*$ and MSE Averaged over $100$ Trajectories}
\label{sc_optvals}
\centering
\begin{tabular}{|c|c|c|c|c|}
 \hline
 parameters & $\nu$ & $\chi$ & ${J}_{CVc}^*$ & MSE \\
 \hline
 values & $6.2090 \times 10^2$ & $3.0116$ & $8.9524$ & $3.4675\times 10^{-4}$ \rule[0mm]{0mm}{2.7mm}\\
 \hline
\end{tabular}
\end{table}

\subsubsection{Motion Planning with an NCM}
Given an NCM, we can solve a robust motion planning problem, where the state constraint is now described by the bounded error tube (see Theorem~\ref{RobustCont}) with radius $R_\mathrm{tube} = \overline{d}(\sqrt{\chi}/\alpha) = 0.4488$. Figure~\ref{robust_SC} shows the spacecraft motion $(p_x,p_y)$ on a planar field, computed using the NCM, sampling-based CV-STEM~\cite{mypaper,mypaperTAC}, and baseline LQR control with $Q = 2.4I$ and $R = I$ which does not account for the disturbance.
\begin{figure}
    \centering

    \includegraphics[width=70mm]{SC_motion_planning.pdf}
    \caption{Spacecraft motion $(p_x,p_y)$ on a planar field.}
    \label{robust_SC}
\end{figure}
As summarized in Table~\ref{con_eff}, input constraints $0 \leq u_i(t) \leq 1,\forall i, \forall t$ are satisfied and the three controllers use a similar amount of control effort.
All the controllers except the LQR keep their trajectories within the tube avoiding collision with the circular obstacles, even under the presence of disturbances as depicted in Fig.~\ref{robust_SC}. Also, the NCM controller predicts the computationally-expensive CV-STEM controller with the small MSE as given in the last column of Table \ref{sc_optvals}.
\begin{table}
\caption{Control Performances for Spacecraft Motion Planning Problem}
\label{con_eff}
\centering

\begin{tabular}{|c|c|c|c|}
 \hline
  & $\int_0^{50}\|u(t)\|^2dt$ & $\min_i(\inf_t u_i(t))$ & $\max_i(\sup_t u_i(t))$  \\
 \hline
 NCM & $4.8959 \times 10$ & $-1.2728 \times 10^{-8}$ & $1.0000$ \rule[0mm]{0mm}{2.7mm}\\
 \hline
 CV-STEM & $4.8019 \times 10$ & $-4.1575 \times 10^{-8}$ & $1.0000$ \rule[0mm]{0mm}{2.7mm}\\
 \hline
 LQR & $4.9260 \times 10$ & $0.0000$ & $1.0000$ \rule[0mm]{0mm}{2.7mm}\\
 \hline
\end{tabular}
\end{table}

\section{Conclusion}
\label{conclusion}
In this paper, we present a Neural Contraction Metric (NCM), a deep learning-based  global approximation of an optimal contraction metric for online nonlinear estimation and control.
The novelty of the NCM approach lies in that: 1) data points of the optimal contraction metric are sampled offline by solving a convex optimization problem, which minimizes an upper bound of the steady-state Euclidean distance between the perturbed and unperturbed trajectories without assuming any hypothesis function space, and 2) the deep LSTM-RNN is constructed to model the sampled metrics with arbitrary accuracy. The superiority of its performance is validated through numerical simulations on state estimation and optimal motion planning problems.
\bibliographystyle{IEEEtran}
\bibliography{ms}

\end{document}

config: arxiv


TITLE: Equally distributing cards on a table. (interpolation)
QUESTION [1 upvotes]: this problem is originally from a programming task I am on.
there is a number of playing cards n. the width of each card is w.
now the cards should be placed next to each other on a table with equal space.
the table's width is also limited, let's call this t. so t is the available width that should be used by the cards.
now I am looking for a spacing-distance that should be put between each card depending on the above variables. cards can overlap.
so far i simply tried to interpolate depending on the number of cards, but it doesn't work out very well. i think i am missing to take the card width into account, but i don't know how.

REPLY [4 votes]: Let the distance between the centers of adjacent cards be $x$. Then $(n-1)x+w=t$, so $x=(t-w)/(n-1)$. That tells you how far apart to put (the centers of) adjacent cards.


text:
\section{Numerical Experiments}
We present four numerical experiments.
 In Sec.~\ref{convergence_study}, we verify the order of the convergence of the proposed scheme (\ref{elastic_semi_c}, \ref{fine_scheme}, \ref{continuous_sol}, \ref{continuous_traction}).  In  Sec.~\ref{iterative_section}, we present three iterative methods for solving the linear systems (\ref{traction_gamma_pre}) and (\ref{traction_gamma_corr}). The efficiency of the iterative methods is investigated and a comparison with the LU-factorization method is conducted. Next, in Sec.~\ref{gaussian_source} we show that our schemes generate little reflection at the mesh refinement interface. Finally, the energy conservation property is verified in Sec.~\ref{conserved_energy} with heterogeneous and discontinuous material properties.


TITLE: How do I show a minimal left ideal of a finite dimensional simple algebra exists? What can you say about its endomorphism ring?
QUESTION [0 upvotes]: How do I approach this ?

Let $k$ be an algebraically closed field and $R$ a $k$-algebra which is also a finite dimensional vector space over $k$. Suppose $R$ has no two-sided ideals other than $0$ and $R$. Show that $R$ has a simple left ideal $I$. What can you say about the ring $\mathrm{End}_R(I)$? Justify your answer.   6 Marks

Original image
Also What does simple left ideal mean here ?

REPLY [0 votes]: A simple left ideal is one which, considered as a left $R$ module, is simple (i.e. there are exactly two submodules: the zero submodule and the submodule itself.)
Every left ideal is patently a subspace of the finite dimensional space $R$. From all dimensions of nonzero left ideals there is necessarily one of minimal dimensionality, and that is clearly a simple left ideal.
The fact that the endomorphism ring of a simple module is a division ring is known as Schur's Lemma, and it is so well-known nobody asks for proofs of it here.  Nevertheless, you can find one here. You can say even more about it, also on the same wiki page.


TITLE: Arnold on proof of uniqueness
QUESTION [1 upvotes]: In his proof of Uniqueness, Arnold mentions the integral approaches infinity as x3 approaches x2. How does he come about this conclusion?

REPLY [1 votes]: Assuming we know that $x_1 \lt x_3 \lt x_2$, then
$$\int_{x_1}^{x_3} \frac{d \xi}{k(\xi - x_2)}= \frac 1k \ln \frac{x_3-x_2}{x_1-x_2}.$$
If $x_3 \to x_2$, then the argument of the logarithm approaches $0$.


TITLE: What are some mathematically productive ways to waste time?
QUESTION [21 upvotes]: What are some productive things that can be done (other than directly studying Mathematics) during leisure time that has a side effect to improve oneself at Mathematics? For example, reading Mathematics Stack Exchange.
Inspired by What to do while compiling?

REPLY [3 votes]: Try to do putnam competition tests. You don't really learn a lot of theory but it's a good exercise in coming up with proofs.


TITLE: Set builder notation, left or right of :| convention
QUESTION [18 upvotes]: Set builder notation which specify a subset such as $Z$ or $R$ tend to put this condition on the left, whereas other conditions go on the right.
$$\{ x ∈ Z : x > 0 \}$$
Why is this preferred over, say:
$$\{ x : x > 0  \textrm{ and } x ∈ Z\}$$
I notice that if the left-side has more than a simple term it tends not to have the contains expression. For example:
$$\{ x + 1 : x > 0 \}$$
In such a form could a $Z$ appear on the left, or must it appear on the right if it needs to be specified?
In what situations can the conditions go on the left, as opposed to the right of the $:$ operator?

REPLY [2 votes]: When you use set builder notation, use
$$\{x\in \hbox{Universe of discourse or subset threof }| {\rm TestForMembership}(x)\}.$$
The stuff to the left of the $|$ bounds the discussion and establishes context.


TITLE: Bounding $\sum_{p\leq x} \chi(p )$ for non-principal character $\chi$
QUESTION [6 upvotes]: Suppose $\chi$ is a non-principal Dirichlet character mod $k$. Let $A(x)=\sum_{n\leq x} \chi(n)$. Since $\sum_{n\leq k} \chi(n)=0$, we easily get the bound $|A(x)|\leq \varphi(k)$ where $\varphi$ is the Euler totient function.
Now let's define $B(x)=\sum_{p\leq x} \chi(p )$ where the sum extends over primes $p\leq x$. What kind of upper bounds do we have on $|B(x)|$? I am looking for any kind of big Oh estimates.
I appreciate any help!

REPLY [5 votes]: It is known that for $x$ large and if $\chi$ is primitive with modulo $k > 2$, then
$$B(x) \ll k^{1/2} x (\log x)^{-A}$$
for any $A > 0$. The implied constant, which is ineffective, depends only on $A$.
Ref H. Iwaniec and E. Kowalski, Analytic Number Theory, AMS 53, 2004, page 124.


text:
\begin{document}
\title{Heat flow on time-dependent manifolds}
\author{Beomjun Choi, Jianhui Gao, Robert Haslhofer, Daniel Sigal}

\begin{abstract} We establish effective existence and uniqueness for the heat flow on time-dependent Riemannian manifolds, under minimal assumptions tailored towards the study of Ricci flow through singularities. The main point is that our estimates only depend on an upper bound for the logarithmic derivative of the volume measure. In particular, our estimates hold for any Ricci flow with scalar curvature bounded below, and such a lower bound of course depends only on the initial data. \end{abstract}
\maketitle

\section{Introduction}

Heat flow plays a central role in analysis, geometry and probability. The theory is of course very classical if the underlying space is Euclidean space $\mathbb{R}^n$ or a closed Riemannian manifold $(M,g)$, but things become much more involved once the space becomes more complicated.\\

In a highly influential paper \cite{AGS1}, Ambrosio-Gigli-Savare developed a deep theory of heat flow in the general setting of metric measure spaces $(M,d,m)$. This is on the one hand of great interest in itself, and on the other hand also provides a fundamental tool for the study of metric measure spaces with Ricci curvature bounded below, see e.g. \cite{AGS2,AGS3,EKS,DePhilippisGigli,MondinoNaber,BrueSemola}. Related to this, there is the abstract theory of Dirichlet-forms, see e.g. \cite{Fukushima}, which also allows to establish existence of heat flow in very general situations, including in particular certain fractals and infinite dimensional spaces.\\

Another much desired generalization is one to the setting of time-dependent spaces. Generally speaking, this is because for many processes the diffusion does not take place on a static space, but rather on a space that itself evolves in time. In terms of applications to geometry, a primary motivation comes from Hamilton's Ricci flow \cite{Ham82,Ham_survey}. There are three recent proposals for a notion of Ricci flow through singularities introduced by Kleiner-Lott \cite{KL1}, Haslhofer-Naber \cite{HaslhoferNaber} and Sturm \cite{Sturm_superRicci}, and a general enough theory of heat flow on time-dependent spaces would be fundamental for the analysis of such Ricci flows through singularities.\\

In an important recent paper \cite{KopferSturm}, Kopfer-Sturm established existence, uniqueness and regularity of heat flow on certain time-dependent metric measure spaces $(M,d_t,m_t)$. Their approach is based on the theory of time-dependent Dirichlet-forms. This is on the one hand very general in the sense that it allows for highly singular spaces, but on the other hand also very restrictive in terms of how the spaces are actually allowed to change in time. Namely, the authors assume throughout their whole paper that their time-dependent metric measure spaces satisfy
\begin{equation}\label{ass_metric}
\left| \log \frac{d_{t_2}(x,y)}{d_{t_1}(x,y)}\right| \leq C_1|t_2-t_1| \qquad\qquad \textrm{(assumption on metrics in \cite{KopferSturm})}
\end{equation}
and
\begin{equation}\label{ass_measure}
\left| \log \frac{dm_{t_2}}{dm_{t_1}}\right| \leq C_2|t_2-t_1| \qquad\qquad \textrm{(assumption on measures in \cite{KopferSturm}).}
\end{equation}
In particular, for a smooth Riemannian manifold evolving by Ricci flow assumption \eqref{ass_metric} is equivalent to the assumption that the Ricci curvature is bounded. It is known since the work of Sesum \cite{Sesum}, that the Ricci curvature always blows up at singularities. Hence, unfortunately the assumption \eqref{ass_metric} is so restrictive that it cannot describe the flow through \emph{any} singularity.\\

Motivated by the above, we investigate the problem of existence and uniqueness for the heat flow on time-dependent spaces, under minimal assumptions tailored towards the study of Ricci flow through singularities. In the present paper, to capture the main ideas in the simplest possible setting, we focus on smooth one-parameter families of closed Riemannian manifolds. We will address the problem in the more general metric measure space setting in subsequent papers.\\

Let $(M,g_t)_{t\in [0,T]}$ be a smooth one-parameter family of closed Riemannian manifolds. Consider the linear heat equation on our evolving family of Riemannian manifolds,
\begin{equation}\label{heat_eq_evol}
\partial_t u=\Delta_{g_t} u.
\end{equation}
By smoothness and compactness, it is of course well-known that given any reasonable initial condition, say $u|_{t=0}=u_0\in L^2(M,g_0)$, there exists a unique solution. This can be shown in many different ways, e.g. via Galerkin approximation, time-discretization, elliptic regularization, or the theory of time-dependent Dirichlet-forms. However, all the existence proofs in the literature depend on several bounds for $(M,g_t)_{t\in [0,T]}$. The best result seems to be the one from \cite{KopferSturm}, which depends on a two-sided bound for the time-derivative of the Riemannian metrics $g_t$ and a two-sided bound for the logarithmic derivative of the volume measure $dm_t=d\textrm{vol}_{g_t}$. Some other proofs even depend on a bound for the full Riemann tensor and a lower bound for the injectivity radius.\\

In this paper, we give an effective proof that only depends on an upper bound for the logarithmic derivative of the volume measure, namely our estimates only depend on the constant $C_0<\infty$ in
\begin{equation}\label{assumption}
dm_{t_2}\leq e^{C_0(t_2-t_1)}dm_{t_1}\qquad \textrm{for } t_2\geq t_1.
\end{equation}
The meaning of \eqref{assumption} is that volume does not increase too much going forward in time. This is of course a perfectly natural assumption in the context of Ricci flow. Indeed, under Ricci flow the volume measure evolves by $\partial_t dm_t = -R dm_t$, where $R$ is the scalar curvature. Hence, one gets \eqref{assumption} provided $R\geq -C_0$, and indeed such a lower bound for the scalar curvature only depends on the initial data, since its minimum is nondecreasing by the evolution equation $\partial_t R = \Lap R + 2|\textrm{Rc}|^2$.\\

We use the implicit Euler scheme. However, due to the time-dependent metrics we have to be more careful how we fill in the intermediate times. Let $h=T/N$ be the time step. Given the initial condition $u_0$, we recursively define $u_k$ as the unique minimizer of the convex functional
\begin{equation}
u\mapsto \int_{M}\left(\abs{\nabla u}^2_{g_{kh}}+\frac{1}{h}(u- u_{k-1})^2\right)dm_{kh}.
\end{equation}

\bigskip

Usually in the literature one defines $u^h(t)$ at intermediate times via DeGiorgi interpolation \cite{DeGiorgi,AGS_book}. Specifically, one sets $u^h(kh)=u_k$, and then for $t=(k-1)h+\delta$, where $\delta\in(0,h)$, lets $u^h(t)$ be the unique minimizer of the functional
\begin{equation}
u\mapsto \int_{M}\left(\abs{\nabla u}^2_{g_t}+\frac{1}{\delta}\left(u- u_{k-1}\right)^2\right)dm_t.
\end{equation}
However, in our time-dependent setting this would not yield any proper $L^2H^{1}$-control. This is because $\abs{\nabla u}^2_{g_t}=g_t^{ij}\partial_i u \partial_j u$ depends on $g_t$, and the metrics at different times could be very different.\\

To get around this issue, we instead fill in the intermediate times using always steps of size $h$. To this end, we first extend the metric and initial condition to negative times by setting $g_t=g_0$ and $u^h(t) = u_0$ for $t<0$. We then define $u^h(t)$ recursively in time as unique minimizer of the convex functional
\begin{equation}
u\mapsto \int_{M}\left({\vert \nabla u\vert}^2_{g_t}+\frac{1}{h}(u- u^{h}(t-h))^2\right)dm_{t}.
\end{equation}
Namely, this first defines $u^h(t)$ for $t\in (0,h]$, then for $t\in[h,2h]$, etc.
Note in particular that this interpolates between the discrete solutions $u_k$ from above, i.e. it holds that $u^h(kh)=u_k$.

\begin{theorem}[uniform estimates and effective existence]\label{thm_main} Let $(M,g_t)_{t\in [0,T]}$ be a smooth one-parameter family of closed Riemannian manifolds. Then the functions $u^{h}(t)$ constructed via the above approximation scheme starting at $u_0\in L^2(M,g_0)$ satisfy the uniform energy estimate
\begin{equation}\label{main_energy_est}
\sup_{t\in[0,T]}\int_M u^h(t)^2 dm_t+ \int_{0}^T \!\! \int_{M} \vert \nabla u^h(t) \vert_{g_t}^2 \, dm_t\,dt \le e^{C_0T} \int_{M}u_0^2 \, dm_0,
\end{equation}
which only depends on $C_0<\infty$ such that $dm_{t_2}\leq e^{C_0(t_2-t_1)}dm_{t_1}$ for  $t_2\geq t_1$.
Moreover, if $u_0$ is essentially bounded above respectively below, then we also have the estimates
\begin{equation}
\sup u^h(t) \leq \sup u_0\quad \textrm{ and }\quad \inf u^h(t)\geq \inf u_0.
\end{equation}
Finally, given $h_i\to 0$, after passing to a subsequence the functions $u^{h_i}(t)$ converge weakly in $L^2 H_0^1$ and weak-$\ast$ in $L^\infty L^2$ to a solution $u$ of the heat equation $\partial_t u = \Lap_{g_t} u$ with initial condition $u_0$.
\end{theorem}

The main point is that our energy estimate \eqref{main_energy_est} only depends on the constant $C_0$ capturing the volume increase in \eqref{assumption}, but does not depend on any other bounds for our family of manifolds. In particular, if $(M,g_t)_{t\in [0,T]}$  evolves by Ricci flow we can simply choose $C_0:=-\min\{\min R_{g_0},0\}$.\\

Furthermore, since our approximation scheme is linear, Theorem \ref{thm_main} immediately implies the following contraction estimate, which in particular gives effective uniqueness:
\begin{corollary}[contraction estimate and effective uniqueness]\label{cor_main}
Let $u^{h}(t)$ and $v^{h}(t)$ be the functions constructed via the above approximation scheme with initial condition $u_0$ and $v_0$, respectively. Then, our approximation scheme with initial condition $\lambda u_0+\mu v_0$ produces the function $\lambda u^{h}(t)+\mu v^{h}(t)$, and we have the uniform estimate
\begin{equation}\label{contr_est}
\sup_{t\in[0,T]}\int_M (u^h(t)-v^h(t))^2 dm_t+ \int_{0}^T \!\! \int_{M} \vert \nabla (u^h(t)-v^h(t)) \vert_{g_t}^2 \, dm_t\,dt \le e^{C_0T} \int_{M}(u_0-v_0)^2 \, dm_0.
\end{equation}
In particular, the subsequential convergence in Theorem \ref{thm_main} entails full convergence, and the unique solutions $u$ and $v$ of the heat equation with initial condition $u_0$ and $v_0$, respectively,  satisfy
\begin{equation}\label{contr_est_sol}
\int_M (u(t)-v(t))^2 dm_t\le e^{C_0t} \int_{M}(u_0-v_0)^2 \, dm_0.
\end{equation}
\end{corollary}

\bigskip

The structure of our proof is as follows. In Section \ref{sec_time_discret}, we consider the recursively defined functions $u_k$ and prove uniform estimates for them, including in particular the energy estimate
\begin{equation}\label{eq-en1_intro}
\sup_{1\leq k\leq N}\int_{M} u_k^2\, dm_{kh}+\sum_{k=1}^N h\int_{M}\abs{\nabla u_k}^2\, dm_{kh}\leq e^{C_0 T}\int_{M} u_0^2\, dm_0.
\end{equation}
In Section \ref{sec_interpolation}, we carefully extend these discrete in time solutions to a function $u^h(t)$ defined for all $t\in[0,T]$ and prove the crucial uniform energy estimate \eqref{main_energy_est}. This estimate depends on the detailed procedure of how we fill in the intermediate times -- in particular, we would not obtain the estimate if the intermediate times were filled in via DeGiorgi-interpolation. Finally, in Section \ref{sec_limits}, we explain how to pass to the limit $h\to 0$. In our time-dependent setting, the weak formulation of solutions of the heat equation involves an extra term coming from the evolution of the volume measure. To handle this we prove a uniform integrability estimate and use Egorov's theorem.\\

\bigskip

\noindent\textbf{Acknowledgements.}
The third author has been supported by an NSERC Discovery Grant and a Sloan Research Fellowship. We are very grateful to Aaron Naber for closely related discussions. This work is based in part on an undergraduate research project by the second author and  the master's project of the fourth author.\\

\bigskip

\section{Time discretization}\label{sec_time_discret}

Let $(M,g_t)_{t\in [0,T]}$ be a smooth one-parameter family of closed Riemannian manifolds. As before we write $dm_t=d\textrm{vol}_{g_t}$ for the volume measure, and let $C_0<\infty$ be such that
\begin{equation}\label{assumption_rest}
dm_{t_2}\leq e^{C_0(t_2-t_1)}dm_{t_1}\qquad \textrm{for } t_2\geq t_1.
\end{equation}
Let $h=T/N$ be the time step for the implicit Euler scheme. Recall that, given the initial condition $u_0\in L^2(M,g_0)$, we recursively define $u_k$ as the unique minimizer of the convex functional
\begin{equation}\label{eq_conv_functional}
u\mapsto \int_{M}\left(\abs{\nabla u}^2_{g_{kh}}+\frac{1}{h}(u- u_{k-1})^2\right)dm_{kh}.
\end{equation}

\begin{proposition}[estimates for time-discretization]\label{prop_discr_time_est}
The functions $u_k$ constructed via the implicit Euler scheme as above satisfy the uniform energy estimate
\begin{equation}\label{eq-en1}
\sup_{1\leq k\leq N}\int_{M} u_k^2\, dm_{kh}+\sum_{k=1}^N h\int_{M}\abs{\nabla u_k}^2\, dm_{kh}\leq e^{C_0 T}\int_{M} u_0^2\, dm_0.
\end{equation}
Moreover, if $u_0$ is essentially bounded above respectively below, then we also have the estimates
\begin{equation}
\sup u_k \leq \sup u_0\quad \textrm{ and }\quad \inf u_k\geq \inf u_0,
\end{equation}
where sup and inf denotes the essential supremum and essential infimum, respectively.
\end{proposition}

\begin{proof}
Observe first that $u_k$ satisfies the Euler-Lagrange equation
\begin{equation}\label{integral_eulerlagrange}
\int_{M}\left(\langle \nabla u_k,\nabla v \rangle_{g_{kh}} +\frac{u_k- u_{k-1}}{h}v\right)\, dm_{kh} =0\qquad \textrm{ for all } v\in H^1(M,g_{kh}).
\end{equation}
Using this, we compute
\begin{align}
2\sum_{k=1}^\ell h \int_{M} \abs{\nabla u_k}^2_{g_{kh}}\, dm_{kh}
&=-2\sum_{k=1}^\ell\int_{M} (u_k- u_{k-1})u_k\, dm_{kh}\\
&\leq \sum_{k=1}^\ell \int_{M}\left(  u_{k-1}^2  -u_k^2\right)\, dm_{kh}\\
&\leq  \sum_{k=1}^\ell e^{C_0h}\!\! \int_{M}\!\!\!\! u_{k-1}^2\,  dm_{(k-1)h} -\int_{M}\!\!  u_k^2\, dm_{kh}\\
&=e^{C_0h}\! \int_{M}\!\!\! u_0^2\, dm_0 +(e^{C_0h}-1) \sum_{k=1}^{\ell-1} \int_{M}\!\!  u_k^2\, dm_{kh} - \int_{M}\!\!  u_\ell^2\, dm_{\ell h} .
\end{align}
Rearranging terms and applying an induction on $\ell$, this yields the uniform energy estimate
\begin{equation}\label{eq-en1_rest}
\sup_{1\leq k\leq N}\int_{M} u_k^2\, dm_{kh}+\sum_{k=1}^N h\int_{M}\abs{\nabla u_k}^2\, dm_{kh}\leq e^{C_0T}\int_{M} u_0^2\, dm_0.
\end{equation}
Now, suppose that $S:=\sup u_0<\infty$. Assume by induction that $u_{k-1}\leq S$ almost everywhere. Using this and the fact that the Dirichlet-energy is Markovian, we see that
\begin{multline}
\int_M\left(\abs{\nabla \min\{u, S\}}^2_{g_{kh}}+\frac{1}{h}(\min\{u, S\}- u_{k-1})^2\right)dm_{kh}\\
\leq  \int_{M}\left(\abs{\nabla u}^2_{g_{kh}}+\frac{1}{h}(u- u_{k-1})^2\right)dm_{kh}
\end{multline}
for all $u\in H^1(M,g_{kh})$. In particular, since $u_k$ is the unique minimizer of this energy functional, it follows that $u_k\leq S$ almost everywhere. This proves that
\begin{equation}
\sup u_k \leq \sup u_0.
\end{equation}
The argument for the essential infimum is similar. This finishes the proof of the proposition.
\end{proof}

\begin{corollary}[contraction estimate]
If $u_k$ and $v_k$ are the functions from the implicit Euler scheme with initial condition $u_0$ and $v_0$, respectively, then
\begin{equation}
\sup_{1\leq k\leq N}\int_{M} (u_k-v_k)^2\, dm_{kh}+\sum_{k=1}^N h\int_{M}\abs{\nabla (u_k-v_k)}^2\, dm_{kh}\leq e^{C_0T}\int_{M}(u_0-v_0)^2\, dm_0.
\end{equation}
\end{corollary}

\begin{proof}
Observe that any solution of the Euler-Lagrange equation \eqref{integral_eulerlagrange} in fact must be the unique minimizer of the functional \eqref{eq_conv_functional}. Since the Euler-Lagrange equation is linear, so is our scheme. Namely, the implicit Euler scheme with initial condition $\lambda u_0+\mu v_0$ produces the functions $\lambda u_k+\mu v_k$. Hence, the corollary follows from the proposition.
\end{proof}

\bigskip

\section{Interpolation}\label{sec_interpolation}
As before, given our smooth one-parameter family of closed Riemannian manifolds $(M,g_t)_{t\in [0,T]}$, we let $C_0<\infty$ be such that the volume measure $dm_t=d\textrm{vol}_{g_t}$ satisfies
\begin{equation}\label{assumption_rest}
dm_{t_2}\leq e^{C_0(t_2-t_1)}dm_{t_1}\qquad \textrm{for } t_2\geq t_1.
\end{equation}
In the previous section, given the initial condition $u_0\in L^2(M,g_0)$, we constructed functions $u_k$ via the implicit Euler scheme with time step $h=T/N$. This defines functions at the discrete times $kh$, for $k=1,\ldots, N$, but does not define functions at times that are not an integer multiple of $h$.\\

Now to fill in the intermediate times, we first extend the metric and initial condition to negative times by setting $g_t=g_0$ and $u^h(t) = u_0$ for $t<0$. We then define $u^h(t)$ recursively in time as unique minimizer of the convex functional
\begin{equation}
u\mapsto \int_{M}\left({\vert \nabla u\vert}^2_{g_t}+\frac{1}{h}(u- u^{h}(t-h))^2\right)dm_{t}.
\end{equation}
Note that this indeed interpolates between the functions $u_k$ from above, namely $u^h(kh)=u_k$.

\begin{proposition}[estimates for interpolated functions]\label{prop_interpol}
The functions $u^h(t)$, as defined above, satisfy
\bea\sup_{t\in[0,T]}\int_M u^h(t)^2 dm_t+ \int_{0}^T \!\! \int_{M} \vert \nabla u^h(t) \vert_{g_t}^2 \, dm_t\,dt \le e^{C_0T} \int_{M}u_0^2 \, dm_0.\eea
Moreover, if $u_0$ is essentially bounded above respectively below, then we also have the estimates
\begin{equation}
\sup u^h(t) \leq \sup u_0\quad \textrm{ and }\quad \inf u^h(t)\geq \inf u_0,
\end{equation}
\end{proposition}

\begin{proof}
Observe that our extension of the metric to negative times preserves the condition \eqref{assumption_rest}. Hence, by Proposition \ref{prop_discr_time_est}, for every fixed $t\in[0,h]$, we get
\begin{equation}\label{eq-112}
\sup_{0\leq j\leq N-1}\int_M  (u^h({t+jh}))^2dm_{t+jh}+\sum_{j=0}^{N-1} h\int_M\vert{\nabla u^h({t+jh})}\vert^2_{g_{t+jh}}dm_{t+jh}\leq e^{C_0 T}\int_{M} u_0^2 dm_0.
\end{equation}
Now, consider the nonnegative function
\begin{equation}
f(t):=\int_M \vert \nabla u^h (t)\vert^2 _{g_t}d m_t.
\end{equation}
Note that
\bea  \int_0^{T}f(t)\, dt =  \int_0^h \sum_{j=0}^{N-1} f(t+ jh)\, dt.
\eea
Hence, using \eqref{eq-112} we infer that
\bea
 \int_0^{T} f(t) \, dt \le \int_0^h \frac{e^{C_0 T}}{h}   \int_M u_0^2 dm_0 \, dt = e^{C_0T} \int_M u_0^2 dm_0. \eea
This proves that
\bea \int_0^T \!\! \int_{M} \vert \nabla u^h(t) \vert^2_{g_t}\, dm_t\, dt \le e^{C_0T} \int_{M_0}u_0^2 \, dm_0.\eea
Finally, the $L^\infty L^2$-bound follows from \eqref{eq-112}, and the bounds for the essential supremum and infimum follow from Proposition \ref{prop_discr_time_est}. This finishes the proof of the proposition.\end{proof}

 \bigskip

 \section{Passing to limits}\label{sec_limits}
 In this final section, we explain how to pass to the limit $h\to 0$. As before, given our smooth one-parameter family of closed Riemannian manifolds $(M,g_t)_{t\in [0,T]}$, let $C_0<\infty$ be such that
\begin{equation}\label{assumption_rest_again}
dm_{t_2}\leq e^{C_0(t_2-t_1)}dm_{t_1}\qquad \textrm{for } t_2\geq t_1.
\end{equation}
Regarding  the initial condition, we assume for the moment that $u_0\in  L^\infty(M,g_0)$ (later, to heat flow general $L^2$ functions we will cut off at level $n$ and pass to a double limit).\\

Let $u^h(t)$ be the function constructed in the previous section with initial condition $u_0$. By Proposition \ref{prop_interpol} we have the estimates
\begin{equation}\label{apest1}
\sup_{t\in [0,T]}\norm{u^h(t)}_{L^\infty}\leq \norm{u_0}_{L^\infty},
\end{equation}
and
\begin{equation}\label{apest2}
 \int_{0}^T \!\! \int_{M} \vert \nabla u^h(t) \vert_{g_t}^2 \, dm_t\,dt \le e^{C_0 T} \int_{M}u_0^2 \, dm_0.
\end{equation}
Also recall that
\be\label{eq-variational2}\int_M \left( \la \nabla u^h(t+h), \nabla v \ra _{g_{t+h}}+  \frac{u^h(t+h)-u^h(t) }{h}v\right) dm_{t+h}=0 \text{ for all }v\in H^1(M,g_{t+h}).\ee
\bigskip

For functions $v:M\times [0,T]\to \mathbb{R}$ on spacetime we consider the norms
\begin{align}
 \Vert v\Vert_{L^\infty L^\infty} := \textrm{sup}_{t,x} |v(x,t)|,
\end{align}
where sup denotes the essential supremum, and
 \begin{align}
  \Vert v\Vert_{L^2 H^1_{0}} &:= \left( \int_0^T\int_M |\nabla v|^2 \, dm_tdt \right)^{1/2},
\end{align}
and
\begin{equation}
 \Vert v\Vert_{L^2H^{-1}} :=  \left( \int_0^T \Vert v (t,\cdot)\Vert_{H^{-1}(M,g_t)}^2\, dt\right)^{1/2},
\end{equation}
where at each fixed time the $H^{-1}(M,g_t)$-norm is defined in duality with $H^1(M,g_t)$.\\

By the uniform $L^\infty L^\infty \cap L^2 H^1_0$-bound from \eqref{apest1} and \eqref{apest2}, for any sequence $h_i\to 0$, after passing to a subsequence, we can pass to a limit
\begin{equation}
u^{h_i} \rightharpoonup u\quad \textrm{weak-$\ast$ in $L^\infty L^\infty$ and weakly in $L^2 H^1_0$}.
\end{equation}

\begin{proposition}[equation for limit]\label{prop_eq_lim}
Any limit $u$ as above is a weak solution of the heat equation on our one-parameter family of closed Riemannian manifolds $(M,g_t)_{t\in [0,T]}$. Namely,
   \bea \label{eq-weaksol1}  \int_0^T\! \int_M u(t)\left(\phi'(t)- \phi(t) R\right)\, dm_tdt  =  \int_0^T\! \int_M \la \nabla u(t),\nabla \phi(t)  \ra_{g_t}\, dm_t dt  \eea
 for all test functions $\phi\in C^1_c(M\times (0,T))$, where $R$ is the function defined by $\partial_t dm_t = -R dm_t$.
\end{proposition}

\begin{proof}
Given $\phi$, let $h_0>0$ be small enough so that the support of $\phi$ is contained in $M\times[h_0,T-h_0]$. Using \eqref{eq-variational2} for $h<h_0$ we compute
\bea 0 &= \int_0^T \int_M \frac{u^h (t+h)- u^h(t)}{h} \phi (t) + \la \nabla u^h(t+h),\nabla \phi(t)  \ra_{g_{t+h}} dm_{t+h} dt \\
 &=  \int_0^{T} \int_M u^h(t) \frac{\phi (t-h)}{h}  + \la \nabla u^h(t),\nabla \phi(t-h)  \ra_{g_t} dm_t dt - \int_0^T \int_M u^h(t) \frac{\phi (t)}{h} dm_{t+h} dt  \, .
 \eea
 Adding and subtracting a term we can rewrite this as
 \begin{multline}\label{eq_three_terms}
0 =  \int _0^T\int_M u^h(t) \frac{\phi (t-h)- \phi(t)}{h}  + \la \nabla u^h(t),\nabla \phi(t-h)  \ra_{g_t} dm_t dt \\
-\int_0^T\int_M u^h(t)\phi(t)\frac{dm_{t+h} - dm_{t}}{h}\,.
\end{multline}
For the first term, since $u^{h_i}$ converges to $u$ weak-$\ast$ in $L^\infty L^\infty$, we see that
\bea
\int _0^T\int_M u^{h_i}(t) \frac{\phi (t-h_i)- \phi(t)}{h_i}\, dm_tdt\to -\int_0^T\int_M u(t)\phi'(t)\, dm_tdt\, .
\eea
For the second term, since $\nabla u^{h_i}$ converges to $\nabla u$ weakly in $L^2 L^2$, we get
\bea
\int _0^T\int_M \la \nabla u^{h_i}(t),\nabla \phi(t-h_i)  \ra_{g_t} dm_t dt \to\int _0^T\int_M  \la \nabla u(t),\nabla \phi(t)  \ra_{g_t} dm_t dt\, .
\eea
It remains to show that the last term in \eqref{eq_three_terms} converges to $\int_0^T \int_M u\phi R$. To this end, note that
\bea
 \frac{dm_{t+h}(x) - dm_t(x)}{h}&= \frac1h \left(e^{-\int_t^{t+h} R (x,s)ds}-1\right) dm_t(x)\\
 &= \frac1h\left(\int_0^h-R(x,t+u) e^{-\int_t^{t+u} R(x,s)ds}\, du\right)dm_t(x),
 \eea
and define
\bea
R^h(x,t):= \fr 1h \int_0^{h}R(x,t+u)e^{-\int_t^{t+u} R(x,s)ds}du.
\eea

\begin{claim}[uniform integrability] For every $\varepsilon>0$ there is $\delta>0$ such that for all $K\subseteq M\times[0,T-h_0]$ with $\iint_K 1 dm_t dt\le \delta$, we have
\begin{equation}
\sup_{h\in (0,h_0)}\iint_K |R^h| dm_tdt \le \varepsilon.
\end{equation}
\end{claim}

\begin{proof}[Proof of the claim] Note that $R\in L^1(M\times [0,T],dm_tdt)$ by smoothness and compactness. Hence, given $\varepsilon>0$, there is a $\delta'>0$ such that for all $K'\subseteq M\times[0,T]$ with $\iint_{K'} 1 dm_t dt\le \delta'$, we have
\bea
\iint_{K'} |R| dm_tdt \le \varepsilon\, .
\eea
Now, choose $\delta= \delta' e^{-C_0}$, where $C_0$ is from \eqref{assumption_rest_again}. Thus, if $K$ is a set in $M\times[0,T-h_0]$ with $\iint_K1dm_t dt<\delta$,  then the  time-shifted set
\bea
K_u:= \{(x,t) \,:\, (x,t-u)\in K \}
\eea
satisfies
\bea
\sup_{u\in(0,h_0)}\iint_{K_u} 1 dm_tdt \le \delta'\, .
\eea
Using this, we can estimate
\begin{equation}\begin{aligned}\label{eq-Rhh} \iint_K |R^h(x,t)|\, dm_t(x) \, dt
 &\le \frac1h \iint_K \int_0^h |R(x,t+u)|e^{-\int_t^{t+u} R(x,s)ds}\, du \, dm_t(x)\, dt  \\
 &= \frac1h \int_0^h\iint_K  |R(x,t+u)|\, dm_{t+u}(x)\, dt\, du\\
 &= \frac1h \int_0^h \iint_{K_u}  |R(x,t)|\, dm_t(x)\, dt\, du\\
 &\le\frac1h \int_0^h \eps =\eps. \end{aligned}
\end{equation}
This proves the claim.
\end{proof}

Continuing the proof of the proposition,
since $R^{h_i}$ converges to $R$ almost everywhere, and since $R^{h_i}$ is uniformly integrable, by Egorov's theorem $R^{h_i}$ converges to $R$ in strongly in $L^1L^1$. Together with the fact that $u^{h_i}\phi$ converges to $u\phi$ weak-$\ast$ in $L^\infty L^\infty$, we conclude that
\begin{equation}
\int_0^T\int_M u^{h_i}(t)\phi(t)\frac{dm_{t+{h_i}} - dm_{t}}{h_i} \to -\int_0^T\int_M u\phi R\, dm_tdt
\end{equation}
This finishes the proof of the proposition.
 \end{proof}

 \begin{corollary}[time derivative]\label{cor_time_der} Any limit $u$ as above has a weak time derivative $\partial_t u\in L^2 H^{-1}_0$. In fact,
 \begin{equation}
\partial_t u=\Delta_{g_t} u.
 \end{equation}
 \end{corollary}

\begin{proof}
Since $u\in L^2H^1_0$, this follows from the theorem via integration by parts.
\end{proof}

\begin{proposition}[continuity and initial data attained]\label{prop_continuity}
Any limit $u$ as above, possibly after suitable modification on a null set, is continuous as an $L^2$-valued function, and we have
\begin{equation}
u(0)=u_0.
\end{equation}
\end{proposition}

\begin{proof} After extending $u$ by reflection to $[-\sigma,T+\sigma]$, let $u_\eps=\eta_\eps\ast u$, where $\eta_\eps(t)$ is a mollifying function. Note that $t\mapsto u_\eps(t)$ is a continuous $L^2$-valued function. For any $t_1\leq t_2$ we have
\begin{align}
\norm{u_\eps(t_2)-u_{\delta}(t_2)}_{L^2}^2
&=\norm{u_\eps(t_1)-u_{\delta}(t_1)}_{L^2}^2
+\int_{t_1}^{t_2}\!\!\int_M \left(2(\dot{u}_\eps-\dot{u}_\delta) (u_\eps-u_\delta) - R(u_\eps-u_\delta)^2\right) \, dm_tdt\nonumber\\
&\leq\norm{u_\eps(t_1)-u_{\delta}(t_1)}_{L^2}^2
+\norm{\dot{u}_\eps-\dot{u}_\delta}_{L^2H^{-1}}^2
+\norm{{u}_\eps-{u}_\delta}_{L^2H^{1}_0}^2
+C_0\norm{{u}_\eps-{u}_\delta}_{L^2L^2}^2.
\end{align}
Observe that $u_\eps\to u$ in $L^2H^1_0$ and $\dot{u}_\eps\to \dot{u}$ in $L^2H^{-1}$. Thus, choosing $t_1$ outside a set of measure zero, we infer that
\begin{equation}
\limsup_{\eps,\delta\to 0}\sup_{t\in [0,T]}\norm{u_\eps(t)-u_{\delta}(t)}_{L^2}^2=0.
\end{equation}
This proves continuity.\\
Now, consider a more general test function $\phi$ that does not vanish near $t=0$. We still assume that $\phi=0$ for $t$ near $T$. Arguing as before we compute
\begin{align}
0 &= \int_{-h}^T \int_M \frac{u^h (t+h)- u^h(t)}{h} \phi (t) + \la \nabla u^h(t+h),\nabla \phi(t)  \ra_{g_{t+h}} dm_{t+h} dt \nonumber\\
 &=  \int_0^{T} \int_M u^h(t) \frac{\phi (t-h)}{h}  + \la \nabla u^h(t),\nabla \phi(t-h)  \ra_{g_t} dm_t dt - \int_{-h}^T \int_M u^h(t) \frac{\phi (t)}{h} dm_{t+h} dt \nonumber  \\
&=  \int_0^{T} \int_M u^h(t) \frac{\phi (t-h)- \phi(t)}{h}  + \la \nabla u^h(t),\nabla \phi(t-h)  \ra_{g_t} dm_t dt\nonumber  \\
& \qquad\qquad + \int_0^T\left[ \int_M u^h(t) \frac{\phi (t)}{h} dm_{t} -\int_M u^h(t) \frac{\phi (t)}{h} dm_{t+h}\right] dt  -\int_{-h}^0\int_M \frac{u^h(t) \phi(t) }{h} dm_{t+h} dt \, .
\end{align}
By taking $h_i\to 0$ we obtain
\begin{multline} 0 =  \int_0^T \int_M -u(t)\phi'(t)  + \la \nabla u(t),\nabla \phi(t)  \ra_{g_t} dm_t dt \\
+\int_0^T \int_M u(t) \phi(t)R dm_t dt - \int_M u_0\phi(0) dm_0,
\end{multline}
where we used that $u^h(t)=u_0$ for $t\in (-h,0)$.
Via integration by parts, this can be rewritten as
\bea 0 &=  \int_0^T \int_M u'(t)\phi(t)  + \la \nabla u(t),\nabla \phi(t)  \ra_{g_t} dm_t dt +\int_M (u(0)- u_0)\phi(0)\, dm_0. \eea
On the other hand, we know that \bea 0 =  \int_0^T \int_M u'(t)\phi(t)  + \la \nabla u(t),\nabla\phi(t)\ra_{g_t} dm_tdt \eea for all test functions $\phi$, even if they do not vanish near $t=0$. Thus, we conclude that $u(0)=u_0$.
\end{proof}

 \bigskip

Combining the above propositions, we can now conclude the proof of our main results:

\begin{proof}[Proof of Theorem \ref{thm_main} and Corollary \ref{cor_main}]
Given our one-parameter family of closed Riemannian manifolds $(M,g_t)_{t\in [0,T]}$, recall that $C_0<\infty$ is so that $dm_{t_2}\leq e^{C_0(t_2-t_1)}dm_{t_1}$ for $t_2\geq t_1$.\\

Let us first deal with the case $u_0\in  L^\infty(M,g_0)$. Recall that we extended the metric and initial condition to negative times by setting $g_t=g_0$ and $u^h(t) = u_0$ for $t<0$. We then defined $u^h(t)$ recursively in time as unique minimizer of the convex functional
\begin{equation}
u\mapsto \int_{M}\left({\vert \nabla u\vert}^2_{g_t}+\frac{1}{h}(u- u^{h}(t-h))^2\right)dm_{t}.
\end{equation}
By Proposition \ref{prop_interpol}, the functions $u^h(t)$ satisfy the uniform energy estimate
\begin{equation}\label{main_pr_energ}
\sup_{t\in[0,T]}\int_M u^h(t)^2 dm_t+ \int_{0}^T \!\! \int_{M} \vert \nabla u^h(t) \vert_{g_t}^2 \, dm_t\,dt \le e^{C_0T} \int_{M}u_0^2 \, dm_0,
\end{equation}
which only depends on $C_0$, as well as the estimates
\begin{equation}
\sup u^h(t) \leq \sup u_0\quad \textrm{ and }\quad \inf u^h(t)\geq \inf u_0.
\end{equation}
Hence, for any sequence $h_i\to 0$, we can pass to a subsequential limit weakly in $L^2 H^1_0$ and weak-$\ast$ in $L^\infty L^\infty$ (and thus in particular also weak-$\ast$ in $L^2 L^\infty$). By Proposition \ref{prop_eq_lim}, Corollary \ref{cor_time_der} and Proposition \ref{prop_continuity}, any such limit $u$ is a weak solution of the heat equation $\partial_t u =\Delta_{g_t} u$ with initial condition $u(0)=u_0$. By standard parabolic estimates $u$ is smooth for $t>0$ and solves the equation in the classical sense. Furthermore, since our approximation scheme is linear, the same estimates hold for the difference between two solutions. In particular, $u$ is unique, and the subsequential convergence entails full convergence.\\

Finally, given any $u_0\in  L^2(M,g_0)$, let $u^{h}(t)$ he function produced by our approximation scheme with initial condition $u_{0}$. We still have the uniform energy estimate \eqref{main_pr_energ}, and we still can pass to a subsequential limit $u$ weakly in $L^2 H^1_0$ and weak-$\ast$ in  $L^2 L^\infty$. To show that $u(t)$ solves the heat equation with initial condition $u_0$, we consider the truncated function
\begin{equation}
u_{0,n}(x):= \left\{\begin{array}{ll}
        -n, & \text{if } u_0(x)\leq -n\\
        u_0(x), & \text{if } -n\leq u_0(x)\leq n\\
        n, & \text{if } u_0(x)\geq n.
        \end{array}\right.
\end{equation}
Let $u^h_n(t)$ be the function produced by our approximation scheme with initial condition $u_{0,n}$. By the above, for any fixed $n$, for $h\to 0$ the functions $u^h_n(t)$ converge to the unique solution $u_n(t)$ of the heat equation with initial condition $u_{0,n}$. Furthermore, since $u_{0,n}\to u_0$ in $L^2(M,g_0)$, we have
\bea
\limsup_{n\to \infty}\left(\sup_{t\in[0,T]}\int_M (u^h_n(t)-u^h(t))^2 dm_t+ \int_{0}^T \!\! \int_{M} \vert \nabla (u^h_n(t)-u^h(t)) \vert_{g_t}^2 \, dm_t\,dt \right)=0\eea
uniformly in $h$. Hence, we conclude that $u(t)$ solves the heat equation with initial condition $u_0$.
\end{proof}

\bigskip

\bibliography{CGHS}

\bibliographystyle{alpha}

\vspace{10mm}

{\sc Beomjun Choi, Department of Mathematics, University of Toronto,  40 St George Street, Toronto, ON M5S 2E4, Canada}\\

{\sc Jianhui Gao, Department of Biostatistics, Dalla Lana School of Public Health, University of Toronto,  155 College Street, Toronto, ON  M5T 3M7, Canada}\\

{\sc Robert Haslhofer, Department of Mathematics, University of Toronto,  40 St George Street, Toronto, ON M5S 2E4, Canada}\\

{\sc Daniel Sigal, Department of Family and Community Medicine, University of Toronto, 500 University Avenue, Toronto, ON M5G 1V7, Canada}\\

\emph{E-mail:} beomjun.choi@utoronto.ca, jianhui.gao@mail.utoronto.ca, roberth@math.toronto.edu, daniel.sigal@mail.utoronto.ca

\end{document}


TITLE: Probability mass function from the distribution
QUESTION [0 upvotes]: I have the following distribution function:
\begin{equation*}
      F(x) = \begin{cases}
      0, x<-1 \\
      \frac{1}{2}, -1 \leq x < \frac{1}{2} \\
      \frac{3}{4}, \frac{1}{2} \leq x <2 \\
      1, x \geq 2
        \end{cases}
    \end{equation*}
How can i obtain the probability mass function? My attempt was to use the discontinuites and try to evaluate the probabilities, but i was no able to confirm anything. I know that the sums off all probabilities must be one.

REPLY [0 votes]: If before -1 the distribution function equals 0 and after -1 it equals $\frac{1}{2}$, it means that there is a mass of probability $\frac{1}{2}$ in $x=-1$.
For the same reason, there is a mass of $\frac{3}{4} - \frac{1}{2} = \frac{1}{4}$ in $x=\frac{1}{2}$, and finally a mass of $1 - \frac{3}{4} = \frac{1}{4}$ in $x = 2$.
The sum of all probabilities is $\frac{1}{2} + \frac{1}{4} + \frac{1}{4} = 1$.