# Multi-level Bézier extraction of truncated hierarchical B-splines for
isogeometric analysis

Andreas Grendas  Institute of Applied Mechanics, TU Graz, Technikerstraße 4,
8010 Graz, Austria  Benjamin Marussig  Institute of Applied Mechanics, TU
Graz, Technikerstraße 4, 8010 Graz, Austria

###### Abstract

Multivariate B-splines and Non-uniform rational B-splines (NURBS) lack
adaptivity due to their tensor product structure. Truncated hierarchical
B-splines (THB-splines) provide a solution for this. THB-splines organize the
parameter space into a hierarchical structure, which enables efficient
approximation and representation of functions with different levels of detail.
The truncation mechanism ensures the partition of unity property of B-splines
and defines a more scattered set of basis functions without overlapping on the
multi-level spline space. Transferring these multi-level splines into Bézier
elements representation facilitates straightforward incorporation into
existing finite element (FE) codes. By separating the multi-level extraction
of the THB-splines from the standard Bézier extraction, a more general
independent framework applicable to any sequence of nested spaces is created.
The operators for the multi-level structure of THB-splines and the operators
of Bézier extraction are constructed in a local approach. Adjusting the
operators for the multi-level structure from an element point of view and
multiplying with the Bézier extraction operators of those elements, a direct
map between Bézier elements and a hierarchical structure is obtained. The
presented implementation involves the use of an open-source Octave/MATLAB
isogeometric analysis (IGA) code called GeoPDEs [1]. A basic Poisson problem
is presented to investigate the performance of multi-level Bézier extraction
compared to a standard THB-spline approach.

##  1 Introduction

Isogeometric analysis (IGA) [2, 3] is a numerical method for solving partial
differential equations (PDEs) by using a unified representation for both the
analysis and design of structures. IGA is promising to close the gap between
analysis and CAD geometries of the structures. Traditionally, engineers have
used separate methods for modeling the geometry of a structure and analyzing
its behavior. However, IGA breaks through this limitation by employing non-
uniform rational B-splines (NURBS) functions, a standard technology employed
in CAD systems. The isoparametric philosophy is invoked, and the solution
space for dependent variables is represented in terms of the same functions
that represent the geometry.

Refinement techniques for NURBS functions are inherently simple and do not
require further communication with the CAD system. Order elevation and knot
insertion are refinement techniques analogous to standard FE methods like
$h$\- and $p$-, and a new, higher-order methodology emerges, $k$-refinement,
which combines order elevation followed by knot insertion. All subsequent
meshes retain the exact geometry of the initial CAD structure.

Due to the tensor product structure of the B-spline and NURBS functions, local
refinement can not be achieved. Various approaches have been developed to
overcome this limitation of tensor product structures, such as T-splines [4],
LR-splines [5], and HB-splines [6]. HB-splines are based on a multi-level
structure with different levels of detail and appear promising to implement
local refinement. Those splines can also be applied to T-splines indicating
hierarchical T-splines [7]. The hierarchical B-splines recently extended with
the truncation mechanism, namely, THB-splines [8]. This work presents an
adaptive isogeometric analysis framework based on THB-splines. This type of
function preserves all the essential mathematical properties of standard
B-splines and retains the partition of unity property in a hierarchical
structure. Despite the good properties of THB-splines and their simplicity,
implementing the hierarchical definition of shape functions into existing FE
solvers can be rather challenging. The proposed approach for this
implementation is based on a generalization of the classical Bézier extraction
[9], extended into a hierarchical concept [10, 11]. In fact, the multi-level
Bézier extraction maps the multi-level hierarchical functions, and the
corresponding knot spans, into a sequence of elements being equipped with a
standard single-level basis.

##  2 Preliminaries

In this section, some preliminary concepts need to be discussed in order to
give a summarized overview of the work steps. In particular, B-splines and
NURBS, the idea of Bézier extraction, and hierarchical splines, together with
the truncation mechanism, are presented.

###  2.1 B-splines and NURBS

We start by introducing the concept of B-splines and NURBS functions, but
further details can be found in [2], [3] and [12]. B-splines basis functions
are defined by degree $p$, and a knot vector:

$\Xi=\\{\xi_{1}\leq...\leq\xi_{n+p+1}\\},$ (1)

where $n$ is the number of basis functions. The Cox-de Boor recursion formula
defines the $n$ functions, by starting from degree $p=0$, up to the prescribed
degree,

$N_{i,0}=\begin{cases}1\leavevmode\nobreak\ \text{for}\leavevmode\nobreak\
\xi_{i}\leavevmode\nobreak\ \leq\xi<\xi_{i+1}\\\ 0\leavevmode\nobreak\
\text{else}\end{cases}N_{i,p}(\xi)={\dfrac{\xi-\xi_{i}}{\xi_{i+p}-\xi_{i}}N_{i,p-1}(\xi)}+{\dfrac{\xi_{i+p+1}-\xi}{\xi_{i+p+1}-\xi_{i+1}}N_{i+1,p-1}(\xi)}.$
(2)

The multiplicity $k$ of a knot value can be found from the knot vector and
defines the smoothness of the B-spline basis at this location, e.g.,
$C^{p-k}$. In the case of open knot vectors, the first and the last knot
values have multiplicity $k=p+1$, and the basis is interpolatory at the ends
of its definition domain. A B-spline curve can be constructed as the linear
combination of the basis functions.

$C(\xi)=\displaystyle\sum_{i=1}^{n}N_{i,p}(\xi)\mathbf{P}_{i},$ (3)

where $\mathbf{P}_{i}\in\mathbb{R}^{d}$ are the control points and equal the
number of basis functions. The Fig.1, shows a representation of a B-spline
with knot vector $\Xi=[0,0,0,0.25,0.5,0.75,0.75,1,1,1]$ and degree $p=2$.

Figure 1: Basis functions of a univariate quadratic B-spline and the
corresponding curve. $C^{0}$ continuity at the $knot=0.75$.

Going into higher dimensions to construct multivariate B-splines, tensor
product of univariate B-splines is formed. Considering $\mathbb{R}^{2}$, the
degrees $p$ and $q$ and knot vectors $\Xi=\\{\xi_{1}\leq...\leq\xi_{n+p+1}\\}$
and $H=\\{\eta_{1}\leq...\leq\eta_{m+q+1}\\}$, define each dimension of a
surface. Thus, two sets of basis functions along with the control net
${\mathbf{P}_{i,j}}$ with $i=1,2,...,n$, $j=1,2,...,m,$ describe the surface:

$S(\xi,\eta)=\displaystyle\sum_{i=1}^{n}\displaystyle\sum_{j=1}^{m}N_{i,p}(\xi)M_{j,q}(\eta)\mathbf{P}_{i,j}$
(4)

###  2.2 Standard Bézier extraction

This section provides a short introduction to Bézier extraction [9]. Unlike
the standard finite element approaches, B-spline basis functions are defined
globally (see Fig.1). Bézier extraction provides a mapping between the smooth
spline space and a $C^{0}$ representation of Bézier elements. Those elements
are defined by Bernstein polynomials, which are local, i.e., their support is
non-zero only in a single element. Thus, conventional element-based FE
routines can be enriched by splines in a straightforward manner.

