# Rotated time-frequency lattices are sets of stable sampling for continuous
wavelet systems

Nicki Holighaus1 and Günther Koliander2  Acoustics Research Institute,
Austrian Academy of Sciences, Wohllebengasse 12–14, 1040 Vienna, Austria.
Email<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

We provide an example for the generating matrix $A$ of a two-dimensional
lattice $\Gamma=A\mathbb{Z}^{2}$, such that the following holds: For any
sufficiently smooth and localized mother wavelet $\psi$, there is a constant
$\beta(A,\psi)>0$, such that $\beta\Gamma\cap(\mathbb{R}\times\mathbb{R}^{+})$
is a set of stable sampling for the wavelet system generated by $\psi$, for
all $0<\beta\leq\beta(A,\psi)$. The result and choice of the generating matrix
are loosely inspired by the studies of low discrepancy sequences and uniform
distribution modulo $1$. In particular, we estimate the number of lattice
points contained in any axis parallel rectangle of fixed area. This estimate
is combined with a recent sampling result for continuous wavelet systems,
obtained via the oscillation method of general coorbit theory.

###### Index Terms:

wavelet transforms, frames, lattice rules, oscillation method

##  I Introduction

A wavelet system [1] is a collection of functions generated from a single
prototype, the _mother wavelet_ , by translation and dilation. Here, we
consider a complex mother wavelet $\psi\in\mathbf{L}^{2}(\mathbb{R})$, such
that its Fourier transform vanishes for negative frequencies, i.e.,
$\hat{\psi}(\xi)=0$ for $\xi\in(-\infty,0]$. With a slight abuse of notation,
we denote the space of square-integrable functions with this property as
$\mathcal{F}^{-1}(\mathbf{L}^{2}(\mathbb{R}^{+}))$. It is a Hilbert space with
respect to the standard inner product on $\mathbf{L}^{2}(\mathbb{R})$. Mother
wavelets $\psi\in\mathcal{F}^{-1}(\mathbf{L}^{2}(\mathbb{R}^{+}))$ are
sometimes called _analytic_ , although the terminology _analytic wavelet
transform_ is not used consistently [2, 3]. The associated continuous wavelet
system is defined as

$\Psi=(\psi_{x,s})_{x\in\mathbb{R},s\in\mathbb{R}^{+}},\ \text{where}$ (1)
$\psi_{x,s}:=\mathbf{T}_{x}\mathbf{D}_{1/s}\psi=\sqrt{s}\psi\left(s(\bullet-x)\right).$
(2)

Here, $\mathbf{D}_{s}$ with $s\in\mathbb{R}^{+}$ denotes a unitary dilation by
the factor $s$, and $\mathbf{T}_{x}$ denotes translation by $x\in\mathbb{R}$.
We note that the above definition is slightly unusual in the sense that we
associate large scales with small values of $s$ [1]. Under the given
conditions on the mother wavelet $\psi$, the natural extension of $\Psi$ to
negative scales $s<0$ has no further consequences on our results and is
therefore omitted. In the following, we refer to
$\Lambda=\mathbb{R}\times\mathbb{R}^{+}$ as the _phase space_ associated with
$\Psi$.

Sets of stable sampling for the continuous wavelet system $\Psi$ are discrete
sets $\Lambda_{D}\subset\Lambda$, such that
$(\psi_{x,s})_{(x\,;\,s)^{\intercal}\in\Lambda_{D}}$ forms a frame, cf.
Section II. Such sets have been systematically studied at least since the
popularization of frame theory and multiresolution analyses in the 1980s [4,
5, 6], although certain wavelet bases were known earlier, as discussed in [1,
Chapter 4.2.1]. Most established sampling schemes for wavelets follow the same
formula:

  1. 1.

Select a basis $a\in(1,\infty)$ and consider all scales $a^{j}$,
$j\in\mathbb{Z}$.

  2. 2.

Select a relative translation step $b\in(0,\infty)$ and consider, at scale
$a^{j}$, the translations $a^{-j}\cdot lb$, $l\in\mathbb{Z}$.

The density of the resulting set $\Lambda_{D}=\big{\\{}\binom{a^{-j}\cdot
lb}{a^{j}}\colon j,l\in\mathbb{Z}\big{\\}}\subset\Lambda$ can be controlled by
scaling $a$ and $b$. Although variations on this scheme are occasionally
studied, e.g., for the construction of shift-invariant wavelet systems [7],
they often only differ by adding additional points to $\Lambda_{D}$.

A few recent works have explored low discrepancy sets and sequences, as
commonly used in the quasi-Monte Carlo method [8], for selecting discrete
subsets from $\Psi$ and other time-frequency systems [9, 10]. In particular,
the numerical results in the work [10] suggest that the restriction of certain
sheared lattices to the upper half-plane form sets of stable sampling for
_inhomogeneous_ wavelet systems which are obtained by removing the scales
$s<1$ and adding an appropriate substitute.

Contribution:  In this work, we consider the rotated square lattice
$\Gamma=A\mathbb{Z}^{2}$, with $A=\begin{pmatrix}1&-\alpha\\\
\alpha&1\end{pmatrix}$, for a specific choice of $\alpha$. We show that
isotropic dilations of $\Gamma$, restricted to the upper half-plane, form sets
of stable sampling for the continuous wavelet system $\Psi$. The main step
towards this result is achieved by proving that the number of lattice points
contained in an arbitrary half-open rectangle is proportional to its area,
provided that the rectangle has at least a certain minimal area. Our result
relies on choosing $\alpha$ to be badly approximable, a property that also
plays a prominent role in the construction of Kronecker sequences [11, 12].
The choice of $\Gamma$ further bears some resemblance to lattice rules [13], a
popular construction rule for low discrepancy sequences.

##  II Preliminaries

For any $\psi\in\mathcal{F}^{-1}(\mathbf{L}^{2}(\mathbb{R}^{+}))$, the
continuous wavelet transform defined for all $(x\,;\,s)^{\intercal}\in\Lambda$
by

$\begin{split}W_{\psi}f(x,s)=\langle f,\psi_{x,s}\rangle_{L_{2}},\ \ \text{for
all }f\in\mathcal{F}^{-1}(\mathbf{L}^{2}(\mathbb{R}^{+})),\end{split}$ (3)

is a function in $\mathbf{L}^{\infty}(\Lambda)$. If the so-called
admissibility constant $C_{\psi}=\|\psi/(\bullet)\|^{2}_{2}$ is finite, then
the system $\Psi\subset\mathcal{F}^{-1}(\mathbf{L}^{2}(\mathbb{R}^{+}))$ is a
_continuous tight frame_[14, 15] with frame bound $C_{\psi}$. In particular,
if $C_{\psi}=1$, then
$\|f\|_{\mathbf{L}^{2}(\mathbb{R})}=\|W_{\psi}f\|_{\mathbf{L}^{2}(\Lambda)}$,
for all $f\in\mathcal{F}^{-1}(\mathbf{L}^{2}(\mathbb{R}^{+}))$. The image
space
$\widetilde{\mathcal{H}}=W_{\psi}(\mathcal{F}^{-1}(\mathbf{L}^{2}(\mathbb{R}^{+})))$
of the wavelet transform with mother wavelet $\psi$ is a reproducing kernel
Hilbert space of continuous, square-integrable functions [1, 15].

This work is concerned with the study of certain discrete subsets
$\Lambda_{D}\subset\Lambda$, such that
$(\psi_{x,s})_{(x\,;\,s)^{\intercal}\in\Lambda_{D}}$ is a discrete frame [15],
i.e.,

$A\|f\|_{2}^{2}\leq\sum_{(x\,;\,s)^{\intercal}\in\Lambda_{D}}|\langle
f,\psi_{x,s}\rangle|^{2}\leq B\|f\|_{2}^{2},$ (4)

for all $f\in\mathcal{F}^{-1}(\mathbf{L}^{2}(\mathbb{R}^{+}))$ and some
constants $0<A\leq B<\infty$. When we say that $\Lambda_{D}$ is a set of
stable sampling for the continuous wavelet system $\Psi$, we mean precisely
that $\Lambda_{D}$ is a set of stable sampling for $\widetilde{\mathcal{H}}$,
which, noting
$C_{\psi}\|f\|_{2}^{2}=\|W_{\psi}f\|_{\widetilde{\mathcal{H}}}^{2}$, is
equivalent to (4).

##  III The Frame Property from Oscillation Estimates

The oscillation method was introduced by Feichtinger and Gröchenig in their
seminal works studying atomic decompositions in _coorbit spaces_ [16, 17, 18].
Although the discretization results in those works can be applied to the
wavelet transform on $\mathcal{F}^{-1}(\mathbf{L}^{2}(\mathbb{R}^{+}))$, it is
nontrivial to show the density and separation requirements therein for the
specific point sets $c\Gamma$ that we consider. Hence, it is more convenient
to rely on _generalized coorbit theory_ , as introducted in [19] and extended
in [20, 21]. Applied to continuous frames on Hilbert spaces $\mathcal{H}$,
this variant of the oscillation method yields a sufficient condition for
irregular sets of stable sampling that can informally be summarized as
follows: Assume that $\Phi=(\phi_{m})_{m\in M}$ is a localized [19],
continuous tight frame for $\mathcal{H}$, and there is a countable covering
$\mathcal{V}=(V_{j})_{j\in J}$ of $M$, such that the oscillation of $\Phi$
with respect to $\mathcal{V}$ is small in the norm of some Schur-type algebra
$\mathcal{A}$ [22]. Then any set $(m_{j})_{j\in J}$, with $m_{j}\in V_{j}$ for
all $j\in J$, is a set of stable sampling for $\Phi$, or equivalently,
$(\phi_{m_{j}})_{j\in J}$ is a discrete frame for $\mathcal{H}$. More
precisely, given a function
$\Xi\colon\Lambda\times\Lambda\rightarrow\mathbb{C}$, with $|\Xi|\equiv 1$,
the $\Xi$-oscillation ${\mathrm{osc}}_{\mathcal{V}}$ of $\Phi$ with respect to
$\mathcal{V}$ is given by

$\begin{split}\@ADDCLASS{ltx_eqn_lefteqn}$\displaystyle{\mathrm{osc}}_{\mathcal{V}}(m_{0},m_{1})$\mbox{}\hfil\\\
&=\sup_{n\in\mathcal{V}_{m_{1}}}\left|\langle\phi_{m_{0}},\phi_{m_{1}}\rangle-\Xi(m_{1},n)\langle\phi_{m_{0}},\phi_{n}\rangle\right|,\end{split}$
(5)

where $\mathcal{V}_{m_{1}}:=\bigcup_{j\in J:m_{1}\in V_{j}}V_{j}$. The
appropriate choice of $\Xi$ is crucial to achieve small $\mathcal{A}$-norm of
${\mathrm{osc}}_{\mathcal{V}}$.

In a recent paper concerned with warped time-frequency systems [23], of which
the continuous wavelet systems $\Psi$ are a special case, it was shown that
there exists a family of coverings
$\mathcal{V^{\delta}}=(V^{\delta}_{j})_{j\in J}$ of
$\Lambda=\mathbb{R}\times\mathbb{R}^{+}$, comprised of half-open rectangles of
identical area $\delta^{2}$, such that the oscillation of the wavelet system
$\Psi$ with respect to $\mathcal{V}^{\delta}$ converges to zero in
$\mathcal{A}$-norm, for $\delta\rightarrow 0$. In particular, [23, Example
4.1, Corollary 6.9] imply the following result.

######  Theorem III.1.

Let $\psi\in\mathcal{F}^{-1}(\mathbf{L}^{2}(\mathbb{R}^{+}))$, with
$C_{\psi}=1$, such that $\mathcal{F}(\psi)\in\mathcal{C}^{2}(\mathbb{R})$,
with
$\max\\{(\bullet)^{5},(\bullet)^{-5}\\}\cdot\mathcal{F}(\psi)\in\mathcal{C}_{0}(\mathbb{R})\cap\mathbf{L}^{2}(\mathbb{R}^{+})$.
Define $\mathcal{V}^{\delta}=(V^{\delta}_{k,\ell})_{k,\ell\in\mathbb{Z}}$ by

