# Sampling discretization of integral norms and its application

F. Dai and V. Temlyakov 111 The first named author’s research was partially
supported by NSERC of Canada Discovery Grant RGPIN-2020-03909. The second
named author’s research was supported by the Russian Federation Government
Grant No. 14.W03.31.0031.

###### Abstract

The paper addresses a problem of sampling discretization of integral norms of
elements of finite-dimensional subspaces satisfying some conditions. We prove
sampling discretization results under two standard kinds of assumptions –
conditions on the entropy numbers and conditions in terms of the Nikol’skii-
type inequalities. We prove some upper bounds on the number of sample points
sufficient for good discretization and show that these upper bounds are sharp
in a certain sense. Then we apply our general conditional results to subspaces
with special structure, namely, subspaces with the tensor product structure.
We demonstrate that applications of results based on the Nikol’skii-type
inequalities provide somewhat better results than applications of results
based on the entropy numbers conditions. Finally, we apply discretization
results to the problem of sampling recovery.

Keywords and phrases: Sampling discretization, entropy numbers, Nikol’skii
inequality, recovery.

MSC classification 2000: Primary 65J05; Secondary 42A05, 65D30, 41A63.

##  1 Introduction

Let $\Omega$ be a subset of ${\mathbb{R}}^{d}$ with the probability measure
$\mu$. By $L_{p}$, $1\leq p<\infty$, norm we understand

$\|f\|_{p}:=\|f\|_{L_{p}(\Omega,\mu)}:=\left(\int_{\Omega}|f|^{p}d\mu\right)^{1/p}.$

By $L_{\infty}$ norm we understand the uniform norm of continuous functions

$\|f\|_{\infty}:=\max_{\mathbf{x}\in\Omega}|f(\mathbf{x})|$

and with some abuse of notation we occasionally write $L_{\infty}(\Omega)$ for
the space ${\mathcal{C}}(\Omega)$ of continuous functions on $\Omega$.

By discretization of the $L_{p}$ norm we understand a replacement of the
measure $\mu$ by a discrete measure $\mu_{m}$ with support on a set
$\xi=\\{\xi^{j}\\}_{j=1}^{m}\subset\Omega$ in such a way that the error
$|\|f\|^{p}_{L_{p}(\Omega,\mu)}-\|f\|^{p}_{L_{p}(\Omega,\mu_{m})}|$ is small
for functions from a given class. In this paper we focus on discretization of
the $L_{p}$ norms of elements of finite-dimensional subspaces. Namely, we work
on the following problem.

The Marcinkiewicz discretization problem. Let $\Omega$ be a compact subset of
${\mathbb{R}}^{d}$ with the probability measure $\mu$. We say that a linear
subspace $X_{N}$ (index $N$ here, usually, stands for the dimension of
$X_{N}$) of $L_{p}(\Omega,\mu)$, $1\leq p<\infty$, admits the Marcinkiewicz-
type discretization theorem with parameters $m\in{\mathbb{N}}$ and $p$ and
positive constants $C_{1}\leq C_{2}$ if there exists a set

$\Big{\\{}\xi^{j}\in\Omega:j=1,\dots,m\Big{\\}}$

such that for any $f\in X_{N}$ we have

$C_{1}\|f\|_{p}^{p}\leq\frac{1}{m}\sum_{j=1}^{m}|f(\xi^{j})|^{p}\leq
C_{2}\|f\|_{p}^{p}.$ (1.1)

The Bernstein discretization problem. In the case $p=\infty$ we define
$L_{\infty}$ as the space of continuous functions on $\Omega$ and ask for

$C_{1}\|f\|_{\infty}\leq\max_{1\leq j\leq m}|f(\xi^{j})|\leq\|f\|_{\infty}.$
(1.2)

We will also use the following brief way to express the above properties: The
$\mathcal{M}(m,p)$ (more precisely the $\mathcal{M}(m,p,C_{1},C_{2})$) theorem
holds for a subspace $X_{N}$, written $X_{N}\in\mathcal{M}(m,p)$ (more
precisely $X_{N}\in\mathcal{M}(m,p,C_{1},C_{2})$). In the case $q=\infty$ we
always have $C_{2}=1$ and for brevity we write $\mathcal{M}(m,\infty,C_{1})$
instead of $\mathcal{M}(m,\infty,C_{1},1)$.

There are known results on the Marcinkiewicz discretization problem proved for
subspaces $X_{N}$ satisfying some conditions. There are two types of
conditions used in the literature: (I) Conditions on the entropy numbers and
(II) Conditions in terms of the Nikol’skii-type inequalities. We now describe
these conditions in detail.

I. Entropy conditions. We begin with the definition of the entropy numbers.
Let $X$ be a Banach space and let $B_{X}$ denote the unit ball of $X$ with the
center at $0$. Denote by $B_{X}(y,r)$ the ball with center $y$ and radius
$r>0$, $\\{x\in X:\|x-y\|\leq r\\}$. For a compact set $A\subset X$ we define
the entropy numbers $\varepsilon_{k}(A,X)$, $k=0,1,\cdots$:

$\varepsilon_{k}(A,X):=\inf\Bigl{\\{}\varepsilon>0:\exists
y^{1},\dots,y^{2^{k}}\in A,\
A\subseteq\cup_{j=1}^{2^{k}}B_{X}(y^{j},\varepsilon)\Bigr{\\}}.$

In our definition of $\varepsilon_{k}(A,X)$ we require $y^{j}\in A$. In a
standard definition of $\varepsilon_{k}(A,X)$ this restriction is not imposed.
However, it is well known (see [8], p.208) that these characteristics may
differ at most by the factor $2$. Throughout the paper we use the following
notation for the unit $L_{q}$ ball of $X_{N}$

$X_{N}^{q}:=\\{f\in X_{N}:\,\|f\|_{q}\leq 1\\}.$

Here is a standard entropy assumption in discretization theory: Suppose that a
subspace $X_{N}$ satisfies the condition $(B\geq 1)$

$\varepsilon_{k}(X^{q}_{N},L_{\infty})\leq B(N/k)^{1/q},\quad 1\leq k\leq N.$
(1.3)

II. Nikol’skii-type inequalities. Let $q\in[1,\infty)$ and $X_{N}\subset
L_{\infty}(\Omega)$. The inequality

$\|f\|_{\infty}\leq M\|f\|_{q},\ \ \forall f\in X_{N}$ (1.4)

is called the Nikol’skii inequality for the pair $(q,\infty)$ with the
constant $M$. It is convenient to write the constant $M$ in the form
$M=BN^{1/q}$. If $X_{N}$ satisfies (1.4) with $M=BN^{1/q}$, then we say that
$X_{N}$ satisfies Condition NqB (see Section 4 below) and write
$X_{N}\in\mathcal{N}(q,\infty,B)$.

It is well known that in the case $q\in[2,\infty)$ the above entropy condition
and Nikol’skii-type inequality are closely related. We now comment on the
relation between the Nikol’skii inequality and the entropy condition (1.3). On
one hand it is easy to see (see [3]) that the entropy condition (1.3) for
$k=1$ implies the following Nikol’skii inequality

$\|f\|_{\infty}\leq 4BN^{1/q}\|f\|_{q}\quad\text{for all}\quad f\in X_{N}.$

On the other hand we note that the Nikol’skii-type inequality condition (1.4)
with $M=BN^{1/q}$ implies the entropy condition (1.3) with $k=1$. Thus, the
Nikol’skii-type inequality condition is equivalent to the entropy condition
(1.3) for $k=1$. Moreover, Lemma 2.2 (see below) from [11] shows that in the
case $q\in[2,\infty)$ the Nikol’skii inequality (1.4) combined with an extra
mild condition implies the entropy condition (1.3) with $B$ replaced by
$C(\log N)^{1/q}B$.

We refer the reader to the recent survey papers [1] and [5] for a detailed
description of known results on the Marcinkiewicz discretization problem under
conditions I and II. In this paper we only cite those results which are
directly related to our new results. We now give brief comments on results
obtained in Sections 2–4.

In Section 2 we discuss the following setting. Assume that parameters $1\leq
p,q<\infty$ are given. We would like to solve the Marcinkiewicz discretization
problem for the $L_{p}$ norm under assumption that either Conditions I or II
is satisfied with the parameter $q$. Typically, the known results address
either the case $p=q$ or the case when the Nikol’skii-type inequality for the
pair $(2,\infty)$ is imposed. In Section 2 (see Corollary 2.1) we show how a
simple argument allows us to derive a discretization result in the case $1\leq
q\leq p<\infty$ under assumptions I from the corresponding result for $p=q$.
The main result of Section 2 is Theorem 2.2, which improves known results in
the case when $p=q$ and $3<q<\infty$ under Conditions II. Then we use Theorem
2.2 to deduce discretization results in the case $2\leq q\leq p<\infty$ (see
Corollary 2.2).

In Section 3 we apply results of Section 2 to subspaces with special
structure, namely, subspaces with the tensor product structure. We demonstrate
that applications of results based on Conditions II provide somewhat better
results than applications of results based on Conditions I. This observation
is based on a known result on the Nikol’skii-type inequalities for subspaces
with the tensor product structure (see Lemma 3.1 below).

In Section 4 we apply discretization results of Section 2 to the problem of
sampling recovery. Recently, it was observed in [12] how discretization
results can help to prove general inequalities between optimal sampling
recovery and the Kolmogorov widths. Namely, it was proved in [12] that the
optimal error of recovery in the $L_{2}$ norm of functions from a class
$\mathbf{F}$ can be bounded above by the value of the Kolmogorov width of
$\mathbf{F}$ in the uniform norm. In Section 4 we demonstrate how to derive
some general inequalities for the optimal sampling recovery in $L_{p}$ from
the corresponding discretization results of Section 2.

##  2 A generalization

We start with the following Theorem 2.1, which was proved in [9] in the case
of $q=1$ with the help of the chaining technique, and in [2] for the general
case.

######  Theorem 2.1.

Let $1\leq q<\infty$. Suppose that a subspace $X_{N}$ satisfies the condition

$\varepsilon_{k}(X^{q}_{N},L_{\infty})\leq B(N/k)^{1/q},\quad 1\leq k\leq N,$
(2.1)

where $B\geq 1$. Then for a large enough constant $C(q)$ there exists a set of

$m\leq C(q)B^{q}N(\log_{2}(2BN))^{2}$

points $\xi^{j}\in\Omega$, $j=1,\dots,m$, such that for any $f\in X_{N}$ we
have

$\frac{1}{2}\|f\|_{q}^{q}\leq\frac{1}{m}\sum_{j=1}^{m}|f(\xi^{j})|^{q}\leq\frac{3}{2}\|f\|_{q}^{q}.$

Here is a direct corollary of Theorem 2.1.

######  Corollary 2.1.

Let $1\leq q\leq p<\infty$. Suppose that the condition (2.1) is satisfied.
Then for a large enough constant $C(p,q)$ there exists a set of

$m\leq C(p,q)B^{p}N^{p/q}(\log_{2}(2BN))^{2}$

points $\xi^{j}\in\Omega$, $j=1,\dots,m$, such that for any $f\in X_{N}$ we
have

$\frac{1}{2}\|f\|_{p}^{p}\leq\frac{1}{m}\sum_{j=1}^{m}|f(\xi^{j})|^{p}\leq\frac{3}{2}\|f\|_{p}^{p}.$

###### Proof.

Let $1\leq q\leq p<\infty$. Then condition (2.1) implies

$\varepsilon_{k}(X^{p}_{N},L_{\infty})\leq\varepsilon_{k}(X^{q}_{N},L_{\infty})\leq
BN^{1/q-1/p}(N/k)^{1/p},\quad 1\leq k\leq N.$ (2.2)

