# U-Former: Improving Monaural Speech Enhancement with Multi-head Self and
Cross Attention

Xinmeng Xu1, Jianjun Hao2,∗ ∗Corresponding author 1E.E. Engineering, Trinity
College Dublin, Dublin, Ireland
2School of Foreign Languages, Hubei University of Chinese Medicine, Wuhan,
China
<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

For supervised speech enhancement, contextual information is important for
accurate spectral mapping. However, commonly used deep neural networks (DNNs)
are limited in capturing temporal contexts. To leverage long-term contexts for
tracking a target speaker, this paper treats the speech enhancement as
sequence-to-sequence mapping, and propose a novel monaural speech enhancement
U-net structure based on Transformer, dubbed U-Former. The key idea is to
model long-term correlations and dependencies, which are crucial for accurate
noisy speech modeling, through the multi-head attention mechanisms. For this
purpose, U-Former incorporates multi-head attention mechanisms at two levels:
1) a multi-head self-attention module which calculate the attention map along
both time- and frequency-axis to generate time and frequency sub-attention
maps for leveraging global interactions between encoder features, while 2)
multi-head cross-attention module which are inserted in the skip connections
allows a fine recovery in the decoder by filtering out uncorrelated features.
Experimental results illustrate that the U-Former obtains consistently better
performance than recent models of PESQ, STOI, and SSNR scores. The source code
is available at: https://github.com/XinmengXu/Uformer.git.

###### Index Terms:

supervised speech enhancement, long-term contexts, sequence-to-sequence
mapping, U-net structure, Transformer, multi-head self-attention, multi-head
cross-attention

##  I Introduction

The problem of enhancing speech corrupted by uncorrelated additive noise, when
only single-channel noisy speech is available, has been widely studied in the
past and it is still a active filed of research. Traditional speech
enhancement approaches include spectral subtraction [1], Wiener filtering [2],
statistical model-based methods [3], and non-negative matrix factorization
[4]. Recently, supervised methods using deep neural networks have become shown
their promising performance on monaural speech enhancement [5, 6].

Various encoder-decoder frameworks based on convolutional neural networks
(CNN) or recurrent neural networks (RNNs) have gained superior network
performance in speech enhancement. For modeling long-range sequence like
speech, CNN requires more convolutional layers to enlarge receptive field [7,
ref101]. The dilated convolutional neural network has been proposed for
processing the long-term temporal sequence [8]. In addition, recurrent neural
networks (RNNs) employing long short-term memory (LSTM) have demonstrated a
robust speech enhancement performance [9]. However, RNNs require large number
of parameters and lengthy training times, and the memory of LSTM is limited,
making it prone to forgetting distant information [10]. Temporal convolutional
networks (TCNs) are proposed to match the speech enhancement performance of
RNNs while use fewer parameters and requiring less time to train [11]. TCNs
utilize causal dilated kernels to garner a fixed-size receptive field over
previous frames, allowing the modelling of long-term dependencies. However,
the performance of TCNs are adversely affected when events occur out of
expected order due to the positional nature of the kernels [12].

Recently, as the outstanding performance in natural language processing (NLP),
the Transformer is introduced in speech enhancement problem [13]. The
Transformer follows the encoder and decoder architecture with stacked self-
attention and point-wise feed-forward layers [14], which promise a stronger
long-term dependencies modelling capability than TCNs. However, the
Transformer has a limitation as difficult to process a multiple-sequence
alignment as an input for feature extraction in the inference stage [15]. In
this study, we integrate the Transformer and encoder-decoder structure for
learning both local and global contextual information of long-range speech.
Consequently, this paper propose a U-Former for monaural speech enhancement,
which keeps the inductive bias of convolution by using a U-Net architecture,
but introduces attention mechanisms at two levels, 1) the multi-head self-
attention (MHSA) module calculates the attention map along both time- and
frequency-axis to generate time and frequency sub-attention maps for
leveraging global interactions between encoder feature, 2) the multi-head
cross-attention module (MHCA) in skip-connections to filter out uncorrelated
feature and to reduce the loss of feature information from corresponding
encoder layer 111Speech samples are available at: https://xinmengxu.github.io/
AVSE/MHACUnet.html. .

Figure 1: Network architecture of proposed U-Former. Conv-E, Conv-D, and BN
denote convolution encoder, convolution decoder, and batch normalization
respectively.

In a nutshell, the contributions of our work are three-fold:

  * •

We integrate the Transformer and encoder-decoder structure, which aims to
learn both local and global contextual information of long-range speech.

  * •

We propose MHSA and MHCA modules to leverage global interactions between
encoder feature and to filter out uncorrelated feature and to reduce the loss
of feature information from corresponding encoder layer.

  * •

To evaluate the proposed U-Former, we perform comprehensive ablation studies
on public available speech data. Results show that U-Former outperforms the
state-of-the-art methods.

Rest of paper is organised as follows: Section II introduces the signal model
and problem formulation. Section III presents the proposed network, and
discusses mechanisms of MHSA and MHCA in detail. Section IV describes the
datasets and network parameters. Section V demonstrates the results and
analysis, and a conclusion is shown in Section VI.

##  II Signal model and problem formulation

Given a single-microphone mixture $y$, monaural SE aims to separate target
speech $s$ from background noise $n$. A noisy mixture can be formulated as

$y[k]=s[k]+n[k],$ (1)

where $k$ is the time sample index. Taking the STFT on both sides, we obtain

$Y(m,f)=S(m,f)+N(m,f),$ (2)

where $Y$, $S$ and $N$ represent the STFT of $y$, $s$ and $n$, respectively,
and $m$ and $f$ index the time frame and frequency bin, respectively. The STFT
of a speech signal can be expressed in Cartesian coordinates. Hence, Eq 2 can
be rewritten into

$\displaystyle Y^{(r)}(m,f)+iY^{(i)}(m,f)$
$\displaystyle=\Big{(}S^{(r)}(m,f)+N{(r)}(m,f)\Big{)}$ (3)
$\displaystyle+i\Big{(}S^{(i)}(m,f)+N^{(i)}(m,f)\Big{)},$

where the superscripts $(r)$ and $(i)$ indicate real and imaginary components,
respectively. In our work, we refer the training target used in complex
spectral mapping, i.e. $S^{(r)}$ and $S^{(i)}$, as the target RI-spectrogram.

The speech enhancement using U-Former can be formulated as

$s_{pre}=f_{\theta}(Y^{(r)},Y^{(i)})$ (4)

where $f_{\theta}$ denotes a function defining a U-Former model parameterized
by $\theta$.

##  III Model Architecture

Fig 1 shows the proposed speech enhancement network. The model uses encoder-
decoder structure that based on the standard convolution U-Net [14], as the
main body. The input to the U-Former is complex valued spectrogram computed by
short-time Fourier transform (STFT), denoted by
$\textbf{Y}_{r,i}\in\mathbb{R}^{T\times F\times 2}$, where $T$ represents the
number of time steps and $F$ represents the number of frequency bands. The
output of U-Former $\textbf{S}_{out}$ is processed by a learnable decoder
layer to transform the feature back to the enhanced time-domain signal
$\textbf{s}_{pre}\in\mathbb{R}$. The network structure of the learnable
decoder is designed to be exactly the same as the convolutional implementation
of inverse STFT. Specifically, the learnable decoder is a 1D transposed
convolution layer whose kernel size and stride being the window length and hop
size in the STFT [16, 17]. .

In addition, the encoder of U-Former contains several stacked convolutional
layers, each of which is followed by batch normalization, and Leaky-ReLU for
non-linearity. The decoder is mirror representations of the encoder. What is
more, the proposed U-Former models long-range contextual interaction and
dependencies by using two types of attention modules, MHSA placed in
bottleneck part and MHCA placed in skip-connection part. Both modules are
designed to express a new representation of the input based on its self-
attention in the first case or on the attention paid to higher level features
in the second.

Figure 2: Schematic diagram of MHSA module.

###  III-A Multi-head Self-attention (MHSA)

In the proposed U-Former, the MHSA module is designed to extract long range
structural information [13]. To this end, it is composed of multi-head self-
attention functions positioned at the bottom of the U-Net as shown in Fig 1.
MHSA takes as input an L-length sequence of embedding and produces a same size
output sequence. The output of the attention matrix is presented as [18]:

$\mathcal{A}(Q,K,V)=\text{Softmax}\Big{(}\frac{QK^{\top}}{\sqrt{L}}\Big{)}V,$
(5)

where $\top$ denotes the transpose symbol. Initially, the full attention map
$\textbf{F}_{in}\in\mathbb{R^{T\times F\times C}}$ is the input to each sub-
layer of the encoder, the proposed MHSA are reshaped the 2D attention map into
1D sub-maps in time- and frequency-axis as $T\times C_{\text{layer}}$ and
$F\times C_{\text{layer}}$, respectively, as shown in Fig 2. Each sub
attention map progrates information along specific axis. Moreover, two sub
attention maps are constructed as parallel calculations on multiple GPUs to
optimize the training process. The multi-head attention for the time direction
can be presented as:

$\text{multihead}(Q^{t},K^{t},V^{t})=[h_{1};h_{2};...;h_{n}]W_{t}^{O},$ (6)

where

$h_{i}=\mathcal{A}\Big{(}Q^{t}W^{Q}_{t},K^{t}W^{K}_{t},V^{t}W^{V}_{t}\Big{)},$
(7)

where $W_{t}^{O}\in\mathbb{R}^{n\times C_{v}\times C_{\text{layer}}}$ ($n$
denotes the number of head),
${W^{Q}_{t},W^{K}_{t}}\in\mathbb{R}^{C_{\text{layer}}\times C_{k}}$,
$W^{V}_{t}\in\mathbb{R}^{C_{\text{layer}}\times C_{v}}$. In the time attention
map, query, keys and values are presented as $Q^{t},K^{t},V^{t}$,
respectively. Similarly, for frequency attention, we adopt same equations but
different notations $f$:

$\text{multihead}(Q^{f},K^{f},V^{f})=[h_{1};h_{2};...;h_{n}]W_{f}^{O},$ (8)

where

$h_{i}=\mathcal{A}\Big{(}Q^{f}W^{Q}_{f},K^{f}W^{K}_{f},V^{f}W^{V}_{f}\Big{)},$
(9)

The proposed MHSA demonstrates high efficacy to learn the long-term
dependencies. Inspired by the position-sensitivity of self-attention [19], the
output $h_{i}$ is enabled to retrieve relative positions by pooling over
query-key affinities $Q^{t}_{p}K^{t}_{p}$, the key-dependent positional bias
term $K_{c}^{t}r^{K^{t}}_{c-p}$:

$\displaystyle h_{i}=\sum_{c\in\mathcal{N}_{1\times
n(c)}}\text{softmax}(Q^{t}_{p}K^{t}_{c}+Q^{t}_{p}r^{Q^{t}}_{c-p}$ (10)
$\displaystyle+K_{c}^{t}r^{K^{t}}_{c-p})(V_{c}-r^{V^{t}}_{c-p}),$

where $\mathcal{N}_{1\times n(c)}$ is the local $1\times m$ region around
position $c$. The learnable $r^{Q^{t}}_{c-p}$, $r^{K^{t}}_{c-p}$, and
$r^{V^{t}}_{c-p}$ are the positional encoding for query, key, and value,
respectively.

To capture global information, we employ two sub-attention layers
consecutively for the time-axis and frequency-axis, respectively.
Consequently, the outputs of time and frequency attentions can be written as:

$\displaystyle M_{t}$ $\displaystyle=\text{multihead}(Q^{t},K^{t},V^{t}),$
(11) $\displaystyle M_{f}$
$\displaystyle=\text{multihead}(Q^{f},K^{f},V^{f}),$

Finally, the masked attention maps are reshaped, integrated and processed by a
$1\times 1$ convolution block to obtained the output feature map,
$\textbf{F}_{out}$, in which residual connections are added as well.

$\textbf{F}_{out}=\text{Conv}(M_{t}+M_{f}+M_{p}),$ (12)

where $M_{p}$ is the input feature map.

###  III-B Multi-head Cross-attention (MHCA)

The MHSA module allows to connect every element in the input with each other.
Attention may also be used to increase the U-Net decoder efficiency and in
particular enhance the lower level feature maps that are passed through the
skip connections.

The idea behind the MHCA module is to turn off irrelevant or noisy areas from
the skip connection features and highlight regions that present a significant
interest for the application. The MHCA block which diagram is shown in Fig 3,
is designed as a gating operation of the skip connection.

The MHCA takes transformed feature maps corresponding to the decoder layer X,
and processed by a $1\times 1$ convolution block to form the query, and takes
transformed feature maps corresponding to the encoder layer Y, to form the
key-value pair by using two $1\times 1$ convolution blocks. The MHCA first
computes the weight P for getting the attention component $\textbf{A},$ given
by

$\textbf{P}=\frac{\textbf{Q}\textbf{K}^{\top}}{\sqrt{F}},$ (13)

where Q, K are represented query and key, respectively, and $F$ denotes the
number of frequency bins. Intuitively, the multiplication operation between Q
and K emphasizes the regions which are slowly varying in time and have high
power. What is more, the softmax function is used to generate attention mask
$\widehat{\textbf{W}}=\\{\widehat{W}_{i,j}\\}$,

$\widehat{W}_{i,j}=\frac{exp(W_{i,j})}{w_{j}},$ (14)

where

$w_{j}=\sum_{i=1}^{F}exp(W_{i,j}),$ (15)

The attention component A is determined by

$\textbf{A}=\widehat{\textbf{W}}\textbf{V},$ (16)

where V denotes the index of value. What is more, the output of MHCA Z is
computed by

$\textbf{Z}=\text{sigmoid}(\textbf{A}),$ (17)

Consequently, the Z is weight value that are re-scaled between 0 and 1 through
a sigmoid activation function, in which low magnitude elements indicated
irrelevant areas to be reduced.

Figure 3: Schematic diagram of MHCA module.

A cleaned up version of $\textbf{X}_{clean}$ is given by

$\textbf{X}_{clean}=\textbf{X}\odot\textbf{Z},$ (18)

where $\odot$ is Hadamard product. Finally the $\textbf{X}_{clean}$ is
concatenated with Y.

###  III-C Loss function

The proposed model is trained by a combination of two losses. First, the time-
domain loss that is defined as:

$L_{t}(\textbf{x},\hat{\textbf{x}})=\frac{1}{M}\sum_{n=0}^{M-1}(x_{i}[n]-\hat{x}_{i}[n])^{2},$
(19)

where $x[n]$ and $\hat{x}[n]$ represent the $n^{th}$ sample of the clean and
the enhanced utterance respectively and M is the utterance length.

Second, the frequency-domain loss which takes STFT of the utterances and use
$L_{1}$ over the $L_{1}$ norm of the STFT coefficients [20], which is given
by:

$\begin{split}L_{f}(\textbf{x},\hat{\textbf{x}})=\frac{1}{T\times
F}\sum_{t=1}^{T}\sum_{f=1}^{F}|(|X(t,f)_{r}|+|X(t,f)_{i}|)\\\
-|(\hat{X}(t,f)_{r}|+|\hat{X}(t,f)_{i}|)|,\end{split}$ (20)

where $X(t,f)$ and $\hat{X}(t,f)$ are the units of STFTs of x and
$\hat{\textbf{x}}$ respectively.$T$ and $F$ denote the index of frames and
frequency bins. $X_{r}$ and $X_{i}$ represent real and the imaginary of
complex variable $X$.

Finally, the time-frequency domain loss is expressed as:

$L(\textbf{x},\hat{\textbf{x}})=\alpha\times
L_{t}(\textbf{x},\hat{\textbf{x}})+(1-\alpha)\times
L_{f}(\textbf{x},\hat{\textbf{x}}),$ (21)

where $\alpha$ is a hyper-parameter that is tuned on the validation set. The
diagram of the loss function is shown in the right part of Fig 1.

##  IV Experimental Setup

###  IV-A Datasets

In order to evaluate performance of the proposed model, experiments are
conducted on Librispeech corpus [21]. There 6500 clean utterances are selected
for training set and 400 are selected for validation set, which are created
under the randomly SNR levels ranging from -5dB to 10dB. Noise signals are
from the Demand dataset [22], along with the clean speech recordings are used
to create the noisy speech for the training and validation set.

Test set contains 500 utterances under the SNR condition of -5dB, 0dB, 5dB and
10dB. Both speakers and noise conditions in the test set are totally unseen by
the training set. All of the clean speech and noise recordings with a sampling
frequency of 16 kHz, and the frame size and frame shift for STFT are set to
512 and 256.

###  IV-B Training and network parameters

In each epoch of the training, we chunk a random segment of 4 seconds from an
utterance if it is larger than 4 seconds. The smaller utterances are zero-
padded to match the size of the largest utterance in the batch. The Adam
optimizer is used for stochastic gradient descent (SGD) based optimization.
The numbers of output channels for the layers in the encoder are changed to
16, 32, 64, 128 and 256 successively, and those for each layer in the decoder
to 128, 64, 32, 16 and 1 successively. The initial learning rate is set to
0.001, and is decreased by 50$\%$ once when consecutive 3 validation
stagnates, and the training is early-stopped when 10 consecutive validation
loss increments happened.

All training audio data are downsampled to 16 kHz and features are extracted
by using frames of length 512 with frame shift of 256, and Hann windowing
followed by STFT of size $K=512$ with respective zero-padding. Real and
imaginary parts of the complex spectrum are divided into separate feature
maps, resulting in $C=2$ input channels, thus the input. In addition, the
hyper-parameter $\alpha$ of time-frequency domain loss in Eq.21 is set to 0.8
[23].

TABLE I: Comparisons of Alternative Models in STOI, PESQ, and SNR.

Test SNR | -5dB | 0dB | 5dB | 10dB | # Param.
---|---|---|---|---|---
Metric | STOI(%) | PESQ | SSNR(dB) | STOI(%) | PESQ | SSNR(dB) | STOI(%) | PESQ | SSNR(dB) | STOI(%) | PESQ | SSNR(dB)
Unprocessed | 57.71 | 1.37 | -5.04 | 71.02 | 1.73 | -0.05 | 82.53 | 2.03 | 4.93 | 90.41 | 2.42 | 9.79 | -
OMLSA [24] | 61.23 | 1.54 | 2.20 | 75.43 | 2.06 | 6.10 | 86.27 | 2.31 | 8.90 | 92.66 | 2.68 | 12.80 | -
Attention-wave-U-net [25] | 78.81 | 2.16 | 6.54 | 86.76 | 2.41 | 8.21 | 92.43 | 2.87 | 10.13 | 94.07 | 3.09 | 15.49 | 10.31 M
Attention-DCUNet [26] | 81.45 | 2.23 | 6.64 | 88.76 | 2.54 | 8.35 | 92.96 | 2.96 | 11.01 | 95.74 | 3.17 | 15.92 | 2.36 M
TSTNN [27] | 83.50 | 2.38 | 6.97 | 89.54 | 2.66 | 8.74 | 93.29 | 3.04 | 11.44 | 96.08 | 3.26 | 16.31 | 1.54 M
U-Former (Proposed) | 85.48 | 2.46 | 7.24 | 91.69 | 2.78 | 9.47 | 94.16 | 3.13 | 12.29 | 96.89 | 3.35 | 16.60 | 2.03 M

###  IV-C Baselines

The baseline systems used for performance comparison are Optimally Modified
Log Spectral Amplitude (OMLSA) method [24], attention-wave-U-net [25],
Attention-DCUNet [26], and TSTNN [27]. The setup of the baseline systems are
detailed as below:

  * •

OMLSA: A statistical-based noise reduction algorithm.

  * •

Attention-wave-U-net: Attention-wave-U-net is an end-to-end speech enhancement
model in the time-domain, which contains 12 trainable blocks and is trained on
randomly-sampled audio excerpts using Adam optimizer, with learning rate =
$10^{-4}$ and batch size of 16. We use $F=24$ filters for convolution in first
layer of network, downsampling block filters of size 15 and upsampling block
filters of size 5 as in [28].

  * •

Attention-DCUNet: Attention-DCUNet takes RI-spectrograms as input and output,
and applies joint time-frequency loss to train the model. The attention-DCUnet
has 20 convolutional layers and applies STFT with a 64 ms sized Hann window
and 16 ms hop length. We set learning rate to $10^{-4}$ and decay it by 0.5
when the validation score increases.

  * •

TSTNN: TSTNN is a time-domain speech enhancement model, which takes s four
stacked two-stage Transformer blocks to efficiently extract local and global
information from the encoder output stage by stage. The TSTNN is trained for
100 epochs and optimized by Adam. We use the gradient clipping with maximum
L2-norm of 5 to avoid gradient explosion. For learning rate, we use the
dynamic strategies during the training stage [18].

###  IV-D Evaluation Metrics

The following three metrics are used to evaluate M2BSE-Net and state-of-the-
art competitors. All metrics are better if higher.

  * •