$V^{\delta}_{k,\ell}=\left[\frac{\delta^{2}k}{|I^{\delta}_{\ell}|},\frac{\delta^{2}(k+1)}{|I^{\delta}_{\ell}|}\right)\times
I^{\delta}_{\ell},$

with $I^{\delta}_{\ell}=[e^{\delta\ell},e^{\delta(\ell+1)})$. Then there
exists $\delta(\Psi)>0$, such that for any $0<\delta\leq\delta(\Psi)$, and any
discrete set $\Lambda_{D}\subset\Lambda$ with

$\inf_{k,\ell\in\mathbb{Z}}|\Lambda_{D}\cap V^{\delta}_{k,\ell}|>0\text{ and
}\sup_{k,\ell\in\mathbb{Z}}|\Lambda_{D}\cap V^{\delta}_{k,\ell}|=:N<\infty,$

the collection $(\psi_{x,s})_{(x\,;\,s)^{\intercal}\in\Lambda_{D}}$ is a frame
for $\mathcal{F}^{-1}(\mathbf{L}^{2}(\mathbb{R}^{+}))$.

Since Theorem III.1 is an application of the results referred to above, its
proof is not self-contained and deferred to the Appendix. In the next section,
we show that certain rotated lattices satisfy the conditions on $\Lambda_{D}$
in Theorem III.1.

##  IV Wavelet Frames by Sampling on Lattices

In the following, we set $\alpha=\varphi^{-1}=\frac{\sqrt{5}-1}{2}$, where
$\varphi$ is the golden ratio, and consider the matrix

$A=\begin{pmatrix}1&-\alpha\\\ \alpha&1\end{pmatrix}\;.$ (6)

With this choice of $A$, we define the lattice

$\Gamma=A\mathbb{Z}^{2},$ (7)

i.e., $\Gamma=\\{A\begin{pmatrix}n\\\ m\end{pmatrix}\colon
n,m\in\mathbb{Z}\\}$. As we will see, any axis parallel rectangle $\Delta$ of
a given size has clear bounds on the number of points in $\Delta\cap\Gamma$
that do not depend on its position or ratio of its side lengths. Before we
proceed to prove a formal version of this statement, we derive some properties
of $\alpha$ that will be subsequently used.

######  Proposition IV.1.

Let $\alpha=\varphi^{-1}=\frac{\sqrt{5}-1}{2}$. Then, for all
$n\in\mathbb{N}$,

$\alpha^{n}=(-1)^{n-1}(f_{n}\alpha-f_{n-1}),$ (8)

where $f_{n}$ is the $n$-th Fibonacci number, defined by $f_{0}=0$, $f_{1}=1$
and, for $n\geq 2$, $f_{n}=f_{n-1}+f_{n-2}$.

Moreover, for any $n\in\mathbb{N}$, we have

$\alpha^{n-1}f_{n+2}+\alpha^{n}f_{n+1}=2+\alpha=\varphi^{2}.$ (9)

###### Proof.

We first prove (8). For $n=1$, the statement trivially holds, while for $n=2$,

$\alpha^{2}=\varphi^{-2}=\frac{1}{1+\varphi}=1-\frac{\varphi}{1+\varphi}=1-\alpha$
(10)

as desired. The induction step follows from

$\begin{split}\alpha^{n+1}=\alpha^{n}\cdot\alpha&=(-1)^{n-1}(f_{n}\alpha-
f_{n-1})\cdot\alpha\\\
&\stackrel{{\scriptstyle\eqref{eq:alphasq}}}{{=}}(-1)^{n-1}(f_{n}(1-\alpha)-f_{n-1}\alpha)\\\
&=(-1)^{n-1}(f_{n}-(f_{n}+f_{n-1})\alpha)\\\ &=(-1)^{n}(f_{n+1}\alpha-
f_{n}).\end{split}$

We next prove (9). Inserting $n=1$ on the left hand side immediately yields

$\alpha^{0}f_{3}+\alpha^{1}f_{2}=2+\alpha,$

as desired. The induction step follows from

$\displaystyle\alpha^{n}f_{n+3}+\alpha^{n+1}f_{n+2}$
$\displaystyle=\alpha^{n}(f_{n+2}+f_{n+1})+\alpha^{n+1}f_{n+2}$
$\displaystyle=(\alpha^{2}+\alpha)\alpha^{n-1}f_{n+2}+\alpha^{n}f_{n+1}$
$\displaystyle\stackrel{{\scriptstyle\eqref{eq:alphasq}}}{{=}}\alpha^{n-1}f_{n+2}+\alpha^{n}f_{n+1}$
$\displaystyle=2+\alpha.\hfill\qed$

We are now ready to show that any axis-parallel rectangle with sufficient area
contains at least one lattice point.

######  Lemma IV.2.

Let $\Delta=[a,b)\times[c,d)$ be an axis parallel half-open rectangle of size
$\mu(\Delta)\geq 2+\alpha=\varphi^{2}$, where $\mu$ is the standard Lebesgue
measure on $\Lambda=\mathbb{R}\times\mathbb{R}^{+}$. Then
$\lvert\Delta\cap\Gamma\rvert\geq 1$.

###### Proof.

Given $\Delta=[a,b)\times[c,d)$, with $\Delta\cap\Gamma=\emptyset$, we assume,
without loss of generality, that there exist $a_{0}\in[a,b)$ and
$c_{0}\in[c,d)$, such that

$\binom{b}{c_{0}},\,\binom{a_{0}}{d}\in\Gamma.$

Otherwise, there is a nonzero $\begin{pmatrix}b_{0}\\\
d_{0}\end{pmatrix}\in[0,\infty)^{2}$, such that $(\Delta\ +\
[0,b_{0})\times[0,d_{0}))\,\cap\,\Gamma=\emptyset$.

We now show that $\Delta\cap\Gamma=\emptyset$ implies that
$\mu(\Delta)<2+\alpha$. To this end, we first consider the case that both
$b-a\geq 1$ and $d-c\geq 1$. Because $\binom{a_{0}+\alpha}{d-1}\in\Gamma$ and
$d-1\in[c,d)$, we have $a_{0}+\alpha\geq b$, since otherwise
$\binom{a_{0}+\alpha}{d-1}\in\Gamma\cap\Delta$. Similarly, because
$\binom{a_{0}-1}{d-\alpha}\in\Gamma$ and $d-\alpha\in[c,d)$, we have
$a_{0}-1<a$. Hence,

$b\leq a_{0}+\alpha<a+1+\alpha$

and we conclude that $b-a<1+\alpha$. Analogously, we obtain $d-c<1+\alpha$.
Together, this implies $\mu(\Delta)<(1+\alpha)^{2}$. Finally, (10) yields

$(1+\alpha)^{2}=1+2\alpha+\alpha^{2}=2+\alpha,$

as desired.

For the remainder of the proof, we assume that $d-c<1$ and remark that the
proof for the case $b-a<1$ is analogous, using the rotational symmetry
$\Gamma=\begin{pmatrix}0&-1\\\ 1&0\end{pmatrix}\Gamma$. Furthermore, since
$\Gamma\subset\mathbb{R}^{2}$ is a lattice, it is in particular a subgroup of
$\mathbb{R}^{2}$: The problem is invariant under shifts $\Delta-\gamma$ of
$\Delta$ by lattice points $\gamma\in\Gamma$. Hence, we can assume, without
loss of generality, that $\begin{pmatrix}a_{0}\\\
d\end{pmatrix}=\begin{pmatrix}0\\\ 0\end{pmatrix}$, implying $a\leq 0$, $b>0$
and $c<0$. Further, let $n\in\mathbb{N}$ be such that

$\alpha^{n}\leq-c<\alpha^{n-1}.$

In particular, this implies

$c\leq-\alpha^{n}<-\alpha^{n+1}<0.$ (11)

If $n\in 2\mathbb{N}$ then, by (8) in Proposition IV.1, the chain of
inequalities in (11) is equivalent to

$c\leq f_{n}\alpha-f_{n-1}<f_{n}-f_{n+1}\alpha<0.$ (12)

For $p_{0}=\begin{pmatrix}f_{n}\\\ -f_{n-1}\end{pmatrix}$ and
$p_{1}=\begin{pmatrix}-f_{n+1}\\\ f_{n}\end{pmatrix}$, we have

$Ap_{0}=\begin{pmatrix}f_{n}+\alpha f_{n-1}\\\ f_{n}\alpha-
f_{n-1}\end{pmatrix}\quad\text{and}\quad Ap_{1}=\begin{pmatrix}-f_{n+1}-\alpha
f_{n}\\\ -f_{n+1}\alpha+f_{n}\end{pmatrix}.$

In particular, (12) yields $Ap_{0}\in((0,\infty)\times[c,0))\,\cap\,\Gamma$
and $Ap_{1}\in((-\infty,0)\times[c,0))\,\cap\,\Gamma$. Thus,
$\Delta\cap\Gamma=\emptyset$ implies $b\leq(Ap_{0})_{1}$ and $a>(Ap_{1})_{1}$.
Together, we obtain

$\displaystyle b-a$ $\displaystyle<(Ap_{0})_{1}-(Ap_{1})_{1}$
$\displaystyle=f_{n}+\alpha f_{n-1}-(-f_{n+1}-\alpha f_{n})$
$\displaystyle=f_{n+2}+\alpha f_{n+1}.$

Similarly, if $n\in 2\mathbb{N}-1$, we set $p_{0}=\begin{pmatrix}-f_{n}\\\
f_{n-1}\end{pmatrix}$ and $p_{1}=\begin{pmatrix}f_{n+1}\\\
{-f_{n}}\end{pmatrix}$ and we arrive at the same bound for $b-a$.

Since $d-c=-c<\alpha^{n-1}$, we obtain

$\mu(\Delta)<\alpha^{n-1}f_{n+2}+\alpha^{n}f_{n+1}=2+\alpha,$

by (9) in Proposition IV.1. This completes the proof. ∎

Furthermore, any axis-parallel rectangle that has sufficiently small area
contains no more than a single element of $\Gamma$.

######  Lemma IV.3.

Let $\Delta=[a,b)\times[c,d)$ be an axis parallel half-open rectangle of size
$\mu(\Delta)\leq 1/(3+2\alpha)$. Then $\lvert\Delta\cap\Gamma\rvert\leq 1$.

###### Proof.

Given $\Delta=[a,b)\times[c,d)$, with $\Delta\cap\Gamma\neq\emptyset$, we
assume, without loss of generality, that there exist $a_{0}\in[a,b)$ and
$c_{0}\in[c,d)$, such that

$\binom{a}{c_{0}},\,\binom{a_{0}}{c}\in\Gamma.$

Otherwise, there is a nonzero $\begin{pmatrix}b_{0}\\\
d_{0}\end{pmatrix}\in[0,\infty)^{2}$, such that
$[a+b_{0},b)\times[c+d_{0},d)\cap\Gamma\neq\emptyset$. We now show that
$\lvert\Delta\cap\Gamma\rvert\geq 2$ implies $\mu(\Delta)>1/(3+2\alpha)$.

Analogous to the previous proof, we only consider the case $d-c<1$ and assume
that $\begin{pmatrix}a_{0}\\\ c\end{pmatrix}=\begin{pmatrix}0\\\
0\end{pmatrix}$, implying $a\leq 0$, $b>0$ and $d>0$. Since $\alpha$ is a so-
called badly approximable number, we can bound how well it can be approximated
by any rational. Specifically, by [24, Sec. 11.7], we have

$\bigg{\lvert}\alpha+\frac{m}{n}\bigg{\rvert}\geq\frac{1}{(3+2\alpha)n^{2}}$
(13)

for any $n,m\in\mathbb{Z}$, $n\neq 0$. In turn, we have $\lvert
n\alpha+m\rvert\geq\frac{1}{(3+2\alpha)|n|}$. Hence, any lattice point in
$\Gamma$ with second component in $[0,d)$ must satisfy
$\frac{1}{(3+2\alpha)|n|}<d$, i.e.,