Bézier extraction is generally based on knot insertion algorithms. The Bézier
decomposition of the B-spline curve into piece-wise Bézier curves is obtained
by increasing the multiplicity of each internal knot in $\Xi$, equals to the
degree $p$. Starting by inserting a single knot $\mathbf{\hat{\xi}}$ into
$\Xi$, so $\hat{\Xi}=\Xi\cup\hat{\xi}$, where
$\hat{\xi}\in[\xi_{s},\xi_{s+1}]$. This procedure continues until the desired
multiplicity of the internal knots is achieved, resulting a new set of basis
functions and a new set of control points that retain the geometry of the
curve. Further details for knot insertion techniques can be found in [2]. The
B-spline curve $C$ is described by a set of Bernstein polynomials $B_{i,p}$
and the Bernstein control points $\mathbf{\bar{P}}_{i}$

$C(\xi)=\displaystyle\sum_{i=1}^{\hat{n}}B_{i,p}(\xi)\mathbf{\bar{P}}_{i}$ (5)

The control points $\mathbf{\bar{P_{i}}}$ can be computed as a linear
combination of the original control points $\mathbf{P}_{i}$, which are
represented by a matrix operator $\mathbf{E}$, the Bézier extraction operator.
The same operator is used for the translation of the basis functions
$N_{i,p}(\xi)$ to the Bernstein polynomials $B_{i,p}(\xi)$. The basis
functions can be written in a vector format with $\mathbf{N}$ and
$\mathbf{B}$, respectively. So, globally defined B-splines transformed into a
basis of Bézier elements reads

$\mathbf{\bar{P}={E}^{T}P}\\\ \mathbf{N=EB}.$ (6)

###  2.3 Truncated hierarchical B-splines

In this section, the hierarchical B-splines are presented, which are used to
achieve local refinement and overcome the limitation of adaptivity due to the
tensor product structure of splines. Then, the extension with the truncation
mechanism is added to retain the partition of unity property [8, 10].

Hierarchical B-splines [6, 13] introduce a multi-level structure with
different levels of refinement. Consider a sequence of nested spline spaces of
univariate splines
$\mathbb{S}^{(0)}(\Omega)\subset\mathbb{S}^{(1)}(\Omega)...\subset\mathbb{S}^{(\ell_{max})}(\Omega)$
with the same polynomial degree, where $\ell=0\dots\ell_{max}$ are the levels
of refinement. In this contribution, the different levels are constructed with
the dyadic refinement technique, where each new level has $2d\cdot n_{el}$
elements ($d$ is the dimension and $n_{el}$ number of elements in $\ell-1$).
In Fig. 2, a univariate quadratic B-spline with two additional levels of
refinement is depicted. The geometry and the parametric representation do not
change under the refinement process, but the relation between the levels is
happening by an operator called, subdivision matrix $\mathbf{S}$. The parent
functions of the level $\ell$ are a linear combination of fine-scale functions
(children functions) of level $\ell+1$

$N(\xi)_{i,p}=\displaystyle\sum_{j=1}^{\hat{n}}\mathbf{S_{j,i}}\hat{N}_{j,p}(\xi).$
(7)

Each nested knot vector $\Xi^{\ell}$ defines a new set of B-spline basis
functions $N_{j,p}^{\ell}(\xi)$. So, the multi-level spline space is defined
as in [14]

$\begin{split}MS(\Omega):=\text{span}\\{{N^{(\ell)}_{i}\text{for
i}\in\eta^{(\ell)}_{A},\ell=0,1,\ldots,\ell_{max}}\\}\\\ \eta^{(\ell)}_{A}\
\text{: active},\eta^{(\ell)}_{D}\text{:
deactivate},\eta^{(\ell)}_{A}\cup\eta^{(\ell)}_{D}=\eta^{(\ell)}.\end{split}$
(8)

Therefore, the refinement process starts by deactivating parent functions of
the corresponding element from the coarse level $\ell$ and activating their
children on level $\ell+1$, until the desired adaptivity is achieved, see Fig.
2. The selection of the coarse and fine elements results from error estimator
algorithms or manual selection of the preferred elements. This information is
stored in the subdivision matrices [14, 15].

The truncated basis was first time introduced in [8]. The truncation mechanism
preserves all the nice properties of hierarchical B-splines, such as linear
independence, local support, and non-negativity. In addition, truncated
hierarchical B-splines (THB-splines) have smaller support and retain the
partition of unity property of traditional B-splines. The truncated basis
functions are defined as

$truncN^{\ell}_{i}(\xi)=\displaystyle\sum_{j\in\eta^{\ell+1}_{D}}S^{(\ell)}_{ji}N^{(\ell+1)}_{j}(\xi).$
(9)

In general, it is straightforward to identify the truncated B-spline
functions. Let’s assume an evaluation of an element on the finest level
$\ell+1$. The basis functions that describe the element are
$N^{\ell+1}_{i}(\xi)$, with $i=s^{\ell+1}-p\ldots s^{\ell+1}$, where the
$s^{\ell+1}$ is the knot span of the element in that level. This element holds
truncated B-splines on the previous level, $\ell$, only if at least one of its
$N^{\ell+1}_{i}(\xi)$ is inactive (see Fig. 2).

##  3 Multi-level Bézier extraction

Having a sequence of nested spline spaces into a hierarchical structure, every
basis function of level $\ell$ can be expressed as a linear combination of
basis functions of level $\ell+1$, with the subdivision matrix (7). The global
multi-level extraction operator, $\mathbf{M}^{glob}_{\ell}$, can be defined by
applying a sequence of nested spline spaces, where the goal is to extract the
hierarchical functions supporting an element at a specific level. For levels
$\ell=0,..,\ell_{max}$ the $\mathbf{M}^{glob}_{\ell_{max}}$ can be obtained by
joining the rows, corresponding to the active basis, of the refinement
operators $\mathbf{S}^{(\ell,\ell_{max})}$. More details for constructing the
global multi-level extraction operator can be found in [11]. Next,
localization of the global multi-level extraction to each element of the
domain leads to a local element-by-element approach. By selecting the
appropriate columns and rows associated with the basis functions of the
element, the extraction operator effectively captures the hierarchical
functions. The multi-level extraction operator is always of the same level as
the element. All the different matrices, $\mathbf{M}^{loc}_{e}$, correspond to
each element of the hierarchical spline space, $e=0,...,n_{el}$. They can be
combined directly with the Bézier extraction operator, resulting the multi-
level Bézier extraction technique (see Fig. 3). This creates a direct map
$\mathbf{C^{e}}$ from a standard set of reference basis functions equal for
each element (Bernstein basis, $\mathbf{B}$) to the multi-level local basis
(hierarchical basis).

Figure 2:  Basis functions for the computational domain. The gray functions
are the deactivated ones and the colored ones are the active ones. The
$N_{3}^{(0)}$ and $N_{7}^{(1)}$ are truncated functions.

$\begin{split}H^{e}&=\mathbf{M}^{loc}_{e}\mathbf{E}^{loc}_{e}\mathbf{B}\\\
&=\mathbf{C}^{e}\mathbf{B}\end{split},\quad\textnormal{with}\quad\mathbf{B}=\begin{bmatrix}B_{0}\\\
B_{1}\\\ \vdots\\\ B_{p}\end{bmatrix}$ (10)

$\begin{bmatrix}N_{6}^{(1)}\\\ N_{7}^{(1)}\\\
N_{14}^{(2)}\end{bmatrix}=\mathbf{M}^{e_{3}}\mathbf{E}^{e_{3}}\begin{bmatrix}B_{0}\\\
B_{1}\\\ B_{2}\end{bmatrix}$

Figure 3: Translate from hierarchical spline space to local Bernstein
polynomials.

As the hierarchical basis functions are mapped into a local approach with
elements with a standard set of basis functions, the calculations into the
Bézier elements are performed. This can happen using the existing FE
algorithms, and there is no need for separate algorithms to handle the
globally defined spline basis functions.

##  4 Numerical example

