2010371-382Nancy, France 371

Jiří Fiala

Marcin Kamiński

Bernard Lidický

Daniël Paulusma

# The $k$-in-a-path problem for claw-free graphs

J. Fiala  Charles University, Faculty of Mathematics and Physics,
DIMATIA and Institute for Theoretical Computer Science (ITI)
Malostranské nám. 2/25, 118 00, Prague, Czech Republic<EMAIL_ADDRESS><EMAIL_ADDRESS>,  M. Kamiński  Computer Science Department,
Université Libre de Bruxelles,
Boulevard du Triomphe CP212, B-1050 Brussels, Belgium
<EMAIL_ADDRESS>,  B. Lidický  and  D. Paulusma  Department of
Computer Science, University of Durham,
Science Laboratories, South Road,
Durham DH1 3LE, England<EMAIL_ADDRESS>
###### Abstract.

Testing whether there is an induced path in a graph spanning $k$ given
vertices is already NP-complete in general graphs when $k=3$. We show how to
solve this problem in polynomial time on claw-free graphs, when $k$ is not
part of the input but an arbitrarily fixed integer.

###### Key words and phrases:

induced path, claw-free graph, polynomial-time algorithm

###### 1991 Mathematics Subject Classification:

G.2.2 Graph algorithms, F.2.2 Computations on discrete structures

Research supported by the Ministry of Education of the Czech Republic as
projects 1M0021620808
and GACR 201/09/0197, by the Royal Society Joint Project Grant JP090172 and by
EPSRC as EP/D053633/1.

##  1\. Introduction

Many interesting graph classes are closed under vertex deletion. Every such
class can be characterized by a set of forbidden induced subgraphs. One of the
best-known examples is the class of perfect graphs. A little over 40 years
after Berge’s conjecture, Chudnovsky et al. [18] proved that a graph is
perfect if and only if it contains neither an odd hole (induced cycle of odd
length) nor an odd antihole (complement of an odd hole). This motivates the
research of detecting induced subgraphs such as paths and cycles, which is the
topic of this paper. To be more precise, we specify some vertices of a graph
called the terminals and study the computational complexity of deciding if a
graph has an induced subgraph of a certain type containing all the terminals.
In particular, we focus on the following problem.

$k$-in-a-Path
Instance: a graph $G$ with $k$ terminals.
Question: does there exist an induced path of $G$ containing the $k$
terminals?

Note that in the problem above, $k$ is a fixed integer. Clearly, the problem
is polynomially solvable for $k=2$. Haas and Hoffmann [11] consider the case
$k=3$. After pointing out that this case is NP-complete as a consequence of a
result by Fellows [9], they prove W$[1]$-completeness (where they take as
parameter the length of an induced path that is a solution for $3$-in-a-Path).
Derhy and Picouleau [6] proved that the case $k=3$ is NP-complete even for
graphs with maximum degree at most three.

A natural question is what will happen if we relax the condition of “being
contained in an induced path” to “being contained in an induced tree”. This
leads to the following problem.

$k$-in-a-Tree
Instance: a graph $G$ with $k$ terminals.
Question: does there exist an induced tree of $G$ containing the $k$
terminals?

As we will see, also this problem has received a lot of attention in the last
two years. It is NP-complete if $k$ is part of the input [6]. However,
Chudnovsky and Seymour [4] have recently given a deep and complicated
polynomial-time algorithm for the case $k=3$.

######  Theorem 1.1 ([4]).

The $3$-in-a-Tree problem is solvable in polynomial time.

The computational complexity of $k$-in-a-Tree for $k=4$ is still open. So far,
only partial results are known, such as a polynomial-time algorithm for $k=4$
when the input is triangle-free by Derhy, Picouleau and Trotignon [7]. This
result and Theorem 1.1 were extended by Trotignon and Wei [20] who showed that
$k$-in-a-Tree is polynomially solvable for graphs of girth at least $k$. The
authors of [7] also show that it is NP-complete to decide if a graph $G$
contains an induced tree $T$ covering four specified vertices such that $T$
has at most one vertex of degree at least three.

In general, $k$-in-a-Path and $k$-in-a-Tree are only equivalent for $k\leq 2$.
However, in this paper, we study claw-free graphs (graphs with no induced
4-vertex star). Claw-free graphs are a rich and well-studied class containing,
e.g., the class of (quasi)-line graphs and the class of complements of
triangle-free graphs; see [8] for a survey. Notice that any induced tree in a
claw-free graph is in fact an induced path.

The $k$-in-a-Path and $k$-in-a-Tree problem are equivalent for the class of
claw-free graphs.

Motivation. The polynomial-time algorithm for 3-in-a-Tree [4] has already
proven to be a powerful tool for several problems. For instance, it is used as
a subroutine in polynomial time algorithms for detecting induced thetas and
pyramids [4] and several other induced subgraphs [16]. The authors of [12] use
it to solve the Parity Path problem in polynomial time for claw-free graphs.
(This problem is to test if a graph contains both an odd and even length
induced paths between two specified vertices. It is NP-complete in general as
shown by Bienstock [1].)

Lévêque et al. [16] use the algorithm of [4] to solve the $2$-Induced Cycle
problem in polynomial time for graphs not containing an induced path or
subdivided claw on some fixed number of vertices. The $k$-Induced Cycle
problem is to test if a graph contains an induced cycle spanning $k$
terminals. In general it is NP-complete already for $k=2$ [1]. For fixed $k$,
an instance of this problem can be reduced to a polynomial number of instances
of the $k$-Induced Disjoint Paths problem, which we define below. Paths
$P_{1},\ldots,P_{k}$ in a graph $G$ are said to be mutually induced if for any
$1\leq i<j\leq k$, $P_{i}$ and $P_{j}$ have neither common vertices (i.e.
$V(P_{i})\cap V(P_{j})=\emptyset$) nor adjacent vertices (i.e. $uv\notin E$
for any $u\in V(P_{i}),v\in V(P_{j})$).

$k$-Induced Disjoint Paths
Instance: a graph $G$ with $k$ pairs of terminals $(s_{i},t_{i})$ for
$i=1,\ldots,k$.
Question: does $G$ contain $k$ mutually induced paths $P_{i}$ such that
$P_{i}$ connects $s_{i}$ and $t_{i}$ for $i=1,\ldots,k$?

This problem is NP-complete for $k=2$ [1]. Kawarabayashi and Kobayashi [14]
showed that, for any fixed $k$, the $k$-Induced Disjoint Paths problem is
solvable in linear time on planar graphs and that consequently $k$-Induced
Disjoint Cycle is solvable in polynomial time on this graph class for any
fixed $k$. In [15], Kawarabayashi and Kobayashi improve the latter result by
presenting a linear time algorithm for this problem, and even extend the
results for both these problems to graphs of bounded genus. As we shall see,
we can also solve $k$-Induced Disjoint Paths and $k$-Induced Cycle in
polynomial time in claw-free graphs. The version of the problem in which any
two paths are vertex-disjoint but may have adjacent vertices is called the
$k$-Disjoint Paths problem. For this problem Robertson and Seymour [17] proved
the following result.

######  Theorem 1.2 ([17]).

For fixed $k$, the $k$-Disjoint Paths problem is solvable in polynomial time.

Our Results and Paper Organization. In Section 2 we define some basic
terminology. Section 3 contains our main result: $k$-in-a-Path is solvable in
polynomial time in claw-free graphs for any fixed integer $k$. This, in fact,
follows from a stronger theorem proved in Section 4; the problem is solvable
in polynomial time even if the terminals are to appear on the path in a fixed
order. A consequence of our result is that the $k$-Induced Disjoint Paths and
$k$-Induced Cycle problems are polynomially solvable in claw-free graphs for
any fixed integer $k$. In Section 4 we present our polynomial-time algorithm
that solves the ordered version of $k$-in-a-Path. The algorithm first performs
“cleaning of the graph”. This is an operation introduced in [12]. After
cleaning the graph is free of odd antiholes of length at least seven. Next we
treat odd holes of length five that are contained in the neighborhood of a
vertex. The resulting graph is quasi-line. Finally, we solve the problem using
a recent characterization of quasi-line graphs by Chudnovsky and Seymour [3]
and related algorithmic results of King and Reed [13]. In Section 5 we mention
relevant open problems.

##  2\. Preliminaries

All graphs in this paper are undirected, finite, and neither have loops nor
multiple edges. Let $G$ be a graph. We refer to the vertex set and edge set of
$G$ by $V=V(G)$ and $E=E(G)$, respectively. The neighborhood of a vertex $u$
in $G$ is denoted by $N_{G}(u)=\\{v\in V\ |\ uv\in E\\}$. The subgraph of $G$
induced by $U\subseteq V$ is denoted $G[U]$. Analogously, the neighborhood of
a set $U\subseteq V$ is $N(U):=\bigcup_{u\in U}N(u)\setminus U$. We say that
two vertex-disjoint subsets of $V$ are adjacent if some of their vertices are
adjacent. The distance $d(u,v)$ between two vertices $u$ and $v$ in $G$ is the
number of edges on a shortest path between them. The edge contraction of an
edge $e=uv$ removes its two end vertices $u,v$ and replaces it by a new vertex
adjacent to all vertices in $N(u)\cup N(v)$ (without introducing loops or
multiple edges).

We denote the path and cycle on $n$ vertices by $P_{n}$ and $C_{n}$,
respectively. Let $P=v_{1}v_{2}\ldots v_{p}$ be a path with a fixed
orientation. The successor $v_{i+1}$ of $v_{i}$ is denoted by $v_{i}^{+}$ and
its predecessor $v_{i-1}$ by $v_{i}^{-}$. The segment $v_{i}v_{i+1}\ldots
v_{j}$ is denoted by $v_{i}\overrightarrow{P}v_{j}$. The converse segment
$v_{j}v_{j-1}\ldots v_{i}$ is denoted by $v_{j}\overleftarrow{P}v_{i}$.

A hole is an induced cycle of length at least 4 and an antihole is the
complement of a hole. We say that a hole is odd if it has an odd number of
edges. An antihole is called odd if it is the complement is an odd hole.

A claw is the graph $(\\{x,a,b,c\\},\\{xa,xb,xc\\})$, where vertex $x$ is
called the center of the claw. A graph is claw-free if it does not contain a
claw as an induced subgraph. A _clique_ is a subgraph isomorphic to a complete
graph. A diamond is a graph obtain from a clique on four vertices after
removing one edge. A vertex $u$ in a graph $G$ is simplicial if $G[N(u)]$ is a
clique.

Let $s$ and $t$ be two specified vertices in a graph $G=(V,E)$. A vertex $v\in
V$ is called irrelevant for vertices $s$ and $t$ if $v$ does not lie on any
induced path from $s$ to $t$. A graph $G$ is clean if none of its vertices is
irrelevant. We say that we clean $G$ for $s$ and $t$ by repeatedly deleting
irrelevant vertices for $s$ and $t$ as long as possible. In general,
determining if a vertex is irrelevant is NP-complete [1]. However, for claw-
free graphs, the authors of [12] could show the following (where they used
Observation 1 and Theorem 2.5 for obtaining the polynomial time bound).

######  Lemma 2.1 ([12]).

Let $s,t$ be two vertices of a claw-free graph $G$. Then $G$ can be cleaned
for $s$ and $t$ in polynomial time. Moreover, the resulting graph does not
contain an odd antihole of length at least seven.

The line graph of a graph $G$ with edges $e_{1},\ldots,e_{p}$ is the graph
$L=L(G)$ with vertices $u_{1},\ldots,u_{p}$ such that there is an edge between
any two vertices $u_{i}$ and $u_{j}$ if and only if $e_{i}$ and $e_{j}$ share
an end vertex in $H$. We note that mutually induced paths in a line graph
$L(G)$ are in one-to-one correspondence with vertex-disjoint paths in $G$.
Combining this observation with Theorem 1.2 leads to the following result.

######  Corollary 2.2.

For fixed $k$, the $k$-Induced Disjoint Paths problem can be solved in
polynomial time in line graphs.

A graph $G=(V,E)$ is called a _quasi-line graph_ if for every vertex $u\in V$
there exist two vertex-disjoint cliques $A$ and $B$ in $G$ such that
$N(u)=V(A)\cup V(B)$ (where $V(A)$ and $V(B)$ might be adjacent). Clearly,
every line graph is quasi-line and every quasi-line graph is claw-free. The
following observation is useful and easy to see by looking at the complements
of neighborhood in a graph.

A claw-free graph $G$ is a quasi-line graph if and only if $G$ does not
contain a vertex with an odd antihole in its neighborhood.