$|n|>\frac{1}{(3+2\alpha)d}.$ (14)

On the other hand, $\lvert n\alpha+m\rvert<d<1$, implies that the cases $n>0$
and $m>0$ as well as $n<0$ and $m<0$ can be excluded, which implies $nm\leq
0$. Thus, for the first component of any point in $\Delta\cap\Gamma$, we have
$\lvert n-m\alpha\rvert=\lvert n\rvert+\lvert m\alpha\rvert$. Furthermore,
$a\leq n-m\alpha<b$ and, hence,

$\lvert n\rvert\leq\lvert n\rvert+\lvert m\alpha\rvert<b-a.$ (15)

Combining (14) and (15), we obtain $\frac{1}{(3+2\alpha)}<(b-a)d=\mu(\Delta)$.
∎

######  Corollary IV.4.

Let $\Delta=[a,b)\times[c,d)$ be an axis parallel half-open rectangle of size
$\mu(\Delta)=2+\alpha=\varphi^{2}$. Then
$1\leq\lvert\Delta\cap\Gamma\rvert\leq 12$.

In particular, for any $\delta>0$, there is a $\beta:=\beta(\delta)>0$, such
that the following holds: If
$\mathcal{V}^{\delta}=(V^{\delta}_{k,\ell})_{k,\ell\in\mathbb{Z}}$ is as in
Theorem III.1, then

$1\leq\lvert\beta\Gamma\cap V^{\delta}_{k,\ell}\rvert\leq 12,$

for all $k,\ell\in\mathbb{Z}$. Hence, if $\delta\leq\delta(\Psi)$, we can
choose $\Lambda_{D}=\beta\Gamma$ in Theorem III.1.

###### Proof.

The lower bound in the first assertion follows from Lemma IV.2. For the upper
bound note that $2+\alpha<\tfrac{12}{2\alpha+3}$, such that an axis-parallel,
half-open rectangle of area $2+\alpha$ can be contained in no more than $12$
axis-parallel, half-open rectangles of area $(2\alpha+3)^{-1}$. The bound now
follows from Lemma IV.3.

For the second assertion, it is sufficient to note that each
$V^{\delta}_{k,l}$ is an axis-parallel, half-open rectangle of area
$\mu(V^{\delta}_{k,l})=\delta^{2}$. Choose
$\beta(\delta)=\delta^{2}\cdot(2+\alpha)^{-1}$ to obtain the desired result. ∎

Considering the coarse estimates used in both previous proofs, it seems quite
likely that the upper bound in Corollary IV.4 can be further improved.

##  V Conclusion and Outlook

We have shown that a certain scale of rotated lattices provides sets of stable
sampling for continuous wavelet systems, when restricted to the upper half
plane. Our proof relies on prior work on discretization of wavelet systems in
the context of coorbit spaces, and a property of the proposed lattices that
evokes discrepancy theory. It should be noted that our result generalizes to
other warped time frequency systems or, more generally, localized continuous
frames that satisfy oscillation estimates with respect to a phase-space
covering comprised of axis-parallel rectangles with identical area. A
generalization to higher dimensional phase space seems quite feasible.

We expect analogues of Lemmas IV.2 and IV.3 for any badly approximable number
in place of $\alpha$. Specifically, some bound in the style of Lemma IV.3
exists for any badly approximable number, but [24, Sec. 11.7] only yields
explicit estimates for algebraic numbers. We are currently working on a proof
for Lemma IV.2 that does not rely on the properties of the golden ratio
$\varphi$ and generalizes to arbitrary badly approximable numbers. With this
extended result, it will be possible to show that a more general class of
time-frequency lattices generates sets of stable sampling for wavelet systems
and other localized continuous frames.

## Acknowledgments

We would like to thank Friedrich Pillichshammer for continued, inspiring
discussions on the use and construction of low discrepancy sequences. G. K.
gratefully acknowledges support by the Austrian Science Fund (FWF) project Y
1199.

###### Proof of Theorem III.1.

First note that [23, Example 4.1] shows that $\Psi$ is a warped time-frequency
system with respect to the warping function $\Phi=\log$ (the natural
logarithm) and the prototype $\theta=\mathcal{F}(\psi)\circ\exp$, where
$\circ$ denotes composition. In particular, it is a warping function in the
sense of [23, Definition 4.2], with associated weight function
$w=(\Phi^{-1})^{\prime}=\exp$. Clearly, $w\in\mathcal{C}^{\infty}(\mathbb{R})$
satisfies $w(t+s)=w(t)w(s)$, for all $t,s\in\mathbb{R}$, such that it is self-
moderate. Finally, the $k$-th derivative $w^{(k)}$ of $w$ equals $w$, such
that $|w^{(k)}/w|=1$, and $\Phi=\log$ satisfies all assumptions on $\Phi$ in
[23, Corollary 6.9]. The covering $\mathcal{V}^{\delta}$ in the statement of
Theorem III.1 is precisely the $\Phi$-induced $\delta$-cover, for $\Phi=\log$,
considered in [23, Corollary 6.9]. Further, Equation (16) in [23] is satisfied
with $Y=\mathbf{L}^{2}(\Lambda)$ and $m\equiv 1$, as stated in [19, Section
3]. It only remains to verify the conditions on
$\theta=\mathcal{F}(\psi)\circ\exp$, before [23, Corollary 6.9] can be
applied.

With this choice of $m$, and estimating $w(t)=\exp(t)\leq\exp(|t|)$, the
conditions on $\theta$ in [23, Corollary 6.9] simplify to

  1. 1.

$\theta\in\mathcal{C}^{2}(\mathbb{R})$ with
$\theta^{(k)}\cdot\exp(|\bullet|)^{3}\in\mathcal{C}_{0}(\mathbb{R})$, for
$0\leq k\leq 2$,

  2. 2.

$\theta^{(k)}\cdot\exp(|\bullet|)^{\frac{7-2k}{2}}\in\mathbf{L}^{2}(\mathbb{R})$.

Since $\exp(|\log(\tau)|)=\max\\{\tau,\tau^{-1}\\}$, for all
$\tau\in\mathbb{R}^{+}$, the first condition is equivalent to

$\theta^{(k)}(\log(\bullet))\cdot\max\\{\bullet^{3},\bullet^{-3}\\}\in\mathcal{C}_{0}(\mathbb{R}^{+}).$

Furthermore,

$\theta^{(1)}\circ\log(\tau)=\tau\cdot(\theta\circ\log)^{(1)}(\tau)=\tau\cdot(\mathcal{F}(\psi))^{(1)}(\tau)$
(16) $\text{and }\
\theta^{(2)}\circ\log(\tau)=\tau\cdot(\mathcal{F}(\psi))^{(2)}(\tau)-(\mathcal{F}(\psi))^{(1)}(\tau),$
(17)

for all $\tau\in\mathbb{R}^{+}$. We conclude that Item (1) is equivalent to
$\max\\{\bullet^{4},\bullet^{-4}\\}\cdot(\mathcal{F}(\psi))^{(k)}\in\mathcal{C}_{0}(\mathbb{R})$,
for all $0\leq k\leq 2$.

Further, for all $l\in\mathbb{N}$ and measurable
$g\colon\mathbb{R}\rightarrow\mathbb{C}$,

$\begin{split}\@ADDCLASS{ltx_eqn_lefteqn}$\displaystyle\int_{\mathbb{R}}|g(t)\cdot\exp(|t|)^{l}|^{2}\leavevmode\nobreak\
dt$\mbox{}\hfil\\\
&=\int_{\mathbb{R}^{+}}\tau^{-1}|\max\\{\tau^{l},\tau^{-l}\\}\cdot(g\circ\log)(\tau)|^{2}\leavevmode\nobreak\
d\tau.\end{split}$

Inserting $g=\theta^{(k)}$ and $l=\tfrac{7-2k}{2}$, for $0\leq k\leq 2$, and
using Equations (16) and (17) once more, we see that Item (2) is implied by
$\max\\{(\bullet)^{5},(\bullet)^{-5}\\}\cdot\mathcal{F}(\psi)\in\mathbf{L}^{2}(\mathbb{R}^{+})$.
Altogether, $\theta=\mathcal{F}(\psi)$ satisfies the conditions of [23,
Corollary 6.9], as desired, such that we can invoke said corollary.

Note that [23, Corollary 6.9] requires a pairwise association of the points
$\lambda_{k,l}\in\Gamma$ and the elements $V^{\delta}_{k,l}$ of
$\mathcal{V}^{\delta}$, for all $k,l\in\mathbb{Z}$, but the choice of point in
$V^{\delta}_{k,l}$ is arbitrary. The covering $\mathcal{V}^{\delta}$ is, in
fact, a tiling of $\Lambda$, such that $\lambda\in V^{\delta}_{k,l}$ implies
$\lambda\notin V^{\delta}_{k^{\prime},l^{\prime}}$, for any
$k,k^{\prime},l,l^{\prime}\in\mathbb{Z}$ with $\begin{pmatrix}k\\\
l\end{pmatrix}\neq\begin{pmatrix}k^{\prime}\\\ l^{\prime}\end{pmatrix}$.
Hence, we can find $\Gamma_{0}\subset\Gamma$, such that $|\Gamma_{0}\cap
V^{\delta}_{k,l}|=1$, for all $k,l\in\mathbb{Z}$, and $\Gamma_{0}$ is a set of
stable sampling for $\Psi$ by [23, Corollary 6.9].

We can further find $\Gamma_{1},\ldots,\Gamma_{N-1}\subset\Gamma$ that satisfy
the following:

  1. 1’)

$\bigcup_{n=0}^{N-1}\Gamma_{n}=\Gamma$, and
$\Gamma_{n}\cap\Gamma_{n^{\prime}}=\emptyset$, for all
$n,n^{\prime}\in\\{0,\ldots,N-1\\}$ with $n\neq n^{\prime}$.

  2. 2’)

$|\Gamma_{n}\cap V^{\delta}_{k,l}|\leq 1$, for all $n\in\\{0,\ldots,N-1\\}$
and all $k,l\in\mathbb{Z}$.

Since the points $(\lambda_{k,l})_{k,l\in\mathbb{Z}}$ with $\lambda_{k,l}\in
V^{\delta}_{k,l}$, for all $k,l\in\mathbb{Z}$ in [23, Corollary 6.9] are
arbitrary, it is clear that each $\Gamma_{n}$ satisfies the implicit upper
frame bound in that result. Hence, we conclude that $\Gamma$ is a set of
stable sampling for $\Psi$. Precisely, the lower bound in (4) equals the lower
bound implied in [23, Corollary 6.9], whereas the upper bound in (4) is no
larger than $N$ times the upper bound implied in [23, Corollary 6.9]. ∎

