# Extending Perfect Matchings to Hamiltonian Cycles in Line Graphs

###### Abstract

A graph has the Perfect–Matching–Hamiltonian property (for short the
PMH–property) if each of its perfect matchings can be extended to a
hamiltonian cycle. In this paper we establish some sufficient conditions for a
graph $G$ in order to guarantee that its line graph $L(G)$ has the
PMH–property. In particular, we prove that this happens when $G$ is (i) a
hamiltonian graph with maximum degree at most $3$, (ii) a complete graph with
an even number of edges, (iii) a balanced complete bipartite graph with at
least $100$ vertices, or (iv) an arbitrarily traceable graph. Further related
questions and open problems are proposed along the paper.

###### keywords:

line graph, hamiltonian cycle, perfect matchings

Marién Abreu1, John Baptist Gauci2, Domenico Labbate3 ††1,3The research that
led to the present paper was partially supported by a grant of the group
GNSAGA of INdAM. ,
Giuseppe Mazzuoccolo4 and Jean Paul Zerafa5M. Abreu, J.B. Gauci, D. Labbate,
G. Mazzuoccolo and J.P. Zerafa 1,3Dipartimento di Matematica, Informatica ed
Economia, Università degli Studi della Basilicata, Italy.
2Department of Mathematics, University of Malta, Malta.
4Dipartimento di Informatica, Università di Verona, Italy.
5Dipartimento di Scienze Fisiche, Informatiche e Matematiche, Università di
Modena e Reggio Emilia<EMAIL_ADDRESS>
<EMAIL_ADDRESS>
<EMAIL_ADDRESS>
<EMAIL_ADDRESS>
<EMAIL_ADDRESS>05C45 Eulerian and Hamiltonian graphs, 05C76
Graph operations, 05C70 Factorization, matching, partitioning, covering and
packing

##  1 Introduction

The main property studied in this paper is related to two of the most studied
concepts in graph theory: perfect matchings and hamiltonian cycles. Let us
recall that a perfect matching of a graph $G$ is a set of independent edges of
$G$ that covers all the vertices in $G$, and a hamiltonian cycle is a cycle
passing through all vertices of $G$. If such a cycle exists then $G$ is
_hamiltonian_.

The complete graph on $n$ vertices, denoted by $K_{n}$, is the graph in which
every two vertices are adjacent. For any graph $G$, $K_{G}$ denotes the
complete graph on the same vertex set $V(G)$ of $G$. A perfect matching of
$K_{G}$ is said to be a _pairing_ of $G$. In [ThomassenEtAl], the authors say
that a graph $G$ has the _Pairing–Hamiltonian property_ (for short the
PH–property) if every pairing $M$ of $G$ can be extended to a hamiltonian
cycle $H$ of $K_{G}$ in which $E(H)-M\subseteq E(G)$. Amongst other results,
the authors show that the only cubic graphs having the PH–property are
$K_{4}$, the complete bipartite graph $K_{3,3}$ and the 3–cube. Adopting a
similar terminology, we say that a graph $G$ has the
_Perfect–Matching–Hamiltonian property_ (for short the PMH–property) if every
perfect matching of $G$ can be extended to a hamiltonian cycle of $G$. This
has already been studied in literature, and graphs having this property are
also known as $F$–Hamiltonian, where $F$ is a perfect matching (see
[Haggkvist, Yang]). Henceforth, if a graph has the
Perfect–Matching–Hamiltonian property, we say that it is a PMH–graph or simply
that it is PMH. Note that since every perfect matching of $G$ is a pairing of
$G$, then, clearly, a graph having the PH–property is also a PMH–graph.

In the 1970s, Las Vergnas [LasVergnas] (see Theorem 1.1) and Haggkvist
[Haggkvist] (see Theorem 1.2) gave two sufficient Ore-type conditions for a
graph to be PMH.

######  Theorem 1.1.

[LasVergnas] Let $G$ be a bipartite graph, with partite sets $U$ and $V$, such
that $|U|=|V|=\frac{n}{2}\geq 2$. If for each pair of non-adjacent vertices
$u\in U$ and $v\in V$ we have $deg(u)+deg(v)\geq\frac{n}{2}+1$, then $G$ is
PMH.

######  Theorem 1.2.

[Haggkvist] Let $G$ be a graph, such that the order of $G$ is even and at
least $4$. If for each pair of non-adjacent vertices $u$ and $v$ we have
$deg(u)+deg(v)\geq n+1$, then $G$ is PMH.

Later on, in 1993, Ruskey and Savage [RuskeySavage] asked whether every
matching in the $n$–dimensional hypercube $Q_{n}$, for $n\geq 2$, extends to a
hamiltonian cycle of $Q_{n}$. This was in fact shown to be true for $n=2,3,4$
(see [Fink]) and for $n=5$ (see [WangZhao]). Moreover, Fink [Fink] also showed
that $Q_{n}$ has the PH–property (and so it is also a PMH–graph). Finally,
Amar, Flandrin and Gancarzewicz in [AFG] gave a degree sum condition for three
independent vertices under which every matching of a graph lies in a
hamiltonian cycle. More results on PMH–graphs can be found in the already
cited paper by Yang [Yang].

The class of line graphs of connected graphs is a compelling class of graphs
for which a great deal is known regarding hamiltonicity and the existence of
perfect matchings. Indeed, it is well-known that if $G$ is connected and has
an even number of edges, then its line graph admits a perfect matching (see
Section 2 for more details). Furthermore, hamiltonicity of a line graph $L(G)$
is another extensively studied property: a necessary and sufficient condition
for hamiltonicity in $L(G)$ is proved in [HararyNashWilliams], while Thomassen
conjectured in [Thomassen] that every $4$–connected line graph is hamiltonian.

Along these lines, we here deal with the line graph of a graph $G$ and search
for sufficient conditions on $G$ which result in $L(G)$ being PMH. In
particular, if the trivial necessary condition that $|E(G)|$ is even is
satisfied, we can prove that $L(G)$ is PMH in all the following cases:

  * •

$G$ is hamiltonian with maximum degree $\Delta(G)$ at most $3$ (Theorem 2.3),

  * •

$G$ is a complete graph (Theorem 3.2),

  * •

$G$ is a complete bipartite graph $K_{m,m}$ and $m\geq 50$ (Theorem 3.5), and

  * •

$G$ is arbitrarily traceable from some vertex (Theorem 3.6).

Further related results and open problems regarding graphs which are
hypohamiltonian, eulerian or with large maximum degree are discussed along the
paper.

###  1.1 Definitions and Notation

All graphs considered in this paper are finite, simple (without loops or
multiple edges) and connected. Most of our terminology is standard, and we
refer the reader to [BM] for further definitions and notation not explicitly
stated.

Unless otherwise stated, we let the order of $G$ be $n$ and denote the set of
vertices of $G$ by $\\{v_{1},v_{2},\ldots,v_{n}\\}$. A walk (of length $k$) in
a graph $G$ is a sequence $v_{1},v_{2},\ldots,v_{k+1}$ of vertices of $G$ such
that $v_{i}$ is adjacent to $v_{i+1}$ for all $i\in[k]$. If $v_{1}=v_{k+1}$,
the walk is said to be closed. A path on $t$ vertices, denoted by $P_{t}$, is
a walk of length $t-1$ in which all the vertices and edges are distinct. We
may also refer to $P_{t}$ as a $t$– _path_. A cycle of length $k$, denoted by
$(v_{1},\ldots,v_{k})$, is a closed walk of length $k$ in which all the
vertices are distinct, except for the first and last. A hamiltonian cycle of a
graph $G$ is a cycle which covers all the vertices of $G$, and when such a
cycle exists we say that $G$ is hamiltonian.

A tour of $G$ is a closed walk having no repeated edges, and an Euler tour is
one that traverses all the edges of $G$. In the latter case, the graph is said
to be eulerian. A dominating tour of $G$ is a tour in which every edge of $G$
is incident with at least one vertex of the tour. In particular, a dominating
tour which is 2–regular is referred to as a dominating cycle. In general, if a
walk does not pass through some vertex $v$, we say that $v$ is untouched or
uncovered.

A clique in a graph $G$ is a complete subgraph of $G$, and so $K_{n}$ may
sometimes be referred to as an $n$– _clique_.

##  2 Line graphs of graphs with small maximum degree

The line graph $L(G)$ of a graph $G$ is the graph whose vertices correspond to
the edges of $G$, and two vertices of $L(G)$ are adjacent if the corresponding
edges in $G$ are incident to a common vertex. For some edge $e\in E(G)$, we
refer to the corresponding vertex in $L(G)$ as $e$, for simplicity, unless
otherwise stated. A clique partition of a graph $G$ is a collection of cliques
of $G$ in which each edge of $G$ occurs exactly once. For any $v\in V(G)$, let
$Q_{v}$ be the set of all the edges incident to $v$. Clearly, $Q_{v}$ induces
a clique in $L(G)$ and $\mathcal{Q}=\\{Q_{v}:v\in V(G)\text{ with degree at
least }2\\}$ is a clique partition of $L(G)$. We say that $\mathcal{Q}$ is the
canonical clique partition of $L(G)$. In the sequel, we shall refer to
$Q_{v_{i}}$ simply as $Q_{i}$ and in order to avoid trivial cases, from now on
we always assume that $G$ is a connected graph of order larger than $2$.

An $H$–decomposition of $G$ is a partition of $E(G)$ into subgraphs of $G$
each being isomorphic to $H$. In general, it is not hard to show that every
connected graph $G$ with $|E(G)|$ even has a $P_{3}$–decomposition. This is
equivalent to saying that $L(G)$ has a perfect matching (see also Corollary 3
in [Sumner]): indeed there is a natural bijection between the paths in a
$P_{3}$–decomposition of $G$ and the edges of the corresponding perfect
matching of $L(G)$. Since we are interested in line graphs which are PMH, a
necessary condition is that the line graph admits a perfect matching, and so
in the sequel we may assume that $G$ has even size, i.e. $|E(G)|=|V(L(G))|$ is
even, unless otherwise stated. Another trivial necessary condition is that
$L(G)$ is hamiltonian: Harary and Nash-Williams in [HararyNashWilliams] showed
that $L(G)$ is hamiltonian if and only if $G$ admits a dominating tour. In
particular, this implies that if $G$ is hamiltonian or eulerian, then, $L(G)$
is also hamiltonian, but the converse is not necessarily true (see also
[Chartrand, HararyNashWilliams, Sedlacek]).

The following technical lemma is the main tool we use to prove Theorem 2.3 as
well as a series of related results contained in this section. It describes a
necessary and sufficient condition to extend a given perfect matching to a
hamiltonian cycle in subcubic graphs.

######  Lemma 2.1.

Let $G$ be a connected graph such that $\Delta(G)\leq 3$. A perfect matching
$M$ of $L(G)$ can be extended to a hamiltonian cycle if and only if there
exists a dominating cycle $D$ of $G$ such that the vertices in $G$ untouched
by $D$ correspond to a subset of cliques in $\mathcal{Q}$ not intersected by
$M$, where $\mathcal{Q}$ is the canonical clique partition of $L(G)$.

######  Proof 2.2.