A clique in a graph $G$ is called nontrivial if it contains at least two
vertices. A nontrivial clique $A$ is called homogeneous if every vertex in
$V(G)\backslash V(A)$ is either adjacent to all vertices of $A$ or to none of
them. Notice that it is possible to check in polynomial time if an edge of the
graph is a homogeneous clique. This justifies the following observation.

The problem of detecting a homogeneous clique in a graph is solvable in
polynomial time.

Two disjoint cliques $A$ and $B$ form a _homogeneous pair_ in $G$ if the
following two conditions hold. First, at least one of $A,B$ contains more than
one vertex. Second, every vertex $v\in V(G)\setminus(V(A)\cup V(B))$ is either
adjacent to all vertices of $A$ or to none vertex of $A$ as well as either
adjacent to all of $B$ or to none of $B$. The following result by King and
Reed [13, Section 3] will be useful.

######  Lemma 2.3 ([13]).

The problem of detecting a homogeneous pair of cliques in a graph is solvable
in polynomial time.

Let $V$ be a finite set of points of a real line, and ${\mathcal{I}}$ be a
collection of intervals. Two points are adjacent if and only if they belong to
a common interval $I\in{\mathcal{I}}$. The resulting graph is a _linear
interval graph_. Analogously, if we consider a set of points of a circle and
set of intervals (angles) on the circle we get a _circular interval graph_.
Graphs in both classes are claw-free, in fact linear interval graphs coincide
with proper interval graphs (intersection graph of a set of intervals on a
line, where no interval contains another from the set) and circular interval
graphs coincide with proper circular arc graphs (defined analogously). We need
the following result of Deng, Hell, and Huang [5].

Figure 1. Composition of three linear interval strips (only part of the graph
is displayed).

######  Theorem 2.4 ([5]).

Circular interval graphs and linear interval graphs can be recognized in
linear time. Furthermore, a corresponding representation of such graphs can be
constructed in linear time as well.

A _linear interval strip_ $(S,a,b)$ is a linear interval graph $S$ where $a$
and $b$ are the leftmost and the rightmost points (vertices) of its
representation. Observe that in such a graph the vertices $a$ and $b$ are
simplicial. Let $S_{0}$ be a graph with vertices
$a_{1},b_{1},\dots,a_{n},b_{n}$ that is isomorphic to an arbitrary disjoint
union of complete graphs. Let
$(S_{1}^{\prime},a_{1}^{\prime},b_{1}^{\prime}),\dots,(S_{n}^{\prime},a_{n}^{\prime},b_{n}^{\prime})$
be a collection of linear interval strips. The _composition_ $S_{n}$ is
defined inductively where $S_{i}$ is formed from the disjoint union of
$S_{i-1}$ and $S_{i}^{\prime}$, where:

  * $\bullet$

all neighbors of $a_{i}$ are connected to all neighbors of $a_{i}^{\prime}$;

  * $\bullet$

all neighbors of $b_{i}$ are connected to all neighbors of $b_{i}^{\prime}$;

  * $\bullet$

vertices $a_{i},a_{i}^{\prime},b_{i},b_{i}^{\prime}$ are removed.

See Figure 1 for an example. We are now ready to state the structure of quasi-
line graphs as characterized by Chudnovsky and Seymour [3].

######  Theorem 2.5 ([3]).

A quasi-line graph $G$ with no homogeneous pair of cliques is either a
circular interval graph or a composition of linear interval strips.

Finally, we need another algorithmic result of King and Reed [13]. They
observe that the composition of the final strip in a composition of linear
interval graphs is a so-called nontrivial interval 2-join and that every
nontrivial interval 2-join contains a so-called canonical interval 2-join. In
Lemma 13 of this paper they show how to find in polynomial time a canonical
interval 2-join in a quasi-line graph with no homogeneous pair of cliques and
no simplicial vertex or else to conclude that none exists. Recursively
applying this result leads to the following lemma.

######  Lemma 2.6 ([13]).

Let $G$ be a quasi-line graph with no homogeneous pairs of cliques and no
simplicial vertex that is a composition of linear interval strips. Then the
collection of linear interval strips that define $G$ can be found in
polynomial time.

##  3\. Our Main Result

Here is our main result.

######  Theorem 3.1.

For any fixed $k$, the $k$-in-a-Path problem is solvable in polynomial time in
claw-free graphs.

In order to prove Theorem 3.1 we define the following problem.

Ordered-$k$-in-a-Path
Instance: a graph $G$ with $k$ terminals ordered as $t_{1},\ldots,t_{k}$.
Question: does there exist an induced path of $G$ starting in $t_{1}$ then
passing through $t_{2},\ldots,t_{k-1}$ and ending in $t_{k}$?

We can resolve the original $k$-in-a-Path problem by $k!$ rounds of the more
specific version defined above, where in each round we order the terminals by
a different permutation. Hence, since we assume that $k$ is fixed, it suffices
to prove Theorem 3.2 in order to obtain Theorem 3.1.

######  Theorem 3.2.

For any fixed $k$, the Ordered-$k$-in-a-Paths problem is solvable in
polynomial time in claw-free graphs.

We prove Theorem 3.2 in Section 4 and finish this section with the following
consequence of it.

######  Corollary 3.3.

For any fixed $k$, the $k$-Disjoint Induced Paths and $k$-Induced Cycle
problem are solvable in polynomial time in claw-free graphs.

######  Proof 3.4.

Let $G$ be a claw-free graph that together with terminals $t_{1},\ldots,t_{k}$
is an instance of $k$-Induced Cycle. We fix an order of the terminals, say,
the order is $t_{1},\ldots,t_{k}$. We fix neighbors $a_{i}$ and $b_{i-1}$ of
each terminal $t_{i}$. This way we obtain an instance of $k$-Induced Disjoint
Paths with pairs of terminals $(a_{i},b_{i})$ where $b_{0}=b_{k}$. Clearly,
the total number of instances we have created is polynomial. Hence, we can
solve $k$-Induced Cycle in polynomial time if we can solve $k$-Induced
Disjoint Paths in polynomial time.

Let $G$ be a claw-free graph that together with $k$ pairs of terminals
$(a_{i},b_{i})$ for $i=1,\ldots,k$ is an instance of the $k$-Induced Disjoint
Paths problem. First we add an edge between each pair of non-adjacent
neighbors of every terminal in
$T=\\{a_{1},\ldots,a_{k},b_{1},\ldots,b_{k}\\}$. We denote the resulting
graphs obtained after performing this operation on a terminal by
$G_{1},\ldots,G_{2k}$, and define $G_{0}:=G$. We claim that
$G^{\prime}=G_{2k}$ is claw-free and prove this by induction.

The claim is true for $G_{0}$. Suppose the claim is true for $G_{j}$ for some
$0\leq j\leq 2k-1$. Consider $G_{j+1}$ and suppose, for contradiction, that
$G_{j+1}$ contains an induced subgraph isomorphic to a claw. Let
$K:=\\{x,a,b,c\\}$ be a set of vertices of $G_{j+1}$ inducing a claw with
center $x$. Let $s\in T$ be the vertex of $G_{j}$ that becomes simplicial in
$G_{j+1}$. Then $x\neq s$. Since $G_{j}$ is claw-free, we may without loss of
generality assume that at least two vertices of $K$ must be in
$N_{G_{j+1}}(s)\cup\\{s\\}$. Since $N_{G_{j+1}}(s)\cup\\{s\\}$ is a clique of
$G_{j+1}$ and $\\{a,b,c\\}$ is an independent set of $G_{j+1}$, we may without
loss of generality assume that $K\cap(N_{G_{j+1}}(s)\cup\\{s\\})=\\{x,a\\}$
and $\\{b,c\\}\subseteq V(G_{j+1})\setminus(N_{G_{j+1}}(s)\cup\\{s\\})$. Then
$\\{x,b,c,s\\}$ induces a claw in $G_{j}$ with center $x$, a contradiction.
Hence, $G^{\prime}$ is indeed claw-free.

We note that $G$ with terminals $(a_{1},b_{1}),\ldots,(a_{k},b_{k})$ forms a
Yes-instance of $k$-Induced Disjoint Paths if and only if $G^{\prime}$ with
the same terminal pairs is a Yes-instance of this problem. In the next step we
identify terminal $b_{i}$ with $a_{i+1}$, i.e., for $i=1,\ldots,k-1$ we remove
$b_{i},a_{i+1}$ and replace them by a new vertex $t_{i+1}$ adjacent to all
neighbors of $a_{i+1}$ and to all neighbors of $b_{i}$. We call the resulting
graph $G^{\prime\prime}$ and observe that $G$ is claw-free. We define
$t_{1}:=a_{1}$ and $t_{k+1}:=b_{k}$ and claim that $G^{\prime}$ with terminal
pairs $(a_{1},b_{1}),\ldots,(a_{k},b_{k})$ forms a Yes-instance of the
$k$-Induced Paths problem if and only if $G^{\prime\prime}$ with terminals
$t_{1},\ldots,t_{k+1}$ forms a Yes-instance of the Ordered-$(k+1)$-in-a-Path
problem.

In order to see this, suppose $G^{\prime}$ contains $k$ mutually induced paths
$P_{i}$ such that $P_{i}$ connects $a_{i}$ to $b_{i}$ for $1\leq i\leq k$.
Then

$P=t_{1}\overrightarrow{P_{1}}b_{1}^{-}t_{2}a_{2}^{+}\overrightarrow{P_{2}}b_{2}^{-}\ldots
t_{k}a_{k}^{+}\overrightarrow{P_{k}}t_{k}$

is an induced path passing through the terminals $t_{i}$ in prescribed order.
Now suppose $G^{\prime\prime}$ contains an induced path $P$ passing through
terminals in order $t_{1},\ldots,t_{k+1}$. For $i=1,\ldots,k+1$ we define
paths $P_{i}=a_{i}t_{i}^{+}\overrightarrow{P}t_{i+1}^{-}b_{i}$, which are
mutually induced. We now apply Theorem 3.2. This completes the proof.

##  4\. The Proof of Theorem 3.2

We present a polynomial-time algorithm that solves the Ordered-$k$-in-a-Path
problem on a claw-free graph $G$ with terminals in order $t_{1},\ldots,t_{k}$
for any fixed integer $k$. We call an induced path $P$ from $t_{1}$ to $t_{k}$
that contains the other terminals in order $t_{2},\ldots,t_{k-1}$ a solution
of this problem. Furthermore, an operation in this algorithm on input graph
$G$ with terminals $t_{1},\ldots,t_{k}$ preserves the solution if the
following holds: the resulting graph $G^{\prime}$ with resulting terminals
$t_{1}^{\prime},\ldots,t_{k^{\prime}}^{\prime}$ for some $k^{\prime}\leq k$ is
a Yes-instance of the Ordered-$k^{\prime}$-in-a-Path problem if and only if
$G$ is a Yes-instance of the Ordered-$k$-in-a-Path problem. We call $G$ simple
if the following three conditions hold:

  * (i)

$t_{1},t_{k}$ are of degree one in $G$ and all other terminals $t_{i}$
($1<i<k$) are of degree two in $G$, and the two neighbors of such $t_{i}$ are
not adjacent;

  * (ii)

the distance between any pair $t_{i},t_{j}$ is at least four;

  * (iii)

$G$ is connected.

The Algorithm and Proof of Theorem 3.2

Let $G$ be an input graph with terminals $t_{1},\ldots,t_{k}$.

If $k=2$, we compute a shortest path from $t_{1}$ to $t_{2}$. If $k=3$, we use
Theorem 1.1 together with Observation 1. Suppose $k\geq 4$.

Step 1. Reduce to a set of simple graphs.
We apply Lemma 4.1 and obtain in polynomial time a set ${\mathcal{G}}$ that
consists of a polynomial number of simple graphs of size at most $|V(G)|$ such
that there is a solution for $G$ if and only if there is a solution for one of
the graphs in ${\mathcal{G}}$. We consider each graph in ${\mathcal{G}}$. For
convenience we denote such a graph by $G$ as well.

Step 2. Reduce to a quasi-line graph.
We first clean $G$ for $t_{1}$ and $t_{k}$. If during cleaning we remove a
terminal, then we output No. Otherwise, clearly, we preserve the solution. By
Lemma 2.1, this can be done in polynomial time and ensures that there are no
odd antiholes of length at least seven left. Also, $G$ stays simple. Then we
apply Lemma 4.3, which removes vertices $v$ whose neighborhood contain an odd
hole of length five, as long as we can. Clearly, we can do this in polynomial
time. Note that $G$ stays connected since we do not remove cut-vertices due to
the claw-freeness. By condition (i), we do not remove a terminal either.
Afterwards, we clean $G$ again for $t_{1}$ and $t_{k}$. If we remove a
terminal, we output No. Otherwise, as a result of our operations, $G$ becomes
a simple quasi-line graph due to Observation 2.