PESQ: Perceptual evaluation of speech quality (from $-0.5$ to $4.5$) [29].

  * •

STOI: Short-time objective intelligibility measure (from $0$ to $100(\%)$)
[30].

  * •

SSNR: Segmental SNR [31].

.

##  V Results and Analysis

###  V-A Model Comparison

Comprehensive comparison among alternative models are shown Table I, in terms
of STOI, PESQ, and SSNR, where the numbers represent the averages over the
test set in each condition. The best scores in each case are highlighted by
boldface.

We firstly compare the OMLSA with other 4 models. As shown in Table I, the
OMLSA achieves about $2.25\%$ to $4.43\%$ STOI improvements, $0.17$ to $0.33$
PESQ improvements, and $3.01$dB to $7.24$dB SSNR improvements over unprocessed
mixtures. Going from OMLSA to attention-wave-U-net substantially improves the
3 metrics. This result is consistent with the finding in [32]. Even OMLSA
enhance noisy speech by minimizing the difference between the clean speech and
the estimated clean speech, which is the most effective algorithm for
traditional monaural speech enhancement [33], ], the OMLSA unable to track a
target speaker in a complex acoustic environment. In contrast, the other 4
models are shown their reliability of performance and robustness in different
noise types and SNR levels.

Unlike the traditional monaural speech enhancement, the two attention based
deep learning models (i.e. attention-wave-U-net and attention-DCUNet)
formulate the speech enhancement as supervised learning and utilizes attention
for improving the network performance. The two deep learning based models, in
which the discriminative patterns within speech or noise signals are learned
from training data, is more advantageous for modelling target speech. It is
worth noting that attention-DCUNet estimates clean RI-spectrograms directly
from noisy speech. As shown in Table I, although a similar performance is
obtained by attention-wave-U-net and attention-DCUNet, attention-DCUNet
generalizes better than attention-wave-U-net.

In addition, the TSTNN is designed to use two stage Transformer block to
efficiently extracts both local and global contextual information for long-
range speech sequences. Although TSTNN is an end-to-end speech enhancement
model in the time domain, it obtains consistently better performance and shows
a more robust and better estimation than attention-DCUNet. This further
demonstrates the effectiveness of Transformer for tracking a target speaker by
leveraging long-term contexts. The proposed U-Former consistently outperforms
attention-wave-U-net, attention-DCUNet, and TSTNN in all conditions. Take, for
example the $-5$ dB SNR case. The proposed U-Former improves STOI by $1.92\%$,
PESQ by $0.08$, SSNR by $0.27$ dB over TSTNN. Figure 4 shows the visualization
of OMLSA, Attention-wave-u-net, Attention-DCUNet, TSTNN, and U-Former
enhancement in $0$ dB case.

(a) Noisy Spectrum

(b) Enhanced Spectrum (OMLSA)

(c) Enhanced Spectrum (Attention-wave-u-net)

(d) Enhanced Spectrum (Attention-DCUNet)

(e) Enhanced Spectrum (TSTNN)

(f) Enhanced Spectrum (U-Former)

Figure 4: Example of input and enhanced spectrum from an example speech utterance. TABLE II: Evaluation of MHSA and MHCA for U-Former  Test SNR | -5 dB | 0 dB | 5 dB | 10 dB
---|---|---|---|---
Metric | STOI(%) | PESQ | STOI(%) | PESQ | STOI(%) | PESQ | STOI(%) | PESQ
U-Former-w/o-MHCA&MHSA | 74.54 | 2.03 | 80.34 | 2.39 | 83.35 | 2.74 | 86.49 | 2.98
U-Former-w/o-MHSA | 79.31 | 2.37 | 86.79 | 2.65 | 93.09 | 3.06 | 95.37 | 3.26
U-Former-w/o-MHCA | 80.45 | 2.42 | 86.81 | 2.68 | 93.25 | 3.09 | 95.98 | 3.29
U-Former | 85.48 | 2.46 | 91.69 | 2.78 | 94.16 | 3.13 | 96.89 | 3.35
TABLE III: Comparison of different loss functions of U-Former.

Test SNR | -5 dB | 0 dB | 5 dB | 10 dB
---|---|---|---|---
Metric |  | STOI (%) | PESQ | SSNR (dB) | STOI (%) | PESQ | SSNR (dB) | STOI (%) | PESQ | SSNR (dB) | STOI (%) | PESQ | SSNR (dB)
Mixture |  | 57.71 | 1.37 | -5.04 | 71.02 | 1.73 | -0.05 | 82.53 | 2.03 | 4.93 | 90.41 | 2.42 | 9.79
U-Former-T | MAE | 83.44 | 2.05 | 6.67 | 89.94 | 2.52 | 9.14 | 93.52 | 2.90 | 11.90 | 95.89 | 3.10 | 16.56
MSE | 83.61 | 2.14 | 6.79 | 90.01 | 2.57 | 9.18 | 93.61 | 3.00 | 12.03 | 96.01 | 3.13 | 16.63
U-Former-RI | MAE | 85.27 | 2.21 | 7.72 | 91.35 | 2.66 | 9.39 | 94.13 | 2.94 | 12.38 | 96.71 | 3.14 | 17.12
MSE | 83.43 | 2.29 | 7.40 | 90.06 | 2.73 | 8.94 | 93.86 | 3.05 | 12.09 | 96.52 | 3.20 | 17.00
U-Former-TF1 | MAE (for time-domain loss) | 85.48 | 2.46 | 7.24 | 91.69 | 2.78 | 9.47 | 94.16 | 3.13 | 12.29 | 96.89 | 3.35 | 16.60
MSE (for time-domain loss) | 83.57 | 2.46 | 6.79 | 90.82 | 2.71 | 9.14 | 94.00 | 3.04 | 12.17 | 96.03 | 3.13 | 16.29
U-Former-TF2 | MAE (for time-domain loss) | 85.36 | 2.45 | 6.96 | 91.75 | 2.80 | 9.25 | 94.16 | 3.15 | 12.06 | 96.64 | 3.26 | 16.42
MSE (for time-domain loss) | 83.62 | 2.46 | 6.63 | 90.96 | 2.64 | 9.08 | 93.88 | 2.98 | 11.94 | 96.15 | 3.11 | 16.38

###  V-B Evaluation of MHSA and MHCA

The proposed U-Former takes MHSA and MHCA for leveraging long-term
correlations and dependencies and filtering out uncorrelated features. In this
study, we remove the MHSA module, MHCA module, and both multi-head attention
modules of U-Former respectively, and compare the performance between these
three “incomplete U-Former” and the “complete U-Former”.

From From Table II, we can conclude that the existence of the MHSA module and
the MHCA module does promote the U-Former performance. Take, for example the
$0$ dB case, the MHSA and MHCA improve $10.35\%$ and $0.39$ on STOI and PESQ
respectively. Furthermore, “U-Former-w/o-MHCA” performs better than
“U-Former-w/o-MHSA” in all SNR cases in terms of STOI and PESQ. Take, for
example the $-5$ dB SNR case, the “U-Former-w/o-MHCA” improves STOI by
$1.14\%$, and PESQ by $0.05$ over “U-Former-w/o-MHSA”

###  V-C Evaluation of Loss Function

The proposed U-Former takes joint time-frequency loss as training objective.
To explore the effectiveness of joint time-frequency loss, we train the
U-Former with different loss functions. All the time domain models are
compared for both the MAE loss and the MSE loss training. The corresponding
abbreviated names for our models trained using different loss functions are
U-Former-T for using loss function on time domain samples, U-Former-T for
using a loss function on both thr real and the imaginary part of STFT, and
U-Former-TF for using a loss on time domain and STFT magnitudes. In
particular, U-Former-TF1 denotes the frequency loss defined on L1 norm and
U-Former-TF2 denotes the frequency loss defined on L2 norm. Table III shows
the average results at $-5$ dB, 0 dB, 5 dB and 10 dB. In addition, the
U-Former-TF1 and U-Former-TF2 using MAE and MSE based time-domian loss are
compared in this table.

From Table III, we can firstly conclude that the existence of the joint time-
frequency loss does promote the network performance. What is more, we observe
that the models trained with a time-domain loss perform better using MSE. The
U-Former-T, U-former-TF1 and U-former-TF2 have better STOI, PESQ and SSNR
scores with MAE based time-domain loss. In addition, the models trained with
with a frequency-domain loss perform better using MAE. The U-former-RI have
better STOI and SSNR scores with MSE based frequency-domian loss but
significantly worse PESQ. Finally, U-former-TF1 and U-former-TF2 have similar
STOI and PESQ scores but U-former-TF1 is consistently better in terms of SSNR.

##  VI Conclusion

This paper proposed a U-Former for monaural speech enhancement network with
MHSA and MHCA. The model adopts U-Net architecture, which applies multi-head
self-attention as bottleneck, multi-head cross-attention as skip-connection,
and a novel time-frequency loss. According to the experiment results, both
attention mechanisms, and time-frequency loss improve performance of speech
enhancement systems by involving U-Net architecture. Through experiments on
two datasets, we show the superiority of the proposed method over prior arts.

In the near future, we plan to speed up our model and apply it to low-latency
applications. Another important direction is to study how different training
targets will influence the proposed method. Finally, we plan to extend the
proposed method to various audio-related tasks such as dereverberation.

