Adaptive Thiele interpolation

Oliver Salazar Celis

ING Belgium

Brussels, Belgium 1000

The current implementation of Thiele rational interpolation in Maple (the  routine) breaks down when the points are not well-ordered. In this article, it is shown how this breakdown can be avoided by ordering the interpolation points in an adaptive way.

§ INTRODUCTION

Maple provides  univariate rational interpolation functionality using the  routine from the  toolbox.
Given $n+1$ distinct complex points $x_0,x_1,\ldots,x_n$ together with finite function valuations $f(x_i)=f_i$ ($i=0,\ldots,n$), this routine produces a continued fraction of the form

\begin{equation} \label{eqn:thiele}
C_n(x) =  \textstyle \contFrac*{  \varphi_0[x_0]  //  x- x_{0} // \varphi_1[x_0,x_1] // x- x_{1} // \varphi_2[x_0,x_1,x_2] // x- x_{2} // \dots // x- x_{n-1}  // \varphi_n[x_0,\ldots,x_n]},
\end{equation}

where the inverse differences $\varphi_i[x_0,\ldots,x_i]$ ($i=0,\ldots,n$) are obtained from the recursion

\begin{equation} \label{eqn:invdif}
\left\{
\begin{aligned}
\varphi_0[x_k] &= f_k \qquad &k \geq 0 \\
\varphi_{i+1}[x_0,\ldots,x_i,x_k] &= \frac{x_k-x_i}{\varphi_{i}[x_0,\ldots,x_{i-1},x_k]-\varphi_{i}[x_0,\ldots,x_i]}\qquad &k > i
\end{aligned}
\right.  .
\end{equation}

It is well-known [1] that the construction of the inverse differences depends on the order in which the points $x_i$ are taken to constuct (<ref>).
In some cases, one indeed encounters $\varphi_{i}[x_0,\ldots,x_i] = \infty$ due to division by zero in the recursion (<ref>). This does not mean that the problem itself does not have a solution; a simple reordering of the points can typically resolve this.  The documentation of the  routine warns the user for this situation, but rather than a reordering suggests a perturbation of the points.
When division by zero is encountered a message as below is shown

It is not convenient to leave it up to the user to add perturbations or to reorder the points manually by trial and error. In this article we show that an ordering exists that ensures the existence of the interpolating Thiele continued fraction (<ref>), meaning $\varphi_{i}[x_0,\ldots,x_i] \neq \infty$.

§ ADAPTIVE SELECTION

The documentation of the  routine already hints to cases to avoid: For example, a division-by-zero error is produced when two successive points have the same dependent value or when three successive points are collinear. We can formalize this observation in the following Theorem.

If the distinct points $(x_i)_{0 \leq i \leq n}$ are ordered such that every two consecutive convergents of the continued fraction (<ref>) are different, then $\varphi_{i}[x_0,\ldots,x_i]  \neq \infty$.

For a proof, we refer to <cit.> where it is shown that the inverse differences can essentially be interpreted as the ratio of two (linearized) residuals of successive convergents up to some non-zero factor.

In light of Theorem <ref>, the division-by-zero error is avoided if the continued fraction (<ref>) can be constructed in such a way that every two consecutive convergents are different.
One way to achieve this, is to choose the next point $x_{i+1}$ in the construction of $C_{i+1}(x)$ with $0<i < n$ such that the current convergent $C_i(x)$ does not interpolate in $x_{i+1}$, i.e. $C_{i}(x_{i+1}) \neq f_{i+1}$. Hence, given $C_{i}(x)$ and $(x_0,\ldots,x_i)$, we propose to reorder the remaining points $(x_{i+1}, \ldots,x_n)$ and determine $C_{i+1}(x)$ such that
$|C_i(x_{i+1}) -f(x_{i+1})|$ is maximal. In this way, $C_n(x)$ is ultimate constructed in an adaptive greedy way by choosing in each step the point where for $0<i<n$ the error between $C_{i}(x)$   and $f(x)$ is maximal. The next theorem shows that this strategy indeed succeeds in the avoidance of infinite inverse differences occurring in (<ref>).

If the distinct points $(x_i)_{0 \leq i \leq n}$ are ordered using a strategy where in each step $C_j(x_{j+1}) \neq f(x_{j+1})$ with $0 \leq j < n$
then every two consecutive convergents of the continued fraction (<ref>) are different and $\varphi_{i}[x_0,\ldots,x_i]  \neq \infty$.

The proof is by induction. Let $x_0$ be chosen with $f(x_i) \neq \infty$ and take $x_1$ such that $f(x_0) \neq f(x_1)$. Then from (<ref>) we have $\varphi_0[x_0] = f(x_0) \neq \infty$ and
$\varphi_1[x_0,x_1] = (x_1 - x_0)/ \left( f(x_1) - f(x_0)\right) \neq \infty$. Clearly, also $C_0(x) = \varphi_0[x_0] \not \equiv C_1(x) = \varphi_0[x_0] + (x-x_0)/\varphi_1[x_0,x_1]$.
Assume that the hypothesis holds up to $0< j< n$. We show further below that this necessarily means that $\varphi_{j+1}[x_0,\ldots,x_{j+1}] \neq \infty$, but momentarily we take it for granted.
Then assume by contradiction that for some $0< j< n$,

C_j(x) = \frac{A_j(x)}{B_j(x)} \, \equiv  \, C_{j+1}(x) = \frac{A_{j+1}(x)}{B_{j+1}(x)}

where for $0 \leq i \leq n$ the numerators $A_i(x)$ and denominators $B_i(x)$ satisfy the recurrence relation [6]

\begin{equation} \label{eqn:3term}
\left(
\begin{aligned}
A_i(x) \\
\end{aligned}
\right)
\begin{aligned}
\varphi_{i}[x_0,\ldots,x_i]  A_{i-1}(x) +(x-x_{i-1})A_{i-2}(x)\\
\varphi_{i}[x_0,\ldots,x_i]  B_{i-1}(x) +(x-x_{i-1})B_{i-2}(x)
\end{aligned}
\right),
\end{equation}

\left\{
\begin{aligned}
A_{-2}(x) = 0, & \qquad B_{-2}(x) = 1 \\
A_{-1}(x) = 1, & \qquad B_{-1}(x) = 0 \\
A_{0}(x) = \varphi_{0}[x_0] = f(x_0), &\qquad  B_{0}(x) = 1
\end{aligned}
\right. .

This implies that the polynomial $\left[ A_jB_{j+1} -A_{j+1}B_{j}\right](x) \equiv 0$.  However, by construction

-\left[ f(x_{j+1})B_j(x_{j+1}) -A_j(x_{j+1}) \right] B_{j+1}(x_{j+1}) + \left[ f(x_{j+1})B_{j+1}(x_{j+1}) -A_{j+1}(x_{j+1}) \right] B_{j}(x_{j+1})  \neq 0

because neither $f(x_{j+1})B_j(x_{j+1}) -A_j(x_{j+1}) \neq 0$ nor $B_{j+1}(x_{j+1}) \neq 0$.
Of these last two inequalities, the first one follows from the selection of $x_{i+1}$ with $C_j(x_{j+1}) \neq f(x_{j+1})$ and the fact that the only common factors of $A_j(x)$ and $B_j(x)$ can be interpolation points used so far (see for instance [2]). For the second inequality,
if it was true that $B_{j+1}(x_{j+1}) = 0$, then necessarily also $A_{j+1}(x_{j+1}) = 0$.
On the other hand (<ref>) can be written as

\begin{equation} \label{eqn:matrix}
\begin{pmatrix}
A_{j+1}(x) \\
\end{pmatrix}
\prod_{k=0}^{j}
\begin{pmatrix}
\varphi_{k}[x_0,\ldots,x_k] 	& x-x_k \\
1    & 0
\end{pmatrix}
\begin{pmatrix}
\varphi_{j+1}[x_0,\ldots,x_{j+1}] \\
\end{pmatrix}.
\end{equation}

Since $x_{j+1} \neq x_k$ for $k=0,\ldots,j$, none of the matrices in (<ref>) are singular when putting $x= x_{j+1}$, hence we can write

\begin{equation}\label{eqn:matrixinv}
\begin{pmatrix}
\varphi_{j+1}[x_0,\ldots,x_{j+1}] \\
\end{pmatrix}
\prod_{k=j}^{0}
\begin{pmatrix}
0 	& 1 \\
1/(x_{j+1}-x_k)    & - \varphi_{k}[x_0,\ldots,x_k]/(x-x_k)
\end{pmatrix}
\begin{pmatrix}
A_{j+1}(x_{j+1}) \\
\end{pmatrix}.
\end{equation}

But if  $B_{j+1}(x_{j+1}) = A_{j+1}(x_{j+1}) = 0 $, then the right-hand side of (<ref>) cannot equal the left-hand side. Therefore $B_{j+1}(x_{j+1}) \neq  0$.

What remains to be shown is that $\varphi_{j+1}[x_0,\ldots,x_{j+1}] =  \infty$ cannot occur. Else from (<ref>) and the induction hypothesis we have $\varphi_{j}[x_0,\ldots,x_{j-1},x_{j+1}]= \varphi_{j}[x_0,\ldots,x_i]\neq \infty$. From application of <cit.> we can then write

\varphi_{j}[x_0,\ldots,x_{i-1},x_{j+1}] = - (x_{j+1}- x_{j-1}) \frac{f(x_{j+1})B_{j-2}(x_{j+1}) -A_{j-2}(x_{j+1}) }{f(x_{j+1})B_{j-1}(x_{j+1}) -A_{j-1}(x_{j+1}) } \neq \infty.

Hence, necessarily  $f(x_{j+1})B_{j-1}(x_{j+1}) -A_{j-1}(x_{j+1}) \neq 0$ so that application of <cit.> is also allowed for $\varphi_{j+1}[x_0,\ldots,x_{j+1}] $ and we have

\begin{equation} \label{eqn:frac}
\varphi_{j+1}[x_0,\ldots,x_{j+1}] = - (x_{j+1}- x_j) \frac{f(x_{j+1})B_{j-1}(x_{j+1}) -A_{j-1}(x_{j+1}) }{f(x_{j+1})B_{j}(x_{j+1}) -A_{j}(x_{j+1}) }.
\end{equation}

But, similarly as before, due to the selection $C_j(x_{j+1}) \neq f(x_{j+1})$, the denominator of (<ref>) does not vanish and therefore also $\varphi_{j+1}[x_0,\ldots,x_{j+1}] \neq \infty$.

Remark 1. Theorem <ref> does not require the selection of the interpolation points to be greedy per se.
Nevertheless, from a numerical point of view it remains important to construct the interpolant in as few steps as possible [1].
A greedy selection is a heuristic way to such an end. The AAA  approach [3] for instance also employs such a strategy; the motivation there is not existence but rather for numerical purposes. The remaining freedom is in the choice of the first point $x_0$. One option is to take a point where $|f(x_0)|$ is minimum. As such, at least one zero of $f(x)$ is exactly represented when present in the data.

Remark 2. Theorem <ref> ensures that $\varphi_{i}[x_0,\ldots,x_i]  \neq \infty$ for those inverse differences appearing in (<ref>).
This does not exclude the possibility that $\varphi_{i}[x_0,\ldots,x_i] =0$, nor does it prevent intermediate occurrence of $\varphi_{i+1}[x_0,\ldots,x_i,x_k] = \infty$ for $k>i+1$ in (<ref>).
Such intermediate non-finite values are not necessarily a concern to continue the recursion (<ref>) using the IEEE 754 standard.
In fact, they are necessary for the occurrence of $\varphi_{i}[x_0,\ldots,x_i] =0$. Such cases are also of no particular concern unless $i=n$, that is, if it occurs for the last inverse difference in $C_n(x)$. This situation can be avoided by adding a stopping criterion when constructing $C_n(x)$. If the maximum absolute error in the remaining points is below a prescribed tolerance, say , then the recursion is stopped. One way to implement this is

\max |C_i(x_{k}) -f(x_{k})| < \text{tol} \times \max_{i<j\leq n}(|f(x_j)|) \qquad  \text{for } i < k \leq n.

Essentially it means that, up to the prescribed tolerance,  the underlying function appears rational and there is no further accuracy  gain to be made by adding more interpolation points.

§ NUMERICAL EXAMPLE

An important result in rational approximation theory is due to Newman [4],
where it is shown that rational approximations can achieve root-exponential convergence $\mathcal{O}(\exp(-C \sqrt{n})$  (with $C>0$) for $f(x) = |x|$ with $x \in [-1,1]$.
This is much faster than what can be achieved with polynomials which converge at an algebraic rate $\mathcal{O}(n^{-1})$ at best.

The aim of this example is to construct Newman approximations, which are rational interpolants to $f(x) = |x|$ in the $2n+1$ points

\begin{equation} \label{newpoints}
(-1, -\eta,\ldots,-\eta^{n-1}, 0, \eta^{n-1},\ldots, 1), \qquad \text{with } \eta = e^{-1/\sqrt{n}}.
\end{equation}

The below Maple code sets up the interpolation data and calls the  routine
>with(ArrayTools); with(CurveFitting);
>N := 5;
>xleft := j -> -(exp(-1/sqrt(N)))^(j-1);
>xright:= j -> (exp(-1/sqrt(N)))^(N-j);
>xdata := Concatenate(1, Vector(N, xleft), 0, Vector(N, xright));
>ydata := Vector(2*N+1, j-> abs(xdata[j]));
>ThieleInterpolation(xdata, ydata, x)

Because the  routine takes the points (<ref>) from left to right, this leads to the division-by-zero error
This is not surprising because the first points (defined by ) basically lie on the line $y = -x$ which is already reconstructed by $C_1(x) = -x$ from the first two points.
Hence this implementation will fail for any $n>0$.

$\|f(x) - C_{2n}(x) \|_\infty$ on $x \in [-1,1] $

$\| \left( f(x_i)- C_{2n}(x_i) \right)_{0\leq i \leq 2n} \|_2$

Adaptive Thiele interpolation of $f(x) =|x|$ in Newman points (<ref>)  for various $n=5,\ldots,50$.  Left: (discrete) maximum error on $[-1,1]$.
Right: 2-norm of the interpolation error in the Newman interpolation points (<ref>).

The situation is completely different when applying the adaptive Thiele interpolation approach.
A prototype Maple implementation of the greedy strategy is given in Appendix <ref>.

Figure <ref> shows the maximum error on $[-1,1]$ obtained from Thiele interpolation of $f(x) = |x|$ in Newman points (<ref>) for $n=5,\ldots,50$.
All obtained interpolants use all interpolation points in their construction, meaning that for $n=50$ we have $2n+1 = 101$ interpolation points and we construct $C_{2n}(x) = C_{100}(x)$.
The root-exponential behavior is clearly visible as a downward sloping straight line when plotting on log10 scale in function of $\sqrt{n}$.
The maximum error is calculated on a discrete grid of $10000$ points between $0$ and $0.01$ (the maximum error of these interpolants typically occurs near $x=0$ where $f(x) = |x|$ is not differentiable). This discretization gives the impression that convergence is slower for odd $n$ than for even $n$. In fact, odd values of $n$ give approximations with poles in $[-1,1]$, while the even $n$ approximations are pole-free. These observations are in line with those observed in the recent AAA approach <cit.>.

For this run we have put  to mimic (software) floating-point precision. Recall that by default Maple uses . As shown in Figure <ref> the interpolation error in the Newman points remains highly accurate.

§ CONCLUDING REMARKS

We have shown how the breakdown in the  routine can be avoided using an adaptive ordering of the interpolation points.
This actually renders Thiele interpolation into a practical tool for rational interpolation. Particularly when also their poles and zeros can be calculated in a simple fashion as shown in [5].

§ MAPLE CODES

The ideas above are implemented in Maple with the below prototype code. Mind that the stopping condition is not included here.
restart; with(ArrayTools); with(ListTools); with(LinearAlgebra);

cfrac_eval := proc (aa, zz, xx)
description "evaluate continued fraction";
local N, res, i;
N   := Dimension(aa);
res := Vector(Dimension(xx), 0);
for i from N by -1 to 2 do
res := zip(`/`, ` `[`-`](xx, zz[i-1]), ` `[`+`](aa[i], res))
end do;
return( ` `[`+`](aa[1], res) )
end proc

cfrac_interpolate := proc (xx, ff)
description "adaptive continued fraction interpolation";
local N, rr, k, aa, zz, i, indx_keep, x, f;
x := xx; f := ff; N := Dimension(xx);
NumericEventHandler(division_by_zero = default);
for k to N do
if k = 1 then
rr := f; i := min[index](abs(rr));
aa := Vector(1, rr[i]); zz := Vector(1, x[i])
i := max[index](abs(cfrac_eval(aa, zz, x)-f));
rr := zip(`/`, ` `[`-`](x, zz[k-1]), ` `[`-`](rr, aa[k-1]));
aa := Append(aa, rr[i]); zz := Append(zz, x[i])
end if;
indx_keep := subsop(i = NULL, [seq(1 .. Dimension(x))]);
x := x[indx_keep];
f := f[indx_keep];
rr := rr[indx_keep]
end do;
return Concatenate(2, aa, zz)
end proc

These procedure can then for instance be called on the previous Newman example.
>coefs := cfrac_interpolate(evalf(xdata), evalf(ydata))
>x := evalf(`<,>`(seq((1/1000)*i, i = -1000 .. 1000)));
>plot(x, cfrac_eval(Column(coefs, 1), Column(coefs, 2), x))

[1]
Annie A.M. Cuyt, Lisa Jacobsen, and Brigitte M. Verdonk.
Instability and modification of Thiele interpolating continued
Applied Numerical Mathematics, 4(2):253–262, 1988.

[2]
P. R. Graves-Morris.
Practical, Reliable, Rational Interpolation.
IMA Journal of Applied Mathematics, 25(3):267–286, 1980.

[3]
Y. Nakatsukasa, Olivier Sète, and L. Trefethen.
The AAA algorithm for rational approximation.
SIAM Journal on Scientific Computing, 40:1494–1522, 2018.

[4]
D. J. Newman.
Rational approximation to $| x| $.
Michigan Mathematical Journal, 11(1):11–14, 1964.

[5]
Oliver Salazar Celis.
Numerical continued fraction interpolation.
https://arxiv.org/abs/2109.10529, 2021.

[6]
John Wallis.
Arithmetica Infinitorum.


#  Regular graphs to induce even periodic Grover walks

Sho Kubota  Department of Information Systems, Faculty of Information Science
and Technology, Osaka Institute of Technology, Osaka 573-0196, Japan.
<EMAIL_ADDRESS>Hiroto Sekido  Graduate School of Environment Information
Sciences, Yokohama National University, Hodogaya, Yokohama 240-8501 Japan.
<EMAIL_ADDRESS>Kiyoto Yoshino  Department of Computer Science,
Faculty of Applied Information Science, Hiroshima Institute of Technology,
Saeki Ward, Hiroshima, 731-5143, Japan<EMAIL_ADDRESS>
###### Abstract

The interest of this paper is a characterization of graphs that induce
periodic Grover walks with given periods. In previous studies, Yoshie has
shown that the only graphs that induce odd periodic Grover walks are cycle
graphs. However, this problem is largely unsolved for even periods. In this
study, we show that regular graphs that induce $2l$-periodic Grover walks are
also cycle graphs in most cases, where $l$ is an odd integer. The proof uses
Galois theory.
Keywords: Grover walk, quantum walk, periodicity, cyclotomic field
MSC 2020 subject classifications: 81Q99; 05C50

##  1 Introduction

Quantum walks are the quantum mechanical counterpart of classical random
walks. Quantum walks are a type of quantum algorithm that has received
significant attention in recent years due to their potential for use in a
variety of applications, such as optimization [13], search [1], and simulation
[12].

One of the interesting properties of quantum walks is periodicity. It refers
to a phenomenon that quantum states return to their initial states at a
certain number of steps, which can occur due to the circumstance that the time
evolution matrix of a quantum walk is unitary. Recently, Panda and Benjamin
proposed a quantum cryptographic protocol focusing on periodicity of quantum
walks [11], and applications of periodicity have also attracted attention.

The model treated in this paper is the Grover walk, which is a typical
discrete-time quantum walk on a graph. A notable feature of Grover walks is
that it is defined from a graph alone. Not all graphs induce a periodic Grover
walk, but rather such graphs are rare. Hence, we are interested in
characterizing graphs that induce periodic Grover walks. The typical study of
periodicity is to characterize graphs in a specific graph class [7, 8, 9, 15].
On the other hand, there is also the point of view of characterizing graphs
that induce a given period, and such studies have been carried out by Yoshie
[14, 16]. An interesting result he showed is that the graphs to induce odd
periods are cycle graphs only [16]. We attempt to develop the work he has done
and focus on even periods. The even-periodic graphs have not been
characterized except for $2$-periodic and $4$-periodic graphs. Graphs that
induce $6$ and $8$ periods distinct from cycle graphs are constructed in [14].
In this study, we restrict graphs we treat to regular graphs and show that
regular graphs that induce $2l$-periodic Grover walks are also only cycle
graphs in many cases, where $l$ is an odd integer. More precisely, we show the
following. See later sections for definitions and terminologies.

######  Theorem 1.1.

Let $G$ be a $k$-regular graph, and let $l$ be an odd integer. If $G$ is a
$2l$-periodic graph, then one of the following holds.

  1. (1)

$G$ is the cycle graph $C_{2l}$ with $2l$ vertices.

  2. (2)

$k=3$ and $l$ is a multiple of $3$.

We remark that this theorem implies if $l$ is not a multiple of $3$, then the
$2l$-periodic regular graph is the cycle graph $C_{2l}$ only.

This paper is organized as follows. Section 2 is mainly preparation. Terms and
facts on spectral graph theory and Grover walks are introduced. In Section 3,
we determine the $6$-periodic regular graphs by combining some results of
previous studies. In Section 4, we derive our main theorem (Theorem 1.1). We
study $2l$-periodic regular graphs, where $l$ is an odd integer, by using the
Galois group of cyclotomic fields. Section 5 summarizes this paper and
introduces several open problems.

##  2 Preliminaries

###  2.1 Graphs

Let $G=(V,E)$ be a finite, simple, connected, and undirected graph with vertex
set $V$ and edge set $E$. For $x,y\in V$, let $xy$ denote the _directed_ edge
$(x,y)\in V\times V$ from $x$ to $y$. Also define $\mathcal{A}=\mathcal{A}(G)$
as the set $\\{xy,yx\mid\\{x,y\\}\in E\\}$. Let $a=xy\in\mathcal{A}$ be a
directed edge. Let $a^{-1}$ denote the directed edge $yx$. Let $o(a)$ and
$t(a)$ be the _origin_ $x$ and _terminus_ $y$ of $a$, respectively. The
_degree_ of a vertex $x\in V$ for a graph $G$ is written as $\deg_{G}x$. The
_adjacency matrix_ $A=A(G)\in\mathbb{C}^{V\times V}$ of a graph $G$ is defined
by

$A_{x,y}=\begin{cases}1&\\{x,y\\}\in E,\\\ 0&\text{otherwise}.\end{cases}$

We define the _degree matrix_ $D=D(G)\in\mathbb{C}^{V\times V}$ as
$D_{x,y}=(\deg_{G}x)\delta_{x,y}$, where $\delta_{x,y}$ is Kronecker’s delta.
Define the matrix $T=T(G)\in\mathbb{C}^{V\times V}$ by

$T=D^{-\frac{1}{2}}AD^{-\frac{1}{2}}.$

In particular, $T=\frac{1}{k}A$ holds if the graph $G$ is $k$-regular. Note
that the diagonal entries of $T$ are always zero, so the sum of the
eigenvalues is zero, i.e.,

$\operatorname{tr}T=0.$ (1)

We denote by $\operatorname{Spec}(P)$ the multiset of eigenvalues of a matrix
$P$, specifying eigenvalues on the first line and respective multiplicities on
the second line as follows.

$\displaystyle\operatorname{Spec}(P)=\begin{bmatrix}\lambda_{0}&\lambda_{1}&\cdots&\lambda_{l-1}&\lambda_{l}\\\
a_{0}&a_{1}&\cdots&a_{l-1}&a_{l}\end{bmatrix}.$

###  2.2 Grover walks

In this section, we provide the definitions of the time evolution matrix of a
Grover walk and its periodicity, and introduce the spectral mapping theorem.
Let $G$ be a graph, and set $\mathcal{A}=\mathcal{A}(G)$. Then the time
evolution matrix $U=U(G)\in\mathbb{C}^{\mathcal{A}\times\mathcal{A}}$ of the
Grover walk over $G$ is defined by

$U_{a,b}=\begin{cases}\frac{2}{\deg_{G}t(b)}-1&a=b^{-1},\\\
\frac{2}{\deg_{G}t(b)}&t(b)=o(a)\text{ and }a\neq b^{-1},\\\ 0&t(b)\neq
o(a).\end{cases}$

Let $\varphi_{0}\in\mathbb{C}^{\mathcal{A}}$ be an initial state of the Grover
walk. Then, the state $\varphi_{t}$ at time $t$ is expressed as
$\varphi_{t}=U^{t}\varphi_{0}$. Let
$I_{\mathcal{A}}\in\mathbb{C}^{\mathcal{A}}$ be the identity matrix. If there
exists $\tau\in\mathbb{N}$ such that $U^{\tau}=I_{\mathcal{A}}$, then we say
that the graph $G$ is _periodic_ and the minimum $\tau$ is _period_. Such a
graph is also called a $\tau$-periodic graph.

######  Theorem 2.1 ([10, Lemma 5.3]).

Let $G$ be a graph, and let $U$ be the time evolution matrix of $G$. Then, $G$
is periodic if and only if there exists $\tau\in\mathbb{N}$ such that
$\lambda^{\tau}=1$ for any $\lambda\in\operatorname{Spec}(U)$.

Next, we state a theorem known as the spectral mapping theorem of Grover
walks.

######  Theorem 2.2 ([6]).

Let $G=(V,E)$ be a connected graph. The multiset of eigenvalues of the time
evolution matrix $U=U(G)$ is expressed as follows.

$\operatorname{Spec}(U)=\\{e^{\pm
i\arccos(\lambda_{T})}|\lambda_{T}\in\operatorname{Spec}(T)\\}\cup[1]^{M_{1}}\cup[-1]^{M_{-1}},$

where $M_{1}=|E|-|V|+1$ and $M_{-1}=|E|-|V|+\dim\operatorname{Ker}(T+I)$.

######  Lemma 2.3.

Let $G$ be a connected $k$-regular graph, and set $T:=T(G)$. If $G$ is
$2l$-periodic, then

$\displaystyle\operatorname{Spec}(T)=\begin{bmatrix}1&\cos(\frac{2\pi}{2l})&\cos(2\cdot\frac{2\pi}{2l})&\cdots&\cos((l-1)\cdot\frac{2\pi}{2l})&-1\\\
1&a_{1}&a_{2}&\cdots&a_{l-1}&a_{l}\end{bmatrix}$

for some non-negative integers $a_{1},\ldots,a_{l-1}$ and $a_{l}\in\\{0,1\\}$.
Furthermore, $G$ is bipartite if and only if $a_{l}=1$.

###### Proof.

Assume that the graph $G$ is $2l$-periodic. By Theorem 2.1, each eigenvalue
$\lambda_{T}\in\operatorname{Spec}(T)$ satisfies $(e^{\pm
i\arccos(\lambda_{T})})^{2l}=1$. This implies

$\lambda_{T}=\cos\left(\frac{2j\pi}{2l}\right)$

for some integer $j\in\\{0,\ldots,l\\}$. Also, by the Perron-Frobenius theorem
[2, Theorem 2.2.1], we see that the largest eigenvalue has multiplicity $1$,
and derive $a_{l}\in\\{0,1\\}$ and the necessary and sufficient condition for
$G$ to be bipartite. ∎

######  Definition 2.4.

Let $A$ be a finite subset of the complex number field $\mathbb{C}$. Then, we
define

$\displaystyle S^{n}(A)=\sum_{a\in A}a^{n}$

for a positive integer $n$. For short, we set $S(A)=S^{1}(A)$.

Using the handshaking lemma, we have the following.

######  Lemma 2.5.

Let $G$ be a $k$-regular graph with n vertices, and let $T=T(G)$. Then we have

$\displaystyle\operatorname{tr}T^{2}=\frac{n}{k}.$ (2)

As a basic result, periodicity of cycle graphs is known as follows.

######  Lemma 2.6.

The cycle graph $C_{n}$ with $n$ vertices is $n$-periodic.

This lemma is essentially derived from [10, Theorem 7.1] by setting $j=0$ and
$p=0$. Of course, it can also be proved by computing the eigenvalues of the
cycle graphs.

##  3 $6$-periodic regular graphs

In this section, we show that the only $6$-periodic regular graph coincides
with the cycle graph $C_{6}$. This corresponds to an exceptional case in the
main theorem. As will be discussed in detail in Section 4, if $l$ is an odd
integer that is a multiple of $3$, then $2l$-periodic regular graphs could
potentially be $3$-regular graphs except for the cycle graph $C_{2l}$.
However, in the case of $l=3$, the $2l$-periodic regular graph is the cycle
graph $C_{6}$ only.

######  Theorem 3.1.

If a connected regular graph $G$ is $6$-periodic, then $G$ is the cycle graph
$C_{6}$.

###### Proof.

Let $G$ be a $6$-periodic $k$-regular graph, and set $T=T(G)$. From Lemma 2.3,
the spectrum of $T$ is written as

$\displaystyle\operatorname{Spec}(T)=\begin{bmatrix}1&\cos\frac{\pi}{3}&\cos(\frac{2\pi}{3})&-1\\\
1&a_{1}&a_{2}&a_{3}\end{bmatrix}=\begin{bmatrix}1&\frac{1}{2}&-\frac{1}{2}&-1\\\
1&a_{1}&a_{2}&a_{3}\end{bmatrix}$

for some non-negative integers $a_{1}$, $a_{2}$, and $a_{3}$. From the Perron-
Frobenius theorem [2, Theorem 2.2.1], the graph is bipartite if and only if
$a_{3}=1$. Assume $a_{3}=1$. Then, $G$ is a bipartite regular graph, so we
have $a_{1}=a_{2}$. If $a_{1}=a_{2}=0$, then the graph $G$ is the path graph
$P_{2}$ with $2$ vertices, but it has period $2$. If $a_{1}=a_{2}\geq 1$, then
the bipartite regular graph $G$ has four distinct eigenvalues. Thus, the
result in [8, Theorem 4.1] yields that $G$ is the cycle graph $C_{6}$ with $6$
vertices.

Next, assume $a_{3}=0$. We have $a_{2}\geq 1$ from (1). If $a_{1}=0$, then (1)
leads to $a_{2}=2$. A graph with such spectrum is the complete graph $K_{3}$
with $3$ vertices only. However, the period of $K_{3}$ is $3$ [7]. Thus, we
may assume that $a_{1}\geq 1$. Then the adjacency matrix of the regular graph
$G$ has three distinct eigenvalues, so $G$ is a strongly regular graph [2,
Theorem 9.1.2]. Periodicity of strongly regular graphs has been investigated
in [7], and periodic strongly regular graphs can only have $(2k,k,0,k)$,
$(3\lambda,2\lambda,\lambda,2\lambda)$, and $(5,2,0,1)$ as parameters. These
are $K_{k,k},K_{\lambda,\lambda,\lambda}$, and $C_{5}$ respectively, and none
of them has period $6$. Therefore, if a connected regular graph $G$ is a
$6$-periodic graph, then $G$ is the cycle graph $C_{6}$. ∎

##  4 Regular graphs inducing period $2l$ where $l$ is an odd integer

As the discussion in Section 3 suggests, it is explicitly determined what
eigenvalues the matrix $T$ should have for a given period. In studying larger
even periods, we will obtain information on the eigenvalues using Galois
theory. We assume readers unfamiliar with Galois theory and attempt a brief
explanation of the theory.

A complex number $\alpha$ is _algebraic_ over $\mathbb{Q}$ if there exists a
non-zero polynomial $p(x)$ with coefficients in $\mathbb{Q}$ such that
$p(\alpha)=0$. Among such polynomials, the monic one with the smallest degree
is called the $\mathbb{Q}$-minimal polynomial of $\alpha$. For example, we see
that $\sqrt{2}$ is a root of the polynomial $f(x)=x^{2}-2$, so it is algebraic
over $\mathbb{Q}$. In addition, the polynomial $f(x)$ is the
$\mathbb{Q}$-minimal polynomial of $\sqrt{2}$. If complex numbers $\alpha$ and
$\beta$ share the same $\mathbb{Q}$-minimum polynomial, they are said to be
conjugate over $\mathbb{Q}$, or we say that $\beta$ is a conjugate of $\alpha$
over $\mathbb{Q}$. For example, $\sqrt{2}$ and $-\sqrt{2}$ are conjugate over
$\mathbb{Q}$. In general, if a complex number $\alpha$ is a root of a
$\mathbb{Q}$-coefficient polynomial $p(x)$, then all conjugates
$\alpha_{1},\dots,\alpha_{s}$ over $\mathbb{Q}$ of $\alpha$ are roots of
$p(x)$. This implies that the multiplicities of $\alpha_{1},\dots,\alpha_{s}$
are equal for the roots of the $\mathbb{Q}$-coefficient polynomial $p(x)$.
Therefore, capturing conjugates over $\mathbb{Q}$ of algebraic numbers is
useful for partially catching roots of polynomials.

To capture information on conjugates, it is useful to study symmetries
(automorphisms) of fields. We take $\sqrt{2}$ and its conjugate over
$\mathbb{Q}$, $-\sqrt{2}$, as an example. The automorphism
$\mathbb{Q}(\sqrt{2})\to\mathbb{Q}(\sqrt{2})$ that does not change elements of
$\mathbb{Q}$ is only $\sigma:\sqrt{2}\mapsto-\sqrt{2}$ except for the identity
mapping. In fact, this mapping $\sigma$ provides us with information on the
conjugates over $\mathbb{Q}$ of $\sqrt{2}$. In the following paragraph, we
supplement terminologies on field theory. Essential importance in this study
is Lemma 4.1.

Let $L$ and $K$ be fields. We denote $L\supset K$ by $L/K$ and say that it is
a _field extension_. Let $\zeta_{n}=e^{\frac{2\pi i}{n}}$ for each positive
integer $n$. It is known that the field extension
$\mathbb{Q}(\zeta_{n})/\mathbb{Q}$ is a Galois extension. This paper does not
define Galois extensions, but we do not need to understand them in depth
either. The set of all automorphisms of $\mathbb{Q}(\zeta_{n})$ that do not
change any elements of $\mathbb{Q}$ is a group with respect to the composition
of maps. We call the set the _Galois group_ of
$\mathbb{Q}(\zeta_{n})/\mathbb{Q}$ and denote it by
$\operatorname{Gal}(\mathbb{Q}(\zeta_{n})/\mathbb{Q})$.

######  Lemma 4.1 ([4, Corollary 5.1.8]).

Let $\alpha\in\mathbb{Q}(\zeta_{n})$. Then, the following are equivalent.

  1. (1)

$\beta\in\mathbb{Q}(\zeta_{n})$ is a conjugate of $\alpha$ over $\mathbb{Q}$.

  2. (2)

There exists $f\in\operatorname{Gal}(\mathbb{Q}(\zeta_{n})/\mathbb{Q})$ such
that $f(\alpha)=\beta$.

Next, we explain the Galois group
$\operatorname{Gal}(\mathbb{Q}(\zeta_{n})/\mathbb{Q})$. Let $n\geq 2$ be a
positive integer. Let $(\mathbb{Z}/n\mathbb{Z})^{\times}$ be the set of units
of $\mathbb{Z}/n\mathbb{Z}$. For each $m\in(\mathbb{Z}/n\mathbb{Z})^{\times}$,
we write $\sigma_{m}$ for the automorphism of $\mathbb{Q}(\zeta_{n})$ such
that

$\displaystyle\sigma_{m}(\zeta_{n})=\zeta_{n}^{m}.$

We note that elements of Galois groups are ring homomorphisms that do not
change the elements of $\mathbb{Q}$, so they are defined by specifying only
the image of the generators. It is known that

$\operatorname{Gal}(\mathbb{Q}(\zeta_{n})/\mathbb{Q})=\\{\sigma_{m}\mid
m\in(\mathbb{Z}/n\mathbb{Z})^{\times}\\}.$

We determine the $2l$-periodic regular graphs where $l$ is an odd integer. For
an integer $j$, we let
$\alpha^{(n)}_{j}:=\cos\big{(}\frac{2\pi}{n}j\big{)}=\frac{1}{2}(\zeta^{j}_{n}+\zeta^{-j}_{n})$.

We define $G_{n}:=\operatorname{Gal}(\mathbb{Q}(\zeta_{n})/\mathbb{Q})$. For
$x\in\mathbb{Q}(\zeta_{n})$, consider the set
$G_{n}x=\\{\sigma(x)\mid\sigma\in\operatorname{Gal}(\mathbb{Q}(\zeta_{n})/\mathbb{Q})\\}$.
From Lemma 4.1, the elements of $G_{n}\alpha^{(n)}_{j}$ are conjugates of
$\alpha^{(n)}_{j}$ over $\mathbb{Q}$.

The following series of lemmas is necessary computations for proving our main
theorem. The essential reason why our main theorem is derived can be explained
as that Lemma 2.5 imposes a strong restriction to $2l$-periodic regular
graphs, where $l$ is an odd integer. Hence, we are interested in the sum of
squares of eigenvalues. Since eigenvalues that are conjugate over $\mathbb{Q}$
to each other have the same multiplicity, the value of
$S^{2}(G_{n}\alpha_{j}^{(n)})$ for each $j$ is key. To compute this quantity,
we first consider properties of orbits containing $\zeta_{n}^{j}$.

######  Lemma 4.2.

Let $n$ be a positive integer, and let $m$ be a positive divisor of $n$. Then
we have

$G_{n}\zeta_{n}^{m}=G_{\frac{n}{m}}\zeta_{\frac{n}{m}}\quad\text{ and }\quad
G_{n}\alpha^{(n)}_{m}=G_{\frac{n}{m}}\alpha^{\left(\frac{n}{m}\right)}_{1}.$

In particular, $S(G_{n}\zeta_{n}^{m})=S(G_{\frac{n}{m}}\zeta_{\frac{n}{m}}).$

###### Proof.

By Lemma 4.1, we have

$\displaystyle G_{n}\zeta_{n}^{m}$
$\displaystyle=\\{z\in\mathbb{C}\mid\text{$z$ and $\zeta_{n}^{m}$ are
conjugate over $\mathbb{Q}$}\\}$ $\displaystyle=\\{z\in\mathbb{C}\mid\text{$z$
and $\zeta_{\frac{n}{m}}$ are conjugate over $\mathbb{Q}$}\\}$
$\displaystyle=G_{\frac{n}{m}}\zeta_{\frac{n}{m}}.$

Also,
$G_{n}\alpha^{(n)}_{m}=G_{\frac{n}{m}}\alpha^{\left(\frac{n}{m}\right)}_{1}$
holds in the same manor. ∎

The function $\phi:\mathbb{Z}_{>0}\to\mathbb{Z}_{>0}$ defined as
$\phi(n)=|(\mathbb{Z}/n\mathbb{Z})^{\times}|$ is the Euler function. Note that

$\phi(2n)=\phi(n)$ (3)

if $n$ is odd.

######  Lemma 4.3.

Let $n\geq 3$ be an integer. Then, the mapping
$\operatorname{Re}:G_{n}\zeta_{n}\to G_{n}\alpha_{1}^{(n)}$, which is defined
by
$\operatorname{Re}(\zeta_{n}^{j})=\frac{\zeta_{n}^{j}+\zeta_{n}^{-j}}{2}=\alpha_{j}^{(n)}$
for $j\in(\mathbb{Z}/n\mathbb{Z})^{\times}$, is a $2$-to-$1$ mapping, i.e.,
for any $\alpha_{j}^{(n)}\in G_{n}\alpha_{1}^{(n)}$, we have
$|\operatorname{Re}^{-1}(\\{\alpha_{j}^{(n)}\\})|=2$. Also, let $m\geq 3$ be a
divisor of $n$. Then, we have

$|G_{n}\alpha_{1}^{(m)}|=\frac{\phi(m)}{2}.$

###### Proof.

From the definition of $\alpha_{j}^{(n)}$, the mapping is a surjection. Next,
we fix $\alpha_{k}^{(n)}\in G_{n}\alpha_{1}^{(n)}$, where
$k\in(\mathbb{Z}/n\mathbb{Z})^{\times}$. We assume that
$\operatorname{Re}(\zeta_{n}^{j})=\alpha_{k}^{(n)}$, where
$j\in(\mathbb{Z}/n\mathbb{Z})^{\times}$. Then,

$\displaystyle 0$
$\displaystyle=\operatorname{Re}(\zeta_{n}^{j})-\alpha_{k}^{(n)}=\alpha_{j}^{(n)}-\alpha_{k}^{(n)}=\cos\big{(}\frac{2\pi}{n}j\big{)}-\cos\big{(}\frac{2\pi}{n}k\big{)}$
$\displaystyle=-2\sin\big{(}\frac{j+k}{n}\pi\big{)}\sin\big{(}\frac{j-k}{n}\pi\big{)}.$

Therefore, we have $j=\pm k$. Moreover, we have $k\neq-k$. Indeed, if $k=-k$,
then $2k=0$. Since $k\in(\mathbb{Z}/n\mathbb{Z})^{\times}$, we have $2=0$.
This contradicts $n\geq 3$. Thus $\zeta_{n}^{k}\neq\zeta_{n}^{-k}$. We see
that the mapping $\operatorname{Re}$ is a $2$-to-$1$ mapping.

Also, let $l$ be a positive integer satisfying $n=ml$. By Lemma 4.2, we have

$G_{n}\zeta_{m}=G_{n}\zeta_{n}^{l}=G_{\frac{n}{l}}\zeta_{\frac{n}{l}}=G_{m}\zeta_{m}.$

Hence,

$G_{n}\alpha_{1}^{(m)}=\operatorname{Re}(G_{n}\zeta_{m})=\operatorname{Re}(G_{m}\zeta_{m}).$

Since the mapping $\operatorname{Re}:G_{m}\zeta_{m}\to G_{m}\alpha_{1}^{(m)}$
is a $2$-to-$1$ mapping as $m\geq 3$, we have

$|G_{n}\alpha_{1}^{(m)}|=|\operatorname{Re}(G_{m}\zeta_{m})|=\frac{|G_{m}\zeta_{m}|}{2}=\frac{\phi(m)}{2}.$

∎

######  Definition 4.4.

For a positive integer $n$, let

$D(n)=\\{m\in\mathbb{Z}\mid\text{$m$ is a positive divisor of $n$}\\}.$

######  Lemma 4.5.

Let $n$ be a positive integer. For distinct integers $i\neq j$ in $D(n)$,
$G_{n}\zeta_{n}^{i}\cap G_{n}\zeta_{n}^{j}=\emptyset$.

###### Proof.

Fix such integers $i$ and $j$. By way of contradiction, we assume
$G_{n}\zeta_{n}^{i}\cap G_{n}\zeta_{n}^{j}\neq\emptyset$. Then there exist $x$
and $y$ in $\mathbb{Z}$ coprime to $n$ such that $ix-jy\equiv 0\pmod{n}$.
Hence $ix\equiv 0\pmod{j}$. Without loss of generality, we may assume that
$j\nmid i$. Then we see that $\gcd(n,x)\geq\gcd(j,x)\geq 2$. This contradicts
the assumption that $x$ and $n$ are coprime. ∎

Let $n$ be a positive integer. The function $\mu(n)$ that satisfies the
following is called the Möbius function.

$\mu(n)=\begin{cases}(-1)^{r}&\text{if $n$ is a product of $r$ different prime
numbers, }\\\ 0&\text{if $n$ has at least one square factor. }\end{cases}$

######  Lemma 4.6 ([5, (16.6.4)]).

Let $n$ be a positive integer. Then, we have

$S(G_{n}\zeta_{n})=\mu(n).$

######  Lemma 4.7.

Let $n$ be a positive integer. Then, we have

$S(G_{n}\zeta_{n}^{2})=\begin{cases}S(G_{n}\zeta_{n})&\text{if $n$ is odd,}\\\
S(G_{\frac{n}{2}}\zeta_{\frac{n}{2}})&\text{if $n$ is even.}\end{cases}$

###### Proof.

If $n$ is odd, then $n$ and $2$ are coprime. We have
$2\in(\mathbb{Z}/n\mathbb{Z})^{\times}$ and $\sigma_{2}\in G_{n}$. Therefore
$\zeta_{n}$ and $\zeta_{n}^{2}$ are conjugate over $\mathbb{Q}$ from Lemma
4.1. Thus

$G_{n}\zeta_{n}^{2}=G_{n}\zeta_{n}.$

When $n$ is even, we have

$G_{n}\zeta_{n}^{2}=G_{\frac{n}{2}}\zeta_{\frac{n}{2}}$

by Lemma 4.2. ∎

######  Lemma 4.8.

Let $m$ be an integer, and let $n$ be a positive integer, we have

$\displaystyle S^{2}(G_{n}\zeta_{n}^{m})=S^{2}(G_{n}\zeta_{n}^{-m}).$ (4)

###### Proof.

Since $n$ and $n-1$ are coprime, $\zeta_{n}$ and
$\zeta_{n}^{n-1}=\zeta_{n}^{-1}$ are conjugate over $\mathbb{Q}$. Hence
$G_{n}\zeta_{n}^{m}=G_{n}(\zeta_{n}^{-1})^{m}=G_{n}\zeta_{n}^{-m}$ by Lemma
4.1. This implies $S^{2}(G_{n}\zeta_{n}^{m})=S^{2}(G_{n}\zeta_{n}^{-m})$. ∎

######  Corollary 4.9.

Let $l\geq 3$ be an odd integer, and set $n:=2l$. Then we have

$S^{2}(G_{n}\alpha_{1}^{(n)})=\frac{1}{4}\\{S(G_{n}\zeta_{n}^{2})+\phi(n)\\}.$

###### Proof.

From Lemma 4.3, we have

$\displaystyle S^{2}(G_{n}\alpha_{1}^{(n)})=\sum_{\alpha\in
G_{n}\alpha_{1}^{(n)}}\alpha^{2}=\frac{1}{2}\sum_{z\in
G_{n}\zeta_{n}}\left(\frac{z+z^{-1}}{2}\right)^{2}.$

We see that

$\displaystyle\frac{1}{2}\sum_{z\in
G_{n}\zeta_{n}}\left(\frac{z+z^{-1}}{2}\right)^{2}$
$\displaystyle=\frac{1}{2}\sum_{j\in(\mathbb{Z}/n\mathbb{Z})^{\times}}\left(\frac{\zeta_{n}^{j}+\zeta_{n}^{-j}}{2}\right)^{2}$
$\displaystyle=\frac{1}{8}\sum_{j\in(\mathbb{Z}/n\mathbb{Z})^{\times}}\\{(\zeta_{n}^{j})^{2}+(\zeta_{n}^{-j})^{2}+2\\}$
$\displaystyle=\frac{1}{8}\sum_{j\in(\mathbb{Z}/n\mathbb{Z})^{\times}}\\{(\zeta_{n}^{2})^{j}+(\zeta_{n}^{-2})^{j}+2\\}$
$\displaystyle=\frac{1}{8}\left\\{S(G_{n}\zeta_{n}^{2})+S(G_{n}\zeta_{n}^{-2})+2\phi(n)\right\\}$
$\displaystyle=\frac{1}{8}\\{2S(G_{n}\zeta_{n}^{2})+2\phi(n)\\}$
$\displaystyle=\frac{1}{4}\\{S(G_{n}\zeta_{n}^{2})+\phi(n)\\},$

where the fifth equality is derived from Lemma 4.8. ∎

######  Theorem 4.10 (Theorem 1.1, restated).

Let $G$ be a $k$-regular graph, and let $l$ be an odd integer. If $G$ is a
$2l$-periodic graph, then one of the following holds.

  1. (1)

$G$ is the cycle graph $C_{2l}$ with $2l$ vertices.

  2. (2)

$k=3$ and $l$ is a multiple of $3$.

###### Proof.

Let $l=p_{1}^{r_{1}}p_{2}^{r_{2}}\cdots p_{s}^{r_{s}}$ be the prime
factorization of $l$, where $p_{i}<p_{i+1}$. By Lemma 2.3, the eigenvalues of
$T$ are elements of $\\{\alpha^{(2l)}_{j}\mid j\in\\{0,\ldots,l\\}\\}$. Noting
that the characteristic polynomial of $T$ is a $\mathbb{Q}$-coefficient
polynomial, we see that a conjugate of an eigenvalue of $T$ is an eigenvalue.
Hence, the set of eigenvalues of $T$ coincides with the union of a subset of
$\\{G_{n}\alpha^{(2l)}_{j}\mid j\in D(2l)\\}$. Here note that the conjugate
classes are disjoint by Lemma 4.5. Since pairwise conjugate eigenvalues over
$\mathbb{Q}$ have the same multiplicity, we write $m_{d}$ ($d\in D(2l)$) for
the multiplicity of an eigenvalue in $G_{n}\alpha^{(2l)}_{d}$. Let
$X_{d^{\prime}}=m_{d^{\prime}}+m_{2d^{\prime}}$ for $d^{\prime}\in D(l)$.
Since $T$ is an $n\times n$ matrix, we have

$\displaystyle n$ $\displaystyle=\sum_{d\in
D(2l)}|G_{2l}\alpha_{d}^{(2l)}|m_{d}$ $\displaystyle=\sum_{d\in
D(2l)}|G_{\frac{2l}{d}}\alpha_{1}^{\left(\frac{2l}{d}\right)}|m_{d}$
$\displaystyle=\frac{1}{2}\sum_{d\in D(2l)}\phi\left(\frac{2l}{d}\right)m_{d}$
$\displaystyle=\frac{1}{2}\left\\{\sum_{d^{\prime}\in
D(l)}\phi\left(\frac{2l}{d^{\prime}}\right)m_{d^{\prime}}+\sum_{d^{\prime}\in
D(l)}\phi\left(\frac{2l}{2d^{\prime}}\right)m_{2d^{\prime}}\right\\},$

where the second and third equalities follow from Lemmas 4.2 and 4.3,
respectively. Since $l$ is odd, Equality (3) leads to

$\displaystyle\phi\left(\frac{2l}{d^{\prime}}\right)$
$\displaystyle=\phi\left(\frac{l}{d^{\prime}}\right)$ (5)

for $d^{\prime}\in D(l)$. Thus,

$\displaystyle\frac{1}{2}\left\\{\sum_{d^{\prime}\in
D(l)}\phi\left(\frac{2l}{d^{\prime}}\right)m_{d^{\prime}}+\sum_{d^{\prime}\in
D(l)}\phi\left(\frac{2l}{2d^{\prime}}\right)m_{2d^{\prime}}\right\\}$
$\displaystyle=\frac{1}{2}\sum_{d^{\prime}\in
D(l)}\phi\left(\frac{l}{d^{\prime}}\right)(m_{d^{\prime}}+m_{2d^{\prime}})$
$\displaystyle=\frac{1}{2}\sum_{d^{\prime}\in
D(l)}\phi\left(\frac{l}{d^{\prime}}\right)X_{d^{\prime}}.$

Therefore, we have

$\displaystyle n=\frac{1}{2}\sum_{d^{\prime}\in
D(l)}\phi\left(\frac{l}{d^{\prime}}\right)X_{d^{\prime}}.$ (6)

Also, we write $S^{2}(\operatorname{Spec}(T))$ for the sum
$\sum_{\lambda}a_{\lambda}\lambda^{2}$ where $\lambda$ is an eigenvalue of $T$
and $a_{\lambda}$ is the multiplicity of $\lambda$. We have

$\displaystyle S^{2}(\operatorname{Spec}(T))$ $\displaystyle=\sum_{d\in
D(2l)}S(G_{2l}(\alpha_{d}^{(2l)})^{2})m_{d}$ $\displaystyle=\sum_{d\in
D(2l)}S(G_{\frac{2l}{d}}(\alpha_{1}^{(\frac{2l}{d})})^{2})m_{d}$
$\displaystyle=\frac{1}{4}\sum_{d\in
D(2l)}\left\\{S(G_{\frac{2l}{d}}\zeta_{\frac{2l}{d}}^{2})+\phi\left(\frac{2l}{d}\right)\right\\}m_{d},$

where the third equality is derived from Corollary 4.9. If $d\in D(2l)$ is
even, it can be displayed as $d=2d^{\prime}$ for some $d^{\prime}\in D(l)$.
Then we have

$\displaystyle\left\\{S(G_{\frac{2l}{d}}\zeta_{\frac{2l}{d}}^{2})+\phi\left(\frac{2l}{d}\right)\right\\}m_{d}$
$\displaystyle=\left\\{S(G_{\frac{2l}{2d^{\prime}}}\zeta_{\frac{2l}{2d^{\prime}}}^{2})+\phi\left(\frac{2l}{2d^{\prime}}\right)\right\\}m_{2d^{\prime}}$
$\displaystyle=\left\\{S(G_{\frac{l}{d^{\prime}}}\zeta_{\frac{l}{d^{\prime}}}^{2})+\phi\left(\frac{l}{d^{\prime}}\right)\right\\}m_{2d^{\prime}}$
$\displaystyle=\left\\{S(G_{\frac{l}{d^{\prime}}}\zeta_{\frac{l}{d^{\prime}}})+\phi\left(\frac{l}{d^{\prime}}\right)\right\\}m_{2d^{\prime}},$

where the last equality is derived from Lemma 4.7. If $d\in D(2l)$ is odd, we
have $d\in D(l)$, so Lemma 4.2 and Equality (5) yield

$\left\\{S(G_{\frac{2l}{d}}\zeta_{\frac{2l}{d}}^{2})+\phi\left(\frac{2l}{d}\right)\right\\}m_{d}=\left\\{S(G_{\frac{l}{d}}\zeta_{\frac{l}{d}})+\phi\left(\frac{l}{d}\right)\right\\}m_{d}$

Thus, by converting the variable $d$ to $d^{\prime}$, we have

$\displaystyle S^{2}(\operatorname{Spec}(T))$
$\displaystyle=\frac{1}{4}\sum_{d\in
D(2l)}\left\\{S(G_{\frac{2l}{d}}\zeta_{\frac{2l}{d}}^{2})+\phi\left(\frac{2l}{d}\right)\right\\}m_{d}$
$\displaystyle=\frac{1}{4}\sum_{d^{\prime}\in
D(l)}\left\\{S(G_{\frac{l}{d^{\prime}}}\zeta_{\frac{l}{d^{\prime}}})+\phi\left(\frac{l}{d^{\prime}}\right)\right\\}(m_{d^{\prime}}+m_{2d^{\prime}})$
$\displaystyle=\frac{1}{4}\sum_{d^{\prime}\in
D(l)}\left\\{S(G_{\frac{l}{d^{\prime}}}\zeta_{\frac{l}{d^{\prime}}})+\phi\left(\frac{l}{d^{\prime}}\right)\right\\}X_{d^{\prime}}$
$\displaystyle=\frac{1}{4}\sum_{d^{\prime}\in
D(l)}\left\\{\mu\left(\frac{l}{d^{\prime}}\right)+\phi\left(\frac{l}{d^{\prime}}\right)\right\\}X_{d^{\prime}},$

where the last equality is derived from Lemma 4.6. Therefore, we have

$\displaystyle S^{2}(\operatorname{Spec}(T))=\frac{1}{4}\sum_{d^{\prime}\in
D(l)}\left\\{\mu\left(\frac{l}{d^{\prime}}\right)+\phi\left(\frac{l}{d^{\prime}}\right)\right\\}X_{d^{\prime}}.$
(7)

Substituting Equalities (6) and (7) into Lemma 2.5 (2), we obtain

$\sum_{d^{\prime}\in
D(l)}\left[k\left\\{\mu\left(\frac{l}{d^{\prime}}\right)+\phi\left(\frac{l}{d^{\prime}}\right)\right\\}-2\phi\left(\frac{l}{d^{\prime}}\right)\right]X_{d^{\prime}}=0.$

Note that $\mu(1)=1,\phi(1)=1$. We have

$\displaystyle\sum_{d^{\prime}\in
D(l)\setminus\\{l\\}}\left[k\left\\{\mu\left(\frac{l}{d^{\prime}}\right)+\phi\left(\frac{l}{d^{\prime}}\right)\right\\}-2\phi\left(\frac{l}{d^{\prime}}\right)\right]X_{d^{\prime}}$
$\displaystyle=-\left[k\\{\mu(1)+\phi(1)\\}-2\phi(1)\right]X_{l}$
$\displaystyle=-2(k-1)X_{l}.$

We remark that $X_{l}$ is positive. Therefore, we see that the graph does not
satisfy

$\displaystyle
k\left\\{\mu\left(\frac{l}{d^{\prime}}\right)+\phi\left(\frac{l}{d^{\prime}}\right)\right\\}-2\phi\left(\frac{l}{d^{\prime}}\right)\geq
0\quad\text{for any}\quad d^{\prime}\in D(l)\setminus\\{l\\}.$ (8)

We have

$\displaystyle\eqref{contraposition}$ $\displaystyle\iff
k\geq\frac{2\phi(\frac{l}{d^{\prime}})}{\mu(\frac{l}{d^{\prime}})+\phi(\frac{l}{d^{\prime}})}\quad\text{for
any}\quad d^{\prime}\in D(l)\setminus\\{l\\}$ $\displaystyle\iff
k\geq\max\left\\{\frac{2\phi(\frac{l}{d^{\prime}})}{\mu(\frac{l}{d^{\prime}})+\phi(\frac{l}{d^{\prime}})}\,\middle|\,d^{\prime}\in
D(l)\setminus\\{l\\}\right\\}.$

The value

$\frac{2\phi(\frac{l}{d^{\prime}})}{\mu(\frac{l}{d^{\prime}})+\phi(\frac{l}{d^{\prime}})}=2-\frac{2\mu(\frac{l}{d^{\prime}})}{\mu(\frac{l}{d^{\prime}})+\phi(\frac{l}{d^{\prime}})}$

takes the maximum when $\phi(\frac{l}{d^{\prime}})$ takes the minimum and
$\mu(\frac{l}{d^{\prime}})=-1$. Since this is attained when
$\frac{l}{d^{\prime}}=p_{1}$, we have

$\displaystyle\max\left\\{2-\frac{2\mu(\frac{l}{d^{\prime}})}{\mu(\frac{l}{d^{\prime}})+\phi(\frac{l}{d^{\prime}})}\,\middle|\,d^{\prime}\in
D(l)\setminus\\{l\\}\right\\}=2+\frac{2}{\phi(p_{1})-1}=2+\frac{2}{p_{1}-2}.$

As a result, (8) is equivalent to

$k\geq 2+\frac{2}{p_{1}-2}.$ (9)

This means that if $k$ satisfies (9), then the graph is not periodic.
Therefore, we conclude that $k\leq 3$ if $p_{1}=3$, and $k=2$ if $p_{1}\geq
5$. Therefore, either $k=3$ and $l$ is a multiple of $3$, or $k=2$ holds. In
particular, if $k=2$, then $G$ is the cycle graph, and hence Lemma 2.6 implies
that the cycle graph $G$ has $2l$ vertices. ∎

It should be noted that Theorem 4.10 refers only to the necessary condition
for $2l$-periodic regular graphs. We already know that the cycle graph with
$2l$ vertices is $2l$-periodic, but we know nothing so far on the situation
where $k=3$ and $l$ is a multiple of $3$. The existence of such graphs is our
future work:

######  Question 4.11.

Let $l$ be an odd integer that is a multiple of $3$. Do $2l$-periodic
$3$-regular graphs exist?

Note that only the complete bipartite graph $K_{3,3}$ is currently discovered
as periodic 3-regular graphs, and its period is $4$ [7].

##  5 Summary and $4s$-periodic regular graphs

Once again, let $l$ be an odd integer. In this paper, we proved that only the
$2l$-periodic regular graphs are cycle graphs $C_{2l}$ with $2l$ vertices if
$l$ is not a multiple of $3$. There could potentially be $2l$-periodic
$3$-regular graphs only if $l$ is a multiple of $3$.

Incidentally, we did not make any mention of the case where $l$ is even in
this paper. In the remainder, we will mention periodic regular graphs whose
period is a multiple of $4$. Let $s$ be a positive integer. In fact, many
examples of $4s$-periodic regular graphs have already been found, for example,
$12$-periodic regular graphs are summarized in Table 2 of [8]. Moreover, if
$G$ is a $4s$-periodic graph, then $G\otimes J_{t}$, which is the Kronecker
product of $G$ and the square all-one matrix $J_{t}$ of size $t$, is also a
$4s$-periodic graph. In particular, $C_{4s}\otimes J_{t}$ is a $4s$-periodic
regular graph for any $t$. For small $s$, we know the following. The only
$4$-periodic graphs are complete bipartite graphs [14]. For $8$-periodic
regular graphs, it is known that graphs are constructed from transversal
designs, besides $C_{8}\otimes J_{t}$ (see Table 3 in [8]). For $12$-periodic
regular graphs, see Table 2 in [8] as already mentioned. For $20$-periodic
regular graphs, some examples have been found besides $C_{20}\otimes J_{t}$,
and they appear in Section 9 of [3]. At least for small $s$, there are
sporadic examples of $4s$-periodic regular graphs besides $C_{4s}\otimes
J_{t}$. We expect that characterizing $4s$-periodic regular graphs will be
difficult, but we believe it will also be an interesting problem.

## Acknowledgements

We would like to thank Professor Norio Konno for his fruitful comments and
helpful advice. S.K. is supported by JSPS KAKENHI (Grant Number JP20J01175).
K.Y is supported by JSPS KAKENHI (Grant Number JP21J14427).

## References

  * [1] A. Ambainis (2004). _Quantum search algorithms_ , ACM SIGACT News, 35(2), 22-35.
  * [2] A.E. Brouwer and W.H. Haemers (2012). _Spectra of graphs. Springer_ , New York.
  * [3] Q. Chen (2022). _Periodicity of bipartite walk on biregular graphs with conditional spectra_ , arXiv preprint arXiv:2211.02752.
  * [4] David A. Cox (2012). _Galois Theory Second Edition_ , Amherst, MA: Wiley.
  * [5] G.H. Hardy and E.M. Wright (2008). _An introduction to the theory of Numbers_ , sixth edition, Oxford University Press, Oxford.
  * [6] Y. Higuchi, N. Konno, I. Sato, E. Segawa (2014). _Spectral and asymptotic properties of Grover walks on crystal lattices_ , J. Funct. Anal. 267, 4197-4235.
  * [7] Y. Higuchi, N. Konno, I. Sato and E. Segawa (2017). _Periodicity of the discrete-time quantum walk on a finite graph_ , Interdisciplinary Information Sciences, 23, 75-86.
  * [8] S. Kubota (2022). _Periodicity of Grover walks on bipartite regular graphs with at most five distinct eigenvalues_ , Linear Algebra and its Applications, 654, 125-142.
  * [9] S. Kubota, E. Segawa, T. Taniguchi and Y. Yoshie (2018). _Periodicity of Grover walks on generalized Bethe trees._ Linear Algebra and its Applications, 554, 371-391.
  * [10] S. Kubota, H. Sekido and H. Yata (2021). _Periodicity of quantum walks defined by mixed paths and mixed cycles_ , Linear Algebra and its Applications, 630, 15-38.
  * [11] A. Panda and C. Benjamin (2021). _Order from chaos in quantum walks on cyclic graphs_ , Physical Review A, 104, 012204.
  * [12] M. Mohseni, P. Rebentrost, S. Lloyd and A. Aspuru-Guzik (2008). _Environment-assisted quantum walks in photosynthetic energy transfer_ , The Journal of chemical physics, 129(17), 11B603.
  * [13] T. Yamagami, E. Segawa, T. Mihana, Röhm, A., R. Horisaki and M. Naruse (2023). _Bandit Algorithm Driven by a Classical Random Walk and a Quantum Walk_ , Entropy, 25(6), 843.
  * [14] Y. Yoshie (2017). _Characterizations of graphs to induce periodic Grover walk_ , Yokohama Mathematical Journal, 63, 9-23.
  * [15] Y. Yoshie (2019). _Periodicities of Grover walks on distance-regular graphs._ Graphs and Combinatorics, 35(6), 1305-1321.
  * [16] Y. Yoshie (2021). _Odd-periodic Grover walk_ , arXiv:2106.06710.


# Crop Disease Classification using Support Vector Machines with Green
Chromatic Coordinate (GCC) and Attention based feature extraction for IoT
based Smart Agricultural Applications

Shashwat Jha1*,Vishvaditya Luhach2*, Gauri Shanker Gupta1, Beependra Singh3

###### Abstract

Crops hold paramount significance as they serve as the primary provider of
energy, nutrition, and medicinal benefits for the human population. Plant
diseases, however, can negatively affect leaves during agricultural
cultivation, resulting in significant losses in crop output and economic
value. Therefore, it is crucial for farmers to identify crop diseases.
However, this method frequently necessitates hard work, a lot of planning, and
in-depth familiarity with plant pathogens. Given these numerous obstacles, it
is essential to provide solutions that can easily interface with mobile and
IoT devices so that our farmers can guarantee the best possible crop
development. Various machine learning (ML) as well as deep learning (DL)
algorithms have been created and studied for the identification of plant
disease detection, yielding substantial and promising results. This article
presents a novel classification method that builds on prior work by utilising
attention-based feature extraction, RGB channel-based chromatic analysis,
Support Vector Machines (SVM) for improved performance, and the ability to
integrate with mobile applications and IoT devices after quantization of
information. Several disease classification algorithms were compared with the
suggested model, and it was discovered that, in terms of accuracy, Vision
Transformer-based feature extraction and additional Green Chromatic Coordinate
feature with SVM classification achieved an accuracy of (GCCViT-SVM) - 99.69%,
whereas after quantization for IoT device integration achieved an accuracy of
- 97.41% while almost reducing 4x in size. Our findings have profound
implications because they have the potential to transform how farmers identify
crop illnesses with precise and fast information, thereby preserving
agricultural output and ensuring food security.

Keywords: Plant disease classification, Deep learning, PlantVillage,
Attention, Embedded devices, Artificial Intelligence

Affiliations
1 Department of Electrical and Electronics Engineering, Birla Institute of
Technology, Mesra, Ranchi 835215, Jharkhand, India
2 Department of Computer Science and Engineering, Maharaja Surajmal Institute
of Technology, New Delhi - 110058, India
3 Department of Remote Sensing, Birla Institute of Technology (BIT),
Mesra-835215, Ranchi. Jharkhand, India
* Authors contributed equally

##  1 Introduction

Plant diseases and unfavourable soil conditions have become more common in
recent years as a result of factors including globalisation, commerce, and
climate change (Kamilaris and Prenafeta-Boldú, 2018; Iqbal et al., 2018)[1,
2]. This has caused a pandemic-like scenario in many nations, endangering the
health of crops and the ability of people to acquire enough food and
nourishment (Mohanty et al., 2016)[3]. Since various parasitic organisms,
including bacteria, fungus, viruses, nematodes, and other plants, can cause
illness, experts must prioritize protecting agricultural plants (Barbedo,
2016[4]). Accurate diagnosis is necessary in order to handle the concerns
raised properly. Several diagnosis techniques include conventional procedures
incorporating neighbourhood plant nurseries and agricultural organisations.
These techniques could be constrained, though, by human error and the
difficulties of reaching plants across wide distances. As an alternative,
utilising software to use machine learning and deep learning approaches can
improve the accuracy of diagnosing damaged plants. New plant disease
categorization systems may now be implemented into a wide range of devices
thanks to the development of new embedded devices with high computing power,
cameras, and integration modules. Farmers may submit field photographs for
analysis, diagnosis, and action planning using this method, which also makes
it easier to perform precise diagnostic tests and preserve resources.
On the other hand, Deep neural networks, machine learning, and sensor-sourced
soil data have recently emerged as very effective methods for continually
monitoring plant health and spotting disease early warning indications
(Pradhan et al., 2022)[5]. A neural network analyses a picture of a sick plant
as input and uses the image’s processing to provide information about the
connection between the crop and the illness. The optimisation of the network
topology, node functions, and edge weights is required to build a deep network
that properly translates the input to the intended output. The method of
training deep neural networks involves changing network parameters to enhance
the mapping. Transformer-based models have excelled in completing this
difficult task (Jha et al., 2022)[6]. Notably, major developments in theory
and real-world applications have significantly improved the performance of
deep neural networks (Bengio and LeCun 2007; Schmidhuber, 2015)[7, 8]. The use
of artificial intelligence (AI) to create a variety of intelligent solutions
for practical applications has gained increasing attention, and results have
been encouraging. However, most of the work done thus far often falls short in
terms of real-time crop assessment compatibility and compromises either
classification performance or a huge memory footprint.

Moreover, numerous methods, including machine learning models, CNN models, CNN
with attention mechanisms, and CNN with Vision Transformer (ViT), have been
investigated in recent research on the categorization of plant diseases. To
extract pertinent leaf characteristics for machine learning-based classifiers
for plant diseases, considerable preprocessing is frequently necessary.
However, these models could show decreased accuracy because of the limits of
machine learning approaches. For instance, a study suggested a machine
learning model built on the PlantVillage dataset using LGBM, although the
performance measures were only 94% or less effective (Tabbakh and Barpanda,
2022)[9].
Since, Images of plant diseases have been successfully classified using CNN
models. It is difficult to encode the direction and location of diseased
sections within leaves due to their design, which largely records pixel
connections. Therefore, these models’ performance measures could not be
particularly near to 1. On the PlantVillage dataset, CNN models were trained
in several experiments, but the performance metrics fell short of 99% (Shijie
et al., 2017; Jasim and Al-Tuwaijar, 2020; Mohana et al., 2021; Sachdeva et
al., 2021)[10, 11, 12, 13]. The performance measures also fell short of 99% in
tests employing other CNN types on additional datasets (Lin et al., 2019;
Kukreja, and Kumar, 2021; Haider et al., 2021; Suri et al., 2023)[14, 15, 16,
17]. Researchers have looked into merging CNNs or pre-trained CNN models with
attention processes to increase accuracy.
Additionally, the attention mechanism functions as an adaptive filter,
assigning weights on a dynamic basis based on the pixel composition. For
instance, one research boosted performance by almost 98% when DenseNet was
combined with an attention mechanism (Chen et al., 2021a)[18]. In another
investigation, an attention mechanism-equipped pre-trained MobileNet-V2 model
obtained a performance measure of almost 97% (Chen et al., 2021b)[19]. Pre-
trained CNN models in conjunction with ViT have been shown to perform the best
in classifying plant diseases among the various methods. By combining the
advantages of CNNs with ViT, this strategy produces metrics that are very near
to 1. On the PlantVillage dataset, a research trained the CNN model used by
ViT, attaining performance metrics of over 99% (Thakur et al., 2021)[20].

This research reveals how diverse categorization methods have advanced our
understanding of plant diseases, with attention processes and the
incorporation of ViT showing promise for improving accuracy. However, it is
evident that the majority of research either focuses on a single task or has a
limited scope in terms of the categories of classes within a dataset. At the
same time, models primarily use large architectures of convolution-based
methods or transfer learning, which demand significant resources and are
afflicted with unwanted transfer bias biased due to the nature of the pre-
trained dataset, whereas the effective methods have high complexity. The
methods and flaws of the suggested study are shown in Table 1 This study
intends to present a solution for precision agriculture leveraging Vision
Transformer for image feature extraction and using RGB Chromatic coordinates
(GCC) calculation as a feature along with SVM based classification trained on
PlantVillage dataset (Hughes and Salathé, 2015) while ensuring optimization
for IoT and device applications using post-training quantization techniques.

Table 1: Analysis of existing literature Referred studies |  Approach |  Shortcomings
---|---|---
Tabbakh et al.,2022[9] |  Discussion of performance of Ml algorithms using GLCM and wavelet based statistical features |  Reduced accuracy due to completely ML based approach
Feng et al.,2019[21] |  Leveraging attention and residual networks- lightweight architecture |  Focusing on a narrow plant category and reduced accuracy due to tradeoff on memory footprint and performance
Shijie et al.,2017 [10] |  Utilizes image expansion for preprocessing and transfer learning with pre-trained weights |  No discussions about integration for real time application. Increased complexity, unwanted bias transfer and loss of task specifity due to transfer learning
Kukreja et al.,2021[15] |  Leverages matrix based convolutional techniques |  Focusing on a single plant/crop category, no integration for real time application discussed. Reduced accuracy due to limitations of purely CNN based approach
Haider et al.,2021[16] |  Deep convolutional neural networks used |  Focusing on a single plant/crop category and High computational cost due to large architecture
Thakur et al.,2021[20] |  Utilizes attention mechanism of Vision transformer with CNN |  No discussions on optimization of model for device applications. Very high computational resource requirement
Tabbakh et al.,2023[22] |  Hybrid implementation of attention based transformer with transfer learning models using pre-trained weights |  Focusing on a specific plant/crop category, no integration for real time application discussed. Unwanted bias transfer and loss of task specify. Large computational memory footprint

This paper presents a disease classification model based on Vision
Transformer, Chromatic indices and SVM which can be deployed on a local IOT
devices for disease identification of crops. The major contributions of this
paper are noted as follows: (i) Utilizing hybrid attention based – Vision
Transformer (ViT) with Support Vector Machine (SVM) for disease
classification, (ii) Leveraging Channel based analysis of Images to calculate
GCC and integrate it as a feature for classification and (iii) Implemented
post-training quantization and conversion to package the models for deployment
on IoT, Web and Smartphone based applications.
The subsequent sections of this article are organized such that Section 2
presents the methodology proposed in this study, outlining the approach taken
to address the challenges of plant disease detection. It also includes an
explanation of various machine learning (ML) and deep learning (DL) methods
utilized. Section 3 focuses on the details of the experimental setup,
providing information on the datasets, tools, and parameters used in the
evaluation of the proposed methodology, whereas in Section 4, the experimental
results are presented along with a comprehensive discussion of the findings.
This section analyzes and interprets the outcomes of the experiments with the
accuracy and effectiveness of the proposed approach. Finally, Section 5
concludes the paper, summarizing the key findings and contributions of the
study.

##  2 Materials and Methods

For disease classification, the proposed method has three steps, initially,
the attention mechanism in the Vision transformer is leveraged to extract
features, including positional features. Then, each image in the dataset is
split into RGB channel, and GCC is calculated after which Support Vector
Machine is utilized to classify the images. Apart from the proposed GCCViT-SVM
approach, the performance of some of the popular pre-trained transfer learning
models, namely – VGG-16 and InceptionV3 were compared. The methodology of
both, the proposed as well as the Transfer learning approaches is discussed in
the following sections. Fig.1 gives an overview of the proposed GCCViT-SVM.

Figure 1: Architecture of GCCViT-SVM

###  2.1 Visual Feature extraction

The vision transformer turns the images into flattened patches and converts
them into patch embeddings. Along with the patch embeddings the transformer
also incorporates standard 1-dimensional positional embeddings to retain the
positional information of the patches. An extra learnable class embeddings is
also attached before turning it into a 1- dimensional vector which is fed into
the transformer encoder Fig. 2(a) illustrates the architecture of transformer
encoder which consists of 3 main components as discussed in the following
subsections

####  2.1.1 Multi Head Self-Attention layer (MSA)

The multi head self-attention layer is used to calculate the attention using
the standard QKV self- attention (Vaswani et al., 2017)[23]. The input
features X are converted into Query (Q), Key (K) and Value (V) matrices which
are used to compute self-attention.

(a)

(b)

Figure 2: (a) Transformer encoder architecture (b) Multi-head self attention

Every element in the input feature $z\in\mathbb{R}^{N\times D}$, a weighted
sum is calculated over every value of V. The transformer encoder calculates
attention weights as

$\displaystyle\text{Attention
}(Q,K,V)=\text{softmax}\left(\frac{QK^{T}}{\sqrt{d_{k}}}\right)V\ $ (1)

Self-attention for the input feature z is calculated using

$\displaystyle\text{SA}(z)=AV\ $ (2)

Multi head self-attention (MSA) is obtained by running multiple self-attention
(SA) operations shown in (2) in parallel and their projected output is
concatenated. Fig.2(b) gives an overview of the MSA layer.

####  2.1.2 Multi-Layer Perceptron (MLP)

A multi-layer perceptron refers to a feed-forward artificial neural network.
The Vision Transformer MLP block has two layers which consists of Gaussian
Error Linear Units (GELU) non-linearity.

####  2.1.3 Layer Normalization (LN)

Layer normalization, according to Ba et al. (2016)[24] is applied before every
block. It is primarily used so as not to introduce new dependencies across two
training samples. The transformer encoder architecture alternates MSA and MLP
blocks, with LN being applied before every block and a residual connection
being established after every block.

####  2.1.4 Green Chromatic Coordinate (GCC)

Vegetation Indices are important in crop mapping using satellite and PhenoCam
data because they provide quantitative assessments of various vegetation
features that allow researchers to monitor, estimate, and analyze crop health
and growth (Reid et al., 2016; Misra et al., 2020; Grey and Ewers, 2021)[25,
26, 27]. The Normalised Difference Vegetation Index (NDVI) is a popular remote
sensing metric. It can provide data on crop physiological health. Crop mapping
indices such as the Normalised Difference Vegetation Index (NDVI), Enhanced
Vegetation Index (EVI), and Normalised Difference Water Index (NDWI), as well
as their specifications, are used in crop management. Green chromatic
coordinates (GCC) are the most often used Phenocam-derived indices from RGB
images.
Since, most of these images are generated from PhenoCams, which collect images
of vegetation throughout time. However, images are collected through UAV and
Camera area and captured through mobile phones and balloon stores as RGB. GCC
vegetation indices ,used to measure phenological changes in agriculture and
vegetation since are comparable and outperformed NDVI (Nijland et al., 2014;
Reid et al., 2016)[28, 27], are used to track agricultural and vegetation
phenological variations. Indices are used for analyzing images from satellite
and PhenoCam, assisting researchers and farmers in tracking crop development,
detecting stress and disease, estimating crop output, and making intelligent
irrigation decisions, fertilization, and pest control decisions (Aydin et al.,
2017)[29]. Moreover, different indices could be more suited for certain crops
based on climatic conditions and research objectives.
Therefore, we use the Plant Village dataset, which contains 61486 images, to
generate the green chromatic coordinate (GCC) for classifying Plant diseases.
Indices are important in crop mapping with satellite and PhenoCam data because
they give quantitative measurements of many vegetation properties, allowing
researchers to monitor and analyse crop health and growth. The Green Chromatic
Coordinate (GCC), derived from graph theory (Smith, and Smith, 2018)[30], has
been widely used in agricultural remote sensing. In graph theory, the
chromatic index of a graph defines the smallest number of colours required to
colour its edges without sharing colours with neighbouring edges. All photos
in this work are divided into RGB channels, and the index is determined as

$\displaystyle GCC=\frac{G_{DN}}{{R_{DN}+B_{DN}+G_{DN}}}\ $ (3)

Where, DN is the digital number that corresponds with the green (G), red (R)
and blue (B) channels.

###  2.2 Classification

One of the most popular machine learning approach for classification and
regression tasks is Support Vector Machines (SVM). This method seeks to
identify the best decision threshold that optimizes the margin between classes
(Cortes and Vapnik, 1995)[31]. The kernel approach for non-linear borders is
used by SVM to find the support vectors, build a hyper plane, and identify the
boundaries. SVM is dependable, manages high-dimensional data, and guards
against over fitting. The extracted reduced features from the ViT along with
GCC values were further fed into a dense layer with 64 neurons, which was
further connected to the final dense layer with 39 neurons (equal to the
number of classes) for classification. L2 regularization was applied to this
layer to implement the functioning of an SVM. This layer is further optimizing
the class boundaries of the features obtained from the Vision Transformer
backbone.

###  2.3 Quantization and size reduction for device compatibility

Post-training quantization was utilized to optimize the proposed model for use
on Mobile and IoT devices. Post-Training dynamic range quantization was
leveraged to transform the initial 32-bit floating-point model into a 8-bit
quantized model using Tensorflow Lite. A balance between reduction of large
memory footprint for the model while maintaining the high level performance
necessary for this application was achieved by quantizing both weights and
activations which makes the approach deployable on devices so as to create a
dependable solution for disease classification. Fig.3 depicts the overall
proposed scheme.

Figure 3: Proposed scheme of solution

###  2.4 Methods for comparison: Transfer Learning

For comparing the performance of our model, traditional transfer learning
approaches were applied for image classification to the dataset. Transfer
learning involves training the earlier layers of a neural network on a
different dataset, preferably with huge amount of data, and then training only
the last few layers of the neural network on the target dataset. This saves
time spent for the training of the model as well as overcomes the issue of not
having large enough datasets. Performance of two popular architectures,VGG-16
and InceptionV3 were compared for disease classification

####  2.4.1 VGG 16

VGG-16 is an implementation of the very deep convolutional neural network
introduced by Simonyan, and Zisserman, (2014)[32]. It is a relatively simple
convolution-based architecture consisting of 13 convolutional layers and 4
‘MaxPool’ layers in between. These are followed by 3 fully connected layers
and a final layer for classification.

####  2.4.2 InceptionV3

InceptionV3 is also a convolution based neural network from the inception
family. It is an improvement upon the existing InceptionV2. It introduces the
use of Label Smoothing, 7x7 factorized convolutions and uses an auxiliary
classifier which helps to send the label information in the lower levels of
the neural network (Szegedy et al., 2016)[33]. It also utilizes batch
normalization in the layers present in the side-head. At the time of its
introduction, it performed better than the other state-of-the-art models on
standardized datasets.

###  2.5 Experimental Analysis

All models used in this work were trained using GPU acceleration. All the
studies were conducted in the Windows 10 operating system running on an AMD
Ryzen 3600 CPU @ 3.60 GHz and 16GB RAM along with a NVIDIA 1660ti GPU having
6GB of VRAM. All the models were designed using TensorFlow 2.8.0 framework and
the Keras API. For disease classification the plantvillage dataset was
utilized (Hughes, and Salathé, 2015)[34]. In this study, an augmented version
of this dataset was utilized, which applies image augmentations such as random
clipping, rotation, etc., to increase the total number of images and
additional images of backgrounds without any leaves to increase the model’s
efficiency in real world applications. The final dataset used consists of a
total of 61,486 images divided across 39 classes. The division of images
across classes is not even, with some classes consisting of more than 5000
images whereas others consist of no less than 1000 images. The full details of
the classes and their samples is given in Table 2.

Table 2: Analysis of existing literature Class | Samples | Class | Samples
---|---|---|---
Apple Scab | 1000 | Grape Esca (Black Measles) | 1383
Apple Black Rot | 1000 | Bell pepper healthy | 1478
Apple cedar apple rust | 1000 | Potato Early blight | 1000
Apple healthy | 1645 | Potato healthy | 1000
Background without leaves | 1143 | Tomato Septoria leaf spot | 1771
Blueberry healthy | 1502 | Raspberry healthy | 1000
Cherry healthy | 1000 | Soybean healthy | 5090
Cherry Powdery mildew | 1052 | Tomato Yellow Leaf Curl Virus | 5357
Corn Cercospora leaf spot | 1000 | Strawberry healthy | 1000
Tomato Leaf Mold | 1000 | Peach Bacterial spot | 2297
Corn healthy | 1162 | Tomato Bacterial spot | 2127
Corn Northern Leaf Blight | 1000 | Tomato Early blight | 1000
Grape Black rot | 1180 | Tomato healthy | 1591
Bell pepper Bacterial spot | 1000 | Strawberry Leaf scorch | 1109
Grape healthy | 1000 | Orange Haunglongbing (Citrus greening) | 5507
Grape Leaf blight (Isariopsis Leaf Spot) | 1076 | Potato Late blight | 1000
Corn Common rust | 1192 | Squash Powdery mildew | 1835
Tomato Late blight | 1909 | Tomato Target Spot | 1404
Peach healthy | 1000 | Tomato mosaic virus | 1000
Tomato Spider mites | 1676 |  |

Fig. 4 shows a sample of some of the images present in the dataset. Stratified
split was utilized to split data into sets for training purposes such that
distribution of images across classes in the same ratio to ensure robustness
and enhanced training proficiency of the model.

Figure 4: Dataset image samples

Further all the image pixels were normalized between 0 to 1 by division with
255 and split into their RGB channels after which GCC was calculated to be fed
as a feature to the SVM layer. Fig.5 Shows the RGB split of a sample image.
Further analysis was done by comparing GCC values of healthy crops to the
diseased crops and Fig.6 compares the cumulative Green chromatic indices for
healthy and diseased crops. The mean value of GCCs for healthy crops was 0.42
whereas for diseased crops was 0.34.

Figure 5: RGB Channel visualization for a sample leaf image

The analysis on distribution as well as mean values indicated that GCC values
of diseased crops were inherently less than that of healthy crops for that
plant.

Figure 6: GCC Value Distribution Box-Plot: Diseased vs Healthy crop leaves

The transformer backbone used in proposed approach uses the ViT-Base
architecture. Larger ViT architectures could not be used due to hardware
limitations. Image size was set at 256x256 for all the models. The activation
function used for the ViT backbone was ‘SoftMax’ whereas all the subsequent
dense layers used ‘Categorical Cross Entropy’ as the loss function with label
smoothing set at 0.2. Table.4 illustrates the architecture of the
classification block over the ViT backbone. The VGG-16 and InceptionV3 model
were implemented using the inbuilt application module in TensorFlow. Both the
models used pretrained weights from the ImageNet Dataset. The output of these
models was flattened into a 1-D Tensor using ‘Flatten’ layer and then
‘Dropout’ layer is added with a dropout rate set at 0.5. Finally, a dense
layer with 39 neurons and SoftMax activation function is used for
classification. ‘Adam’ optimizer is used as the optimization function for both
the models, along with Categorical Cross Entropy loss. All the models were
trained for a total of 50 epochs with batch size set at 32 and post analysis
and performance comparison of model. Table.3 gives an overview of the
experimental parameters utilized for the experiment.

Table 3: Experimental parameters Function | Parameter | Value
---|---|---
Image augmentation | Rotation by a random angle in degrees | range [ -25 , 25 ]
Random shifting across the width | 0.1
Random shifting across the height | 0.1
Random shearing | 0.2
Horizontal and vertical flipping | TRUE
Random zooming | 0.2
Rescale | 1./255
Dataset Split | Training | 0.8
Validating and Testing | 0.2
Training parameters | Batch size | 32
Epochs | 50
Optimizer RMSprop | adam
Initial learning rate | 1.00e - 04
Classifier (SVM) | Regularizer | L2(0.01)
GCC | Normalization of pixels | 0-1
ViT parameters | Patch size | 4
Projection dimension | 64
Number of heads | 4
Transformer layers | 8

For analyzing the performance of the disease classification model 4 metrics
namely Accuracy, Precision, Recall and F1-score have been utilized which are
described as follows:

(a) Precision

It measures the proportion of correctly predicted positive instances among the
total predicted positive instances.

$\displaystyle\text{Precision}=\frac{TP}{TP+FP}$ (4)

(b) Accuracy

It measures the overall correctness of the model’s predictions by comparing
the number of correct predictions with the total number of predictions.

$\displaystyle\text{Accuracy}=\frac{TP+TN}{TP+TN+FP+FN}$ (5)

(c) Recall (Sensitivity or True Positive Rate)

It measures the proportion of correctly predicted positive instances among the
total actual positive instances.

$\displaystyle\text{Recall}=\frac{TP}{TP+FN}$ (6)

(d) F1-Score

It is a harmonic mean of precision and recall, providing a balanced measure
that considers both metrics.

$\displaystyle\text{F1
Score}=\frac{2\times(\text{Precision}\times\text{Recall})}{\text{Precision}+\text{Recall}}$
(7)

Where TP refers to True Positives (correctly predicted positive instances), TN
refers to True Negatives (correctly predicted negative instances), FP refers
to False Positives (incorrectly predicted positive instances), and FN refers
to False Negatives (incorrectly predicted negative instances).

Table 4: Model Summary over ViT based feature extraction Layer | Output Size | Activation
---|---|---
ViT-Base32 Output Layer ( Dense ) | 768 | GeLU
Dense | 128 | ReLU
SVM | 39 | Softmax

##  3 Results

Both the transfer learning models and the proposed approach were analyzed
using multiple metrics Table.5 shows the comparison between accuracy of the
models used in this work.

Table 5: Cross model performance comparison Model | Accuracy | Precision | Recall | F1-Score
---|---|---|---|---
VGG-16 | 88.49 | 90.01 | 88.03 | 88.76
InceptionV3 | 79.93 | 81.88 | 76.43 | 76.21
GCCViT-SVM | 99.69 | 99.63 | 99.57 | 99.59

VGG-16 model achieved an accuracy score of 88.49%. Though, it is to be noted
that VGG-16 model performs better over a higher number of epochs, hence,
training the model for a greater number of epochs could result in considerably
higher performance. However, this score still falls considerably short of the
accuracy of our proposed approach. It should also be noted that the accuracy
of the model varied considerably in each training epoch and the model loss on
both the training and validation set was on an increasing trend throughout the
training as shown in Fig. 7(a) and 7(b). The InceptionV3 model performed
poorly, achieving an accuracy of only 79.93%. It was also plagued by the same
problem of an overall increasing loss during the training.

Figure 7: (a) GCCViT-SVM accuracy on training and validation set (b) GCCViT-
SVM loss on training and validation set

On comparison with recent work, results of this study indicate tremendous
potential for the mentioned classification task, Table 7 depicts the model
performance comparison of our model with some of the recent studies. The
proposed model achieved an accuracy of 99.69% for the plant Village dataset
which is higher than the work discussed in Table 7. It can be observed that
attention based networks show better performance since they extract additional
positional embeddings, but even in comparison to approaches based on vision
transformer, the proposed model is less complex while still ensuring superior
performance pertaining to the additional feature leveraged by calculating
Green Chromatic Coordinate for input data. Also, it is to be noted that the
model achieved higher accuracy in training and validation set much earlier in
the training phase than the other two models. The model loss on both the
training and test set was also decreasing throughout the training phase, and
was considerably lower than the other models.

In terms of class-wise performance, the proposed model achieved a perfect
score across all 3 metrics for more than 15 classes. The class wise overview
of model performance is given in Table.6. Whereas Fig.8 depicts the confusion
matrix for the model across all 39 classes labelled 0 – 38 in the same order
as in Table 6.

By quantizing the proposed model post training and converting both activations
and weights to 8-bit precision, 4 times reduction in size of the model was
observed with approximately only 2.28% loss in accuracy. Table.8 gives an
overview of the changes post quantization on the proposed model.

Figure 8: Confusion matrix for GCCViT-SVM

##  4 Discussions

This section presents a comprehensive discussion on the findings and
implications of the proposed methods. Key aspects of the study are addressed,
including the challenges posed by the dataset, the nature of image processing
and feature extraction, and experimental parameter optimization. Additionally,
potential avenues have been discussed for future work and highlight the
significance of the findings in the broader context of image classification.

Table 6: Class-wise performance of GCCViT-SVM Label | Class | Precision | Recall | F-1 Score
---|---|---|---|---
0 | Apple Scab | 1 | 1 | 1
1 | Apple Black Rot | 1 | 1 | 1
2 | Apple Cedar apple rust | 1 | 1 | 1
3 | Apple healthy | 1 | 1 | 1
4 | Background without leaves | 1 | 0.99 | 1
5 | Blueberry healthy | 1 | 1 | 1
6 | Cherry healthy | 1 | 1 | 1
7 | Cherry Powdery mildew | 1 | 0.99 | 0.99
8 | Corn Cercospora leaf spot | 0.99 | 0.98 | 0.98
9 | Corn Common rust | 1 | 1 | 1
10 | Corn healthy | 0.98 | 0.99 | 0.99
11 | Corn Northern Leaf Blight | 1 | 1 | 1
12 | Grape Black rot | 1 | 0.99 | 1
13 | Grape Esca (Black Measles) | 0.99 | 1 | 1
14 | Grape healthy | 0.99 | 1 | 1
15 | Grape Leaf blight (Isariopsis Leaf Spot) | 1 | 1 | 1
16 | Orange Haunglongbing (Citrus greening) | 1 | 1 | 1
17 | Peach Bacterial spot | 1 | 1 | 1
18 | Peach healthy | 1 | 1 | 1
19 | Bell pepper Bacterial spot | 1 | 1 | 1
20 | Bell pepper healthy | 1 | 1 | 1
21 | Potato Early blight | 1 | 1 | 1
22 | Potato healthy | 1 | 1 | 1
23 | Potato Late blight | 1 | 1 | 1
24 | Raspberry healthy | 1 | 1 | 1
25 | Soybean healthy | 1 | 1 | 1
26 | Squash Powdery mildew | 1 | 1 | 1
27 | Strawberry healthy | 1 | 1 | 1
28 | Strawberry Leaf scorch | 1 | 1 | 1
29 | Tomato Bacterial spot | 1 | 1 | 1
30 | Tomato Early blight | 0.99 | 0.97 | 0.98
31 | Tomato healthy | 1 | 0.99 | 1
32 | Tomato Late blight | 0.99 | 1 | 1
33 | Tomato Leaf Mold | 1 | 1 | 1
34 | Tomato Septoria leaf spot | 0.98 | 0.99 | 0.99
35 | Tomato Spider mites | 0.98 | 0.99 | 0.99
36 | Tomato Target Spot | 1 | 1 | 1
37 | Tomato mosaic virus | 1 | 1 | 1
38 | Tomato Yellow Leaf Curl Virus | 1 | 0.99 | 1
Table 7: Performance Comparison with recent work on Plant Village Referred studies |  Algorithm (classification) |  Accuracy |  Precision |  Recall |  F1-Score
---|---|---|---|---|---
Tabbakh and Barpanda, 2022[9] |  Machine learning model using LGBM model | 0.9439 | 0.9475 | 0.9476 | 0.9472
Mohana et al., 2021 [10] |  CNN | 0.9677 | 0.9646 | 0.9625 | 0.9635
Sachdeva et al., 2021[11] |  Deep Convolutional neural network with Bayesian learning | 0.989 | 0.982 | 0.979 | 0.9804
Jasim and Al-Tuwaijari, 2020[12] |  CNN | 0.9803 | 0.9827 | 0.9801 | 0.9814
Shijie, et al., 2017 [13] |  VGG16 | 0.88 | - | - | -
Karthik et al., 2020[35] |  Attention and the residual network | 0.9583 | 0.962 | 0.956 | 0.9589
Chen et al., 2021a [18] |  DenseNet along with attention approach | 0.9794 | 0.8959 | 0.8671 | 0.8807
Chen et al., 2021b [19] |  pre-trained MobileNet-V2 and attention mechanism | 0.9668 | 0.9749 | 0.9583 | 0.9664
Thakur et al., 2021 [20] |  PlantViT | 0.9861 | 0.9824 | 0.9833 | 0.9828
Tabbakh and Barpanda, 2023[22] |  TLMViT (VGG19 followed by ViT ) | 0.9881 | 0.9872 | 0.9876 | 0.9873
Proposed model |  GCCViT-SVM (GCC and ViT output features fed to SVM ) | 0.9969 | 0.9978 | 0.9965 | 0.9971

###  4.1 Imabalanced Dataset

One of the challenges encountered in this study was the imbalanced nature of
the dataset. The dataset consisted of 39 classes, but the number of samples
per class varied significantly. This class imbalance poses a significant
obstacle for image classification tasks as it can lead to biased model
performance. To address this issue, we employed techniques such as data
augmentation and stratification of split during training. Data augmentation
techniques, including rotation, flipping, and scaling, were used to generate
additional samples for underrepresented classes. Moreover, the use of
stratified split provided a way to assign same ratio of test and train sets
amongst the minority as well as majority classes, thereby reducing the impact
of the class imbalance on the model’s performance. However, it must be noted
that better balanced datasets can influence the performance of the model
positively and make it further scalable.

Table 8: Model Comparison before and after quantization Model | Before Quantization | After Quantization (TF-Lite format)
---|---|---
Accuracy | 99.69% | 97.41%
Size | 338.4 MB | 84.6 MB
Weights and Activations | 32 bit | 8 bit

###  4.2 Image processing and feature extraction

The Images utilized for the experiment, when fed to the model rely completely
on the model’s capability to extract features. To ensure the integration of
relevant techniques which align with the agricultural literature, Indices like
Green Chromatic Coordinate was utilized to analyze the crop health and the
spread of the disease.

It must be noted that further experiments pertinent to agricultural
methodologies, such as analysis of near-infrared reflectance, are required to
analyze the density of green in the crops or vegetation, which can further
enhance the model’s capability in detecting diseases and improve large-scale
implementation and usability.

###  4.3 Hyperparameters

Optimizing hyperparameters is a critical step in achieving optimal model
performance. This study implemented various experimental parameter tuning
approaches to identify the best configuration for our image classification
model. Grid search and random search were utilized to explore a wide range of
parameter combinations and evaluate their impact on the model’s performance.
Additionally, techniques such as cross-validation to estimate the
generalization performance of different hyperparameter settings and ensure the
reliability of the results were leveraged. In terms of reducing the memory
footprint and ensuring low-computational resource device compatibility (IoT,
Mobiles etc.) Post-training quantization was used. Further fine-tuning of
hyperparameters, including learning rate, batch size, quantization aware
training, mixed quantization, and regularization strength, may significantly
improve the model’s ability to generalize to unseen data, increase overall
classification accuracy, and reduce memory footprint.

###  4.4 Deployment and user interfaces

Farmers and agriculture have historically served as the cornerstone of the
Indian economy. This research not only presents its findings but also lays the
groundwork for the development of a scalable and cost-effective solution that
can be readily implemented to benefit the agricultural community. The
comprehensive website, built upon this model to maximize accuracy, is
currently in the developmental phase. Future work will encompass the creation
of a mobile application and the integration of additional algorithms for crop
recommendation and soil nutrition monitoring, aiming to create an all-
encompassing solution.

##  5 Conclusions

In this paper, a hybrid model called GCCViT-SVM is proposed for plant disease
classification, combining Support Vector Machines with a vision transformer.
The GCCViT-SVM model consists of four stages: data acquisition, image
augmentation, feature extraction with GCC calculation, and classification.
Initially, the model is trained and evaluated using the PlantVillage dataset
and all its 39 classes. Image augmentation techniques, including rotation,
shifting, shearing, zooming, and flipping, are applied to increase the number
of training samples. The feature extraction process involves a vision
transformer that is employed to extract deep features based on the initial
features and then GCC for each image is calculated. Finally, a MLP head
classifier along with SVM determines the class to which the leaf belongs. The
performance of the proposed GCCViT-SVM model is evaluated using various
metrics such as accuracy, loss, precision, F1-score, and recall. Experimental
results show that the model achieves high accuracy, and the validation
accuracy reaches 99.69% with corresponding training accuracy of 100%.
Furthermore, the performance of GCCViT-SVM is compared to transfer learning-
based models (demonstrating the effectiveness of incorporating attention based
networks). GCCViT -SVM outperforms the transfer learning-based model,
achieving higher validation accuracy and lower validation loss for all classes
of the dataset. It outperforms VGG -16 by 11.2% and inception v3 by 19.7% in
terms of accuracy. The findings of this study highlight the benefits of data
augmentation, the effectiveness of ViT for deep feature extraction with
traditional remote sensing and image processing based GCC, and classification
capability of traditional Machine learning classification algorithms, SVM for
the scope of this experimentation. The model is then converted into TF. Lite
model includes size reduction by quantization to ensure compatibility with IoT
devices, which can then be accessed through mobile or web-app, achieving a
single stop software solution for crop disease classification. Further
research is encouraged with improvements in dataset quality, integration, and
experimentation with multiple image processing and feature extraction
techniques for better performance and stability.

## References

  * [1] Andreas Kamilaris and Francesc X Prenafeta-Boldú.  Deep learning in agriculture: A survey.  Computers and electronics in agriculture, 147:70–90, 2018.
  * [2] Zahid Iqbal, Muhammad Attique Khan, Muhammad Sharif, Jamal Hussain Shah, Muhammad Habib ur Rehman, and Kashif Javed.  An automated detection and classification of citrus plant diseases using image processing techniques: A review.  Computers and electronics in agriculture, 153:12–32, 2018.
  * [3] Sharada P Mohanty, David P Hughes, and Marcel Salathé.  Using deep learning for image-based plant disease detection.  Frontiers in plant science, 7:1419, 2016.
  * [4] Jayme Garcia Arnal Barbedo.  A review on the main challenges in automatic plant disease identification based on visible range images.  Biosystems engineering, 144:52–60, 2016.
  * [5] Abhishek Kumar Pradhan, Sudhansu Swain, and Jitendra Kumar Rout.  Role of machine learning and cloud-driven platform in iot-based smart farming.  In Machine Learning and Internet of Things for Societal Issues, pages 43–54. Springer Nature Singapore, 2022.
  * [6] Shashwat Jha, Vishvaditya Luhach, and Raju Poddar.  Retinal malady classification using ai: A novel vit-svm combination architecture.  In 2022 6th International Conference on Computing Methodologies and Communication (ICCMC), pages 1659–1664. IEEE, 2022.
  * [7] Yoshua Bengio and Yann LeCun.  Scaling learning algorithms towards ai.  Large-scale kernel machines, 34:1–41, 2007.
  * [8] Jürgen Schmidhuber.  Deep learning in neural networks: An overview.  Neural Networks, 61:85–117, 2015.
  * [9] Asghar Tabbakh and Somanath Satapathy Barpanda.  Evaluation of machine learning models for plant disease classification using modified glcm and wavelet based statistical features.  Traitement du Signal, 39(6):1893, 2022.
  * [10] R. M Mohana, C Kishor Kumar Reddy, and P. R Anisha.  A study and early identificatıon of leaf diseases in plants using convolutional neural network.  In Smart Computing Techniques and Applications: Proceedings of the Fourth International Conference on Smart Computing and Informatics, Volume 2, pages 693–709. Springer Singapore, 2021.
  * [11] Gargi Sachdeva, Parvinder Singh, and Pooja Kaur.  Plant leaf disease classification using deep convolutional neural network with bayesian learning.  Materials Today: Proceedings, 45:5584–5590, 2021.
  * [12] Mohammed A Jasim and Jaseem M Al-Tuwaijari.  Plant leaf diseases detection and classification using image processing and deep learning techniques.  In 2020 International Conference on Computer Science and Software Engineering (CSASE), pages 259–265. IEEE, 2020.
  * [13] Jia Shijie, Jiang Peiyi, and Hou Siping.  Automatic detection of tomato diseases and pests based on leaf images.  In 2017 Chinese automation congress (CAC), pages 2537–2510. IEEE, 2017.
  * [14] Devina Suri, Sheetal Saksena, Upasana Sehgal, and Rinku Garg.  Disease classification in wheat from images using cnn.  In 2023 13th International Conference on Cloud Computing, Data Science & Engineering (Confluence), pages 566–571. IEEE, 2023.
  * [15] Zhihui Lin, Shuai Mu, Fei Huang, Khurram A Mateen, Minghui Wang, Wenzhong Gao, and Jiaya Jia.  A unified matrix-based convolutional neural network for fine-grained image classification of wheat leaf diseases.  IEEE Access, 7:11570–11590, 2019.
  * [16] Varun Kukreja and Dheeraj Kumar.  Automatic classification of wheat rust diseases using deep convolutional neural networks.  In 2021 9th International Conference on Reliability, Infocom Technologies and Optimization (Trends and Future Directions)(ICRITO), pages 1–6. IEEE, 2021.
  * [17] Waseem Haider, Aamer U Rehman, Nasruddin M Durrani, and Shahzad U Rehman.  A generic approach for wheat disease classification and verification using expert opinion for knowledge-based decisions.  IEEE Access, 9:31104–31129, 2021.
  * [18] Jie Chen, Wei Wang, Dengwen Zhang, Atta Zeb, and Yashar A Nanehkaran.  A attention embedded lightweight network for maize disease recognition.  Plant Pathology, 70(3):630–642, 2021.
  * [19] Jie Chen, Dengwen Zhang, Atta Zeb, and Yashar A Nanehkaran.  Identification of rice plant diseases using lightweight attention networks.  Expert Systems with Applications, 169:114514, 2021.
  * [20] Pragya S Thakur, Preeti Khanna, Tarkeshwari Sheorey, and Ajita Ojha.  Vision transformer for plant disease detection: Plantvit.  In International Conference on Computer Vision and Image Processing, pages 501–511. Springer International Publishing, 2021.
  * [21] Chao Feng, Han Zhang, Shuai Wang, Yilin Li, Hongli Wang, and Fei Yan.  Structural damage detection using deep convolutional neural network and transfer learning.  KSCE Journal of Civil Engineering, 23:4493–4502, 2019.
  * [22] Asghar Tabbakh and Somanath Satapathy Barpanda.  A deep features extraction model based on the transfer learning model and vision transformer” tlmvit” for plant disease classification.  IEEE Access, 2023.
  * [23] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, and Illia Polosukhin.  Attention is all you need.  In Advances in Neural Information Processing Systems, volume 30, 2017.
  * [24] Jimmy Lei Ba, Jamie Ryan Kiros, and Geoffrey E Hinton.  Layer normalization.  arXiv preprint arXiv:1607.06450, 2016.
  * [25] R E Gray and R M Ewers.  Monitoring forest phenology in a changing world.  Forests, 12(3):297, 2021.
  * [26] Gaurav Misra, Fergus Cawkwell, and Angela Wingler.  Status of phenological research using sentinel-2 data: A review.  Remote Sensing, 12(17):2760, 2020.
  * [27] A. M. Reid, W. K. Chapman, C. E. Prescott, and W. Nijland.  Using excess greenness and green chromatic coordinate colour indices from aerial images to assess lodgepole pine vigour, mortality and disease occurrence.  Forest Ecology and Management, 374:146–153, 2016.
  * [28] W. Nijland, R. De Jong, S. M. De Jong, M. A. Wulder, C. W. Bater, and N. C. Coops.  Monitoring plant condition and phenology using infrared sensitive consumer grade digital cameras.  Agricultural and Forest Meteorology, 184:98–106, 2014.
  * [29] A. Çay Aydin and B. Polat.  Image analysis applications in plant growth and health assessment.  J. Agric. Fac. Mustafa Kemal Univ., 22(1):112, 2017.
  * [30] Carl A Smith and Allan W Smith.  Introduction to the green chromatic index.  CRC Press, 2018.
  * [31] Corinna Cortes and Vladimir Vapnik.  Support-vector networks.  Machine learning, 20:273–297, 1995.
  * [32] Karen Simonyan and Andrew Zisserman.  Very deep convolutional networks for large-scale image recognition.  arXiv preprint arXiv:1409.1556, 2014.
  * [33] Christian Szegedy, Vincent Vanhoucke, Sergey Ioffe, Jon Shlens, and Zbigniew Wojna.  Rethinking the inception architecture for computer vision.  Proceedings of the IEEE conference on computer vision and pattern recognition, pages 2818–2826, 2016.
  * [34] David Hughes and Marcel Salathé.  An open access repository of images on plant health to enable the development of mobile disease diagnostics.  arXiv preprint arXiv:1511.08060, 2015.
  * [35] R Karthik, M Hariharan, S Anand, P Mathikshara, Arun Johnson, and R Menaka.  Attention embedded residual cnn for disease detection in tomato leaves.  Applied Soft Computing, 86:105933, 2020.