This contribution uses GeoPDEs [1, 16], an open-source FE solver for IGA,
based on Matlab/Octave. Let us first highlight an advantage of Bézier
extraction over the direct use of B-splines basis functions. The problem
refers to the evaluation of points at the boundaries of the elements. Due to
the Cox-de Boor formula (2), boundary points are generally associated with the
right element of the domain, which can lead to misinterpretations. Consider
the numerical integration of an element using a Newton-Cotes quadrature rule.
These rules contain the boundary points, and based on (2), the contribution of
the last point would be associated with the next element instead of the
current one. This can be easily overcome with the use of Bézier extraction. An
example to illustrate the problem is in Fig. 4, where the Newton-Cotes
quadrature rule is applied for the integration of the elements in a univariate
problem, instead of the Gaussian quadrature method. Bézier extraction should
be applied to evaluate accurately. In this case, improving the results is not
the goal of Newton-Cotes, but to verify the problem of spline-based algorithms
using Cox-de Boor formula.

Figure 4: Newton-Cotes integration points appear in the boundary of the
elements and can not be evaluated correctly due to the Cox-de Boor formula.
Bézier extraction, in the right figure, overcomes this limitation with a
standard set of Bernstein polynomials.

###  4.1 Unit square boundary value problem

The numerical example for this work is a second-order elliptic boundary value
problem in a unit square domain. The functions $f$, $g$ and $h$ are chosen
from the exact solution (see Fig. 5) of the problem
$u_{ex}=\exp{(-C\cdot((x-0.5)^{2}+(y-0.5)^{2}))}$, where $C$ is constant.

$\begin{cases}\Delta u=f&\textnormal{in}\>\>\Omega\\\
u=g&\textnormal{on}\>\>\Gamma_{D}\\\ \triangledown
u\cdot\mathbf{n}=h&\textnormal{on}\>\>\Gamma_{N}\end{cases},\\\
\Omega=\left[0,1\right]^{2}\>\&\>{\Gamma_{N}\cup\Gamma_{D}}=\partial{\Omega}$
(11)

For the calculation, two types of THB-splines are assumed, one quadratic and
one cubic. In both cases, global and local refinement techniques are compared.
For the local refinement, the refined mesh is shown in Fig. 6. Now, as for the
multi-level Bézier extraction, the goal is to approach the error of the local
refinement that GeoPDEs is resulting in. Calculating the multi-level Bézier
extraction operator $\mathbf{C}^{e}$, as described in Section 3, and then
calculating the stiffness matrix of a single Bézier element, the stiffness
matrix of an element in the hierarchical structure can be derived.

$\begin{split}\mathbf{K}_{B-spline,e}=\mathbf{C}^{e}\mathbf{K}_{Bezier}(\mathbf{C}^{e})^{T}\\\
\mathbf{K}_{global}=\displaystyle\sum_{i=1}^{n_{el}}\mathcal{T}(\mathbf{K}_{B-spline,i}^{e})\end{split}$
(12)

Figure 5: Exact solution of the unit square boundary value problem.

Gathering all the element-wise stiffness matrices, the stiffness matrix for
the whole multi-level spline space is obtained. Fig. 7 shows the convergence
of the multi-level Bézier extraction and the local refinement of GeoPDEs.

Figure 6: Mesh through iterations of local refinement with THB-splines.

Figure 7: L2 norm error. Global refinement, local refinement, and multi-level
Bézier extraction on the local refinement. On the left are quadratic splines,
and on the right are cubic splines. The green line of multi-level Bézier
extraction matches exactly the blue line of the local refinement from the
patch-wise approach.

When comparing the values of the graphs in both cases, the results of multi-
level Bézier extraction fit the IGA-based algorithm. This verifies that by
just evaluating a single Bézier element, the stiffness matrix can be directly
mapped into a hierarchical structure and evaluate multi-level spline spaces.

##  5 Conclusion

This study demonstrates that Bézier extraction can be extended into a multi-
level structure of truncated hierarchical B-splines (THB-splines), resulting
the multi-level Bézier extraction. The calculation over Bézier elements is
sufficient to extract results for hierarchical spline spaces which perform
local refinement. The only calculation that needs to be derived is the multi-
level Bézier extraction operators for each element of the domain and the
standard Bézier extraction operator. Then those operators are applied to
Bézier elements. The implementation of the isogeometric analysis concept into
existing finite element solvers can be employed. Additionally, this general
approach is not restricted to THB-splines but can be compatible with any
nested space.

## References

  * [1] E. M. Garau and R. Vázquez, Appl. Numer. Math. 123, 58–87 (2018).
  * [2] T. J. Hughes, J. A. Cottrell, and Y. Bazilevs, Comput. Methods Appl. Mech. Eng. 194(39-41), 4135–4195 (2005).
  * [3] J. A. Cottrell, T. J. Hughes, and Y. Bazilevs, Isogeometric analysis: toward integration of CAD and FEA (John Wiley & Sons, 2009).
  * [4] M. A. Scott, M. J. Borden, C. V. Verhoosel, T. W. Sederberg, and T. J. Hughes, Int. J. Numer. Methods Eng. 88(2), 126–156 (2011).
  * [5] T. Dokken, T. Lyche, and K. F. Pettersen, Comput. Aided Geom. Des. 30(3), 331–356 (2013).
  * [6] R. Kraft Adaptive and linearly independent multilevel B-splines (Univ., Sonderforschungsbereich 404, 1997).
  * [7] E. Evans, M. Scott, X. Li, and D. Thomas, Comp. Methods Appl. Mech. Eng. 284, 1–20 (2015).
  * [8] C. Giannelli, B. Jüttler, and H. Speleers, Comput. Aided Geom. Des. 29(7), 485–498 (2012).
  * [9] M. J. Borden, M. A. Scott, J. A. Evans, and T. J. Hughes, Int. J. Numer. Methods Eng. 87(1-5), 15–47 (2011).
  * [10] P. Hennig, S. Müller, and M. Kästner, Comput. Methods Appl. Mech. Eng. 305, 316–339 (2016).
  * [11] D. D’Angella, S. Kollmannsberger, E. Rank, and A. Reali, Comput. Methods Appl. Mech. Eng. 328, 147–174 (2018).
  * [12] L. Piegl and W. Tiller, The NURBS book (Springer Science & Business Media, 1996).
  * [13] A. V. Vuong, C. Giannelli, B. Jüttler, and B. Simeon, Comput. Methods Appl. Mech. Eng. 200(49-52), 3554–3567 (2011).
  * [14] B. Marussig, R. Hiemstra, and T. J. Hughes, Comput. Methods Appl. Mech. Eng. 334, 79–110 (2018).
  * [15] G. Kiss, Theory and algorithms for truncated hierarchical B-splines/eingereicht von: Gábor Kiss, PhD thesis, Linz, 2015.
  * [16] R. Vázquez, Comput. Math. Appl. 72(3), 523–554 (2016).


# Self Multi-Head Attention for Speaker Recognition

###### Abstract

Most state-of-the-art Deep Learning (DL) approaches for speaker recognition
work on a short utterance level. Given the speech signal, these algorithms
extract a sequence of speaker embeddings from short segments and those are
averaged to obtain an utterance level speaker representation. In this work we
propose the use of an attention mechanism to obtain a discriminative speaker
embedding given non fixed length speech utterances. Our system is based on a
Convolutional Neural Network (CNN) that encodes short-term speaker features
from the spectrogram and a self multi-head attention model that maps these
representations into a long-term speaker embedding. The attention model that
we propose produces multiple alignments from different subsegments of the CNN
encoded states over the sequence. Hence this mechanism works as a pooling
layer which decides the most discriminative features over the sequence to
obtain an utterance level representation. We have tested this approach for the
verification task for the VoxCeleb1 dataset. The results show that self multi-
head attention outperforms both temporal and statistical pooling methods with
a $18\%$ of relative EER. Obtained results show a $58\%$ relative improvement
in EER compared to i-vector+PLDA.