Step 3. Reduce to a simple quasi-line graph with no homogeneous clique
We first exhaustively search for homogeneous cliques by running the polynomial
algorithm mentioned in Observation 2 and apply Lemma 4.5 each time we find
such a clique. Clearly, we can perform the latter in polynomial time as well.
After every reduction of such a clique to a single vertex, $G$ stays simple
and quasi-line, and at some moment does not contain any homogeneous clique
anymore, while we preserve the solution.

Step 4. Reduce to a circular interval graph or to a composition of interval
strips.
Let $t_{1}^{\prime},t_{k}^{\prime}$ be the (unique) neighbor of $t_{1}$ and
$t_{k}^{\prime}$, respectively. As long as $G$ contains homogeneous pairs of
cliques $(A,B)$ so that $A$ neither $B$ is equal to
$\\{t_{1},t_{1}^{\prime}\\}$ or $\\{t_{k},t_{k}^{\prime}\\}$, we do as
follows. We first detect such a pair in polynomial time using Lemma 2.3 and
reduce them to a pair of single vertices by applying Lemma 4.7. Also
performing Lemma 4.7 clearly takes only polynomial time. After every
reduction, $G$ stays simple and quasi-line, and we preserve the solution. At
some moment, the only homogeneous pairs of cliques that are possibly left in
$G$ are of the form $(\\{t_{1},t_{1}^{\prime}\\},B)$ and
$(\\{t_{k},t_{k}^{\prime}\\},B)$. As $G$ does not contain a homogeneous clique
(see Step 3), the cliques in such pairs must have adjacent vertex sets. Hence,
there can be at most two of such pairs. We perform Lemma 4.7 and afterwards
make the graph simple again. Although this might result in a number of new
instances, their total number is still polynomial because we perform this
operation at most twice. Hence, we may without loss of generality assume that
$G$ stays simple. By Theorem 2.5, $G$ is either a circular interval graph or a
composition of linear interval strips; we deal with theses two cases
separately after recognizing in polynomial time in which case we are by using
Theorem 2.4.

Step 5a. Solve the problem for a circular interval graph.
Let $G$ be a circular interval graph. Observe that the order of vertices in an
induced path must respect the natural order of points on a circle. Hence,
deleting all points that lie on the circle between $t_{k}$ and $t_{1}$
preserves the solution. So, we may even assume that $G$ is a linear interval
graph. We solve the problem in these graphs in Theorem 4.9.

Step 5b. Solve the problem for a composition of linear interval strips.
Let $G$ be a composition of linear interval strips. Because $G$ is assumed to
be clean for $t_{1},\ldots,t_{k}$, $G$ contains no simplicial vertex. Then we
can find these strips in polynomial time using Lemma 2.6 and use this
information in Lemma 4.11. There we create a line graph $G^{\prime}$ with
$|V(G^{\prime})|\leq|V(G)|$, while preserving the solution. Moreover, this can
be done in polynomial time by the same theorem. Then we use Corollary 2.2 to
prove that the problem is polynomially solvable in line graphs in Theorem
4.12.

Now it remains to state and prove Lemmas 4.1–4.11 and Theorems 4.9– 4.12.

######  Lemma 4.1.

Let $G$ be a graph with terminals ordered $t_{1},\ldots,t_{k}$. Then there
exists a set ${\mathcal{G}}$ of $n^{O(k)}$ simple graphs, each of size at most
$|V(G)|$, such that $G$ has a solution if and only if there exists a graph in
${\mathcal{G}}$ that has a solution. Moreover, ${\mathcal{G}}$ can be
constructed in polynomial time.

######  Proof 4.2.

We branch as follows. First we guess the first six vertices after $t_{1}$ in a
possible solution. Then we guess the last six vertices before $t_{n}$.
Finally, for $2\leq i\leq n-1$, we guess the last six vertices preceding
$t_{i}$ and the first six vertices following $t_{i}$. We check if the subgraph
induced by the terminals and all guessed vertices has maximum degree 2. If not
we discard this guess. Otherwise, for every terminal and for every guessed
vertex that is not an end vertex of a guessed subpath, we remove all its
neighbors that are not guessed vertices. This way we obtain a number of graphs
which we further process one by one.

Let $G^{\prime}$ be such a created subgraph. If $G^{\prime}$ does not contain
all terminals, we discard $G^{\prime}$. If $G^{\prime}$ is disconnected then
we discard $G^{\prime}$ if two terminals are in different components, or else
we continue with the component of $G^{\prime}$ that contains all the
terminals. Suppose there is a guessed subpath in $G^{\prime}$ containing more
than one terminal. If the order is not $t_{i},t_{i+1},\ldots,t_{j}$ for some
$i<j$, we discard $G^{\prime}$. Otherwise, if necessary, we place $t_{i}$ and
$t_{j}$ on this subpath such that they are at distance at least four of each
other and also are of distance at least four of each end vertex of the
subpath. Because the guessed subpaths are sufficiently long, such a placement
is possible. We then remove $t_{i+1},\ldots,t_{j-1}$ from the list of
terminals. After processing all created graphs as above, we obtain the desired
set ${\mathcal{G}}$. Since $k$ is fixed, ${\mathcal{G}}$ can be constructed in
polynomial time.

######  Lemma 4.3.

Let $G$ be a simple claw-free graph. Removing a vertex $u\in V(G)$, the
neighborhood of which contains an induced odd hole of length five, preserves
the solution.

######  Proof 4.4.

Because $G$ is simple, $u$ is not a terminal. We first show the following
claim.

Claim 1. Let $G[\\{v,w,x,y\\}]$ be a diamond in which $vw$ is a non-edge. If
there is a solution $P$ that contains $v,x,w$, then there is another solution
that contains $v,y,w$ (and that does not contain $x$).

In order to see this take the original solution $P$ and notice that by claw-
freeness any neighbor of $y$ on $P$ must be in the (closed) neighborhood of
$v$ or $w$. This way the solution can be rerouted via $y$, without using $x$.
This proves Claim 1.

Now suppose that $u$ is a vertex which has an odd hole $C$ of length five in
its neighborhood. Obviously, $G$ is a Yes-instance if $G-u$ is a Yes-instance.
To prove the reverse implication, suppose $G$ is a Yes-instance. Let $P$ be a
solution. If $u$ does not belong to $P$ then we are done. Hence, we suppose
that $u$ belongs to $P$ and consider three cases depending on $|V(C)\cap
V(P)|$.

Case 1. $|V(C)\cap V(P)|\geq 2$. Then $|V(C)\cap V(P)|=2$, as any vertex on
$P$ will have at most two neighbors. We are done by Claim 1.

Case 2. $|V(C)\cap V(P)|=1$. Let $w\in V(C)$ belong to $P$ and let the other
neighbor of $u$ that belongs to $P$ be $x$. We note that $x$ must be adjacent
to at least one of the neighbors of $w$ in $C$. Then we can apply Claim 1
again.

Case 3. $|V(C)\cap V(P)|=0$. Let the two neighbors of $u$ on $P$ be $x$ and
$y$. To avoid a claw at $u$, every vertex of $C$ must be adjacent to $x$ or
$y$. If there is a vertex in $C$ adjacent to both, we apply Claim 1. Suppose
there is no such vertex and that the vertices of the $C$ are partitioned in
two sets $X$ (vertices of $C$ only adjacent to $x$) and $Y$ (vertices of $C$
only adjacent to $y$). We assume without loss of generality that $|X|=3$, and
hence contains a pair of independent vertices which together with $u$ and $y$
form a claw. This is a contradiction.

######  Lemma 4.5.

Let $G$ be a simple quasi-line graph with a homogeneous clique $A$. Then
contracting $A$ to a single vertex preserves the solution and the resulting
graph is a simple quasi-line graph containing the same terminals as $G$.

######  Proof 4.6.

Each vertex in $A$ lies on a triangle, unless $G$ is isomorphic to $P_{2}$,
which is not possible. Hence, by condition (i), $A$ does not contain a
terminal. We remove all vertices of $A$ except one. The resulting graph will
be a simple quasi-line graph containing the same terminals, and we will
preserve the solution.

######  Lemma 4.7.

Let $G$ be a simple quasi-line graph with terminals ordered
$t_{1},\ldots,t_{k}$ that has no homogeneous clique. Contracting the cliques
$A$ and $B$ in a homogeneous pair to single vertices preserves the solution.
The resulting graph is quasi-line; it is simple unless $A$ or $B$ consists of
two vertices $u,u^{\prime}$ with $u\in\\{t_{1},t_{k}\\}$ and
$d(u^{\prime},t_{i})\leq 3$ for some $t_{i}\neq u$.

######  Proof 4.8.

Because $G$ does not contain a homogeneous clique, $V(A)$ and $V(B)$ must be
adjacent. Then, due to condition (ii), there can be at most one terminal in
$V(A)\cup V(B)$. In all the cases discussed below we will actually not
contract edges but only remove vertices from $A$ and $B$. Hence, the resulting
graph will always be a quasi-line graph.

Suppose $A$ contains $t_{1}$ or $t_{k}$, say $t_{1}$. Suppose $|V(A)|=1$, so
$A$ only contains $t_{1}$. Then the neighbor of $t_{1}$ is in $B$ and
$|V(B)|\geq 2$. We delete all vertices from $B$ except this neighbor, because
they will not be used in any solution. Clearly, the resulting graph is simple
and the solution is preserved. Suppose $|V(A)|\geq 2$. Because $t_{1}$ is of
degree one, $A$ consists of two vertices, namely $t_{1}$ and its neighbor
$t_{1}^{\prime}$. Note that $t_{1}^{\prime}$ does not have a neighbor outside
$A$ and $B$, as $t_{1}$ is of degree one. As $V(A)$ and $V(B)$ are adjacent,
$t_{1}^{\prime}$ has a neighbor $u$ in $B$. We delete $t_{1}$ and replace it
by $t_{1}^{\prime}$ in the set of terminals. We delete all vertices of $B$
except $u$, because of the following reasons. If these vertices are not
adjacent to $t_{1}^{\prime}$, they will never appear in any solution. If they
are adjacent to $t_{1}^{\prime}$, they will not appear in any solution
together with $u$, and as such they can be replaced by $u$. Note that
$t_{1}^{\prime}$ has degree one in the new graph and that this graph is only
simple if $d(t_{1}^{\prime},t_{j})\geq 4$ for all $2\leq j\leq k$. Clearly,
the solution is preserved.

Suppose $A$ contains a terminal $t_{i}$ for some $2\leq i\leq k-1$. Suppose
$A$ only contains $t_{i}$. Because $V(A)$ and $V(B)$ are adjacent, $t_{i}$ is
adjacent to a vertex $u$ in $B$. By condition (i), $u$ is the only vertex in
$B$ adjacent to $t_{i}$. We delete all vertices of $B$ except $u$. Clearly,
the resulting graph is simple and the solution is preserved. Suppose
$|V(A)|\geq 2$. By condition (ii), $A$ contains only one other vertex
$t_{i}^{\prime}$ and $t_{i},t_{i}^{\prime}$ do not have a common neighbor.
Then $A$ must be separated of the rest of the graph by $B$. Furthermore, the
other neighbor of $t_{i}$ must be in $B$. We delete $t_{i}^{\prime}$ and all
vertices of $B$ except the neighbor of $t_{i}$. Clearly, the resulting graph
is simple and the solution is preserved.

Suppose $A$ does not contain a terminal. By symmetry, we may assume that $B$
does not contain a terminal either. Let $a^{\prime}b^{\prime}\in E(G)$ with
$a^{\prime}\in V(A)$ and $b^{\prime}\in V(B)$. Let $G^{\prime}$ be the graph
obtained from $G$ by removing all vertices of $A$ except $a^{\prime}$ and $B$
except $a^{\prime},b^{\prime}$. Note that we have kept all terminals and that
the resulting graph is simple. Any solution $P^{\prime}$ for $G^{\prime}$ is a
solution for $G$.

Now assume we have a solution $P$ for $G$. We claim that $|P\cap A|\leq 1$ and
$|P\cap B|\leq 1$. Suppose otherwise, say $|P\cap A|\geq 2$. Then $|P\cap
A|=2$, as $P$ is a path. Since $t_{1}$ and $t_{k}$ are not in $A$, we find
that $P$ contains a subpath $xuvy$ with $u,v\in A$. Since $x$ is adjacent to
$u\in A$, but also non-adjacent to $v\in A$, we find that $x\in B$.
Analogously we get that $y\in B$. However, then $xy\in E(G)$. This is a
contradiction.