Thus, condition (2.1) is satisfied for $p$ with $B^{\prime}=BN^{1/q-1/p}$.
Theorem 2.1 gives

$m\leq C(p)(B^{\prime})^{p}N(\log_{2}(2B^{\prime}N))^{2}\leq
C(p,q)B^{p}N^{p/q}(\log_{2}(2BN))^{2}.$

∎

We now prove an analog of Theorem 2.1 for $q\in(2,\infty)$ under a condition
on $X_{N}$ in terms of the Nikol’skii inequality instead of the entropy
condition (2.1) in Theorem 2.1.

######  Theorem 2.2.

Let $2\leq q<\infty$. Suppose that a subspace $X_{N}$ satisfies the Nikol’skii
type inequality

$\|f\|_{\infty}\leq BN^{1/q}\|f\|_{q},\quad\forall f\in X_{N},$ (2.3)

where $B\geq 1$. Then for any $\epsilon\in(0,1)$ there is a large enough
constant $C=C(p,q,\epsilon)$ such that there exists a set of

$m\leq CB^{q}N(\log_{2}(2BN))^{3}$ (2.4)

points $\xi^{j}\in\Omega$, $j=1,\dots,m$, such that for any $f\in X_{N}$ we
have

$(1-\epsilon)\|f\|_{q}^{q}\leq\frac{1}{m}\sum_{j=1}^{m}|f(\xi^{j})|^{q}\leq(1+\epsilon)\|f\|_{q}^{q}.$

###### Proof.

We derive Theorem 2.2 from the $\epsilon$-version of Theorem 2.1. The
following Remark 2.1 is from [2].

######  Remark 2.1.

Under the assumptions of Theorem 2.1, we can deduce a slightly stronger
result, namely, that for any $\epsilon\in(0,1)$, there exists a set of $m$
points $\\{\xi^{j}\\}_{j=1}^{m}\subset\Omega$ with

$m\leq C(q,\epsilon)B^{q}N(\log_{2}(2BN))^{2}$

such that

$(1-\epsilon)\|f\|_{q}^{q}\leq\frac{1}{m}\sum_{j=1}^{m}|f(\xi^{j})|^{q}\leq(1+\epsilon)\|f\|_{q}^{q},\
\qquad\forall f\in X_{N},$

where $C(q,\epsilon)$ is a positive constant depending only on $\epsilon$ and
$q$.

At the first step we use the following Lemma 2.1 from [3].

######  Lemma 2.1.

Let $1\leq p<\infty$ be a fixed number. Assume that $X_{N}$ is an
$N$-dimensional subspace of $L_{\infty}(\Omega)$ satisfying the following
condition for some parameter $\beta>0$ and constant $K\geq 2$:

$\|f\|_{\infty}\leq(KN)^{\frac{\beta}{p}}\|f\|_{p},\ \ \forall f\in X_{N}.$
(2.5)

Let $\\{\mathbf{x}^{j}\\}_{j=1}^{\infty}$ be a sequence of independent random
points selected from $\Omega$ according to $\mu$. Then there exists a positive
constant $C_{\beta}$ depending only on $\beta$ such that for any
$0<\epsilon\leq\frac{1}{2}$ and

$m\geq C_{\beta}K^{\beta}\epsilon^{-2}(\log(2/\epsilon))N^{\beta+1}\log N,$
(2.6)

the inequality

$\displaystyle(1-\epsilon)\|f\|_{p}^{p}\leq\frac{1}{m}\sum_{j=1}^{m}|f(\mathbf{x}^{j})|^{p}\leq(1+\epsilon)\|f\|_{p}^{p},$
(2.7)

holds for all $f\in X_{N}$ with probability $\geq 1-m^{-N/\log K}$.

By Lemma 2.1 with $p=q$, $\beta=1$, $K=B^{q}$, and $m=S$ we replace the
$L_{q}(\Omega,\mu)$ space by the $L_{q}(\Omega_{S},\mu_{S})$ with
$\Omega_{S}=\\{\mathbf{x}^{j}\\}_{j=1}^{S}$, $\mu_{S}(\mathbf{x}^{j})=1/S$,
$j=1,\dots,S$ with the relations

$(1-\epsilon)\|f\|_{L_{q}(\Omega,\mu)}^{q}\leq\|f\|_{L_{q}(\Omega_{S},\mu_{S})}^{q}\leq(1+\epsilon)\|f\|_{L_{q}(\Omega,\mu)}^{q},$
(2.8) $S\leq C_{2}B^{q}\epsilon^{-2}(\log(2/\epsilon))N^{2}\log N.$ (2.9)

At the second step we apply the following Lemma 2.2 from [11], which is based
on the corresponding results from [6], with $s=S$ to the restriction
$X_{N}(\Omega_{S})$ of the subspace $X_{N}$ onto the $\Omega_{S}$ in the case
of $L_{q}(\Omega_{S},\mu_{S})$.

######  Lemma 2.2.

Let $q\in[2,\infty)$. Assume that for any $f\in X_{N}$ we have

$\|f\|_{\infty}\leq BN^{1/q}\|f\|_{q}$ (2.10)

with some constant $B\geq 1$. Also, assume that
$X_{N}\in\mathcal{M}(s,\infty,C_{1})$ with $s\geq 1$. Then for $k\in[1,N]$ we
have

$\varepsilon_{k}(X_{N}^{q},L_{\infty})\leq C(q,C_{1})(\log
s)^{1/q}B(N/k)^{1/q}.$ (2.11)

This gives us the bound

$\varepsilon_{k}(X_{N}^{q}(\Omega_{S}),L_{\infty})\leq
C(q,\epsilon,C_{2})B(\log(2BN))^{1/q}(N/k)^{1/q}.$ (2.12)

At the third step we apply Remark 2.1 to the $X_{N}(\Omega_{S})$ and complete
the proof.

∎

Here is a direct corollary of Theorem 2.2.

######  Corollary 2.2.

Let $2\leq q\leq p<\infty$. Suppose that condition (2.3) is satisfied with
$B\geq 1$. Then for any $\epsilon\in(0,1)$ there is a large enough constant
$C=C(p,q,\epsilon)$ such that there exists a set of

$m\leq CB^{p}N^{p/q}(\log_{2}(2BN))^{3}$ (2.13)

points $\xi^{j}\in\Omega$, $j=1,\dots,m$, such that for any $f\in X_{N}$ we
have

$(1-\epsilon)\|f\|_{p}^{p}\leq\frac{1}{m}\sum_{j=1}^{m}|f(\xi^{j})|^{p}\leq(1+\epsilon)\|f\|_{p}^{p}.$

###### Proof.

Let $2\leq q\leq p<\infty$. Then condition (2.3) implies

$\|f\|_{\infty}\leq BN^{1/q}\|f\|_{q}\leq BN^{1/q-1/p}N^{1/p}\|f\|_{p},\quad
1\leq k\leq N.$ (2.14)

Thus, condition (2.3) is satisfied for $p$ with $B^{\prime}=BN^{1/q-1/p}$.
Theorem 2.2 gives

$m\leq C(p,\epsilon)(B^{\prime})^{p}N(\log_{2}((2B^{\prime}N)))^{3}\leq
C(p,q,\epsilon)B^{p}N^{p/q}(\log_{2}(2BN))^{3}.$

∎

######  Remark 2.2.

Corollary 2.2 provides bound (2.13) on $m$ that consists of three factors:
$N^{p/q}$, $(\log_{2}(2BN))^{3}$, which grow with $N$, and $B^{p}$, which may
grow with $N$. We do not know if the factor $(\log_{2}(2BN))^{3}$ can be
dropped in (2.13). However, we know that in the case $q>2$ neither $N^{p/q}$
can be replaced by $N^{p/q-\delta}$ nor $B^{p}$ can be replaced by
$B^{p-\delta}$ with any $\delta>0$. In the case $q=2$ the factor $N^{p/2}$
cannot be replaced by $N^{p/2-\delta}$ with any $\delta>0$.

###### Proof.

We begin with the case $q=2$. Let $\Lambda_{n}=\\{k_{j}\\}_{j=1}^{n}$ be a
lacunary sequence: $k_{1}=1$, $k_{j+1}\geq bk_{j}$, $b>1$, $j=1,\dots,n-1$.
Denote

$\mathcal{T}(\Lambda_{n}):=\left\\{f\,:\,f(x)=\sum_{k\in\Lambda_{n}}c_{k}e^{ikx},\quad
x\in\mathbb{T}\right\\}.$

It is clear that $\mathcal{T}(\Lambda_{n})\in\mathcal{N}(2,\infty,1)$. Indeed,
for $f(x)=\sum_{k\in\Lambda_{n}}c_{k}e^{ikx}$ we have

$\|f\|_{\infty}\leq\sum_{k\in\Lambda_{n}}|c_{k}|\leq
n^{1/2}\left(\sum_{k\in\Lambda_{n}}|c_{k}|^{2}\right)^{1/2}=n^{1/2}\|f\|_{2}.$
(2.15)

It is proved in [5] (see D.20. A lower bound) that the condition
$\mathcal{T}(\Lambda_{n})\in\mathcal{M}(m,p,C_{1},C_{2})$ with $p>2$ and fixed
$C_{1}$ and $C_{2}$ implies $m\geq C(p,C_{1},C_{2})n^{p/2}$. This completes
the proof of Remark 2.2 in the case $q=2$.

We now let $q>2$ and rewrite (2.15) in the form

$\|f\|_{\infty}\leq n^{1/2}\|f\|_{2}\leq n^{1/2-1/q}n^{1/q}\|f\|_{q}.$

Therefore, $\mathcal{T}(\Lambda_{n})\in\mathcal{N}(q,\infty,n^{1/2-1/q})$.
Then, on one hand we know from the above that $m$ must grow in the sense of
order as $n^{p/2}$, on the other hand if we replace in (2.13) $N^{p/q}$ by
$N^{p/q-\delta}$, then we obtain

$m\leq Cn^{p(1/2-1/q)}n^{p/q-\delta}(\log n)^{3}\leq Cn^{p/2-\delta}(\log
n)^{3}.$

We get a contradiction. In the same way we get a contradiction in the case of
replacement $B^{p}$ by $B^{p-\delta}$. The proof is complete.

∎

A comment. Sometimes it is convenient to have the entropy bound (2.1) for all
$k\in{\mathbb{N}}$, namely, the bound

$\varepsilon_{k}(X^{q}_{N},L_{\infty})\leq B_{1}(N/k)^{1/q},\quad 1\leq
k<\infty.$ (2.16)

We now prove that (2.1) implies (2.16) with $B_{1}=6B$. We begin by pointing
out that the assumption (2.1) for $k=N$ implies the inequality

$\varepsilon_{k}(X_{N}^{q},L_{\infty})\leq 6B2^{-k/N}\ \ \text{ for $k>N$}.$
(2.17)

This follows directly from the facts that for each Banach space $X$ (see [10,
(7.1.6), p. 323]),

$\varepsilon_{k}(A,X)\leq\varepsilon_{N}(A,X)\varepsilon_{k-N}(B_{X},X),\ \
k>N,$

and for each $N$-dimensional space $X$ (see [10, Corollary 7.2.2, p. 324]),

$\varepsilon_{m}(B_{X},X)\leq 3(2^{-m/N}).$

Next, we use the inequality $2^{x}\geq 1+x$, for $x\geq 1$. This inequality
follows from ($x\geq 1$, $a=\ln 2$)

$e^{ax}=1+ax+\frac{(ax)^{2}}{2!}+\dots\geq
1+x\left(a+\frac{a^{2}}{2!}+\dots\right)=1+x(e^{a}-1)=1+x.$

Therefore, condition (2.1) implies condition (2.16) with $B_{1}=6B$.

##  3 Discretization in subspaces with tensor product structure