Let $M$ be a perfect matching of $L(G)$ which can be extended to a hamiltonian
cycle $H_{L}$ of $L(G)$. For some orientation of $H_{L}$, let
$Q_{1},Q_{2},\ldots,Q_{s}$ be the order in which $H_{L}$ intersects at least
one edge of the cliques in $\mathcal{Q}$, where $s\in[n]$. Since
$\Delta(G)\leq 3$, $\mathcal{Q}$ consists of 2–cliques and 3–cliques, implying
that the sequence $Q_{1},Q_{2},\ldots,Q_{s}$ does not have repetitions. We
claim that $D=(v_{1},v_{2},\ldots,v_{s})$ is a dominating cycle of $G$. If
every clique in $\mathcal{Q}$ is visited by $H_{L}$, then
$(v_{1},v_{2},\ldots,v_{s})$ is a hamiltonian cycle because for every two
consecutive vertices $v_{i},v_{j}$ in $D$, $v_{i}$ is adjacent to $v_{j}$, and
$s=n$. So, let $Q$ be a clique in $\mathcal{Q}$ not visited by $H_{L}$. Let
$Q_{j_{1}},\ldots,Q_{j_{k}}$ be the cliques in $\mathcal{Q}$ which share a
vertex with $Q$, for $k=2$ or $3$ and $j_{1},\ldots,j_{k}\in[s]$. Let the
corresponding vertices of $Q$ and $Q_{j_{1}},\ldots,Q_{j_{k}}$, in $G$, be $v$
and $v_{j_{1}},\ldots,v_{j_{k}}$, respectively. Clearly, $D$ is a cycle, since
consecutive cliques in the sequence $Q_{1},Q_{2},\ldots,Q_{s}$ imply the
existence of an edge between the corresponding two vertices in $D$. Also,
since $v\neq v_{t}$ for all $v_{t}$ in $D$, and $M$ is a perfect matching of
$L(G)$, then the vertices $v_{j_{1}},\ldots,v_{j_{k}}$ are in the cycle $D$
(not necessarily adjacent amongst themselves) and so the edges in $G$ having
$v$ as an end-vertex have at least one end-vertex in $D$. Thus, since $v$ was
arbitrary, $D$ is dominating. Moreover, every vertex in $G$ untouched by $D$
corresponds to a clique in $\mathcal{Q}$ not intersected by $H_{L}$, which is
a subset of the cliques in $\mathcal{Q}$ not intersected by $M$.

Conversely, let $M$ be a perfect matching of $L(G)$ and let
$D=(v_{1},v_{2},\ldots,v_{s})$ be a dominating cycle in $G$, for some $s\leq
n$, such that the untouched vertices correspond to a subset of the cliques in
$\mathcal{Q}$ not intersected by $M$. Note that there exists a one-to-one
mapping between the untouched vertices in $G$ and the unintersected cliques in
$\mathcal{Q}$, which is not necessarily onto. We traverse the cliques in
$\mathcal{Q}$ as follows. Let $Q$ be a clique in $\mathcal{Q}$, with
corresponding vertex $v\in V(G)$. We consider three cases:

Case 1: $E(Q)\cap M\neq\emptyset$.
By our assumption, $v=v_{i}$, for some $i\in[s]$, and we traverse $Q$
($=Q_{i}$) using the unique path joining $V(Q_{i-1})\cap V(Q_{i})$ and
$V(Q_{i})\cap V(Q_{i+1})$ which contains $E(Q)\cap M$.

Case 2: $E(Q)\cap M=\emptyset$ and $v\in D$.
In this case, $v=v_{j}$, for some $j\in[s]$, and we traverse $Q$ ($=Q_{j}$)
using the edge with end-vertices $V(Q_{j-1})\cap V(Q_{j})$ and $V(Q_{j})\cap
V(Q_{j+1})$.

Case 3: $E(Q)\cap M=\emptyset$ and $v\not\in D$.
Since $M$ is a perfect matching, all the cliques in $\mathcal{Q}$ sharing a
vertex with $Q$ (which must be triangles in this case) are intersected by $M$.
These 3–cliques are traversed as in Case 1, and in this way the edges of $Q$
are not intersected.

We traverse all the cliques in $\mathcal{Q}$ in the above way and let the
resulting sequence of edges be $H_{L}$. We claim that $H_{L}$ is a hamiltonian
cycle of $L(G)$ containing $M$. By Case 1, $H_{L}$ contains $M$ and so every
vertex of $L(G)$ is covered by $H_{L}$. Also, the sequence of cliques
intersected by $H_{L}$, i.e. $Q_{1},Q_{2},\ldots,Q_{s}$, corresponds to the
sequence of vertices in $D$, and so, since $D$ is connected and 2–regular,
then $H_{L}$ is a connected cycle, proving our claim.

The previous lemma can be generalised to connected graphs of arbitrary large
degree by replacing dominating cycle with dominating tour. The proof is
similar, but we omit the details here, since we do not really need this more
general statement in what follows.

######  Remark 1.

Note that Lemma 2.1 is not true in general for $\Delta(G)>3$. An easy example
is shown in Figure 1: indeed, an arbitrary perfect matching of $L(G)$ can be
extended to a hamiltonian cycle, i.e. $L(G)$ is PMH, but there is no
dominating cycle in $G$.

Figure 1: A graph with maximum degree 4 whose line graph is PMH.

By using Lemma 2.1, we can furnish a first sufficient condition on $G$
assuring that its line graph is PMH.

######  Theorem 2.3.

Let $G$ be a hamiltonian graph such that $\Delta(G)\leq 3$. Then, $L(G)$ is
PMH.

######  Proof 2.4.

Let $H$ be a hamiltonian cycle of $G$. Given any perfect matching $M$ of
$L(G)$, since the set of vertices untouched by $H$ in $G$ is empty, it is
trivially a subset of the cliques in $\mathcal{Q}$ not intersected by $M$.
Consequently, by Lemma 2.1, $M$ can be extended to a hamiltonian cycle of
$L(G)$. Since $M$ was arbitrary, $G$ is PMH.

In particular, Theorem 2.3 applies for all hamiltonian cubic graphs. However,
in the cubic case we can say more. In 1964, Kotzig [Kotzig] proved that the
existence of a hamiltonian cycle in a cubic graph is both a necessary and
sufficient condition for a partition of $L(G)$ into two hamiltonian cycles. We
show that:

######  Corollary 2.

Let $G$ be a hamiltonian cubic graph and $M$ a perfect matching of $L(G)$.
Then, $L(G)$ can be partitioned into two hamiltonian cycles, one of which
contains $M$.

######  Proof 2.5.

If we extend $M$ to a hamiltonian cycle of $L(G)$ using the method described
in Lemma 2.1, we obtain a hamiltonian cycle which intersects each triangle in
$\mathcal{Q}$, since $G$ is hamiltonian. It is easy to see that the complement
of a hamiltonian cycle of $L(G)$ which intersects each triangle in
$\mathcal{Q}$ in one or two edges is again a hamiltonian cycle.

When considering Theorem 2.3, one could wonder if the two conditions on the
maximum degree and the hamiltonicity of $G$ could be improved in some way.
First of all, we remark that our result is best possible in terms of the
maximum degree of $G$: indeed, if $G$ is a hamiltonian graph such that
$\Delta(G)=4$, then, $L(G)$ is not necessarily PMH. For instance, consider the
hamiltonian graph in Figure 2 having maximum degree $4$, and let $M$ be the
perfect matching of $L(G)$ shown in the figure.

Figure 2: A hamiltonian graph with maximum degree 4 whose line graph is not
PMH.

Suppose $M$ can be extended to a hamiltonian cycle. Then, it should include
all edges incident to its vertices of degree $2$, and so it should contain the
paths $v_{1},v_{2},\ldots,v_{4}$ and $v_{5},v_{6},\ldots,v_{10}$. However,
these two paths cannot be extended to a hamiltonian cycle of $L(G)$ containing
$M$, contradicting our assumption.

On the other hand, hamiltonicity of $G$ in Theorem 2.3 is not a necessary
condition, since there exist non-hamiltonian cubic graphs whose line graph is
PMH. In particular, in Proposition 3 we prove that hypohamiltonian cubic
graphs are examples of such graphs. Let us recall that a graph $G$ is
hypohamiltonian if $G$ is not hamiltonian, but for every $v\in V(G)$, $G-v$
has a hamiltonian cycle.

######  Proposition 3.

Let $G$ be a hypohamiltonian graph such that $\Delta(G)\leq 3$. Then, $L(G)$
is PMH.

######  Proof 2.6.

Let $M$ be a perfect matching of $L(G)$. Then, by an easy counting argument,
there surely exists some clique $Q\in\mathcal{Q}$ which is not intersected by
$M$. Let $v$ be the corresponding vertex in $G$. Since $G$ is hypohamiltonian,
there exists a dominating cycle in $G$ which touches all vertices of $G$
except $v$, and so by Lemma 2.1, $L(G)$ is PMH, since $M$ was arbitrary.

Finally, another possible improvement of Theorem 2.3 could be a weaker
assumption on the length of the longest cycle of $G$ (i.e. the circumference
of $G$, denoted by $circ(G)$). However, in Proposition 5 we exhibit cubic
graphs having circumference just one less than the order of $G$ whose line
graphs are not PMH.

We will make use of the following standard operations on cubic graphs known as
$Y$–reduction (shrinking a triangle to a vertex) and of its inverse,
$Y$–extension (expanding a vertex to a triangle), illustrated in Figure 3.

Figure 3: $Y$–operations

For the proof of Proposition 5, we also need to show that each edge of $L(G)$,
where $G$ is cubic and hamiltonian, belongs to a perfect matching. This kind
of property is extensively studied in many papers and it is usually called
$1$–extendability. Theorem 2.1 in [Plummer] states that every claw-free
$3$–connected graph is $1$–extendable. By recalling that every line graph is a
claw-free graph, we have, in particular, that $L(G)$ is $1$–extendable if $G$
is cubic and $3$–edge-connected. The generalisation to an arbitrary
hamiltonian cubic graph $G$ is not hard to achieve by using such a result, but
here we prefer to present a direct short proof which is valid for any
bridgeless cubic graph and which makes use of the following tool from the
proof of Proposition 2 in [Mazzuoccolo].

######  Remark 4.

[Mazzuoccolo] Let $G_{1}$ be a cubic graph of even size and $M$ a perfect
matching of $L(G_{1})$. The graph $G_{2}$ obtained by applying $Y$–reductions
to the triangles in $L(G_{1})-M$ belonging to the canonical clique partition
of $L(G_{1})$ is isomorphic to $G_{1}$.

######  Lemma 2.7.

Let $G$ be a bridgeless cubic graph of even size. Every edge of $L(G)$ belongs
to a perfect matching.

######  Proof 2.8.

Let $e\in E(L(G))$ and let $M$ be a perfect matching of $L(G)$. Assume
$e\notin M$, otherwise the statement holds. The graph $L(G)-M$ is cubic and by
Remark 4 can be obtained by applying suitable $Y$–extensions to $G$. Since $G$
is bridgeless, then $L(G)-M$ is bridgeless as well. Moreover, in
[Schonberger], Schönberger proved that every bridgeless cubic graph is
$1$–extendable: hence, there exists a perfect matching of $L(G)-M$ which
contains $e$. Such a perfect matching is trivially also a perfect matching of
$L(G)$ containing $e$.

The following proposition shows that the hamiltonicity condition in Theorem
2.3 cannot be relaxed to any other condition regarding the length of the
longest cycle in $G$. Indeed, starting from an appropriate cubic graph and
performing suitable $Y$–extensions, we obtain a graph of circumference one
less than its order whose line graph is not PMH.

######  Proposition 5.

Let $G$ be a hypohamiltonian cubic graph of odd size. Let $G^{\prime}$ be a
graph obtained by performing a $Y$–extension to all vertices of $G$ except
one. Then, $circ(G^{\prime})=|V(G^{\prime})|-1$ and $L(G^{\prime})$ is not
PMH.

######  Proof 2.9.