Index Terms: Speaker Embeddings, Speaker Verification, Multi-Head Self
Attention, Attention Models

##  1 Introduction

Recently there have been several attempts to apply Deep Learning (DL) in order
to build speaker embeddings. Speaker embedding is often referred to a single
low dimensional vector representation of the speaker characteristics from a
speech signal extracted using a Neural Network (NN) model. For text-
independent Speaker Recognition (SR), which is the focus of this work, these
models can be trained either in a supervised (e.g., [1, 2]) or in an
unsupervised (e.g., [3, 4]) fashion. Supervised speaker embeddings are
produced by training a deep architecture using speaker-labeled background
data. This network, which is capable to produce high-level features, is
usually trained to discriminate the background speakers. Then in the testing
phase, the output layer is discarded, the feature vectors of an unknown
speaker are given through the network, and the pooled representation from the
activation of a given hidden layer are considered as the speaker embedding [1,
2, 5, 6]. The reported results from different works have shown that, in most
of cases, the largest improvements are obtained on short utterances compared
to the conventional i-vectors [5, 2]. That suggests that DL technology can
model the speaker characteristics of a short-duration speech signal better
than the traditional signal processing techniques.

In [1], the inputs of the network are the speaker feature vectors stacked over
a context window. They use a Deep Neural Network (DNN) with max-pooling and
dropout regularization applied on the last two hidden layers. There are also
other works which employes other deep architectures such as CNN and Time Delay
Neural Network (TDNN) [5, 7]. Snyder et al., in [8] introduced a temporal
pooling to extract speaker embeddings and a DNN architecture with a PLDA-like
objective function. This function operates on pairs of embeddings to maximize
the probability for the embeddings of the same speakers and minimize it
otherwise. In [2], they take advantage of a TDNN which is further followed by
a statistical pooling and a DNN classifier. The statistical pooling layer
aggregates input segments over the variable-length and prepares the fixed-
dimensional statistics vectors as the inputs of a feed-forward network. The
second part of the network has only two hidden layers whose activations can be
used as speaker embeddings. The preliminary results showed that these
embeddings outperform the traditional i-vectors [9] for short duration speech
segments [2]. However, [6] a recent work has shown that data augmentation,
consisting of added noise and reverberation, can significantly improve the
performance of these embeddings (x-vectors as they referred to), while it is
not so effective for i-vectors [6]. There have also been some efforts to
improve the quality and generalization powers of x-vectors by the modification
applied to the network architecture [10] and the training procedure [11, 12,
13].

Attention mechanisms are one of the main reasons of the success of sequence-
to-sequence (seq2seq) models in tasks like Neural Machine Translation (NMT) or
Automatic Speech Recognition (ASR) [14, 15, 16]. In seq2seq models, these
algorithms are applied over the encoded sequence in order to help the decoder
to decide which region of the sequence must be either translated or
recognized. For speaker recognition, these models have been also used for
text-dependent speaker verification. In works like [5, 17, 18], attention is
applied over the hidden states of a Recurrent Neural Network (RNN) in order to
pool these states into speaker embeddings. The same idea has been also used
for text-independent verification. In [19], a unified framework is introduced
for both speaker and language recognition. In this architecture, variable-
length input utterance is fed into a network that encodes an utterance level
representation. In addition to temporal pooling, they have also adopted a
self-attention pooling mechanism and a learnable dictionary encoding layer to
get the utterance level representation. Multi-head attention is a newly
emerging attention mechanism which is originally proposed in [15] for a
Transformer architecture and appeared very effective in many seq2seq models
such as [15, 20, 21].

In this paper we present a multi-head attention based network for speaker
verification. This mechanism is used as a self attentive pooling layer to
create an utterance level embedding. Given a set of encoded representations
from a CNN feature extractor, self attention performs a weighted average of
these representations. This mechanism differs from other pooling methods in
that the average weights are also trained as network parameters. In comparison
with other works like [19], our approach introduces a major improvement by
using multi-head attentions (instead of single-head attention as in [19]).
This allows the model to attend to different parts of the sequence, which is
one of the main limitations of vanilla self attentive pooling. In the same
way, multi-head also helps the network to attend to different sub-sets of the
encoded representations. Therefore the encoder is not forced to create overall
speaker embeddings from the feature level. Attention allows the encoder to
create different sets of features, so the model can attend to the most
discriminative patterns from different positions of the sequence. The main
contribution of this works is the introduction of a pooling layer which takes
advantage of multi-head self attention mechanism to create more discriminative
speaker embeddings. We compare this pooling mechanism with temporal and
statistical pooling layers. In order to show the effectiveness of the proposed
approach, these embeddings will be assessed in a text-independent speaker
verification task.

The rest of this paper is structured as follows. Section 2 explains self
multi-head attention pooling. Section 3 illustrates the architecture of the
system. Section 4 gives the details of the system setup. Experimental results
are presented in section 5. The concluding remarks and some future works are
given in section 6.

##  2 Self Multi-Head Attention Pooling

Self attentive pooling attention was initially proposed in [19] for text-
independent speaker verification. Their objective was to use a trainable and
more adapted layer for pooling than vanilla temporal average. Given a sequence
of encoded hidden states from a network, temporal pooling averages these
representations over the time to obtain a final encoded embedding. The main
problem of this method is that assumes that all the elements of the sequence
must contribute equally in obtaining the utterance level representation. Self
attentive pooling is a mechanism that through a trainable layer is able to
assign a weight over each representation of the sequence. Hence given these
weights, the utterance level representation is obtained through the respective
weighted average of these representations.

Consider a sequence of hidden of sequence states $h=[h_{1}h_{2}...h_{N}]$,
with $h_{t}\in\mathbb{R}^{d}$, and a trainable $u\in\mathbb{R}^{d}$. We can
define a relevance scalar weight for each element of the sequence trough a
softmax layer:

$\centering
w_{t}=\frac{\exp{(h^{T}_{t}u)}}{\sum^{N}_{l=1}\exp{(h^{T}_{l}u)}}\@add@centering$
(1)

Given the set of weights over all the elements of the sequence, we can then
obtain the pooled representation as the weighted average of the hidden states:

$\centering c=\sum^{N}_{t=1}h^{T}_{t}w_{t}\@add@centering$ (2)

This attention mechanism has some limitations. The main restriction is that
attention weights are calculated considering the whole information of the
embedding. Therefore, we assume that all the discriminative information of the
signal must come from the same encoded representations of the utterance.

Figure 1: An example of the Self Multi-Head Attention Pooling with $3$ heads.

Multi-head attention model was firstly introduced in [15]. This approach
consists on splitting the encoded representations of the sequence into
homogeneous sub-vectors called heads (Figure 1). If we consider a number of
$k$ heads for the multi-head attention, now $h_{t}=[h_{t1}h_{t2}...h_{tk}]$
where $h_{tj}\in\mathbb{R}^{d/k}$. We can compute then the head size as $d/k$.
In the same way we have also a trainable parameter $u=[u_{1}u_{2}...u_{k}]$
where $u_{j}\in\mathbb{R}^{d/k}$. A different attention is then applied over
each head of the encoded sequence:

$\centering
w_{tj}=\frac{\exp{(h^{T}_{tj}u_{j})}}{\sum^{N}_{l=1}\exp{(h^{T}_{lj}u_{j})}}\@add@centering$
(3)