Let $s\in{\mathbb{N}}$. Suppose that we have $s$ subspaces
$X(N_{i},i)\subset{\mathcal{C}}(\Omega_{i})$ with $\dim X(N_{i},i)=N_{i}$,
$i=1,\dots,s$. Denote $\mathbf{N}:=(N_{1},\dots,N_{s})$ and

$\mathbf{X}_{\mathbf{N}}:=\operatorname{span}\\{f_{1}(\mathbf{x}^{1})\times\cdots\times
f_{s}(\mathbf{x}^{s})\,:\,f_{i}\in X(N_{i},i),i=1,\dots,s\\}$

a subspace of ${\mathcal{C}}(\Omega_{1}\times\cdots\times\Omega_{s})$.
Consider a product measure $\mu=\mu_{1}\times\cdots\times\mu_{s}$ on
$\Omega:=\Omega_{1}\times\cdots\times\Omega_{s}$ with $\mu_{i}$ being a
probability measure on $\Omega_{i}$, $i=1,\dots,s$. First, we prove some
discretization results for the $\mathbf{X}_{\mathbf{N}}$ under the conditions

$\varepsilon_{k}(X^{q}(N_{i},i),L_{\infty})\leq B_{i}(N_{i}/k)^{1/q},\quad
1\leq k<\infty,\quad i=1,\dots,s,$ (3.1)

where $B_{i}\geq 1$, $i=1,\cdots,s$. Note, that as it is explained at the end
of Section 2, conditions (3.1) are equivalent to the same conditions with a
weaker restrictions on $k$: instead of $1\leq k<\infty$ we can take $1\leq
k\leq N_{i}$. We begin with a simple observation.

######  Proposition 3.1.

Let $1\leq q\leq p<\infty$. Suppose that conditions (3.1) are satisfied. Then
for a large enough constant $C(p,q,s)$ there exists a set $\xi(m)$ with a
tensor product structure of

$m\leq C(p,q,s)\prod_{i=1}^{s}B_{i}^{p}N_{i}^{p/q}(\log_{2}(2B_{i}N_{i}))^{2}$

points $\xi^{j}\in\Omega$, $j=1,\dots,m$, such that for any
$f\in\mathbf{X}_{\mathbf{N}}$ we have

$\left(\frac{1}{2}\right)^{s}\|f\|_{p}^{p}\leq\frac{1}{m}\sum_{j=1}^{m}|f(\xi^{j})|^{p}\leq\left(\frac{3}{2}\right)^{s}\|f\|_{p}^{p}.$
(3.2)

###### Proof.

By Corollary 2.1 for each subspace $X(N_{i},i)$, $i=1,\dots,s$, we find a set
$\xi(m_{i},i)=\\{\xi^{j}(m_{i},i)\\}_{j=1}^{m_{i}}\subset\Omega_{i}$ of
$m_{i}$ points such that

$m_{i}\leq C(p,q)B_{i}^{p}N_{i}^{p/q}(\log_{2}(2B_{i}N_{i}))^{2}$ (3.3)

and for any $f\in X(N_{i},i)$ we have

$\frac{1}{2}\|f\|_{p}^{p}\leq\frac{1}{m_{i}}\sum_{j=1}^{m_{i}}|f(\xi^{j}(m_{i},i))|^{p}\leq\frac{3}{2}\|f\|_{p}^{p}.$
(3.4)

Then applying (3.4) successively with respect to $i=1,\dots,s$ we obtain for
$f\in\mathbf{X}_{\mathbf{N}}$ inequalities (3.2) with
$\xi(m)=\xi(m_{1},1)\times\cdots\times\xi(m_{s},s)$ and by (3.3)

$m=\prod_{i=1}^{s}m_{i}\leq
C(p,q)^{s}\prod_{i=1}^{s}B_{i}^{p}N_{i}^{p/q}(\log_{2}(2B_{i}N_{i}))^{2}.$

This completes the proof. ∎

Second, we discuss some results, when instead of conditions (3.1) we impose
conditions in terms of Nikol’skii-type inequalities: For any $f\in X(N_{i},i)$

$\|f\|_{\infty}\leq B_{i}N_{i}^{1/q}\|f\|_{q},\quad i=1,\dots,s.$ (3.5)

In the same way as Proposition 3.1 was derived from the discretization result
– Corollary 2.1 – we derive from Corollary 2.2 the following statement.

######  Proposition 3.2.

Let $2\leq q\leq p<\infty$. Suppose that conditions (3.5) are satisfied with
$B_{i}\geq 1$, $i=1,\dots,s$. Then for a large enough constant $C=C(p,q,s)$
there exists a set $\xi(m)$ with a tensor product structure of

$m\leq C\prod_{i=1}^{s}B_{i}^{p}N_{i}^{p/q}(\log_{2}(2B_{i}N_{i}))^{3}$ (3.6)

points $\xi^{j}\in\Omega$, $j=1,\dots,m$, such that for any
$f\in\mathbf{X}_{\mathbf{N}}$ we have

$\left(\frac{1}{2}\right)^{s}\|f\|_{p}^{p}\leq\frac{1}{m}\sum_{j=1}^{m}|f(\xi^{j})|^{p}\leq\left(\frac{3}{2}\right)^{s}\|f\|_{p}^{p}.$
(3.7)

In a particular case when $N_{i}=N$ and $B_{i}=B$ for $i=1,\dots,s$, the extra
logarithmic factor in (3.6) will be of order $(\log(2BN))^{3s}$. We now show
how it could be reduced to $(\log(2BN))^{3}$. We need the following lemma,
which is a particular case of Theorem 3.3.3 from [10, p.107] in the case of
periodic functions with $\Omega_{i}=\mathbb{T}$, $i=1,\dots,s$.

######  Lemma 3.1.

Let $1\leq q<\infty$. Suppose that conditions (3.5) are satisfied. Then for
$f\in\mathbf{X}_{\mathbf{N}}$ we have

$\|f\|_{\infty}\leq\left(\prod_{i=1}^{s}(B_{i}N_{i}^{1/q})\right)\|f\|_{q}.$

###### Proof.

Let $f\in\mathbf{X}_{\mathbf{N}}$. Then for any
$\mathbf{x}=(\mathbf{x}^{1},\mathbf{x}^{2})\in\Omega_{1}\times\Omega_{2}$, we
have

$\displaystyle|f(\mathbf{x}^{1},\mathbf{x}^{2})|^{q}$ $\displaystyle\leq
B_{1}^{q}N_{1}\int_{\Omega_{1}}|f(\mathbf{y}^{1},\mathbf{x}^{2})|^{q}\,d\mu_{1}(\mathbf{y}^{1})$
$\displaystyle\leq
B_{1}^{q}N_{1}B_{2}^{q}N_{2}\int_{\Omega_{1}}\Bigl{[}\int_{\Omega_{2}}|f(\mathbf{y}^{1},\mathbf{y}^{2})|^{q}d\mu_{2}(\mathbf{y}^{2})\Bigr{]}\,d\mu_{1}(\mathbf{y}^{1}),$

where we used (3.5) for $i=1$ and the fact that $f(\cdot,\mathbf{x}^{2})\in
X(N_{1},1)$ in the first step, and (3.5) for $i=2$ and the fact that
$f(\mathbf{y}^{1},\cdot)\in X(N_{2},2)$ for each fixed
$\mathbf{y}^{1}\in\Omega_{1}$ in the second step. This proves the stated
inequality for $s=2$. The inequality for the general case $s\geq 2$ follows by
induction.

∎

Using Lemma 3.1, we may apply Corollary 2.2 to the space
$X_{N}:=\mathbf{X}_{\mathbf{N}}$ with $N=\prod_{i=1}^{s}N_{i}$ and
$B=\prod_{i=1}^{s}B_{i}$. We then obtain the following version of Proposition
3.2.

######  Proposition 3.3.

Let $2\leq q\leq p<\infty$. Suppose that the conditions (3.5) are satisfied
with $B_{i}\geq 1$, $i=1,\dots,s$. Then for a large enough constant $C=C(p,q)$
there exists a set $\xi(m)$ of

$m\leq
C\left(\prod_{i=1}^{s}B_{i}^{p}N_{i}^{p/q}\right)\left(\log_{2}(\prod_{i=1}^{s}(B_{i}N_{i}))\right)^{3}$
(3.8)

points $\xi^{j}\in\Omega$, $j=1,\dots,m$, such that

$\frac{1}{2}\|f\|_{p}^{p}\leq\frac{1}{m}\sum_{j=1}^{m}|f(\xi^{j})|^{p}\leq\frac{3}{2}\|f\|_{p}^{p},\
\ \forall f\in\mathbf{X}_{\mathbf{N}}.$ (3.9)

Clearly, Proposition 3.3 is a better version of Proposition 3.2. However,
there is no guarantee that the set $\xi(m)$ in Proposition 3.3 has the tensor
product structure. It would be interesting to prove an analog of Proposition
3.3 where the set $\xi(m)$ of points is given by a tensor product of subsets
of $\Omega_{i}$, $i=1,\cdots,s$ and the power of the log factor in the
estimate (3.8) is independent of $s$. An affirmative answer to this question
would yield a significant reduction of the log factor in the estimate (2.4) of
Theorem 2.2, as can be seen from the following simple lemma.

######  Lemma 3.2.

Let $X_{N}\subset{\mathcal{C}}(\Omega)$ be an $N$-dimensional subspace
satisfying

$\|f\|_{\infty}\leq BN^{1/p}\|f\|_{L_{p}(\Omega,\mu)},\quad\forall f\in
X_{N},$ (3.10)

for some $1\leq p<\infty$, and constant $B\geq 1$. Assume that $1\in X_{N}$
and there exists a positive constant $\alpha$ such that for each integer
$s\geq 2$, there exists a finite subset
$\Lambda=\Lambda_{1}\times\cdots\times\Lambda_{s}\subset\Omega^{s}$ such that
$|\Lambda|=|\Lambda_{1}|\cdots|\Lambda_{s}|\leq
C(p,s,\alpha)(B^{p}N)^{s}\left(\log_{2}(2BN)\right)^{\alpha}$ and

$\displaystyle\frac{1}{2}\|F\|_{L_{p}(\Omega^{s},\mu^{s})}^{p}\leq\frac{1}{|\Lambda|}\sum_{\omega\in\Lambda}|F(\omega)|^{p}\leq\frac{3}{2}\|F\|_{L_{p}(\Omega^{s},\mu^{s})}^{p},\
\ \forall F\in\mathbf{X}_{\mathbf{N}},$

where
$\mathbf{X}_{\mathbf{N}}:=\operatorname{span}\\{f_{1}(\mathbf{x}^{1})\times\cdots\times
f_{s}(\mathbf{x}^{s})\,:\,f_{i}\in X_{N},i=1,\dots,s\\}.$ Then for any
$\delta\in(0,1)$, there exist

$m\leq C(p,\delta,\alpha)B^{p}N(\log_{2}(2BN))^{\delta}$

points $\xi^{j}\in\Omega$, $j=1,\dots,m$, such that for any $f\in X_{N}$ we
have

$\frac{1}{2}\|f\|_{p}^{p}\leq\frac{1}{m}\sum_{j=1}^{m}|f(\xi^{j})|^{p}\leq\frac{3}{2}\|f\|_{p}^{p}.$

###### Proof.

Let $s\geq 2$ be an integer, and let
$\Lambda=\Lambda_{1}\times\cdots\times\Lambda_{s}$ be a finite subset of
$\Omega^{s}$ with the stated properties in Lemma 3.2. Without loss of
generality, we may assume that $|\Lambda_{1}|=\min_{1\leq i\leq
s}|\Lambda_{i}|$. Then

