# Deep learned SVT: Unrolling singular value thresholding to obtain better MSE

Siva Shanmugam* Sheetal Kalyani *The authors are with the Department of
Electrical Engineering, Indian Institute of Technology Madras, Chennai, India
600 036. Email: ee17s024<EMAIL_ADDRESS>
###### Abstract

Affine rank minimization problem is the generalized version of low rank matrix
completion problem where linear combinations of the entries of a low rank
matrix are observed and the matrix is estimated from these measurements. We
propose a trainable deep neural network by unrolling a popular iterative
algorithm called the singular value thresholding (SVT) algorithm to perform
this generalized matrix completion which we call Learned SVT (LSVT). We show
that our proposed LSVT with fixed layers (say $T$) reconstructs the matrix
with lesser mean squared error (MSE) compared with that incurred by SVT with
fixed (same $T$) number of iterations and our method is much more robust to
the parameters which need to be carefully chosen in SVT algorithm.

###### Index Terms:

Affine rank minimization, deep neural network, generalized matrix completion,
singular value thresholding.

##  I Introduction

The problem of completing a low rank matrix by sampling only a few of its
entries is a well studied problem which finds its application in variety of
areas a few of which include Euclidean distance matrix completion [1],
environmental monitoring using sensors [2] [3], array signal processing [4],
beamforming [5] and wireless channel estimation [6]. In [7] the authors showed
that its possible to perfectly complete low rank matrix by observing only a
few entries and by solving a convex optimization problem.

The generalized low rank matrix completion problem in which a number of linear
combinations of its entries are measured as opposed to sampling the entries
directly has also attracted a lot of attention. The problem of reconstructing
finite dimensional quantum states is naturally a generalized matrix completion
problem [8], [9]. In [10], the affine rank minimization problem which
minimizes the rank of the matrix with affine constraints was proposed for
solving this generalized matrix completion. The work in [11] quantified the
number of measurements required for the success of matrix recovery from its
linear measurements. In [12] authors proposed the power factorization
algorithm for generalized matrix completion and the idea was further extended
in [13]. In [14], the authors extended the power factorization algorithm to
estimate sparse low rank matrix whose left and right singular matrices are
sparse. The recovery of positive semidefinite matrix in the context of
generalized matrix completion has been analyzed in [15] and [16]. The singular
value thresholding (SVT) [17] algorithm is a very popular algorithm used for
performing matrix completion and generalized matrix completion.

The capability of computing machines to store and process a huge amount of
data and the capability of neural networks to learn very complicated functions
have enabled the deep networks to find its roots in almost all fields.
However, it has been very hard to interpret these deep neural networks. In
this context, unrolled algorithms which are deep neural networks whose
architecture is inspired from interpretable classical algorithms have
attracted considerable attention recently [18]. We present a deep neural
network inspired from SVT algorithm for general matrix completion which
reconstructs matrix with significantly lower MSE and is more robust to the
parameters that need to be carefully chosen in SVT.

###  I-A Our contributions and the outline of work

In this paper, we design a trainable deep neural network to perform affine
rank minimization by unrolling the SVT algorithm. Each layer of the deep
network is similar to a single iteration of the SVT algorithm except that the
parameters such as measurement matrices, the step sizes, threshold values used
in the SVT are now learnable. We term the proposed method Learned SVT (LSVT).
The advantages of the proposed method are as follows. Firstly, the proposed
LSVT outperforms SVT meaning that our network with $T$ layers reconstructs the
matrix with lesser mean squared error (MSE) compared with the MSE incurred by
SVT with fixed (same $T$) number of iterations. Secondly, LSVT seems more
robust to the initialization than SVT in all our empirical results.

###  I-B Notations used

Matrices, vectors and scalars are represented by upper case, bold lower case
and lower case respectively. $\operatorname{Tr}[A],\left\lVert
A\right\rVert_{F}$ and $\left\lVert A\right\rVert_{tr}$ denote trace,
Frobenius norm and nuclear norm of matrix $A$ respectively where nuclear norm
is the sum of singular values of $A$. The $i^{th}$ element of $\bm{b}$ is
denoted by $b_{i}$ and $\left\lVert\bm{b}\right\rVert_{2}$ denotes the
Euclidean norm of $\bm{b}$.

##  II Problem formulation

Let $X\in\mathbb{R}^{d\times d}$ be the true matrix to be recovered and $r$ be
the rank of $X$. Note that, in general, we need $d^{2}$ measurements of the
matrix $X$ to get the complete information about the matrix $X$. This holds
when the matrix is of full rank. But the low rank structure enables the
recovery of $X$ from its fewer than $d^{2}$ measurements. For a rank-$r$
matrix, the degree of freedom reduces from $d^{2}$ to $r\times(2d-r)$. Let
$\\{A_{i}\in\mathbb{R}^{d\times d}\\}_{i=1}^{m}$ be a set of $m$ ($m<d^{2}$)
measurement matrices such that
$\operatorname{Tr}[A_{i}^{T}A_{j}]=\delta_{ij}$. Let $\bm{b}\in\mathbb{R}^{m}$
be $m$ linear measurements of the matrix $X$ which are given as

$b_{i}=\operatorname{Tr}[A_{i}X],\quad\forall\,i=1,\dots m$ (1)

In other words, $\bm{b}$ is the linear function of the unknown matrix $X$
where the linear map $\mathcal{A}:\mathbb{R}^{d\times d}\to\mathbb{R}^{m}$
(also called the sampling operator) is defined as

$\mathcal{A}(X)=\begin{bmatrix}\operatorname{Tr}[A_{1}X]&\operatorname{Tr}[A_{2}X]&\dots&\operatorname{Tr}[A_{m}X]\end{bmatrix}^{T}$
(2)

The problem that we consider in this paper is to recover the matrix $X$ from
the measurements $\bm{b}$ assuming that the measurement matrices are known.
The matrix recovery is done by solving the affine rank minimization problem
given as

$\displaystyle\\!\min_{X\in\mathbb{R}^{d\times d}}$
$\displaystyle\text{Rank}(X)$ (3a) such that
$\displaystyle\mathcal{A}(X)=\bm{b}$ (3b)

where $\mathcal{A}$ is the linear map as defined in (2). The affine rank
minimization problem (3) minimizes the rank of the matrix within an affine
constraint set $\\{X:\mathcal{A}(X)=\bm{b}\\}$ which is a level set of the
linear map $\mathcal{A}$.

We design a deep neural network inspired from SVT [17] algorithm to solve the
affine rank minimization formulated in (3). First, we present the SVT
algorithm in the next section then in subsequent sections we design a neural
network by unrolling the iterations of the SVT algorithm.

$\displaystyle\mathcal{A}(.\
;{\color[rgb]{0.82,0.01,0.11}\definecolor[named]{pgfstrokecolor}{rgb}{0.82,0.01,0.11}W}{\color[rgb]{0.82,0.01,0.11}{}_{t}})\
$$\displaystyle+$$\displaystyle-$$\displaystyle+$$\displaystyle\mathbf{b}$$\displaystyle{\mathbf{y}_{t}}_{-1}$$\displaystyle{\mathbf{y}_{t}}$$\displaystyle
X_{t}$Hidden layer - $\displaystyle t$Hidden layer - $\displaystyle
t+1$$\displaystyle\mathcal{D}_{{\color[rgb]{0.82,0.01,0.11}\definecolor[named]{pgfstrokecolor}{rgb}{0.82,0.01,0.11}\tau}{\color[rgb]{0.82,0.01,0.11}{}_{t}}}(.)\
$$\displaystyle\mathcal{A}^{*}(.\
;{\color[rgb]{0.82,0.01,0.11}\definecolor[named]{pgfstrokecolor}{rgb}{0.82,0.01,0.11}W}{\color[rgb]{0.82,0.01,0.11}{}_{t}})\
$$\displaystyle{\mathbf{y}_{t+1}}$$\displaystyle\mathbf{b}$$\displaystyle{\color[rgb]{0.83,0.07,0.07}\definecolor[named]{pgfstrokecolor}{rgb}{0.83,0.07,0.07}\delta}{\color[rgb]{0.83,0.07,0.07}{}_{t}}$$\displaystyle{\color[rgb]{0.83,0.07,0.07}\definecolor[named]{pgfstrokecolor}{rgb}{0.83,0.07,0.07}\delta}{\color[rgb]{0.83,0.07,0.07}{}_{t}}$$\displaystyle\mathcal{A}(.\
;{\color[rgb]{0.82,0.01,0.11}\definecolor[named]{pgfstrokecolor}{rgb}{0.82,0.01,0.11}W}{\color[rgb]{0.82,0.01,0.11}{}_{t+1}})\
$$\displaystyle+$$\displaystyle-$$\displaystyle+$$\displaystyle
X_{t+1}$$\displaystyle\mathcal{D}_{{\color[rgb]{0.82,0.01,0.11}\definecolor[named]{pgfstrokecolor}{rgb}{0.82,0.01,0.11}\tau}{\color[rgb]{0.82,0.01,0.11}{}_{t+1}}}(.)\
$$\displaystyle\mathcal{A}^{*}(.\
;{\color[rgb]{0.82,0.01,0.11}\definecolor[named]{pgfstrokecolor}{rgb}{0.82,0.01,0.11}W}{\color[rgb]{0.82,0.01,0.11}{}_{t+1}})\
$$\displaystyle{\color[rgb]{0.83,0.07,0.07}\definecolor[named]{pgfstrokecolor}{rgb}{0.83,0.07,0.07}\delta}{\color[rgb]{0.83,0.07,0.07}{}_{t+1}}$$\displaystyle{\color[rgb]{0.83,0.07,0.07}\definecolor[named]{pgfstrokecolor}{rgb}{0.83,0.07,0.07}\delta}{\color[rgb]{0.83,0.07,0.07}{}_{t+1}}$
(a) Hidden layers of the Learned SVT network. Two hidden layers connected
sequentially are depicted.