## References

  * [1] I. Daubechies, _Ten lectures on wavelets._ SIAM, 1992.
  * [2] N. Holighaus, G. Koliander, Z. Průša, and L. D. Abreu, “Characterization of Analytic Wavelet Transforms and a New Phaseless Reconstruction Algorithm,” _IEEE Transactions on Signal Processing_ , vol. 67, no. 15, pp. 3894–3908, 2019.
  * [3] J. M. Lilly and S. C. Olhede, “On the analytic wavelet transform,” _IEEE Transactions on Information Theory_ , vol. 56, no. 8, pp. 4135–4156, 2010.
  * [4] I. Daubechies, A. Grossmann, and Y. Meyer, “Painless nonorthogonal expansions,” _Journal of Mathematical Physics_ , vol. 27, no. 5, pp. 1271–1283, 1986.
  * [5] S. G. Mallat, “Multiresolution approximations and wavelet orthonormal bases of $\mathbf{L}^{2}(\mathbb{R})$,” _Transactions of the American Mathematical Society_ , vol. 315, no. 1, pp. 69–87, 1989.
  * [6] Y. Meyer, _Wavelets and Operators_ , ser. Cambridge Studies in Advanced Mathematics, D. H. Salinger, Ed. Cambridge University Press, 1993, vol. 1.
  * [7] A. Ron and Z. Shen, “Affine systems inl2(rd): The analysis of the analysis operator,” _Journal of Functional Analysis_ , vol. 148, no. 2, pp. 408–447, 1997.
  * [8] J. Dick and F. Pillichshammer, _Digital Nets and Sequences: Discrepancy Theory and Quasi–Monte Carlo Integration_. Cambridge University Press, 2010.
  * [9] R. Levie, H. Avron, and G. Kutyniok, “Quasi Monte Carlo time-frequency analysis,” _Journal of Mathematical Analysis and Applications_ , vol. 518, no. 2, p. 126732, 2023.
  * [10] N. Holighaus, G. Koliander, C. Hollomey, and F. Pillichshammer, “Grid-Based Decimation for Wavelet Transforms With Stably Invertible Implementation,” _IEEE/ACM Transactions on Audio, Speech, and Language Processing_ , vol. 31, pp. 789–801, 2023.
  * [11] L. Kuipers and H. Niederreiter, _Uniform Distribution of Sequences_. John Wiley, 1974.
  * [12] M. Drmota and R. F. Tichy, _Sequences, Discrepancies and Applications_. Springer Berlin Heidelberg, 1997.
  * [13] F. J. Hickernell, _Lattice Rules: How Well Do They Measure Up?_ New York, NY: Springer New York, 1998, pp. 109–166.
  * [14] S. T. Ali, J. P. Antoine, and J. P. Gazeau, “Continuous frames in Hilbert space,” _Annals of Physics_ , vol. 222, no. 1, pp. 1–37, February 1993.
  * [15] O. Christensen, _An Introduction to Frames and Riesz Bases_ , ser. Applied and Numerical Harmonic Analysis. Cham: Springer International Publishing, 2016.
  * [16] H. G. Feichtinger and K. Gröchenig, “A unified approach to atomic decompositions via integrable group representations,” in _Function Spaces and Applications_ , M. Cwikel, J. Peetre, Y. Sagher, and H. Wallin, Eds. Springer Berlin Heidelberg, 1988, pp. 52–73.
  * [17] ——, “Banach spaces related to integrable group representations and their atomic decompositions, I,” _J. Func. Ana._ , vol. 86, no. 2, pp. 307–340, 1989.
  * [18] ——, “Banach spaces related to integrable group representations and their atomic decompositions. part ii,” _Monatshefte für Mathematik_ , vol. 108, pp. 129–148, 1989.
  * [19] M. Fornasier and H. Rauhut, “Continuous frames, function spaces, and the discretization problem,” _J. Fourier Anal. Appl._ , vol. 11, no. 3, pp. 245–287, 2005.
  * [20] H. Rauhut and T. Ullrich, “Generalized coorbit space theory and inhomogeneous function spaces of Besov-Lizorkin-Triebel type,” _J. Funct. Anal._ , vol. 260, no. 11, pp. 3299–3362, 2011.
  * [21] H. Kempka, M. Schäfer, and T. Ullrich, “General coorbit space theory for quasi-Banach spaces and inhomogeneous function spaces with variable smoothness and integrability,” _J. Fourier Anal. Appl._ , vol. 23, no. 6, pp. 1348–1407, 2017.
  * [22] N. Holighaus and F. Voigtlaender, “Schur-type Banach modules of integral kernels acting on mixed-norm Lebesgue spaces,” _Journal of Functional Analysis_ , vol. 281, no. 9, p. 109197, 2021.
  * [23] N. Holighaus, C. Wiesmeyr, and P. Balazs, “Continuous warped time-frequency representations—coorbit spaces and discretization,” _Applied and Computational Harmonic Analysis_ , vol. 47, no. 3, pp. 975–1013, 2018.
  * [24] G. H. Hardy and E. M. Wright, _An Introduction to the Theory of Numbers_. Oxford university press, 1979\.


# Perfect matching and distance spectral radius in graphs and bipartite graphs

Yuke Zhang and Huiqiu Lin111Supported by the National Natural Science
Foundation of China (Nos. 11771141 and 12011530064). E-mail<EMAIL_ADDRESS>(H.Q. Lin<EMAIL_ADDRESS>(Y.K. Zhang)
Department of Mathematics, East China University of Science and Technology,
Shanghai 200237, P.R. China

###### Abstract

A perfect matching in a graph $G$ is a set of nonadjacent edges covering every
vertex of $G$. Motivated by recent progress on the relations between the
eigenvalues and the matching number of a graph, in this paper, we aim to
present a distance spectral radius condition to guarantee the existence of a
perfect matching. Let $G$ be an $n$-vertex connected graph where $n$ is even
and $\lambda_{1}(D(G))$ be the distance spectral radius of $G$. Then the
following statements are true.

$\rm{I)}$ If $4\leq n\leq 10$ and
${\lambda}_{1}(D\left(G\right))\leq{\lambda}_{1}(D(S_{n,{\frac{n}{2}}-1}))$,
then $G$ contains a perfect matching unless $G\cong S_{n,{\frac{n}{2}-1}}$
where $S_{n,{\frac{n}{2}-1}}\cong
K_{{\frac{n}{2}-1}}\vee({\frac{n}{2}+1})K_{1}$.

$\rm{II)}$ If $n\geq 12$ and
${\lambda}_{1}(D\left(G\right))\leq{\lambda}_{1}(D(G^{*}))$, then $G$ contains
a perfect matching unless $G\cong G^{*}$ where $G^{*}\cong
K_{1}\vee(K_{n-3}\cup 2K_{1})$.

Moreover, if $G$ is a connected $2n$-vertex balanced bipartite graph with
$\lambda_{1}(D(G))\leq\lambda_{1}(D(B_{n-1,n-2}))$, then $G$ contains a
perfect matching, unless $G\cong B_{n-1,n-2}$ where $B_{n-1,n-2}$ is obtained
from $K_{n,n-2}$ by attaching two pendent vertices to a vertex in the
$n$-vertex part.

Keywords: Distance spectral radius; Perfect matching;

2000 Mathematics Subject Classification: 05C50

##  1 Introduction

All graphs considered in this paper are undirected, connected and simple. Let
$G$ be a graph with vertex set $V(G)=\\{v_{1},v_{2},\ldots,v_{n}\\}$ and edge
set $E(G)$. The _distance_ between $v_{i}$ and $v_{j}$, denoted by
$d_{G}(v_{i},\,v_{j})$ (or $d_{ij}$), is the length of a shortest path from
$v_{i}$ to $v_{j}$. The _distance matrix_ of $G$, denoted by $D(G)$, is the
$n\times n$ real symmetric matrix whose $(i,\,j)$-entry is
$d_{G}(v_{i},\,v_{j})$ $(\mbox{or }d_{ij})$, then we can order the eigenvalues
of $D(G)$ as

$\lambda_{1}(D(G))\geq\lambda_{2}(D(G))\geq\cdots\geq\lambda_{n}(D(G)).$

By the Perron-Frobenius theorem, $\lambda_{1}(D(G))$ is always positive
(unless $G$ is trivial) and $\lambda_{1}(D(G))\geq|\lambda_{i}(D(G))|$ for
$i=2,3,\ldots,n$, and we call $\lambda_{1}(D(G))$ the _distance spectral
radius_.

The study of distance eigenvalues can be traced back to 1971 by Graham and
Pollack [6] and they described a relationship between the number of negative
distance eigenvalues and the addressing problem in data communication system.
In the same paper, they showed a very interesting and insightful result that
the determinant of the distance matrix of a tree with order $n$ is
$(-1)^{n-1}(n-1)2^{n-2}$, which is independent of the structure of the tree.
Since then, the study of distance eigenvalues of a graph has become a research
subject of enormous interest and this topic has received growing attention
over recent years, some latest results see [1, 10, 11, 13, 17]. For more
results on the distance matrix and its spectral properties, we refer the
reader to the excellent survey [2].

A _matching_ $M$ of a graph $G$ is a set of pairwise nonadjacent edges. The
maximum number of edges of a matching in $G$ is called _matching number_ of
$G$, denoted by $\alpha(G)$. A vertex incident with an edge in $M$ is called
to be _saturated_ by $M$. A _perfect matching_ is one matching which all
vertices of $G$ are saturated by it. Obviously, a graph with a perfect
matching has an even number of vertices and $\alpha(G)=\frac{|V(G)|}{2}$.

The studies of the connections between eigenvalues and the matching number of
a graph were mainly based on the tree in 1990s. Chang [4] obtained an upper
bound and a tight lower bound for the second largest eigenvalue of an
$n$-vertex tree with a given matching number. Later, Hou and Li [8] gave some
upper bounds for the spectral radius of a tree in terms of its order and
matching number. Brouwer and Heamers [3] investigated this problem to the
general graph and showed that if $\mu_{1}(G)\leq 2\mu_{n-1}(G)$, then $G$
contains a perfect matching where $\mu_{1}(G)$ and $\mu_{n-1}(G)$ are the
largest and second smallest Laplacian eigenvalues of $G$, respectively. Feng,
Yu and Zhang [5] investigated the maximal spectral radius of graphs with a
given matching number and order. In the past decade, some quality and
interesting results on the matching number of a graph and its distance
spectral radius have been obtained. Ilić [9] characterized $n$-vertex trees
with a given matching number which minimize the distance spectral radius. Liu
[12] characterized graphs with minimum distance spectral radius in connected
graphs on $n$ vertices with fixed matching number. Zhang [19] and Lu and Luo
[14] characterized unicyclic graphs with a perfect matching and a given
matching number which minimize the distance spectral radius, respectively.

Very recently, O [15] proved a lower bound for the spectral radius in an
$n$-vertex graph to guarantee the existence of a perfect matching. Along this
line, we consider this problem with respect to the distance spectral radius in
this paper.

We denote by $G\cup H$ the _disjoint union_ of two graphs $G$ and $H$, which
is the graph with $V(G\cup H)=V(G)\cup V(H)$ and $E(G\cup H)=E(G)\cup E(H)$,
particularly if $G\cong H$, then write $2G=G\cup H$ for short. Denote by
$G\vee H$ the _join_ of two graphs $G$ and $H$, which is the graph such that
$V(G\vee H)=V(G)\cup V(H)$ and $E(G\vee H)=E(G)\cup E(G)\cup\\{vu:u\in V(G)\
\mbox{and}\ v\in V(H)\\}.$ The graph $S_{n,k}$ is obtained from a copy of
$K_{k}$ by adding $n-k$ vertices, each of which has neighborhood $V(K_{k})$
i.e. $S_{n,k}\cong K_{k}\vee(n-k)K_{1}$. In the following, we first give a
distance spectral radius condition which guarantees a graph to have a perfect
matching.

$K_{n-3}$$G^{*}$ Figure 1: The extremal graph $G^{*}$ of Theorem 1.1.

######  Theorem 1.1.

Let $G$ be a connected graph with order $n$ and $n\geq 4$ be an even integer.

  1. (i)

For $n\leq 10$, if
${\lambda}_{1}(D\left(G\right))\leq{\lambda}_{1}(D(S_{n,{\frac{n}{2}}-1}))$,
then $G$ contains a perfect matching unless $G\cong S_{n,{\frac{n}{2}-1}}$.

  2. (ii)

For $n\geq 12$, if
${\lambda}_{1}(D\left(G\right))\leq{\lambda}_{1}(D(G^{*}))$, then $G$ contains
a perfect matching unless $G\cong G^{*}$ where $G^{*}\cong
K_{1}\vee(K_{n-3}\cup 2K_{1})$ (see Fig. 1).

A connected bipartite graph with two parts of size $n_{1}$ and $n_{2}$. We say
that it is balanced if $n_{1}=n_{2}$. Note that if a connected bipartite graph
is not balanced. Then it has no perfect matching. Let $B_{n-1,n-2}$ be the
graph obtained from $K_{n,n-2}$ by attaching two pendent vertices to a vertex
in $n$-vertex part (see Fig. 2). Then we have the following result.

$(n-1)$vertices$(n-2)$vertices$B_{n-1,n-2}$ Figure 2: The extremal graph
$B_{n-1,n-2}$ of Theorem 1.2.