Let $v$ be the vertex of $G$ to which we do not apply a $Y$–extension, and let
the resulting graph be $G^{\prime}$. The assertion on the circumference of
$G^{\prime}$ immediately follows by its construction and by the
hypohamiltonicity of $G$. Therefore, suppose $L(G^{\prime})$ is PMH, for
contradiction. Denote by $Q_{v}$ the triangle in the canonical clique
partition of $L(G^{\prime})$ which corresponds to the vertex $v$. By
construction of $G^{\prime}$, we have $|E(G^{\prime})|=|E(G)|+3(|V(G)|-1)$.
Since both $|V(G)|-1$ and $|E(G)|$ are odd, then $|E(G^{\prime})|$ is even,
i.e. $L(G^{\prime})$ has even order. By Lemma 2.7, there exists a perfect
matching $M$ of $L(G^{\prime})$ which intersects a chosen edge of $Q_{v}$.
Lemma 2.1 assures that there exists a dominating cycle $D$ in $G^{\prime}$
such that the set of its uncovered vertices does not contain $v$. Furthermore,
every dominating cycle of $G^{\prime}$, in particular $D$, intersects at least
one edge of all the $Y$–expanded triangles. Consequently, the dominating cycle
$D$ induces a cycle in $G$ which passes through $v$ and also through every
other vertex of $G$, making $G$ hamiltonian, a contradiction.

As already remarked, the graph in Figure 2 is hamiltonian, but not every
perfect matching in its line graph can be extended to a hamiltonian cycle.
Such example is not regular, and we are not able to find a regular one. A most
natural question to ask is whether the hamiltonicity and regularity of a graph
are together sufficient conditions to guarantee the PMH–property of its line
graph. Thus, we suggest the following problem:

Phys. Rev. B Let $G$ be an $r$–regular hamiltonian graph of even size, for
$r\geq 4$. Does $L(G)$ admit the PMH–property?

To conclude this section, let us note that not all $4$–regular (and so not all
eulerian) graphs of even size have a PMH line graph. A non-hamiltonian example
is given in Figure 4. It is not hard to check that every perfect matching of
$L(G)$ which contains the edges $e_{1}e_{2}$ and $e_{3}e_{4}$ cannot be
extended to a hamiltonian cycle of $L(G)$, whose vertices are given the same
label as the corresponding edges in $G$.

Figure 4: A non–hamiltonian $4$-regular graph whose line graph does not have
the PMH–property.

Since the graphs in Figure 2 and Figure 4 are both not simultaneously eulerian
and hamiltonian, we pose a further problem:

Phys. Rev. B Let $G$ be a graph of even size which is both eulerian and
hamiltonian. Does $L(G)$ admit the PMH–property?

##  3 Other classes of graphs whose line graphs admit the PMH–property

The complete graph $K_{n}$, for even $n$, and the complete bipartite graph
$K_{m,m}$, for $m\geq 2$, are clearly PMH. To stay in line with the contents
of this paper, we now see whether their line graphs are also PMH. To this
purpose, given an edge-colouring (not necessarily proper) of a hamiltonian
graph, a hamiltonian cycle in which no two consecutive edges have the same
colour will be referred to as a _properly coloured hamiltonian cycle_.

###  3.1 Complete graphs

First of all, we note that the line graph of a complete graph $K_{n}$ has a
perfect matching if and only if the number of edges in $K_{n}$ is even. Hence,
in the sequel we consider only complete graphs with $n\equiv 0,1\mod 4$.

We denote the vertices of $K_{n}$ by $\\{v_{i}:i\in[n]\\}$ and the edges of
$K_{n}$ by $\\{e_{i,j}=v_{i}v_{j}:i\neq j\\}$. Moreover,
$V(L(K_{n}))=\\{v_{i,j}:i\neq j\\}$ where the vertex $v_{i,j}$ corresponds to
the edge $e_{i,j}$ of $K_{n}$. Finally, we denote the edges of $L(K_{n})$ by
$\\{e^{i}_{j,k}=v_{i,j}v_{i,k}:i\neq j\neq k\\}$. Note that the upper index in
the notation $e^{i}_{j,k}$ immediately indicates that the considered edge
belongs to the clique $Q_{i}$ in the canonical clique partition of $L(K_{n})$,
while the order of lower indices is irrelevant.

The proof of our main theorem in this section, Theorem 3.2, makes use of a
special case of a result by Daykin from 1976 [Daykin1976] which asserts the
existence of a properly coloured hamiltonian cycle if the edges of $K_{n}$ are
coloured according to the following constraints.

######  Theorem 3.1.

[Daykin1976] If the edges of the complete graph $K_{n}$, for $n\geq 6$, are
coloured in such a way that no three edges of the same colour are incident to
any given vertex, then there exists a properly coloured hamiltonian cycle.

In the following proof, the process of traversing one path after another will
be called concatenation of paths. If two paths $P_{1}$ and $P_{2}$ have end-
vertices $x,y$ and $y,z$, respectively, we write $P_{1}P_{2}$ to denote the
path starting at $x$ and ending at $z$ obtained by traversing $P_{1}$ and then
$P_{2}$.

######  Theorem 3.2.

For $n\equiv 0,1\mod 4$, $L(K_{n})$ is PMH.

######  Proof 3.3.

Since $K_{4}$ is hamiltonian and cubic, by Theorem 2.3, the result holds for
$n=4$. Therefore, we can assume $n>4$.

Let $M$ be a perfect matching of $L(K_{n})$. We colour the $\frac{1}{4}n(n-1)$
edges of $M$ with $\frac{1}{4}n(n-1)$ different colours. For all
$e^{i}_{j,k}\in M$, we colour the corresponding edges $e_{i,j}$ and $e_{i,k}$
in $K_{n}$ with the same colour given to the edge $e^{i}_{j,k}$ in $L(K_{n})$.
This gives a $P_{3}$–decomposition of $K_{n}$ in which each $P_{3}$ is
monochromatic and the colours of all the 3–paths are pairwise distinct.

If $n=5$, the total number of hamiltonian cycles in $K_{5}$ is
$\frac{4!}{2}=12$. Each of the five monochromatic 3–paths in $K_{5}$ is on
exactly two distinct hamiltonian cycles. Therefore, the number of hamiltonian
cycles containing a monochromatic $P_{3}$ is at most 10, hence $K_{5}$
contains at least two (complementary) properly coloured hamiltonian cycles.
Without loss of generality, let one of them be $H$, say
$H=(v_{1},v_{2},\ldots,v_{5}).$

For $n\geq 8$, by Theorem 3.1, there exists a properly coloured hamiltonian
cycle $H$ in $K_{n}$ and again, without loss of generality, we can assume
$H=(v_{1},v_{2},\ldots,v_{n})$.

Now, for all $n\geq 5$ and $n\equiv 0,1\mod 4$, we will use the properly
coloured hamiltonian cycle $H$ in $K_{n}$ to obtain a hamiltonian cycle
$H_{L}$ in $L(K_{n})$ containing the perfect matching $M$. We construct the
hamiltonian cycle $H_{L}$ in such a way that it enters and exits each clique
in the canonical clique partition $\mathcal{Q}$ of $L(K_{n})$ exactly once.
More precisely, we construct a suitable path $P_{i}$ in each clique $Q_{i}$
and we obtain $H_{L}$ as concatenation of such paths following the order
determined by $H$. Consider the $(n-1)$–clique $Q_{i}$ and its two vertices
$v_{i-1,i}$ and $v_{i,i+1}$. The corresponding edges $e_{i-1,i}$ and
$e_{i,i+1}$, in $K_{n}$, are not of the same colour since they are consecutive
in $H$, and so the edge $e^{i}_{i-1,i+1}\not\in M$. Consequently, there exists
an $M$–alternating path, which we denote by $P_{i}$, starting at $v_{i-1,i}$
and ending at $v_{i,i+1}$ in $Q_{i}$ such that $M\cap E(Q_{i})\subset P_{i}$.
We define $H_{L}:=P_{1}P_{2}\dots P_{n}.$ Note that $H_{L}$ is a cycle since
the paths $P_{i}$ are all internally and pairwise disjoint, and the beginning
of $P_{1}$ coincides with the end of $P_{n}$. Moreover, $H_{L}$ is hamiltonian
because $M\subset E(H_{L})$ and so each vertex of the line graph belongs to
$H_{L}$.

###  3.2 Complete bipartite graphs

In 1976, Chen and Daykin considered an analogous version of Theorem 3.1 for
the complete bipartite graph $K_{m,m}$ (see [ChenDaykin1976]). A particular
case of Theorem $1^{\prime}$ in [ChenDaykin1976] can be stated as follows.

######  Theorem 3.4.

[ChenDaykin1976] Consider an edge-colouring of the complete bipartite graph
$K_{m,m}$ such that no vertex is incident to more than $k$ edges of the same
colour. If $m\geq 25k$, then there exists a properly coloured hamiltonian
cycle.

By considering the case $k=2$ in the previous theorem, i.e. $m\geq 50$, and by
using an argument very similar to the one used for complete graphs, we obtain
the following result.

######  Theorem 3.5.

For every even $m\geq 50$, $L(K_{m,m})$ is PMH.

In a forthcoming paper, two of the authors are going to extend Theorem 3.5 by
using a more direct, but quite technical, approach.

###  3.3 Arbitrarily traceable graphs

A graph $G$ is said to be arbitrarily traceable (or equivalently randomly
eulerian) from a vertex $v\in V(G)$ if every walk starting from $v$ and not
containing any repeated edges can be completed to an eulerian tour. This
notion was firstly introduced by Ore in [Ore], who proved that a graph $G$ is
arbitrarily traceable from $v$ if and only if every cycle in $G$ touches $v$.
Here we show that every perfect matching $M$ of the line graph of an
arbitrarily traceable graph can be extended to a hamiltonian cycle.

Note that the technique used in this proof is in someway different from what
was used in the case of complete graphs in Section 3.1. Again, a perfect
matching $M$ of $L(G)$ corresponds to a $P_{3}$–decomposition of $G$, but this
time we construct an Euler tour of the original graph (instead of a
hamiltonian cycle) such that two edges in the same $3$–path are consecutive in
the Euler tour (as opposed to what was done in Section 3.1 where we forbade
two edges in the same $3$–path to be consecutive in the hamiltonian cycle
considered in $K_{n}$).

######  Theorem 3.6.

Let $G$ be an arbitrarily traceable graph from some vertex such that $G$ is of
even size. Then, its line graph has the PMH–property.

######  Proof 3.7.

Let $M$ be a perfect matching of $L(G)$. Consider the $P_{3}$–decomposition of
$G$ induced by $M$. Since $G$ is arbitrarily traceable from some vertex, there
exists an Euler tour in which every pair of edges in the same $3$–path are
consecutive. The sequence of edges in this Euler tour corresponds to a
sequence of vertices in $L(G)$ which gives a hamiltonian cyle $H$ of $L(G)$,
and since the two edges of each 3–path in the $P_{3}$–decomposition are
consecutive in the Euler tour, then $H$ contains all the edges of $M$, as
required.

##  4 Concluding Remark

Along the paper, we have proposed several sufficient conditions of different
types for a graph in order to guarantee the PMH–property in its line graph.
The wide variety of such conditions, ranging between sparse and dense graphs,
do not allow us to easily identify non trivial necessary conditions to this
problem. This could be seemingly hard, but we still consider it an intriguing
problem to be addressed in the future.