$\displaystyle\mathcal{D}_{{\color[rgb]{0.82,0.01,0.11}\definecolor[named]{pgfstrokecolor}{rgb}{0.82,0.01,0.11}\tau}{\color[rgb]{0.82,0.01,0.11}{}_{T}}}(.)\
$$\displaystyle\mathcal{A}^{*}(.\
;{\color[rgb]{0.82,0.01,0.11}\definecolor[named]{pgfstrokecolor}{rgb}{0.82,0.01,0.11}W}{\color[rgb]{0.82,0.01,0.11}{}_{T}})\
$$\displaystyle\mathbf{y}_{T-1}$$\displaystyle X_{out}$Output
layer$\displaystyle b$ (b) Output layer of the Learned SVT network.

Hidden layer-1 Hidden layer-T
$\displaystyle{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\delta_{0}}b$$\displaystyle
X_{out}$ Output layer $\displaystyle\dotsc$ (c) The architechture of the LSVT
network

Figure 1: Deep neural network for the Learned SVT. The variables in red are
learnable parameters.

##  III SVT algorithm

SVT algorithm solves affine rank minimization formulated in (3) by minimizing
the nuclear norm of the matrix which is a surrogate to the rank function.
Specifically, the convex optimization problem that the SVT solves is given as
[17]

$\displaystyle\\!\min_{X\in\mathbb{R}^{d\times d}}$
$\displaystyle\tau\left\lVert X\right\rVert_{tr}+\frac{1}{2}\left\lVert
X\right\rVert_{F}^{2}$ (4a) such that $\displaystyle\mathcal{A}(X)=\bm{b}$
(4b)

where $\tau>0$ is a constant and the map $\mathcal{A}$ is as defined in (2).
In theorem 3.1 of [17], authors proved that in the limit $\tau$ tending to
infinity, the solutions to (4) converge to the matrix with minimum trace norm
that is also consistent with the measurements i.e., ($\mathcal{A}(X)=\bm{b}$).
In [10] authors proved that minimizing the nuclear norm yields the minimum
rank solution with high probability (see theorem 3.3 and theorem 4.2 of [10]).
Hence SVT minimizes rank formulated in (3) by solving (4).

Note that the problem (4) is a contrained convex optimization problem and the
strong duality holds for the problem [19]. The Lagrangian function for the
problem is given as

$\mathcal{L}(X,\bm{y})=\tau\left\lVert
X\right\rVert_{tr}+\frac{1}{2}\left\lVert
X\right\rVert_{F}^{2}+\bm{y}^{T}(\bm{b}-\mathcal{A}(X))$ (5)

where $X$ is the optimization variable and $\bm{y}$ is the Lagrangian
variable. Since strong duality holds for the problem, finding the saddle point
$(X^{*},\bm{y}^{*})$ of the Lagrangian $\mathcal{L}(X,\bm{y})$ gives the
solution ($X^{*}$) to (4). The saddle point is written as

$\underset{\bm{y}}{\sup}\,\underset{X}{\inf}\,\mathcal{L}(X,\bm{y})=\mathcal{L}(X^{*},\bm{y}^{*})=\underset{X}{\inf}\,\underset{\bm{y}}{\sup}\,\mathcal{L}(X,\bm{y})$
(6)

Authors in [17] used Uzawa’s iterations [20] to find the saddle point of the
Lagrangian. Uzawa’s iterations starts with an initial $\bm{y}^{0}$ and repeats
two steps until convergence. In the first step, the minimizer (say $X^{k}$) of
$\mathcal{L}(.,\bm{y})$ for the given $\bm{y}$ is found. In the second step, a
gradient ascent step is taken along the direction $\bm{y}$ for the given
$X^{k}$ found in the previous step. These steps are given as follows

$\displaystyle\begin{cases}X^{k}&=\underset{X}{\arg\min}\,\mathcal{L}(X,\bm{y}^{k-1})\\\
\bm{y}^{k}&=\bm{y}^{k-1}+\delta_{k}\nabla_{\bm{y}}\mathcal{L}(X^{k},\bm{y})\end{cases}$
(7)

where $\delta_{k}>0$ is the step size used for gradient ascent in the $k^{th}$
iteration. The gradient $\nabla_{\bm{y}}\mathcal{L}(X^{k},\bm{y})$ is given as
$\mathcal{A}(X^{k})-\bm{b}$. The closed form solution to the minimization
problem in (7) is given as

$\underset{X}{\arg\min}\,\mathcal{L}(X,\bm{y}^{k-1})=\mathcal{D}_{\tau}(\mathcal{A}^{*}(\bm{y}^{k-1}))$
(8)

where the operator $\mathcal{A}^{*}:\mathbb{R}^{m}\to\mathbb{R}^{d\times d}$
is the adjoint of the linear map $\mathcal{A}$ and is defined as

$\mathcal{A}^{*}(\bm{y})=\sum_{i=1}^{m}y_{i}A_{i}^{T}$ (9)

and the operator $\mathcal{D}_{\tau}:\mathbb{R}^{d\times
d}\to\mathbb{R}^{d\times d}$ is the singular value thresholding operator and
is defined as

$\mathcal{D}_{\tau}(X)=U\mathcal{D}_{\tau}(\Sigma)V^{T}$ (10)

where the singular value decomposition of $X$ is given as $X=U\Sigma V^{T}$,
$\Sigma$ is the diagonal matrix with the singular values of $X$ in its
diagonal positions which we write as
$\Sigma=\text{diag}(\sigma_{1}(X),\dots\sigma_{r}(X))$ where $r$ represents
the rank of $X$. $\mathcal{D}_{\tau}(\Sigma)$ is a diagonal matrix whose non
zero entries are found by soft thresolding the entries of $\Sigma$ and is
given as
$\mathcal{D}_{\tau}(\Sigma)=\text{diag}(\max(\sigma_{1}(X)-\tau,0),\dots\max(\sigma_{r}(X)-\tau,0))$.
Using the gradient of $\mathcal{L}$ along $\bm{y}$ and the equations (8), (9)
and (10) Uzawa’s iterations (7) can be rewritten as

$\displaystyle\begin{cases}X^{k}&=\mathcal{D}_{\tau}(\mathcal{A}^{*}(\bm{y}^{k-1}))\\\
\bm{y}^{k}&=\bm{y}^{k-1}+\delta_{k}(\bm{b}-\mathcal{A}(X^{k}))\end{cases}$
(11)

where $\delta_{k}>0$ is the stepsize to do gradient ascent, $\tau>0$ is the
threshold value used in singular value thresholding operator and the maps
$\mathcal{A}$ and $\mathcal{A}^{*}$ are defined using the measurement matrices
$A_{1}$ through $A_{m}$ (given in (2) and (9)).

SVT algorithm repeatedly performs the steps in (11) which requires the
knowledge of the right choice of $\delta_{k}$ and $\tau$ to solve the affine
rank minimization problem (3). In the subsequent sections, we design a
trainable deep network based on the steps in (11) for performing affine rank
minimization that demands no such tunable parameters.

##  IV Learned SVT

In this section, we design a deep neural network based on the SVT algorithm
discussed in the previous section and present a training method to train the
network for performing affine rank minimization.

###  IV-A Network Architecture

Recall that in each iteration of SVT (11), two steps are performed. We first
design a single hidden layer of our network which performs these two steps. To
do so, we see that the steps (11) can be rewritten as

$\bm{y}_{t}=\bm{y}_{t-1}+\delta_{t}\left[\bm{b}-\mathcal{A}(\mathcal{D}_{\tau}(\mathcal{A}^{*}(\bm{y}_{t-1})))\right]$
(12)

where $\bm{y}_{t}$ would represent the output of the $t^{th}$ hidden layer. It
can be seen from this reformulation that performing (12) $T$ times is
equivalent to running the SVT algorithm for $T$ iterations. We design the deep
network wherein each hidden layer perform (12) 111$\mathcal{D}_{\tau}(.)$ in
(12) is the singular value thresholding (SVT) operator. Note that the recent
work on RPCA [21] also designed a neural network which uses SVT in its layers
and backpropagates through it. To obtain a matrix as the output, we add an
output layer at the end of the network which performs the first step of (11).

To unroll a fixed number (say $T$) of SVT iterations, we build $T-1$ hidden
layers and an output layer and connect them sequentially. Hence, a $T$ layered
unrolled network and the SVT algorithm that runs for a fixed $T$ number of
iterations are comparable and they are one and the same when the maps
$\mathcal{A},\mathcal{A}^{*}$ and the parameters $\delta_{t}$, $\tau_{t}$ used
in both algorithms are same.