Suppose $|P\cap A|=0$ and $|P\cap B|=0$. Then $P$ is a solution for
$G^{\prime}$ as well. Suppose $|P\cap A|=0$ and $|P\cap B|=1$. Then we may
without loss of generality assume that $b^{\prime}\in V(P)$ and find that $P$
is a solution for $G^{\prime}$ as well. The case $|P\cap A|=1$ and $|P\cap
B|=0$ follows by symmetry. Suppose $|P\cap A|=|P\cap B|=1$, say $P$ intersects
$A$ in $a$ and $B$ in $b$. If $ab\in E(G)$ then we replace $ab$ by
$a^{\prime}b^{\prime}$ and obtain a solution for $G^{\prime}$. Suppose
$ab\notin E(G)$. Because $a$ is not a terminal, $a$ has neighbors $x$ and $y$
on $P$. If $x,y\notin N(b)$ then $\\{a^{\prime},x,y,b^{\prime}\\}$ induces a
claw in $G$ with center $a^{\prime}$. This is not possible. Hence, we may
assume without loss of generality that $y$ is adjacent to $b$. Since $A$ or
$B$ contains at least two vertices, $y$ has degree at least three. Then $y$ is
not a terminal. Thus we can skip $y$ and exchange $ayb$ in $P$ with
$a^{\prime}b^{\prime}$ to get the desired induced path $P^{\prime}$.

######  Theorem 4.9.

The Ordered-$k$-in-a-Path problem can be solved in polynomial time in linear
interval graphs.

######  Proof 4.10.

Let $G$ be a linear interval graph. We may assume without loss of generality
that the terminals form an independent set. We use its linear representation
that we obtain in polynomial time by Lemma 2.6. In what follows the notions of
predecessors (left) and successors (right) are considered for the linear
ordering of the points on the line. Without loss of generality we may assume
that $t_{1}$ is the first point and that $t_{k}$ is the last and that no two
points coincide. By our assumption, $t_{i}$ and $t_{i+1}$ are nonadjacent.
From the set of points belonging to the closed interval $[t_{i},t_{i+1}]$ we
remove all neighbors of $t_{i}$ except the rightmost one and all neighbors of
$t_{i+1}$ except the leftmost. Then the shortest path between $t_{i}$ and
$t_{i+1}$ is induced. In addition, these partial paths combined together
provide a solution unless for some terminal $t_{i}$ its leftmost predecessor
is adjacent to its rightmost successor. Hence, no induced path may have
$t_{i}$ among its inner vertices.

######  Lemma 4.11 (proof postponed to journal version).

Let $G$ be a composition of linear interval strips. It is possible to create
in polynomial time a line graph $G^{\prime}$ with $|V(G^{\prime})|\leq|V(G)|$,
while preserving the solution.

######  Theorem 4.12.

For fixed $k$, Ordered-$k$-in-a-Path is polynomially solvable in line graphs.

######  Proof 4.13.

A version of Ordered-$k$-in-a-Path in which the path is not necessarily
induced can be easily translated into an instance of the $k$-Disjoint Paths
problem and solved in polynomial time due to Theorem 1.2. Noting that mutually
induced paths in a line graph $L(G)$ are in one-to-one correspondence with
vertex-disjoint paths in $G$ enables us to solve the Ordered-$k$-in-a-Path
problem in polynomial time for line graphs.

##  5\. Conclusions and Further Research

We showed that, for any fixed $k$, the problems $k$-in-a-Path, $k$-Disjoint
Induced Paths and $k$-Induced Cycle are polynomially solvable on claw-free
graphs. If $k$ is part of the input these problems are known to be NP-
complete. In the journal version we show this is true, even when the input is
restricted to be claw-free. Perhaps the two most fascinating related open
problems are to determine the complexity of deciding if a graph contains an
odd hole (whereas the problem of finding an even hole is polynomially solvable
[2]) and to determine the computational complexity of deciding if a graph
contains two mutually induced holes (whereas it is known that the case of two
mutually induced odd holes is NP-complete [10]). For claw-free graphs these
two problems are solved. Shrem et al. [19] even obtained a polynomial-time
algorithm for detecting a shortest odd hole in a claw-free graph. In the
journal version we will address the second problem for claw-free graphs.

## References

  * [1] D. Bienstock. On the complexity of testing for odd holes and induced odd paths. Discrete Mathematics 90 (1991) 85–92, See also Corrigendum, Discrete Mathematics 102 (1992) 109.
  * [2] M. Chudnovsky, K. Kawarabayashi and P.D. Seymour. Detecting even holes. Journal of Graph Theory 48 (2005) 85–111.
  * [3] M. Chudnovsky and P.D. Seymour. The structure of claw-free graphs. In Surveys in combinatorics 2005, Cambridge (2005) 153–171.
  * [4] M. Chudnovsky and P.D. Seymour. The three-in-a-tree problem. Combinatorica, to appear.
  * [5] X. Deng, P. Hell, and J. Huang. Linear time representation algorithm for proper circular-arc graphs and proper interval graphs. SIAM Journal on Computing 25 (1996) 390–403.
  * [6] N. Derhy and C. Picouleau. Finding induced trees. Discrete Applied Mathematics 157 (2009) 3552–3557.
  * [7] N. Dehry, C. Picouleau, and N. Trotignon. The four-in-a-tree problem in triangle-free graphs. Graphs and Combinatorics 25 (2009) 489–502.
  * [8] R. Faudree, E. Flandrin, and Z. Ryjáček. Claw-free graphs—a survey. Discrete Mathematics 164 (1997) 87–147.
  * [9] M.R. Fellows. The Robertson Seymour theorems: A survey of applications. In: Proceedings of AMS-IMS-SIAM Joint Summer Research Conf. Contemporary Mathematics, Providence, RI (1989) 1- 18.
  * [10] P. Golovach, M. Kamiński, D. Paulusma, and D. M. Thilikos. Induced packing of odd cycles in a planar graph. In: Proceedings of ISAAC 2009, LNCS 5878 (2009) 514–523.
  * [11] R. Haas and M. Hoffmann. Chordless paths through three vertices. Theoretical Computer Science 351 (2006) 360–371.
  * [12] P. van ’t Hof, M. Kamiński and D. Paulusma. Finding induced paths of given parity in claw-free graphs. In: Proceedings of WG 2009, LNCS, to appear.
  * [13] A. King and B. Reed. Bounding $\chi$ in terms of $\omega$ and $\delta$ for quasi-line graphs. Journal of Graph Theory 59 (2008) 215- 228.
  * [14] Y. Kobayashi and K. Kawarabayashi. The induced disjoint paths problem. In: Proceedings of IPCO 2008, LNCS 5035 (2008) 47–61.
  * [15] Y. Kobayashi and K. Kawarabayashi. Algorithms for finding an induced cycle in planar graphs and bounded genus graphs. In: Proceedings of SODA 2009 (2009) 1146–1155.
  * [16] B. Lévêque, D.Y. Lin, F. Maffray, and N. Trotignon. Detecting induced subgraphs. Discrete Applied Mathematics 157 (2009) 3540–3551.
  * [17] N. Robertson and P.D. Seymour.  Graph minors. XIII. The disjoint paths problem.  Journal of Combinatorial Theory, Series B 63 (1995) 65–110.
  * [18] M. Chudnovsky, N. Robertson, P.D. Seymour, and R. Thomas. The strong perfect graph theorem. Annals of Mathematics 164 (2006) 51–229.
  * [19] S. Shrem, M. Stern and M.C. Golumbic. Smallest odd holes in claw-free graphs. In Proceedings of WG 2009, LNCS 5911 (2009) 329–340.
  * [20] N. Trotignon and L. Wei. The $k$-in-a-tree problem for graphs of girth at least $k$, manuscript.


# Color image restoration with impulse noise based on fractional-order total
variation and framelet

R. Parvaz111Corresponding author, Email<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Restore lost images due to noise and blurred is a burgeoning subject in image
processing and despite the different algorithms on this subject, but the
effort to improve is always considered. The definition of fractional
derivatives in recent years has created a powerful tool for this purpose. In
the present paper, using fractional-order total variation and framelet
transform, the nonconvex model for image restoration with impulse noise
problem is improved. Then by alternating direction method of multipliers
(ADMM) and primal-dual problem, the proposed model is solved. The convergence
of the proposed algorithm is studied. And the proposed algorithm is evaluated
using different types of tests. The output results show the efficiency of
proposed method.

Department of Mathematics, University of Mohaghegh Ardabili, 56199-11367
Ardabil, Iran.

Keywords: Image deblurring; Fractional total variation; Framelet; Nonconvex.

##  1 Introduction

The image blurring and noise process can be considered by using the following
formula

$\displaystyle F=h\circledast U+N_{\epsilon},$

where $F$ and $U\in\mathds{R}^{n\times m}$ are observed and original images,
respectively, and $N_{\epsilon}$ shows noise. Also, $h\in\mathds{R}^{r\times
s}$ is blurred kernel and $\circledast$ denotes two-dimensional convolution
operator. The above relation can be rewritten as a linear equation as follows

$\displaystyle f=Au+n_{\epsilon},$

where $f$ and $u\in\mathds{R}^{nm\times 1}$ denote the reshaped of observed
and original images, respectively. Also $A\in\mathds{R}^{nm\times nm}$ is
obtained according to the blurred kernel and boundary conditions for the
blurred process. There are four main boundary conditions that include zero,
periodic, reflexive and anti-reflexive boundary conditions. Depending on each
of these boundary conditions, the matrix $A$ has a special structure. For
example in the zero boundary condition, $A$ is a block toeplitz with toeplitz
blocks (BTTB) matrix or in the periodic boundary condition, $A$ is a block
circulant with circulant blocks (BCCB) matrix. Due to the noise and large size
of the unknown coefficients and ill-conditioned for this linear equation, it
is not possible to solve this problem directly. The first attempts to solve
this problem can be made on SVD decompositions. But in most cases, this method
does not have the desired output. Other method, that can be used for this
problem is the basis pursuit problem [5] by minimization problem as

$\displaystyle\min_{u}\\{\|u\|_{1}:Au=f\\},$

which is studied in many papers as [26, 35]. One of the most popular methods
that has attracted the most attention is the use of total variation (TV) based
on regularization scheme (the ROF model). This model is introduced by Rudin,
Osher, and Fatemi [25] as

$\displaystyle\min_{u}\frac{\lambda}{2}\|Au-f\|^{2}_{2}+\int_{\Omega}|Du|,$

where $\Omega$ shows a bounded open subset with Lipschitzian boundary in
$\mathds{R}^{2}$ and $Du$ denotes the derivative of $u$. The idea of using
total variation has been considered in recent years and has been used in
various articles, for example [24, 1, 19, 32]. One of the most important tools
that has improved this method in recent years is the use of fractional
derivatives. Despite the existence of different definitions for fractional
derivatives, such as Riemann-Liouville (R-L) and Caputo definition, the
Grünwald-Letnikov (G-L) definition is often used in image processing due to
its lower computational complexity than other definitions. Based on these
types of derivatives, fractional-order total variation (FTV) is introduced and
used in image and signal processing [16, 22, 6]. With the development of the
wavelet and framelet concept, an efficient tool for image and signal
processing is developed that has been used in various articles as [4, 13, 3,
17]. These concepts are introduced in the following subsections. The reader
can find more information about these concepts in [12, 28, 11]. The $l_{1}$
norm based on frame transform for restoration problem is introduced by Dong,
Ji and Shen [7]. Due to the structure of $l_{1}$ norm as nonsmooth and
nonseparable, solving a problem that includes these norms is hard. The split
Bregman algorithm is a suitable tool for solving these types of problems [29,
36, 14]. In the proposed model a non-convex $(l_{1}-l_{2})$-norm is considered
as regularization term. $(l_{1}-l_{2})$-norm is studied in many papers as [18,
21]. Also, this norm based on frame transform is used by Jingjing Liu et al in
[18] as following model

$\displaystyle\min_{u}\|Au-f\|_{1}+\lambda_{1}\big{(}\|Wu\|_{1}-\beta\|u\|_{2}\big{)},$

where $W$ represent the matrix of framelet transform. As it is clear from this
model, the total variation phrase is not observed in this model. Therefore,
adding this expression can improve the algorithm. Total variation method can
preserve edges very well in the restored image, then this helps to improve the
restored image. Although the ordinary method of minimization is slow for this
problem [2, 33], the optimal algorithm based on primal-dual is introduced for
solving this problem in [34, 10, 8, 9].

The organization of this paper is as follows: In Section 2, the tools used in
the proposed algorithm briefly introduced. The details of the proposed method
are given in Section 3. The convergence analysis of the proposed algorithm is
given in Section 4. Simulation results and algorithm analysis are studied in
Section 5. Also the summary of paper is given in Section 6.

##  2 Preliminaries

######  Definition 2.1.