######  Theorem 1.2.

Let $G$ be a connected balanced bipartite graph with order $2n$ where $n$ is
an integer and $n\geq 3$. If
$\lambda_{1}(D(G))\leq\lambda_{1}(D(B_{n-1,n-2}))$, then $G$ has a perfect
matching unless $G\cong B_{n-1,n-2}$ (see Fig. 2).

##  2 Proofs

For $S\subseteq V(G)$, the subgraph induced by $V(G)-S$ is denoted by $G-S$. A
component is called an odd (even) component if the number of vertices in this
component is odd (even) and let $o(G)$ denote the number of odd components of
$G$.

$G_{1}$$G_{2}$$G_{q}$$R_{1}$$R_{2}$$R_{k}$$S$$G$oddcomponentsevencomponents
Figure 3: The graph in Tutte’s theorem.

######  Lemma 2.1 (Tutte’s theorem [16]).

A graph $G$ has a perfect matching (see Fig.3) if and only if

$o(G-S)\leq|S|$ for each $S\subseteq V(G)$.

Let $W(G)=\sum_{i<j}d_{ij}$ be the _Wiener index_ of a connected graph $G$
with order $n$. Note that
$\lambda_{1}(D(G))=\max\limits_{\textbf{x}\in{\mathbb{R}}^{n}}\frac{\textbf{x}^{t}D(G)\textbf{x}}{\textbf{x}^{t}\textbf{x}}$.
Then we have

$\lambda_{1}(D(G))=\max\limits_{\textbf{x}\in{\mathbb{R}}^{n}}\frac{\textbf{x}^{t}D(G)\textbf{x}}{\textbf{x}^{t}\textbf{x}}\geq\frac{\mathbf{1}^{t}D\mathbf{1}}{\mathbf{1}^{t}\mathbf{1}}\geq\frac{2W(G)}{n},$

where $\mathbf{1}=(1,1,\ldots,1)^{t}$. Now we give the proof of Theorem 1.1.

Proof of Theorem 1.1.

By way of contradiction assume that $G$ has no perfect matching with the
minimum distance spectral radius. By Lemma 2.1, there exists $S\subset V(G)$
such that $q-|S|>0$, where $o(G-S)=q$ and all components of $G-S$ are odd,
otherwise, we can remove one vertex from each even component to the set $S$,
in consequence, the number of odd component and the number of vertices in $S$
have the same increase, so that $q$ is always larger than $|S|$ and all
components of $G-S$ are odd. Note that $G$ is connected, which implies that
$S$ is not empty. $|S|$ and $q$ have the same parity because $n$ is even, so
$q-|S|\geq 2$. Let $G^{\prime}$ be the graph obtained from $G$ by joining $S$
and $G-S$ and by adding edges in $S$ and in all components of $G-S$ so that
all components of $G-S$ and $G[S]$ are cliques. It’s clear that
${G}^{\prime}\cong{K}_{s}\vee\left({K}_{n_{1}}\cup
K_{n_{2}}\cup\cdots\cup{K}_{n_{q}}\right)$ where $|S|=s$,
${n}_{1}\geq{n}_{2}\geq\dots\geq{n}_{q}\geq 1$ and
${n}_{1}+{n}_{2}+\dots+{n}_{q}=n-s$. Note that $G^{\prime}\cong G$, otherwise,
referring to the Perron-Frobenius theorem, we have
${\lambda}_{1}\left(D\left(G^{\prime}\right)\right)<{\lambda}_{1}\left(D\left(G\right)\right)$,
a contradiction. Suppose ${n}_{2}={n}_{3}=\dots={n}_{q}=1$, then we get a
graph
${G}^{\prime\prime}\cong{K}_{s}\vee\left({K}_{n-s-\left(q-1\right)}\cup(q-1)K_{1}\right)$.

######  Claim 1.

${\lambda}_{1}\left(D\left(G^{\prime}\right)\right)\geq{\lambda}_{1}\left(D\left(G^{\prime\prime}\right)\right)$
with equality if and only if $G^{\prime}\cong G^{\prime\prime}$.

If $n_{1}=1$, then $n_{1}={n}_{2}={n}_{3}=\dots={n}_{q}=1$ and
$G^{\prime}\cong G^{\prime\prime}$. Now we consider $n_{1}\geq 3$. Denote the
vertex set of $G^{\prime\prime}$ by $V(G^{\prime\prime})=V(K_{s})\cup
V(K_{n-s-(q-1)})\cup V((q-1)K_{1})$. Suppose that $X$ is the Perron vector of
$D(G^{\prime\prime})$, and let $x(v)$ denote the entry of $X$ corresponding to
the vertex $v\in V(G^{\prime\prime})$. By symmetry, it is easy to see that all
vertices of $V(K_{s})$ (resp. $V(K_{n-s-(q-1)})$ and $V((q-1)K_{1})$) have the
same entries in $X$. Thus we can suppose $x(u)=a$ for any $u\in
V((q-1)K_{1})$, $x(v)=b$ for any $v\in V(K_{n-s-(q-1)})$ and $x(w)=c$ for any
$w\in V(K_{s})$. Then

$\left\\{\begin{array}[]{l}\lambda_{1}(D(G^{\prime\prime}))a=sc+2\left(n-s-q+1\right)b+2\left(q-2\right)a,\\\\[8.53581pt]
\lambda_{1}(D(G^{\prime\prime}))b=sc+\left(n-s-q\right)b+2\left(q-1\right)a,\\\\[8.53581pt]
\lambda_{1}(D(G^{\prime\prime}))c=(s-1)c+\left(n-s-q+1\right)b+\left(q-1\right)a.\end{array}\right.$

Thus,

$a=\left[1+\frac{n-s-q}{\lambda_{1}(D(G^{\prime\prime}))+2}\right]b.$

It follows that

$\displaystyle{\lambda}_{1}\left(D\left(G^{\prime}\right)\right)-{\lambda}_{1}\left(D\left(G^{\prime\prime}\right)\right)~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}$
$\displaystyle\geq$
$\displaystyle{X}^{t}\left(D\left({G}^{\prime}\right)-D\left({G}^{\prime\prime}\right)\right)X$
$\displaystyle=$ $\displaystyle
n_{1}\sum_{k=2}^{q}\left({n}_{k}-1\right){b}^{2}+\left({n}_{2}-1\right)\left[\left(n-s-{n}_{2}-\left(q-2\right)\right){b}^{2}-2ab\right]$
$\displaystyle+$
$\displaystyle\left({n}_{3}-1\right)\left[\left(n-s-{n}_{3}-\left(q-2\right)\right){b}^{2}-2ab\right]+\left({n}_{4}-1\right)\left[\left(n-s-{n}_{4}-\left(q-2\right)\right){b}^{2}-2ab\right]$
$\displaystyle+$
$\displaystyle\cdots+\left({n}_{q}-1\right)\left[\left(n-s-{n}_{q}-\left(q-2\right)\right){b}^{2}-2ab\right].$

Since $n_{1}\geq 3$ and $n_{2}\geq n_{3}\geq\cdots\geq n_{q}\geq 1$, in order
to show
${\lambda}_{1}\left(D\left(G^{\prime}\right)\right)-{\lambda}_{1}\left(D\left(G^{\prime\prime}\right)\right)>0$,
we only need to prove
$\left(n-s-{n}_{2}-\left(q-2\right)\right){b}^{2}-2ab>0$.

Note that $K_{n-q+1}$ is a subgraph of $G^{\prime\prime}$. Then
${\lambda}_{1}\left(D\left(G^{\prime\prime}\right)\right)>{\lambda}_{1}\left(D\left(K_{n-q+1}\right)\right)=n-q,$
which implies

$\displaystyle\left(n-s-{n}_{2}-\left(q-2\right)\right){b}^{2}-2ab~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}$
$\displaystyle=$ $\displaystyle b^{2}\left(n-s-
n_{2}-q-\frac{2n-2s-2q}{\lambda_{1}(D(G^{\prime\prime}))+2}\right)$
$\displaystyle>$ $\displaystyle b^{2}\left(n-s-
n_{2}-q-\frac{2n-2s-2q}{n-q+2}\right)$ $\displaystyle=$ $\displaystyle
b^{2}\left(n-s-n_{2}-q-2+\frac{2s+4}{n-q+2}\right)$ $\displaystyle>$
$\displaystyle{b}^{2}\left(n-s-{n}_{2}-q-2\right)$ $\displaystyle=$
$\displaystyle{b}^{2}(n_{1}+n_{2}+\cdots+n_{q-1}+n_{q}-n_{2}-q-2)$
$\displaystyle=$ $\displaystyle{b}^{2}\left(\sum_{i=1,i\neq
2}^{q}\left({n}_{i}-1\right)-1\right)$ $\displaystyle>$ $\displaystyle 0.$

So Claim 1 holds.

So $G\cong G^{\prime\prime}$, or there will be a contradiction. We know that
$q-|S|\geq 2$. Let
$\widetilde{G}\cong{K}_{s}\vee\left({K}_{n-2s-1}\cup\left(s+1\right){K}_{1}\right)$.
We compare the distance spectral radius of $G^{\prime\prime}$ and
$\widetilde{G}$ in the following.

######  Claim 2.

${\lambda}_{1}\left(D\left(G^{\prime\prime}\right)\right)\geq{\lambda}_{1}(D(\widetilde{G}))$
with equality if and only if $G^{\prime\prime}\cong\widetilde{G}$.

Recall
${G}^{\prime\prime}\cong{K}_{s}\vee\left({K}_{n-s-\left(q-1\right)}\cup(q-1)K_{1}\right)$.
If $q=s+2$, then $\widetilde{G}\cong G^{\prime\prime}$. Now we consider $q\geq
s+4$. Denote the vertex set of $\widetilde{G}$ by
$V(\widetilde{G})=V(K_{s})\cup V(K_{n-2s-1})\cup V((s+1)K_{1})$. Suppose that
$Y$ is the Perron vector of $D(\widetilde{G})$, and let $Y(v)$ denote the
entry of $Y$ corresponding to the vertex $v\in V(\widetilde{G})$. By symmetry,
it is easy to see that all vertices of $V(K_{s})$ (resp. $V(K_{n-2s-1})$ and
$V((s+1)K_{1})$) have the same entries in $X$. Thus we can suppose
$Y(u)=y_{1}$ for any $u\in V((s+1)K_{1})$, $Y(v)=y_{2}$ for any $v\in
V(K_{n-2s-1})$ and $Y(w)=y_{3}$ for any $w\in V(K_{s})$. Let
$n_{1}^{\prime}=n-s-(q-1)\geq 1$ and
${G}^{\prime\prime}\cong{K}_{s}\vee\left({K}_{n_{1}^{\prime}}\cup(q-1)K_{1}\right)$.
Then

$\displaystyle{\lambda}_{1}\left(D\left(G^{\prime\prime}\right)\right)-{\lambda}_{1}(D(\widetilde{G}))~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}$
$\displaystyle\geq$
$\displaystyle{Y}^{t}\left(D\left({G^{\prime\prime}}\right)-D(\widetilde{G})\right)Y$
$\displaystyle=$ $\displaystyle
n_{1}^{\prime}(q-s-2)y_{2}^{2}+(n_{1}^{\prime}+q-s-3)(q-s-2)y_{2}^{2}$
$\displaystyle=$ $\displaystyle
y_{2}^{2}\left[{q}^{2}+\left(2{n}_{1}^{\prime}-2s-5\right)q+{s}^{2}+5s-2{n}_{1}^{\prime}s-4{n}_{1}^{\prime}+6\right].$

Since

$\frac{-\left(2{n}_{1}^{\prime}-2s-5\right)}{2}=-{n}_{1}^{\prime}+s+\frac{5}{2}<s+4,$

we obtain