## References

  * [1] S. Boll, “Suppression of acoustic noise in speech using spectral subtraction,” _IEEE Transactions on acoustics, speech, and signal processing_ , vol. 27, no. 2, pp. 113–120, 1979.
  * [2] J. Lim and A. Oppenheim, “All-pole modeling of degraded speech,” _IEEE Transactions on Acoustics, Speech, and Signal Processing_ , vol. 26, no. 3, pp. 197–210, 1978.
  * [3] P. C. Loizou, _Speech enhancement: theory and practice, second ed_. CRC press, 2013.
  * [4] N. Mohammadiha, P. Smaragdis, and A. Leijon, “Supervised and unsupervised speech enhancement using nonnegative matrix factorization,” _IEEE Transactions on Audio, Speech, and Language Processing_ , vol. 21, no. 10, pp. 2140–2151, 2013.
  * [5] X. Lu, Y. Tsao, S. Matsuda, and C. Hori, “Speech enhancement based on deep denoising autoencoder.” in _Interspeech_ , vol. 2013, 2013, pp. 436–440.
  * [6] Y. Xu, J. Du, L.-R. Dai, and C.-H. Lee, “A regression approach to speech enhancement based on deep neural networks,” _IEEE/ACM Transactions on Audio, Speech, and Language Processing_ , vol. 23, no. 1, pp. 7–19, 2014.
  * [7] S. R. Park and J. W. Lee, “A fully convolutional neural network for speech enhancement,” _Proc. Interspeech 2017_ , pp. 1993–1997, 2017.
  * [8] S. Pirhosseinloo and J. S. Brumberg, “Monaural speech enhancement with dilated convolutions.” in _INTERSPEECH_ , 2019, pp. 3143–3147.
  * [9] J. Chen and D. Wang, “Long short-term memory for speaker generalization in supervised speech separation,” _The Journal of the Acoustical Society of America_ , vol. 141, no. 6, pp. 4705–4714, 2017.
  * [10] S. Li, W. Li, C. Cook, C. Zhu, and Y. Gao, “Independently recurrent neural network (indrnn): Building a longer and deeper rnn,” in _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 2018, pp. 5457–5466.
  * [11] D. Rethage, J. Pons, and X. Serra, “A wavenet for speech denoising,” in _2018 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_. IEEE, 2018, pp. 5069–5073.
  * [12] S. Bai, J. Z. Kolter, and V. Koltun, “An empirical evaluation of generic convolutional and recurrent networks for sequence modeling,” _arXiv preprint arXiv:1803.01271_ , 2018.
  * [13] J. Kim, M. El-Khamy, and J. Lee, “T-gsa: Transformer with gaussian-weighted self-attention for speech enhancement,” in _ICASSP 2020-2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_. IEEE, 2020, pp. 6649–6653.
  * [14] J. Chen, Q. Mao, and D. Liu, “Dual-path transformer network: Direct context-aware modeling for end-to-end monaural speech separation,” _Interspeech_ , 2020.
  * [15] S. Khan, M. Naseer, M. Hayat, S. W. Zamir, F. S. Khan, and M. Shah, “Transformers in vision: A survey,” _arXiv preprint arXiv:2101.01169_ , 2021\.
  * [16] R. Gu, J. Wu, S.-X. Zhang, L. Chen, Y. Xu, M. Yu, D. Su, Y. Zou, and D. Yu, “End-to-end multi-channel speech separation,” _arXiv preprint arXiv:1905.06286_ , 2019.
  * [17] C. Tang, C. Luo, Z. Zhao, W. Xie, and W. Zeng, “Joint time-frequency and time domain learning for speech enhancement,” in _Proceedings of the Twenty-Ninth International Conference on International Joint Conferences on Artificial Intelligence_ , 2021, pp. 3816–3822.
  * [18] A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, Ł. Kaiser, and I. Polosukhin, “Attention is all you need,” in _Advances in neural information processing systems_ , 2017, pp. 5998–6008.
  * [19] H. Wang, Y. Zhu, B. Green, H. Adam, A. Yuille, and L.-C. Chen, “Axial-deeplab: Stand-alone axial-attention for panoptic segmentation,” in _European Conference on Computer Vision_. Springer, 2020, pp. 108–126.
  * [20] J. Ho, N. Kalchbrenner, D. Weissenborn, and T. Salimans, “Axial attention in multidimensional transformers,” _arXiv preprint arXiv:1912.12180_ , 2019\.
  * [21] V. Panayotov, G. Chen, D. Povey, and S. Khudanpur, “Librispeech: an asr corpus based on public domain audio books,” in _2015 IEEE international conference on acoustics, speech and signal processing (ICASSP)_. IEEE, 2015, pp. 5206–5210.
  * [22] J. Thiemann, N. Ito, and E. Vincent, “Demand: a collection of multi-channel recordings of acoustic noise in diverse environments,” in _Proc. Meetings Acoust_ , 2013, pp. 1–6.
  * [23] A. Pandey and D. Wang, “Densely connected neural network with dilated convolutions for real-time speech enhancement in the time domain,” in _ICASSP 2020-2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_. IEEE, 2020, pp. 6629–6633.
  * [24] I. Cohen and B. Berdugo, “Speech enhancement for non-stationary noise environments,” _Signal processing_ , vol. 81, no. 11, pp. 2403–2418, 2001\.
  * [25] R. Giri, U. Isik, and A. Krishnaswamy, “Attention wave-u-net for speech enhancement,” in _2019 IEEE Workshop on Applications of Signal Processing to Audio and Acoustics (WASPAA)_. IEEE, 2019, pp. 249–253.
  * [26] S. Zhao, T. H. Nguyen, and B. Ma, “Monaural speech enhancement with complex convolutional block attention module and joint time frequency losses,” in _ICASSP 2021-2021 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_. IEEE, 2021, pp. 6648–6652.
  * [27] K. Wang, B. He, and W.-P. Zhu, “Tstnn: Two-stage transformer based neural network for speech enhancement in the time domain,” in _ICASSP 2021-2021 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_. IEEE, 2021, pp. 7098–7102.
  * [28] D. Stoller, S. Ewert, and S. Dixon, “Wave-u-net: A multi-scale neural network for end-to-end audio source separation,” _arXiv preprint arXiv:1806.03185_ , 2018.
  * [29] A. W. Rix, J. G. Beerends, M. P. Hollier, and A. P. Hekstra, “Perceptual evaluation of speech quality (pesq)-a new method for speech quality assessment of telephone networks and codecs,” in _2001 IEEE international conference on acoustics, speech, and signal processing. Proceedings (Cat. No. 01CH37221)_ , vol. 2. IEEE, 2001, pp. 749–752.
  * [30] C. H. Taal, R. C. Hendriks, R. Heusdens, and J. Jensen, “An algorithm for intelligibility prediction of time–frequency weighted noisy speech,” _IEEE Transactions on Audio, Speech, and Language Processing_ , vol. 19, no. 7, pp. 2125–2136, 2011.
  * [31] P. Mermelstein, “Evaluation of a segmental snr measure as an indicator of the quality of adpcm coded speech,” _The Journal of the Acoustical Society of America_ , vol. 66, no. 6, pp. 1664–1667, 1979.
  * [32] Y. Xu, J. Du, L.-R. Dai, and C.-H. Lee, “An experimental study on speech enhancement based on deep neural networks,” _IEEE Signal processing letters_ , vol. 21, no. 1, pp. 65–68, 2013.
  * [33] E. Principi, S. Cifani, R. Rotili, S. Squartini, and F. Piazza, “Comparative evaluation of single-channel mmse-based noise reduction schemes for speech recognition,” _Journal of Electrical and Computer Engineering_ , vol. 2010, 2010.


# New Eigenvalue Bound for the Fractional Chromatic Number

Krystal Guo Korteweg-de Vries Institute for Mathematics, University of
Amsterdam, Amsterdam, the Netherlands<EMAIL_ADDRESS>Sam Spiro Dept. of
Mathematics, Rutgers University, Piscataway NJ, United States of America.
<EMAIL_ADDRESS>This material is based upon work supported by
the National Science Foundation Mathematical Sciences Postdoctoral Research
Fellowship under Grant No. DMS-2202730.

###### Abstract

Given a graph $G$, we let $s^{+}(G)$ denote the sum of the squares of the
positive eigenvalues of the adjacency matrix of $G$, and we similarly define
$s^{-}(G)$. We prove that

$\chi_{f}(G)\geq
1+\max\left\\{\frac{s^{+}(G)}{s^{-}(G)},\frac{s^{-}(G)}{s^{+}(G)}\right\\}$

and thus strengthen a result of Ando and Lin, who showed the same lower bound
for the chromatic number $\chi(G)$. We in fact show a stronger result wherein
we give a bound using the eigenvalues of $G$ and $H$ whenever $G$ has a
homomorphism to an edge-transitive graph $H$. Our proof utilizes ideas
motivated by association schemes.

Keywords: graph eigenvalues, fractional chromatic number, spectral graph
theory

Mathematics Subject Classifications 2020: 05C50, 05C72

##  1 Introduction

Given a graph $G$, we say that $\lambda$ is an eigenvalue of $G$ if it is an
eigenvalue for the adjacency matrix of $G$. There is a long history of using
the eigenvalues of a graph $G$ to bound its chromatic number. Early work on
chromatic numbers and graph spectra includes a result of Wilf [22] which gives
an upper bound on $\chi(G)$ using the largest eigenvalue of $G$. Recent
variants of this upper bound have been proven for digraphs [16], hypergraphs
[5], and simplicial complexes [13]. A spectral lower bound for $\chi(G)$ was
established by Hoffman [14] in terms of the largest and smallest eigenvalues
of $G$ (see (1) below), and it is related to an upper bound for the
independence number in the setting of association schemes by Delsarte [7,
Section 3.3]. Many extensions of these results have been established; for
example, see [4, 17, 21].

Using the numbers of positive and negative eigenvalues, Cvektović [6] proved a
lower bound for $\chi(G)$ (see also [8]). In a similar spirit, Ando and Lin
[1] proved a lower bound for $\chi(G)$ in terms of the squares of the positive
and negative eigenvalues of $G$, which will be of particular importance to
this work. To formally state their result, we let $\lambda_{i}$ be the $i$th
largest eigenvalue of a graph $G$ and define

$s^{+}(G)=\sum_{i:\lambda_{i}>0}\lambda_{i}^{2},\qquad
s^{-}(G)=\sum_{j:\lambda_{j}<0}\lambda_{j}^{2}.$

When the context is clear, we will omit $G$ from this notation. The quantities
$s^{+}$ and $s^{-}$ were first considered by Wocjan and Elphick [23]. They
conjectured the following, which was proven by Ando and Lin [1].

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

For any graph $G$, we have

$\chi(G)\geq
1+\max\left\\{\frac{s^{+}(G)}{s^{-}(G)},\frac{s^{-}(G)}{s^{+}(G)}\right\\}.$

Theorem 1.1 has inspired a large amount of follow up work, including
extensions to quantum chromatic numbers [9], quantum graphs [10], and similar
bounds for $p$-norms of certain classes of matrices [15].

In this paper, we show that Theorem 1.1 also holds when $\chi(G)$ is replaced
by the fractional chromatic number $\chi_{f}(G)$ (whose definition is recalled
below). We note that Anekstein, Elphick, and Wocjan [2] asked whether Theorem
1.1 can be strengthened by replacing the chromatic number $\chi(G)$ with the
vector chromatic number $\chi_{c}(G)$, which satisfies the inequality
$\chi(G)\geq\chi_{c}(G)$. Our result can be viewed as the first progress
towards this question;, it is well-known that these various chromatic numbers
satisfy the inequalities $\chi(G)\geq\chi_{f}(G)\geq\chi_{c}(G)$, see for
example [19].