Let $\mathcal{H}$ be a separable Hilbert space. Then the sequence
$F=\\{f_{i}\\}_{i\in I}\subseteq\mathcal{H}$ is named a frame in $\mathcal{H}$
if there exist two constants as $\rho_{1}$ and $\rho_{2}$ such that for all
$f\in\mathcal{H}$

$\displaystyle\rho_{1}\|f\|^{2}\leq\sum_{i\in I}|\langle
f,f_{i}\rangle|^{2}\leq\rho_{2}\|f\|^{2}.$

When $\rho_{1}=\rho_{2}=1$, frame is called a Parseval frame in
$\mathcal{H}=L_{2}(\mathds{R})$.

In this paper, particular Parseval framelet systems in $\mathcal{H}$ that are
constructed by B-spline whose refinement mask is $h_{0}=\frac{1}{4}[1,2,1]$,
with two corresponding framelet masks $h_{1}=\frac{\sqrt{2}}{4}[1,0,-1]$ and
$h_{2}=\frac{1}{4}[-1,2,-1]$. Complete information about frame and framelet is
available in [12, 28, 11], and the reader can refer to these sources.

######  Definition 2.2.

The G-L fractional-order derivatives $D^{\alpha}_{x}$ and $D^{\alpha}_{y}$ for
input image $u$ of order $\alpha\in\mathds{R}^{+}$ are defined as

$\displaystyle
D^{\alpha}_{x}u_{i,j}:=\sum_{l=0}^{k-1}\phi^{\alpha}_{l}u_{i-k,j},$
$\displaystyle
D^{\alpha}_{y}u_{i,j}:=\sum_{l=0}^{k-1}\phi^{\alpha}_{l}u_{i,j-k},$

where
$\phi^{\alpha}_{l}=(-1)^{l}\frac{\Gamma(\alpha+1)}{\Gamma(l+1)\Gamma(\alpha+1-l)}$
and $k$ denotes the number of neighboring pixels. Also the discrete
fractional-order gradient is considered as
$\nabla^{\alpha}u=[D^{\alpha}_{x}u,D^{\alpha}_{y}u]^{T}$.

######  Definition 2.3.

The adjoint operators of the fractional-order derivatives are defined as

$\displaystyle(D^{\alpha}_{x})^{T}u_{i,j}:=\sum_{l=0}^{k-1}\phi^{\alpha}_{l}u_{i+k,j},$
$\displaystyle(D^{\alpha}_{y})^{T}u_{i,j}:=\sum_{l=0}^{k-1}\phi^{\alpha}_{l}u_{i,j+k}.$

Based on above definitions for a vector function
$\textbf{p}(x,y)=\big{(}p_{1}(x,y),p_{2}(x,y)\big{)}$ the fractional
divergence operator can be obtained as

$\displaystyle
div^{\alpha}\textbf{p}=(-1)^{\alpha}(\nabla^{\alpha})^{T}\textbf{p}=(-1)^{\alpha}\big{(}(D^{\alpha}_{x})^{T}p^{1}_{i,j}+(D^{\alpha}_{y})^{T}p^{2}_{i,j}\big{)}.$

##  3 Proposed minimization model and iterative method

###  3.1 Proposed model

In the proposed model, the following model based on FTV is introduced for
restoration of image with impulse noise

$\displaystyle\min_{u}\|Au-f\|_{1}+\lambda_{1}\big{(}\|Wu\|_{1}-\beta\|u\|_{2}\big{)}+\lambda_{2}\|u\|_{FTV},$
(3.1)

where $\lambda_{1},\lambda_{2}$ and $\beta$ are positive given parameters.
Also $\|\cdot\|_{FTV}$ denotes fractional-order total variation norm that
defined as

$\displaystyle\|u\|_{FTV}=\sum_{i,j}\sqrt{(D^{\alpha}_{x}u_{i,j})^{2}+(D^{\alpha}_{y}u_{i,j})^{2}}.$

This model contains a nonconvex sentence. There are several methods for
solving nonconvergent optimization problems, for example see [23]. In the
proposed method, alternating direction method of multipliers (ADMM) is used
for solving this problem. By auxiliary variables $m=\\{m_{i}\\}^{3}_{i=1}$,
(3.1) can be written as

$\displaystyle\min_{u}\|m_{1}\|_{1}+\lambda_{1}\big{(}\|m_{2}\|_{1}-\beta\|u\|_{2}\big{)}+\lambda_{2}\|m_{3}\|_{FTV},$
$\displaystyle\text{s.t.}~{}~{}m_{1}=Au-f,~{}~{}m_{2}=Wu,~{}~{}m_{3}=u.$ (3.2)

The augmented Lagrangian for (3.2) is obtained as

$\displaystyle\min_{u,m,n}L(u,m_{1},m_{2},m_{3}$
$\displaystyle,n_{1},n_{2},n_{3})=\min_{u,m,n}\|m_{1}\|_{1}+\lambda_{1}\big{(}\|m_{2}\|_{1}-\beta\|u\|_{2}\big{)}+\lambda_{2}\|m_{3}\|_{FTV}$
$\displaystyle+\mu_{1}\langle Au-f-m_{1},n_{1}\rangle+\frac{\mu_{1}}{2}\|Au-f-
m_{1}\|^{2}_{2}+\mu_{2}\langle Wu-m_{2},n_{2}\rangle$
$\displaystyle+\frac{\mu_{2}}{2}\|Wu-m_{2}\|^{2}_{2}+\mu_{3}\langle
u-m_{3},n_{3}\rangle+\frac{\mu_{3}}{2}\|u-m_{3}\|^{2}_{2},$ (3.3)

where $n=\\{n_{i}\\}^{3}_{i=1}$ and $\mu_{i}>0,~{}i=1,2,3$ are the Lagrange
multipliers and penalty parameters, respectively. The extended iterative
algorithm for solving problem (3.3) based on ADMM is given as

$\displaystyle u^{k+1}$
$\displaystyle=\arg\min_{u}-\lambda_{1}\beta\|u\|_{2}+\mu_{1}\langle Au-
f-m^{k}_{1},n^{k}_{1}\rangle+\frac{\mu_{1}}{2}\|Au-f-m^{k}_{1}\|^{2}_{2}$
$\displaystyle+\mu_{2}\langle
Wu-m^{k}_{2},n^{k}_{2}\rangle+\frac{\mu_{2}}{2}\|Wu-m^{k}_{2}\|^{2}_{2}+\mu_{3}\langle
u-m^{k}_{3},n^{k}_{3}\rangle$
$\displaystyle+\frac{\mu_{3}}{2}\|u-m^{k}_{3}\|^{2}_{2},$ (3.4) $\displaystyle
m^{k+1}_{1}$ $\displaystyle=\arg\min_{m_{1}}\|m_{1}\|_{1}+\mu_{1}\langle
Au^{k+1}-f-m_{1},n^{k}_{1}\rangle+\frac{\mu_{1}}{2}\|Au^{k+1}-f-m_{1}\|^{2}_{2},$
(3.5)

$\displaystyle n^{k+1}_{1}$ $\displaystyle=n^{k}_{1}+Au^{k+1}-f-m^{k+1}_{1},$
(3.6) $\displaystyle m^{k+1}_{2}$
$\displaystyle=\arg\min_{m_{2}}\lambda_{1}\|m_{2}\|_{1}+\mu_{2}\langle
Wu^{k+1}-m_{2},n^{k}_{2}\rangle+\frac{\mu_{2}}{2}\|Wu^{k+1}-m_{2}\|^{2}_{2},$
(3.7) $\displaystyle n^{k+1}_{2}$
$\displaystyle=n^{k}_{2}+Wu^{k+1}-m^{k+1}_{2},$ (3.8) $\displaystyle
m^{k+1}_{3}$
$\displaystyle=\arg\min_{m_{3}}\lambda_{2}\|m_{3}\|_{FTV}+\mu_{3}\langle
u^{k+1}-m_{3},n^{k}_{3}\rangle+\frac{\mu_{3}}{2}\|u^{k+1}-m_{3}\|^{2}_{2},$
(3.9) $\displaystyle n^{k+1}_{3}$
$\displaystyle=n^{k}_{3}+u^{k+1}-m^{k+1}_{3}.$ (3.10)

###  3.2 Solve subproblems

In this subsection, the solution to each of the subproblems introduced in the
previous subsection are studied. For (3.4) by using the optimal condition, we
get

$\displaystyle\big{(}\mu_{1}A^{T}A$
$\displaystyle+\mu_{3}I+\mu_{2}I-\lambda_{1}\beta/\|u^{k}\|_{2}I\big{)}u$
$\displaystyle=\mu_{1}A^{T}(f+m^{k}_{1}-n^{k}_{1})+\mu_{2}W^{T}(m^{k}_{2}-n^{k}_{2})+\mu_{3}(m^{k}_{3}-n^{k}_{3}).$
(3.11)

Under the periodic condition for blurred processing, the blurred matrix can be
generated as block circulant with circulant blocks (BCCB) matrix. It is well
known in the field of linear algebra that these types of matrices are
decomposed using Fourier transform. And due to the fast Fourier transform
(FFT), the calculation is performed faster. So by considering the periodic
condition, Eq. (3.11) is changed as

$\displaystyle\big{(}\mu_{1}\Lambda^{\ast}\Lambda$
$\displaystyle+(\mu_{3}+\mu_{2}-\lambda_{1}\beta/\|u^{k}\|_{2})I\big{)}Fu^{k+1}$
$\displaystyle=\mu_{1}\Lambda^{\ast}F(f+m^{k}_{1}-n^{k}_{1})+\mu_{2}FW^{T}(m^{k}_{2}-n^{k}_{2})+\mu_{3}F(m^{k}_{3}-n^{k}_{3}),$
(3.12)

where $\ast$ and $F$ denote the complex conjugacy and fast Fourier transform,
respectively. Also $\Lambda$ is a diagonal matrix dependent on the eigenvalues
of the blurred matrix. The equation (3.12) can be easily solved using Fourier
calculations.

Subproblem (3.5) can be rewritten as

$\displaystyle m^{k+1}_{1}$
$\displaystyle=\arg\min_{m_{1}}\|m_{1}\|_{1}+\frac{\mu_{1}}{2}\|m_{1}-(Au^{k+1}-f+n^{k}_{1})\|^{2}_{2}.$

The solution for the above problem based on proximal mapping for $l_{1}$-norm
can be obtained as

$\displaystyle m^{k+1}_{1}=\Psi_{1/\mu_{1}}(Au^{k+1}-f+n^{k}_{1}),$ (3.13)

where $\Psi$ is defined as

$\displaystyle\Psi_{a}(x)=\operatorname{sign}(x)\max(|x|-a,0).$

In a similar way, (3.7) can be written as

$\displaystyle m^{k+1}_{2}$
$\displaystyle=\arg\min_{m_{2}}\lambda_{1}\|m_{2}\|_{1}+\frac{\mu_{2}}{2}\|m_{2}-(Wu^{k+1}+n^{k}_{2})\|^{2}_{2},$

and the solution by proximal mapping is earned as

$\displaystyle m^{k+1}_{2}=\Psi_{\lambda_{1}/\mu_{2}}(Wu^{k+1}+n^{k}_{2}).$
(3.14)

In order to avoid complex calculations for Eq. (3.9), the dual problem is used
to find the solution. In the first step, Eq. (3.9) is changed as

$\displaystyle m^{k+1}_{3}$
$\displaystyle=\arg\min_{m_{3}}\lambda_{2}\|m_{3}\|_{FTV}+\frac{\mu_{3}}{2}\|m_{3}-(u^{k+1}-n^{k}_{3})\|^{2}_{2},$
(3.15)

then in the next step, the dual problem is obtained and solved for this
problem.

######  Lemma 3.1.

If we consider $J(u)=\min_{u}\|u\|_{FTV}$ then the dual problem of $J(u)$ is
obtained as [8]

$\displaystyle
J(u)=\sup_{\textbf{p}}~{}\langle\textbf{p},\nabla^{\alpha}u\rangle-J^{\ast}(\textbf{p}),$

where