We denote by $W_{t}$ the measurements matrices $A_{1}$ through $A_{m}$ used in
the maps $\mathcal{A}$ and $\mathcal{A}^{*}$ and make it learnable. Here
$W_{t}$ is an $m\times d^{2}$ matrix whose $i^{th}$ row is formed from the
entries of $A_{i}$ such that the measurement vector $\bm{b}$ given in (1) can
be written as $W_{t}vec(X)$. By making this pair
$\\{\mathcal{A},\mathcal{A}^{*}\\}$ learnable we try to leverage the power of
deep learning to obtain an unrolled variant of SVT which performs better than
SVT (which has fixed known pair of $\\{\mathcal{A},\mathcal{A}^{*}\\}$. We
denote by $\delta_{t}$ the step size used in the $t^{th}$ layer and by
$\tau_{t}$ the threshold used in the $t^{th}$ layer and we also make these
learnable. With these learnable parameters, the complete network architecture
is depicted in Fig. 1 where Fig. 1(a) depicts the hidden layers of our
unrolled network and Fig. 1(b) depicts the output layer of our network.

###  IV-B Training the network

Consider a Learned SVT network with $T$ layers as discussed in previous
subsection. The input to this network is $\bm{y}_{0}\in\mathbb{R}^{m}$ and the
output of the network is a matrix $\hat{X}\in\mathbb{R}^{d\times d}$. From
(12) it can be seen that if $\bm{y}_{0}$ was a zero vector, $\bm{y}_{1}$ would
then be $\delta\bm{b}$. Hence we feed the network with
$\bm{y}_{0}=\delta_{0}\bm{b}$ to recover the corresponding matrix $X$. Note
that we can also feed the network with zero vector and compare its performance
with SVT whose input is also zero vector. We denote by $\Theta$ the set of all
learnable parameters in the network i.e., $\Theta=\\{W_{1},\dots
W_{T},\delta_{0},\delta_{1},\dots\delta_{T},\tau_{1},\dots\tau_{T}\\}$. With
this notation, the output of the network for a given measurement vector (say
$\bm{b}$) is written as

$\hat{X}=f_{\Theta}(\bm{b})$ (13)

We denote the training dataset by $\\{X^{(i)},\bm{b}^{(i)}\\}_{i=1}^{M}$ where
$\bm{b}^{(i)}\in\mathbb{R}^{m}$ is the measurement vector of the matrix
$X^{(i)}\in\mathbb{R}^{d\times d}$ obtained using the known measurement
matrices $A_{1}$ through $A_{m}$ as described in (1). For our numerical
simulations, which we discuss in the next section, we generate the measurement
matrices and $\\{X^{(i)}\\}$ synthetically. Then we obtain
$\\{\bm{b}^{(i)}\\}$ using (2) as
$\bm{b}^{(i)}=\mathcal{A}(X^{(i)};A_{1},\dots A_{m})$. We train our network to
minimize the mean squared error (MSE) between the matrices $\\{X^{(i)}\\}$ in
the training dataset and the estimated matrices $f_{\Theta}(\bm{b}^{(i)})$.
The MSE loss is given as

$\ell\\{\Theta;\\{X^{(i)},\bm{b}^{(i)}\\}\\}=\frac{1}{M}\sum_{i=1}^{M}\left\lVert
X^{(i)}-f_{\Theta}(\bm{b}^{(i)})\right\rVert_{F}^{2}$ (14)

| Iterations/
---
Layers
2 | 3 | 4 | 5 | 6
Rank(r) | SVT | LSVT | SVT | LSVT | SVT | LSVT | SVT | LSVT | SVT | LSVT
1 | 2.3166 | 0.2234 | 0.8655 | 0.0687 | 0.4269 | 0.0300 | 0.2240 | 0.0174 | 0.1460 | 0.0158
2 | 4.0590 | 0.1594 | 1.2707 | 0.0268 | 0.4320 | 0.0086 | 0.1826 | 0.0053 | 0.0969 | 0.0013
3 | 5.3233 | 0.4035 | 1.8576 | 0.0913 | 0.8466 | 0.0370 | 0.4532 | 0.0184 | 0.2748 | 0.0107

TABLE I: MSE in estimating 10 x 10 matrix by SVT and LSVT for different
layers.

| Iterations/
---
Layers
2 | 3 | 4 | 5 | 6
Rank(r) | SVT | LSVT | SVT | LSVT | SVT | LSVT | SVT | LSVT | SVT | LSVT
2 | 4.6028 | 0.5565 | 1.4991 | 0.1630 | 0.7064 | 0.0693 | 0.3738 | $\mathbf{0.2690}^{@}$ | 0.2538 | $\mathbf{0.1364}^{@}$
4 | 8.3921 | 0.4007 | 2.5227 | 0.0784 | 0.8701 | 0.0893 | 0.3832 | 0.0942 | 0.2224 | 0.0097
6 | 10.9441 | 1.008 | 3.9163 | 0.2498 | 1.7994 | 0.2904 | 0.9914 | 0.0471 | 0.6328 | 0.0564

TABLE II: MSE in estimating 20 x 20 matrix by SVT and LSVT for different
layers.

###  IV-C Initialization and training

We initialize the network’s trainable parameters $\Theta$ with those used in
SVT algorithm. We initialize each of $\\{W_{t}\\}$ with the measurement
matrices $A_{1}$ through $A_{m}$. Each of the stepsizes
$\\{\delta_{0},\delta_{1},\dots\delta_{T}\\}$ is initialized to
$1.2\times\frac{d^{2}}{m}$ and each of the thresholds
$\\{\tau_{1},\dots\tau_{T}\\}$ is initializes to $5\times d$ as these values
were adapted by the authors of SVT for better results. Since we initialize our
network with the parameters used in SVT algorithm, our networks performs
similar to SVT (with fixed $T$ number of iterations) initially. We also
initialize the parameters
$\\{\delta_{0},\delta_{1},\dots\delta_{T}\dots\tau_{1}\dots\tau_{T}\\}$ with
values other than the ones used by authors of SVT, to see the dependence of
SVT and LSVT on these parameters. The initial error that the network incurs is
same as that incurred by SVT. We use gradient based optimizer ADAM [22] to
minimize the loss (14) and train the network.

##  V Numerical simulation

We design and train the proposed Learned SVT network to estimate $d\times d$
matrices of rank $r$ from its $m$ linear measurements. The linear map
$\mathcal{A}$ that defines the linear measurements is synthetically generated
and is fixed through out the experiments. To do this we randomly generate the
matrices $A_{1}$ through $A_{m}$ such that
$\operatorname{Tr}[A_{i}^{T}A_{j}]=\delta_{ij}$. We generate 61,000 ground
truth data $\\{X^{(i)}\in\mathbb{R}^{d\times
d},\bm{b}^{(i)}\in\mathbb{R}^{m}\\}_{i=1}^{61,000}$ where $\\{X^{(i)}\\}$ are
of rank-r and $\\{\bm{b}^{(i)}\\}$ are the corresponding measurement vectors.
To do this, we generate $P^{(i)}\in\mathbb{R}^{d\times r}$ and
$Q^{(i)}\in\mathbb{R}^{r\times d}$ randomly with each entry of $P^{(i)}$ and
$Q^{(i)}$ generated from $\mathcal{N}(0,2)$ then we get $X^{(i)}$ by
multiplying $P^{(i)}$ and $Q^{(i)}$. $\bm{b}^{(i)}$ are obtained by measuring
$X^{(i)}$ using the measurement map generated. We use PyTorch to design and
train our LSVT network. PyTorch automatically computes the gradients of the
loss function with respect to the network parameters using computational
graphs and Autograd functionality. We use stochastic gradient descent based
ADAM optimizer with a learning rate of $10^{-4}$ to train the network. We
perform mini batch training with a minibatch size of 1000. Of the 61,000
ground truth data, we use 50,000 to train the network, 10,000 to validate the
network. We validate the network every time the network parameter gets updated
and we stop the training process when this validation loss doesn’t decrease
over the course of training. Once the training is over, we freeze the network
parameters and test the network with the remaining 1000 ground truth data and
the resulted MSE are reported.

LSVT is designed and trained to estimate $10\times 10$ matrices of rank 1, 2
and 3 with different layers. We sampled the rank-1 matrix with a oversampling
ratio of $3$. For rank-2 and rank-3 matrix, 90 linear measurements were
obtained. The MSE in estimating the matrices by both SVT and LSVT algorithms
are compared in Table I. We also estimated $20\times 20$ matrices of ranks 2,
4 and 6. Rank-2 matrices were sampled with oversampling ratio 3. 350 linear
measurements were obtained for rank-4 and rank-6 matrices. The corresponding
MSE values are compared in Table II. The learning rate of $10^{-4}$ is used to
train all the networks except for the values super-scripted by $@$ where
$10^{-5}$ was used. All MSE values are reported by averaging over 1000
instances. It can be seen from Tables I and II that the Learned LSVT performs
much better in terms of MSE in estimating the matrices compared with the
original SVT algorithm.

To study the dependence of SVT and LSVT on the threshold value ($\tau$) and
stepsize $(\delta)$ both algorithms are simulated with different thresholds
($\tau$) and stepsizes ($\delta$) to estimate $20\times 20$ matrices of rank-2
with a oversampling ratio of 3. SVT uses these parameters and performs 4 SVT
iterations, while 4-layered LSVT is initialized with these parameters and
trained. The corresponding MSE values are tabulated in Table III where the $*$
denoted values are the ones used by the authors of SVT. From Table III it can
be seen that even with different initial parameters ($\tau,\delta$) LSVT
always performs better than SVT in terms of MSE.

Parameters | SVT | LSVT
---|---|---
$\tau=5,\delta=1$ | 2.2477 | 0.1831
$\tau=50,\delta=0.5$ | 6.4043 | 0.0479
$\tau=50,\delta=2.10^{*}$ | 0.2536 | 0.0483
$\tau=100^{*},\delta=2.10^{*}$ | 0.7064 | 0.0693
$\tau=200,\delta=5$ | 7.5677 | 0.4287
$\tau=300,\delta=5$ | 8.1711 | 1.2766

TABLE III: Comparing MSE in estimating matrices by SVT and LSVT when different
parameters are used.

##  VI Conclusion

We designed a trainable deep neural network called LSVT by appropriately
unrolling the SVT algorithm. The proposed LSVT with fixed $T$ layers estimates
matrices with significantly lesser mean squared error (MSE) compared with MSE
incurred by SVT with fixed $T$ iterations. We also showed that LSVT
outperforms SVT even when both algorithms use different values for the step
sizes and thresholds rather than those suggested by the authors of SVT [17].

## References

  * [1] H. Zhang, Y. Liu, and H. Lei, “Localization from incomplete euclidean distance matrix: Performance analysis for the svd–mds approach,” _IEEE Transactions on Signal Processing_ , vol. 67, no. 8, pp. 2196–2209, 2019.
  * [2] J. He, Y. Zhou, and G. Sun, “Environmental monitoring in wireless sensor networks using structured matrix completion,” in _GLOBECOM 2020 - 2020 IEEE Global Communications Conference_ , 2020, pp. 1–5.
  * [3] K. Xie, L. Wang, X. Wang, G. Xie, and J. Wen, “Low cost and high accuracy data gathering in wsns with matrix completion,” _IEEE Transactions on Mobile Computing_ , vol. 17, no. 7, pp. 1595–1608, 2018.
  * [4] Z. Weng and X. Wang, “Low-rank matrix completion for array signal processing,” in _2012 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_ , 2012, pp. 2697–2700.
  * [5] J. Wen, X. Zhou, B. Liao, C. Guo, and S. Chan, “Adaptive beamforming in an impulsive noise environment using matrix completion,” _IEEE Communications Letters_ , vol. 22, no. 4, pp. 768–771, 2018.
  * [6] E. Vlachos, G. C. Alexandropoulos, and J. Thompson, “Massive mimo channel estimation for millimeter wave systems via matrix completion,” _IEEE Signal Processing Letters_ , vol. 25, no. 11, pp. 1675–1679, 2018.
  * [7] E. J. Candès and B. Recht, “Exact matrix completion via convex optimization,” _Foundations of Computational mathematics_ , vol. 9, no. 6, pp. 717–772, 2009.
  * [8] D. Gross, Y.-K. Liu, S. T. Flammia, S. Becker, and J. Eisert, “Quantum state tomography via compressed sensing,” _Physical review letters_ , vol. 105, no. 15, p. 150401, 2010.
  * [9] C. Riofrío, D. Gross, S. T. Flammia, T. Monz, D. Nigg, R. Blatt, and J. Eisert, “Experimental quantum compressed sensing for a seven-qubit system,” _Nature communications_ , vol. 8, no. 1, pp. 1–8, 2017.
  * [10] B. Recht, M. Fazel, and P. A. Parrilo, “Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization,” _SIAM review_ , vol. 52, no. 3, pp. 471–501, 2010.
  * [11] D. Gross, “Recovering low-rank matrices from few coefficients in any basis,” _IEEE Transactions on Information Theory_ , vol. 57, no. 3, pp. 1548–1566, 2011.
  * [12] J. P. Haldar and D. Hernando, “Rank-constrained solutions to linear matrix equations using powerfactorization,” _IEEE Signal Processing Letters_ , vol. 16, no. 7, pp. 584–587, 2009.
  * [13] D. Zachariah, M. Sundin, M. Jansson, and S. Chatterjee, “Alternating least-squares for low-rank matrix reconstruction,” _IEEE Signal Processing Letters_ , vol. 19, no. 4, pp. 231–234, 2012.
  * [14] K. Lee, Y. Wu, and Y. Bresler, “Near-optimal compressed sensing of a class of sparse low-rank matrices via sparse power factorization,” _IEEE Transactions on Information Theory_ , vol. 64, no. 3, pp. 1666–1698, 2018.
  * [15] Y. Li, Y. Sun, and Y. Chi, “Low-rank positive semidefinite matrix recovery from corrupted rank-one measurements,” _IEEE Transactions on Signal Processing_ , vol. 65, no. 2, pp. 397–408, 2016.
  * [16] Q. Zheng and J. Lafferty, “A convergent gradient descent algorithm for rank minimization and semidefinite programming from random linear measurements,” in _Advances in Neural Information Processing Systems_ , C. Cortes, N. Lawrence, D. Lee, M. Sugiyama, and R. Garnett, Eds., vol. 28. Curran Associates, Inc., 2015.
  * [17] J.-F. Cai, E. J. Candès, and Z. Shen, “A singular value thresholding algorithm for matrix completion,” _SIAM Journal on optimization_ , vol. 20, no. 4, pp. 1956–1982, 2010.
  * [18] V. Monga, Y. Li, and Y. C. Eldar, “Algorithm unrolling: Interpretable, efficient deep learning for signal and image processing,” _IEEE Signal Processing Magazine_ , vol. 38, no. 2, pp. 18–44, 2021.
  * [19] S. Boyd, S. P. Boyd, and L. Vandenberghe, _Convex optimization_. Cambridge university press, 2004.
  * [20] K. Arrow, H. Chenery, H. Azawa, K. M. R. Collection, L. Hurwicz, H. Uzawa, S. Johnson, S. Karlin, T. Marschak, and R. Solow, _Studies in Linear and Non-linear Programming_ , ser. Stanford mathematical studies in the social sciences. Stanford University Press, 1958\.
  * [21] O. Solomon, R. Cohen, Y. Zhang, Y. Yang, Q. He, J. Luo, R. J. G. van Sloun, and Y. C. Eldar, “Deep unfolded robust pca with application to clutter suppression in ultrasound,” _IEEE Transactions on Medical Imaging_ , vol. 39, no. 4, pp. 1051–1063, 2020.
  * [22] D. P. Kingma and J. Ba, “Adam: A method for stochastic optimization,” in _3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings_ , Y. Bengio and Y. LeCun, Eds., 2015.


# Time to stop and think:
what kind of research do we want to do? ††thanks: Citation: J. Ceberio, B.
Calvo. Time to stop and think: what kind of research do we want to do?

Josu Ceberio, Borja Calvo
Department of Computer Science and Artificial Intelligence
University of the Basque Country UPV/EHU
Donostia-San Sebastian, 20018, Spain
{josu.ceberio<EMAIL_ADDRESS>
manuscript version 3.0

###### Abstract

Experimentation is an intrinsic part of research since it allows for
collecting quantitative observations, validating hypotheses, and providing
evidence for their reformulation. For that reason, experimentation must be
coherent with the purposes of the research, properly addressing the relevant
questions in each case. Unfortunately, the literature is full of works whose
experimentation is neither rigorous nor convincing, oftentimes designed to
support prior beliefs rather than answering the relevant questions.

In this paper, we focus on the field of metaheuristic optimization, since it
is our main field of work, and it is where we have observed the misconduct
that has motivated this letter. Our main goal is to sew the seed of sincere
critical assessment of our work, sparking a reflection process both at the
individual and the community level. Such a reflection process is too complex
and extensive to be tackled as a whole. Therefore, to bring our feet to the
ground, we will include in this document our reflections about the role of
experimentation in the two approaches of conducting research: engineering vs.
scientific.

_K_ eywords Optimization $\cdot$ experimentation $\cdot$ benchmarks $\cdot$
instance generators $\cdot$ research.

##  1 Previous considerations

This manuscript is the result of a growing concern about the way research is
conducted in the field of metaheuristic optimization. However, this concern is
by no means limited to this field. Alarms have been ringing for some time in
many other scientific domains [1, 2, 3, 4]. The problem is extremely complex,
having many dimensions, such as the pressure to publish or the inappropriate
experimental designs and empirical data analysis. Tackling all of these
aspects is out of the scope of this document, but the general picture of the
growing concern is essential to put the ideas collected in this work in
context. To express it with simple words, it seems that research is, to some
extent, going astray, dragged by a sort of long-established inertia that is
not questioned or reviewed.

In such a scenario, rather than trying to blindly push harder, we should stop
for a moment and consider what doing research means, how it should be
conducted, and critically (and sincerely) reflect on how we are doing our
work. We are aware that this is not the first time that scientists have
questioned the way research is conducted and raised their voices to claim the
importance of its quality for progress in our field. Previous manuscripts
before this, such as [5], [6] or [7] seem to arise from similar concerns. We
are not here to replace those works, but to reinforce their message, promoting
the critical questioning of the traditions. For our part, we will focus
specifically on the role of experimentation in the research activity.

Please, keep in mind that all the ideas presented are our personal views on
the topic and, certainly, are subject to discussion (indeed, promoting that
discussion is our main goal).

##  2 Motivation

We have participated with great passion in metaheuristic optimization (and
neighboring fields) for years, and we have published dozens of works in a wide
variety of forums such as international conferences and prestigious journals
in the area. During our research activity, we have also attended many talks,
given others, participated in the review process of several papers, and joined
researchers in many other scientific events. Throughout this activity, we have
seen works (including our own) that have less relevance, while others acquire
greater relevance due to their impact.

Certainly, concepts such as relevance and impact are at the center of this
discussion, as they can only be assessed once we answer one fundamental
question: what is the ultimate goal behind the research activity? We may be
tempted to regard this as a simple, even obvious question but, as we will try
to show in this document, the possible answers to this question will lead us
to consider some aspects of the current research activity in the field as
inappropriate.

To a greater or lesser extent, the development of these works is guided by
existing inertia. While using existing methodologies and approaches is not
necessarily a bad practice, when established traditions are blindly followed
without considering their appropriateness, problems arise. As an example, one
such inertial behavior (not only present in our work as authors but also as
reviewers) is the use of statistical tests without considering their need or
usefulness for the particular situation.

The problem of ‘inertial’ research, which is not exclusive to our research
field, is very nicely illustrated by the questions posed by George Cobb to an
American Statistical Association (ASA) discussion held in 2014 regarding,
precisely, the (not always appropriate) use of statistical tests. This
discussion eventually ended in a statement by the ASA on the use of
$p$-values, which was published in 2016 [8]. The beginning of that publication
summarizes the main idea:

> In February 2014, George Cobb, Professor Emeritus of Mathematics and
> Statistics at Mount Holyoke College, posed these questions to an ASA
> discussion forum:
>
>   * •
>
> Q: Why do so many colleges and grad schools teach p = 0.05?
>
>   * •
>
> A: Because that’s still what the scientific community and journal editors
> use.
>
>   * •
>
> Q: Why do so many people still use p = 0.05?
>
>   * •
>
> A: Because that’s what they were taught in college or grad school.
>
>

>
> Cobb’s concern was a long-worrisome circularity in the sociology of science
> based on the use of bright lines such as p < 0.05: “We teach it because it’s
> what we do; we do it because it’s what we teach.” This concern was brought
> to the attention of the ASA Board.

Similarly, we could ask ourselves why we do, in metaheuristic optimization
(and for that matter, any other field), research the way it is done. The
answer is that it is what we have been taught. Then, we teach our PhD students
to do research in exactly the same way, because it is the way research is done
(and thus, the way to get our work published). Following this loop without any
questioning is one of the reasons behind the undesired behaviors too
frequently observed. In this regard, there is only one way to break the loop:
critically questioning how research is conducted.

##  3 Two approaches to research in metaheuristic optimization

Whenever a new research project is conceived, the very first question to
consider is (or should be) what the specific goal of the research is. Every
work will have one or more specific goals, but behind those specific goals,
there is a basic, fundamental one. It is this fundamental goal that we will
discuss in this section.

Research is a collaborative and incremental activity, where the researcher
conducts specific works, generates some kind of output (some conclusions,
data, etc.), and, eventually, communicates the procedure and the results to
their respective research community, usually by publishing the work in a
certain journal or by presenting it in a conference. The whole point of the
process is that any research work takes some other previous works as a basis
and, in turn, potentially serves as a starting point for further developments.
Indeed, the relevance and impact of a research project can be (and, although
indirectly, is) measured based on the future research works that take it as a
basis.

The use of metaheuristic algorithms to solve optimization problems falls into
the general discipline of applied mathematics. That is, the subject of study
is the mathematical methods that are used to solve real-life problems. As
such, this research area lies somewhere between engineering, and science. This
implies that there is not just one way a research project can contribute to
further developments. We distinguish, in this regard, two different general
approaches, one guided by an engineering goal, and another one that adopts a
scientific perspective. As we will see, the differences in both approaches
have implications in several aspects related to the experimentation required.

Any engineering research work is usually of an applied nature and aims at
resolving a real optimization problem. By real, we mean that there is some
community (customers, a certain institution, some company, etc.) that is
requesting a solution for a problem that they have in their activity. Then,
the research work will probably imply formalizing the optimization problem at
hand and developing a strategy or algorithm for providing an acceptable
solution.

In such a situation, the relevance of the research work (assuming it is
properly tackled) is directly related to the relevance of the problem. That
is, if there is a large community interested (currently or in the future) in
having the best possible solution to that problem, the contribution will have
a potentially high impact. Conversely, if very few people are interested in
the solution per se, research guided solely by the goal of achieving state-of-
the-art results has the risk of being futile.

This train of thought brings us to one of the loops that we keep following
without questioning it: research works where the only goal is to achieve
state-of-the-art results in classical optimization problems, such as the TSP
or the graph coloring problem. The main problem with this kind of research
work does not lie in the use of classical problems but in the lack of interest
in the solutions themselves, as any real optimization problem will, most
certainly, significantly diverge from these simple abstractions. Nevertheless,
year after year we see articles published whose only rationale is to obtain
better results on artificial instances (whose origin in most cases is
obscure). Not only that, but in many cases the reviewers request us to act in
this way.

We are not implying that there should not be research works that propose new
approaches to solving classical problems, but we argue that a sheer
engineering approach is not suitable in these cases.

It is worth noting that research works with the engineering scope do not need
to propose brand-new optimization paradigms. The idea is simpler: the better
the solution/algorithm proposed, the more satisfactory the result. The process
ends by deploying the solution or algorithm in a real context, and confirming
with the customer that it has the quality that was observed during the
experimentation. If this is not confirmed, either the formalization of the
problem or the design of the algorithm needs to be reconsidered (and also the
empirical assessment during the research, as long as it does not match the
real-life results).

Assuming that in an engineering research work the fundamental objective is to
solve a particularly relevant real problem, the experimentation should be
designed to show that, indeed, the proposed solution outperforms any existing
approach in real instances and to quantify, as far as possible, the expected
performance of the proposed solution. In other words, the key to good
experimentation in this approach lies in the instances used to evaluate the
alternatives. Certainly, in many situations, we will not be able to evaluate
the alternatives in all the possible instances111Note that there could be
projects where this is possible, for example when the goal is solving specific
relevant instances and, therefore, we have to develop the assessment of the
algorithms using only a subset of those.

The engineering approach is ultimately a utilitarian one, aimed at solving a
problem in the best possible way. Conversely, the goal of scientific research
is radically different: increasing the knowledge in a particular area. In
metaheuristic optimization, this knowledge can be, for instance, the
explanation of the behavior of a certain algorithm, or an analysis of the
structure of a particular optimization problem. The way we see it, there are
two paths to gaining new knowledge in metaheuristic optimization, through
theoretical mathematical analyses or experimental works.

Let us illustrate the situation with other research areas with a longer
tradition: natural sciences. The ultimate goal of natural sciences is gaining
knowledge about the natural world. This knowledge can be at different levels
of complexity, from the fundamental laws at the atomic level to complex
systems such as the human brain. At the lowest levels of complexity,
mathematical modeling allows working in a purely theoretical plane, but as the
complexity of the subjects of study increases, our modeling capacity becomes
insufficient, and eventually, experimental science is the only way to increase
the body of knowledge.

We can establish a parallelism between natural sciences and (certain domains
of) applied mathematics. The scientific approach aims not just to solve
problems, but to understand them and the algorithms that solve them. In that
regard, simple problems and algorithms are suitable for mathematical
theoretical analyses, which is a classical scientific approach to research in
this area (for example, a runtime analysis of the (1+1)EA on the one max
problem). However, as happens in natural sciences, the complexity of the
situations that are currently being studied has long passed the threshold that
allows for such theoretical analyses, leaving as the only feasible approach
that of experimental sciences (for instance, analyzing the convergence of a
memetic algorithm on an NP-hard problem is usually unaffordable with
mathematical tools).

The parallelism between experimental natural sciences and (experimental?)
applied mathematics can be also extended to the methodology. That is, to
consider how research should be conducted in our field of interest, we can pay
attention to how research is done in experimental natural sciences: the long-
established scientific method.

In the scientific method, the starting point is usually an observation, the
identification of something that strikes us as ‘odd’ or ‘interesting’. Then,
the observed event is then characterized and quantified, obtaining some
experimental data. Considering the collected data, and the current body of
knowledge, the researchers face the challenging task of proposing hypotheses,
i.e., sensible explanations that match the quantitative observations. Then,
the formulated hypotheses are put to the test, usually designing new
experiments to challenge the proposed explanations. The final result of this
process can be the reformulation of the hypotheses if they are not able to
explain the newly collected evidence or the design of new experiments to
further test the hypotheses.

The interest in the scientific approach to research in metaheuristic
optimization is obvious, and certainly, many researchers have taken that path.
However, the perspective of following this path can be daunting, mainly
because we associate this kind of research with the theoretical approach,
rather than with the experimental one, and the degree of mathematical
complexity of the problems and algorithms of interest is, in many cases, far
beyond our capacity to tackle them from a sheer theoretical point of view. It
is like trying to perfectly model the human brain to analyze it
mathematically.

As we have previously said, research is a collaborative and incremental
process. That is particularly true in the scientific approach to research,
where no single work will provide all the answers and information. Conversely,
each individual research should aim at contributing relevant information or
knowledge at any of the steps in the scientific method. Obviously, proposing
hypotheses regarding the functionality of a particular algorithm or the
features of a specific problem is a significant contribution. However,
formulating such hypotheses requires the accumulation of valuable experimental
data from prior research efforts. It is important to note that this data
collection phase does not always need to be conducted by the same team of
researchers or within the same research project.

That is, there can be observational research projects aimed at quantitatively
describing the performance of algorithms and strategies of interest in solving
properly characterized problem instances and, then, when enough data has been
collected, other research works can tackle the task of proposing and
evaluating hypothesis that try to explain the observations.

Compared with the engineering approach, the goal of scientific research is not
necessarily guided by practical utility, any knowledge can be arguably useful,
as it can serve as the basis for future developments not foreseen at the time
the work is undertaken. In this regard, conversely to what happens in
engineering projects, working with classical problems is a perfectly valid
solution, as long as the research aims at providing further knowledge about
these problems and how the algorithms operate on them, and not just better
solutions.

Certainly, the obsessive search for algorithms that always outperform the
state-of-the-art can be a completely misleading guide if it implies, as
unfortunately far too often happens, hand-picking the instances and benchmarks
where the desired results are given. Proceeding in this way hardly contributes
to the advancement of the field. Rather than that, a much more interesting
contribution would be the identification and proper characterization of
instances where the new proposal outperforms all the existing algorithms, and
instances where it does not. Such a contribution, together with other similar
contributions in different kinds of instances, could be the evidence basis
that can lead to new explanations and hypotheses about how the algorithms work
or about the problem itself and, thus, to the expansion of the body of
knowledge in the area.

##  4 Conclusion

This manuscript arises from the feeling that we are trying to move ever
faster, shortening the research-publication cycle, and the concern that this
behavior gives rise to different kinds of problems. The solution is, in our
opinion, a shared reflection on the fundamentals of our work as researchers.
We have to take some time to reflect on what we do and why we do it.

We have focused here on a particular aspect of our research field, the role of
experimentation in metaheuristic optimization, but there are many other
aspects in this and other fields that require a serious discussion. Probably
the one that has the highest impact on our professional lives is the
publication of the results.

Many questions arise regarding the publication process, starting from the goal
itself, which should be the communication of the results. With that in mind,
we could ask which is (at the end of the first quarter of the XXI century) the
best way to communicate the results of a research project, or what means that
a research project is ’worthy of publication’.

All the content presented here is our personal view, and we are sure that many
other researchers share (partially or totally) this view, but similarly, we
are sure that many others do not. We are not claiming to have the solutions to
all the problems present in the current research world, but we are convinced
that it is time to take them seriously and discuss the fundamentals of
research in metaheuristic optimization.

## References

  * [1] John PA Ioannidis.  Why most published research findings are false.  PLoS medicine, 2(8):e124, 2005.
  * [2] Monya Baker.  Reproducibility crisis.  Nature, 533(26):353–66, 2016.
  * [3] Matthew Hutson.  Artificial intelligence faces reproducibility crisis.  Science, 359 6377:725–726, 2018.
  * [4] Andrew D Higginson and Marcus R Munafò.  Current incentives for scientists lead to underpowered studies with erroneous conclusions.  PLoS Biology, 14(11):e2000995, 2016.
  * [5] Kenneth Sörensen.  Metaheuristics—the metaphor exposed.  International Transactions in Operational Research, 22(1):3–18, 2015.
  * [6] Vahid Beiranvand, Warren Hare, and Yves Lucet.  Best practices for comparing optimization algorithms.  Optimization and Engineering, 18:815–848, 2017.
  * [7] Thomas Bartz-Beielstein, Carola Doerr, Daan van den Berg, Jakob Bossek, Sowmya Chandrasekaran, Tome Eftimov, Andreas Fischbach, Pascal Kerschke, William La Cava, Manuel Lopez-Ibanez, Katherine M. Malan, Jason H. Moore, Boris Naujoks, Patryk Orzechowski, Vanessa Volz, Markus Wagner, and Thomas Weise.  Benchmarking in optimization: Best practice and open issues, 2020.
  * [8] American Statistical Association et al.  Statement on statistical significance and p-values.  Am. Stat, 70:129–133, 2016.


# Multi-rate attention architecture for fast streamable Text-to-speech
spectrum modeling

###### Abstract

Typical high quality text-to-speech (TTS) systems today use a two-stage
architecture, with a spectrum model stage that generates spectral frames and a
vocoder stage that generates the actual audio. High-quality spectrum models
usually incorporate the encoder-decoder architecture with self-attention or
bi-directional long short-term (BLSTM) units. While these models can produce
high quality speech, they often incur O($L$) increase in both latency and
real-time factor (RTF) with respect to input length $L$. In other words,
longer inputs leads to longer delay and slower synthesis speed, limiting its
use in real-time applications. In this paper, we propose a multi-rate
attention architecture that breaks the latency and RTF bottlenecks by
computing a compact representation during encoding and recurrently generating
the attention vector in a streaming manner during decoding. The proposed
architecture achieves high audio quality (MOS of 4.31 compared to groundtruth
4.48), low latency, and low RTF at the same time. Meanwhile, both latency and
RTF of the proposed system stay constant regardless of input lengths, making
it ideal for real-time applications.

Index Terms—  text-to-speech, spectrum model, attention

##  1 Introduction

With the increasing popularity of voice assistant, virtual reality and other
artificial intelligence technologies, text-to-speech (TTS) is becoming an
important component in a wide range of applications. While recent advancements
in neural TTS technologies have brought significant improvement in audio
quality, efficient synthesis remains challenging in many scenarios [1, 2, 3,
4, 5, 6, 7, 8]. In practical applications, latency, computational complexity,
synthesis speed and streamability are key metrics for a production TTS system,
especially if it has limited computational resources such as on mobile
devices.

TTS synthesis is a process of generating high-fidelity audio waveform using
raw text representation. While solutions exists such as WaveNet[6] and
WaveRNN[5] to generate speech waveform directly from text (with the help of a
prosody model that predicts the tempo and intonation features), lower compute
TTS such as Tacotron[1], Tacotron2[2], FastSpeech[3], Deep voice 3[8] etc,
usually synthesize speech in two stages: 1: generate the speech spectrum from
text; and 2: generate the speech waveform by conditioning on the predicted
spectrum. We focus on the problem of two-stage TTS system design and propose a
spectrum model that achieves low latency, supports streaming and produces
high-quality TTS at the same time.

Conventional high-quality spectrum models are usually based on the encoder-
decoder attention framework [1, 2, 4]. In these models, the encoder summarizes
the input utterance into a context representation and the decoder generates
the spectral feature of each frame by attending to appropriate positions in
the context. Since decoding starts after encoder computes the input utterance
context, the latency of the model (i.e, time between compute starts and
returning the first frame) is bounded by the compute time of the encoder,
which increases proportionally with input length $L_{\text{input}}$ for both
Bi-directional Long Short-term Memory (BLSTM) [2] and self-attention [3, 4]
models. Moreover, the size of the encoder output context is also proportional
to the input length in these systems. Since decoding speed is affected by the
size of the encoder context, the inference speed per frame becomes slower with
increasing input length. Additionally, since the output spectrum is generated
per frame, many systems use or upsample linguistic features to finer
granularity for inference, which leads to increased synthesis computation
complexity.

In this paper, we propose a light-weight, low-latency and constant speed
spectrum model. The model has the following characteristics: 1) the encoder
adopts the parallelizable convolutional neural network (CNNs) and computes
multi-head attention from linguistic source features at different levels
(e.g., word, syllable, phone levels), leading to a compact context matrix and
low-latency; 2) the model supports streaming as the multi-head attention
vector is computed sequentially during decoding at each frame. 3) We perform
dynamic pooling on the context matrix to restrict it to fixed length while
still preserving information on the whole utterance. This ensures constant RTF
during inference. Through MOS study and RTF measurements, we show that the
model generates high quality speech while maintaining a constant (non-
increasing) inference speed independent of input utterance lengths.