where $w_{tj}$ corresponds to the attention weight of the head $j$ on the step
$t$ of the sequence. If each head corresponds to a subspace of the hidden
state, the weight sequence of that head can be considered as a probability
distribution function from that sub-space features over the sequence. We then
compute a new pooled representation for each head in the same way than vanilla
self attention:

$\centering c_{j}=\sum^{N}_{t=1}h^{T}_{tj}w_{tj}\@add@centering$ (4)

where $c_{j}\in\mathbb{R}^{d/k}$ corresponds to the utterance level
representation from head $j$. The final utterance level representation is then
obtained with the concatenation of the utterance level vectors from all the
heads $c=[c_{1}c_{2}...c_{k}]$. This method allows the network to extract
different kind information over different regions of the network. Besides, the
main advantage of this attention variation is that it does not increase the
complexity of the model adding more parameters on the model. Instead of having
a global $u$ attention vector, we have now a subset of attention vector
$u_{j}$ which sums the same number of components than $u$.

##  3 System Description

Figure 2 shows the overall architecture used for this work. The proposed
neural network is a CNN based encoder and an attention based pooling layer
followed by a set of dense layers. The network is fed with variable length
mel-spectrogram features. These features are then mapped into a sequence of
speaker representations trough a CNN encoder. This CNN feature extractor is
based on of the VGG proposed in [22] for the ASR task. In our case, we have
extended this architecture so as to work for speaker verification. Our adapted
VGG is composed of three convolution blocks, where each block contains two
concatenated convolutional layers followed by a max pooling layer with a
$2$x$2$ stride. Hence given a spectrogram a of $N$ frames, the VGG performs a
down-sampling reducing its output into a sequence of $N/8$ representations.
Given this set of representations, the attention mechanism is then used to
transform the encoded states of the CNN into an overall speaker
representation. Finally this fixed length embedding is feed into a set of
Fully Connected (FC) layers and a softmax layer. We refer to bottle neck layer
previous to the softmax layer as the speaker embedding. The softmax layer
corresponds to the speaker labels of the train partition corpus. Hence the
network is trained as a speaker classifier. The speaker embedding layer
corresponds to the speaker representation that will be used for the speaker
verification task.

Figure 2: System Diagram. Layer | Size | In Dim. | Out Dim. | Stride | Feat Size
---|---|---|---|---|---
conv11 | 3x3 | 1 | 128 | 1x1 | 128xN
conv12 | 3x3 | 128 | 128 | 1x1 | 128xN
mpool1 | 2x2 | - | - | 2x2 | 64xN/2
conv21 | 3x3 | 128 | 256 | 1x1 | 64xN/2
conv22 | 3x3 | 256 | 256 | 1x1 | 64xN/2
mpool2 | 2x2 | - | - | 2x2 | 32xN/4
conv31 | 3x3 | 256 | 512 | 1x1 | 32xN/4
conv32 | 3x3 | 512 | 512 | 1x1 | 32xN/4
mpool3 | 2x2 | - | - | 2x2 | 16XN/8
flatten | - | 512 | 1 | - | 8192xN/8
Table 1: CNN Architecture. In and Out Dim. refers to the input and output
feature maps of the layer. Feat Size refers to the dimension of each one of
this output feature maps.

##  4 Experimental Setup

The proposed system in this work will be tested on VoxCeleb1 [23]. This corpus
is a large multimedia database that contains over $100,00$ utterances for
$1,251$ celebrities, extracted from videos uploaded to Youtube. For each
person in the corpus there is an average of $18$ videos. Each of these videos
has been split into approximately $123$ short speech utterances of $8.2$
seconds average length. The proposed approaches will be evaluated on the
original VoxCeleb1 speaker verification protocol [24]. Hence the network is
trained with VoxCeleb1 development partition and evaluated on the test set.

Three different baselines will be considered to compare with the presented
approach. The soft multi-head attention pooling will be evaluated against two
statistical based methods: temporal and statistical pooling. In order to
evaluate them, this pooling layers will replace the attention pooling block
without modifying any other parameter of the network. The speaker vectors used
for the verification tests will be extracted from the same speaker embedding
layer for each of the pooling methods. The metric used to compute the scores
between embeddings for the verification task is cosine distance. Additionally
we have also considered an i-vector + PLDA baseline [9, 25]. The i-vector is
created from $20$ MFCC + delta coefficients features. The extraction is
performed using a $1024$ Universal Background Model (UBM) and a $400$ total
variability matrix. G-PLDA[25] is applied with $200$ eigenvector size.

Table 2: Evaluation results of the text-independent verification task on VoxCeleb 1. The results for our proposed architecture have been obtained using cosine scoring. Approach | DCF | EER
---|---|---
I-vector + PLDA | 0.0078 | $9.54$
CNN + Temporal Pooling | 0.0047 | $4.91$
CNN + Statistical Pooling | 0.0046 | $4.9$
CNN + Att. Pooling | 0.005 | $4.71$
CNN + MHA Pooling | 0.0045 | 4.0
Figure 3: DET curves for the experiments on VoxCeleb 1 verification task. MHA
stands for the Multi-Head Attention. Figure 4: Top: Analysis of the weight
values for the first six multi-head attentions over a test utterance. Bottom:
Comparison between vanilla attention weights and the averaged weights over all
the heads of our proposed model (Cumulative MHA). The weights are extracted
from the same test utterance than the top image.

The proposed network has been trained to classify variable length speaker
utterances. For feature extraction we have used librosa [26] to extract $128$
dimension mel-spectrograms. The CNN encoder is then feed with $128$x$N$
spectrograms to obtain a sequence of $8192$x$N/8$ encoded hidden
representations. The setup of the CNN feature extractor can be found on Table
1. The pooling layer maps the encoded sequence into an unique speaker
representation. The following FC Block consists on two consecutive dense
layers with $1024$ and $500$ dimension, where the last layer correspond to the
speaker embedding. A final softmax layer is then fed with the speaker
embedding. Batch normalization has been applied on the $1024$ dense layer and
$0.2$ dropout on the softmax layer. Adam optimizer has been used to train all
the models with standard values and learning rate of $1e-4$. Finally we have
applied a $5$ epochs patience early stopping criterion.

##  5 Results

The proposed attention pooling layer has been evaluated with different
approaches in the VoxCeleb1 text-independent verification task and presented
in Table 2. Performance is evaluated using the Equal Error Rate (EER) and the
minimum Decision Cost Function (DCF) calculated using $C_{FA}=1$, $C_{M}=1$,
and $P_{T}=0.01$. MHA Pooling refers to the best self multi-head attention
model that we have trained. This model has a $128$ head size, which
corresponds to $64$ heads per encoded representation. I-vector with PLDA have
shown the worst results for this task. As it has mentioned before, i-vectors
performance decreases in short-utterance condition. Following the i-vector,
the statistical based pooling layers have scored $4.91\%$ and $4.9\%$ EER,
respectively. Vanilla self attentive pooling performance has shown a $4.71\%$
EER. Similar to the work proposed in [19], self attentive pooling doesn’t lead
to a big improvement. Here it has only shown a $4\%$ improvement relative
improvement. Self Multi-Head attention has shown the best result of all the
evaluated approaches. It outperforms both i-vector+PLDA and statistical based
pooling layers with a $58\%$ EER and $18\%$ EER improvement, respectively. In
comparison with self attentive pooling layer, MHA also shows a noticeable
improvement of $14\%$ EER.

Figure 3 shows the Detection Error Tradeoff (DET) curves of the i-vector+PLDA
baseline and our proposed architecture with different pooling mechanisms. It
shows that not only at the EER but also at all other working points MHA
pooling outperforms other pooling mechanisms by a large margin.