$|\Lambda_{1}|\leq C(p,s,\alpha)^{1/s}(B^{p}N)(\log_{2}(2BN))^{\alpha/s}.$

Let $f\in X_{N}$, and define

$F(\mathbf{x}^{1},\cdots,\mathbf{x}^{s}):=f(\mathbf{x}^{1}),\ \ \
\mathbf{x}:=(\mathbf{x}^{1},\cdots,\mathbf{x}^{s})\in\Omega^{s}.$

Clearly, $\|F\|_{L_{p}(\Omega^{s})}^{p}=\|f\|_{L_{p}(\Omega)}^{p}$ and

$\frac{1}{|\Lambda|}\sum_{\omega\in\Lambda}|F(\omega)|^{p}=\frac{1}{|\Lambda_{1}|}\sum_{\omega_{1}\in\Lambda_{1}}|f(\omega_{1})|^{p}.$

Since $1\in X_{N}$, we have $F\in\mathbf{X}_{\mathbf{N}}$. It then follows
that

$\frac{1}{2}\|f\|_{p}^{p}\leq\frac{1}{|\Lambda_{1}|}\sum_{\omega_{1}\in\Lambda_{1}}|f(\omega_{1})|^{p}\leq\frac{3}{2}\|f\|_{p}^{p}.$

∎

##  4 Sampling recovery

We first recall the setting of the optimal recovery. For a fixed integer $m$
and a set of points $\xi:=\\{\xi^{j}\\}_{j=1}^{m}\subset\Omega$, let $\Phi$ be
a linear operator from $\mathbb{C}^{m}$ into $L_{p}(\Omega,\mu)$. For a class
$\mathbf{F}\subset L_{p}(\Omega,\mu)$ (usually, centrally symmetric and
compact subset of $L_{p}(\Omega,\mu)$), define

$\varrho_{m}(\mathbf{F},L_{p}):=\inf_{\text{linear}\,\Phi;\,\xi}\sup_{f\in\mathbf{F}}\|f-\Phi(f(\xi^{1}),\dots,f(\xi^{m}))\|_{p}.$

The above described recovery procedure is a linear procedure. The following
modification of the above recovery procedure is also of interest. We now allow
any mapping $\Phi:\mathbb{C}^{m}\to X_{N}\subset L_{p}(\Omega,\mu)$, where
$X_{N}$ is a linear subspace of dimension $N\leq m$, and define

$\varrho_{m}^{*}(\mathbf{F},L_{p}):=\inf_{\Phi;\xi;X_{N},N\leq
m}\sup_{f\in\mathbf{F}}\|f-\Phi(f(\xi^{1}),\dots,f(\xi^{m}))\|_{p}.$

In both of the above cases we build an approximant, which comes from a linear
subspace of dimension at most $m$. It is natural to compare the quantities
$\varrho_{m}(\mathbf{F},L_{p})$ and $\varrho_{m}^{*}(\mathbf{F},L_{p})$ with
the Kolmogorov widths. Let $\mathbf{F}\subset L_{p}$ be a centrally symmetric
compact. The quantities

$d_{n}(\mathbf{F},L_{p}):=\operatornamewithlimits{inf}_{\\{u_{i}\\}_{i=1}^{n}\subset
L_{p}}\sup_{f\in\mathbf{F}}\operatornamewithlimits{inf}_{c_{i}}\left\|f-\sum_{i=1}^{n}c_{i}u_{i}\right\|_{p},\quad
n=1,2,\dots,$

are called the Kolmogorov widths of $\mathbf{F}$ in $L_{p}$. In the definition
of the Kolmogorov widths we take the element of best approximation of
$f\in\mathbf{F}$ as an approximating element from
$U:=\operatorname{span}\\{u_{i}\\}_{i=1}^{n}$. This means that in general
(i.e. if $p\neq 2$) this method of approximation is not linear.

We have the following obvious inequalities

$d_{m}(\mathbf{F},L_{p})\leq\varrho_{m}^{*}(\mathbf{F},L_{p})\leq\varrho_{m}(\mathbf{F},L_{p}).$
(4.1)

The main result of the paper [12] is the following general inequality.

######  Theorem 4.1.

There exist two positive absolute constants $c$ and $C$ such that for any
compact subset $\Omega$ of ${\mathbb{R}}^{d}$, any probability measure $\mu$
on it, and any compact subset $\mathbf{F}$ of ${\mathcal{C}}(\Omega)$ we have

$\varrho_{cn}(\mathbf{F},L_{2}(\Omega,\mu))\leq
Cd_{n}(\mathbf{F},L_{\infty}).$

We now formulate a conditional result from [12], which was used for the proof
of Theorem 4.1. Let $X_{N}$ be an $N$-dimensional subspace of the space of
continuous functions ${\mathcal{C}}(\Omega)$. For a fixed $m$ and a set of $m$
points $\xi:=\\{\xi^{\nu}\\}_{\nu=1}^{m}\subset\Omega$, we associate a
function $f\in{\mathcal{C}}(\Omega)$ with a vector

$S(f,\xi):=(f(\xi^{1}),\dots,f(\xi^{m}))\in\mathbb{C}^{m}.$

Define

$\|S(f,\xi)\|_{p}:=\left(\frac{1}{m}\sum_{\nu=1}^{m}|f(\xi^{\nu})|^{p}\right)^{1/p},\quad
1\leq p<\infty,$

and

$\|S(f,\xi)\|_{\infty}:=\max_{\nu}|f(\xi^{\nu})|.$

For a positive weight
$\mathbf{w}:=(w_{1},\dots,w_{m})\in{\mathbb{R}}_{+}^{m}$, consider the
following norm

$\|S(f,\xi)\|_{p,\mathbf{w}}:=\left(\sum_{\nu=1}^{m}w_{\nu}|f(\xi^{\nu})|^{p}\right)^{1/p},\quad
1\leq p<\infty.$

Define the best approximation of $f\in L_{p}(\Omega,\mu)$, $1\leq p\leq\infty$
by elements of $X_{N}$ as follows

$d(f,X_{N})_{p}:=\inf_{u\in X_{N}}\|f-u\|_{p}.$

It is well known that there exists an element, which we denote by
$P_{X_{N},p}(f)\in X_{N}$, such that

$\|f-P_{X_{N},p}(f)\|_{p}=d(f,X_{N})_{p}.$

The operator $P_{X_{N},p}:L_{p}(\Omega,\mu)\to X_{N}$ is called the Chebyshev
projection.

Theorem 4.2 below was proved in [12] under the following assumptions.

A1. Discretization. Let $1\leq p\leq\infty$. Suppose that
$\xi:=\\{\xi^{j}\\}_{j=1}^{m}\subset\Omega$ is such that for any $u\in X_{N}$
in the case $1\leq p<\infty$ we have

$C_{1}\|u\|_{p}\leq\|S(u,\xi)\|_{p,\mathbf{w}}$

and in the case $p=\infty$ we have

$C_{1}\|u\|_{\infty}\leq\|S(u,\xi)\|_{\infty}$

with a positive constant $C_{1}$ which may depend on $d$ and $p$.

A2. Weights. Suppose that there is a positive constant $C_{2}=C_{2}(d,p)$ such
that $\sum_{\nu=1}^{m}w_{\nu}\leq C_{2}$.

Consider the following well known recovery operator (algorithm)

$\ell p\mathbf{w}(\xi)(f):=\ell
p\mathbf{w}(\xi,X_{N})(f):=\text{arg}\min_{u\in
X_{N}}\|S(f-u,\xi)\|_{p,\mathbf{w}}.$

Note that the above algorithm $\ell p\mathbf{w}(\xi)$ only uses the function
values $f(\xi^{\nu})$, $\nu=1,\dots,m$. In the case $p=2$ it is a linear
algorithm – orthogonal projection with respect to the norm
$\|\cdot\|_{2,\mathbf{w}}$. Therefore, in the case $p=2$ approximation error
by the algorithm $\ell 2\mathbf{w}(\xi)$ gives an upper bound for the recovery
characteristic $\varrho_{m}(\cdot,L_{2})$. In the case $p\neq 2$ approximation
error by the algorithm $\ell p\mathbf{w}(\xi)$ gives an upper bound for the
recovery characteristic $\varrho_{m}^{*}(\cdot,L_{p})$.

######  Theorem 4.2.

Under assumptions A1 and A2 for any $f\in{\mathcal{C}}(\Omega)$ we have for
$1\leq p<\infty$

$\|f-\ell
p\mathbf{w}(\xi,X_{N})(f)\|_{p}\leq(2C_{1}^{-1}C_{2}^{1/p}+1)d(f,X_{N})_{\infty}.$

Under assumption A1 for any $f\in{\mathcal{C}}(\Omega)$ we have

$\|f-\ell\infty(\xi,X_{N})(f)\|_{\infty}\leq(2C_{1}^{-1}+1)d(f,X_{N})_{\infty}.$

Theorem 4.2 is devoted to recovery by weighted least squares algorithms $\ell
p\mathbf{w}(\xi)$. It requires a discretization theorem with positive weights
$\mathbf{w}$. There is such a theorem from [7] for $p=2$ and a general
subspace $X_{N}$ of $L_{2}(\Omega,\mu)$, which we formulate as follows.

######  Theorem 4.3.

There exist three absolute positive constants $C_{0},c_{0},C_{0}^{\prime}$
such that for every $N$-dimensional subspace $X_{N}$ of $L_{2}(\Omega,\mu)$,
there exist $m\leq C_{0}^{\prime}N$ points $\xi^{1},\cdots,\xi^{m}\in\Omega$
and positive weights $w_{1},\cdots,w_{m}$ such that

$\displaystyle c_{0}\|f\|_{2}^{2}\leq\sum_{j=1}^{m}w_{j}|f(\xi^{j})|^{2}\leq
C_{0}\|f\|_{2}^{2},\ \ \forall f\in X_{N}.$ (4.2)

For a fixed integer $m\geq 1$ and a class
$\mathbf{F}\subset{\mathcal{C}}(\Omega)$ (usually, a centrally symmetric
compact in ${\mathcal{C}}(\Omega)$), we define

$\varrho_{m}^{wls}(\mathbf{F},L_{2}):=\inf_{\xi,\mathbf{w},X_{N},N\leq
m}\sup_{f\in\mathbf{F}}\|f-\ell 2\mathbf{w}(\xi,X_{N})(f)\|_{2},$

where the infimum is taken over all $N$-dimensional subspaces $X_{N}\subset
L_{2}(\Omega,\mu)$ with $N\leq m$, all collections
$\xi:=\\{\xi^{j}\\}_{j=1}^{m}\subset\Omega$ of $m$ points in $\Omega$, and all
positive weights $\mathbf{w}=(w_{1},\cdots,w_{m})\in\mathbb{R}_{+}^{m}$.

Note that if we assume in addition that $1\in X_{N}$ in Theorem 4.3, then the
weights $w_{j}$ in (4.2) satisfy $\sum_{j=1}^{m}w_{j}\leq C_{0}$. As a result,
Theorem 4.3 combined with Theorem 4.2 gives an analog of the following Theorem
4.4 from [12].

######  Theorem 4.4.

There exist two positive absolute constants $c$ and $C$ such that for any
compact subset $\Omega$ of ${\mathbb{R}}^{d}$, any probability measure $\mu$
on it, and any compact subset $\mathbf{F}$ of ${\mathcal{C}}(\Omega)$ we have

$\varrho_{cn}^{wls}(\mathbf{F},L_{2}(\Omega,\mu))\leq
Cd_{n}(\mathbf{F},L_{\infty}).$

We may want the recovery algorithm $\ell 2\mathbf{w}(\xi)$ to be the classical
least square algorithm, i.e. $\mathbf{w}=\mathbf{w}_{m}:=(1/m,\dots,1/m)$. For
that we need an $L_{2}$\- discretization theorem with equal weights. There is
such a theorem from [7] under an extra assumption on the subspace $X_{N}$:

Condition E($t$). We say that an orthonormal system
$\\{u_{i}(\mathbf{x})\\}_{i=1}^{N}$ defined on $\Omega$ satisfies Condition
E($t$) with a constant $t>0$ if for all $\mathbf{x}\in\Omega$

$\sum_{i=1}^{N}|u_{i}(\mathbf{x})|^{2}\leq Nt^{2}.$

Under Condition E($t$), we have the following discretization theorem, which
was proved in [7]:

######  Theorem 4.5.

Let $\Omega\subset{\mathbb{R}}^{d}$ be a compact set with the probability
measure $\mu$. Assume that $\\{u_{i}(\mathbf{x})\\}_{i=1}^{N}$ is a real (or
complex) orthonormal system in $L_{2}(\Omega,\mu)$ satisfying Condition E($t$)
for some constant $t>0$. Then there exists a set
$\\{\xi^{j}\\}_{j=1}^{m}\subset\Omega$ of $m\leq C_{1}t^{2}N$ points such that
for any $f=\sum_{i=1}^{N}c_{i}u_{i}$ we have

$C_{2}\|f\|_{2}^{2}\leq\frac{1}{m}\sum_{j=1}^{m}|f(\xi^{j})|^{2}\leq
C_{3}t^{2}\|f\|_{2}^{2},$

where $C_{1},C_{2}$ and $C_{3}$ are absolute positive constants.

Recall that
$\mathbf{w}_{m}=(\frac{1}{m},\cdots,\frac{1}{m})\in\mathbb{R}^{m}$. For a
fixed positive integer $m$ and a class
$\mathbf{F}\subset{\mathcal{C}}(\Omega)$ (usually, a centrally symmetric
compact in ${\mathcal{C}}(\Omega)$), define

$\varrho_{m}^{ls}(\mathbf{F},L_{2}):=\inf_{\xi,\,X_{N},N\leq
m}\sup_{f\in\mathbf{F}}\|f-\ell 2\mathbf{w}_{m}(\xi,X_{N})(f)\|_{2},$

where the infimum is taken over all $N$-dimensional subspaces $X_{N}\subset
L_{2}(\Omega,\mu)$ with $N\leq m$, and all collections
$\xi:=\\{\xi^{j}\\}_{j=1}^{m}\subset\Omega$ of $m$ points in $\Omega$. We now
define $E(t)$-conditioned Kolmogorov widths by

$d_{N}^{E(t)}(\mathbf{F},L_{p}):=\inf_{\\{u_{1},\dots,u_{N}\\}\,\text{satisfies
Condition}E(t)}\sup_{f\in\mathbf{F}}\inf_{c_{1},\dots,c_{N}}\|f-\sum_{i=1}^{N}c_{i}u_{i}\|_{p}.$

Now combining Theorem 4.5 with Theorem 4.2, we obtain the following result,
which was proved in [12].

######  Theorem 4.6.

Let $\mathbf{F}$ be a compact subset of ${\mathcal{C}}(\Omega)$. There exist
two positive constants $c$ and $C$ which may depend on $t$ such that

$\varrho_{cn}^{ls}(\mathbf{F},L_{2})\leq
Cd_{n}^{E(t)}(\mathbf{F},L_{\infty}).$

We now present some results on the sampling recovery in $L_{p}$, $2<p<\infty$.
For a fixed positive integer $m$, and a class
$\mathbf{F}\subset{\mathcal{C}}(\Omega)$ (usually, a centrally symmetric
compact in ${\mathcal{C}}(\Omega)$), we define

$\varrho_{m}^{lp}(\mathbf{F},L_{p}):=\inf_{\xi,\,X_{N},N\leq
m}\sup_{f\in\mathbf{F}}\|f-\ell p\mathbf{w}_{m}(\xi,X_{N})(f)\|_{p},$

where the infimum is taken over all $N$-dimensional subspaces $X_{N}\subset
L_{p}(\Omega,\mu)$ with $N\leq m$, and all collections
$\xi:=\\{\xi^{j}\\}_{j=1}^{m}\subset\Omega$ of $m$ points in $\Omega$.

Condition NpB. We say that an $N$-dimensional subspace $X_{N}\subset
L_{p}(\Omega,\mu)$ satisfies Condition NpB (Nikol’skii-type inequality for the
pair $(p,\infty)$) if for all $\mathbf{x}\in\Omega$ we have for all $f\in
X_{N}$

$|f(\mathbf{x})|\leq BN^{1/p}\|f\|_{p},$

where $B\geq 1$ is a constant. It is well known that Condition E($t$) is
equivalent to Condition N2$t$ (see, for instance, [7] for an explanation and
[4] for a detailed discussion).

We now define the NpB-conditioned Kolmogorov width by

$d_{N}^{NpB}(\mathbf{F},L_{p}):=\inf_{X_{N}\,\text{satisfies Condition
NpB}}\sup_{f\in\mathbf{F}}\inf_{g\in X_{N}}\|f-g\|_{p}.$

Theorem 2.2 combined with Theorem 4.2 gives the following analog of Theorem
4.6.

######  Theorem 4.7.

Let $\mathbf{F}$ be a compact subset of ${\mathcal{C}}(\Omega)$. For
$p\in(2,\infty)$ and every constant $B\geq 1$, there exist two positive
constants $c$ and $C$, which may depend on $p$, such that

$\varrho_{m}^{lp}(\mathbf{F},L_{p})\leq Cd_{n}^{NpB}(\mathbf{F},L_{\infty})$

provided $m\geq cB^{p}n(\log(2Bn))^{3}$.

Corollary 2.2 combined with Theorem 4.2 gives the following generalization of
Theorem 4.7.

######  Theorem 4.8.

Let $\mathbf{F}$ be a compact subset of ${\mathcal{C}}(\Omega)$, and let
$2\leq q\leq p<\infty$. Let $B\geq 1$ be a given constant. Then there exist
two positive constants $c$, $C$, which may depend on $q,p$, such that

$\varrho_{m}^{lp}(\mathbf{F},L_{p})\leq Cd_{n}^{NqB}(\mathbf{F},L_{\infty})$

provided $m\geq cB^{p}n^{p/q}(\log(2Bn))^{3}$.

Condition EqB. We say that an $N$-dimensional subspace $X_{N}\subset
L_{p}(\Omega,\mu)$ satisfies Condition EqB (Entropy condition with parameters
$q$ and $B$) if it satisfies inequalities (2.1).

Using Corollary 2.1 and Theorem 4.2 we obtain the following version of Theorem
4.8.

######  Theorem 4.9.

Let $\mathbf{F}$ be a compact subset of ${\mathcal{C}}(\Omega)$ and let $1\leq
q\leq p<\infty$. There exist two positive constants $c$ and $C$ which may
depend on $p$ and $q$ such that

$\varrho_{m}^{lp}(\mathbf{F},L_{p})\leq Cd_{n}^{EqB}(\mathbf{F},L_{\infty})$

provided $m\geq cB^{p}n^{p/q}(\log(2Bn))^{2}$.

## References

  * [1] F. Dai, A. Prymak, V.N. Temlyakov, and S.U. Tikhonov, Integral norm discretization and related problems, Russian Math. Surveys 74:4 (2019), 579–630. Translation from Uspekhi Mat. Nauk 74:4(448) (2019), 3–58; arXiv:1807.01353v1.
  * [2] F. Dai, A. Prymak, A. Shadrin, V. Temlyakov, S. Tikhonov, Sampling discretization of integral norms, Constructive Approximation, https://doi.org/10.1007/s00365-021-09539-0; Published online: 08 April 2021; arXiv:2001.09320v1 [math.CA] 25 Jan 2020.
  * [3] F. Dai, A. Prymak, A. Shadrin, V. Temlyakov, and S. Tikhonov, Entropy numbers and Marcinkiewicz-type discretization theorem, J. Functional Analysis 281 (2021) 109090; arXiv:2001.10636v1 [math.CA] 28 Jan 2020.
  * [4] Z. Ditzian and A. Prymak, On Nikol’skii inequalities for domains in ${\mathbb{R}}^{d}$, Constr. Approx., 44 (2016), 23–51.
  * [5] B. Kashin, E. Kosov, I. Limonova, and V. Temlyakov, Sampling discretization and related problems, arXiv:2109.07567v1 [math.FA] 15 Sep 2021.
  * [6] E. Kosov, Marcinkiewicz-type discretization of $L^{p}$-norms under the Nikolskii-type inequality assumption, J. Math. Anal. Appl. 504:1 (2021), 125358.
  * [7] I. Limonova and V. Temlyakov, On sampling discretization in $L_{2}$, arXiv:2009.10789v1 [math.FA] 22 Sep 2020.
  * [8] V.N. Temlyakov, Greedy Approximation, Cambridge University Press, 2011.
  * [9] V.N. Temlyakov, The Marcinkiewicz-type discretization theorems, Constructive Approximation, 48 (2018), 337–369; arXiv: 1703.03743v1 [math.NA] 10 Mar 2017.
  * [10] V. Temlyakov, Multivariate Approximation, Cambridge University Press, 2018.
  * [11] V. Temlyakov, Sampling discretization of integral norms of the hyperbolic cross polynomials, Trudy MIAN, 312 (2021), 282-293; Engl. Translation in Proceedings of the Steklov Institute of Mathematics, 312 2021, 270–281.
  * [12] V.N. Temlyakov, On optimal recovery in $L_{2}$, J. Complexity, 65, (2021), 101545; Available online 19 December 2020, 101545; doi: https://doi.org/10.1016/j.jco.2020.101545; arXiv:2010.03103v1 [math.NA] 7 Oct 2020.

F. Dai,  Department of Mathematical and Statistical Sciences
University of Alberta
Edmonton, Alberta T6G 2G1, Canada
E-mail<EMAIL_ADDRESS>
V.N. Temlyakov, University of South Carolina,
Steklov Institute of Mathematics,
Lomonosov Moscow State University,
and Moscow Center for Fundamental and Applied Mathematics.
E-mail<EMAIL_ADDRESS>


# Resource-efficient DNNs for Keyword Spotting using Neural Architecture
Search and Quantization

David Peter  Signal Processing and
Speech Communication Laboratory
Graz University of Technology
Graz, Austria
<EMAIL_ADDRESS>Wolfgang Roth  Signal Processing and
Speech Communication Laboratory
Graz University of Technology
Graz, Austria
<EMAIL_ADDRESS>Franz Pernkopf  Signal Processing and
Speech Communication Laboratory
Graz University of Technology
Graz, Austria
<EMAIL_ADDRESS>
###### Abstract

This paper introduces neural architecture search (NAS) for the automatic
discovery of small models for keyword spotting (KWS) in limited resource
environments. We employ a differentiable NAS approach to optimize the
structure of convolutional neural networks (CNNs) to maximize the
classification accuracy while minimizing the number of operations per
inference. Using NAS only, we were able to obtain a highly efficient model
with 95.4% accuracy on the Google speech commands dataset with 494.8 kB of
memory usage and 19.6 million operations. Additionally, weight quantization is
used to reduce the memory consumption even further. We show that weight
quantization to low bit-widths (e.g. 1 bit) can be used without substantial
loss in accuracy. By increasing the number of input features from 10 MFCC to
20 MFCC we were able to increase the accuracy to 96.3% at 340.1 kB of memory
usage and 27.1 million operations.

###### Index Terms:

keyword spotting, neural architecture search, weight quantization

##  I Introduction

Automatic speech recognition (ASR) is becoming an increasingly important
technology for user interaction with everyday consumer devices. However, ASR
systems are typically complex and computation-intensive, i.e. running ASR in
always-on mode results in a steady high energy consumption. This is especially
problematic for mobile devices whose batteries are drained quickly when
running ASR permanently.