##  2 Related work

Tacotron2 [2] and FastSpeech [3] are representative two-stage TTS systems that
consist of an encoder-decoder spectrum model followed by a neural vocoder.
Tacotron2’s encoder incorporates layers of CNNs and a BLSTM, whereas the
decoder computes an attention context from the encoder context and feeds it
into a LSTM network with CNN post-net. The BLSTM in the encoder leads to
$\mathbf{O}(L_{\text{input}})$ latency. Even though decoding is streamable,
it’s computation time per frame would be larger with longer utterances as it
depends on the size of the encoder attention context. On the other hand,
FastSpeech is a non-streaming model that generates the spectrum frames in
parallel. Both of FastSpeech’s encoder and decoder employ an architecture with
layers of Feed-forward Transformer (FFT), which is composed of a multi-head
self-attention layer and a 1D CNN layer. Even though parallel computation
significantly reduces the total latency, the latency to return the first frame
is still $\mathbf{O}(L_{\text{frames}})$ and the computation complexity is
bounded by $\mathbf{O}(L_{\text{frames}}^{2})$, which is not suitable for
real-time streaming TTS applications on lower-resource devices. This is
general for other transformer based models such as [4].

Towards delivering a streaming solution with low-latency and constant
inference speed regardless of input utterance length, we develop a multi-rate
attention model architecture that utilizes a recurrent network with global
attention context architecture similar to [9]. The global context is computed
with multi-head attention as described in [10].