In order to understand the improvement achieved with self-multihead attention
pooling in comparison with vanilla attention models, we have assessed their
attention weights. Figure 4 shows the weight values created over the encoded
features of the CNN for both vanilla and multi-head attention pooling in one
of the VoxCeleb1 test utterances. On the top we can appreciate how each of the
several heads of the multi-head model attends to different regions of the
sequence. That suggests that the model is able to capture sub-sets of features
from the encoded representations in different parts of the signal. On the
bottom, the weight values from vanilla attention model are compared with the
averaged weights of the different heads of the multi-head model (cumulative
multi-head). Vanilla attention weights have a more uniform distribution over
the sequence than the weights showed by the heads of the multi-head model in
the top image. If we compare the weight alignment created from both vanilla
attention and cumulative multi-head, several discriminative regions are
commonly detected. However, there are some regions of the sequence attended by
the MHA model that vanilla attention has not detected. That suggests that MHA
degrees of freedom permits the detection procedure to focus on more specific
regions of the sequence.

##  6 Conclusions

In this paper we have applied a self multi-head attention mechanism to obtain
speaker embeddings at level utterance by pooling short-term features. This
pooling layer have been tested in a neural network based on a CNN that maps
spectrograms into sequences of speaker vectors. These vectors are then input
to the pooling layer, which output activation is then connected to a set of
dense layers. The network is trained as a speaker classifier and a bottleneck
layer from the fully connected block is used as speaker embedding. We have
evaluated this approach with other pooling methods for the text-independent
verification task using the speaker embeddings and applying cosine distance.
The presented approach have outperformed standard pooling methods based on
statistical layers and vanilla attention models. We have also analyzed the
multi-head attention alignments over a sequence. This analysis have shown that
self multi head attention layer allows to capture specific sub-sets of
features over different regions of a sequence.

##  7 Acknowledgements

This work was supported in part by the Spanish Project DeepVoice
(TEC2015-69266-P).

## References

  * [1] E. Variani, X. Lei, E. McDermott, I. L. Moreno, and J. Gonzalez-Dominguez, “Deep neural networks for small footprint text-dependent speaker verification,” in _2014 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_. IEEE, 2014, pp. 4052–4056.
  * [2] D. Snyder, D. Garcia-Romero, D. Povey, and S. Khudanpur, “Deep neural network embeddings for text-independent speaker verification,” in _Interspeech_ , 2017, pp. 999–1003.
  * [3] V. Vasilakakis, S. Cumani, P. Laface, and P. Torino, “Speaker recognition by means of deep belief networks,” _Proc. Biometric Technologies in Forensic Science_ , 2013.
  * [4] P. Safari, O. Ghahabi, and F. J. Hernando Pericás, “From features to speaker vectors by means of restricted boltzmann machine adaptation,” in _ODYSSEY 2016-The Speaker and Language Recognition Workshop_ , 2016, pp. 366–371.
  * [5] G. Bhattacharya, M. J. Alam, and P. Kenny, “Deep speaker embeddings for short-duration speaker verification,” in _Interspeech_ , 2017, pp. 1517–1521.
  * [6] D. Snyder, D. Garcia-Romero, G. Sell, D. Povey, and S. Khudanpur, “X-vectors: Robust dnn embeddings for speaker recognition,” in _2018 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_. IEEE, 2018, pp. 5329–5333.
  * [7] L. Li, Z. Tang, D. Wang, and T. F. Zheng, “Full-info training for deep speaker feature learning,” in _2018 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_. IEEE, 2018, pp. 5369–5373.
  * [8] D. Snyder, P. Ghahremani, D. Povey, D. Garcia-Romero, Y. Carmiel, and S. Khudanpur, “Deep neural network-based speaker embeddings for end-to-end speaker verification,” in _2016 IEEE Spoken Language Technology Workshop (SLT)_. IEEE, 2016, pp. 165–170.
  * [9] N. Dehak, P. J. Kenny, R. Dehak, P. Dumouchel, and P. Ouellet, “Front-end factor analysis for speaker verification,” _IEEE Transactions on Audio, Speech, and Language Processing_ , vol. 19, no. 4, pp. 788–798, 2011.
  * [10] S. Novoselov, A. Shulipa, I. Kremnev, A. Kozlov, and V. Shchemelinin, “On deep speaker embeddings for text-independent speaker recognition,” _arXiv preprint arXiv:1804.10080_ , 2018.
  * [11] L. Li, Z. Tang, Y. Shi, and D. Wang, “Gaussian-constrained training for speaker verification,” _arXiv preprint arXiv:1811.03258_ , 2018.
  * [12] H. Zeinali, L. Burget, J. Rohdin, T. Stafylakis, and J. Cernocky, “How to improve your speaker embeddings extractor in generic toolkits,” _arXiv preprint arXiv:1811.02066_ , 2018.
  * [13] Z. Huang, S. Wang, and K. Yu, “Angular softmax for short-duration text-independent speaker verification,” _Proc. Interspeech, Hyderabad_ , 2018\.
  * [14] D. Bahdanau, K. Cho, and Y. Bengio, “Neural machine translation by jointly learning to align and translate,” _arXiv preprint arXiv:1409.0473_ , 2014\.
  * [15] 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.
  * [16] W. Chan, N. Jaitly, Q. V. Le, and O. Vinyals, “Listen, attend and spell,” _arXiv preprint arXiv:1508.01211_ , 2015.
  * [17] S.-X. Zhang, Z. Chen, Y. Zhao, J. Li, and Y. Gong, “End-to-end attention based text-dependent speaker verification,” in _2016 IEEE Spoken Language Technology Workshop (SLT)_. IEEE, 2016, pp. 171–178.
  * [18] F. Chowdhury, Q. Wang, I. L. Moreno, and L. Wan, “Attention-based models for text-dependent speaker verification,” _arXiv preprint arXiv:1710.10470_ , 2017.
  * [19] W. Cai, J. Chen, and M. Li, “Exploring the encoding layer and loss function in end-to-end speaker and language recognition system,” in _Proc. Odyssey 2018 The Speaker and Language Recognition Workshop_ , 2018, pp. 74–81.
  * [20] C.-C. Chiu, T. N. Sainath, Y. Wu, R. Prabhavalkar, P. Nguyen, Z. Chen, A. Kannan, R. J. Weiss, K. Rao, E. Gonina _et al._ , “State-of-the-art speech recognition with sequence-to-sequence models,” in _2018 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_. IEEE, 2018, pp. 4774–4778.
  * [21] M. Dehghani, S. Gouws, O. Vinyals, J. Uszkoreit, and Ł. Kaiser, “Universal transformers,” _arXiv preprint arXiv:1807.03819_ , 2018.
  * [22] T. Hori, S. Watanabe, Y. Zhang, and W. Chan, “Advances in joint ctc-attention based end-to-end speech recognition with a deep cnn encoder and rnn-lm,” _arXiv preprint arXiv:1706.02737_ , 2017.
  * [23] A. Nagrani, J. S. Chung, and A. Zisserman, “Voxceleb: a large-scale speaker identification dataset,” in _INTERSPEECH_ , 2017.
  * [24] J. S. Chung, A. Nagrani, and A. Zisserman, “Voxceleb2: Deep speaker recognition,” in _INTERSPEECH_ , 2018.
  * [25] S. J. Prince and J. H. Elder, “Probabilistic linear discriminant analysis for inferences about identity,” in _2007 IEEE 11th International Conference on Computer Vision_. IEEE, 2007, pp. 1–8.
  * [26] B. McFee, M. McVicar, S. Balke, V. Lostanlen, C. Thomé, C. Raffel, D. Lee, K. Lee, O. Nieto, F. Zalkow, D. Ellis, E. Battenberg, R. Yamamoto, J. Moore, Z. Wei, R. Bittner, K. Choi, nullmightybofo, P. Friesch, F.-R. Stöter, Thassilo, M. Vollrath, S. K. Golu, nehz, S. Waloschek, Seth, R. Naktinis, D. Repetto, C. F. Hawthorne, and C. Carr, “librosa/librosa: 0.6.3,” Feb. 2019\. [Online]. Available: https://doi.org/10.5281/zenodo.2564164