Recall that a homomorphism between two graphs $G,H$ is a map $\phi:V(G)\to
V(H)$ such that $\phi(u)\phi(v)\in E(H)$ whenever $uv\in E(G)$. We define the
Kneser graph $K_{n;k}$ to be the graph whose vertices are the $k$-subsets of
an $n$-element set, where two $k$-subsets are adjacent if and only if they are
disjoint. The fractional chromatic number of a graph $G$ is then defined by

$\chi_{f}(G)=\inf_{(n,k)}\frac{n}{k},$

where the infimum runs over all pairs $(n,k)$ such that there exist a
homomorphism from $G$ to $K_{n;k}$. We note that one can equivalently define
the fractional chromatic number as the optimum of the linear programming
relaxation for an integer programming formulation of chromatic number. For
more background on the fractional chromatic number, we refer to [18]. With
$\chi_{f}(G)$ defined we can now state our strengthening of Theorem 1.1.

######  Theorem 1.2.

For any graph $G$, we have

$\chi_{f}(G)\geq
1+\max\left\\{\frac{s^{+}(G)}{s^{-}(G)},\frac{s^{-}(G)}{s^{+}(G)}\right\\}.$

Our proof of Theorem 1.2 uses ideas motivated by association schemes. By
generalizing our approach, we also prove the following result, which turns out
to be somewhat stronger than Theorem 1.2.

######  Theorem 1.3.

If there exists a homomorphism from a graph $G$ to an edge-transitive graph
$H$, then

$\frac{\lambda_{\max}(H)}{|\lambda_{\min}(H)|}\geq\max\left\\{\frac{s^{+}(G)}{s^{-}(G)},\frac{s^{-}(G)}{s^{+}(G)}\right\\},$

where $\lambda_{\max}(H),\lambda_{\min}(H)$ are the largest and smallest
eigenvalue of the adjacency matrix of $H$, respectively.

As an aside, Theorem 1.3 can be used to show the non-existence of
homomorphisms between graphs. For example, it shows that the Petersen graph
$P$ has no homomorphism into $C_{7}$, since
$\nicefrac{{s^{+}(P)}}{{s^{-}(P)}}=\nicefrac{{8}}{{7}}=1.\overline{142857}$
and $\nicefrac{{\lambda_{\max}(C_{7})}}{{|\lambda_{\min}(C_{7})|}}=1.109916$,
correct to the first six decimals.

###  1.1 Tightness and comparisons with other bounds

Here we briefly discuss examples showing that our bounds are tight, as well as
how our bounds compare to other known lower bounds for $\chi_{f}(G)$

Theorem 1.1 (and hence the stronger Theorems 1.2 and 1.3) is tight for a
number of examples. The complete graph $K_{n}$ has $s^{+}(K_{n})=(n-1)^{2}$
and $s^{-}(K_{n})=n-1$, so Theorem 1.1 holds with equality. For a bipartite
graph with $m$ edges, we have $s^{+}=s^{-}=m$ and the bound also holds with
equality here. A less trivial example includes the Paley graph $P_{9}$ on $9$
vertices (see Figure 1), which has chromatic number 3 and spectrum
$\\{4^{(1)},2^{(4)},(-2)^{(4)}\\}$ (where the multiplicities are shown in
superscript). We note that the clique and Paley graph examples can also be
shown through Theorem 1.3 by considering the homomorphisms from these graphs
to themselves.

Figure 1: From left to right: Graphs $W_{5}$ and $H_{5}$, which are witnesses
to the comparability of Theorem 1.2 with the clique number and with the
Hoffman bound, respectively, and $P_{9}$ the Paley graph of order $9$.

In addition to these examples, there are several other ways that one can view
Theorems 1.2 and 1.3 as being tight. For example, Theorem 1.3 can not be
strengthened to hold whenever $G$ has a homomorphism to an $H$ which is
vertex-transitive. A counterexample to such a statement follows by considering
$G=K_{3}$ and $H=\overline{C_{6}}$ (which is vertex-transitive but not edge-
transitive). As $\overline{C_{6}}$ contains a triangle, there exists a
homomorphism from $K_{3}$ to $\overline{C_{6}}$, but

$\frac{3}{2}=\frac{\lambda_{\max}(\overline{C_{6}})}{|\lambda_{\min}(\overline{C_{6}})|}<1+\max\left\\{\frac{s^{+}(K_{3})}{s^{-}(K_{3})},\frac{s^{-}(K_{3})}{s^{+}(K_{3})}\right\\}=3,$

showing that an extension of Theorem 1.3 to vertex-transitive graphs can not
hold.

We next consider how Theorem 1.2 compares with other well known lower bounds
for $\chi_{f}(G)$. Unlike the chromatic number, relatively few spectral bounds
are known for $\chi_{f}(G)$. One such bound is Hoffman’s bound, which says

$\chi_{f}(G)\geq 1+\frac{\lambda_{\max}(G)}{|\lambda_{\min}(G)|}.$ (1)

In general the bounds of Theorem 1.2 and (1) are incomparable. For example,
(1) gives $\chi_{f}(G)\geq\nicefrac{{5}}{{2}}$ when $G$ is the Petersen graph
(which is tight), while Theorem 1.2 only gives
$\chi_{f}(G)\geq\nicefrac{{11}}{{3}}$. On the other hand, a small computation
in SageMath [20] gives that amongst the $11,855$ graphs on $5,6,7,8$ vertices
which are connected and non-bipartite, there are $11,014$ graphs $G$ for which
Theorem 1.2 gives a better bound on the fractional chromatic number than (1).
A concrete example is $H_{5}$, shown in the middle of Figure 1, which has

$1+\max\left\\{\frac{s^{+}(H_{5})}{s^{-}(H_{5})},\frac{s^{-}(H_{5})}{s^{+}(H_{5})}\right\\}\approx
2.331454,\qquad 1+\frac{\lambda_{\max}(H_{5})}{|\lambda_{\min}(H_{5})|}\approx
2.291859,$

rounded to the sixth digit. Thus Theorem 1.2 and (1) are incomparable.

Another well known bound is $\chi_{f}(G)\geq\omega(G)$, where $\omega(G)$ is
the size of the largest clique of $G$. Out bound is also incomparable with
$\omega(G)$: the wheel $W_{5}$ (see left side of Figure 1) has

$3=\omega(W_{5})>1+\max\left\\{\frac{s^{+}}{s^{-}},\frac{s^{-}}{s^{+}}\right\\}\approx
2.725877$

and the $5$-cycle $C_{5}$ has

$2=\omega(C_{5})<1+\max\left\\{\frac{s^{+}}{s^{-}},\frac{s^{-}}{s^{+}}\right\\}\approx
2.099106.$

###  1.2 Organization and notation

We prove Theorem 1.3 in Section 2 assuming a technical lemma, and then show
how this implies Theorem 1.2. In Section 3 we prove this technical lemma,
thereby completing the proof. We conclude with some open problems in Section
4.

Notation. Given real matrices $X=(x_{i,j})_{i,j}$ and $Y=(y_{i,j})_{i,j}$, we
let $\operatorname{sum}(X)=\sum_{i,j}x_{i,j}$. We denote the Schur product
with $\circ$ and recall that $X\circ Y=(x_{i,j}y_{i,j})_{i,j}$. We use the
following standard inner product for real $m\times n$ matrices $X$ and $Y$:

$\langle X,Y\rangle:=\operatorname{tr}(XY^{T})=\operatorname{sum}(X\circ Y)$

where the second equality is a standard property of matrix multiplication. We
will sometimes write $\|X\|^{2}$ for $\langle X,X\rangle$. Note that if $X$ is
symmetric, then $\|X\|^{2}$ is equal to the sum of the squares of the
eigenvalues of $X$. Throughout $J$ denotes the all 1’s matrix.

##  2 Partitions into fibres: proof of main results

Before going into the details of the proof, we briefly overview the ideas of
the argument. Consider the spectral decomposition of the adjacency matrix
$A=\sum\mu_{i}E_{i}$, where $E_{i}$ is the idempotent projector onto the
$\mu_{i}$-eigenspace. We may write $A=X-Y$ where

$X=\sum_{i:\mu_{i}>0}\mu_{i}E_{i}\,\text{ and
}\,Y=-\sum_{i:\mu_{i}<0}\mu_{i}E_{i}.$

We observe that $X$ and $Y$ are both positive semidefinite matrices and that
$\|X\|^{2}=s^{+},\|Y\|^{2}=s^{-}$. Thus proving Theorem 1.3 is equivalent to
showing

$\|X\|^{2}\leq\frac{\lambda_{\max}(H)}{|\lambda_{\min}(H)|}\|Y\|^{2}\text{\ \
\ and\ \ \
}\|Y\|^{2}\leq\frac{\lambda_{\max}(H)}{|\lambda_{\min}(H)|}\|X\|^{2}$

whenever there exists a homomorphism $\phi:V(G)\to V(H)$. Given such a map
$\phi$, we can naturally partition $V(G)$ into the sets $\phi^{-1}(u)$ with
$u\in V(H)$. With this in mind, we make the following definition.

######  Definition 1.

Given a graph $G$, we say that $\bigsqcup_{u\in V(H)}V_{u}$ is an
$H$-partition of $G$ if the sets $V_{u}\subseteq V(G)$ partition $V(G)$. Given
an $H$-partition, if $X$ is a matrix whose rows and columns are indexed by
$V(G)$, we write $X_{[u,v]}$ to be the submatrix consisting of the rows
indexed by $V_{u}$ and the columns indexed by $V_{v}$.

We now state our main lemma.

######  Lemma 2.1.

Let $G$ be a graph with an $H$-partition $\bigsqcup_{u\in V(H)}V_{u}$, and let
$X$ be a PSD matrix with rows and columns indexed by $V(G)$. If $H$ is vertex
and edge-transitive, then

$\|X\|^{2}\leq\left(1+\frac{\lambda_{\max}(H)}{|\lambda_{\min}(H)|}\right)\sum_{(u,v):u,v\in
V(H),\\{u,v\\}\notin E(H)}\|X_{[u,v]}\|^{2}.$

For the moment we postpone the proof of Lemma 2.1 and show how it implies
Theorem 1.2. We note that our approach for the rest of this section will
closely follow that of Ando and Lin [1].

######  Lemma 2.2.

Let $G$ be a graph with an $H$-partition $\bigsqcup_{u\in V(H)}V_{u}$, and let
$X,Y$ be real PSD matrices with rows and columns indexed by $V(G)$. If $H$ is
vertex and edge-transitive, and if $XY=0$ and $X_{[u,v]}=Y_{[u,v]}$ whenever
$\\{u,v\\}\notin E(H)$, then