##  3 Model Architecture

Fig. 1: Text to speech framework: the linguistic frontend transforms text into
an hierarchical IPA representation (Fig.2). The prosody model generates the
phone durations. The spectrum model generates the spectrum frames which are
fed into the neural vocoder to gernerate the audio waveforms.

The TTS framework under investigation is shown in Fig.1. The multi-stage
framework consists of a linguistic frontend that generates the linguistic
representation of the input utterance at different levels (more details in
Section 3.1); a prosody model that predicts the phone level duration, which is
used to unroll the linguistic features; a spectrum model that takes the
linguistic features to predict the spectrum frames; and a conditional neural
vocoder that generates the audio waveform. Our proposed multi-rate attention
architecture is a critical block in the spectrum model.

###  3.1 Multi-rate features

Fig. 2: Linguistic context tree using the super-segmental IPA representation:
the input text is transformed into a hierarchical representation of features
containing information at different levels.

TTS is a process of generating information and adding details. For an input
utterance, there are different levels of information. Conventional TTS systems
upsample lingustic information to a higher rate (e.g., sample rate [6], frame
rate [3] and character rate [2]). Instead, our system uses the features at
their original information rates and perform computation on the low rate
features.

Specifically, our linguistic frontend adopts the super-segmental International
Phonetic Alphabet (IPA) representation [11]. As shown in Fig.2, the linguistic
feature is an hierarchical representation of the normalized input text. There
are sentence level features such as question/statement, language ID and
speaker ID; phrase level features such as punctuation and intonation; word
level features such as word embedding; syllable level features such as
syllable type; and phone level features such as articulation diacritics[11].
The linguistic features are rolled out using the phone level duration
predictions from the prosody model to generate the frame level features, which
contains information such as frame position in the current phone, phone
duration and $\text{f}_{0}$, etc.