# Sumsets as Unions of Sumsets of Subsets

Jordan S. Ellenberg

###### Abstract

We show that, for any subsets $S$ and $T$ of $\mathbb{F}_{q}^{n}$, there are
subsets $S^{\prime}\subset S$ and $T^{\prime}\subset T$ such that
$|S^{\prime}|+|T^{\prime}|<c_{q}^{n}$ for some $c_{q}<q$, and
$(S^{\prime}+T)\cup(S+T^{\prime})=S+T$.

title = Sumsets as Unions of Sumsets of Subsets, author = Jordan S. Ellenberg,
plaintextauthor = Jordan S. Ellenberg, plaintexttitle = Sumsets as Unions of
Sumsets of Subsets, year=2017, number=14, received=22 May 2017, published=6
September 2017, doi=10.19086/da.2103,

[classification=text]

The novel approach to additive combinatorics in abelian groups introduced by
Croot, Lev, and Pach in [CLP] has led to rapid progress in a range of problems
in extremal combinatorics: for instance, a new upper bound for the cap set
probem [ellegijs], bounds for complexity of matrix-multiplication methods
based on elementary abelian groups [blasiak], bounds for the Erdős-Szemeredi
sunflower conjecture [naslund], and polynomial bounds for the arithmetic
triangle removal lemma [fox]. In many of the applications, the original bound
on cap sets in [ellegijs] does not suffice for applications: for instance, in
[blasiak] and [fox] one needs to bound the size of a multi-colored sum-free
set, a somewhat more general object.

In the present note, we use the Croot-Lev-Pach lemma, combined with an older
result of Meshulam on linear spaces of low-rank matrices, to prove a still
more general lemma on sumsets which implies many of the combinatorial bounds
used in applications so far. Loosely speaking, we show that the sumset $S+T$
of two large subsets $S$ and $T$ of $\mathbb{F}_{q}^{n}$ can be expressed
“more efficiently” as a union of sumsets of smaller subsets.

We first introduce some notation. Write $m_{d}$ for the number of monomials in
$x_{1},\ldots,x_{n}$ with degree at most $(q-1)$ in each variable and total
degree at most $(q-1)n/3$, and write $M(\mathbb{F}_{q}^{n})$ for the upper
bound proved in [ellegijs] for the size of a subset of $\mathbb{F}_{q}^{n}$
with no three-term arithmetic progressions; to be precise, we have

$M(\mathbb{F}_{q}^{n})=3m_{(q-1)n/3}$

and $M(\mathbb{F}_{q}^{n})$ is bounded above by $c^{n}$ for some $c<q$. (We
note that for the sake of the present argument there is no need to consider
prime powers $q$ other than primes.)

######  Theorem 1.

Let $\mathbb{F}_{q}$ be a finite field and let $S,T$ be subsets of
$\mathbb{F}_{q}^{n}$. Then there is a subset $S^{\prime}$ of $S$ and a subset
$T^{\prime}$ of $T$ such that

  * •

$|S^{\prime}|+|T^{\prime}|\leq M(\mathbb{F}_{q}^{n})$;

  * •

$(S^{\prime}+T)\cup(S+T^{\prime})=S+T$.

Applying Theorem 1 to the symmetric case $S=T$, we obtain the following
corollary:

######  Corollary 2.

Let $S$ be a subset of $\mathbb{F}_{q}^{n}$. Then $S$ has a subset
$S^{\prime}$ of size at most $M(\mathbb{F}_{q}^{n})$ such that
$S^{\prime}+S=S+S$.

###### Proof.

By Theorem 1 there are subsets $S_{1}$ and $S_{2}$ of $S$ such that
$S+S=(S_{1}+S)\cup(S+S_{2})$ and $|S_{1}|+|S_{2}|\leq M(\mathbb{F}_{q}^{n})$.
Taking $S^{\prime}$ to be $S_{1}\cup S_{2}$ we are done. ∎

This immediately implies the bound proved in [ellegijs] on subsets of
$\mathbb{F}_{q}^{n}$ with no three terms in arithmetic progression:

######  Corollary 3 ([ellegijs]).

A subset $S$ of $\mathbb{F}_{q}^{n}$ containing no three-term arithmetic
progression has size at most $M(\mathbb{F}_{q}^{n})$.

###### Proof.

If $S$ has no 3-term arithmetic progression, then $S^{\prime}+S$ is strictly
smaller than $S+S$ for every proper subset $S^{\prime}\subset S$ (because
$S^{\prime}+S$ fails to contain $2s$ if $s$ lies in the complement of
$S^{\prime}$.) Thus, the subset $S^{\prime}$ guaranteed by Corollary 2 must be
equal to $S$, whence $|S|=|S^{\prime}|\leq M(\mathbb{F}_{q}^{n})$. ∎

Theorem 1 also implies the bounds on multi-colored sum-free sets proved in
[kleinberg] and [blasiak]. (We note that [blasiak] proves a substantially more
general result which applies, for example, to arbitrary abelian groups of
bounded exponent.)

######  Corollary 4 (Th 1, [kleinberg]).

Let $S,T$ be subsets of $\mathbb{F}_{q}^{n}$ of the same cardinality $N$,
assigned an ordering $s_{1},\ldots s_{N}$ and $t_{1},\ldots,t_{N}$ such that
the equation $s_{i}+t_{i}=s_{j}+t_{k}$ holds only when $(j,k)=(i,i)$. Then
$N\leq M(\mathbb{F}_{q}^{n})$.

###### Proof.

Let $S^{\prime},T^{\prime}$ be chosen as in Theorem 1. Each sum $s_{i}+t_{i}$
therefore lies in either $S+T^{\prime}$ or $S^{\prime}+T$. But since
$s_{i}+t_{i}$ cannot be expressed as $s_{j}+t_{k}$ for any other $j,k$, this
implies that either $s_{i}\in S^{\prime}$ or $t_{i}\in T^{\prime}$. It follows
that $N\leq|S^{\prime}|+|T^{\prime}|\leq M(\mathbb{F}_{q}^{n})$. ∎

We now prove Theorem 1. The proof is along the same lines as the arguments in
the papers cited, but there is one new ingredient: a result of Meshulam
[meshulam:rank] on linear spaces of matrices of low rank.

###### Proof.

Let $V$ be the space of polynomials in $\mathbb{F}_{q}[x_{1},\ldots,x_{n}]$
with degree at most $q-1$ in each variable and total degree at most $d$, that
vanish on the complement of $S+T$. Then $\dim V$ is at least
$m_{d}-q^{n}+|S+T|$. Write $\mathcal{M}$ for the space of of $|S|\times|T|$
matrices, where the rows are understood to be indexed by $S$ and the columns
by $T$.

For each $P\in V$ we may consider the matrix $M(P)\in\mathcal{M}$ whose
entries are $P(s+t)_{s\in S,t\in T}$. By the argument of the Croot-Lev-Pach
lemma [CLP], this matrix has rank at most $2m_{d/2}$.