$\displaystyle
J^{\ast}(\textbf{p})=\left\\{\begin{array}[]{l}\begin{array}[]{*{20}{c}}0,&\text{if}~{}~{}|\textbf{p}|\leq
1,\\\ \end{array}\\\
\begin{array}[]{*{20}{c}}\infty,&\text{if}~{}~{}|\textbf{p}|>1.\\\
\end{array}\\\ \end{array}\right.$

Based on Lemma 3.1, the corresponding primal-dual problem of (3.15) is written
as follows

$\displaystyle(m^{k+1}_{3},\textbf{p}^{k+1})=\arg\min_{m_{3}}\max_{\textbf{p}\in\chi}~{}\frac{\lambda_{2}}{\mu_{3}}\langle\textbf{p},\nabla^{\alpha}m_{3}\rangle+\frac{1}{2}\|m_{3}-(u^{k+1}-n^{k}_{3})\|^{2}_{2},$
(3.16)

where
$\chi=\big{\\{}\textbf{p}\in\mathds{R}^{2nm}|\textbf{p}_{i}\in\mathds{R}^{2},\|\textbf{p}_{i}\|_{2}\leq
1,\forall i\in\\{1,\ldots,nm\\}\big{\\}}$. By the iterative scheme, the
solution of the primal-dual problem (3.16) can be written as

$\displaystyle\textbf{p}^{k+1}=\arg\max_{\textbf{p}\in\chi}\frac{\lambda_{2}}{\mu_{3}}\langle\textbf{p},\nabla^{\alpha}\hat{m}_{3}^{k}\rangle-\frac{1}{2\gamma}\|\textbf{p}-\textbf{p}^{k}\|^{2}_{2},$
(3.17) $\displaystyle
m_{3}^{k+1}=\arg\min_{m_{3}}~{}\frac{\lambda_{2}}{\mu_{3}}\langle\textbf{p}^{k+1},\nabla^{\alpha}m_{3}\rangle+\frac{1}{2}\|m_{3}-(u^{k+1}-n^{k}_{3})\|^{2}_{2},$
(3.18) $\displaystyle\hat{m}_{3}^{k+1}=2m^{k+1}_{3}-m^{k}_{3}.$ (3.19)

After simplifying (3.17)-(3.18), the following statements are obtained

$\displaystyle\textbf{p}^{k+1}=\frac{\textbf{p}^{k}+\frac{\lambda_{2}\gamma}{\mu_{3}}\nabla^{\alpha}\hat{m}_{3}^{k}}{\max(|\textbf{p}^{k}+\frac{\lambda_{2}\gamma}{\mu_{3}}\nabla^{\alpha}\hat{m}_{3}^{k}|,1)},$
(3.20) $\displaystyle
m^{k+1}_{3}=m^{k}_{3}-\tau\big{(}\frac{\lambda_{2}\gamma}{\mu_{3}}(\nabla^{\alpha})^{T}\textbf{p}^{k+1}+m^{k}_{3}-(u^{k+1}+n^{k}_{3})\big{)},$
(3.21)

where $\tau$ is step size and $\gamma$ is a positive constant.
The general structure of the proposed method for restoration of blurred images
with impulse noise is summarized in Algorithm 1.

Algorithm 1: Restoration proposed algorithm.

Initialization:
$\alpha,\beta,\tau,\gamma,\\{\lambda_{i}\\}^{2}_{i=1},\\{\mu_{i}\\}^{3}_{i=1},m^{0},n^{0},u^{0}$.

for k=1,… do

Compute $u^{k}$ by solving (3.12),

Compute $m^{k}_{1}$ by solving (3.13),

Compute $n^{k}_{1}$ by solving (3.6),

Compute $m^{k}_{2}$ by solving (3.14),

Compute $n^{k}_{2}$ by solving (3.8),

Compute $m^{k}_{3}$ by solving (3.19)-(3.21),

Compute $n^{k}_{3}$ by solving (3.10),

end for

If the stop condition is met in the above step, stop the loop.

###  3.3 Extended algorithm for color image

The proposed restoration algorithm for grayscale image is introduced in the
previous subsection. But this algorithm can be extended to color images. In
the following, the details of the proposed algorithm for color images are
explained. The blurred matrix for color image is given in
$\mathds{R}^{3nm\times 3nm}$ as

$\displaystyle
A=\left[{\begin{array}[]{*{20}{c}}{\begin{array}[]{*{20}{c}}A_{rr}\\\
A_{gr}\\\ A_{br}\\\ \end{array}}&{\begin{array}[]{*{20}{c}}A_{rg}\\\ A_{gg}\\\
A_{bg}\\\ \end{array}}&{\begin{array}[]{*{20}{c}}A_{rb}\\\ A_{gb}\\\ A_{bb}\\\
\end{array}}\\\ \end{array}}\right].$

Also, in the calculations related to this subsection, for different layers of
the color image, we expand the values that is calculated in the previous
subsection as $u=[u_{r};u_{g};u_{b}]$, $f=[f_{r};f_{g};f_{b}]$,
$m_{i}=[m_{i,r};m_{i,g};m_{i,b}]$, $n_{i}=[n_{i,r};n_{i,g};n_{i,b}]$ for
$i=1,2,3$.
Using the same procedure mentioned in the pervious section the following
phrase is obtained

$\displaystyle\big{(}\mu_{1}\Lambda^{\ast}\Lambda$
$\displaystyle+(\mu_{3}+\mu_{2}-\lambda\beta/\|u\|_{2})I\big{)}\hat{F}u^{k+1}$
$\displaystyle=\mu_{1}\Lambda^{\ast}\hat{F}(f+m^{k}_{1}-n^{k}_{1})+\mu_{2}\hat{F}W^{T}(m^{k}_{2}-n^{k}_{2})+\mu_{3}\hat{F}(m^{k}_{3}-n^{k}_{3}),$
(3.22)

where $\hat{F}=I\otimes F$, here $\otimes$ shows the Kronecker product. Also
$\Lambda$ is obtained after decomposed using Fourier transform as

$\displaystyle\Lambda=\left[{\begin{array}[]{*{20}{c}}{\begin{array}[]{*{20}{c}}\Lambda_{rr}\\\
\Lambda_{gr}\\\ \Lambda_{br}\\\
\end{array}}&{\begin{array}[]{*{20}{c}}\Lambda_{rg}\\\ \Lambda_{gg}\\\
\Lambda_{bg}\\\ \end{array}}&{\begin{array}[]{*{20}{c}}\Lambda_{rb}\\\
\Lambda_{gb}\\\ \Lambda_{bb}\\\ \end{array}}\\\ \end{array}}\right].$

Other parts of the proposed algorithm are similar to those described in the
pervious section, and the calculation details are given in Algorithm 2. The
simulation results of the algorithms described in this section are studied in
the simulation results section.

Algorithm 2: Color image restoration proposed algorithm.

Initialization:
$\alpha,\beta,\tau,\gamma,\\{\lambda_{i}\\}^{2}_{i=1},\\{\mu_{i}\\}^{3}_{i=1},m^{0},n^{0},u^{0}$.

for k=1,… do

Compute $u^{k}$ by solving (3.22),

for l=r,g,b do

Compute $m^{k}_{1,l}$ by solving:
$m^{k}_{1,l}=\Psi_{1/\mu_{1}}(Au^{k}_{l}-f_{l}+n^{k-1}_{1,l})$,

Compute $n^{k}_{1,l}$ by solving:
$n^{k}_{1,l}=n^{k-1}_{1,l}+Au^{k}_{l}-f-m^{k}_{1,l}$,

Compute $m^{k}_{2,l}$ by solving:
$m^{k}_{2,l}=\Psi_{\lambda_{1}/\mu_{2}}(Wu^{k}_{l}+n^{k-1}_{2,l})$,

Compute $n^{k}_{2,l}$ by solving:
$n^{k}_{2,l}=n^{k-1}_{2,l}+Wu^{k}_{l}-m^{k}_{2,l}$,

Compute $m^{k}_{3,l}$ by solving:

$\textbf{p}^{k}_{l}=\frac{\textbf{p}^{k-1}_{l}+\frac{\lambda_{2}\gamma}{\mu_{3}}\nabla^{\alpha}\hat{m}_{3,l}^{k-1}}{\max(|\textbf{p}^{k-1}_{l}+\frac{\lambda_{2}\gamma}{\mu_{3}}\nabla^{\alpha}\hat{m}_{3,l}^{k-1}|,1)}$,

$m^{k}_{3,l}=m^{k-1}_{3,l}-\tau\big{(}\frac{\lambda_{2}\gamma}{\mu_{3}}(\nabla^{\alpha})^{T}\textbf{p}^{k}_{l}+m^{k-1}_{3,l}-(u^{k}_{l}+n^{k-1}_{3,l})\big{)}$,

$\hat{m}_{3,l}^{k}=2m^{k}_{3,l}-m^{k-1}_{3,l}$,

Compute $n^{k}_{3,l}$ by solving:
$n^{k}_{3,l}=n^{k-1}_{3,l}+u^{k}_{l}-m^{k}_{3,l}$,

end for

end for

If the stop condition is met in the above step, stop the loop.

##  4 Convergence analysis

In this section, the convergence of the proposed method is studied. The
convergence analysis for proposed method is based on the described method in
[18, 21].

######  Lemma 4.1.

Let the objective function be increasing, that is
$\|Au-f\|_{1}+\lambda_{1}\big{(}\|Wu\|_{1}-\beta\|u\|_{2}\big{)}+\lambda_{2}\|u\|_{FTV}\rightarrow\infty$
when $\|x\|_{2}\rightarrow\infty$. Also assume that
$\\{u^{k},m_{1}^{k},m_{2}^{k},m_{3}^{k},n_{1}^{k},n_{2}^{k},n_{3}^{k}\\}$ be
the sequence generated by the proposed method, then the following statements
hold:

a)

$\displaystyle L(u^{k+1},m_{1}^{k+1},m_{2}^{k+1},$ $\displaystyle
m_{3}^{k+1},n_{1}^{k+1},n_{2}^{k+1},n_{3}^{k+1})-L(u^{k},m_{1}^{k},m_{2}^{k},m_{3}^{k},n_{1}^{k},n_{2}^{k},n_{3}^{k})$
$\displaystyle\leq\sum^{3}_{i=1}C_{i}\|m^{k+1}_{i}-m^{k}_{i}\|^{2}_{2}.$

b) If there exists a
$p\in\partial_{u}L(u^{k+1},m_{1}^{k+1},m_{2}^{k+1},m_{3}^{k+1},n_{1}^{k+1},n_{2}^{k+1},n_{3}^{k+1})$
then

$\displaystyle\|p\|_{2}+\sum^{3}_{i}(\partial_{m_{i}}$
$\displaystyle+\partial_{n_{i}})L(u^{k+1},m_{1}^{k+1},m_{2}^{k+1},m_{3}^{k+1},n_{1}^{k+1},n_{2}^{k+1},n_{3}^{k+1})$
$\displaystyle\leq\sum^{3}_{i=1}C_{i+3}\|m^{k+1}_{i}-m^{k}_{i}\|_{2},$

where in conditions (a) and (b), $\\{C_{i}\\}^{6}_{i=1}$ are constant.

###### Proof.

a) By problem (3.4), we get

$\displaystyle
L(u^{k+1},m_{1}^{k},m_{2}^{k},m_{3}^{k},n_{1}^{k},n_{2}^{k},n_{3}^{k})-L(u^{k},m_{1}^{k},m_{2}^{k},m_{3}^{k},n_{1}^{k},n_{2}^{k},n_{3}^{k})\leq
0.$

Also by using (3.5)-(3.10), we obtain

$\displaystyle L(u^{k+1},$ $\displaystyle
m_{1}^{k+1},m_{2}^{k+1},m_{3}^{k+1},n_{1}^{k+1},n_{2}^{k+1},n_{3}^{k+1})-L(u^{k},m_{1}^{k},m_{2}^{k},m_{3}^{k},n_{1}^{k},n_{2}^{k},n_{3}^{k})$
$\displaystyle\leq\|m^{k+1}_{1}\|_{1}-\|m^{k}_{1}\|_{1}+\lambda_{1}\big{(}\|m^{k+1}_{2}\|_{1}-\|m^{k}_{2}\|_{1}\big{)}+\lambda_{2}\big{(}\|m^{k+1}_{3}\|_{FTV}-\|m^{k}_{3}\|_{FTV}\big{)}$
$\displaystyle+\sum^{3}_{i=3}\mu_{i}\big{(}\|n^{k+1}_{i}-n^{k}_{i}\|^{2}_{2}-\langle
n^{k}_{i},m^{k+1}_{i}-m^{k}_{i}\rangle-\frac{1}{2}\|m^{k+1}_{i}-m^{k}_{i}\|^{2}_{2}$
$\displaystyle-\langle
m^{k+1}_{i}-m^{k}_{i},n^{k+1}_{i}-n^{k}_{i}\rangle\big{)}.$

Based on optimality conditions for (3.5)-(3.10), we have
$\partial_{m_{1}}\|m^{k+1}\|_{1}=\mu_{1}n^{k+1}_{1}$,
$\lambda_{1}\partial_{m_{2}}\|m_{2}^{k+1}\|_{1}=\mu_{2}n^{k+1}_{2}$ and
$\lambda_{2}\partial_{m_{3}}\|m_{3}^{k+1}\|_{FTV}=\mu_{3}n^{k+1}_{3}$, then by
using Lipschitz continuous gradient and Young’s inequality, the following
inequalities for any positive $\\{c_{i}\\}^{3}_{i=1}$ hold