###  3.2 Multi-rate attention model

Fig. 3: Multi-rate attention architecture: attention contexts are computed
separately from each input source and then combined to provide overall
context, $c(t)$, for each frame prediction. Each attention head contains
compact linguistic information of the utterance at a difference IPA segmental
level.

The multi-rate recurrent attention architecture is shown in Fig.3. It adopts
the global attention model as described in Section 3.1 of [9]. At each frame
step $t$, the model first takes the corresponding frame level feature,
$x_{\text{f}}(t)$, as input and runs it through one time-step in the LSTM. The
hidden state $h(t)$ is used as the query vector to derive the context vector
$c(t)$ that captures relevant information from each of the multi-rate source
features, which are the word level feature, $x_{\text{w}}$, the syllable level
feature, $x_{\text{s}}$ and the phone level feature, $x_{\text{p}}$. The input
lengths of these features are $L_{\text{w}}$, $L_{\text{s}}$ and
$L_{\text{p}}$, respectively. Then, the context $c(t)$ is concatenated with
$h(t)$ to predict the current frame $y(t)$. Overall, the model is designed to
predict the conditional distribution of the current frame given the current
input and multi-rate linguistic context as follows:

$p\big{(}y(t)|y(<t),x_{\text{f}}(t),x_{\text{w}},x_{\text{s}},x_{\text{p}}\big{)}.$
(1)