$\|X\|^{2}\leq\frac{\lambda_{\max}(H)}{|\lambda_{\min}(H)|}\|Y\|^{2}.$

###### Proof.

For ease of notation, we omit writing that our sums are over all ordered pairs
$(u,v)$ with $u,v\in V(H)$. Let $X,Y$ be as in the hypothesis of the lemma.
Because $XY=0$, we have $\|X+Y\|^{2}=\|X-Y\|^{2}$, which by hypothesis on
$X,Y$ is equivalent to

$4\sum_{\\{u,v\\}\notin E(H)}\|X_{[u,v]}\|^{2}+\sum_{\\{u,v\\}\in
E(H)}\|X_{[u,v]}+Y_{[u,v]}\|^{2}=\sum_{\\{u,v\\}\in
E(H)}\|X_{[u,v]}-Y_{[u,v]}\|^{2}.$

This is equivalent to

$\displaystyle 4\sum_{\\{u,v\\}\notin E(H)}\|X_{[u,v]}\|^{2}$
$\displaystyle=\sum_{\\{u,v\\}\in
E(H)}\operatorname{tr}((X_{[u,v]}-Y_{[u,v]})(X_{[u,v]}-Y_{[u,v]})^{T})-\operatorname{tr}((X_{[u,v]}+Y_{[u,v]})(X_{[u,v]}+Y_{[u,v]})^{T})$
$\displaystyle=-4\sum_{\\{u,v\\}\in
E(H)}\operatorname{tr}(X_{[u,v]}Y_{[u,v]}^{T}).$

Let $d=\sum_{\\{u,v\\}\notin E(H)}\|X_{[u,v]}\|^{2}$. The equality above
together with two applications of Cauchy-Schwarz gives

$\displaystyle d$ $\displaystyle=-\sum_{\\{u,v\\}\in
E(H)}\operatorname{tr}(X_{[u,v]}Y_{[u,v]}^{T})$
$\displaystyle\leq\sum_{\\{u,v\\}\in E(H)}\|X_{[u,v]}\|\cdot\|Y_{[u,v]}\|$
$\displaystyle\leq\left(\sum_{\\{u,v\\}\in
E(H)}\|X_{[u,v]}\|^{2}\right)^{1/2}\left(\sum_{\\{u,v\\}\in
E(H)}\|Y_{[u,v]}\|^{2}\right)^{1/2}$
$\displaystyle=(\|X\|^{2}-d)^{1/2}(\|Y\|^{2}-d)^{1/2}.$

Thus

$d^{2}\leq(\|X\|^{2}-d)(\|Y\|^{2}-d),$

which is equivalent to

$(\|X\|^{2}+\|Y\|^{2})d\leq\|X\|^{2}\|Y\|^{2}.$ (2)

By Lemma 2.1, we have

$\|X\|^{2}\leq\left(1+\frac{\lambda_{\max}(H)}{|\lambda_{\min}(H)|}\right)d.$

Combining this with (2) implies

$\|X\|^{2}+\|Y\|^{2}\leq\left(1+\frac{\lambda_{\max}(H)}{|\lambda_{\min}(H)|}\right)\|Y\|^{2},$

giving the desired result. ∎

We can now prove our main theorem, which we restate below.

###### Theorem 1.3.

If there exists a homomorphism from a graph $G$ to an edge-transitive graph
$H$, then

$\frac{\lambda_{\max}(H)}{|\lambda_{\min}(H)|}\geq\max\left\\{\frac{s^{+}(G)}{s^{-}(G)},\frac{s^{-}(G)}{s^{+}(G)}\right\\},$

where $\lambda_{\max}(H),\lambda_{\min}(H)$ are the largest and smallest
eigenvalue of the adjacency matrix of $H$, respectively.

###### Proof.

If $H$ is edge-transitive but not vertex-transitive, then $H$ is bipartite by
[12, Lemma 3.2.1]. The existence of a homomorphism $\phi:V(G)\to V(H)$ implies
that $G$ is also bipartite. Since the spectrum of bipartite graphs are
symmetric about $0$ on the real line, we have $s^{+}(G)=s^{-}(G)$ and
$\lambda_{\max}(H)=-\lambda_{\min}(H)$ and the result is trivial. Thus from
now on we may assume $H$ is both vertex and edge-transitive.

For each $u\in V(H)$, define $V_{u}=\phi^{-1}(u)$. Note that $\sqcup_{u}V_{u}$
is an $H$-partition. Consider the spectral decomposition of the adjacency
matrix $A=\sum\mu_{i}E_{i}$, where $E_{i}$ is the idempotent eigenprojector on
to the $\mu_{i}$-eigenspace. We write $A=X-Y$ where
$X=\sum_{i:\mu_{i}>0}\mu_{i}E_{i}$ and $Y=-\sum_{i:\mu_{i}<0}\mu_{i}E_{i}$.
Note that $X,Y$ are both real PSD matrices. Since $\phi$ is a homomorphism,
there are no edges between $V_{u}$ and $V_{v}$ in $G$ if $\\{u,v\\}\notin
E(H)$, so $A_{[u,v]}=0$ in this case. Since $A=X-Y$, this implies
$X_{[u,v]}=Y_{[u,v]}$ whenever $\\{u,v\\}\notin E(H)$. By Lemma 2.2 we
conclude

$\|X\|^{2}\leq\frac{\lambda_{\max}(H)}{|\lambda_{\min}(H)|}\|Y\|^{2}.$

Since $\|X\|^{2}=s^{+}(G)$ and $\|Y\|^{2}=s^{-}(G)$, this gives
$\frac{\lambda_{\max}(H)}{|\lambda_{\min}(H)|}\geq s^{+}(G)/s^{-}(G)$, and a
completely analogous proof gives the lower bound of $s^{-}(G)/s^{+}(G)$. ∎

We now show how Theorem 1.3 implies the analogous lower bound for the
fractional chromatic number.

###### Proof of Theorem 1.2.

We first claim that the Kneser graphs $K_{n;k}$ satisfy

$\frac{\lambda_{\max}(K_{n;k})}{|\lambda_{\min}(K_{n;k})|}=\frac{n}{k}-1.$

Indeed, it is well known that the eigenvalues of the Kneser graph $K_{n;k}$
can be written as

$(-1)^{i}\binom{n-k-i}{k-i}$

for all $0\leq i\leq k$. In particular,
$\lambda_{\max}(K_{n;k})=\binom{n-k}{k}$ and
$\lambda_{\min}=-\binom{n-k-1}{k-1}=-\frac{k}{n-k}\binom{n-k}{k}$, giving the
claim.

It is not difficult to see that the Kneser graphs are edge-transitive. Thus if
we let $\Phi(G)$ (respectively $\mathcal{K}(G)$) denote the set of edge-
transitive graphs (respectively kneser graphs) $H$ such that there exists a
homomorphism $\phi:V(G)\to V(H)$, then Theorem 1.3 implies

$\max\left\\{\frac{s^{+}(G)}{s^{-}(G)},\frac{s^{-}(G)}{s^{+}(G)}\right\\}\leq\inf_{H\in\Phi(G)}\ratio{H}\leq\inf_{K_{n;k}\in\mathcal{K}(G)}\ratio{K_{n;k}}=\inf_{K_{n;k}\in\mathcal{K}(G)}\frac{n}{k}-1=\chi_{f}(G)-1,$

giving the result. ∎

##  3 Proof of Lemma 2.1

We begin by establishing the key property we need about edge-transitive
graphs. For this we let $\operatorname{Aut}(H)$ denote the automorphism group
of $H$, i.e. the group of permutations on $V(H)$ which are graphs
isomorphisms. For ease of notation, we write $\\{u,v\\}$ as $uv$ and
$\\{\pi(u),\pi(v)\\}$ as $\pi(uv)$.

######  Lemma 3.1.

If $H$ is edge-transitive, then there exists a set of non-empty graphs
${\mathcal{H}}=\\{H_{1},\ldots,H_{n}\\}$ on $V(H)$ satisfying the following
properties:

  1. (a)

$H\in{\mathcal{H}}$;

  2. (b)

For every pair of distinct vertices $u,v\in V(H)$, there exists a unique $i$
with $uv\in V(H_{i})$;

  3. (c)

For every pair of edges $uv,xy\in E(H_{i})$, there exists
$\pi\in\operatorname{Aut}(H)$ with $\pi(uv)=xy$; and

  4. (d)

For all $i$, the restriction of any $\pi\in\operatorname{Aut}(H)$ to $H_{i}$
is an automorphism for $H_{i}$.

###### Proof.

We consider the action of $\operatorname{Aut}(H)$ on the set of unordered pair
of vertices of $H$ and we take $O_{1},\ldots O_{n}$ to be the orbits of this
action. Here, the orbit containing a pair $uv$ is
$O=\\{xy:\exists\pi\in\operatorname{Aut}(H),\ \pi(uv)=xy\\}$. Define $H_{i}$
to be the graph on $V(H)$ with edge set $O_{i}$ and let
${\mathcal{H}}:=\\{H_{1},\ldots,H_{m}\\}$.

Since $H$ is edge-transitive, $E(H)$ must be an orbit, so we have
$H\in{\mathcal{H}}$. Since the orbits partition the pairs of $V(H)$, we have
that the sets $\\{E(H_{i})\\}_{i=1}^{n}$ partition the pairs. Since orbit
partitions give rise to systems of blocks of imprimitivity, the other
properties follow. ∎

As an aside, it is known that if $H$ is a Kneser graph, then
$\operatorname{Aut}(H)$ is the set of permutations of $V(H)$ induced by
permuting the underlying ground set. Using this, one can verify that when $H$
is a Kneser graph, the family ${\mathcal{H}}$ from Lemma 3.1 is the set of
graphs known as the Johnson scheme, which is one of the most famous examples
of an association scheme. As such, one can view the family ${\mathcal{H}}$
from Lemma 3.1 as an analog of association schemes which exist for all edge-
transitive graphs. For more on association schemes we refer the reader to the
books [3, 11]. However, we emphasize that our approach, which was originally
motivated by association schemes, requires no knowledge of association schemes
to understand the details of our arguments.

For the rest of this section, we fix $H$ to be a vertex and edge-transitive
graph with ${\mathcal{H}}=\\{H_{1},\ldots,H_{n}\\}$ the family guaranteed by
Lemma 3.1, and without loss of generality we assume $H_{n}=H$. We let $A_{i}$
denote the adjacency matrix of $H_{i}$, and for notational convenience we let
$A_{0}$ denote the identity matrix of dimension $|V(H)|$. Note that Lemma
3.1(b) implies $\sum_{i=0}^{n}A_{i}=J$.