## References

  * [1] ThomassenEtAlA. Alahmadi, R.E.L. Aldred, A. Alkenani, R. Hijazi, P. Solé and C. ThomassenExtending a perfect matching to a Hamiltonian cycleDiscrete Math. Theor. Comput. Sci.17(1)2015241–254
  * [2] AFGD. Amar, E. Flandrin and G. GancarzewiczA degree condition implying that every matching is contained in a hamiltonian cycleDiscrete Math.30920093703–3713
  * [3] BMJ.A. Bondy and U.S.R. MurtyGraph TheoryGrad. Texts in Math.2442008
  * [4] ChartrandG. ChartrandGraphs and their associated line-graphsDoctoral dissertation, Michigan State University1964
  * [5] Daykin1976D.E. DaykinGraphs with Cycles Having Adjacent Lines Different ColorsJ. Combin. Theory Ser. B201976149–152
  * [6] ChenDaykin1976D.E. Daykin and C.C. ChenGraphs with Hamiltonian Cycles Having Adjacent Lines Different ColorsJ. Combin. Theory Ser. B211976135–139
  * [7] FinkJ. FinkPerfect matchings extend to Hamilton cycles in hypercubesJ. Combin. Theory Ser. B9720071074–1076
  * [8] HaggkvistR. HaggkvistOn $F$-Hamiltonian graphin: Graph Theory and Related Topics by J.A. Bondy, U.S.R. Murty, Academic Press, New York1979219–231
  * [9] HararyNashWilliamsF. Harary and C. St. J.A. Nash-WilliamsOn Eulerian and Hamiltonian graphs and line graphsCanad. Math. Bull.81965701–709
  * [10] KotzigA. KotzigHamilton graphs and Hamilton circuitsTheory of Graphs and its Applications (Proc. Sympos. Smolenice 1963), Nakl. CSAV, Praha196463–82
  * [11] LasVergnasM. Las VergnasThesisUniversity of Paris, Paris1972
  * [12] MazzuoccoloG. MazzuoccoloPerfect one-factorizations in line-graphs and planar graphsAustralas. J. Combin.412008227–233
  * [13] OreO. OreA problem regarding the tracing of graphsElem. Math.6195149–53
  * [14] PlummerM. PlummerExtending matchings in claw-free graphsDiscrete Math.1251994301–307
  * [15] RuskeySavageF. Ruskey and C. SavageHamilton cycles that extend transposition matchings in Cayley graphs of $S_{n}$SIAM J. Discrete Math.61993152–166
  * [16] SchonbergerT. SchönbergerEin Beweis des Petersenschen GraphensatzesActa Litt. Acad. Sci. Szeged7193451–57
  * [17] SedlacekJ. SedlačekSome properties of interchange graphsin: Theory of graphs and its applications, edited by M. Fiedler, Prague1964145–150
  * [18] SumnerD.P. SumnerGraphs with $1$-factorsProc. Amer. Math. Soc.4219748–12
  * [19] ThomassenC. ThomassenReflections on graph theoryJ. Graph Theory101986309–324
  * [20] WangZhaoF. Wang and W. ZhaoMatchings extend to hamiltonian cycles in 5-cubeDiscuss. Math. Graph Theory382018217–231
  * [21] YangZ. YangOn $F$–Hamiltonian graphsDiscrete Math.1961999281–286
  * [22]


# Numerical differentiation by the polynomial-exponential basis

Phuong M. Nguyen Department of Mathematics and Statistics, University of North
Carolina at Charlotte, Charlotte, NC, 28223, USA<EMAIL_ADDRESS>Thuy T.
Le Department of Mathematics and Statistics, University of North Carolina at
Charlotte, Charlotte, NC, 28223, USA<EMAIL_ADDRESS>Loc H. Nguyen Department
of Mathematics and Statistics, University of North Carolina at Charlotte,
Charlotte, NC, 28223, USA<EMAIL_ADDRESS>corresponding author. Michael
V. Klibanov Department of Mathematics and Statistics, University of North
Carolina at Charlotte, Charlotte, NC, 28223, USA<EMAIL_ADDRESS>
###### Abstract

Our objective is to calculate the derivatives of data corrupted by noise. This
is a challenging task as even small amounts of noise can result in significant
errors in the computation. This is mainly due to the randomness of the noise,
which can result in high-frequency fluctuations. To overcome this challenge,
we suggest an approach that involves approximating the data by eliminating
high-frequency terms from the Fourier expansion of the given data with respect
to the polynomial-exponential basis. This truncation method helps to
regularize the issue, while the use of the polynomial-exponential basis
ensures accuracy in the computation. We demonstrate the effectiveness of our
approach through numerical examples in one and two dimensions.

Keywords: Numerical differentiation, derivatives, polynomial-exponential
basis, truncation

AMS subject classification: 65D10, 65D25

##  1 Introduction

We revisit the problem how to differentiate noisy data. The problem is
formulated as follows:

######  Problem 1.1.

Let $\Omega=(-R,R)^{d}$, $d\geq 1$, be an open and bounded domain of
$\mathbb{R}^{d}$ where $R$ is a positive number. Let
$f^{*}:\Omega\to\mathbb{R}$ be a function. Given the noisy data

$f^{\delta}({\bf x})=f^{*}({\bf x})+\delta\eta({\bf x})\quad{\bf x}\in\Omega,$
(1.1)

where $\eta$ is a function taking random numbers in the range $[-1,1]$ and
$\delta\in(0,1)$ is the noise level, find an approximation of the derivatives
of $f^{*}$. More precisely, compute

  1. 1.

the gradient vector $\nabla f^{*}=(\partial_{x_{i}}f^{*})_{i=1}^{d}$,

  2. 2.

the Hessian matrix $D^{2}f^{*}=(\partial_{x_{i}x_{j}}^{2}f^{*})_{i,j=1}^{d}.$

The task of differentiating noisy data holds great importance in various
fields, including applied mathematics, statistics, data science, physics,
engineering, etc. However, the problem of computing derivatives is severely
ill-posed. Even a minor amount of noise in the data can result in significant
errors in computation, see e.g., [1, 3]. We present a well-known example in
1D. Consider $\eta(x)=\sin(nx)$, where $n$ is an integer and $x\in\mathbb{R}$.
We have

$f^{\delta}(x)=f^{*}(x)+\delta\sin(nx),\quad{f^{\delta}}^{\prime}(x)={f^{*}}^{\prime}(x)+n\delta\cos(nx),$
(1.2)

for $x\in\mathbb{R}$. The absolute error in this example is
$\|n\delta\cos(nx)\|_{L^{\infty}(\mathbb{R})}=n\delta\gg 1$ as $n\to\infty$,
even though the perturbation term $\delta\sin(nx)$ is compatible to the noise
level $\delta$, which is assumed to be small. Due to the importance of
differentiating noisy data, much research has been conducted in this area. In
the following, we review some commonly employed methods for carrying out this
task.

  1. 1.

The finite difference method is the most natural approach for differentiation.
An approximation of the derivative of $f^{\delta}$ can be obtained using the
following formula:

${f^{\delta}}^{\prime}(x)\approx\frac{f^{\delta}(x+h)-f^{\delta}(x)}{h}\approx{f^{*}}^{\prime}(x)+\frac{\delta(\eta(x+h)-\eta(x))}{h}$
(1.3)

for $x\in\mathbb{R}$ where $h$ is a step size. The step size $h$, which serves
as a regularization factor, must be chosen appropriately to ensure stability.
It is important to note that if the step size $h$ is too small, the expression
on the right-hand side of (1.3) becomes too large, leading to significant
computational errors. This is because $\eta(x+h)$ and $\eta(x)$ might take any
value and, hence, the term $\frac{\delta(\eta(x+h)-\eta(x))}{h}$ might diverge
as $h\to 0$. For further details and the strategy to choose the step size $h$,
we refer the reader to [5, 20].

  2. 2.

Tikhonov optimization is a more commonly used approach that involves
introducing cost functionals with a Tikhonov regularization term. An example
of such a cost functional is

$J(u)=\Big{\|}f^{\delta}(x)-f^{\delta}(-R)-\int_{\mathbb{R}}^{x}u(s)ds\Big{\|}^{2}_{L^{2}(-R,R)}+\epsilon\|u\|_{X}^{2},$
(1.4)

where $\epsilon>0$ is the regularization parameter and $X$ is a functional
space. The absolute minimum of this cost functional provides an approximation
to ${f^{*}}^{\prime}$. This approach is discussed in more details in [15].
Selecting the appropriate regularization parameter $\epsilon$ for each
functional space $X$ for the regularization term in (1.4) is not a trivial
task. A well-known method for determining the regularization parameter is
Morozov’s discrepancy principle, which is detailed in [3, 18, 19, 23].

  3. 3.

An alternative method for computing derivatives of data involves the use of
cubic spline curves to smooth the data. It is worth mentioning that the cubic
smoothing spline was initially introduced in [21, 22, 24]. Suppose that
$f^{\delta}$ is the given data, and let $S$ be the natural cubic spline that
approximates $f^{\delta}$. Here, by natural cubic spline, we mean that the
function $S$ is twice continuously differentiable with
$S^{\prime\prime}(-R)=S^{\prime\prime}(R)=0$, and $S$ coincides on each
subinterval $[x_{i-1},x_{i}]$ with some cubic polynomial, where
$x_{0}=-R<x_{1}<x_{2}<\dots<x_{n}=R$, $n>1$, is a partition of $(-R,R)$. One
can then use the derivatives of $S$ to approximate the derivatives of $f^{*}$.
For a method that combines cubic spline and Tikhonov optimization technique to
differentiate noisy data, we refer the reader to [6].

  4. 4.

Other methods for differentiation are discussed in [2, 4, 15, 16] and their
references.

The example of $f^{\delta}(x)=f^{*}(x)+\delta\sin(nx)$ in (1.2) highlights the
ill-posed nature of the problem, which arises from the high-frequency
components of the data. It suggests cutting off these components to increase
stability. More precisely, given a function $f^{\delta}\in L^{2}(\Omega)$, we
approximate

$f^{\delta}({\bf x})=\sum_{n=1}^{\infty}f_{n}^{\delta}\Phi_{n}({\bf
x})\simeq\sum_{n=1}^{N}f_{n}^{\delta}\Phi_{n}({\bf x})\quad{\bf x}\in\Omega$
(1.5)

for some cut-off number $N$, where $\\{\Phi_{n}\\}_{n=1}^{\infty}$ is an
orthonormal basis of $L^{2}(\Omega)$ and

$f_{n}^{\delta}({\bf x})=\int_{\Omega}f^{\delta}({\bf x})\Phi_{n}({\bf
x})d{\bf x}.$

Then, we can approximate the desired derivatives using the following formulas

$\nabla f^{\delta}({\bf x})=\sum_{n=1}^{N}f_{n}^{\delta}\nabla\Phi_{n}({\bf
x}),\quad D^{2}f^{\delta}({\bf
x})=\sum_{n=1}^{N}f_{n}^{\delta}D^{2}\Phi_{n}({\bf x}),$ (1.6)

for ${\bf x}\in\Omega.$ Although the numerical method based on (1.6) may not
be rigorously valid due to the term-by-term differentiation of the series in
(1.5), it is an effective technique for numerical computation. Proving the
analytical validity of this approach as $N$ approaches $\infty$ poses a
significant challenge, which is not addressed in our paper. Nevertheless, our
method remains acceptable. In fact, it is well-known that Problem 1.1 is
highly unstable, and therefore, a regularized technique is necessary.
Truncating the series in (1.5) serves as an option for this purpose.

The main concern in (1.6) is to identify a suitable basis
$\\{\Phi_{n}\\}_{n\geq 1}$ that enables reliable numerical differentiation
through (1.6). We observe that using a popular basis such as Legendre
polynomials or trigonometric functions in the well-known Fourier expansion
might not be appropriate. This is mainly due to the fact that the initial
function of these bases is a constant, which has an identically zero
derivative. Consequently, the contribution of $f_{1}$ in (1.6) is overlooked.
The lack of this information significantly reduces the accuracy of the method.
The basis $\\{\Phi_{n}\\}_{n\geq 1}$ we use in this paper is constructed by
extending the polynomial-exponential basis initially introduced by Klibanov,
the fourth author of this paper, in [10] and [12, Section 6.2.3]. The original
goal of Klibanov was to use this basis for the numerical solution of some
coefficient inverse problems, see, e.g. [7, 8, 9, 11, 13, 17], [12, Chapters
7,10-12], and [14]. This basis is an appropriate choice for (1.6) since it
satisfies the necessary condition that derivatives of $\Phi_{n}$, $n\geq 1$,
are not identically zero. We will demonstrate the effectiveness of the
polynomial-exponential basis by comparing some numerical results due to (1.6)
in two cases when $\\{\Phi_{n}\\}_{n\geq 1}$ is the polynomial-exponential
basis and $\\{\Phi_{n}\\}_{n\geq 1}$ is the widely-used trigonometric basis.
Additionally, we will compare the numerical results obtained by our method
with those obtained by the Tikhonov regularization and the cubic spline
methods, which will serve as further evidence of the efficiency of our
approach.