At each frame step, an attention vector,
$c_{\text{i}}(t),\text{i}\in\\{\text{w},\text{s},\text{p}\\}$, is computed
from each of the source input using the dot-product attention [10]:

$c_{\text{i}}\big{(}q(t),\mathbf{K}_{\text{i}},\mathbf{V}_{\text{i}}\big{)}(t)=\text{softmax}\left(\frac{q(t)\mathbf{K}_{\text{i}}^{T}}{\sqrt{d_{k_{\text{i}}}}}\right)\mathbf{V}_{\text{i}},\hskip
5.69046pt\text{i}\in\\{\text{w},\text{s},\text{p}\\}$ (2)

where, the query $q(t)=h(t)$; keys, $\mathbf{K}_{i}$, and values,
$\mathbf{V}_{i}$, are computed from the linguistic feature source,
$\tilde{x}_{\text{i}}$, and have the same dimension $d_{k_{\text{i}}}$ and
length $\tilde{L}_{\text{i}}$. The computation complexity of the attention
vector $c_{\text{i}}(t)$ at each frame step is
$\mathbf{O}(d_{k_{\text{i}}}\times\tilde{L}_{\text{i}})$, where
$\tilde{L}_{\text{w}}$, $\tilde{L}_{\text{s}}$ and $\tilde{L}_{\text{p}}$
correspond to the lengths of $\tilde{x}_{\text{w}}$, $\tilde{x}_{\text{s}}$
and $\tilde{x}_{\text{p}}$, respectively, as shown in Fig.3.

Finally, the overall context, $c(t)$ attends to information from different
feature level and different positions using the multi-head mechanism as
described in [10]. Specifically:

$c(t)=\text{Concat}(c_{\text{w}},c_{\text{s}},c_{\text{p}})\mathbf{W}$ (3)

where $\mathbf{W}$ is a linear layer such that
$\mathbf{W}\in\mathbb{R}^{(d_{\text{w}}+d_{\text{s}}+d_{\text{p}})\times
d_{\text{model}}}$.

###  3.3 Context length regulation

As discussed in section 3.2, the amount of compute for each attention vector
is proportional to the size of the context matrix, i.e.,
$\mathbf{O}(d_{k_{\text{i}}}\times\tilde{L}_{\text{i}})$. We take two steps to
reduce its complexity by reducing $\tilde{L}_{\text{i}}$.

First, we use source information at its original compact representation in
each hierarchical level without upsampling to a higher rate representation,
which is a common practice in conventional TTS systems [2, 3, 4]. The lengths
$L_{\text{w}}$, $L_{\text{s}}$ and $L_{\text{p}}$ are orders of magnitude
smaller than the model output length $L_{\text{f}}$ (i.e., number of spectrum
frames). As a result, the overall computation is reduced by using the low-rate
features.

Secondly, in conventional systems, the length ${\tilde{L}}_{\text{i}}$ of the
attention context matrix is equal to or proportional to the length of the
input source ${L}_{\text{i}},\text{i}\in\\{\text{w},\text{s},\text{p}\\}$ [2,
3, 4]. This leads to increased computation complexity with increasing input
utterance length. In order to maintain constant inference speed, we enforce a
hard limit on the length of the attention context matrices (i.e,
${\tilde{L}}_{\text{i}}$) by performing dynamic max-pooling after the 1D CNN.
This way, the reduced context matrix can still retain information of the
entire input utterance. Dynamic max-pooling is done as follows:

$\hat{x}_{\text{i}}[m,n]=\sum^{d_{\text{i}}-1}_{c=0}\sum^{K-1}_{k=0}\mathbf{W}_{\text{i}}^{m}[c,k]x_{\text{i}}[n+k],\hskip
5.69046pt\text{i}\in\\{\text{w},\text{s},\text{p}\\}$ (4)

where, $0\leq m<d_{k_{\text{i}}}$, $0\leq n<L_{\text{i}}$, $d_{\text{i}}$ is
the feature dimension of $x_{\text{i}}$, $K$ is CNN filter kernel size and
$\mathbf{W}_{\text{i}}^{m}$ corresponds to the output filter matrix. Here, we
assume the input is well padded and hence, $\hat{x}_{\text{i}}$ and
$x_{\text{i}}$ have the same length $L_{\text{i}}$. After the CNN layer, we
perform a dynamic max-pooling to limit the attention context length to be less
or equal to a configurable value: $L_{\text{i}}^{\text{max}}$. Specifically,

$\tilde{x}_{\text{i}}[m,n]=\max_{nS_{\text{i}}\leq\alpha\leq
nS_{\text{i}}+S_{\text{i}}-1}\hat{x}_{\text{i}}[m,\alpha],\hskip
5.69046pt\text{i}\in\\{\text{w},\text{s},\text{p}\\}$ (5)

where $0\leq m\leq d_{k_{\text{i}}}$, $0\leq
n<\tilde{L}_{\text{i}}=\min(L_{\text{i}},L_{\text{i}}^{\text{max}})$, and
$S_{\text{i}}$ is the max pooling stride such that $S_{\text{i}}=\lceil
L_{\text{i}}/L_{\text{i}}^{\text{max}}\rceil$. Note that $\hat{x}_{\text{i}}$
is zero-padded to have length $S_{\text{i}}\times\tilde{L}_{\text{i}}$.