A common approach to this challenge is to run a low-cost keyword spotting
(KWS) system that is listening permanently only for a limited set of
prespecified keywords. Upon detection of such a keyword, a full ASR system is
triggered which then listens for a rich set of user commands.

The requirements of a KWS system are:

  1. i.

The system should be resource-efficient to mitigate the aforementioned energy
problem,

  2. ii.

it should run in real-time, and

  3. iii.

it should be accurate to maintain a high user-experience.

In this paper, we aim to find efficient and small KWS models for limited
resource environments. We make use of neural architecture search (NAS) — a
popular technique to automate the design of deep neural network (DNN)
architectures. A NAS algorithm tries to find the best performing neural
network architecture within a given search space using some arbitrary search
method. To obtain efficient DNN models we use the techniques from ProxylessNAS
[1]. However, unlike ProxylessNAS [1] whose focus is on finding models for
large-scale image classification tasks such as ImageNet, our focus lies on
small-scale KWS tasks such as Google speech commands [2].

We quantize model weights during NAS by default to 8 bits to better compare to
[3]. In [3], model weights are also quantized to 8 bits. Using NAS we obtain a
model with 95.4% accuracy on the test set of the Google speech commands
dataset [2] while using 494.8 kB of memory (for the storage of weights) and
19.6 million operations per inference. Once the efficient DNN architecture has
been found, we compare different weight quantization schemes to show that the
memory requirements can be reduced even further. Compressing the weights of
this model to 1 bit allowed us to retain a test accuracy of 94.7% while only
using 61.85 kB of memory and 19.6 million operations.

Furthermore, we show that the number of features extracted from the raw audio
waveform has a substantial impact on the performance. By changing the number
of extracted MFCC features from 10 to 20 we were able to find a model with a
test accuracy of 96.3% using 340.1 kB of memory and 27.1 million operations.

The outline of the paper is as follows: Section II introduces the related
work. In Section III we present our NAS configuration, the trade-off objective
between accuracy and number of operations, and the weight quantization methods
utilized in this paper. The experimental setup and the discussion of the
results is shown in Section IV. Finally, Section V provides the conclusion.
Code related to the paper is available online at
https://github.com/dapeter/nas-for-kws.

##  II Related Work

Popular NAS approaches use concepts such as reinforcement learning [4],
gradient based methods [5] or even evolutionary methods [6] for exploring the
search space. Recently, NAS techniques have also been used to find
architectures that are specifically tailored to the underlying hardware [1, 7]
by, for instance, additionally minimizing memory requirements, number of
operations, or latency of the resulting model. Therefore, NAS techniques are
well-suited for finding DNNs that run on mobile phones or even embedded
devices.

Conventional NAS algorithms require thousands of architectures to be trained
to find the final architecture. Not only is this very time consuming but in
some cases even infeasible, especially for large-scale tasks such as ImageNet
or when computational resources are limited. Therefore, several proposals have
been made to reduce the computational overhead. So called _proxy tasks_ for
reducing the search cost are training for fewer epochs, training on a smaller
dataset or learning a smaller model that is then scaled up. As an example, [8]
searches for the best convolutional layer on the CIFAR-10 dataset which is
then stacked and applied to the much larger ImageNet dataset. Many other NAS
methods implement this technique with great success [9, 10, 11, 5, 7, 12].
Another approach, called EfficientNet [13], employs the NAS approach from [7]
to find a small baseline model which is subsequently scaled up. By scaling the
three dimensions depth, width and resolution of the small baseline model, they
obtain state-of-the-art performance.

Although model scaling and stacking achieves good performances, the
convolutional layers optimized on the proxy task may not be optimal for the
target task. Therefore, several approaches have been proposed to get rid of
proxy tasks. Instead, architectures are directly trained on the target task
and optimized for the hardware at hand. In [1] an overparameterized network
with multiple parallel candidate operations per layer is used as the base
model. Every candidate operation is gated by a binary gate which either prunes
or keeps the operation. During architecture search, the binary gates are then
trained such that only one operation per layer remains and the targeted memory
and latency requirements are met. This is extended in [14] by using shared
parameters among individual layers to avoid excessive parameter overhead
during training.

In KWS, models using neural networks for keyword classification have become
increasingly popular. They are not only easy to train, but they also achieve
state-of-the-art performances on image and speech classification tasks. In [3]
several models from the literature [15, 16, 17, 18] are evaluated on the
Google speech commands dataset [2]. They compare their models in terms of
accuracy, memory requirements and number of operations. To allow easy
deployment on microcontrollers they train their models using 32 bit float
numbers and quantize the weights after training to 8 bit fixed-point numbers.
They argue that fixed point numbers have been shown to suffice to run neural
networks with minimal loss in accuracy [19, 20, 21]. We use the results from
[3] in our experiments as a baseline for our models.

In binarized neural networks (BNNs) the resolution of both weights and
activations is reduced to binary values $\\{-1,1\\}$ [22] while still
retaining state-of-the art performance on image classification tasks such as
MNIST, CIFAR-10 and SVHN. BNNs rely on the straight-through estimator (STE)
[23, 24] which approximates the gradient of non-differentiable or piecewise
constant functions, such as quantizers, by the non-zero gradient of some other
function. The STE was also used in [22] to substitute the derivative of
piecewise-constant functions. Another method for quantizing neural networks
involves a Bayesian approach to learn weight distributions over discrete
weights [25]. The discrete-weight network is then obtained by selecting the
most probable weights. For a comprehensive overview of resource-efficient
methods for DNNs, we refer the interested reader to [26].

##  III Methods

###  III-A Neural Architecture Search

We use convolutional neural networks (CNNs) for keyword classification. Our
goal is to find well performing architectures for different computing regimes.
To achieve this, we use the multi-objective NAS approach from [1] called
ProxylessNAS. In ProxylessNAS, hardware-aware optimization is performed by NAS
to optimize the model accuracy and latency on different hardware platforms.
However, we optimize for accuracy and number of operations and not for
latency. By optimizing for number of operations, the model size is implicitly
optimized as well. The trade-off between the accuracy and the number of
operations is established by regularizing the architecture loss as explained
in Section III-B.

ProxylessNAS constructs an overparameterized network with multiple parallel
candidate operations per layer as the base model. A single operation is
denoted by $o_{i}$. Every operation is assigned a real-valued architecture
parameter $\alpha_{i}$. The $N$ architecture parameters are transformed to
probability values $p_{i}$ by applying the softmax function

$p_{i}=\frac{\exp(\alpha_{i})}{\sum_{j}\exp(\alpha_{j})}.$ (1)

Every candidate operation is gated by a binary gate $g_{i}$ which either
prunes or keeps the operation. Only one gate per layer is active at a time.
Gates are sampled randomly according to

$[g_{1},g_{2},\dots,g_{N}]=\begin{cases}[1,0,\dots,0]&\text{with prob.
}p_{1},\\\ [0,1,\dots,0]&\text{with prob. }p_{2},\\\ \,\quad\quad\dots\\\
[0,0,\dots,1]&\text{with prob. }p_{N}.\\\ \end{cases}.$ (2)

Based on the binary gates and the layer input $x$, the output of the mixed
operation $m_{\mathcal{O}}^{\mathrm{Binary}}$ (i.e. the output of the layer)
is defined as

$m_{\mathcal{O}}^{\mathrm{Binary}}=\sum_{i=1}^{N}g_{i}o_{i}(x).$ (3)

During architecture search, the training of the architecture parameters
$\alpha_{i}$ and the weight parameters of the operations $o_{i}$ are performed
in an alternating manner. When training weight parameters, the architecture
parameters are frozen and binary gates are sampled according to (2). Weight
parameters are then updated via standard gradient descent on the training set.
When training architecture parameters, the weight parameters are frozen and
the architecture parameters are updated on the validation set. Updating the
architecture parameters via backpropagation requires computing $\partial
L/\partial\alpha_{i}$ which is not defined due to the sampling in (2).
ProxylessNAS proposes two methods for estimating the gradient. Method one
estimates the gradient of $\partial L/\partial p_{i}$ as $\partial L/\partial
g_{i}$. This estimation is an application of the STE explained in Section
III-C. With this estimation, backpropagation can be used to compute $\partial
L/\partial\alpha_{i}$ since the gates $g_{i}$ are part of the computation
graph and thus $\partial L/\partial g_{i}$ can be calculated using
backpropagation. Method two utilizes REINFORCE [27] to find the optimal binary
gates that maximize a certain reward $R(\cdot)$. The reward $R(\cdot)$ is
directly proportional to the model accuracy and inversely proportional to the
number of operations of the model. We did not observe any benefits of using
REINFORCE over the gradient based approach. Therefore, we use the gradient
based approach in our experiments to approximate the gradient.

Our overparameterized network, shown in Table I, consist of three stages, (i)
an input stage, (ii) an intermediate stage, and (iii) an output stage. Stages
(i) and (iii) are fixed to a 5$\times$11 convolution and a 1$\times$1
convolution respectively. The network size is lower bounded by the size of
stage (i) and stage (iii), which however is negligible regarding the overall
model size. We apply batch normalization [28] followed by the ReLU [29] non-
linearity as an activation function after the convolutions of stages (i) and
(iii). We use mobile inverted bottleneck convolutions (MBCs) [30] as our main
building blocks in stage (ii).

Only convolutions from stage (ii) are optimized. MBCs have two learnable
parameters, the expansion rate $e$ and the size $k$ of the quadratic
$k$$\times$$k$ convolution kernel. MBCs consist of three separate
convolutions, one 1$\times$1 convolution followed by a depthwise-separable
3$\times$3 convolution followed again by a 1$\times$1 convolution. The first
two convolutions use batch normalization and ReLU activation functions. The
third convolution only uses batch normalization. The first and third
1$\times$1 convolution change the number of feature maps by the expansion rate
factor of $e$ and $1/e$ respectively. Stride (as stated in Table I) is only
applied to the first convolution of each stage. The stride can be different
along certain dimensions. Therefore it is parametrized by (H, W), where H is
the stride along the height and W is the stride along the width of a certain
feature map.

During NAS, we allow MBCs with expansion rates $e\in\\{1,2,3,4,5,6\\}$ and
kernel sizes $k\in\\{3,5,7\\}$ for selection. We also include the zero
operation. Therefore, our overparameterized network has $\\#e\cdot\\#k+1=19$
binary gates per layer. For blocks where the input feature map size is equal
to the output feature map size we include skip connections. If a zero
operation is selected as a block by NAS, the skip connection allows this
particular layer to be skipped similar to [1] resulting in an identity layer.

TABLE I: Three stage model used for the KWS task. Stages (i) and (iii) are fixed to a 5$\times$11 convolution and a 1$\times$1 convolution respectively. Stage (ii) convolutions are optimized. Stage | Operation | Stride (H, W) | #Channels | #Layers
---|---|---|---|---
(i) | Conv, 5$\times$11 | 1, 2 | 72 | 1
(ii) | MBC[e], [k]$\times$[k] | 2, 2 | 72 | 12
| or Identity |  |  |
(iii) | Conv, 1$\times$1 | 1, 1 | 144 | 1
| Global Avg. Pooling |  |  |
| Fully connected |  |  |

###  III-B Accuracy and Operations Trade-off Objective

The trade-off between the network accuracy and the number of operations is
established by regularizing the architecture loss similar as in [1] according
to

$\mathrm{loss}_{arch}=\mathrm{CE}_{loss}\cdot\left(\frac{\log(\mathrm{ops}_{exp})}{\log(\mathrm{ops}_{target})}\right)^{\beta}$
(4)