The polynomial-exponential basis $\\{\Phi_{n}\\}_{n\geq 1}$ has an additional
significant property, in addition to the ”non-identically zero” characteristic
mentioned earlier. This property states that for all values of $N\geq 2$, the
matrix $(\langle\Phi_{n},\Phi_{m}^{\prime}\rangle_{L^{2}})_{1\leq m,n\geq N}$
is invertible. This property guarantees a global convergence of Carleman-based
convexification methods to solve inverse scattering problems in [7, 8, 9, 12,
17].

The organization of this paper is as follows. Section 2 provides an overview
of our approach. Section 3 presents numerical results for one and two
dimensions. A comparison between our method and other numerical approaches can
be found in section 4. Section 5 is for concluding remarks.

##  2 The numerical method based on the truncation technique

In [10], Klibanov proposed a special orthonormal basis of $L^{2}(-R,R)$ to
numerically solve inverse problems. For any $x\in(-R,R)$, we define
$\phi_{n}(x)=x^{n-1}e^{x}$. It is clear that the set $\\{\phi\\}_{n\geq 1}$ is
complete in $L^{2}(-R,R)$. By applying the Gram-Schmidt orthonormalization
process to this set, we obtain an orthonormal basis for $L^{2}(-R,R)$, which
is denoted by $\\{\Psi_{n}\\}_{n\geq 1}$ and named the polynomial-exponential
basis. The basis $\\{\Psi_{n}\\}_{n\geq 1}$ plays a vital role in our method
for addressing Problem 1.1. The product of $\\{\Psi_{n}\\}_{n\geq 1}$ is the
basis we use to approximate the noisy data $f^{\delta}$. For ${\bf
n}=(n_{1},n_{2},\dots,n_{d})$, we define

$P_{{\bf n}}({\bf
x})=\Psi_{n_{1}}(x_{1})\Psi_{n_{2}}(x_{2})\dots\Psi_{n_{d}}(x_{d})\quad\mbox{for
all }{\bf x}=(x_{1},\dots,x_{d})\in\Omega.$ (2.1)

It is obvious that $\\{P_{{\bf n}}\\}_{{\bf n}\in\mathbb{N}^{d}}$ forms an
orthonormal basis of $L^{2}(\Omega).$ For any function $f\in L^{2}(\Omega)$,
we can write

$f({\bf x})=\sum_{{\bf n}\in\mathbb{N}^{d}}a_{{\bf n}}P_{{\bf n}}({\bf
x})=\sum_{{\bf n}=(n_{1},\dots,n_{d})\in\mathbb{N}^{d}}a_{{\bf
n}}\Psi_{n_{1}}(x_{1})\Psi_{n_{2}}(x_{2})\dots\Psi_{n_{d}}(x_{d})\quad{\bf
x}\in\Omega,$ (2.2)

where

$a_{{\bf n}}=a_{n_{1}n_{2}\dots n_{d}}=\int_{\Omega}f({\bf x})P_{{\bf n}}({\bf
x})d{\bf
x}=\int_{\Omega}f(x_{1},x_{2},\dots,x_{d})\Psi_{n_{1}}(x_{1})\Psi_{n_{2}}(x_{2})\dots\Psi_{n_{d}}(x_{d})({\bf
x})d{\bf x}.$ (2.3)

Motivated by the Galerkin approximation, we truncate the representation of the
function $f$ in (2.2) as

$f({\bf x})=\sum_{n_{1}=1}^{\infty}\dots\sum_{n_{d}=1}^{\infty}a_{{\bf
n}}\Psi_{n_{1}}(x_{1})\Psi_{n_{2}}(x_{2})\dots\Psi_{n_{d}}(x_{d})\simeq\sum_{n_{1}=1}^{N_{1}}\dots\sum_{n_{d}=1}^{N_{d}}a_{{\bf
n}}\Psi_{n_{1}}(x_{1})\Psi_{n_{2}}(x_{2})\dots\Psi_{n_{d}}(x_{d})$

for some positive integers $N_{1},\dots,N_{d}$ where ${\bf
n}=(n_{1},\dots,n_{d})$ and ${\bf x}=(x_{1},\dots,x_{d})$. Hence, the function
$f$ approximately becomes

$f({\bf x})\simeq\sum_{n_{1}=1}^{N_{1}}\dots\sum_{n_{d}=1}^{N_{d}}a_{{\bf
n}}\Psi_{n_{1}}(x_{1})\Psi_{n_{2}}(x_{2})\dots\Psi_{n_{d}}(x_{d}).$ (2.4)

######  Remark 2.1.

Truncating the Fourier series, as depicted in equation (2.4), provides an
effective regularization technique for addressing ill-posed problems like
Problem 1.1. This approach involves eliminating the high-frequency components
of function $f$, resulting in a partial reduction of the ill-posedness of the
problem. This technique has been successfully employed in solving inverse
problems, where it enables the computation of numerical solutions even when
significant noise levels are present, as evidenced by [7, 11, 13]. In
particular, highly noisy experimental data are treated by this technique in
[7] and [12, Chapter 10]. The cut-off numbers $N_{1},\dots,N_{d}$ are utilized
as regularization parameters in our method, and their determination can be
achieved through numerical methods using the available data without requiring
any knowledge of the noise level. We refer to Section 3.1 for further details
on selecting these cut-off numbers.

After smoothing the data using (2.4), we can compute the first derivatives of
$f$ via the formulas

$\partial_{x_{i}}f({\bf
x})\simeq\sum_{n_{1}=1}^{N_{1}}\dots\sum_{n_{d}=1}^{N_{d}}a_{{\bf
n}}\Psi_{n_{1}}(x_{1})\Psi_{n_{2}}(x_{2})\dots\Psi_{n_{i}}^{\prime}(x_{i})\dots\Psi_{n_{d}}(x_{d}).$
(2.5)

for $i\in\\{1,\dots,d\\}$. The second derivatives of $f$ are computed using