##  4 Experiment

###  4.1 Dataset and feature extraction

The TTS dataset was recorded in a voice production studio by contracted
professional voice talents. The corpus we used for training consists of 40,244
utterances from a single female speaker, which is approximately 40 hours of
data with 24kHz sampling rate. The phone level duration feature is extracted
with an unsupervised alignment algorithm, which uses the softDTW loss[12] and
is trained using approximately $100$ hours of TTS multispeaker data. The
$\text{f}_{0}$ feature is extracted for each frame using spectrum analysis.

###  4.2 Model details and baseline models

The overall framework is described in Section 3 and more details can be found
in [13]. The prosody model is a LSTM model with 256 hidden units with content-
based global attention [9]. The spectrum feature is a 19-dim feature vector
consisting of a 13-dim MFCC feature along with the $\text{f}_{0}$ feature and
a 5-dim periodicity feature. In the multi-rate attention spectrum model, the
CNN module has 2 layers of 1-D convolution with channel size set to be equal
to the input feature dimensions; the dynamic pooling layer has a maximum
sequence length, $L^{\text{max}}$, set to 50 for all heads; the dimension of
the attention context $d_{k_{i}}$ is set to be equal to the dimension of the
corresponding input features; the first and second layer of the LSTM has a
hidden dimension of 256 and 128, respectively. The model is trained with the
mean-square-error loss and the Adam [14] optimizer with learning-rate
$1e^{-3}$ and decays with a factor of 0.85 for every 10 epochs. Lastly, the
conditional neural vocoder is a WaveRNN [5] model, with hidden dimension 1024.

We compare with several baseline models in terms of synthesis quality and
inference speed. The inference speed metric is RTF, which is defined as
(synthesis time)/(audio time). The LSTM baseline is a simple 2-layer LSTM
model. The self-attention model uses frame rate features and the transformer
architecture as described in [10]. We also compare with the Tacotron2 [2]
system, which uses the 80-dim mel spectrum features and the same WaveRNN
vocoder [2].

Table 1: MOS with 95% confidence intervals Model | Normal | Long
---|---|---
Groundtruth | 4.48 $\pm$ 0.03 | 4.58 $\pm$ 0.04
Multi-rate attention (ours) | 4.31 $\pm$ 0.04 | 4.08 $\pm$ 0.05
| Multi-rate attention
---
(no dynamic pooling)
4.30 $\pm$ 0.04 | 4.24 $\pm$ 0.05
LSTM | 3.72 $\pm$ 0.05 | 3.85 $\pm$ 0.06
Self-attention [10] | 4.21 $\pm$ 0.04 | 4.05 $\pm$ 0.06
Tacotron 2 [15] | 3.56 $\pm$ 0.05 | 3.46 $\pm$ 0.08

###  4.3 Experiment results

We have conducted two sets of mean opinion score (MOS) studies with testing
utterances excluded from training data. Each MOS test has 400 participants who
rate each sample between 1-5 (1:bad - 5:excellent). In the first test, we
evaluate the general quality of the TTS using utterances with ”normal” audio
length ranging from 1 second to 20 seconds. In the second test, we focus on
”long” utterances, with audio lengths ranging from 15 seconds to 40 seconds,
in order to evaluate the model’s ability to capture long range information and
measure the effect of dynamic pooling when the stride is large. 111Audio
samples: https://multirate-spectrum-model.github.io/samples/ Table 1 shows the
results of the MOS studies. Overall, the proposed model achieves better MOS
scores than the baseline models. For normal utterances, the proposed multi-
rate architecture delivers very natural TTS speech that is close to human
speech. Dynamic pooling did not affect audio quality when utterances lengths
are less than 20s. For long utterances, the gap between the proposed TTS voice
and human voice increased because the prosody for longer utterances is harder
to learn. In addition, we observed a small drop in audio quality when applying
dynamic pooling with maximum context length $L^{max}=50$.

In addition, we evaluate the inference speed of the spectral model by
measuring its RTF, which is an important metric for a production TTS. The RTF
is measured as: (total synthesis time)/(audio length) using a single core on
the Intel(R) Xeon(R) 2.0GHz CPU. As shown in Fig.4, the proposed multi-rate
attention architecture achieves almost constant RTF with increasing input
utterance length, whereas the RTF of the baseline self-attention model
increases proportionally with audio length. Moreover, the multi-rate attention
model RTF is only slightly higher than the simple 2-layer LSTM model. Notice
that, when we remove dynamic pooling from the model, the RTF starts to
increase when input length is long. Hence, there is a small trade-off between
RTF and audio quality with long utterances and maximum context length,
$L^{max}$, can be tuned accordingly based on the quality and speed requirement
of the target application.

Fig. 4: RTF evaluation with increasing audio length

##  5 Conclusion

In conclusion, we proposed a spectrum model using the multi-rate attention
architecture. The proposed model uses the compact hierarchical linguistic
features as input, computes the multi-head attention contexts in a streaming
manner and performs dynamic pooling to restrict context length. It achieves
constant latency and RTF regardless of input utterance lengths while producing
high quality speech. Our MOS study shows the proposed model achieves better
quality compared to the self-attention baseline, as well as other baseline
models.

## References

  * [1] Yuxuan Wang, RJ Skerry-Ryan, Daisy Stanton, Yonghui Wu, Ron J Weiss, Navdeep Jaitly, Zongheng Yang, Ying Xiao, Zhifeng Chen, Samy Bengio, et al.,  “Tacotron: Towards end-to-end speech synthesis,”  Proc. Interspeech 2017, pp. 4006–4010, 2017.
  * [2] Jonathan Shen, Ruoming Pang, Ron J Weiss, Mike Schuster, Navdeep Jaitly, Zongheng Yang, Zhifeng Chen, Yu Zhang, Yuxuan Wang, Rj Skerrv-Ryan, et al.,  “Natural tts synthesis by conditioning wavenet on mel spectrogram predictions,”  in 2018 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP). IEEE, 2018, pp. 4779–4783.
  * [3] Yi Ren, Yangjun Ruan, Xu Tan, Tao Qin, Sheng Zhao, Zhou Zhao, and Tie-Yan Liu,  “Fastspeech: Fast, robust and controllable text to speech,”  in Advances in Neural Information Processing Systems, 2019, pp. 3171–3180.
  * [4] Naihan Li, Shujie Liu, Yanqing Liu, Sheng Zhao, and Ming Liu,  “Neural speech synthesis with transformer network,”  in Proceedings of the AAAI Conference on Artificial Intelligence, 2019, vol. 33, pp. 6706–6713.
  * [5] Nal Kalchbrenner, Erich Elsen, Karen Simonyan, Seb Noury, Norman Casagrande, Edward Lockhart, Florian Stimberg, Aäron van den Oord, Sander Dieleman, and Koray Kavukcuoglu,  “Efficient neural audio synthesis,”  in ICML, 2018.
  * [6] Aäron van den Oord, Sander Dieleman, Heiga Zen, Karen Simonyan, Oriol Vinyals, Alex Graves, Nal Kalchbrenner, Andrew Senior, and Koray Kavukcuoglu,  “Wavenet: A generative model for raw audio,”  in 9th ISCA Speech Synthesis Workshop, pp. 125–125.
  * [7] Ryan Prenger, Rafael Valle, and Bryan Catanzaro,  “Waveglow: A flow-based generative network for speech synthesis,”  in ICASSP 2019-2019 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP). IEEE, 2019, pp. 3617–3621.
  * [8] Wei Ping, Kainan Peng, Andrew Gibiansky, Sercan O Arik, Ajay Kannan, Sharan Narang, Jonathan Raiman, and John Miller,  “Deep voice 3: Scaling text-to-speech with convolutional sequence learning,”  arXiv preprint arXiv:1710.07654, 2017.
  * [9] Minh-Thang Luong, Hieu Pham, and Christopher D Manning,  “Effective approaches to attention-based neural machine translation,”  arXiv preprint arXiv:1508.04025, 2015.
  * [10] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin,  “Attention is all you need,”  in Advances in neural information processing systems, 2017, pp. 5998–6008.
  * [11] International Phonetic Association,  “The international phonetic alphabet,” 2015,  https://www.internationalphoneticassociation.org/sites/default/files/IPA_Kiel_2015.pdf.
  * [12] Marco Cuturi and Mathieu Blondel,  “Soft-dtw: a differentiable loss function for time-series,”  arXiv preprint arXiv:1703.01541, 2017.
  * [13] Yang Gao, Weiyi Zheng, Zhaojun Yang, Thilo Kohler, Christian Fuegen, and Qing He,  “Interactive text-to-speech via semi-supervised style transfer learning,”  arXiv preprint arXiv:2002.06758, 2020.
  * [14] Diederik Kingma and Jimmy Ba,  “Adam: A method for stochastic optimization,”  International Conference on Learning Representations, 12 2014.
  * [15] Nvidia,  “Tacotron 2 - pytorch implementation with faster-than-realtime inference,” https://github.com/NVIDIA/tacotron2.