It turns out that to prove Lemma 2.1 for the matrix $X$, it suffices to prove
an analogous inequality for the matrix $Z$ defined by
$Z_{u,v}:=||X_{[u,v]}||^{2}$ for $u,v\in V(H)$. Note that $Z$ is non-negative,
and it will turn out to be PSD whenever $X$ is. The following lemma
establishes this analogous inequality for $Z$ in the special case that $Z$ is
in the span of the $A_{i}$ matrices.

######  Lemma 3.2.

Let $z_{0},z_{1},\ldots,z_{n}$ be real numbers such that
$Z:=\sum_{k=0}^{n}z_{i}A_{i}$ is a non-negative PSD matrix. Then

$\operatorname{sum}(Z)\leq\left(1+\frac{\lambda_{\max}(A_{n})}{|\lambda_{\min}(A_{n})|}\right)\operatorname{sum}((J-A_{n})\circ
Z).$

###### Proof.

Because the graphs $H_{i}$ are edge disjoint, $Z=\sum_{k=0}^{n}z_{i}A_{i}$
will be non-negative if and only if $z_{i}\geq 0$ for all $i$. By using
Raleigh quotients, we see
$\textbf{x}^{T}A_{i}\textbf{x}\leq\lambda_{\max}(A_{i})$ for any real vector x
and $0\leq i\leq n$. In particular, if x is the eigenvector of $A_{n}$
associated to $\lambda_{\min}(A_{n})$, then $Z$ being PSD implies

$0\leq\textbf{x}^{T}Z\textbf{x}=\sum_{i=0}^{n}z_{i}\cdot\textbf{x}^{T}A_{i}\textbf{x}\leq\sum_{i=0}^{n-1}z_{i}\lambda_{\max}(A_{i})+z_{n}\lambda_{\min}(A_{n}),$

where this last step implicitly used $z_{i}\geq 0$ for all $i$. Rearranging
gives

$\sum_{i=0}^{n-1}z_{i}\lambda_{\max}(A_{i})\geq-
z_{n}\lambda_{\min}(A_{n})=z_{n}|\lambda_{\min}(A_{n})|,$ (3)

where the last step used that the smallest eigenvalue of a real symmetric
matrix with 0 diagonals is non-negative.

Recall that we assumed $H=H_{n}$ is vertex-transitive, so by Lemma 3.1(d) each
of the $H_{i}$ graphs are vertex-transitive as well. In particular, each
$H_{i}$ is a graph on $|V(H)|$ vertices which is regular, and hence is regular
of degree $\lambda_{\max}(A_{i})$. This implies

$\operatorname{sum}(A_{i})=\lambda_{\max}(A_{i})|V(H)|$

for $i\geq 1$, and this expression trivially holds for $i=0$ as well. Using
this and (3) gives

$\displaystyle\left(1+\frac{\lambda_{\max}(A_{n})}{|\lambda_{\min}(A_{n})|}\right)\cdot\operatorname{sum}((J-A_{n})\circ
Z)$
$\displaystyle=\left(1+\frac{\lambda_{\max}(A_{n})}{|\lambda_{\min}(A_{n})|}\right)\cdot\sum_{i=0}^{n-1}z_{i}\operatorname{sum}(A_{i})$
$\displaystyle=\sum_{i=0}^{n-1}z_{i}\lambda_{\max}(A_{i})|V(H)|+\frac{\lambda_{\max}(A_{n})}{|\lambda_{\min}(A_{n})|}\cdot\sum_{i=0}^{n-1}z_{i}\lambda_{\max}(A_{i})|V(H)|$
$\displaystyle\geq\sum_{i=0}^{n-1}z_{i}\lambda_{\max}(A_{i})|V(H)|+\frac{\lambda_{\max}(A_{n})}{|\lambda_{\min}(A_{n})|}\cdot
z_{n}|\lambda_{\min}(A_{n})||V(H)|$
$\displaystyle=\sum_{i=0}^{n}z_{i}\lambda_{\max}(A_{n})|V(H)|=\operatorname{sum}(Z),$

proving the result. ∎

We can bootstrap Lemma 3.2 to prove an analogous result for matrices that are
not necessarily in the span of the $A_{i}$ matrices.

######  Lemma 3.3.

Let $Z$ be a non-negative PSD matrix indexed by $V(H)$. Then

$\operatorname{sum}{(Z)}\leq\left(1+\frac{\lambda_{\max}(A_{n})}{|\lambda_{\min}(A_{n})|}\right)\operatorname{sum}{((J-A_{n})\circ
Z)}.$

###### Proof.

For each permutation $\pi\in\operatorname{Aut}(H)$ of $V(H)$, let $P_{\pi}$
denote its corresponding permutation matrix indexed by $V(H)$. Define

${\mkern
2.0mu\overline{\mkern-2.0muZ}}=\frac{1}{|\operatorname{Aut}(H)|}\sum_{\pi\in\operatorname{Aut}(H)}P_{\pi}^{T}ZP_{\pi}.$

######  Claim 3.4.

We have $\operatorname{sum}({\mkern
2.0mu\overline{\mkern-2.0muZ}})=\operatorname{sum}(Z)$.

###### Proof.

Observe that $\operatorname{sum}{(P^{T}ZP)}=\operatorname{sum}{(Z)}$ for any
permutation matrix $P$ since permuting the terms in the sum does not change
the result. With this we see

$\operatorname{sum}({\mkern
2.0mu\overline{\mkern-2.0muZ}})=\frac{1}{|\operatorname{Aut}(H)|}\sum_{\pi\in\operatorname{Aut}(H)}\operatorname{sum}(P_{\pi}^{T}ZP_{\pi})=\operatorname{sum}(Z).$

∎

######  Claim 3.5.

We have $\operatorname{sum}((J-A_{n})\circ{\mkern
2.0mu\overline{\mkern-2.0muZ}})=\operatorname{sum}((J-A_{n})\circ Z)$.

###### Proof.

We first observe that for all $i\geq 0$ and $\pi\in\operatorname{Aut}(H)$, we
have $P_{\pi}^{T}A_{i}P_{\pi}=A_{i}$. This trivially holds for the identity
matrix $A_{0}$, and for $i\geq 1$ this statement is equivalent to saying that
each $\pi\in\operatorname{Aut}(H)$ is an automorphism of each $H_{i}$ which
follows from Lemma 3.1(d). In particular, since $\operatorname{Aut}(H)$ is
closed under inverses and $J=\sum_{i=0}^{n}A_{i}$, this observation implies

$P_{\pi^{-1}}^{T}(J-A_{n})P_{\pi^{-1}}=J-A_{n}$

for any $\pi\in\operatorname{Aut}(H)$.

Now, for any $\pi\in\operatorname{Aut}(H)$, we have

$\displaystyle\operatorname{sum}{((J-A_{n})\circ P_{\pi}^{T}ZP_{\pi})}$
$\displaystyle=\operatorname{tr}((J-A_{n})(P_{\pi}^{T}ZP_{\pi}))$
$\displaystyle=\operatorname{tr}(P_{\pi}(J-A_{n})P_{\pi}^{T}Z)$
$\displaystyle=\operatorname{tr}((J-A_{n})Z)$
$\displaystyle=\operatorname{sum}{((J-A_{n})\circ Z)},$

where the third equality used the observation made above and
$P_{\pi}^{T}=P_{\pi^{-1}}$. Summing this equality over all
$\pi\in\operatorname{Aut}(H)$ and dividing by $|\operatorname{Aut}(H)|$ gives
the desired result. ∎

######  Claim 3.6.

There exist real numbers $z_{i}$ such that ${\mkern
2.0mu\overline{\mkern-2.0muZ}}=\sum_{i=0}^{n}z_{i}A_{i}$.

###### Proof.

Let $u,v$ and $x,y$ be pairs of distinct vertices such that $uv,xy\in
E(H_{i})$ for some $i\geq 1$. By Lemma 3.1(c), there exists some
$\sigma\in\operatorname{Aut}(H)$ with $\sigma(uv)=xy$, and by definition we
have

${\mkern 2.0mu\overline{\mkern-2.0muZ}}_{x,y}=(P_{\sigma}^{T}{\mkern
2.0mu\overline{\mkern-2.0muZ}}P_{\sigma})_{u,v}=\left(\frac{1}{|\operatorname{Aut}(H)|}\sum_{\pi\in\operatorname{Aut}(H)}P_{\pi\circ\sigma}^{T}ZP_{\pi\circ\sigma}\right)_{u,v}=\left(\frac{1}{|\operatorname{Aut}(H)|}\sum_{\pi\in\operatorname{Aut}(H)}P_{\pi}^{T}ZP_{\pi}\right)_{u,v}={\mkern
2.0mu\overline{\mkern-2.0muZ}}_{u,v},$

where the third equality used that $\operatorname{Aut}(H)$ is a group so that
summing over $\pi$ or $\pi\circ\sigma^{-1}$ gives the same quantity.

The result above implies that for all $i\geq 1$ there exists some real number
$z_{i}$ such that $Z_{u,v}=z_{i}$ whenever $(A_{i})_{u,v}=1$. An analogous
argument using that $H$ is vertex-transitive implies that there exists a
$z_{0}$ with $Z_{u,u}=z_{0}$ for all $u$. These two facts give the claim. ∎

Note that ${\mkern 2.0mu\overline{\mkern-2.0muZ}}$, which is the sum of non-
negative PSD matrices, is also non-negative and PSD, so the previous claim
shows that Lemma 3.2 applies to ${\mkern 2.0mu\overline{\mkern-2.0muZ}}$.
Using this and the other two claims gives

$\operatorname{sum}(Z)=\operatorname{sum}({\mkern
2.0mu\overline{\mkern-2.0muZ}})\leq\left(1+\frac{\lambda_{\max}(A_{n})}{|\lambda_{\min}(A_{n})|}\right)\operatorname{sum}{((J-A_{n})\circ{\mkern
2.0mu\overline{\mkern-2.0muZ}})}=\left(1+\frac{\lambda_{\max}(A_{n})}{|\lambda_{\min}(A_{n})|}\right)\operatorname{sum}{((J-A_{n})\circ
Z)},$

proving the result.

∎

We now prove Lemma 2.1, which we restate below.

###### Lemma 2.1.

Let $G$ be a graph with an $H$-partition $\bigsqcup_{u\in V(H)}V_{u}$, and let
$X$ be a PSD matrix with rows and columns indexed by $V(G)$. If $H$ is vertex
and edge-transitive, then