Note that $M$ is a homomorphism from $V$ to $\mathcal{M}$, which is injective:
if $P$ lies in the kernel, it vanishes at $S+T$, but $P$ vanishes on the
complement of $S+T$, so $P$ vanishes on every point of $\mathbb{F}_{q}^{n}$
and is $0$.

We thus can, and shall, think of $V$ as a vector subspace of $\mathcal{M}$ of
dimension at least $m_{d}-q^{n}+|S+T|$, each of whose members has rank at most
$2m_{d/2}$.

The arguments of [ellegijs],[kleinberg],[blasiak] proceed by showing that, if
$S,T$ satisfy the conditions Corollary 4, then $V$ contains a diagonal matrix
with at least $m_{d}-q^{n}+|S|$ nonzero entries, which implies

$m_{d}-q^{n}+|S|\leq 2m_{d/2},$

an upper bound on $|S|$. The mild novelty of the present paper is to exploit
the Croot-Lev-Pach rank bound for the whole space $V$, not just for its
subspace of diagonal matrices. The earlier papers use the easy fact that a
vector space of diagonal matrices of dimension at least $r$ contains a matrix
of rank at least $r$. For spaces of general matrices, the problem of
controlling the maximal rank attained in a linear space of matrices is much
richer. We will use a theorem of Meshulam [meshulam:rank, Theorem 1] in this
area, which (rather surprisingly to us) turns out to be perfectly adapted to
the combinatorial application. (Indeed, we did not set out to prove Theorem 1;
rather, we encountered Meshulam’s theorem and simply worked out what it had to
say about sumsets when combined with the argument of [ellegijs].)

In the interest of self-containedness, we state Meshulam’s theorem below.

######  Theorem 5 (Meshulam).

Let $k$ be a field and $W$ a vector subspace of $M_{n}(k)$. For each $w\in W$
let $p(w)\in\\{1,\ldots,n\\}\times\\{1,\ldots,n\\}$ be the lexicographically
first $(i,j)$ such that the entry $w_{ij}$ is nonzero, and let $\Sigma$ be the
set of all $p(w)$ as $w$ ranges over $W$. Suppose every matrix in $W$ has rank
at most $r$. Then there exists a set of $m$ rows and $m^{\prime}$ columns such
that every element of $\Sigma$ is contained in one of the rows or one of the
columns, and $m+m^{\prime}\leq r$.

We now return to the proof of Theorem 1. Choose an ordering on $S$ and an
ordering on $T$. These choices endow the entries of a matrix in $\mathcal{M}$
with a lexicographic order. As above, for each matrix $A\in\mathcal{M}$, we
denote by $p(A)\in S\times T$ the location of the lexicographically first
nonzero entry of $A$.

We note that $p(M(P))$ cannot be an arbitrary element of $S\times T$, since
$M(P)$ has equal entries at $(s,t)$ and $(s^{\prime},t^{\prime})$ whenever
$s+t=s^{\prime}+t^{\prime}$. In particular, this means that $(s,t)$ and
$(s^{\prime},t^{\prime})$ cannot both be $p(M(P))$ for polynomials $P\in V$;
only the lexicographically prior of these two pairs can appear.

By Gaussian elimination, there is a basis $A_{1},\ldots,A_{\dim V}$ for $V$
such that $p(A_{1}),\ldots,p(A_{\dim V})$ are distinct. Now apply Theorem 5,
which shows that there is a set of $2m_{d/2}$ lines (a line being a row or a
column) whose union contains $p(A_{i})$ for all $i$.

This set of lines consists of a subset of $S$, which we call $S_{0}$, and a
subset of $T$, which we call $T_{0}$, satisfying $|S_{0}|+|T_{0}|=2m_{d/2}$.

We now have, for $i=1,\ldots,\dim V$,

$p(A_{i})=(s_{i},t_{i})$

with either $s_{i}\in S_{0}$ or $t_{i}\in T_{0}$. What’s more, $s_{i}+t_{i}$
and $s_{j}+t_{j}$ are distinct whenever $i$ and $j$ are. So the union of
$S_{0}+T$ with $S+T_{0}$ contains at least $\dim V$ elements of $S+T$.

Since $\dim V\geq m_{d}-q_{n}+|S+T|$, the set $W$ of elements of $S+T$ not
contained in $(S_{0}+T)\cup(S+T_{0})$ has cardinality at most $q_{n}-m_{d}$.
Let $S_{1}$ be a subset of $S$ of size $q_{n}-m_{d}$ such that each $w\in W$
is represented as $s+t$ for some $s\in S_{1}$. Then taking
$S^{\prime}=S_{0}\cup S_{1}$ and $T^{\prime}=T_{0}$, we have that
$S^{\prime}+T\cup S+T^{\prime}$ contains all of $S+T$; moreover,

$|S^{\prime}|+|T^{\prime}|\leq 2m_{d/2}+q^{n}-m_{d}$

and minimizing over $d$ we get the desired result. ∎

######  Remark 6.

We note that the algebraic approach to bounding sumsets is much older than
[CLP] and [ellegijs]; one ancestor, for instance, is Alon’s short proof of the
Erdős-Heilbronn conjecture via combinatorial Nullstellensatz [alon, Prop 4.2],
which also proceeds by considering algebraic properties of a polynomial
vanishing on the set of distinct sums in an abelian group (in that case a
cyclic group.)

######  Question 7.

Corollary 4, the bound on multi-colored sum-free sets, can be expressed in a
more symmetric, and thus more appealing, form: Suppose $S,T,U$ are subsets of
$\mathbb{F}_{q}^{n}$ such that the set

$\\{(s,t,u)\in S\times T\times U:s+t+u=0\\}$

forms a perfect matching between the three sets. Then $|S|=|T|=|U|$ is at most
$M(\mathbb{F}_{q}^{3})$. The proof, too, has a symmetric formulation; Tao
introduced the notion of slice rank for tensors in
$\mathbb{F}_{q}^{n}\otimes\mathbb{F}_{q}^{n}\otimes\mathbb{F}_{q}^{n}$, which
was quickly generalized in many directions and applied to a range of further
combinatorial problems (see e.g. [naslund:multi].)

Symmetric methods of this type seem to be the most elegant way to approach
these problems. Is there a way to state Theorem 1, and prove it, as a
statement about solutions to $s+t+u=0$ which places the three summands on an
equal footing?

######  Question 8.

One naturally wonders whether Theorem 1 has an analogue for cyclic groups.
That is: let $g(N)$ be the smallest integer such that, for any subsets $S$ and
$T$ of $\mathbb{Z}/N\mathbb{Z}$, there are always $S^{\prime}\subset S$ and
$T^{\prime}\subset T$ with $(S+T^{\prime})\cup(S^{\prime}+T)=S+T$ and
$|S^{\prime}|+|T^{\prime}|\leq g(N)$. What can we say about the growth of
$g(N)$? Behrend’s example [behrend] of a large subset of
$\mathbb{Z}/N\mathbb{Z}$ with no three-term arithmetic progressions shows that
$g(N)$ would have to be at least $N^{1-\epsilon}$. Jacob Fox and Will Sawin
explained to me that $g(N)=o(N)$ follows from known bounds for arithmetic
triangle removal.

## Acknowledgments

The author is supported by NSF Grant DMS-1402620 and a Guggenheim Fellowship.
He thanks Jacob Fox, Will Sawin, the referees, and the readers of
Quomodocumque for useful discussions about the subject of this paper.

## References

[pgom]

Jordan S. Ellenberg
Professor
University of Wisconsin-Madison
ellenbermathwiscedu
http://www.math.wisc.edu/ ellenber