$\displaystyle
y_{2}^{2}\left[{q}^{2}+\left(2{n}_{1}^{\prime}-2s-5\right)q+{s}^{2}+5s-2{n}_{1}^{\prime}s-4{n}_{1}^{\prime}+6\right]~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}$
$\displaystyle\geq$ $\displaystyle
y_{2}^{2}\left[{(s+4)}^{2}+\left(2{n}_{1}^{\prime}-2s-5\right)(s+4)+{s}^{2}+5s-2{n}_{1}^{\prime}s-4{n}_{1}^{\prime}+6\right]$
$\displaystyle=$ $\displaystyle y_{2}^{2}(4{n}_{1}^{\prime}+2)$
$\displaystyle>$ $\displaystyle 0.$

So Claim 2 holds.

So $G\cong\widetilde{G}$, or there will be a contradiction. Let $G^{*}\cong
K_{1}\vee(K_{n-3}\cup 2K_{1})$. In the end, we shall show that $G^{*}$
contains the minimum distance spectral radius and no perfect matching under
the most situations.

######  Claim 3.

If $n\geq 2s+4$, then
${\lambda}_{1}(D(\widetilde{G}))\geq{\lambda}_{1}\left(D\left(G^{*}\right)\right)$
with equality if and only if $\widetilde{G}\cong G^{*}$.

Recall
$\widetilde{G}\cong{K}_{s}\vee\left({K}_{n-2s-1}\cup\left(s+1\right){K}_{1}\right)$.
If $s=1$, then $G^{*}\cong\widetilde{G}$. Now we suppose $s\geq 2$ so that
$n\geq 2s+4\geq 8$. Then the quotient matrix of the partition
$\\{V(K_{n-2s-1},V(K_{s}),V((s+1)K_{1}))\\}$ of $\widetilde{G}$ is

$\left(\begin{array}[]{ccccccc}n-2s-2&s&2(s+1)\\\ &&\\\ n-2s-1&s-1&s+1\\\
&&\\\ 2(n-2s-1)&s&2s\end{array}\right),$

the characteristic polynomial of the matrix is

$\displaystyle
f(x)={x}^{3}-\left(s+n-3\right){x}^{2}-\left(2sn-5{s}^{2}+5n-6s-6\right)x+n{s}^{2}-2{s}^{3}-sn+2{s}^{2}-4n+6s+4.$

We know that ${\lambda}_{1}(D(\widetilde{G}))$ is the largest root of
$f(x)=0$. Since ${\lambda}_{1}\left(D\left(G^{*}\right)\right)=\theta(n)$
(simply $\theta$) is the largest root of the equation
$q(x)={x}^{3}-\left(n-2\right){x}^{2}-\left(7n-17\right)x-4n+10=0$, we have

$\displaystyle h(\theta)$ $\displaystyle=$ $\displaystyle
f\left(\theta\right)-q\left(\theta\right)$ $\displaystyle=$
$\displaystyle-\left(s-1\right){\theta}^{2}-\left(2ns-5{s}^{2}-2n-6s+11\right)\theta+n{s}^{2}-2{s}^{3}-sn+2{s}^{2}+6s-6$
$\displaystyle=$
$\displaystyle(s-1)(-\theta^{2}+(-2n+5s+11)\theta+sn-2s^{2}+6).$

Moreover,
$\theta={\lambda}_{1}\left(D\left(G^{*}\right)\right)\geq\frac{2W(G^{*})}{n}=\frac{n^{2}+3n-10}{n}\geq
n+1$ and $s\geq 2$. To show
${\lambda}_{1}(D(\widetilde{G}))>{\lambda}_{1}\left(D\left(G^{*}\right)\right)$,
we only need to prove
$h_{1}(\theta)=-\theta^{2}+(-2n+5s+11)\theta+sn-2s^{2}+6<0$ when $\theta\geq
n+1$, then $h(\theta)<h_{1}(\theta)<0$. Note that

$\frac{-2n+5s+11}{2}=-n+\frac{5}{2}s+\frac{11}{2}<n+1.$

So when $\theta\geq n+1$, $h_{1}(\theta)$ monotonically decreases as $\theta$
increases and $h_{1}(\theta)\leq h_{1}(n+1)$. Let
$g(n)=h_{1}(n+1)=-3n^{2}+(6s+7)n-2s^{2}+5s+16$ where $n\geq 2s+4$. Then

$\frac{6{s}+7}{6}=s+\frac{7}{6}<2s+4.$

So when $n\geq 2s+4$, $g(n)$ is monotonically decreasing and
$h(\theta)<h_{1}(\theta)\leq g(n)\leq g(2s+4)=-2s^{2}-5s-4<0$. So Claim 3
holds.

If $n=2s+2$, observe that $\widetilde{G}\cong S_{n,{\frac{n}{2}-1}}$ and the
quotient matrix of the partition
$\\{V(K_{\frac{n}{2}-1}),V(({\frac{n}{2}+1})K_{1})\\}$ of
$S_{n,{\frac{n}{2}-1}}$ is

$\left(\begin{array}[]{cccccccc}{\frac{n}{2}-2}&&{\frac{n}{2}+1}\\\ &&\\\
{\frac{n}{2}-1}&&n\end{array}\right).$

By a simple calculation,

$\lambda_{1}(D(S_{n,{\frac{n}{2}-1}}))=\frac{3n-4+\sqrt{n^{2}+24n-16}}{4}.$

######  Claim 4.

If $n=2s+2$ and $n\geq 12$, then
${\lambda}_{1}(D(S_{n,{\frac{n}{2}-1}}))>{\lambda}_{1}\left(D\left(G^{*}\right)\right)$.

Let $n=2s+2$, then $g(n)<0$ when $n\geq 12$. So Claim 4 holds.

######  Claim 5.

If $n=2s+2$ and $n\leq 10$, then
${\lambda}_{1}(D(S_{n,{\frac{n}{2}-1}}))\leq{\lambda}_{1}\left(D\left(G^{*}\right)\right)$
with equality if and only if $G^{*}\cong S_{n,{\frac{n}{2}-1}}$.

If $s=1$ and $n=4$, then $S_{n,{\frac{n}{2}-1}}\cong G^{*}$. If $s=2$ and
$n=6$, then $\lambda_{1}(D(S_{6,2}))=\frac{7+\sqrt{41}}{2}$ and
$q(\frac{7+\sqrt{41}}{2})<0$, so ${\lambda}_{1}(D(S_{6,2}))<\theta(6)$. If
$s=3$ and $n=8$, then $\lambda_{1}(D(S_{8,3}))=5+\sqrt{15}$ and
$q(5+\sqrt{15})<0$, so ${\lambda}_{1}(D(S_{8,3}))<\theta(8)$. If $s=4$ and
$n=10$, then $\lambda_{1}(D(S_{10,4}))=11$ and $q(11)<0$, so
${\lambda}_{1}(D(S_{10,4}))<\theta(10)$. So Claim 5 holds.

In conclusion, $G\cong G^{*}$ if $n\geq 12$ and $G\cong S_{n,{\frac{n}{2}-1}}$
if $4\leq n\leq 10$, otherwise $G$ doesn’t contain the minimum distance
spectral radius, a contradiction. ∎

In some specific applications, one needs to find a matching in a bipartite
graph which can cover one partite. Essential and sufficient conditions for the
existence of such a matching was first proposed by Hall [7]. Let $S$ be a set
of vertices in a graph $G$. The set of all neighbours of the vertices in $S$
is denoted by $N(S)$.

######  Lemma 2.2 (Hall’s theorem [7]).

A bipartite graph $G:=G[X,Y]$ has a matching which covers every vertex in $X$
if and only if

$|N(S)|\geq|S|$ for each $S\subseteq X.$

$S$$N(S)$$X-S$$Y-N(S)$$G[X,Y]$ Figure 4: The graph $B_{|S|,|N(S)|}$ in Theorem
1.2.

For two vertex sets $X$ and $Y$, let $e(X,Y)$ be the set of all edges between
$X$ and $Y$. Now we are in a position to prove Theorem 1.2.

Proof of Theorem 1.2.

Assume to the contrary that $G$ has no perfect matching with the minimum
distance spectral radius. Let $G:=G[X,Y]$ be a connected balanced bipartite
graph, where $|X|=|Y|=n$. By Lemma 1.2, since $G$ has no perfect matching,
there exists $S\subset X$ and $|N(S)|<|S|$. Notice that there exists no edges
between $S$ and $Y-N(S)$, otherwise, we can find a vertex $v\in S$ and
$Y-N(S)$ contains its neighbors, a contradiction. Let $B_{s,p}$ be the
connected balanced bipartite graph obtained from $G$ by joining $S$ and
$N(S)$, $X-S$ and $Y-N(S)$ and by adding all possible edges between $X-S$ and
$N(S)$ where $|S|=s$, $|N(S)|=p$ and $1\leq p<s\leq n-1$, so that
$B_{s,p}\cong K_{s,p}\cup K_{n-s,n-p}+e(N(S),X-S)$, i.e. $B_{s,p}\cong
K_{n,n}-e(S,Y-N(S))$ (see Fig.4). Note that $G\cong B_{s,p}$, otherwise, we
have
${\lambda}_{1}\left(D\left(B_{s,p}\right)\right)<{\lambda}_{1}\left(D\left(G\right)\right)$
by Perron-Frobenius theorem, a contradiction.

######  Claim 1.

$\lambda_{1}(D(B_{s,p}))\geq\lambda_{1}(D(B_{s,s-1}))$ with equality if and
only if $B_{s,p}\cong B_{s,s-1}$.

If $p=s-1$, then $B_{s,p}\cong B_{s,s-1}$. Now we consider $1\leq p\leq s-2$.
Denote the vertex set of $B_{s,s-1}$ by $V(B_{s,s-1})=S\cup(X-S)\cup
N(S)\cup(Y-N(S))$ where $|S|=s$ and $|N(S)|=s-1$. Referring to the Perron-
Frobenius theorem, suppose that a positive vector $Z$ is the Perron vector of
$D(B_{s,s-1})$, and let $Z(v)$ denote the entry of $Z$ corresponding to the
vertex $v\in V(B_{s,s-1})$. By symmetry, it is easy to see that all vertices
of $S$ (resp. $X-S$, $N(S)$ and $Y-N(S)$) have the same entries in $Z$. Thus
we can suppose $Z(u)=z_{1}$ for any $u\in S$, $Z(v)=z_{2}$ for any $v\in X-S$,
$Z(w)=z_{3}$ for any $w\in N(S)$ and $Z(z)=z_{4}$ for any $z\in Y-N(S)$.
Therefore, we have

$\displaystyle{\lambda}_{1}\left(D\left(B_{s,p}\right)\right)-{\lambda}_{1}(D(B_{s,s-1}))~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}$
$\displaystyle\geq$
$\displaystyle{Z}^{t}\left(D\left({B_{s,p}}\right)-D(B_{s,s-1})\right)Z$
$\displaystyle=$ $\displaystyle 4s(s-1-p)z_{1}z_{3}$ $\displaystyle>$
$\displaystyle 0.$

So Claim 1 holds.

Therefore, $G\cong B_{s,s-1}$, or there will be a contradiction.

######  Claim 2.

$\lambda_{1}(D(B_{s,s-1}))\geq\lambda_{1}(D(B_{n-1,n-2}))$ with equality if
and only if $B_{s,s-1}\cong B_{n-1,n-2}$.

If $s=n-1$, then $B_{s,s-1}\cong B_{n-1,n-2}$. Now consider $2\leq s\leq n-2$.
The quotient matrix of the partition $\\{S,X-S,N(S),Y-N(S)\\}$ of $B_{s,s-1}$
where $|S|=s\leq n-2$ and $|N(S)|=s-1$ is

$\left(\begin{array}[]{ccccccccc}2s-2&s-1&2n-2s&3n-3s+3\\\\[8.53581pt]
s&2s-4&n-s&2n-2s+2\\\\[8.53581pt] 2s&s-1&2n-2s-2&n-s+1\\\\[8.53581pt]
3s&2s-2&n-s&2n-2s\\\\[8.53581pt] \end{array}\right),$

the characteristic polynomial of the matrix is