$\|X\|^{2}\leq\left(1+\frac{\lambda_{\max}(H)}{|\lambda_{\min}(H)|}\right)\sum_{(u,v):u,v\in
V(H),\\{u,v\\}\notin E(H)}\|X_{[u,v]}\|^{2}.$

###### Proof.

Let $X$ be as in the statement of the lemma. Let $Z$ be the matrix with rows
and columns indexed by $V(H)$ such that

$Z_{u,v}=\|X_{[u,v]}\|^{2}=\operatorname{sum}((X\circ X)_{[u,v]}).$

######  Claim 3.7.

The matrix $Z$ is non-negative and PSD.

###### Proof.

Non-negativity is clear. To show that it is PSD, consider any vector z indexed
by $V(H)$. Define a vector x indexed by $V(G)$ with
$\textbf{x}_{w}=\textbf{z}_{u}$ whenever $w\in V_{u}$. Because $X$ is PSD,
$X\circ X$ is also PSD by the Schur product theorem. Thus

$0\leq\textbf{x}^{T}(X\circ X)\textbf{x}=\sum_{(u,v):u,v\in
V(H)}\textbf{z}_{u}\textbf{z}_{v}\operatorname{sum}((X\circ
X)_{[u,v]})=\textbf{z}^{T}Z\textbf{z}.$

As z was arbitrary, we conclude that $Z$ is PSD. ∎

From the definition of $Z$ we have

$\|X\|^{2}=\sum_{(u,v):u,v\in V(H)}\|X_{[u,v]}\|^{2}=\sum_{(u,v):u,v\in
V(H)}Z_{u,v}=\operatorname{sum}(Z).$

With this it suffices to prove

$\displaystyle\operatorname{sum}{Z}=$
$\displaystyle\leq\left(1+\frac{\lambda_{\max}(H)}{|\lambda_{\min}(H)|}\right)\sum_{(u,v):u,v\in
V(H),\\{u,v\\}\notin E(H)}Z_{u,v}$
$\displaystyle=\left(1+\frac{\lambda_{\max}(H)}{|\lambda_{\min}(H)|}\right)\operatorname{sum}{((J-A_{n})\circ
Z)}$

The inequality above follows immediately from our claim and Lemma 3.3, proving
the result. ∎

##  4 Further directions and open problems

As noted in the introduction, it was asked by Anekstein, Elphick, and Wocjan
[2] whether the lower bound of Ando and Lin [1] in Theorem 1.1 holds for the
vector chromatic number $\chi_{c}(G)$. In this paper we have taken the first
step towards this question by showing that it holds for the fractional
chromatic number $\chi_{f}(G)$. While it is unlikely that our methods can
bring us all the way down to proving bounds for $\chi_{c}(G)$, it is plausible
that one can strengthen our Theorems 1.2 and 1.3 by considering other variants
of the chromatic number defined in terms of homomorphisms.

To formalize this idea, we let $\Phi(G)$ denote the set of graphs $H$ such
that there exists a homomorphism from $G$ to $H$. Given a set of graphs
${\mathcal{H}}$, we define the ${\mathcal{H}}$-chromatic number  of a graph
$G$ by

$\chi_{\mathcal{H}}(G):=1+\inf_{H\in{\mathcal{H}}\cap\Phi(G)}\frac{\lambda_{\max}(H)}{|\lambda_{\min}(H)|}.$

For example, if ${\mathcal{H}}$ consists of the set of cliques then
$\chi_{\mathcal{H}}(G)$ is exactly the chromatic number, and if
${\mathcal{H}}$ is the set of Kneser graphs then $\chi_{\mathcal{H}}(G)$ is
the fractional chromatic number. Similarly Theorem 1.3 can be viewed as a
lower bound on $\chi_{{\mathcal{H}}}(G)$ when ${\mathcal{H}}$ is the set of
edge-transitive graphs. It would be of interest to study other bounds and
properties of $\chi_{{\mathcal{H}}}(G)$ for other families of graphs
${\mathcal{H}}$. In particular, we ask the following.

######  Question 4.1.

What is the largest family of graphs ${\mathcal{H}}$ such that for all graphs
$G$,

$\chi_{\mathcal{H}}(G)\geq
1+\max\left\\{\frac{s^{+}(G)}{s^{-}(G)},\frac{s^{-}(G)}{s^{+}(G)}\right\\}.$

For example, Theorem 1.3 shows this holds when ${\mathcal{H}}$ consists of all
$H$ which are edge-transitive. This result trivially extends to all $H$ for
which there exists an edge-transitive graph $H^{\prime}\in\Phi(H)$ such that
$\lambda_{\max}(H)/|\lambda_{\min}(H)|\geq\lambda_{\max}(H^{\prime})/|\lambda_{\min}(H^{\prime})|$,
so for example, this applies to all $H$ which are bipartite. As discussed in
Subsection 1.1, by considering $H=\overline{C_{6}}$, we know that Question 4.1
can not hold for any ${\mathcal{H}}$ containing all vertex-transitive graphs.

There are other spectral problems where our approach may be fruitful. In
particular, Elphick and Wocjan [8] proved the following inertial bound for
$\chi(G)$:

$\chi(G)\geq 1+\max\left\\{\frac{n^{+}}{n^{-}},\frac{n^{-}}{n^{+}}\right\\},$

where $n^{+},n^{-}$ denote the numbers positive and negative eigenvalues of
$G$, respectively. They conjectured that this same lower bound also holds for
$\chi_{f}(G)$, and it is plausible that some of the ideas used here could be
used to tackle this conjecture. We note however that the stronger result

$\chi_{{\mathcal{H}}}(G)\geq
1+\max\left\\{\frac{n^{+}}{n^{-}},\frac{n^{-}}{n^{+}}\right\\}$

does not hold when ${\mathcal{H}}$ consists of all edge-transitive graphs (due
to $G=C_{5}$ mapping to $C_{5}\in{\mathcal{H}}$). Thus to prove this
conjectured lower bound for $\chi_{f}(G)$ using our approach, one would likely
need to use stronger properties of the Johnson scheme than those guaranteed by
Lemma 3.1.

## Acknowledgements

The authors gratefully acknowledge the American Institute of Mathematics; this
collaboration started at Spectral Graph and Hypergraph Theory: Connections &
Applications, December 6–10, 2021, a workshop at the American Institute of
Mathematics. The authors also are grateful for discussion on positive and
negative squared energies with Aida Abiad, Leonardo de Lima, Dheer Noal Desai,
Leslie Hogben and José Madrid.

## References

  * [1] T. Ando and M. Lin.  Proof of a conjectured lower bound on the chromatic number of a graph.  Linear Algebra and its Applications, 485:480–484, 2015.
  * [2] D. Anekstein, C. Elphick, and P. Wocjan.  More tales of Hoffman: bounds for the vector chromatic number of a graph.  Discussiones Mathematicae Graph Theory, 43, 01 2020.
  * [3] E. Bannai, E. Bannai, T. Ito, and R. Tanaka.  Algebraic combinatorics.  In Algebraic Combinatorics. De Gruyter, 2021.
  * [4] Y. Bilu.  Tales of hoffman: Three extensions of hoffman’s bound on the graph chromatic number.  Journal of Combinatorial Theory, Series B, 96(4):608–613, 2006\.
  * [5] J. Cooper and A. Dutle.  Spectra of uniform hypergraphs.  Linear Algebra and its Applications, 436(9):3268–3292, 2012.
  * [6] D. Cvetković.  Chromatic number and the spectrum of a graph.  Publ. Inst. Math.(Beograd), 14(28):25–38, 1972.
  * [7] P. Delsarte.  An algebraic approach to the association schemes of coding theory.  Philips Res. Rep. Suppl., (10):vi+97, 1973.
  * [8] C. Elphick and P. Wocjan.  An inertial lower bound for the chromatic number of a graph.  Electron. J. Combin., 24(1):#P1.58, 9, 2017.
  * [9] C. Elphick and P. Wocjan.  Spectral lower bounds for the quantum chromatic number of a graph.  J. Combin. Theory Ser. A, 168:338–347, 2019.
  * [10] P. Ganesan.  Spectral bounds for the quantum chromatic number of quantum graphs, 2021\.
  * [11] C. Godsil and K. Meagher.  Erdős-Ko-Rado theorems: algebraic approaches.  Number 149. Cambridge University Press, 2016.
  * [12] C. Godsil and G. Royle.  Algebraic graph theory, volume 207 of Graduate Texts in Mathematics.  Springer-Verlag, New York, 2001.
  * [13] K. Golubev.  On the chromatic number of a simplicial complex.  Combinatorica, 37(5):953–964, 2017.
  * [14] A. J. Hoffman.  On eigenvalues and colorings of graphs.  In Graph Theory and its Applications (Proc. Advanced Sem., Math. Research Center, Univ. of Wisconsin, Madison, Wis., 1969), pages 79–91. Academic Press, New York, 1970.
  * [15] Y. Mao and X. Liu.  On some inequalities for accretive-dissipative matrices.  Linear and Multilinear Algebra, 69(9):1657–1664, 2021.
  * [16] B. Mohar.  Eigenvalues and colorings of digraphs.  Linear Algebra and its Applications, 432(9):2273–2277, 2010.  Special Issue devoted to Selected Papers presented at the Workshop on Spectral Graph Theory with Applications on Computer Science, Combinatorial Optimization and Chemistry (Rio de Janeiro, 2008).
  * [17] V. Nikiforov.  Chromatic number and spectral radius.  Linear algebra and its applications, 426(2):810–814, 2007.
  * [18] E. Scheinerman and D. Ullman.  Fractional Graph Theory: A Rational Approach to the Theory of Graphs.  Dover books on mathematics. Dover Publications, 2011.
  * [19] A. Schrijver.  A comparison of the Delsarte and Lovász bounds.  IEEE Transactions on Information Theory, 25(4):425–429, 1979.
  * [20] The Sage Developers.  SageMath, the Sage Mathematics Software System (Version 8.3), 2018.  http://www.sagemath.org.
  * [21] E. van Dam and R. Sotirov.  New bounds for the max-k-cut and chromatic number of a graph.  Linear algebra and its applications, 488:216–234, 2016.
  * [22] H. S. Wilf.  The eigenvalues of a graph and its chromatic number.  Journal of the London Mathematical Society, s1-42(1):330–332, 1967\.
  * [23] P. Wocjan and C. Elphick.  New spectral bounds on the chromatic number encompassing all eigenvalues of the adjacency matrix.  Electron. J. Combin., 20(3):#P39, 2013.