$\displaystyle\|m^{k+1}_{1}\|_{1}-\|m^{k}_{1}\|_{1}-\mu_{1}\langle
n^{k}_{1},m^{k+1}_{1}-m^{k}_{1}\rangle\leq\frac{L_{1}}{2}\|m^{k+1}_{1}-m^{k}_{1}\|^{2}_{2},$
$\displaystyle\lambda_{1}\big{(}\|m^{k+1}_{2}\|_{1}-\|m^{k}_{2}\|_{1}\big{)}-\mu_{2}\langle
n^{k}_{2},m^{k+1}_{2}-m^{k}_{2}\rangle\leq\frac{L_{2}}{2}\|m^{k+1}_{2}-m^{k}_{2}\|^{2}_{2},$
$\displaystyle\lambda_{2}\big{(}\|m^{k+1}_{3}\|_{FTV}-\|m^{k}_{3}\|_{FTV}\big{)}-\mu_{3}\langle
n^{k}_{3},m^{k+1}_{3}-m^{k}_{3}\rangle\leq\frac{L_{3}}{2}\|m^{k+1}_{3}-m^{k}_{3}\|^{2}_{2},$
$\displaystyle-\mu_{i}\langle
m^{k+1}_{i}-m^{k}_{i},n^{k+1}_{i}-n^{k}_{i}\rangle\leq
c_{i}\mu_{i}\|n^{k+1}_{3}-n^{k}_{3}\|^{2}_{2}+\frac{\mu_{i}}{4c_{i}}\|m^{k+1}_{3}-m^{k}_{3}\|^{2}_{2},~{}~{}i=1,2,3,$

if $\\{c_{i}\\}^{3}_{i=1}$ is chosen as $\\{\mu_{i}/2L_{i}\\}^{3}_{i=1}$, we
get

$\displaystyle L(u^{k+1},$ $\displaystyle
m_{1}^{k+1},m_{2}^{k+1},m_{3}^{k+1},n_{1}^{k+1},n_{2}^{k+1},n_{3}^{k+1})-L(u^{k},m_{1}^{k},m_{2}^{k},m_{3}^{k},n_{1}^{k},n_{2}^{k},n_{3}^{k})$
$\displaystyle\leq\sum^{3}_{i}\big{(}\frac{L_{i}}{2}-\frac{\mu_{i}}{2}+\frac{\mu_{1}}{4c_{i}}\big{)}\|m^{k+1}_{i}-m^{k}_{i}\|^{2}_{2}+(1+c_{i})\mu_{i}\|n^{k+1}_{i}-n^{k}_{i}\|^{2}_{2}$
$\displaystyle=\sum^{3}_{i=1}C_{i}\|m^{k+1}_{i}-m^{k}_{i}\|^{2}_{2},$

where $C_{i}=(3L_{i}-\mu_{i})/2+L_{i}^{2}/\mu_{i}$. Therefore, the first part
of the lemma is proved.
b) By using optimality condition for (3.4), there is a
$q\in\partial_{u}\big{(}-\lambda_{1}\beta_{1}\|u\|_{2}\big{)}$ such that

$\displaystyle q$
$\displaystyle+\mu_{1}A^{T}\big{(}Au^{k+1}-f+n^{k}_{1}-m^{k}_{1}\big{)}+\mu_{2}W^{T}\big{(}Wu^{k+1}+n^{k}_{2}-m^{k}_{2}\big{)}$
$\displaystyle+\mu_{3}\big{(}u^{k+1}+n^{k}_{3}-m^{k}_{3}\big{)}=0,$

now let

$\displaystyle p$
$\displaystyle=q+\mu_{1}A^{T}\big{(}Au^{k+1}-f+n^{k+1}_{1}-m^{k+1}_{1}\big{)}+\mu_{2}W^{T}\big{(}Wu^{k+1}+n^{k+1}_{2}-m^{k+1}_{2}\big{)}$
$\displaystyle+\mu_{3}\big{(}u^{k+1}+n^{k+1}_{3}-m^{k+1}_{3}\big{)}\in\partial_{u}L(u^{k+1},m^{k+1}_{1},m^{k+1}_{2},m^{k+1}_{3},n^{k+1}_{1},n^{k+1}_{2},n^{k+1}_{3}),$

then we obtain

$\displaystyle\|p\|_{2}\leq\sum^{3}_{i=1}c_{i+3}(\mu_{i}+L_{i})\|m^{k+1}_{i}-m^{k}_{i}\|_{2},$
(4.1)

where $\\{c_{i}\\}^{6}_{i=4}$ are constant. From the optimality condition of
(3.4)-(3.10), the following inequalities for $i=1,2,3$ are obtained

$\displaystyle\|\partial_{m_{i}}L(u^{k+1},m^{k+1}_{1},m^{k+1}_{2},m^{k+1}_{3},n^{k+1}_{1},n^{k+1}_{2},n^{k+1}_{3})\|_{2}\leq
L_{i}\|m^{k+1}_{i}-m^{k}_{i}\|_{2},$
$\displaystyle\|\partial_{n_{i}}L(u^{k+1},m^{k+1}_{1},m^{k+1}_{2},m^{k+1}_{3},n^{k+1}_{1},n^{k+1}_{2},n^{k+1}_{3})\|_{2}\leq
L_{i}\|m^{k+1}_{i}-m^{k}_{i}\|_{2}.$

Therefore, by combining the above inequalities with (4.1), the relation (b) is
obtained. ∎

Using the above lemma, the final theorem for convergence is considered as
follows. Due to the similarity of the proof with [21], the proof is omitted.

######  Theorem 4.2.

Considering the assumptions of Lemma 4.1 and let
$\mu_{i}>(3+\sqrt{17})L_{i}/2$ for $i=1,2,3$, then
a) the sequence
$\big{(}u^{k},\\{m^{k}_{i}\\}^{3}_{i=1},\\{n^{k}_{i}\\}^{3}_{i=1}\big{)}$
generated by proposed method is bounded and has at least one limit point.
b) $\|u^{k+1}-u^{k}\|_{2}\rightarrow 0$,
$\|m^{k+1}_{i}-m^{k}_{i}\|_{2}\rightarrow 0$ and
$\|n_{i}^{k+1}-n_{i}^{k}\|_{2}\rightarrow 0$ for $i=1,2,3$.
c) each limit point
$(u^{\ast},m_{1}^{\ast},m_{2}^{\ast},m_{3}^{\ast},n_{1}^{\ast},n_{2}^{\ast},n_{3}^{\ast})$
is a stationary point of $L(u,m_{1},m_{2},m_{3},n_{1},n_{2},n_{3})$, and
$u^{\ast}$ is a stationary point of the proposed model (3.1).

##  5 Simulation results

The simulation results of the proposed algorithm that introduced in the
previous sections are studied in this section. For simulation results, a
computer based on Windows 10-64bit, Intel(R) Core(TM) i3-5005U CPU @2.00GHz,
by matlab 2014b is used. Also stopping criterion in this section is considered
as

$\displaystyle\frac{\|u^{k+1}-u^{k}\|_{2}}{\|u^{k+1}\|_{2}}\leq tol,$

where $u^{k}$ is the restored image at the $k$th iteration. In all examples,
the $tol$ equal to $10^{-3}$ is selected. In the analysis of the proposed
algorithm various tests including peak signal to noise ratio (PSNR), signal-
to-noise ratio (SNR), structural similarity (SSIM), Feature Similarity (FSIM)
and Relative Error (ReErr) are studied. More information on these criteria
value can be found in [31, 27, 15]. Also ReErr is calculated as

$\displaystyle ReErr=\frac{\|u^{k}-u\|^{2}_{2}}{\|u\|^{2}_{2}}.$

In the following examples, $M(len,\theta)$ denotes the linear motion blur of a
camera by $len$ pixels, with an angle of $\theta$ degrees in a
counterclockwise direction, $A([r_{1},r_{2}])$ shows the average blur with a
size $[r_{1},r_{2}]$, $G(hsize,\sigma)$ denotes the Gaussian blur of size
$hsize$ with standard deviation $\sigma$ (positive).

######  Example 5.1.

(Grayscale image) In this example, Algorithm 1 is used for different images
from the USC-SIPI images database222http://sipi.usc.edu/database/, i.e.,
“5.1.12 ($256\times 256$)”, “5.2.10 ($512\times 512$)” and “7.1.09 ($512\times
512$)”. Also “4.2.05” is changed to image with size ($256\times 256$) by
Matlab internal functions and used in the simulation. For images “5.1.12” and
“5.2.10”, $A([11,11])$ with “salt $\&$ pepper” and “Random-valued” noise,
respectively, with different density are used, for image “7.1.09”, blur kernel
$G(7,4)$ with “salt $\&$ pepper” noise with different densities are used.
Table 1 compares numerical results for different densities value by proposed
algorithm and method in [18]. These results indicate an improvement in the
output of the proposed algorithm. Also the blurred and noisy images for
“5.2.10” are shown in Figure 1, and the restored images corresponding to each
image are given below each image in this figure. Also in order to show the
effect of blurred kernel and noise on the image, in Figure 2 (a-d), each of
the steps of blurring by $M(35,135)$ and adding noise by “random-valued” noise
with $10\%$ density and restoring image is given separately. In this case we
have $PSNR=33.031,~{}SNR=30.241$, $SSIM=0.92600$ and $FSIM=0.99712$. The
results in this example show a good representation of the proposed algorithm.

Figure 1: (a-d) Blurred and noisy images, (e-h) restored images for 5.2.10.  Table 1: Test results for different grayscale images. imgae | density | method | PSNR | SNR | ISNR | ReErr | SSIM | FSSIM
---|---|---|---|---|---|---|---|---
| $10\%$ | Proposed | 35.741 | 33.393 | 21.702 | 0.00045781 | 0.95021 | 0.9991
5.1.12 |  | [18] | 33.682 | 31.334 | 19.55 | 0.00073556 | 0.95406 | 0.9988
| $30\%$ | Proposed | 28.344 | 25.995 | 18.746 | 0.0025146 | 0.89537 | 0.99418
|  | [18] | 27.769 | 25.421 | 13.78 | 0.00287 | 0.90592 | 0.99223
| $10\%$ | Proposed | 27.843 | 21.739 | 11.106 | 0.0067000 | 0.83063 | 0.99917
5.2.10 |  | [18] | 27.419 | 21.315 | 10.654 | 0.0073876 | 0.81419 | 0.99900
| $30\%$ | Proposed | 26.515 | 20.411 | 13.120 | 0.0090975 | 0.77559 | 0.99851
|  | [18] | 26.327 | 20.223 | 12.929 | 0.0094992 | 0.76804 | 0.99835
| $10\%$ | Proposed | 33.699 | 27.89 | 18.254 | 0.0016255 | 0.89393 | 0.99977
7.1.09 |  | [18] | 33.254 | 27.445 | 17.903 | 0.001801 | 0.88131 | 0.99976
| $30\%$ | Proposed | 32.385 | 26.576 | 21.557 | 0.0021999 | 0.86585 | 0.99963
|  | [18] | 31.707 | 25.898 | 20.87 | 0.0025715 | 0.84426 | 0.99961

######  Example 5.2.

(Color image) In this example, Algorithm 2 is studied for different color
images. In the simulation results, “Lena” $(512\times 512)$ image is blurred
by following kernel

$\displaystyle
A=\left[{\begin{array}[]{*{20}{c}}{\begin{array}[]{*{20}{c}}0.7A([15,15])\\\
0.1G(21,11)\\\ 0.0M(41,90)\\\
\end{array}}&{\begin{array}[]{*{20}{c}}0.15G(11,9)\\\ 0.8A([17,17])\\\
0.2M(21,45)\\\ \end{array}}&{\begin{array}[]{*{20}{c}}0.15G(31,13)\\\
0.1A([13,13])\\\ 0.6M(61,135)\\\ \end{array}}\\\ \end{array}}\right],$

“House” $(512\times 512)$ image is blurred by

$\displaystyle A=\frac{1}{3}diag\big{(}A([5,5]),A([7,7]),A([9,9])\big{)},$

blurred kernel for “Peppers” image $(256\times 256)$ is considered as

$\displaystyle
A=\left[{\begin{array}[]{*{20}{c}}{\begin{array}[]{*{20}{c}}0.8A([11,11])\\\
0.15A([11,11])\\\ 0.2A([11,11])\\\
\end{array}}&{\begin{array}[]{*{20}{c}}0.1G(11,5)\\\ 0.7G(11,5)\\\
0.2G(11,5)\\\ \end{array}}&{\begin{array}[]{*{20}{c}}0.1M(21,135)\\\
0.15M(21,135)\\\ 0.6M(21,135)\\\ \end{array}}\\\ \end{array}}\right],$