$\displaystyle f(\lambda)=\lambda^{4}$ $\displaystyle+$
$\displaystyle(-4n+8)\lambda^{3}+(3n^{2}-8ns+8s^{2}-24n-8s+24)\lambda^{2}$
$\displaystyle+$
$\displaystyle(8n^{2}s-8ns^{2}+12n^{2}-32ns+40s^{2}-48n-40s+32)\lambda$
$\displaystyle-$ $\displaystyle
12n^{2}s^{2}+24s^{3}n-12s^{4}+28n^{2}s-52ns^{2}+24s^{3}+12n^{2}$
$\displaystyle-$ $\displaystyle 20sn+36s^{2}-32n-48s+16.$

We know that ${\lambda}_{1}(D(B_{s,s-1}))$ is the largest root of
$f(\lambda)=0$. Since ${\lambda}_{1}\left(D\left(B_{n-1,n-2}\right)\right)$,
written by $\rho$, is the largest root of the equation

$q(\lambda)=\lambda^{4}+(-4n+8)\lambda^{3}+(3n^{2}-40n+40)\lambda^{2}+(28n^{2}-144n+112)\lambda+20n^{2}-88n+64=0,$

we have

$\displaystyle h(\rho)$ $\displaystyle=$ $\displaystyle
f\left(\rho\right)-q\left(\rho\right)$ $\displaystyle=$
$\displaystyle(8s^{2}-(8n+8)s+16n-16)\rho^{2}$ $\displaystyle+$
$\displaystyle(8sn^{2}-8ns^{2}-16n^{2}-32ns+40s^{2}+96n-40s-80)\rho$
$\displaystyle-$ $\displaystyle
12n^{2}s^{2}+24s^{3}n-12s^{4}+28sn^{2}-52ns^{2}+24s^{3}-8n^{2}-20sn+36s^{2}+56n-48s-48.$

Now we need to state $h(\rho)<0$. Firstly, we give a lower bound on $\rho$,

$\frac{2W(B_{n-1,n-2})}{2n}=2n+5-\frac{6}{n}<\rho.$

By a simple computation, we obtain

$8s^{2}-(8n+8)s+16n-16\leq 0\ \mbox{for}\ 2\leq s\leq n-2,$

and

$\displaystyle\frac{8sn^{2}-8ns^{2}-16n^{2}-32ns+40s^{2}+96n-40s-80}{-2(8s^{2}-(8n+8)s+16n-16)}=\frac{n-5}{2}<2n<\rho.$

Thus, $h(\rho)$ is monotonically decreasing for $\rho>2n$ and $h(\rho)<h(2n)$.
Let $h(2n)$ be written by $g(s)$ and we only need to prove $g(s)<0$ for $2\leq
s\leq n-2$ in the following steps. Based on Matlab programming, we have

$\displaystyle g(s)=-4(s-2)(-s+n-1)[-3s^{2}+(3s+3)n+19n+4n^{2}+6].$

It is easy to see $s-2\geq 0$ and $-s+n-1>0$. Define
$r(s)=-3s^{2}+(3s+3)n+19n+4n^{2}+6$, we can easily get for $2\leq s\leq n-2$
and $n\geq 3$,

$\displaystyle r(s)=-3s^{2}+(3s+3)n+19n+4n^{2}+6$ $\displaystyle>$
$\displaystyle\min\\{r(2),\
r(n-2)\\}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}$
$\displaystyle=$ $\displaystyle\min\\{4n^{2}+25n,\ 4n^{2}+28n-12\\}$
$\displaystyle>$ $\displaystyle 0.$

Therefore, $h(\rho)<h(2n)=g(s)<0$. So Claim 2 holds.

In conclusion, $G\cong B_{n-1,n-2}$ has the minimum distance spectral radius
among all $2n$-vertex balanced bipartite graphs without a perfect matching.∎

## References

  * [1] M. Aouchiche, P. Hansen, Proximity, remoteness and distance eigenvalues of a graph, _Discrete Appl. Math._ 222 213 (2016) 17–25.
  * [2] M. Aouchiche, P. Hansen, Distance spectra of graphs: A survey, _Linear Algebra Appl._ 458 (2014) 301–386.
  * [3] A. E. Brouwer, W. H. Haemers, Eigenvalues and perfect matchings, _Linear Algebra Appl._ 395 (2005) 155–162.
  * [4] A. Chang, Bounds on the second largest eigenvalue of a tree with perfect matchings, _Linear Algebra Appl._ 283 (1998) 247–255.
  * [5] L. Feng, G. Yu, X. Zhang, Spectral radius of graphs with given matching number, _Linear Algebra Appl._ 422 (2007) 133–138.
  * [6] R.L. Graham, H.O. Pollack, On the addressing problem for loop switching, _Bell Syst. Tech. J._ 50 (1971) 2495–2519.
  * [7] P. Hall, On a Theorem of Frobenius, _Proc. London Math. Soc._ 40 (2) (1936) 468–501.
  * [8] Y. Hou, J. Li, Bounds on the largest eigenvalues of trees with a given size of matching, _Linear Algebra Appl._ 342 (2002) 203–217.
  * [9] A. Ilić, Distance spectral radius of trees with given matching number, _Discret. Appl. Math._ 158 (2010) 1799–1806.
  * [10] H. Lin, On the sum of $k$ largest distance eigenvalues of graphs, _Discrete Appl. Math._ 259 (2019) 153–159.
  * [11] H. Lin, Y. Zhang, Extremal problems on distance spectra of graphs, _Discrete Applied Math._ 289 (2021) 139–147.
  * [12] Z. Liu, On spectral radius of the distance matrix, _Appl. Anal. Discret. Math._ 4 (2010) 269–277.
  * [13] Z. Lou, H. Lin, Distance eigenvalues of a cograph and their multiplicities, _Linear Algebra Appl._ 608 (2021) 1–12.
  * [14] H. Lu, J. Luo, Extremal unicyclic graphs with minimal distance spectral radius, _Discuss. Math. Graph Theory_ 34 (2014) 735–749.
  * [15] S. O, Spectral radius and matchings in graphs, _Linear Algebra Appl._ (2020) https://doi.org/10.1016/j.laa.2020.06.004.
  * [16] W.T. Tutte, The factorization of linear graphs, _J. Lond. Math. Soc._ 22 (1947) 107–111.
  * [17] J.Xue, H. Lin, J. Shu, On the second largest distance eigenvalue of a block graph, _Linear Algebra Appl._ 591 (2020) 284–298.
  * [18] M. Zhang, S. Li, Extremal cacti of given matching number with respect to the distance spectral radius, _Applied Math. Comput._ 291 (2016) 89–97.
  * [19] X. Zhang, On the distance spectral radius of unicyclic graphs with perfect matching, _Electron. J. Linear Algebra_ 27 (2014) 569–587.


# Automatic Detection of Satire in Bangla Documents: A CNN Approach Based on
Hybrid Feature Extraction Model

Arnab Sen Sharma  Computer Science and Engineering
Shahjalal University of
Science & Technology
Sylhet-3114, Bangladesh
Email<EMAIL_ADDRESS>Maruf Ahmed Mridul  Computer Science and
Engineering
Shahjalal University of
Science & Technology
Sylhet-3114, Bangladesh
Email<EMAIL_ADDRESS>Md Saiful Islam  Computer Science and Engineering
Shahjalal University of
Science & Technology
Sylhet-3114, Bangladesh
Email<EMAIL_ADDRESS>
###### Abstract

Wide spread of satirical news in online communities is an ongoing trend. The
nature of satires are so inherently ambiguous that sometimes it’s too hard
even for humans to understand whether it’s actually satire or not. So,
research interest has grown in this field. The purpose of this research is to
detect Bangla satirical news spread in online news portals as well as social
media. In this paper we propose a hybrid technique for extracting feature from
text documents combining Word2Vec and TF-IDF. Using our proposed feature
extraction technique, with standard CNN architecture we could detect whether a
Bangla text document is satire or not with an accuracy of more than 96%.

###### Index Terms:

satire detection, natural language processing, TF-IDF, fact-checking, CNN,
Word2Vec.

##  I Introduction

Satires can be considered as a literary form which involves a delicate balance
between criticism and humor. Through satire or sarcasm, messages are conveyed
in an artistic form that sometimes creates a deviated implicit meaning. The
goal of satire is not always to tell the truth. Sometimes humans are not
effective enough to distinguish between satires and actual news because often
the satires are so ambiguous that it is easy to get deceived.

The spread of satirical news is not a new concept. But in the recent years it
has become a real threat that can not be ignored anymore. Easy access of
Internet and hyperactivity of users in various social media platforms has
given rise to the extensive spread of satirical news. Internet has largely
replaced traditional news media. Many people, especially a huge portion of
youth depend on Internet and social media as the primary source for news
consumption because of their easy access, low cost and 24/7 availability. They
simply believe in what they read in internet and spread the news what they
assumed to be true. So, most of the times, satires are not spread with an
intention to deceive. But sometimes some people for their personal benefits
take advantage and promote the spread of satires as actual news.

As a matter of fact, there are some web based applications such as Snopes.com,
FactCheck.org, PolitiFact etc which act as fact-checkers. But, these services
use human staffs to manually check facts. Though these services provide
accurate information most of the time, these are not efficient enough since
they are not automated. We propose an automated system based on Convolutional
Neural Network and Natural Language Processing to address the problem.

There are some related existing works. The Literature Review section will
discuss about these. Also, we’ll define some terms and techniques that we used
in this work.

###  I-A Literature Review

De Sarkar, et al. proposed a hierarchical deep neural network approach to
detect satirical fake news which is capable of capturing satire both at the
sentence level and at the document level [1]. Burfoot, et al. used SVM and
bag-of-words to detect satires [2]. They used binary feature weights and bi-
normal separation feature scaling for feature weighting. They got a best
overall F-score of 79.8%[2].

Rubin, et al. classifies news as Satires, Fabrications and Hoaxing as the
parts of fake news [3]. Reyes, et al. used figurative language processing for
humour and irony detection [4].

Ahmad and Tanvir used tockenized, stopword free and stemmed data to classify
satire and irony using SVM and got an accuracy of 83.41%[5]. el Pilar Salas-
Zárate and María used some psycholinguistic approaches for satire detection in
twitter and got F-score of 85.5% for mexican data and 84.0% for spanish data
[6].

Tacchini and Eugenio check facts using the information of the users who liked
a news[7]. Applying logistic regression on the information of likers, around
99% accuracy is achieved for their dataset.

Some approaches simply used a naive bayes classifier to classify a news. After
a little bit of preprocessing on 1-grams from the news context, words are fed
to a naive bayes classifier. Granik, et al. proposed to do a stemming to
increase accuracy[8]. The accuracy got using this approach without
preprocessing is nearly 70%[8] and Pratiwi, et al. got accuracy of 78.6% with
preprocessing in Indonesian Language[9].

Ruchansky, et al. proposed a Capture Score and Integrate model[10]. Sense
making words from the body text of the news of twitter[11] and weibo[12] are
taken and fed to a RNN and the reviews of the news are taken as feature. The
accuracy for this model is 89.2% for twitter data and 95.3% for weibo
data[10].

Conroy,et al. proposed two different approaches for detecting fake news [13].
One is linguistic approach which includes deep syntax analysis and semantic
analysis. Deep syntax analysis is implemented based on Probability Context
Free Grammars(PCFG). It can predict falsehood approximately 91% accurately.

Another one is network approach that is based on fact checking using the
knowledge networks formed by interconnecting the linked data. This approach
gives an accuracy in the range of 61% to 95% for different subject areas.

###  I-B Definitions

####  I-B1 Word Embedding

Word embedding simply refers to vector representation of words. Normally
machine learning models are not capable of processing string or text as input.
These models expect vectors or values as input. So, transformation of a word
to a vector is a crucial part. There are several techniques to convert word to
vectors. These techniques can be categorized as two types 1\. Frequency based
(TF-IDF, CountVectorizer, HashVectorizer) 2\. Prediction based (Word2Vec)

####  I-B2 TF-IDF