where $\mathrm{CE}_{loss}$ is the cross entropy loss, $\mathrm{ops}_{exp}$ the
expected number of operations, $\mathrm{ops}_{target}$ the target number of
operations and $\beta$ the regularization parameter. The expected number of
operations $\mathrm{ops}_{exp}$ is the overall number of operations expected
to be used in the convolutions and in the fully connected layer based on the
probabilities $p_{i}$ of the final network. For stages (i) and (iii) we simply
sum the number of operations used in the convolutions and in the fully
connected layer. For stage (ii) layers, the expected number of operations is
defined as the weighted sum of the numbers of operations used in $o_{i}$
weighted by the probabilities $p_{i}$.

Establishing an accuracy/operations trade-off using (4) is usually achieved by
fixing $\mathrm{ops}_{target}$ and choosing $\beta$ such that the number of
operations of the final architecture after NAS are close to
$\mathrm{ops}_{target}$. If $\mathrm{ops}_{target}$ is close to
$\mathrm{ops}_{exp}$, the right term of (4) becomes one thus leaving the
$\mathrm{CE}_{loss}$ unchanged. However, if $\mathrm{ops}_{exp}$ is larger or
smaller than $\mathrm{ops}_{target}$, the $\mathrm{CE}_{loss}$ is scaled up or
down respectively.

In our work, we focus on obtaining a wide variety of networks with a different
number of operations, rather than reaching a certain number of target
operations. Therefore, we kept $\mathrm{ops}_{target}$ fixed while varying
$\beta$. Varying $\beta$ while fixing $\mathrm{ops}_{target}$ resulted in more
diverse networks in terms of number of operations than fixing $\beta$ and
varying $\mathrm{ops}_{target}$.

###  III-C Weight Quantization

Our goal is to find resource efficient models for limited resource
environments. Therefore, we use weight quantization to reduce the model size
in terms of memory consumption even further. Unless noted otherwise, we
quantize our model weights to 8 bits during NAS. This allows us to compare our
models to the quantized 8 bit models in [3] while also reducing the model size
substantially.

We perform quantization similar to quantizek in [31]. quantizek takes a real-
valued input $r_{i}\in[0,1]$ and quantizes it to a $k$ bit number
$r_{o}\in[0,1]$. However, we want to quantize real-valued weights
$w\in\mathbb{R}$ to $k$ bit weights $w_{q}\in[-1,1]$. We achieve this by
extending quantizek to

$w_{q}=2\cdot\left[\frac{1}{2^{k}-1}\mathrm{round}\left((2^{k}-1)\frac{w+1}{2}\right)\right]_{0}^{1}-1$
(5)

where $[x]_{a}^{b}$ is the clamping function

$[x]_{a}^{b}=\max(a,\min(x,b))\in[a,b].$ (6)

The real-valued weights are quantized to a set of discrete values
$\\{q_{1},q_{2},\dots,q_{N}\\}$. The quantizer is uniform since the
quantization steps $q_{i+1}-q_{i}$ are equal. Non-uniform quantization is used
by some methods by applying a linear quantization to the logarithm of the
input [32]. Furthermore, our quantizer is a Mid-Rise type quantizer which
means that the origin is not included in the set of discrete output values. In
contrast, a Mid-Tread type quantizer includes the origin in the set of
discrete output values.

We compare two techniques for quantization: bit-rounding as a post-processing
step and quantization aware training using the STE. Both techniques use (5) to
quantize the weights between +1 and -1.

Bit-rounding as a post-processing step is performed after training by simply
quantizing the weights according to (5). The STE is used to quantize the
weights during training. The STE approximates the gradient of functions that
are non-differentiable or whose gradient is zero almost everywhere such as
quantization functions. We apply the quantizer from (5) to quantize the
weights during the forward pass. During backpropagation, the zero-gradient of
the quantizer is replaced by the non-zero gradient of the linear function
$f(x)=x$, i.e., $f^{\prime}(x)=1$, which essentially passes the gradient
through the quantizer. This allows us to train the network while
simultaneously quantizing the weights.

Figure 1 illustrates weight quantization using the STE on a typical
convolutional layer (without batch normalization). During the forward pass,
the quantizer $Q$ performs the quantization of the weight tensor
$\mathbf{W}^{l}$ according to (5). During the backward pass, the STE replaces
the derivative of the quantizer $Q$ by the derivative of the identity
function. In this way, the gradient can propagate back to $\mathbf{W}^{l}$.

Generally, we observe that quantization aware training with the STE performs
better than bit-rounding as a post-processing step (cf. Section IV-D).

Figure 1: Weight quantization using the STE on a typical convolutional layer
(without batch normalization). Red boxes have zero gradients whereas green
boxes have non-zero gradients. Weight updates are performed to the blue
circle. During the forward pass, the weight tensor $\mathbf{W}^{l}$ is
quantized to obtain the $k$ bit weight tensor $\mathbf{W}^{l}_{q}$ used in the
convolution. The activation function is then applied to the output of the
convolution $\mathbf{a}^{l+1}$ to obtain $\mathbf{x}^{l+1}$ which is the input
tensor of the subsequent layer. During the backward pass, the STE replaces the
derivative of the quantizer by the derivative of the identity function id.
Note that the activations are not quantized.

##  IV Experiments

###  IV-A Dataset

We use the first version of the Google speech commands dataset [2]. It
consists of 65.000 1-second long audio files sampled with 16 bit at 16 kHz
sampling frequency. Every audio file contains one utterance of an english word
spoken by one person. In total there are 30 words spoken by thousands of
people. The words are grouped into 30 different classes. We follow the
procedure of [3] and use the following 10 classes ”Yes”, ”No”, ”Up”, ”Down”,
”Left”, ”Right”, ”On”, ”Off”, ”Stop” and ”Go” from the dataset. Likewise, we
also include an ”unknown” class which is a blend of randomly selected samples
from the remaining 20 classes. Furthermore, a ”silence” class is added. The
”silence” class is artificially generated and consists of 1-second audio files
containing a random slice of audio from a randomly selected noise sample
provided by the Google Speech commands dataset. We made sure that the number
of samples in the ”unknown” class and in the ”silence” class is equal to the
average number of samples in all 30 classes to obtain equal class sizes. Our
test set consists of the keyword samples from the test set and includes the
same random selection of samples from the ”unknown” and the ”silence” class as
used in [3] to make our results comparable.

###  IV-B Experimental Setup

We extract MFCC features from the raw audio streams before performing
classification. Unless noted otherwise, we extract 10 MFCC features per 40ms
frame. We use a stride length of 20ms which yields a total of 10$\times$51
features per 1 second of audio.

We augment all training samples with a random time shift of up to 100ms.
Furthermore, 80% of the training data is augmented with background noise. We
use the noise samples from the Google speech commands dataset. It includes
environmental sounds, speech, as well as white and pink noise. If a sample is
augmented, it is first time shifted and then, in 80% of the cases, overlayed
with a 1 second interval of a random noise sample. The desired signal and the
noise signal are mixed in a $(1-\epsilon):\epsilon$ ratio using
$\epsilon\sim\mathcal{U}(0,0.1)$.

Before actually performing the architecture search we pretrain the
architecture blocks for 40 epochs at a learning rate of 0.05. During
pretraining, architecture blocks are randomly sampled and trained on one batch
of the training set. Sampling and training repeats until 40 epochs of training
are passed. Optimization is performed with stochastic gradient descent using a
mini-batch size of 100. After pretraining we perform an architecture search
for 120 epochs with an initial learning rate of 0.2. The learning rate is
decayed according to a cosine schedule [1].

An architecture is trained until convergence after selection by the NAS
procedure to optimize the performance. We use the same hyperparameters as in
the architecture search process.

###  IV-C Efficient Architecture Search

We search for architectures of different sizes by varying the regularization
parameter $\beta\in\\{0,1,2,4,8,16\\}$ to obtain a trade-off between the
number of operations and accuracy. Furthermore, we kept
$\mathrm{ops}_{target}$ fixed at $20\cdot 10^{6}$ during all experiments. By
default, we perform quantization aware training using the STE during NAS to
quantize the model weights to 8 bits.

Our models have the same number of channels across all layers except for the
last 1$\times$1 convolution where the number of feature maps is doubled with
respect to the number of feature maps in the previous layers. We use networks
with 72 channels in stage (i) and (ii) and 144 channels in stage (iii) as our
base networks. To achieve more diversity, we employ a channel multiplier
$\omega$ which scales the number of channels in each layer. We evaluated
$\omega\in\\{0.75,1,1.25\\}$ and rounded the resulting number of channels to
the closest multiple of 8 [30].

Figure 2 shows the test accuracy versus the number of operations for all
models found using NAS. The model size (i.e. memory used to store weights in
bytes) corresponds to the circle size. We observe a variety of models from
different operation regimes.

Figure 2: Test accuracy versus number of operations using multi-objective NAS for varying trade-offs $\beta$. The model size (i.e. memory used to store the weights in bytes) corresponds to the circle size. Numbers above circles represent the model size in bytes for some selected models. TABLE II: Test accuracy, number of operations and memory requirements of three models obtained using NAS. Architecture | Test Acc. (%) | Operations | Memory
---|---|---|---
Hello Edge DS-CNN [3] | 94.4 | 5.4 M | 38.6 kB
Hello Edge DS-CNN [3] | 94.9 | 19.8 M | 189.2 kB
Hello Edge DS-CNN [3] | 95.4 | 56.9 M | 497.6 kB
Ours (Fig. 3c), $\omega=0.75$ | 95.0 | 4.6 M | 89.8 kB
Ours (Fig. 3b), $\omega=1.25$ | 95.4 | 19.6 M | 494.8 kB
Ours (Fig. 3a), $\omega=1$ | 96.0 | 23.4 M | 554.0 kB

We compare three of our models with depthwise-separable convolutional neural
network (DS-CNN) models from [3] in Table II. Figure 3 (a), (b) and (c)
provide the corresponding network topologies. Inverted bottleneck convolutions
are denoted by _MBC[e], [k] $\times$[k]_ with expansion rate $e$ and kernel
size $k$. Expansion rates, kernel sizes and number of layers are determined by
NAS. MFCC features at the input are processed first by a 5$\times$11
convolution which reduces the width by a factor of 2 by means of a strided
convolution. The first inverted bottleneck convolution then reduces the height
and width by a factor of 2 by means of a strided convolution. The last stage
contains a 1$\times$1 convolution as well as global average pooling followed
by a fully connected layer. Individual MBC blocks have skip connections if the
output of the block has the same shape as the input of the block. Skip
connections are drawn symbolically and are denoted by _id_. The output of the
convolutions are three dimensional tensors, with dimensions
C$\times$H$\times$W, where C is the number of channels, H is the height and W
is the width of the corresponding tensor.

DS-CNN models are currently among the best performing models. Still, NAS
allows us to find models that match or even outperform the baseline while
requiring substantially fewer operations.

Figure 3: Large (a), medium (b) and small (c) sized models found by NAS using
10 MFCCs (cf. Section IV-C). Identical consecutive MBC blocks are depicted as
one block for representational purposes. Model (d) is the best model found by
NAS among all models using 20 MFCCs (cf. Section IV-E).

###  IV-D Weight Quantization

Reducing the model size in terms of memory consumption is not only possible by
efficient architectures but also by efficient weight representations. Several
methods are known, including weight pruning and weight quantization [26]. We
apply weight quantization to reduce our model sizes even further.

We perform several tests where we quantize the weight tensors of our second
model from Table II in the range of 8 bit to 1 bit. Note that our models use 8
bit weights by default. The activations are kept at full precision. We
investigate the influence of weight quantization on the test accuracy. We
compare two different methods for weight quantization as discussed in Section
III-C:

  * •

Quantization aware training using the STE.

  * •