and finally blurred kernel $A=B\otimes M(41,135)$ is used for “Plate” with
size ($256\times 256$), where

$\displaystyle
A=\left[{\begin{array}[]{*{20}{c}}{\begin{array}[]{*{20}{c}}0.8\\\ 0.15\\\
0.2\\\ \end{array}}&{\begin{array}[]{*{20}{c}}0.1\\\ 0.7\\\ 0.2\\\
\end{array}}&{\begin{array}[]{*{20}{c}}0.1\\\ 0.15\\\ 0.6\\\ \end{array}}\\\
\end{array}}\right].$

Also for the noise process, “salt $\&$ pepper” noise is used for “Lena”,
“House” and “Plate” images and “random-valued” noise is used for “Peppers”
image. Table 2 compares the results of the proposed method with the results of
the algorithms in [30] and [20]. Other results are also given in Table 3 for
test images. The results show the efficiency of the proposed algorithm in
comparison with these algorithms. Also, the proposed algorithm outputs for
different images with different noise densities are given in Figures 3-5.
Figure 2 (e-h) shows the effect of the blurred kernel and noise on the color
image. In this results “salt $\&$ pepper” noise with $30\%$ density is used.
Test results for this case are included $PSNR=28.871$, $SNR=27.049$,
$ISNR=20.636$, $ReErr=0.0019729$, $SSIM=0.9535$ and $FSIM=0.99884$.

Figure 2: (a,e) Original images, (b,f) blurred images, (c,g) blurred and noisy images, (d,h) restored images.  Table 2: Test results for different color images. | density | $10\%$ | $20\%$ | $30\%$ | $40\%$
---|---|---|---|---|---
imgae | method | SNR | SSIM | SNR | SSIM | SNR | SSIM | SNR | SSIM
| Proposed | 27.23 | 0.9620 | 26.83 | 0.9591 | 26.04 | 0.9524 | 24.04 | 0.9348
House | [30] | 22.70 | 0.9103 | 22.33 | 0.9045 | 22.08 | 0.9027 | 21.61 | 0.8904
| [20] | 25.54 | 0.9185 | 24.57 | 0.9071 | 23.36 | 0.9024 | 22.58 | 0.8876
| Proposed | 25.15 | 0.9744 | 24.96 | 0.9734 | 24.66 | 0.9717 | 24.33 | 0.9699
Lena | [30] | 23.50 | 0.8831 | 23.48 | 0.8841 | 23.87 | 0.8907 | 23.71 | 0.8864
| [20] | 25.12 | 0.9035 | 24.48 | 0.8941 | 23.88 | 0.8860 | 23.90 | 0.8856
| Proposed | 26.34 | 0.9895 | 25.80 | 0.9877 | 24.49 | 0.9826 | 20.43 | 0.9547
Peppers | [30] | 22.34 | 0.8530 | 21.79 | 0.8379 | 20.88 | 0.8208 | 19.88 | 0.7941
| [20] | 23.85 | 0.8681 | 22.88 | 0.8504 | 21.73 | 0.8302 | 20.39 | 0.7982
Figure 3: (a-d) Blurred and noisy images, (e-h) restored images for Lena $(512\times 512)$.  Figure 4: (a-d) Blurred and noisy images, (e-h) restored images for Peppers $(256\times 256)$.  Figure 5: (a-d) Blurred and noisy images, (e-h) restored images for Househ $(512\times 512)$.  Table 3: Test results for different grayscale images with different noise densities. imgae | density | ISNR | ReErr | FSIM
---|---|---|---|---
| $10\%$ | 24.054 | 0.0018923 | 0.99976
House | $20\%$ | 23.907 | 0.0020754 | 0.99973
| $30\%$ | 23.342 | 0.0024927 | 0.99965
| $40\%$ | 21.567 | 0.0039502 | 0.99947
| $10\%$ | 16.234 | 0.0030536 | 0.99914
Lena | $20\%$ | 18.433 | 0.0031943 | 0.99908
| $30\%$ | 19.703 | 0.0034223 | 0.99898
| $40\%$ | 20.507 | 0.0036912 | 0.99886
| $10\%$ | 16.785 | 0.0023246 | 0.99724
Peppers | $20\%$ | 17.983 | 0.0026354 | 0.99716
| $30\%$ | 17.946 | 0.0035549 | 0.99689
| $40\%$ | 14.841 | 0.0090734 | 0.99597

##  6 Conclusion

In this paper the nonconvex model based on fractional-order total variation
and framelet transfer is introduced for image restoration. The proposed model
is solved by ADMM and primal-dual methods. In the analysis of the proposed
algorithm convergence analysis is studied and simulation results are
evaluated. The results have been compared with other methods and these results
show the efficiency of the proposed algorithm in restoring images that have
been damaged due to blur and noise.

## References

  * [1] Adam, Tarmizi, and Raveendran Paramesran. Hybrid non-convex second-order total variation with applications to non-blind image deblurring. Signal, Image and Video Processing 14, no. 1 (2020): 115-123.
  * [2] Bioucas-Dias, José M., Mário AT Figueiredo, and Joao P. Oliveira. Adaptive total variation image deconvolution: A majorization-minimization approach. In 2006 14th European Signal Processing Conference, pp. 1-4. IEEE, 2006.
  * [3] Cai, Jian-Feng, Jae Kyu Choi, Jingyang Li, and Ke Wei. Image restoration: Structured low rank matrix framework for piecewise smooth functions and beyond. Applied and Computational Harmonic Analysis 56 (2022): 26-60.
  * [4] Cai, Jian-Feng, Stanley Osher, and Zuowei Shen. Split Bregman methods and frame based image restoration. Multiscale modeling $\&$ simulation 8, no. 2 (2010): 337-369.
  * [5] Chen, Scott Shaobing, David L. Donoho, and Michael A. Saunders. Atomic decomposition by basis pursuit. SIAM review 43, no. 1 (2001): 129-159.
  * [6] De Oliveira, Edmundo Capelas, and José António Tenreiro Machado. A review of definitions for fractional derivatives and integral. Mathematical Problems in Engineering 2014 (2014).
  * [7] Dong, Bin, Hui Ji, Jia Li, Zuowei Shen, and Yuhong Xu. Wavelet frame based blind image inpainting. Applied and Computational Harmonic Analysis 32, no. 2 (2012): 268-279.
  * [8] Dong, Fangfang, and Yunmei Chen. A fractional-order derivative based variational framework for image denoising. Inverse Problems $\&$ Imaging 10, no. 1 (2016): 27.
  * [9] Dong, Fangfang, and Qianting Ma. Single image blind deblurring based on the fractional-order differential. Computers $\&$ Mathematics with Applications 78, no. 6 (2019): 1960-1977.
  * [10] Esser, Ernie, Xiaoqun Zhang, and Tony Chan. A general framework for a class of first order primal-dual algorithms for TV minimization. Ucla Cam Report 9 (2009): 67.
  * [11] Han, Bin. Framelets and wavelets. In Algorithms, Analysis, and Applications, Applied and Numerical Harmonic Analysis. Birkhäuser xxxiii Cham, 2017.
  * [12] Han, Bin. Properties of discrete framelet transforms. Mathematical Modelling of Natural Phenomena 8, no. 1 (2013): 18-47.
  * [13] He, Yiyang, Hongli Wang, Lei Feng, and Sihai You. Motion-blurred star image restoration based on multi-frame superposition under high dynamic and long exposure conditions. Journal of Real-Time Image Processing 18, no. 5 (2021): 1477-1491.
  * [14] Jing, Yu, Jianxin Liu, Zhaoxia Liu, and Hongju Cao. Fast edge detection approach based on global optimization convex model and split Bregman algorithm. Diagnostyka 19 (2018).
  * [15] Kumar, Rohit, and Vishal Moyal. Visual image quality assessment technique using fsim. International Journal of Computer Applications Technology and Research 2, no. 3 (2013): 250-254.
  * [16] Li, Bo, and Wei Xie.  Adaptive fractional differential approach and its application to medical image enhancement. Computers $\&$ Electrical Engineering 45 (2015): 324-335.
  * [17] Li, Dongming, Changming Sun, Jinhua Yang, Huan Liu, Jiaqi Peng, and Lijuan Zhang. Robust multi-frame adaptive optics image restoration algorithm using maximum likelihood estimation with poisson statistics. Sensors 17, no. 4 (2017): 785.
  * [18] Liu, Jingjing, Anqi Ni, and Guoxi Ni. A nonconvex l1(l1-l2) model for image restoration with impulse noise. Journal of Computational and Applied Mathematics 378 (2020): 112934.
  * [19] Liu, Jingjing, Ruijie Ma, Xiaoyang Zeng, Wanquan Liu, Mingyu Wang, and Hui Chen. An efficient non-convex total variation approach for image deblurring and denoising. Applied Mathematics and Computation 397 (2021): 125977.
  * [20] Liu, Jun, Ting-Zhu Huang, Xiao-Guang Lv, and Jie Huang. Restoration of blurred color images with impulse noise. Computers $\&$ Mathematics with Applications 70, no. 6 (2015): 1255-1265.
  * [21] Lou, Yifei, and Ming Yan. Fast L1-L2 minimization via a proximal operator. Journal of Scientific Computing 74, no. 2 (2018): 767-785.
  * [22] Love, Eric Russell. Fractional derivatives of imaginary order. Journal of the London Mathematical Society 2, no. 2 (1971): 241-259.
  * [23] Mistakidis, Euripidis S., and Georgios E. Stavroulakis. Nonconvex optimization in mechanics: algorithms, heuristics and engineering applications by the FEM. Vol. 21. Springer Science $\&$ Business Media, 2013.
  * [24] Oliveira, Joao P., José M. Bioucas-Dias, and Mário AT Figueiredo. Adaptive total variation image deblurring: a majorization–minimization approach. Signal processing 89, no. 9 (2009): 1683-1693.
  * [25] Rudin, Leonid I., Stanley Osher, and Emad Fatemi. Nonlinear total variation based noise removal algorithms. Physica D: nonlinear phenomena 60, no. 1-4 (1992): 259-268.
  * [26] Sajjad, Muhammad, Irfan Mehmood, Naveed Abbas, and Sung Wook Baik. Basis pursuit denoising-based image superresolution using a redundant set of atoms. Signal, Image and Video Processing 10, no. 1 (2016): 181-188.
  * [27] Sara, Umme, Morium Akter, and Mohammad Shorif Uddin. Image quality assessment through FSIM, SSIM, MSE and PSNR-a comparative study. Journal of Computer and Communications 7, no. 3 (2019): 8-18.
  * [28] Shen, Yi, Bin Han, and Elena Braverman. Image inpainting from partial noisy data by directional complex tight framelets. The ANZIAM Journal 58, no. 3-4 (2017): 247-255.
  * [29] Setzer, Simon. Split Bregman algorithm, Douglas-Rachford splitting and frame shrinkage. In International Conference on Scale Space and Variational Methods in Computer Vision, pp. 464-476. Springer, Berlin, Heidelberg, 2009.
  * [30] Tao, Min, Junfeng Yang, and Bingsheng He. Alternating direction algorithms for total variation deconvolution in image reconstruction. TR0918, Department of Mathematics, Nanjing University (2009).
  * [31] Wang, Zhou, Alan C. Bovik, Hamid R. Sheikh, and Eero P. Simoncelli. Image quality assessment: from error visibility to structural similarity. IEEE transactions on image processing 13, no. 4 (2004): 600-612.
  * [32] Yang, Jingjing, Yingpin Chen, and Zhifeng Chen. Infrared Image Deblurring via High-Order Total Variation and Lp-Pseudonorm Shrinkage. Applied Sciences 10, no. 7 (2020): 2533.
  * [33] Zhang, Yi, Weihua Zhang, Yinjie Lei, and Jiliu Zhou. Few-view image reconstruction with fractional-order total variation. JOSA A 31, no. 5 (2014): 981-995.
  * [34] Zhu, Mingqiang, and Tony Chan. An efficient primal-dual hybrid gradient algorithm for total variation image restoration. UCLA CAM Report 34 (2008): 8-34.
  * [35] Zifan, Ali, and Panos Liatsis. Medical image deblurring via lagrangian pursuit in frame dictionaries. In 2011 Developments in E-systems Engineering, pp. 86-91. IEEE, 2011.
  * [36] Zou, Jian, Haifeng Li, and Guoqi Liu. Split Bregman algorithm for structured sparse reconstruction. IEEE Access 6 (2018): 21560-21569.