In this work we focused on TF-IDF vectorizer amongst TF-IDF, CountVectorizer,
HashVectorizer etc. as the frequency based word embedder. TF stands for Term
Frequency and IDF stands for Inverse Document Frequency. It is used in text
mining as a weighting factor for features. The equation representing the TF-
IDF weight of a term t for a particular document d (given the whole dataset D
and the number of documents in the dataset N) is

$tf-idf(t,d)=tf(t,d)\times idf(t,D)$ (1) $Here,$

$tf(t,d)=$ Frequency of $t$ in $d$

$idf(t,D)=log(\frac{N}{\left|\\{d\epsilon D:t\epsilon d\\}\right|})$ [14]

TF is upweighted by the number of times a term occurs in an article. And IDF
is downweighted by the number of times a term occurs in the whole
dataset/corpus. So TF-IDF assigns less significant values to words that
generally occurs in most documents such as is, are, be, to, on … etc.

####  I-B3 Word2Vec

Though heavily used in the field of NLP, frequency based word embedders fail
to capture the semantic value of a word or document. Word2Vec is the process
of transforming words to vectors preserving some of their syntactical and
semantic correlations. Word2Vec tries to determine the meaning of a word and
understand its correlation with other words by looking at it’s context. For
example, lets take two sentences ”Range Rover is great car” and ”Range Rover
is a wonderful vehicle”, then a well-trained Word2vec should be able map
similarities between the words great and wonderful and the words car and
vehicle. Word2Vec uses cosine distance over euclidean distance to measure the
similarity or distance between two words. Let’s take some pair of singular-
plural words like cat and cats, dog and dogs. Here the singular-plural
relation between the words cat and cats is represented by the cosine
difference between the two words $V_{cat}$ and $V_{cats}$ (2) is given by the
equation below

$cosine(V_{cat},V_{cats})=\frac{V_{cat}\times
V_{cats}}{||V_{cat}||\times||V_{cats}||}$ (2)

Figure 1: Word2Vec (a)

Figure 2: Word2Vec (b)

And now the word pair dog and dogs have the same singular-plural relationship
between them like cat and cats (2). So according to Word2Vec

$V_{dog}-V_{dogs}=V_{cat}-V_{cats}$ $\Rightarrow
V_{dogs}=V_{cats}-V_{cat}+V_{dog}$

So, if we know the particular relationship between two words and know one of
the words, Word2vec can predict the other word.

####  I-B4 CNN in NLP

Convolutional Neural Network(CNN) is a deep learning algorithm that takes a
multidimentional vector or an image as input. CNNs captures the significant
aspects of the input through the application of appropriate filters and
perform classification tasks. With enough training CNNs are able to learn
which filters are appropriate for different contexts. Different
filters/kernels are slided on the beginning layers named after convolutional
layer and extract different features and feed-forward the values to next layer
of the architecture. Besides learning high level features of an image these
filters also reduce the size of convolved feature space and thus reduce the
computational power required for processing the data. The convolved features
extracted by the convolutional layers are then fed to a normal neural network
architecture possibly with a number of hidden layers. This neural network
learns the convolved feature vector and does the actual classification task.

Recently CNNs are used heavily in NLP. CNN expects the input to be a
multidimensional image but we have a one dimensional vector from a word after
word embedding. So, instead of single words we feed whole sentences or
documents into CNN . From a 20 word document or sentence where each word is
embedded to a 200 dimension vector, we can get a $20\times 200$ matrix. This
two dimensional vector can act as an image and can be fed as an input to CNN.
From various experiments and researches it was found that CNN performs quite
well in generalizing the relationships between words in a document and thus
capturing itś semantic meaning. CNN performs better than the simple bag of
words and prone to less inaccurate assumptions.

##  II Proposed method

First of all, we built our own Word2Vec model modifying the traditional
Word2Vec model. Then an image is created from a preprocessed document
combining Word2Vec and TF-IDF vectorizers. Finally, that image is used as
input to a CNN architecture. The detailed procedure is discussed below.

###  II-A Building our own Word2Vec model

There are some great Word2Vec models for English language, but as per our
knowledge there is no good performing Word2Vec model for Bangla. So, we had to
create our own Word2Vec model. To do so, we relied on gensim library of
python. We needed a lot of textual data to train the model. We used the scrapy
library of python to build crawlers and crawled Bangla textual data from
Wikipedia and online news portals. We collected 380832 articles in total and
used these to train our model. Our Word2Vec model converts Bangla words to a
vector of size 10. To check the performance of our model, we checked the 5
most similar words of a Bangla word. Here are the results.

Figure 3: Testing Word2Vec model with a word

###  II-B Dataset

We used the scrapy library of Pyhon to build crawlers to crawl bangla textual
data from different websites. For authentic news data we crawled news articles
from two bangla news portals Prothom Alo[15] and Ittefaq[16]. For satire data
we crawled articles from a renowned satire news portal Motikontho[17]. We
crawled a total of 1480 articles from Motikontho. To balance our dataset we
randomly selected 1480 articles from the REAL news articles we collected from
Prothom Alo and Ittefaq. The formation of the dataset is very simple. A single
data is only a document and a label (satire or not).

###  II-C Data Preprocessing

The collected dataset might be mixed with some noisy and unnecessary data. So,
we had to get rid of them through a bit of preprocessing. Our preprocessing
consisted of the following steps.

####  II-C1 Ignoring stopwords and punctuations

We ignored the stopwords from every news document. Because, these words appear
in almost every article and do not provide any significant information. Some
example of stopwords -

We collected the list of Bangla stopwords from a github repository by
genediazjr[18].

####  II-C2 Stemming

The purpose of a stemming is to find the root word. We used a stemmer
developed by Rafi Kamal[19] which we found in his github repository. The
stemmer performed better compared to other available Bangla stemmers that we
could find.

Figure 4: Stemming

###  II-D Document to Image

For converting a document to a vector we selected TF-IDF vectorizer of size
1000. It means 1000 words/terms were selected based on our corpus. We ignored
the terms that occur in more than 70% of the documents in our corpus. Because
common words do not add any significant value to a specific document. We also
ignored rare terms(the terms that occur in less than 10% of the documents).
Because these terms might overfit any model. Also any numeric terms were
ignored. The term frequency of the rest of the words were calculated and most
significant 1000 terms were selected. The respective TF-IDF values of these
terms for a document are used to create a vector of size 1000 that represents
the document. But these TF-IDF values do not hold any semantic meanings. So
each of the words were converted to a vector of size 10 using our Word2Vec
model. These vectors of size 10 were multiplied by their respective TF-IDF
values for a document. So, for each document we had a 2D vector of size
$1000\times 10$. Also, convolutional layers expect pixel values of an image.
Pixel values are never negative. So, CNNs cannot take a vector which contains
some negative values. But word2vec embedded vectors can contain negative
values. CNN input layers actually take a 3 dimensional vector. First two
dimensions represents the 2D image and the third dimension is the number of
filters. For coloured images the number of filters is 3(Red, Green, Blue) and
each pixel value of image is formed with 3 values in RGB system. Our strategy
to handle negative numbers was to separate the positive and negative values in
two dimensions just like the picture below.

Figure 5: Transformation of Feature Vectors

So, for each document we had a 3D vector of size $1000\times 10\times 2$.

###  II-E Structure of the model

  * •

Input layer: Input layer contains a Convolutional2D layer with $256$ filters
that takes vectors of shape $1000\times 10\times 2$ as input.

  * •

Another Convolutional2D layer with $128$ filters with ReLU activation.

  * •

Pooling layer of size $2\times 2$.

  * •

Dropout layer with value $0.25$ to avoid overfitting.

  * •

A Dense layer with $512$ neurons with ReLU activation.

  * •

Dropout layer with value $0.5$.

  * •

Output layer: One neuron with sigmoid activation.

##  III Results and Analysis

The dataset was randomly split to two parts. 70% of the data (2018 documents)
were used as training dataset. The rest 30% (942 documents) were used to test
the performance of our model. This model gave us an accuracy rate of 96.4% on
the test dataset. Since the dataset was balanced the F1 score was same as the
accuracy value. The confusion matrix is given below.

Figure 6: (a) Total Count Representation

Figure 7: (b) Percentile Representation

Figure 8: Confusion Matrices showing the results

There are some scopes to improve our Word2Vec model and a perfect stemmer for
Bangla language can boost the overall performance of our proposed model. The
model was compiled with 2GB graphics card of NVIDIA GeForce 940M. So, we could
not use a TF-IDF vector and a Word2Vec vector of larger size. If we had access
to more resources we could use bigger feature vectors and the accuracy might
have improved some.

Actually, in terms of accuracy, humans are much more effective than a machine
for this task. Maybe for our dataset, human will be able to detect satires
100% accurately. But, though the accuracy falls a bit, we think it’s much
better to use an automated approach which saves a lot of time.

##  IV Conclusion

Satire detection for Bangla news is completely new. As per our knowledge, no
such work has been done in this sector for Bangla language. We found that our
hybrid feature extraction technique combined with a CNN model performs great
in language processing for pattern finding. Since satire is a type of
fakeness, satire detection can be an important prerequisite of fake news
detection. So, this work might be helpful to take better decisions on fake
news detection and other such works. Also our hybrid feature extraction
technique can be used in other works of similar nature.

## References

  * [1] De Sarkar, Sohan, Fan Yang, and Arjun Mukherjee. ”Attending sentences to detect satirical fake news.” In Proceedings of the 27th International Conference on Computational Linguistics (pp. 3371-3380).
  * [2] Burfoot, Clint, and Timothy Baldwin. ”Automatic satire detection: Are you having a laugh?.” Proceedings of the ACL-IJCNLP 2009 conference short papers. 2009.
  * [3] Rubin, Victoria L., Yimin Chen, and Niall J. Conroy. ”Deception detection for news: three types of fakes.” Proceedings of the 78th ASIS&T Annual Meeting: Information Science with Impact: Research in and for the Community. American Society for Information Science, 2015.
  * [4] Reyes, Antonio, Paolo Rosso, and Davide Buscaldi. ”From humor recognition to irony detection: The figurative language of social media.” Data & Knowledge Engineering 74 (2012): 1-12.
  * [5] Ahmad, Tanvir, et al. ”Satire detection from web documents using machine learning methods.” 2014 International Conference on Soft Computing and Machine Intelligence. IEEE, 2014.
  * [6] del Pilar Salas-Zárate, María, et al. ”Automatic detection of satire in Twitter: A psycholinguistic-based approach.” Knowledge-Based Systems 128 (2017): 20-33.
  * [7] Tacchini, Eugenio, et al. ”Some like it hoax: Automated fake news detection in social networks.” arXiv preprint arXiv:1704.07506 (2017).
  * [8] Granik, Mykhailo, and Volodymyr Mesyura. ”Fake news detection using naive Bayes classifier.” 2017 IEEE First Ukraine Conference on Electrical and Computer Engineering (UKRCON). IEEE, 2017.
  * [9] Pratiwi, Inggrid Yanuar Risca, Rosa Andrie Asmara, and Faisal Rahutomo. ”Study of hoax news detection using naïve bayes classifier in Indonesian language.” 2017 11th International Conference on Information & Communication Technology and System (ICTS). IEEE, 2017.
  * [10] Ruchansky, Natali, Sungyong Seo, and Yan Liu. ”Csi: A hybrid deep model for fake news detection.” Proceedings of the 2017 ACM on Conference on Information and Knowledge Management. ACM, 2017.
  * [11] https://twitter.com/

  * [12] https://www.weibo.com

  * [13] Conroy, Niall J., Victoria L. Rubin, and Yimin Chen. ”Automatic deception detection: Methods for finding fake news.” Proceedings of the Association for Information Science and Technology 52.1 (2015): 1-4.
  * [14] https://en.wikipedia.org/wiki/Tf-idf

  * [15] https://www.prothomalo.com/

  * [16] https://www.ittefaq.com.bd/

  * [17] https://motikontho.wordpress.com/

  * [18] https://github.com/stopwords-iso/stopwords-bn/blob/master/stopwords-bn.txt

  * [19] https://github.com/rafi-kamal/bangla-stemmer