Quantization as a post-processing step by rounding parameters of a trained
network to a prespecified parameter bit-width.

Figure 4 includes the results and compares the test accuracy of both methods
for different bit-widths. We observe that the performance of the post-
processing quantization method is only slightly worse than the STE for 8 bits
to 5 bits. However, the performance drops rapidly when using fewer than 4
bits. Quantization using the STE on the other hand preserves the performance
even for binary weight (1-bit) networks. We observe only a slight drop in
performance of around $0.9\%$ when going from 8 bit to 1 bit weights using the
STE.

As we have seen, weight quantization using the STE can be employed
successfully without any substantial loss in accuracy. Also, note that the
training overhead introduced by the STE is only marginal. Training with the
STE does not take much longer than conventional training. Post-processing
quantization performed worse by comparison but has some advantages. It is easy
to implement and it can be performed on arbitrary models without changing the
model.

Figure 4: Test accuracy versus number of bits for two weight quantization
methods evaluated on our second model from Table II for bit-widths in the
range of $\\{1,2,\dots,8\\}$. For every bit-width, the model is trained from
scratch and quantized according to the quantization method. Results for STE
(blue) are obtained by learning quantized weights during training. Results for
post-processing quantization (red) are obtained by rounding the weights after
training.

###  IV-E Varying Number of MFCC Features

For the previous experiments we kept the number of MFCC features at 10 MFCCs.
We have seen that using 10 MFCC features is sufficient for achieving a
reasonable performance. Here, we aim to explore if using more than 10 MFCC
features affects the performance, number of operations and memory requirements
of the networks.

To compare performances we run 4 NAS experiments using 10, 20, 30 and 40 MFCC
respectively. As before we select $\beta\in\\{0,1,2,4,8,16\\}$ and search for
optimal architectures followed by retraining of the weights. The channel
multiplier was kept at $\omega=1$. In order to compare to the baseline, weight
quantization to 8 bits using the STE is performed during training.

Figure 5 shows the results for using 10, 20, 30 and 40 MFCCs for several
trade-offs $\beta$. We also provide a comparison of models found by NAS with
$\beta=8$ using 10, 20, 30 and 40 MFCCs in Table III.

Figure 5: Test accuracy versus number of operations using Multi-objective NAS with varying trade-offs $\beta$ for 10 (blue), 20 (red), 30 (yellow) and 40 (green) MFCCs. The model size corresponds to the circle size. TABLE III: Test accuracy, number of operations and memory requirements (for storing weights) of models obtained by NAS with $\beta=8$ using a different number of MFCCs as features. # MFCCs | Test Accuracy (%) | Operations | Memory
---|---|---|---
10 | 94.9 | 10.9 M | 258.8 kB
20 | 96.3 | 27.1 M | 340.1 kB
30 | 96.2 | 41.4 M | 348.2 kB
40 | 96.6 | 54.7 M | 344.7 kB

We notice a definite improvement of using 20 MFCCs over 10 MFCCs. In
particular, one model found by NAS uses 340.1 kB of memory, 27.1 million
operations and achieves 96.3 % accuracy which outperforms [3] by a large
margin. We include the model structure of this particular network in Figure
3d. Using 30 MFCCs, we obtained the best performing network with a test
accuracy of 96.7% using 1403.3 kB of memory and 155.3 million operations.

##  V Conclusion

Resource efficient DNNs are the key components in modern keyword spotting
(KWS) systems. We show that neural architecture search (NAS) can be used to
obtain efficient convolutional neural networks (CNNs) without compromising
classification accuracy. The CNN models obtained by NAS achieve state-of-the-
art performance while being small enough to fit inside the memory of devices
with limited resources such as a microcontroller. To make our results
comparable, we performed NAS on the Google speech commands dataset. By using
an accuracy/operations trade-off objective for NAS we obtained different
models and compared them in terms of accuracy, memory and number of
operations. We furthermore showed that weight quantization is a viable option
to reduce the memory footprint for storing the CNN weights even further. Even
1 bit weights are sufficient for CNNs without severely degrading the accuracy.
We also showed that changing the number of MFCC features can have a
substantial impact on the performance of the models.

## Acknowledgement

This work was supported by the Austrian Science Fund (FWF) under the project
number I2706-N31.

## References

  * [1] H. Cai, L. Zhu, and S. Han, “ProxylessNAS: Direct neural architecture search on target task and hardware,” in _International Conference on Learning Representations (ICLR)_ , 2019.
  * [2] P. Warden, “Speech commands: A dataset for limited-vocabulary speech recognition,” _CoRR_ , vol. abs/1804.03209, 2018.
  * [3] Y. Zhang, N. Suda, L. Lai, and V. Chandra, “Hello edge: Keyword spotting on microcontrollers,” _CoRR_ , vol. abs/1711.07128, 2017.
  * [4] H. Pham, M. Y. Guan, B. Zoph, Q. V. Le, and J. Dean, “Efficient neural architecture search via parameter sharing,” in _International Conference on Machine Learning (ICML)_ , 2018, pp. 4092–4101.
  * [5] H. Liu, K. Simonyan, and Y. Yang, “DARTS: Differentiable architecture search,” in _International Conference on Learning Representations (ICLR)_ , 2019.
  * [6] H. Liu, K. Simonyan, O. Vinyals, C. Fernando, and K. Kavukcuoglu, “Hierarchical representations for efficient architecture search,” in _International Conference on Learning Representations (ICLR)_ , 2018.
  * [7] M. Tan, B. Chen, R. Pang, V. Vasudevan, M. Sandler, A. Howard, and Q. V. Le, “MnasNet: Platform-aware neural architecture search for mobile,” in _Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2019, pp. 2820–2828.
  * [8] B. Zoph, V. Vasudevan, J. Shlens, and Q. V. Le, “Learning transferable architectures for scalable image recognition,” in _Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2018, pp. 8697–8710.
  * [9] C. Liu, B. Zoph, M. Neumann, J. Shlens, W. Hua, L. Li, L. Fei-Fei, A. L. Yuille, J. Huang, and K. Murphy, “Progressive neural architecture search,” in _European Conference on Computer Vision (ECCV)_ , 2018, pp. 19–35.
  * [10] E. Real, A. Aggarwal, Y. Huang, and Q. V. Le, “Regularized evolution for image classifier architecture search,” in _Association for the Advancement of Artificial Intelligence (AAAI)_ , 2019, pp. 4780–4789.
  * [11] H. Cai, J. Yang, W. Zhang, S. Han, and Y. Yu, “Path-level network transformation for efficient architecture search,” in _International Conference on Machine Learning (ICML)_ , 2018, pp. 677–686.
  * [12] R. Luo, F. Tian, T. Qin, E. Chen, and T. Liu, “Neural architecture optimization,” in _Advances in Neural Information Processing Systems (NeurIPS)_ , 2018, pp. 7827–7838.
  * [13] M. Tan and Q. V. Le, “EfficientNet: Rethinking model scaling for convolutional neural networks,” in _International Conference on Machine Learning (ICML)_ , 2019, pp. 6105–6114.
  * [14] D. Stamoulis, R. Ding, D. Wang, D. Lymberopoulos, B. Priyantha, J. Liu, and D. Marculescu, “Single-path NAS: Designing hardware-efficient convnets in less than 4 hours,” in _European Conference on Machine Learning (ECML)_ , 2019, pp. 481–497.
  * [15] G. Chen, C. Parada, and G. Heigold, “Small-footprint keyword spotting using deep neural networks,” in _International Conference on Acoustics, Speech and Signal Processing (ICASSP)_ , 2014, pp. 4087–4091.
  * [16] T. N. Sainath and C. Parada, “Convolutional neural networks for small-footprint keyword spotting,” in _Annual Conference of the International Speech Communication Association (ISCA)_ , 2015, pp. 1478–1482.
  * [17] S. Ö. Arik, M. Kliegl, R. Child, J. Hestness, A. Gibiansky, C. Fougner, R. Prenger, and A. Coates, “Convolutional recurrent neural networks for small-footprint keyword spotting,” in _Annual Conference of the International Speech Communication Association (ISCA)_ , 2017, pp. 1606–1610.
  * [18] M. Sun, A. Raju, G. Tucker, S. Panchapagesan, G. Fu, A. Mandal, S. Matsoukas, N. Strom, and S. Vitaladevuni, “Max-pooling loss training of long short-term memory networks for small-footprint keyword spotting,” in _Spoken Language Technology Workshop (SLT)_ , 2016, pp. 474–480.
  * [19] N. Suda, V. Chandra, G. Dasika, A. Mohanty, Y. Ma, S. B. K. Vrudhula, J. Seo, and Y. Cao, “Throughput-optimized OpenCL-based FPGA accelerator for large-scale convolutional neural networks,” in _International Symposium on Field-Programmable Gate Arrays (FPGA)_ , 2016, pp. 16–25.
  * [20] J. Qiu, J. Wang, S. Yao, K. Guo, B. Li, E. Zhou, J. Yu, T. Tang, N. Xu, S. Song, Y. Wang, and H. Yang, “Going deeper with embedded FPGA platform for convolutional neural network,” in _International Symposium on Field-Programmable Gate Arrays (FPGA)_ , 2016, pp. 26–35.
  * [21] L. Lai, N. Suda, and V. Chandra, “Deep convolutional neural network inference with floating-point weights and fixed-point activations,” _CoRR_ , vol. abs/1703.03073, 2017.
  * [22] I. Hubara, M. Courbariaux, D. Soudry, R. El-Yaniv, and Y. Bengio, “Binarized neural networks,” in _Advances in Neural Information Processing Systems (NeurIPS)_ , 2016, pp. 4107–4115.
  * [23] G. Hinton, “Neural networks for machine learning,” _Coursera, video lectures_ , 2012.
  * [24] Y. Bengio, N. Léonard, and A. C. Courville, “Estimating or propagating gradients through stochastic neurons for conditional computation,” _CoRR_ , vol. abs/1308.3432, 2013.
  * [25] W. Roth, G. Schindler, H. Fröning, and F. Pernkopf, “Training discrete-valued neural networks with sign activations using weight distributions,” in _European Conference on Machine Learning (ECML)_ , 2019, pp. 382–398.
  * [26] W. Roth, G. Schindler, M. Zöhrer, L. Pfeifenberger, R. Peharz, S. Tschiatschek, H. Fröning, F. Pernkopf, and Z. Ghahramani, “Resource-efficient neural networks for embedded systems,” _CoRR_ , vol. abs/2001.03048, 2020.
  * [27] R. J. Williams, “Simple statistical gradient-following algorithms for connectionist reinforcement learning,” _Mach. Learn._ , vol. 8, pp. 229–256, 1992.
  * [28] S. Ioffe and C. Szegedy, “Batch normalization: Accelerating deep network training by reducing internal covariate shift,” in _International Conference on Machine Learning (ICML)_ , 2015, pp. 448–456.
  * [29] V. Nair and G. E. Hinton, “Rectified linear units improve restricted boltzmann machines,” in _International Conference on Machine Learning (ICML)_ , 2010, pp. 807–814.
  * [30] M. Sandler, A. G. Howard, M. Zhu, A. Zhmoginov, and L. Chen, “MobileNetV2: Inverted residuals and linear bottlenecks,” in _Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2018, pp. 4510–4520.
  * [31] S. Zhou, Z. Ni, X. Zhou, H. Wen, Y. Wu, and Y. Zou, “DoReFa-Net: Training low bitwidth convolutional neural networks with low bitwidth gradients,” _CoRR_ , vol. abs/1606.06160, 2016.
  * [32] D. Miyashita, E. H. Lee, and B. Murmann, “Convolutional neural networks using logarithmic data representation,” _CoRR_ , vol. abs/1603.01025, 2016.