$\partial_{x_{i}x_{j}}f({\bf
x})\simeq\left\\{\begin{array}[]{ll}\displaystyle\sum_{n_{1}=1}^{N_{1}}\dots\sum_{n_{d}=1}^{N_{d}}a_{{\bf
n}}\Psi_{n_{1}}(x_{1})\Psi_{n_{2}}(x_{2})\dots\Psi_{n_{i}}^{\prime}(x_{i})\dots\Psi_{n_{j}}^{\prime}(x_{j})\dots\Psi_{n_{d}}(x_{d})&i\not=j,\\\
\displaystyle\sum_{n_{1}=1}^{N_{1}}\dots\sum_{n_{d}=1}^{N_{d}}a_{{\bf
n}}\Psi_{n_{1}}(x_{1})\Psi_{n_{2}}(x_{2})\dots\Psi_{n_{i}}^{\prime\prime}(x_{i})\dots\Psi_{n_{d}}(x_{d})&i=j,\end{array}\right.$
(2.6)

for $i,j\in\\{1,\dots,d\\}.$ The approximations in (2.5) and (2.6) suggest
Algorithm 1 to solve Problem 1.1. We refer the reader to Section 3.1 for a
numerical method to choose the cut-off numbers in the first step of Algorithm
1.

Algorithm 1 The procedure to compute derivatives of noisy data

1: Choose cut-off numbers $N_{1},N_{2},\dots,N_{d}$.

2: Construct the orthonormal basis $\\{\Psi_{n}\\}_{n\geq 1}$ defined in the
first paragraph of Section 2.

3: For each ${\bf n}\in\\{(n_{1},\dots,n_{d}):1\leq n_{1}\leq
N_{1},\dots,1\leq n_{d}<N_{d}\\}$, compute the coefficients $a_{{\bf n}}$
$a_{{\bf n}}=a_{n_{1}n_{2}\dots
n_{d}}=\int_{\Omega}f(x_{1},x_{2},\dots,x_{d})\Psi_{n_{1}}(x_{1})\Psi_{n_{2}}(x_{2})\dots\Psi_{n_{d}}(x_{d})d{\bf
x}.$ (2.7)

4: Find the first derivatives of $f$ via formulas (2.5).

5: Find the second derivatives of $f$ via formulas (2.6).

######  Remark 2.2.

The selection of the polynomial-exponential basis $\\{P_{\bf n}\\}_{{\bf
n}\in\mathbb{N}^{d}}$ is critical for achieving success in our approach. Upon
revisiting equations (2.5) and (2.6), it becomes apparent that the accuracy of
the computed results is heavily reliant on the contribution of the Fourier
coefficients $a_{\bf n}$, ${\bf n}\in\mathbb{N}^{d}$. Therefore, if an
inappropriate basis such as $\\{Q_{\bf n}\\}_{n\geq 1}$ is chosen, which
contains an entry $Q_{\bf m}$ with zero derivative for some ${\bf
m}\in\mathbb{N}^{d}$, then the corresponding Fourier coefficient $b_{\bf
m}=\int_{\Omega}f({\bf x})Q_{\bf m}({\bf x})d{\bf x}$ would not be present in
equations (2.5) and (2.6). For instance, in 1D, the first entry of the
trigonometric basis involving $\cos\Big{(}\frac{\pi nx}{R}\Big{)}$, $n\geq 0$,
and $\sin\Big{(}\frac{\pi mx}{R}\Big{)}$, $m\geq 1$, used in the Fourier
expansion is the constant $\cos 0=1$, whose derivative vanishes. Consequently,
the first term in equations (2.5) and (2.6) for computed derivatives will be
missing. This leads to a decrease in accuracy during computation as the first
term in the series could be the most crucial one. Thus, the trigonometric
basis is unsuitable for our method. This observation will be confirmed through
numerical experiments in this paper.

##  3 Numerical examples

We implement Algorithm 1 for the cases of 1D and 2D. In all tests below, we
compute the derivatives of a function $f^{*}$ using the noisy data given by

$f^{\delta}({\bf x})=f^{*}({\bf x})(1+\delta\mbox{rand}({\bf x}))$ (3.1)

where rand$({\bf x})$ is a function that generates uniformly distributed
random numbers in $[-1,1].$ The noise levels are set to be $5\%$, $10\%,$ and
$20\%.$

###  3.1 Choosing the cut-off number

Before presenting the numerical results, we explain the process of selecting
the cut-off number in Step 1 of Algorithm 1. To simplify matters, we will only
present our strategy for the one-dimensional case. The same approach is
utilized for selecting the cut-off numbers in the two-dimensional case. For
each $N>1$, we compare noisy data $f^{\delta}$ with the sum
$\sum_{n=1}^{N}f_{n}^{\delta}\Psi_{n}(x)$. In other words, for each given data
$f^{\delta}$, we compute

$\varphi_{N}(x)=\frac{\big{|}f^{\delta}(x)-\sum_{n=1}^{N}f_{n}^{\delta}\Psi_{n}(x)\big{|}}{\|f^{\delta}\|_{L^{\infty}}},\quad\mbox{where
}f_{n}^{\delta}=\int_{-R}^{R}f^{\delta}(x)\Psi_{n}(x)dx,$

for several values of $N$. Then we choose $N$ is
$\|\varphi_{N}\|_{L^{\infty}(-R,R)}$ is sufficiently small. An illustration of
this strategy is provided in Figure 1.

(a) The data $f^{\delta}$ (dash-dot) and its approximation
$\sum_{n=1}^{N}f_{n}^{\delta}\Psi_{n}(x)$ (solid) when $N=10$.

(b) The data $f^{\delta}$ (dash-dot) and its approximation
$\sum_{n=1}^{N}f_{n}^{\delta}\Psi_{n}(x)$ (solid) when $N=15$.

(c) The data $f^{\delta}$ (dash-dot) and its approximation
$\sum_{n=1}^{N}f_{n}^{\delta}\Psi_{n}(x)$ (solid) when $N=20$.

(d) The function $\varphi_{N}$ when $N=10$.

(e) The function $\varphi_{N}$ when $N=15$.

(f) The function $\varphi_{N}$ when $N=20$.

Figure 1:  An example of how to choose the cut-off number $N$ where the data,
with $5\%$ noise, is taken from Test 1 below. It is evident that $N=20$ should
be chosen for Test 1.

This methodology is implemented in all of the following tests. The same
procedure is used for the experiment involving two dimensions.

###  3.2 The case of one dimension

We compute the first and second derivatives of some functions $f^{*}(x)$
defined in $(-R,R)$ where $R=3.$ On $(-R,R)$, we arrange a partition

$\mathcal{G}=\big{\\{}x_{i}=-R+(i-1)h,i=1,\dots,N\big{\\}}\subset[-3,3]$ (3.2)

where the step size $h=0.001$ and $N=6001$.

####  3.2.1 Test 1

In this test, we take $f^{*}(x)=\sin(4x)$ as our function of interest. The
accurate first and second-order derivatives are $f_{\rm
true}^{\prime}(x)=4\cos(x)$ and $f_{\rm true}^{\prime\prime}(x)=-16\sin(x)$,
respectively. Our chosen cut-off number for this test is $N=20$.

(a) The true and computed $f^{\prime}(x)$; noise level $\delta=5\%$

(b) The true and computed $f^{\prime}(x)$; noise level $\delta=10\%$

(c) The true and computed $f^{\prime}(x)$; noise level $\delta=20\%$

(d) The true and computed $f^{\prime\prime}(x)$; noise level $\delta=5\%$

(e) The true and computed $f^{\prime\prime}(x)$; noise level $\delta=10\%$

(f) The true and computed $f^{\prime\prime}(x)$; noise level $\delta=20\%$

Figure 2:  Test 1. The true and computed derivatives of the function
$f(x)=\sin(4x)$. As can be seen, our method is highly proficient in accurately
computing derivatives of both the first and second order. Notably, the errors
are primarily concentrated at the endpoints of the computed domain.

The graphical representation in Figure 2 illustrates both the computed and
true derivatives of $f^{*}$. Based on the outcomes shown in Figure 2, it is
apparent that Algorithm 1 performs effectively in computing derivatives, even
when there is a high level of noise, up to 20%. It is worth mentioning that
the errors mostly occur at the endpoints of the computational interval, while
the computed function’s accuracy within the interval exceeds expectations. The
first two columns of Table 1 display the computed errors over the entire
interval $(-3,3)$, while the last two columns show the computed errors over
the interval $(-2,2)$.

| $\frac{\|f^{\prime}_{\rm true}-f^{\prime}_{\rm comp}\|_{L^{2}(-3,3)}}{\|f^{\prime}_{\rm true}\|_{L^{2}(-3,3)}}$ | $\frac{\|f^{\prime\prime}_{\rm true}-f^{\prime\prime}_{\rm comp}\|_{L^{2}(-3,3)}}{\|f^{\prime\prime}_{\rm true}\|_{L^{2}(-3,3)}}$ | $\frac{\|f^{\prime}_{\rm true}-f^{\prime}_{\rm comp}\|_{L^{2}(-2,2)}}{\|f^{\prime}_{\rm true}\|_{L^{2}(-2,2)}}$ | $\frac{\|f^{\prime\prime}_{\rm true}-f^{\prime\prime}_{\rm comp}\|_{L^{2}(-2,2)}}{\|f^{\prime\prime}_{\rm true}\|_{L^{2}(-2,2)}}$
---|---|---|---|---
$\delta=0.05$ | 0.0060 | 0.0268 | 0.0030 | 0.0195
$\delta=0.10$ | 0.0110 | 0.0996 | 0.0031 | 0.0201
$\delta=0.20$ | 0.0260 | 0.1123 | 0.0073 | 0.0282
Table 1: Test 1. The relative computed errors with respect to the $L^{2}$
norms over the intervals $(-3,3)$ and $(-2,2)$. As can be observed, the
relative errors are lower than the noise level.

####  3.2.2 Test 2

We calculate the derivatives for the function $f^{*}(x)=\sin(x^{2})$. The true
first-order and second-order derivatives for this function are given by
$f_{\rm true}^{\prime}=2x\cos(x^{2})$ and $f^{\prime\prime}_{\rm
true}=2\cos(x^{2})-4x^{2}\sin(x^{2})$, respectively. For this test, we use a
cut-off number of $N=25$. Figure 3 displays the graphs of the computed
derivatives.

(a) The true and computed $f^{\prime}(x)$; noise level $\delta=5\%$

(b) The true and computed $f^{\prime}(x)$; noise level $\delta=10\%$

(c) The true and computed $f^{\prime}(x)$; noise level $\delta=20\%$

(d) The true and computed $f^{\prime\prime}(x)$; noise level $\delta=5\%$

(e) The true and computed $f^{\prime\prime}(x)$; noise level $\delta=10\%$

(f) The true and computed $f^{\prime\prime}(x)$; noise level $\delta=20\%$

Figure 3:  Test 2. The true and computed derivatives of the function
$f(x)=\sin(x^{2})$. As seen, the performance of Algorithm 1 in this test is
out of expectation. The errors occur at the endpoints $\\{-3,3\\}$ while the
computed derivatives are accurate inside the interval $(-3,3)$.

Similar to Test 1, Figure 3 visually confirms that our algorithms for
computing the first and second derivatives are highly effective. The errors
are primarily localized at the endpoints of the interval, whereas the computed
function demonstrates noteworthy accuracy within the subinterval $(-2,2)$.
Detailed information can be found in Table 2.

| $\frac{\|f^{\prime}_{\rm true}-f^{\prime}_{\rm comp}\|_{L^{2}(-3,3)}}{\|f^{\prime}_{\rm true}\|_{L^{2}(-3,3)}}$ | $\frac{\|f^{\prime\prime}_{\rm true}-f^{\prime\prime}_{\rm comp}\|_{L^{2}(-3,3)}}{\|f^{\prime\prime}_{\rm true}\|_{L^{2}(-3,3)}}$ | $\frac{\|f^{\prime}_{\rm true}-f^{\prime}_{\rm comp}\|_{L^{2}(-2,2)}}{\|f^{\prime}_{\rm true}\|_{L^{2}(-2,2)}}$ | $\frac{\|f^{\prime\prime}_{\rm true}-f^{\prime\prime}_{\rm comp}\|_{L^{2}(-2,2)}}{\|f^{\prime\prime}_{\rm true}\|_{L^{2}(-2,2)}}$
---|---|---|---|---
$\delta=0.05$ | 0.0052 | 0.0380 | 0.0017 | 0.0309
$\delta=0.10$ | 0.0074 | 0.0955 | 0.0047 | 0.0484
$\delta=0.20$ | 0.0240 | 0.1734 | 0.0117 | 0.0704
Table 2:  Test 2. The computed errors with respect to the $L^{2}$ norms over
the intervals $(-3,3)$ and $(-2,2)$. It is apparent that the relative errors
are below the noise level.

###  3.3 The case of two dimensions

Our computation involves setting $\Omega=(-R,R)^{2}$, where $R=3$. Similar to
the one-dimensional case, we implement Algorithm 1 in the finite difference
scheme. To define our grid, we set

$\mathcal{G}=\big{\\{}{\bf x}_{ij}=(x_{i}=-R+(i-1)h,y_{j}=-R+(j-1)h:1\leq
i,j\leq N_{{\bf x}}\big{\\}}$

where $N_{\bf x}=601$ and $h=2R/(N_{\bf x}-1)=0.01$. We choose the cut-off
numbers $N_{1}$ and $N_{2}$ using the same strategy as in Section 4.1, i.e.,
we find $N_{1}$ and $N_{2}$ such that the approximation in (2.2) is
satisfactory. For both tests presented below, we set $N_{1}=N_{2}=20$.

####  3.3.1 Test 3

In this test, we take $f^{*}(x,y)=\sin(x^{2}+y^{2})$. Then

$\displaystyle|\nabla f^{*}(x,y)|$
$\displaystyle=2\sqrt{(x^{2}+y^{2})\cos^{2}(x^{2}+y^{2})},$
$\displaystyle\Delta f^{*}(x,y)$
$\displaystyle=4\cos(x^{2}+y^{2})-4x^{2}\sin(x^{2}+y^{2})-4y^{2}\sin(x^{2}+y^{2}).$

In Figure 4, we show the true and computed magnitudes of the gradient,
$|\nabla f^{*}|$, and the Laplacian, $\Delta f^{*}$, are depicted using data
that has been affected by a 10% noise level.

(a) The true function $|\nabla f^{*}|$

(b) The computed function $|\nabla f_{\rm comp}|$

(c) $|\nabla f^{*}-\nabla f_{\rm comp}|/\|\nabla f^{*}\|_{L^{\infty}}$

(d) The true function $\Delta f^{*}$

(e) The computed function $\Delta f_{\rm comp}$

(f) $|\Delta f^{*}-\Delta f_{\rm comp}|/\|\Delta f^{*}\|_{L^{\infty}}$

Figure 4:  Test 3. The true and computed $|\nabla f|$ and $\Delta f$, using
data that has been corrupted with a 10% noise level.

It follows from Figure 4 that we successfully compute the first and second
derivatives of the function $f^{*}(x,y)=\sin(x^{2}+y^{2}).$ It is interesting
to mention that the errors in the computation are less than the noise level.
As seen in the last column of Figures 4c and 4f, the computed errors occur
mainly on the boundary of the computed domain. This feature is true when we
test our algorithm with up to the noise level 20%.

| $\frac{\|\nabla f_{\rm true}-\nabla f_{\rm comp}\|_{L^{2}(\Omega)}}{\|\nabla f_{\rm true}\|_{L^{2}(\Omega)}}$ | $\frac{\|\Delta f_{\rm true}-\Delta f_{\rm comp}\|_{L^{2}(\Omega)}}{\|\Delta f_{\rm true}\|_{L^{2}(\Omega)}}$ | $\frac{\|\nabla f_{\rm true}-\nabla f_{\rm comp}\|_{L^{2}(\Omega^{\prime})}}{\|\nabla f_{\rm true}\|_{L^{2}(\Omega^{\prime})}}$ | $\frac{\|\Delta f_{\rm true}-\Delta f_{\rm comp}\|_{L^{2}(\Omega^{\prime})}}{\|\Delta f_{\rm true}\|_{L^{2}(\Omega^{\prime})}}$
---|---|---|---|---
$\delta=0.05$ | 0.0303 | 0.1282 | 0.0163 | 0.0320
$\delta=0.10$ | 0.0313 | 0.1306 | 0.0165 | 0.0324
$\delta=0.20$ | 0.0338 | 0.1610 | 0.0173 | 0.0337
Table 3:  Test 3. The relative computed errors with respect to the $L^{2}$
norms on $\Omega=(-3,3)^{2}$ and $\Omega^{\prime}=(-2,2)^{2}$. As can be
observed, the relative errors are lower than the noise level.

The performance of our method with different noise levels
$\delta\in\\{5\%,10\%,20\%\\}$ is out of expectation. Table 3 shows that the
relative computed errors are consistent with the corresponding noise levels.
The relative error with respect to the $L^{2}(\Omega^{\prime})$ norm is
significantly low.

####  3.3.2 Test 2

We test our algorithms by computing derivatives of
$f^{*}(x,y)=x^{3}\sin(y^{2}).$ As in Test 2.1, we will compute numerical
versions of the functions

$\displaystyle|\nabla f^{*}(x,y)|$
$\displaystyle=\sqrt{9x^{4}\sin^{2}(y^{2})+4x^{6}y^{2}\cos^{2}(y^{2})}$
$\displaystyle\Delta f^{*}(x,y)$
$\displaystyle=(-4x^{3}y^{2}+6x)\sin(y^{2})+2x^{3}\cos(y^{2}).$

The numerical results are displayed in Figure 5.

(a) The true function $|\nabla f^{*}|$

(b) The computed function $|\nabla f_{\rm comp}|$

(c) $|\nabla f^{*}-\nabla f_{\rm comp}|/\|\nabla f^{*}\|_{L^{\infty}}$

(d) The true function $\Delta f^{*}$

(e) The computed function $\Delta f_{\rm comp}$

(f) $|\Delta f^{*}-\Delta f_{\rm comp}|/\|\Delta f^{*}\|_{L^{\infty}}$

Figure 5:  Test 4. The true and computed $|\nabla f|$ and $\Delta f$, using
data that has been corrupted with a 10% noise level.

Like Test 3, it is evident from Figure 5 and Table 4 that Algorithm 1 provides
out-of-expectation numerical results for the first and second derivatives of
the function $f^{*}$ with acceptable relative errors.

| $\frac{\|\nabla f_{\rm true}-\nabla f_{\rm comp}\|_{L^{2}(\Omega)}}{\|\nabla f_{\rm true}\|_{L^{2}(\Omega)}}$ | $\frac{\|\Delta f_{\rm true}-\Delta f_{\rm comp}\|_{L^{2}(\Omega)}}{\|\Delta f_{\rm true}\|_{L^{2}(\Omega)}}$ | $\frac{\|\nabla f_{\rm true}-\nabla f_{\rm comp}\|_{L^{2}(\Omega^{\prime})}}{\|\nabla f_{\rm true}\|_{L^{2}(\Omega^{\prime})}}$ | $\frac{\|\Delta f_{\rm true}-\Delta f_{\rm comp}\|_{L^{2}(\Omega^{\prime})}}{\|\Delta f_{\rm true}\|_{L^{2}(\Omega^{\prime})}}$
---|---|---|---|---
$\delta=0.05$ | 0.0336 | 0.1981 | 0.0128 | 0.0587
$\delta=0.10$ | 0.0386 | 0.2301 | 0.0142 | 0.0645
$\delta=0.20$ | 0.0571 | 0.3666 | 0.0154 | 0.0734
Table 4:  Test 4. The relative computed errors with respect to the $L^{2}$
norms on $\Omega=(-3,3)^{2}$ and $\Omega^{\prime}=(-2,2)^{2}$. As can be
observed, the relative errors are lower than the noise level.

##  4 Comparison with some existing differentiating methods

In this section, we compare the efficiency of Algorithm 1 with some other
widely-used methods for differentiation. We brevity, we only implement and
present the computation of these methods in one dimension.

###  4.1 Fourier expansion with the trigonometric basis

If we substitute the polynomial-exponential basis with the trigonometric basis
in Algorithm 1, what would be the outcome? Let $N_{\rm trig}>0$ be a cut-off
number. Write

$f^{\delta}(x)\simeq f_{\rm trig}^{\delta}(x)=a_{0}+\sum_{n=1}^{N_{\rm
trig}}a_{n}\cos\Big{(}\frac{\pi nx}{R}\Big{)}+\sum_{n=1}^{N_{\rm
trig}}b_{n}\sin\Big{(}\frac{n\pi x}{R}\Big{)}$ (4.1)

where

$\displaystyle a_{0}$
$\displaystyle=\frac{1}{2R}\int_{-R}^{R}f^{\delta}(s)ds,$ $\displaystyle
a_{n}$
$\displaystyle=\frac{1}{R}\int_{-R}^{R}f^{\delta}(s)\cos\Big{(}\frac{\pi
ns}{R}\Big{)}ds,\quad n\geq 1,$ $\displaystyle b_{n}$
$\displaystyle=\frac{1}{R}\int_{-R}^{R}f^{\delta}(s)\sin\Big{(}\frac{\pi
ns}{R}\Big{)}ds,\quad n\geq 1.$

Like in Section 3.1, we choose the optimal cut-off number $N_{\rm trig}$ using
the following formula

$N_{\rm trig}=\underset{3\leq N\leq 25}{\rm
argmin}\Big{\\{}\|f^{\delta}-\Big{[}a_{0}+\sum_{n=1}^{N}a_{n}\cos\Big{(}\frac{\pi
nx}{R}\Big{)}+\sum_{n=1}^{N}b_{n}\sin\Big{(}\frac{n\pi
x}{R}\Big{)}\Big{]}\|_{L^{\infty}(-R,R)}\Big{\\}}.$ (4.2)

The range $3\leq N\leq 25$ in (4.2) can be changed. However, we observe that
when $N$ exceeds 25, the numerical results get worse. Using (4.1), we
approximate ${f^{*}}^{\prime}$ via the formula

$f_{\rm trig}^{\prime}(x)\simeq-\sum_{n=1}^{N_{\rm trig}}\frac{\pi
na_{n}}{R}\sin\Big{(}\frac{\pi nx}{R}\Big{)}+\sum_{n=1}^{N_{\rm
trig}}\frac{n\pi b_{n}}{R}\cos\Big{(}\frac{n\pi x}{R}\Big{)}.$ (4.3)

We also can approximate ${f^{*}}^{\prime\prime}$ via

$f_{\rm trig}^{\prime\prime}(x)=-\sum_{n=1}^{N_{\rm trig}}\Big{(}\frac{\pi
n}{R}\Big{)}^{2}a_{n}\cos\Big{(}\frac{\pi nx}{R}\Big{)}-\sum_{n=1}^{N_{\rm
trig}}\Big{(}\frac{\pi n}{R}\Big{)}^{2}b_{n}\sin\Big{(}\frac{n\pi
x}{R}\Big{)}.$ (4.4)

In rows 3 of Table 5 and Table 6, we present the relative errors of the method
utilizing (4.3) and (4.4) with respect to the $L^{2}(-3,3)$ norm. The
experiment employs data with 5%, 10%, and 20% noise components. The comparison
of these results and those via Algorithm 1 in rows 2 and 5 reveals that, in
terms of accuracy, the polynomial-exponential basis outperforms the
trigonometric basis. We conclude that the use of the polynomial-exponential
basis is crucial to the success of our approach.

###  4.2 Comparison with the Tikhonov regularization method

A widely used approach to differentiate the data is to employ the Tikhonov
optimization. Define $u=f^{\prime}$. By the fundamental theorem of calculus,
we write

$f^{\delta}(x)-f^{\delta}(-R)=\int_{-R}^{x}u(s)ds.$

This suggests us to find $u$ by minimizing the following Tikhonov cost
functional

$J_{\gamma}(u)=\int_{-R}^{R}\Big{|}\int_{-R}^{x}u(s)ds-[f^{\delta}(x)-f^{\delta}(-R)]\Big{|}^{2}dx+\gamma\|u\|_{L^{2}(-R,R)}^{2}$

where $\gamma>0$ is a regularization parameter. The term
$\gamma\|u\|_{L^{2}(-R,R)}^{2}$ is called the regularization term. It is
possible to employ higher-order norms, such as $H^{1}$ and $H^{2}$, instead of
the $L^{2}$ norm for the regularization term. The derivative ${f^{\delta}_{\rm
Tik}}^{\prime}$ is determined to be $u^{\gamma}_{\rm min}$, which is the
minimizer of $J_{\gamma}$. We compute the second derivative of $f$, denoted by
${f^{\delta}_{\rm Tik}}^{\prime\prime}$, by differentiating ${f^{\delta}_{\rm
Tik}}^{\prime}$ using the Tikhonov optimization approach again. While the
Tikhonov regularization approach is known for its robustness, selecting the
appropriate norm and regularization parameter is not trivial. A popular
approach to selecting the regularization parameter is Morosov’s discrepancy
principle [18], in which the regularization parameter $\gamma$ is determined
such that

$\Big{\|}\int_{-R}^{x}u^{\gamma}_{\rm
min}(s)ds-[f(x)-f(-R)]\Big{\|}_{L^{2}(-R,R)}=O(\delta)$ (4.5)

where $\delta$ is the noise level. Morosov’s discrepancy method requires
knowledge of the noise level, which is not always known in practical
applications. The $L-$shape method is a good option to find $\gamma$. One
sketches the graph of the function $l:(0,1)\to\mathbb{R}$ defined as

$l(\gamma)=\Big{\|}\int_{-R}^{x}u^{\gamma}_{\rm
min}(s)ds-[f(x)-f(-R)]\Big{\|}_{L^{2}(-R,R)}^{2}.$

The graph of $l$ is an $L$-shape curve, see Figure 6. The optimal
regularization parameter is determined by the horizontal coordinate of the
corner of the $L$ curve. We show in row 4 and row 8 of Table 5 the relative
computing error using the Tikhonov regularization method, in which we use the
$L$-shape method to choose the parameter $\gamma.$ Comparing the relative
errors in row 2 and row 6 of this Table, we conclude that our method performs
better than the Tikhonov optimization method.

(a) The graph of the function $l(\gamma)$, $\gamma\in(10^{-5},10^{-2})$,
computed by 5% noisy data taken in Test 1

(b) The graph of the function $l(\gamma)$, $\gamma\in(10^{-5},10^{-2})$,
computed by 5% noisy data taken in Test 2

Figure 6: The $L$-shape behavior of the function $l$. The optimal
regularization $\gamma$ occurs at the corner of the graph.

######  Remark 4.1.

Since we need to compute $l(\gamma)$, we have to repeatedly attempt to
minimize $J_{\gamma}$ for each value of $\gamma$, which makes the
optimization-based method time-consuming. In the conducted experiments, we
utilized an iMac 3.2 GHz Quad-Core Intel Core I5 to evaluate $l(\gamma)$ on
uniformly partitioning the interval $(10^{-5},10^{-2})$ with a step size of
$5\times 10^{-4}$. The computation took 93.85 seconds. In contrast, the same
computer required just 0.01167 seconds to compute both the first and second
derivatives of the function in each of Test 1 and Test 2. Thus, our method is
considerably faster.

###  4.3 Comparison with the method based on cubic spline

One can apply cubic spline curves, introduced in [21, 22, 24], to smooth data
before differentiating it. Define a partition
$\\{x_{i}=-R+(i-1)h,i=1,2,\dots,N\\}$ of the computational interval $(-R,R)$
similarly to the partition in (3.2). The difference between this partition and
the one in (3.2) is that we change the step size to $h=0.1$ because the cubic
spline method works better with sparse data. Then, we use the ”spline” command
in Matlab to construct a set of spline curves that fit the data $f^{\delta}$.
The command spline provides the coefficients of each cubic function in each
subdomain $[x_{i},x_{i+1}]$, $i\in\\{1,\dots,N_{x}-1\\}$, that allows us to
compute the first and second derivatives of the function $f^{\delta}.$

To evaluate the performance of the cubic spline method, we show the relative
error in computation in rows 5 of Table 5 and Table 6. Our experiment reveals
that this method is well-suited for computing the first derivative; however,
it may lead to a large computation error when computing the second derivative.
A comparison of the first and final columns of the aforementioned tables leads
us to the conclusion that our method yields markedly more accurate results.

###  4.4 Numerical results

In Figure 7, we show the graphs of the following functions

$\begin{array}[]{cc}\displaystyle{\rm err}_{\rm Trig}(x)=\frac{|f_{\rm
Trig}^{\prime}(x)-f_{\rm true}^{\prime}(x)|}{\|f_{\rm
true}^{\prime}\|_{L^{\infty}(-3,3)}},&\displaystyle{\rm err}_{\rm
Tik}(x)=\frac{|f_{\rm Tik}^{\prime}(x)-f_{\rm true}^{\prime}(x)|}{\|f_{\rm
true}^{\prime}\|_{L^{\infty}(-3,3)}},\\\ \displaystyle{\rm err}_{\rm
Cub}(x)=\frac{|f_{\rm Cub}^{\prime}(x)-f_{\rm true}^{\prime}(x)|}{\|f_{\rm
true}^{\prime}\|_{L^{\infty}(-3,3)}},&\displaystyle{\rm err}_{\rm
comp}(x)=\frac{|f_{\rm comp}^{\prime}(x)-f_{\rm true}^{\prime}(x)|}{\|f_{\rm
true}^{\prime}\|_{L^{\infty}(-3,3)}}\end{array}$ (4.6)

where $f_{\rm Trig}^{\prime}$, $f_{\rm Tik}^{\prime}$, $f_{\rm Cub}^{\prime}$,
and $f_{\rm comp}^{\prime}$ are the computed first derivatives via the methods
in Sections 4.1, 4.2, 4.3, and 2, respectively. The data is taken from Test 1
and Test 2 in Section 4.1 when the noise level are 5%, 10%, and 20%. We do not
show similar graphs for the computed derivatives since the methods mentions in
Sections 4.1, 4.2, and 4.3 are not accurate, see Table 5. It is evident from
Figure 7 that our method performs better than the methods mentioned.

(a) Test 1; noise level $\delta=5\%$

(b) Test 1; noise level $\delta=10\%$

(c) Test 1; noise level $\delta=20\%$

(d) Test 2; noise level $\delta=5\%$

(e) Test 2; noise level $\delta=10\%$

(f) Test 2; noise level $\delta=20\%$

Figure 7:  The relative difference of the true and computed first derivatives of the functions in Test 1 and Test 2. These relative difference functions are defined in (4.6) for $x\in(-3,3)$. | Test 1 | Test 1 | Test 1 | Test 2 | Test 2 | Test 2
---|---|---|---|---|---|---
| $\delta=0.05$ | $\delta=0.10$ | $\delta=0.20$ | $\delta=0.05$ | $\delta=0.10$ | $\delta=0.20$
$\frac{\|f^{\prime}_{\rm true}-f^{\prime}_{\rm comp}\|_{L^{2}(-3,3)}}{\|f^{\prime}_{\rm true}\|_{L^{2}(-3,3)}}$ | 0.0060 | 0.0110 | 0.0260 | 0.0017 | 0.0047 | 0.0117
$\frac{\|f^{\prime}_{\rm true}-f^{\prime}_{\rm trig}\|_{L^{2}(-3,3)}}{\|f^{\prime}_{\rm true}\|_{L^{2}(-3,3)}}$ | 0.4157 | 0.4397 | 0.4485 | 0.2216 | 0.2219 | 0.2260
$\frac{\|f^{\prime}_{\rm true}-f^{\prime}_{\rm Tik}\|_{L^{2}(-3,3)}}{\|f^{\prime}_{\rm true}\|_{L^{2}(-3,3)}}$ | 0.0652 | 0.0879 | 0.1484 | 0.1115 | 0.1248 | 0.1780
$\frac{\|f^{\prime}_{\rm true}-f^{\prime}_{\rm cub}\|_{L^{2}(-3,3)}}{\|f^{\prime}_{\rm true}\|_{L^{2}(-3,3)}}$ | 0.0775 | 0.1185 | 0.2450 | 0.0551 | 0.1904 | 0.2355
Table 5:  The relative errors in computing the first derivatives of our method and several other approaches are evaluated with respect to the $L^{2}(-3,3)$ norm. In this table, $f^{\prime}_{\rm true}$ is the true first derivative that we aim to approximate. The function $f^{\prime}_{\rm comp}$ is the first derivative computed by our approach. The functions $f^{\prime}_{\rm trig}$, $f^{\prime}_{\rm Tik}$ and $f^{\prime}_{\rm cub}$ are the derivative computed by the existing methods reviewed in Sections 4.1, 4.2, and 4.3 respectively. | Test 1 | Test 1 | Test 1 | Test 2 | Test 2 | Test 2
---|---|---|---|---|---|---
| $\delta=0.05$ | $\delta=0.10$ | $\delta=0.20$ | $\delta=0.05$ | $\delta=0.10$ | $\delta=0.20$
$\frac{\|f^{\prime\prime}_{\rm true}-f^{\prime\prime}_{\rm comp}\|_{L^{2}(-3,3)}}{\|f^{\prime\prime}_{\rm true}\|_{L^{2}(-3,3)}}$ | 0.0268 | 0.0996 | 0.1123 | 0.0380 | 0.0955 | 0.1734
$\frac{\|f^{\prime\prime}_{\rm true}-f^{\prime\prime}_{\rm trig}\|_{L^{2}(-3,3)}}{\|f^{\prime\prime}_{\rm true}\|_{L^{2}(-3,3)}}$ | 1.2419 | 1.4411 | 1.5455 | 1.0224 | 1.0314 | 1.0674
$\frac{\|f^{\prime\prime}_{\rm true}-f^{\prime\prime}_{\rm Tik}\|_{L^{2}(-3,3)}}{\|f^{\prime\prime}_{\rm true}\|_{L^{2}(-3,3)}}$ | 0.3410 | 0.4504 | 0.6334 | 0.5912 | 0.6044 | 0.6700
$\frac{\|f^{\prime}_{\rm true}-f^{\prime\prime}_{\rm cub}\|_{L^{2}(-3,3)}}{\|f^{\prime\prime}_{\rm true}\|_{L^{2}(-3,3)}}$ | 0.5406 | 0.6970 | 1.2402 | 0.5118 | 0.7455 | 1.0360
Table 6:  The relative errors in computing the second derivatives of our
method and several other approaches are evaluated with respect to the
$L^{2}(-3,3)$ norm. In this table, $f^{\prime\prime}_{\rm true}$ is the true
second derivative that we aim to approximate. The function
$f^{\prime\prime}_{\rm comp}$ is the second derivative computed by our
approach. The functions $f^{\prime\prime}_{\rm trig}$, $f^{\prime\prime}_{\rm
Tik}$ and $f^{\prime\prime}_{\rm cub}$ are the derivative computed by the
existing methods reviewed in Sections 4.1, 4.2, and 4.3 respectively.

We also show in Table 5 and Table 6 the relative computational errors with
respect to the $L^{2}(-3,3)$ norm. Based on the information in Table 5 and
Table 6, we can infer that our approach is the most precise one. The relative
errors in computing the first derivative are roughly ten times lower than the
noise levels, while the other methods have relative errors that are consistent
with the noise levels. Additionally, our method’s relative errors in computing
second derivatives are in line with the noise levels, whereas other methods’
relative errors in computing second derivatives are not satisfactory.

##  5 Concluding remarks

We introduce a technique to compute derivatives of data affected by noise,
which can be difficult due to the potential for significant computation errors
even from a small amount of noise. Our method is straightforward. Firstly, we
represent the data by its Fourier series with respect to the polynomial-
exponential basis. Then, we remove all high-frequency components by truncating
this series. The desired derivatives are then obtained directly. To
demonstrate the efficacy of our algorithm, we provide numerical examples in
both one and two dimensions. Furthermore, we compare our approach with some
commonly used methods and conclude that our method is more precise.

## References

  * [1] K. Ahnert and L. A. Segel.  Numerical differentiation of experimental data: local versus global methods.  Computer Physics Communications, 177:764–774, 2007.
  * [2] F. V. Breugel, J. N. Kutz, and B. W. Brunton.  Numerical differentiation of noisy data: A unifying multi-objective optimization framework.  IEEE Access, 8:196865–196877, 2020.
  * [3] H. W. Engl, M. Hanke, and A. Neubauer.  Regularization of Inverse Problems, Mathematics and its Applications.  Kluwer Academic Publishers Group, Dordrecht, 1996.
  * [4] K. O. Friedrichs.  The identity of weak and strong extensions of differential operators.  Trans. Amer. Math. Soc., 55:132–151, 1944.
  * [5] C. W. Groetsch.  Differentiation of approximately specified functions.  Am. Math. Mon., 98:847–850, 1991.
  * [6] M. Hanke and O. Sherzer.  Inverse problems light numerical differentiation.  Am. Math. Mon., 108:512–521, 2001.
  * [7] V. A. Khoa, G. W. Bidney, M. V. Klibanov, L. H. Nguyen, L. Nguyen, A. Sullivan, and V. N. Astratov.  Convexification and experimental data for a 3D inverse scattering problem with the moving point source.  Inverse Problems, 36:085007, 2020.
  * [8] V. A. Khoa, G. W. Bidney, M. V. Klibanov, L. H. Nguyen, L. Nguyen, A. Sullivan, and V. N. Astratov.  An inverse problem of a simultaneous reconstruction of the dielectric constant and conductivity from experimental backscattering data.  Inverse Problems in Science and Engineering, 29(5):712–735, 2021\.
  * [9] V. A. Khoa, M. V. Klibanov, and L. H. Nguyen.  Convexification for a 3D inverse scattering problem with the moving point source.  SIAM J. Imaging Sci., 13(2):871–904, 2020.
  * [10] M. V. Klibanov.  Convexification of restricted Dirichlet to Neumann map.  J. Inverse and Ill-Posed Problems, 25(5):669–685, 2017.
  * [11] M. V. Klibanov, T. T. Le, and L. H. Nguyen.  Convergent numerical method for a linearized travel time tomography problem with incomplete data.  SIAM Journal on Scientific Computing, 42:B1173–B1192, 2020.
  * [12] M. V. Klibanov and J. Li.  Inverse Problems and Carleman Estimates: Global Uniqueness, Global Convergence and Experimental Data.  De Gruyter, 2021.
  * [13] M. V. Klibanov and L. H. Nguyen.  PDE-based numerical method for a limited angle X-ray tomography.  Inverse Problems, 35:045009, 2019.
  * [14] M. V. Klibanov and A. Timonov.  A comparative study of two globally convergent numerical methods for acoustic tomography.  Communications in Analysis and Computation, 1:12–31, 2023.
  * [15] I. Knowles and R. J. Renka.  Methods for numerical differentiation of noisy data.  Elect. J. Diff. Equations, Conference 21:235–246, 2014.
  * [16] I. Knowles and R. Wallace.  A variational method for numerical differentiation.  Numer. Math., 70:91–110, 1995.
  * [17] T. T. Le and L. H. Nguyen.  The gradient descent method for the convexification to solve boundary value problems of quasi-linear PDEs and a coefficient inverse problem.  Journal of Scientific Computing, 91(3):74, 2022.
  * [18] V. A. Mozorov.  Methods for solving incorrectly posed problems.  Springer Verlag, New York, 1984.
  * [19] R. Ramlau.  Morozov’s discrepancy principle for Tikhonov regularization of nonlinear operators.  Journal for Numer. Funct. Anal. and Opt., 23:147–172, 2002.
  * [20] A. G. Ramm and A. B. Smirnova.  On stable numerical differentiation.  Math. Comp., 70:1131–1153, 2001.
  * [21] C. H. Reinsch.  Smoothing by spline functions.  Numer. Math., 10:177–183, 1967.
  * [22] C. H. Reinsch.  Smoothing by spline functions. II.  Numer. Math., 16:451–454, 1971.
  * [23] O. Scherzer.  The use of Morozov’s discrepancy principle for Tikhonov regularization for solving non-linear ill-posed problems.  SIAM J. Numer. Anal., 30:1796–1838, 1993.
  * [24] I. J. Schoenberg.  Spline functions and the problem of graduation.  Proc. Amer. Math. Soc., 52:497–950, 1964.