# On visual self-supervision and its effect on model robustness

Michal Kucer, Diane Oyen, Garrett Kenyon
Los Alamos National Laboratory
Los Alamos, NM
{michal, doyen<EMAIL_ADDRESS>
###### Abstract

Recent self-supervision methods have found success in learning feature
representations that could rival ones from full supervision, and have been
shown to be beneficial to the model in several ways: for example improving
models robustness and out-of-distribution detection. In our paper, we conduct
an empirical study to understand more precisely in what way can self-
supervised learning - as a pre-training technique or part of adversarial
training - affects model robustness to $l_{2}$ and $l_{\infty}$ adversarial
perturbations and natural image corruptions. Self-supervision can indeed
improve model robustness, however it turns out the devil is in the details. If
one simply adds self-supervision loss in tandem with adversarial training,
then one sees improvement in accuracy of the model when evaluated with
adversarial perturbations smaller or comparable to the value of
$\epsilon_{train}$ that the robust model is trained with. However, if one
observes the accuracy for $\epsilon_{test}\geq\epsilon_{train}$, the model
accuracy drops. In fact, the larger the weight of the supervision loss, the
larger the drop in performance, i.e. harming the robustness of the model. We
identify primary ways in which self-supervision can be added to adversarial
training, and observe that using a self-supervised loss to optimize both
network parameters and find adversarial examples leads to the strongest
improvement in model robustness, as this can be viewed as a form of ensemble
adversarial training. Although self-supervised pre-training yields benefits in
improving adversarial training as compared to random weight initialization, we
observe no benefit in model robustness or accuracy if self-supervision is
incorporated into adversarial training.

##  1 Introduction

Convolutional Neural Networks are notoriously data hungry and require a large
amount of labeled data to achieve adequate performance; though much work has
been devoted to exploring and devising methods that do not require labeled
data, or require a much smaller number of labels to learn powerful
representations - e.g. unsupervised learning [8, 16] and self-supervised
learning [9, 20, 3]. Self-supervised learning (SSL) has gained popularity as
it proposes techniques to leverage a particular structure of the data to learn
very good representations through optimizing the network weight via auxiliary
tasks: e.g. in-painting [23], rotation prediction [9] and image colorization
[34].

Figure 1: Example showing that increasing $\lambda_{1}$, the weight of self-
supervised loss when combined with supervised loss, affects performance of the
ResNet-18 [13] architecture as $\epsilon_{test}$ is varied. Model trained with
maximum allowable $l_{2}$ perturbations of $\epsilon_{train}=0.10$.  Figure 2:
Figure showing the the two types of self-supervised tasks we studied and a
general diagram of our model, in which we highlight where a self-supervised
loss can be utilized - while generating adversarial examples, or optimizing
network weights.

Though neural networks achieve state of the art results in many tasks and
domains, much recent work has focused on defending against and understanding
adversarial examples, one of the main weaknesses of deep models [25, 10, 31].
Adversarial examples are inputs which have been imperceptibly changed and
cause a model to provide erroneous output. However, recent work [4, 15]
suggests that leveraging self-supervised learning can lead to improvements in
robustness of models. The goal of this paper is to understand how does
incorporating self-supervision into model training affect model robustness to
adversarial perturbations [19] and common image corruptions [14], as there is
more to using self-supervision to improve robustness than meets the eye.
Figure 1 shows a plot of the performance of an adversarially trained ResNet-18
[13] model on the CIFAR-10 dataset ( with $l_{2}$ constraint and
$\epsilon=0.1$) when a self-supervision (SS) loss is also used in network
parameter optimization. We can see from this figure, that as we increase the
maximum allowable perturbation $\epsilon$ of the adversarial examples, the
model robustness worsens as the importance of SS loss, $\lambda_{1}$,
increases. Training a model that optimizes both SS loss and supervised loss
with larger $\epsilon_{train}$ further reveals that

  * •

for several value of $\epsilon_{test}\leq\epsilon_{train}$, the accuracy of a
model trained with SS loss in tandem with supervision is higher, and thus one
can say the model is more robust at that $\epsilon_{test}$; and,

  * •

if $\epsilon_{test}\geq\epsilon_{train}$, the performance of the model trained
with self-supervision drops, and the effect is larger with stronger weight
$\lambda_{1}$ of the self-supervised loss.

This represents only one of the cases in which self-supervision can be added
to adversarial training. Refer to Figure 2 for a diagram that shows ways that
self-supervised learning can be incorporated into adversarial training and the
choices to consider: (a) self-supervision task, (b) generation of adversarial
examples, and (c) network parameter optimization. We find that leveraging the
self-supervised task loss in generating adversarial examples (loss
$\mathcal{L}$ at the bottom of Figure 2) is crucial to boosting model
robustness, however it penalizes its non-robust accuracy111This is expected,
as there is much work exploring the trade-off between robustness and accuracy
[28]..

Contributions In this paper, we conduct a comprehensive study to understand
various ways one can combine self-supervision with adversarial training and
observe the effects on $l_{2}$ and $l_{\infty}$ adversarial robustness. Our
study is motivated by the following three questions:

  * •

Is there a best way to combine self-supervised learning with adversarial
training?

  * •

Is there anything special about predicting image rotations? Or would other SS
tasks work as well.

  * •

Does adversarial self-supervised pre-training further boost model robustness
if one incorporates self-supervision into adversarial training?

Our contributions are the answers to the above questions:

  * •

Depends on the meaning of best. If one is interested in model accuracy,
incorporating self-supervision loss into optimizing network parameters
improves the non-robust model accuracy and robustness for small values
$\epsilon$, however it can hurt model robustness for larger perturbations.
Optimizing the model with self-supervision and adversarial examples generated
with both supervised and self-supervised losses is optimal for boosting model
robustness, is this can be viewed as a form ensemble adversarial training.

  * •

Our results indicate that there is nothing special about predicting image
rotations and its ability to boost model robustness. We see a similar boost in
adversarial robustness when swapping image rotations with the task of solving
a jigsaw puzzle [2].

  * •

Our results indicate the answer is no. Self-supervised adversarial pre-
training does boost accuracy if starting adversarial training [19] from pre-
trained weights. However we see no further benefit from SS adversarial pre-
training if we incorporate SS into adversarial training.

##  2 Related work

###  2.1 Self-supervised learning

Self-supervised learning has gained popularity in recent years in many domains
as a method of learning feature representations without the need of labeled
data, e.g. images [9], or video [33]. Many of the visual self-supervised
learning methods utilize a particular structure of the data to create a task
and generate pseudo-labels that can then be optimized using supervised
learning, e.g image colorization [34], or rotations prediction [9]. Noroozi et
al. [20] propose to learn features by solving jigsaw puzzles on natural
images. Zhang et al. [34] propose to learn image features by learning to
predict plausible color version of a photograph from its greyscale version.
Gidaris et al [9] propose to learn visual features by predicting the nature of
geometrical transformation applied to the image, in this case image rotations.
Trinh et al. [27] learn visual features by learning to predict which image
patches correctly fill in masked out image among a set of “distractor”
patches. Further, some of the recent methods such as SwAV [3] or MoCo-V2 [5]
utilize contrastive learning and feature clustering to learning strong feature
representations.

###  2.2 Adversarial robustness

Though neural networks have been in the forefront of state-of-the-art research
in many branches of computer vision, they exhibit some weaknesses, among them
vulnerability to adversarial examples [25, 11], which completely change the
output of the model. Recent years have seen many attempts to propose defenses
against such examples. Dhillon et al. [6] propose Stochastic Activation
Pruning, a strategy which randomly prunes a subset of activations. Guo et al.
[12] propose to use input transformation (e.g. JPEG compression) to defend
against adversarial attacks. Xie et al. [32] attempt to defend against
adversarial attacks by adding an additional layer that randomly rescales the
input. However, as Athalye et al. [1] show, many of these defenses can be
easily circumvented. One of the most effective approaches to defending against
adversarial attacks is shown to be adversarial training [19, 1].

##  3 Improving robustness with self-supervision

In this section, we describe the form of our empirical study into the role of
self-supervision and its effects on model robustness. Previous studies, most
notably Chen et al. [4] and Hendrycks et al. [15], explore using self-
supervision to improve model robustness via pre-training and as an auxiliary
loss, both focusing on the particular setting where the adversarial examples
are generated with projected gradient descent (PGD) attacks [19] with the
$l_{\infty}$ norm and attack strength equal to $\epsilon=\frac{8}{255}$. A
recent empirical study by Salman et al. [24] shows that model robustness
(mainly models trained with small values of $l_{2}$ perturbation) can improve
the performance in downstream learning tasks. Motivated by this research, our
empirical study focuses on understanding the effect of self-supervision on
model robustness in case of both $l_{2}$ and $l_{\infty}$ adversarial
perturbations of various strength.

###  3.1 Self-supervised learning

As LeCun et al. [18] point out, “self-supervised learning obtains supervisory
signals from the data itself, often leveraging the underlying structure in the
data.” Imagine we are given an input image $x$ and we apply to it a
transformation $T(\cdot)$ that gives us the a transformed version of the image
$x_{SS}$ and label $y_{SS}$:

$(x_{SS},y_{SS})=T(x).$ (1)

In our experiments, we study the following self-supervised task: rotation
prediction [9], and solving a jigsaw puzzle [20, 2] (see Figure 2). Both of
these tasks are implemented as a supervised task with multi-class cross-
entropy loss as a criterion to be optimized. This allows us to easily
incorporate rotation prediction as a auxiliary task to be optimized in
addition to classification. In case of rotations predictions, the
transformation $T(\cdot)$ consists of rotating the image by a multiple of
$90\deg$, and returning a rotated image $x_{SS}$ and a label $y_{SS}$ assigned
to the particular rotation. In case of the jigsaw puzzle, the task of consists
of dividing the image into $n\times n$ grid, and randomly picking a set of $J$
permutations (each assigned its own label). The transformation $T(\cdot)$ then
consists of scrambling the image parts according to the randomly chosen
permutation, returning the scrambled image and label associated with the
permutation. The task of the network is then to either predict the rotation of
the image, or the permutation that would unscramble the image.

###  3.2 Defending against adversarial perturbations

To set the setting, we will borrow the notation from Madry et al. [19, 28].
Typically, machine learning models are optimized to maximize a certain metric
and thus have a low expected loss,

$\underset{(x,y)\sim\mathcal{D}}{\operatorname{\mathbb{E}}}\left[\mathcal{L}(x,y;\theta)\right].$
(2)

As mentioned earlier, neural networks were found to be vulnerable to
adversarial examples [25, 10], which are images that have been altered to fool
a model. Therefore, there is a lot of interest in developing models that are
robust, i.e. resistant to adversarial examples. Therefore, the goal is now to
train models that minimize the adversarial loss,

$\underset{(x,y)\sim\mathcal{D}}{\operatorname{\mathbb{E}}}\left[\max_{\delta\in\Delta}\mathcal{L}(x+\delta,y;\theta)\right],$
(3)

where $\Delta$ is a set of $l_{p}$-bounded perturbations, or alternatively a
set $S$ of adversarial examples $x^{\prime}\in\mathcal{X}$ where
$S=\\{x^{\prime}\in\mathcal{X}:\lVert x^{\prime}-x\rVert_{p}<\epsilon\\}$.

One of the most successful methods for defending is adversarial training [10,
19, 31]. A variant of adversarial training proposed by Madry et al [19] solves
the above problem by finding the worst case $l_{p}$ bounded adversarial
examples using projected gradient descent (PGD) and finds set of parameters
$\theta$ that minimize the empirical training loss using these examples [1],

$\theta^{*}=\underset{\theta}{\arg\min}\underset{(x,y)\in
X}{\operatorname{\mathbb{E}}}\left[\underset{\delta\in[-\epsilon,\epsilon]}{\max}\mathcal{L}(x+\delta,y;F_{\theta})\right]$
(4)

Algorithm 1 Finding adversaries with self-supervision

1:input: Robustness parameter $\epsilon$, attack learning rate $\alpha$,
number of attack steps $K$, image batches $X$ and $X_{SS}$, labels $y$ and
$y_{SS}$, $\lambda_{2}$

2:output: Adversarial images $X$ and optionally $X_{SS}$

3:Randomly perturb images $X$ (and optionally $X_{SS}$)

4:$X^{0}=X+U(-\epsilon,\epsilon),X^{0}_{SS}=X_{SS}+U(-\epsilon,\epsilon)$

5:for $k=0,\dots,K-1$ do

6: $\mathcal{L}=\mathcal{L}_{sup}(F_{\theta}(X^{k}),y)$

7: if should use self-supervised loss then

8:
$\mathcal{L}\mathrel{+}=\lambda_{2}*\mathcal{L}_{SS}(F_{\theta}^{SS}(X_{SS}^{k}),y_{SS})$

9: end if

10:end for

11:$X^{k+1}=\Pi_{S}\left(X^{k}+\alpha\cdot\text{sign}\left(\nabla_{x}\mathcal{L}\right)\right)$

In adversarial training by Madry et al. [19], an image $x$ is first perturbed
in its neighborhood $U(x,\epsilon)$, i.e.

$x_{0}=x+U(-\epsilon,\epsilon).$ (5)

It then follows the generation process of the Basic Iterative Method [17, 21],

$x^{k+1}=\Pi_{S}\left(x_{k}+\alpha\cdot\text{sign}\left(\nabla_{x}\mathcal{L}(x+\delta,y;F_{\theta})\right)\right)$
(6)

where $K$ is the number of attacks steps, or iterations of projected gradient
descent performed to find the worst case $l_{p}$ bounded adversarial example
$x^{adv}$. $\Pi_{p}$ is an operator that will project the iterates onto an
$l_{p}$ ball, in our case $p=2$ and $\infty$.

Algorithm 1 describes the general procedure for generating PGD adversaries. As
we see in Figure 2 and Algorithm 1, there are several choices to be made
regarding how to incorporate self-supervision into adversarial training (AT).
For now, assume our self-supervised task of choice is rotation prediction [9],
though we show that there is nothing unique about rotation prediction and one
can substitute any self-supervised task of choice. One can use image rotation
in the image pre-processing pipeline (without incorporating self-supervised
loss), however this hurts the baseline AT performance, and therefore is not
further considered.

The first way to incorporate self-supervision into AT is to apply the
transformation $T$ to the batch of images $X$ to obtain the rotated versions
of the batch and corresponding labels $X_{SS}$ and $y_{SS}$ respectively. One
then computes the adversarial version of $X_{SS}^{adv}$ and compute the
following loss

$\mathcal{L}_{sup}(F_{\theta}(X_{SS}^{adv}),y)+\lambda_{1}*\mathcal{L}_{SS}(F_{\theta}^{SS}(X_{SS}^{adv}),y_{SS}),$
(7)

where $\lambda_{1}$ is the weight of the self-supervised loss222Note that the
loss $\mathcal{L}$ also includes the weight regularization term. however this
is not shown as this term is present for all of the cases., $F_{\theta}$
represents a neural network model with two prediction heads, one for the
supervised task ($F_{\theta}(\cdot)$) and the other for self-supervised task
($F_{\theta}^{SS}(\cdot)$). This too is found to be inferior to baseline
adversarial training, dropping the clean and robust ($\epsilon_{test}=8/255$)
accuracy from 85.46% and 44.69% to 74.9% and 36.60% respectively.

Figure 3: A comparison of models for which $\lambda_{1}$ is varied. The top
figure shows the full plot for values of $\epsilon_{test}$ The bottom row
shows figures highlighted different parts of the domain. Leftmost plot rather
than showing the performance of the various models, shows the comparison of
performance for the given model, e.g. the line in the bottom left plot that
shares the yellow colour with the plot in the top figure, shows the difference
in performance $\text{Acc}(\lambda_{1}=0.25)-\text{Acc}(\lambda_{1}=0)$.

The following are options for adding self-supervision that involve making a
copy of the batch to which the self-supervised transformation $T$ will be
applied, resulting in a batch $X$ and a batch $X_{SS}=T(X)$333Transformation
$T$ also gives us the self-supervised labels $y_{SS}$. These scenarios fit the
description of Algorithm 1 and Figure 2. The simplest way to add self-
supervision into AT (denoted as SS $\mathcal{T}_{1}$) is by generating
adversarial examples $X^{adv}$, while leaving $X_{SS}$ unchanged, and
computing the combined loss

$\mathcal{L}_{sup}(F_{\theta}(X^{adv}),y)+\lambda_{1}*\mathcal{L}_{SS}(F_{\theta}^{SS}(X_{SS}),y_{SS})$
(8)

Lastly, one can attack both the original batch images $X$ and transformed
images $X_{SS}$, resulting in the following loss

$\mathcal{L}_{sup}(F_{\theta}(X^{adv}),y)+\lambda_{1}*\mathcal{L}_{SS}(F_{\theta}^{SS}(X_{SS}^{adv}),y_{SS}).$
(9)

This scenario offers another set of decisions corresponding to lines 4-6 of
Algorithm 1: when generating adversarial examples for $X$ and $X_{SS}$, should
one use the supervised loss (SS $\mathcal{T}_{2}$), the self-supervised loss,
or both (and what ratio $\lambda_{2}$) (SS $\mathcal{T}_{3}$) to find the
worst case adversarial examples? As can be seen, incorporating self-
supervision into AT is not straightforward. Using just SS loss for generating
adversarial examples is much worse as compared to the baseline, due to the
fact that they are not optimized to defend against perturbations that they are
tested against.

###  3.3 Self-supervised pre-training

We first study how incorporating SSL into adversarial training impact the
model robustness. However, from Chen et al. [4] we know that adversarial self-
supervised pre-training can help robustness. Therefore, we want to understand
whether self-supervised pre-training will further aid in model robustness, or
whether majority of the benefits are realized by combining SSL and AT. As Chen
et al. point out [4], partial fine-tuning, where a portion of the early layers
is frozen, is inferior to tuning the full model (as expected, as it is similar
to fixed-feature and full-network transfer learning setting of [24]).
Therefore, once we have understood the best way to incorporate SSL into AT, we
will consider the following settings for initializing our weights: random
initialization, adversarial self-supervised pre-training $\mathcal{P}_{1}$
with $l_{2}$ perturbations, and adversarial self-supervised pre-training
$\mathcal{P}_{2}$ with $l_{\infty}$. This is equivalent to AT, except $X_{SS}$
and $y_{SS}$ are used for AT algorithm of [19].

Method / $\epsilon_{test}$ | 0 | 0.01 | 0.03 | 0.05 | 0.07 | 0.1 | 0.25 | 0.5 | 0.75 | 1.0 | 2.0 | 3.0
---|---|---|---|---|---|---|---|---|---|---|---|---
Baseline $\mathcal{T}_{0}$ | 88.98 | 88.63 | 87.87 | 87.08 | 86.48 | 85.49 | 78.52 | 64.46 | 48.15 | 34.05 | 8.13 | 2.15
SS $\mathcal{T}_{1}$ | 90.57 | 90.20 | 89.48 | 88.69 | 87.76 | 86.68 | 78.78 | 62.17 | 44.65 | 28.80 | 4.09 | 0.48
SS $\mathcal{T}_{2}$ | 90.20 | 89.94 | 89.30 | 88.54 | 87.94 | 87.02 | 80.31 | 66.18 | 50.28 | 34.91 | 6.28 | 1.77
SS $\mathcal{T}_{3}$ | 89.07 | 88.75 | 88.14 | 87.48 | 86.85 | 85.73 | 79.77 | 66.15 | 50.87 | 36.55 | 7.50 | 2.09

Table 1:  Top-1 accuracy on the CIFAR-10 test set with ResNet-18 models
trained with $l_{2}$ norm and $\epsilon_{train}=0.5$ evaluated at different
values of $\epsilon_{test}$ used to generate the robust test set as we vary
the training method and SSL involvement.

Method / $\epsilon_{test}$ | $0/255$ | $3/255$ | $4/255$ | $5/255$ | $6/255$ | $7/255$ | $8/255$ | $9/255$ | $10/255$
---|---|---|---|---|---|---|---|---|---
Baseline $\mathcal{T}_{0}$ | 85.46 | 72.09 | 66.98 | 61.29 | 55.83 | 50.19 | 44.69 | 39.38 | 34.60
SS $\mathcal{T}_{1}$ | 86.59 | 73.69 | 68.71 | 62.86 | 56.88 | 50.52 | 44.51 | 38.90 | 33.89
SS $\mathcal{T}_{2}$ | 86.24 | 74.06 | 68.96 | 63.29 | 57.63 | 51.50 | 45.77 | 40.51 | 35.54
SS $\mathcal{T}_{3}$ | 84.61 | 73.33 | 68.61 | 64.01 | 59.09 | 53.73 | 48.11 | 43.42 | 38.76

Table 2:  Top-1 accuracy on the CIFAR-10 test set with ResNet-18 models
trained with $l_{\infty}$ norm and $\epsilon_{train}=8/255$ evaluated at
different values of $\epsilon_{test}$ used to generate the robust test set as
we vary the training method and SSL involvement.

##  4 Experiments and results

###  4.1 Datasets

Our experiments consider the following datasets: CIFAR-10, and CIFAR-10C [14].
All of the ablation experiments are done using CIFAR-10. The CIFAR-10C dataset
[14] is used to test our model against common corruptions that can be
encountered.

###  4.2 Implementation details

All of our code is implemented in Python using the PyTorch [22] deep learning
framework. In pursuit of simplicity and reproducibility, our code extends the
robustness library [7]444Source code can be made available upon internal
review.. Our code is developed on an internal cluster, where each server node
is equipped with 4 NVIDIA Tesla P100 cards (each with 16 GB of VRAM), paired
with a dual 18-core Intel Xeon CPUs and 256GB of memory. Our ablation
experiments utilize the ResNet-18, and ResNet-34 architectures555Note that the
robustness package uses slightly different architectures for the CIFAR-10 and
ImageNet dataset. CIFAR-10 uses slightly smaller convolutional kernels. For
more details, please see: https://github.com/MadryLab/robustness.

When applying self-supervised transformation $T(\cdot)$ to $X$, each image is
randomly rotated by $\phi$ degrees, where
$\phi\in\\{0^{\circ},90^{\circ},180^{\circ},270^{\circ}\\}$. This
implementation differs from [15], as they simultaneously generate and predict
all four possible rotations for each image in the batch (if the size of $X$ is
$b$ samples, $X_{SS}$ is of size $4\cdot b$). Furthermore, when leveraging SS
loss to guide adversarial training (step 6 of Algorithm 1), we use the
following form of the loss:

$\mathcal{L}_{SS}(X_{SS},y_{SS})=\frac{1}{N}\sum_{i\in\\{1,\cdots,n\\}}\mathcal{L}_{CE}(F^{SS}_{\theta}(x^{i}_{SS}),y^{i}_{SS}),$
(10)

which differs from [15] in that they omit the averaging term $1/N$. In our
experiments, averaging reduction for the loss gives consistently better
results.

Training and evaluation details All of the ablation experiments investigating
addition of SS into AT are trained for 100 epochs, with a starting learning
rate of 0.1 (reduced by 10 every 40 epochs) and optimized using Stochastic
Gradient Descent (SGD) with the momentum of 0.9. The CIFAR-10 training set is
further split into a training and validation set (15% or 7500 images are used
for validation and the rest are used for training). For adversarial training
and evaluation, we use 10 and 20-step $l_{p}$ PGD attacks [19] respectively.
For $l_{2}$ adversaries, the attack learning rate is set to
$\alpha=\frac{\epsilon\cdot 2}{\\#\text{ of steps}}$ (see supplement of [24]).
For $l_{\infty}$ adversaries, the $\epsilon_{train}=8/255$ and attack learning
rate is set to $\alpha=2/255$ [15, 4]. Similar to [4], in our results we refer
to the non-robust, i.e. $\epsilon=0$, accuracy as the Standard Testing
Accuracy (TA), and robust accuracy at $\epsilon_{test}=\epsilon$ as the Robust
Testing Accuracy ($RA_{\epsilon}$). For particular set of hyper-parameters, we
pick a model with the highest validation TA and test across a range of
$\epsilon_{test}$ values. The adversarial perturbations for testing images are
only generating using the supervision loss in the PGD attack.

Method / $\epsilon_{test}$ | $0/255$ | $3/255$ | $4/255$ | $5/255$ | $6/255$ | $7/255$ | $8/255$ | $9/255$ | $10/255$
---|---|---|---|---|---|---|---|---|---
Baseline | 85.46 | 72.09 | 66.98 | 61.29 | 55.83 | 50.19 | 44.69 | 39.38 | 34.60
Rotations | 84.61 | 73.33 | 68.61 | 64.01 | 59.09 | 53.73 | 48.11 | 43.42 | 38.76
Jigsaw | 83.90 | 72.39 | 67.91 | 63.18 | 57.99 | 52.89 | 47.57 | 42.31 | 37.66

Table 3:  Top-1 accuracy on the CIFAR-10 test set with ResNet-18 models
trained with $l_{\infty}$ norm and $\epsilon_{train}=8/255$ evaluated at
different values of $\epsilon_{test}$ used to generate the robust test set as
we vary the SSL tasks that is used in tandem with AT.

###  4.3 Effect of self-supervision on model robustness

In this section, we compare the ways SS can be incorporated into AT (SS
$\mathcal{T}_{1}$, SS $\mathcal{T}_{2}$, and SS $\mathcal{T}_{3}$) and we
compare it against the baseline AT procedure of Madry et al. [19] ( Baseline
$\mathcal{T}_{0}$). Tables 1 and 2 summarize the general trends we see for the
$l_{2}$ and $l_{\infty}$-robust performance of the various methods for the
ResNet18 architecture. We see similar trends for the ResNet-34 architecture,
whose tabulated results can be found in the appendix.

Our first set of experiments explores the effects on AT of the training
scenario SS $\mathcal{T}_{1}$, which optimizes

$\mathcal{L}_{sup}(F_{\theta}(X^{adv}),y)+\lambda_{1}*\mathcal{L}_{SS}(F_{\theta}^{SS}(X_{SS}),y_{SS}).$
(11)

$\mathcal{L}_{sup}$ is the supervised portion of the loss operating on PGD-
attacked batch $X^{adv}$, and $\mathcal{L}_{SS}$ is the self-supervised loss
(SSL) operating on clean batch $X_{SS}$. Figure 3 illustrates the general
trend we see for SS $\mathcal{T}_{1}$. The bottom row of Figure 3 splits the
$x$-axis into three ranges, to better illustrate the trend. The tabulated
results for various values of $\epsilon_{test}$ and $\lambda_{1}$ can be found
in Supplemental Materials. In general, we see that TA is higher for models
with $\lambda_{1}>0$. In fact, the TA for models trained under SS
$\mathcal{T}_{1}$ scenario is better than the non-robust model with maximum
allowable $l_{2}$ perturbation $\epsilon_{train}$ as high as 0.1. The use of
self-supervision ($\alpha_{1}>0$) consistently improves the TA and RA for
several values of $\epsilon_{test}<\epsilon_{train}$, as compared to baseline
$\mathcal{T}_{0}$ (see bottom left plot of Figure 3). Furthermore, larger
values of $\alpha_{1}$ result in larger increase in TA and RA for several
values of $\epsilon_{test}<\epsilon_{train}$. However, for
$\epsilon_{test}>\epsilon_{train}$ we can see the opposite behavior - RA drops
further as compared to the baseline the larger the weight $\lambda_{1}$. From
Figure 3, and Tables 1 and 2, we can see that SS $\mathcal{T}_{1}$ is very
effective in regularizing the model training and provides the largest increase
in TA as compared to other methods (though sacrificing RA).

Figure 4: Figure depicting the Top-1 accuracy comparing the various methods to
incorporate self-supervision into adversarial training for the various
corruption types present in the corrupted CIFAR-10 dataset [14]. Top figure
shows the non-robust Top-1 accuracy and bottom figure shows the robust Top-1
accuracy. The baseline ResNet-18 model is trained with a maximum allowable
$l_{2}$ corruptions of $\epsilon=1.0$.

Method / $\epsilon_{test}$ | $0/255$ | $3/255$ | $4/255$ | $5/255$ | $6/255$ | $7/255$ | $8/255$ | $9/255$ | $10/255$
---|---|---|---|---|---|---|---|---|---
Baseline $\mathcal{P}_{0}|\mathcal{T}_{0}$ | 85.29 | 71.90 | 66.63 | 60.96 | 55.42 | 49.52 | 44.01 | 39.28 | 34.41
$\mathcal{P}_{1}|\mathcal{T}_{0}$ | 84.67 | 72.67 | 67.91 | 62.61 | 56.91 | 51.46 | 45.91 | 40.27 | 35.88
$\mathcal{P}_{2}|\mathcal{T}_{0}$ | 85.37 | 72.01 | 66.69 | 61.05 | 55.52 | 49.61 | 43.70 | 38.17 | 33.66
$\mathcal{P}_{1}|\mathcal{T}_{3}$ | 83.78 | 72.75 | 68.20 | 63.32 | 58.25 | 52.85 | 47.37 | 42.24 | 37.93
$\mathcal{P}_{2}|\mathcal{T}_{3}$ | 84.08 | 72.65 | 68.08 | 62.94 | 58.01 | 52.77 | 47.16 | 41.67 | 36.58
$\mathcal{P}_{0}|\mathcal{T}_{3}$ | 84.61 | 73.33 | 68.61 | 64.01 | 59.09 | 53.73 | 48.11 | 43.42 | 38.76

Table 4:  Top-1 accuracy on the CIFAR-10 test set with ResNet-18 models
trained with different combinations of pre-training and AT.

The row SS $\mathcal{T}_{2}$ and The row SS $\mathcal{T}_{3}$ from tables 1
and 2 show the cases in which both original ($X$) and transformed images
($X_{SS}$) were attacked using the PGD (Alg. 1) and use the following loss for
network parameter optimization:

$\mathcal{L}_{sup}(F_{\theta}(X^{adv}),y)+\lambda_{1}*\mathcal{L}_{SS}(F_{\theta}^{SS}(X_{SS}^{adv}),y_{SS}).$
(12)

The main difference between rows SS $\mathcal{T}_{2}$ and SS $\mathcal{T}_{3}$
is the manner in which the adversarial images are generated. Row SS
$\mathcal{T}_{2}$ shows result for a ResNet-18 trained model in which only
line 6 of Algorithm 1 is used to generate loss for the PGD attack, whereas row
SS $\mathcal{T}_{3}$ shows the results for the case in which line 8 of
Algorithm 1 is used to add SSL term. For the case of $\mathcal{T}_{2}$, in
both $l_{2}$ (Table 1) and $l_{\infty}$ (Table 2) we can see that the TA and
RA are better than $\mathcal{T}_{0}$ for all values of $\epsilon_{test}$,
though TA is worse than SS $\mathcal{T}_{1}$. Lastly, for SS $\mathcal{T}_{3}$
we can see that TA either does not change or gets worse compared to all the
other methods, showing that if one wants to optimize the model for clean
accuracy, one should not use SSL in generating adversarial examples. However,
where $\mathcal{T}_{3}$ shines is its increase in RA as compared to baseline
or the other methods, especially for larger values of $\epsilon_{test}$. What
causes this behavior (drop in RA and increase in TA)? By attacking both the
supervision and self-supervision loss, we are optimizing the model to be
robust to multiple objectives, which can be viewed as a form of ensemble
adversarial training [26, 29], in which one performs an ensemble attack over
multiple tasks [30].

Discussion From our empirical study, we can see that both (a) combining the
supervision with self-supervised loss, and (b) attacking both the supervision
and self-supervision losses play a vital role in affecting the TA and
robustness to $l_{2}$ and $l_{\infty}$-PGD attacks, which is contrary to
findings of Hendrycks et al. [4]. Just adding SS loss improves the TA and RA
for $\epsilon_{test}\leq\epsilon_{train}$, however hurts in for
$\epsilon_{test}>\epsilon_{train}$. Using the adversarial version of both $X$
and $X_{SS}$ (using only the supervised loss) slightly improves the accuracy
for all $\epsilon_{test}$ as compared to $\mathcal{T}_{1}$, however slightly
lowers TA and RA for small values of $\epsilon$. SS $\mathcal{T}_{3}$ can be
viewed as a form of a ensemble adversarial attack over multiple tasks,
resulting in an increase in model robustness to larger perturbations however
sacrificing TA [28].

Is there something special about rotation prediction? Our experiments suggest
the answer to be no. Refer to Table 3, where we compare swapping the task of
predicting image rotations to the jigsaw task [2], where one scrambles the
image parts into one of several pre-selected permutations and then predicts
the nature of the permutation. We can see from Table 3 that either the
rotations or jigsaw task succeed in improving the robustness of the model in a
similar way, though we can see that jigsaw is slightly inferior to rotation
prediction. This is similar to the result of [4], which observes that jigsaw
pre-training provides worse pre-training performance as compared to rotations.

How beneficial is pre-training? Another question is: how beneficial is self-
supervised adversarial pre-training to SS $\mathcal{T}_{3}$. Please see Table
4 for a comparison of the training methods with the different pre-training
scenarios. Similar to [4], we see a boost in model robustness when adversarial
self-supervised pre-training is followed by AT. However, we do not see any
significant benefit from adversarial SS pre-training if AT is combined with
self-supervision (SS $\mathcal{T}_{3}$).

Clarification of contributions We provide a comprehensive study on the effects
of SS and training choices on model robustness, with explanations of observed
trends. Although this study is limited to one dataset and two architectures,
this work is a solid platform for exploring and understanding the ways that
incorporating SS into AT affects model accuracy and robustness; with findings
that reach significantly beyond results from other published work.

###  4.4 Robustness to natural corruptions

In this section, we report the performance of the various SS training on the
CIFAR-10C dataset, which contains various common corruptions, e.g. Gaussian
noise, blur. Figure 4 shows the plots of the non-robust (Top) and robust
(Bottom) Top-1 accuracies for $l_{2}$-robust ResNet18 model trained with
$\epsilon=1.0$ (the plot for $l_{\infty}$-robust model can be found in the
supplement). From all of these examples we can see the following trend (which
is similar to the $l_{\infty}$ trained models): adding the self-supervised
loss (SS $\mathcal{T}_{1}$ and $\mathcal{T}_{2}$) helps the model improve its
TA accuracy for the various common image corruptions - the clean accuracy goes
from 78.36% mean accuracy over all corruptions to 80.23% and 79.15% for
$\mathcal{T}_{1}$ and $\mathcal{T}_{2}$ trained models respectively. The clean
accuracy drops from 78.36% mean accuracy to 76.52% when SS task loss is added
to PGD. However, one can see the benefit of $\mathcal{T}_{3}$ when adversarial
perturbations are added to natural corruptions as RA goes from 35.83% to
38.33% mean RA for $l_{2}$-robust models and from 32.20% to 36.22% mean RA for
$l_{\infty}$-robust models. In terms of RA, $\mathcal{T}_{1}$ and
$\mathcal{T}_{2}$ are worse than $\mathcal{T}_{0}$ in case of $l_{2}$-robust
models) and $\mathcal{T}_{1}$ is worse than $\mathcal{T}_{0}$ for
$l_{\infty}$. Interestingly, even though the mean TA for both $l_{2}$ and
$l_{\infty}$ robust models is similar, $l_{2}$-robust models (trained using
$\mathcal{T}_{0}$, $\mathcal{T}_{2}$, $\mathcal{T}_{3})$ outperformed
$l_{\infty}$ robust models.

##  5 Conclusion

Our paper aims to understand how incorporating self-supervision into
adversarial training improves model robustness to adversarial perturbations
and natural corruptions. As we saw, the task of incorporating SS into AT is
not straightforward and requires care. Generating a separate image batch
transformed by the self-supervised task and incorporating self-supervised task
loss into the training objective provides a significant boost in standard
testing accuracy, though can hurt the robust testing accuracy for larger
values of $\epsilon_{test}$. If the main goal is to improve model robustness,
one should should take the approach of ensemble adversarial training (EAT) and
generate images that are trying to fool both the self-supervised and
supervised training objectives. Though EAT results in a drop in clean
accuracy, we see gains in robustness against adversarial perturbations and
natural image corruptions. Additionally, we show that these benefits can be
had with different SS tasks (rotation prediction vs. jigsaw).

## References

  * [1] Anish Athalye, Nicholas Carlini, and David A. Wagner.  Obfuscated gradients give a false sense of security: Circumventing defenses to adversarial examples.  In ICML, pages 274–283, 2018.
  * [2] Fabio Maria Carlucci, Antonio D’Innocente, Silvia Bucci, Barbara Caputo, and Tatiana Tommasi.  Domain generalization by solving jigsaw puzzles.  In CVPR, 2019.
  * [3] Mathilde Caron, Ishan Misra, Julien Mairal, Priya Goyal, Piotr Bojanowski, and Armand Joulin.  Unsupervised learning of visual features by contrasting cluster assignments.  2020\.
  * [4] T. Chen, S. Liu, S. Chang, Y. Cheng, L. Amini, and Z. Wang.  Adversarial robustness: From self-supervised pre-training to fine-tuning.  In IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pages 696–705, 2020.
  * [5] Xinlei Chen, Haoqi Fan, Ross B. Girshick, and Kaiming He.  Improved baselines with momentum contrastive learning.  CoRR, abs/2003.04297, 2020.
  * [6] Guneet S. Dhillon, Kamyar Azizzadenesheli, Zachary C. Lipton, Jeremy Bernstein, Jean Kossaifi, Aran Khanna, and Anima Anandkumar.  Stochastic activation pruning for robust adversarial defense.  CoRR, abs/1803.01442, 2018.
  * [7] Logan Engstrom, Andrew Ilyas, Hadi Salman, Shibani Santurkar, and Dimitris Tsipras.  Robustness (python library), 2019.
  * [8] Dumitru Erhan, Yoshua Bengio, Aaron Courville, Pierre-Antoine Manzagol, Pascal Vincent, and Samy Bengio.  Why does unsupervised pre-training help deep learning?  Journal of Machine Learning Research, 11(19):625–660, 2010.
  * [9] Spyros Gidaris, Praveer Singh, and Nikos Komodakis.  Unsupervised representation learning by predicting image rotations.  In International Conference on Learning Representations, 2018.
  * [10] Ian Goodfellow, Jonathon Shlens, and Christian Szegedy.  Explaining and harnessing adversarial examples.  In International Conference on Learning Representations, 2015.
  * [11] Ian J. Goodfellow, Jonathon Shlens, and Christian Szegedy.  Explaining and harnessing adversarial examples, 2015.
  * [12] Chuan Guo, Mayank Rana, Moustapha Cisse, and Laurens van der Maaten.  Countering adversarial images using input transformations.  In International Conference on Learning Representations, 2018.
  * [13] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Deep residual learning for image recognition.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770–778, 2016.
  * [14] Dan Hendrycks and Thomas Dietterich.  Benchmarking neural network robustness to common corruptions and perturbations.  In International Conference on Learning Representations, 2019.
  * [15] Dan Hendrycks, Mantas Mazeika, Saurav Kadavath, and Dawn Song.  Using self-supervised learning can improve model robustness and uncertainty.  In Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
  * [16] Diederik P Kingma and Max Welling.  Auto-encoding variational bayes.  arXiv preprint arXiv:1312.6114, 2013.
  * [17] Alexey Kurakin, Ian Goodfellow, Samy Bengio, et al.  Adversarial examples in the physical world, 2016.
  * [18] Yan LeCun and Ishan Mishra.  Self-supervised learning: The dark matter of intelligence.  https://ai.facebook.com/blog/self-supervised-learning-the-dark-matter-of-intelligence/, 2021\.  Accessed 2021-03-04.
  * [19] Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu.  Towards deep learning models resistant to adversarial attacks.  In International Conference on Learning Representations, 2018.
  * [20] Mehdi Noroozi and Paolo Favaro.  Unsupervised learning of visual representations by solving jigsaw puzzles.  In ECCV, pages 69–84. Springer International Publishing, 2016.
  * [21] Tianyu Pang, Kun Xu, Chao Du, Ning Chen, and Jun Zhu.  Improving adversarial robustness via promoting ensemble diversity.  In International Conference on Machine Learning, pages 4970–4979. PMLR, 2019.
  * [22] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang, Zachary DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala.  Pytorch: An imperative style, high-performance deep learning library.  In Advances in Neural Information Processing Systems 32, pages 8024–8035. Curran Associates, Inc., 2019.
  * [23] Deepak Pathak, Philipp Krähenbühl, Jeff Donahue, Trevor Darrell, and Alexei Efros.  Context encoders: Feature learning by inpainting.  In Computer Vision and Pattern Recognition (CVPR), 2016.
  * [24] Hadi Salman, Andrew Ilyas, Logan Engstrom, Ashish Kapoor, and Aleksander Madry.  Do adversarially robust imagenet models transfer better?  In Advances in Neural Information Processing Systems, volume 33, pages 3533–3545. Curran Associates, Inc., 2020.
  * [25] Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus.  Intriguing properties of neural networks.  arXiv preprint arXiv:1312.6199, 2013.
  * [26] Florian Tramèr, Alexey Kurakin, Nicolas Papernot, Ian Goodfellow, Dan Boneh, and Patrick McDaniel.  Ensemble adversarial training: Attacks and defenses.  arXiv, 2020.
  * [27] Trieu H. Trinh, Minh-Thang Luong, and Quoc V. Le.  Selfie: Self-supervised pretraining for image embedding.  CoRR, abs/1906.02940, 2019.
  * [28] Dimitris Tsipras, Shibani Santurkar, Logan Engstrom, Alexander Turner, and Aleksander Madry.  Robustness may be at odds with accuracy.  In International Conference on Learning Representations, 2019.
  * [29] Jingkang Wang, Tianyun Zhang, Sijia Liu, Pin-Yu Chen, Jiacen Xu, Makan Fardad, and Bo Li.  Beyond adversarial training: Min-max optimization in adversarial attack and defense.  CoRR, abs/1906.03563, 2019.
  * [30] Jingkang Wang, Tianyun Zhang, Sijia Liu, Pin-Yu Chen, Jiacen Xu, Makan Fardad, and Bo Li.  Adversarial attack generation empowered by min-max optimization.  In Advances in Neural Information Processing Systems (NeurIPS), 2021\.
  * [31] Eric Wong and Zico Kolter.  Provable defenses against adversarial examples via the convex outer adversarial polytope.  In International Conference on Machine Learning, pages 5286–5295. PMLR, 2018.
  * [32] Cihang Xie, Jianyu Wang, Zhishuai Zhang, Zhou Ren, and Alan Yuille.  Mitigating adversarial effects through randomization.  In International Conference on Learning Representations, 2018.
  * [33] Dejing Xu, Jun Xiao, Zhou Zhao, Jian Shao, Di Xie, and Yueting Zhuang.  Self-supervised spatiotemporal learning via video clip order prediction.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), June 2019.
  * [34] Richard Zhang, Phillip Isola, and Alexei A Efros.  Colorful image colorization.  In ECCV, 2016.


# Compression using quasi-interpolation

Martin D. Buhmann  Mathematics Institute, Justus-Liebig University
Arndtstrasse 2
D-35392 Giessen, Germany<EMAIL_ADDRESS>and  Feng Dai
Department of Mathematical and Statistical Sciences
University of Alberta
Edmonton, Alberta T6G 2G1, Canada<EMAIL_ADDRESS>
###### Abstract.

We consider quasi-interpolation with a main application in radial basis
function approximations and compression in this article. Constructing and
using these quasi-interpolants, we consider wavelet and compression-type
approximations from their linear spaces and provide convergence estimates. The
results include an error estimate for nonlinear approximation by quasi-
interpolation, results about compression in the space of continuous functions
and a pointwise convergence estimate for approximands of low smoothness.

The work of the second author was supported in part by NSERC Canada under
grant RGPIN 311678-2010 and by the Alexander-von-Humboldt Foundation.

##  1\. Introduction

We wish to study multivariate approximation schemes in this artice which are
useful approximation methods called quasi-interpolation methods. A principal
useful context – but not the only one – we have in mind is the related to the
so-called radial basis functions and the linear spaces spanned by their
translates because they in particular provide excellent means for multivariate
approximations in $d$-dimensional spaces. They are known in a variety of types
for at least thirty years [17]. Among their attractive, interesting properties
are (i) their approximation orders [6, 28] and (ii) their ability to adapt to
many different applications in several dimensions. Thus they are similar to
other successful approximation methods such as multivariate splines or finite
elements (both as the aforementoned piecewise polynomials) in low dimensional
ambient spaces [4],[3]. The most often used forms of approximation are either
interpolation at the same points by which they are translated [6, 2], or
quasi-interpolation (as detailed below), or wavelets [14], [7], [11].

All the different approaches to multivariate approximation have very positive
aspects; in this article we choose among them the mentioned quasi-
interpolation [8]. To this end, let $A$ be a set of quasi-uniformly
distributed points in ${\mathbb{R}}^{d}$, let a function
$f:{\mathbb{R}}^{d}\to{\mathbb{R}}$ be a at a minimum continuous given and to
be approximated (the “approximand”) based on knowing its values on $A$, and
let $\psi_{\alpha}$, $\alpha\in A$, be decaying continuous functions. The we
define the quasi-interpolant in the simplest case as

$Qf(x)=\sum_{\alpha\in A}f(\alpha)\psi_{\alpha}(x),\qquad
x\in{\mathbb{R}}^{d},$

requiring that the $\psi_{\alpha}$ decay sufficiently fast for large argument,
so that the above sum is well-defined, that is

$|\psi_{\alpha}(x)|=O((1+\|x-\alpha|)^{-d-m_{2}})$

for a positive $m_{2}$ and agrees with $f$ in case $f$ is a polynomial of some
maximum degree $\ell$ to be specified below.

We wish to find some pointwise convergence results of such approximations, and
we will study compression using them too. Our theorems include an error
estimate for nonlinear approximation by quasi-interpolation using radial basis
functions and otherwise, positive and negative results about compression in
the space of continuous functions using such approximations, and a pointwise
convergence estimate for approximands of low smoothness and quasi-
interpolation.

First, still keeping in mind the key context in which we wish to create and
use quasi-interpolation, we mention a few advantages of the radial basis
function approach: first they are available in any dimension of the ambient
space, so that it is now possible – in contrast to many of the polynomial
spline approaches – to approximate target functions in arbitrary dimensions.
This is needed often in practical scientific applications. From time to time
they are actually the only feasible approach to function approximation.

In this paper, we have some pointwise convergence results for very general
sets of approximands and compression methods. After repeating some preliminary
results partly from [9], we analyse approximants with quasi-interpolation and
find that both for compression and for deriving the convergence properties of
the approximants and the spaces where they are from, quasi-interpolation is a
suitable approach. Let us initially describe the form of the approximants more
precisely, including some examples for radial basis functions.

Since they will be our main application, let us briefly summarise that radial
basis function approximants typically have the form of sums multiples of
translates

$\varphi(\|\cdot-\alpha\|),$

where the norm is Euclidean, $\alpha\in{\mathbb{R}}^{d}$ are from a fixed,
discrete set $A$ of points (finite in applications, often infinite in the
theoretical analysis, sometimes equally spaced), and $\varphi$ is a
continuous, univariate function that is called the radial basis function.
Typical radial functions are multiquadrics $\varphi(r)=\sqrt{r^{2}+c^{2}}$ for
a positive, fixed parameter $c$ (which may incidentally be zero, in which case
we speak about the linear radial basis function $\varphi(r)=r$), or
$\varphi(r)=r^{2}\log r$, the so-called thin-plate spline [16], the Dagum-
Class [12] $\phi(r)=1-(r^{\beta}/(1+r^{\beta}))^{\gamma}$ with a variety of
choices for the parameters $\beta$ and $\gamma$, or an exponential function
$\varphi(r)=\exp(-c^{2}r^{2})$ or $\varphi(r)=\exp(-cr)$ with the same
positive parameter $c$ as above (but here it is not allowed to vanish).

There are many ways to form decaying functions for quasi-interpolation as
(finite) linear combinations of (increasing) radial basis functions, see for
instance [2]; all of them can be viewed as a type of preconditioning of the
approximation methods. For this article we adopt the conditions with respect
to general quasi-interpolation from [10] as they are general and admit even
non-equally spaced data $\alpha$. The resulting localised functions are
central to pointwise-error estimates which are one of the central features of
[9] and to some extent in this work. Estimates in $L^{p}$-norms such as
presented in the third section are also important, for instance, in the paper
[24] about errors of interpolation by surface or thin-plate splines (but not
about quasi-interpolation as we do here), and in the papers [2, 20, 22] for
$L^{p}$-approximation from shift-invariant spaces (where the quasi-
interpolation used is different from that in this paper). Using Gauß-
quadrature formulae and similar techniques, the paper [30] does indeed
consider quasi-interpolation and $L^{p}$-error estimates too, but neither
methods nor results are going in the same direction as here.

We use a wavelet approach as in [14], [11], [7], and compression with general
quasi-interpolation.

We begin our article by summarising suitable conditions on the aforementioned
generation of localised quasi-interpolating basis functions. We will then give
some useful pointwise convergence estimates (as to be contrasted to the usual
ones in norms) for approximands which may be outside the usual smoothness
requirements (of lower smoothness; or “rougher” in other words) of
differentiability as in [5].

The idea of compression, i.e. approximations employed where the sizes of the
coefficients in use are essential gives rise to the results, whereas
approximations of the wavelet-type are featured at the end of the paper. We
include, among other things, a result about the $N$-width type approximations
and a negative result about compression within the space of continuous
functions.

Throughout the paper, every function on ${\mathbb{R}}^{d}$ and every subset of
${\mathbb{R}}^{d}$ are assumed to be Lebesgue measurable. The letter $C$ will
denote a general positive constant depending only on the parameters indicated
as subscripts, and the notation $C^{\prime}\sim C^{\prime\prime}$ means that
there exist inessential positive constants $c_{1}$, $C_{1}$ such that
$c_{1}C^{\prime}\leq C^{\prime\prime}\leq C_{1}C^{\prime}$.

##  2\. Quasi-interpolation: General assumptions and results

In this section, we summarise results from [10], [9] and [8] on quasi-
interpolation and using the central example of radial basis functions which
will play crucial roles in our discussions in the later sections of this
article. We will also at this stage set the general definitions and
assumptions on the radial basis functions $\varphi$ in use which enable us to
go from plain shifts of radial basis functions to quasi-interpolants. Indeed,
we no longer require the functions to be radially symmetric as in the
introduction but deal with general, $d$-variate, real-valued continuous
functions $\varphi$.

We start with a brief description of some necessary notation. The Fourier
transform is specified by

$\widehat{f}(\xi):=\int_{{\mathbb{R}}^{d}}f(y)e^{-i\xi\cdot y}\,dy,\ \ \
\xi\in{\mathbb{R}}^{d},\ \ f\in L^{1}({\mathbb{R}}^{d}),$

thus the inverse Fourier transform will be scaled in this way:

${1\over(2\pi)^{d}}\int_{{\mathbb{R}}^{d}}\widehat{f}(\xi)e^{i\xi\cdot
y}\,d\xi,\ \ \ y\in{\mathbb{R}}^{d},\ \ \widehat{f}\in
L^{1}({\mathbb{R}}^{d}).$

We provide these definitions also because we need to state which normalisation
we take for the transforms. The convolution of two functions on
${\mathbb{R}}^{d}$ is defined by

$f\ast g(x):=\int_{{\mathbb{R}}^{d}}f(x-y)g(y)\,dy,\ \ x\in{\mathbb{R}}^{d},$

where $f\in\bigcup_{1\leq p\leq\infty}L^{p}({\mathbb{R}}^{d})$ and $g\in
L^{1}$, or vice-versa, or $f$ and $g$ are both nonnegative. We denote by
$B_{r}(x):=\\{y\in{\mathbb{R}}^{d}:\|x-y\|\leq r\\}$ the ball centred at
$x\in{\mathbb{R}}^{d}$ with radius $r$. For $f\in C^{k}({\mathbb{R}}^{d})$ and
$x\in{\mathbb{R}}^{d}$, we use the notation $T_{x}^{k}f$ to denote the Taylor
polynomial of $f$ of degree $k$ at the point $x$; that is,

$T_{x}^{k}f(y)=\sum_{|\gamma|\leq
k}\frac{D^{\gamma}f(x)}{\gamma!}(y-x)^{\gamma},\ \ y\in{\mathbb{R}}^{d}.$

Here, with respect to
$\gamma=(\gamma_{1},\ldots,\gamma_{d})\in{\mathbb{Z}}_{+}^{d}$ we use the
standard multi-index notation; in particular,
$|\gamma|=\gamma_{1}+\cdots+\gamma_{d}$ and
$D^{\gamma}=\Bigl{(}\frac{\partial}{\partial
x_{1}}\Bigr{)}^{\gamma_{1}}\cdots\Bigl{(}\frac{\partial}{\partial
x_{d}}\Bigr{)}^{\gamma_{d}}$. Furthermore, we denote by $\Pi_{n}^{d}$ the set
of all algebraic polynomials of degree at most $n$ on ${\mathbb{R}}^{d}$,
$\mathcal{P}_{j}^{d}$ being the homogeneous ones of degree $j$.

The set of centres by which the quasi-interpolating basis functions are
translated is of course relevant in any approach using quasi-interpolation. In
our work here, we allow infinite sets of such centres which need not, however,
be placed on a lattice. A countable subset $A$ of ${\mathbb{R}}^{d}$ is called
quasi-uniformly distributed in ${\mathbb{R}}^{d}$ if there exist positive
constants $c_{0}$ and $C_{1}$ such that ${\mathbb{R}}^{d}=\cup_{\alpha\in
A}B_{c_{0}}(\alpha)$, and

$\sum_{\alpha\in A}\raisebox{2.0pt}{$\chi$}_{B_{c_{0}}(\alpha)}\leq C_{1}.$

We denote by $\mathcal{A}$ the collection of all quasi-uniformly distributed
subsets of ${\mathbb{R}}^{d}$ with the same constants $c_{0}$ and $C_{1}$. For
convenience, we call the constants $c_{0}$ and $C_{1}$ here the geometric
constants of the set $A$. Throughout this paper, the letter $A$ will always
denote a quasi-uniformly distributed subset of ${\mathbb{R}}^{d}$ with the
same and fixed geometric constants $c_{0}$ and $C_{1}$. All the general
constants $C$ in this paper may depend on the geometric constants $c_{0}$ and
$C_{1}$ but will be independent of the set $A$ itself.

The following lemma, proved in [10, Lemma 3], and used also in [9], plays an
important general role in the definition of quasi-interpolation:

######  Lemma 2.1.

Given a quasi-uniformly distributed subset $A$ of ${\mathbb{R}}^{d}$ and a
positive integer $k$, there exists a sequence of compactly supported functions
$\\{N_{\alpha}\\}_{{\alpha}\in A}\subset C_{c}^{k}({\mathbb{R}}^{d})$ with the
properties that each $N_{\alpha}$ is supported in the ball $B_{M/2}({\alpha})$
for a positive constant $M$; $\sup_{{\alpha}\in
A}\|D^{\gamma}N_{{\alpha}}\|_{\infty}\leq C$ for all
$\gamma\in{\mathbb{Z}}_{+}^{d}$ with $|\gamma|\leq k$; and

$q=\sum_{{\alpha}\in A}q({\alpha})N_{{\alpha}},\ \ \ \forall q\in\Pi_{k}^{d}.$

Here the constants $C$ and $M$ depend only on $k$, $d$.

According to the proof in [10, Lemma 3], each function $N_{\alpha}$ in the
above lemma may be a compactly supported multivariate spline depending only on
$d$, $k$ and the points in the set $A\cap B_{M/2}({\alpha})$. In particular,
if $A\cap B_{M/2}({\alpha})={\mathbb{Z}}^{d}\cap B_{M/2}({\alpha})$ for some
${\alpha}\in A$, then we write $N_{\alpha}(x)=N(x-{\alpha})$ for a compactly
supported multivariate spline $N\in C_{c}^{k}({\mathbb{R}}^{d})$ independent
of the set $A$.

Let now $\varphi:{\mathbb{R}}^{d}\to{\mathbb{R}}$ be a continuous function. We
require this $\varphi$ to be of at most polynomial growth so that it can be
viewed as a tempered distribution or so-called generalised function. Therefore
it has a distributional Fourier transform $\widehat{\varphi}$ which we
specifically require to be of the form
$\widehat{\varphi}(\xi)=(F(\xi)+bG_{0}(\xi)\log\|\xi\|)/G(\xi)$ for $\xi$ near
the origin, say for $\xi\in B_{1}(0)$. Here $b$ is a constant, $G_{0}$ is a
homogeneous polynomial of degree $n_{0}\geq 0$. Furthermore $F$ and $G$ are
real-valued functions on the ball $B_{1}(0)$ satisfying the following
conditions:

  1. (2A)

$G$ is a homogeneous polynomial of positive even degree $2m_{1}$ and
$G(\xi)\neq 0$ for all $\xi\in{\mathbb{R}}^{d}\setminus\\{0\\}$.

  2. (2B)

$F\in C^{m_{0}}(B_{1}(0))\cap C^{m_{0}+d+1}(B_{1}(0)\setminus\\{0\\})$ for
some nonnegative integer $m_{0}$, $F(0)\neq 0$, and there exists
${\theta}\in(0,1]$ such that for all $\gamma\in{\mathbb{Z}}_{+}^{d}$ with
$|{\gamma}|\leq m_{0}+d+1$,

(2.1) $\Bigl{|}D^{\gamma}\bigl{[}F(\xi)-\tau_{m_{0}}(\xi)\bigr{]}\Bigr{|}\leq
C\|\xi\|^{m_{0}+{\theta}-|\gamma|},\ \ \text{as $\|\xi\|\to 0_{+}$},$

where $\tau_{m_{0}}$ denotes the Taylor polynomial of $F$ of degree $m_{0}$
about $\xi=0$.

In addition to the conditions (2A) and (2B), we also assume the following
condition on derivatives of $\widehat{\varphi}(\xi)$ for large $\|\xi\|$:

  1. (2C)

The Fourier transform $\widehat{\varphi}$ of $\varphi$ is $(m_{0}+d+1)$-times
continuously differentiable on the domain $\\{\xi\in{\mathbb{R}}^{d}:\
\|\xi\|>\frac{1}{4}\\}$, and

(2.2) $\max_{|{\gamma}|\leq
m_{0}+d+1}\int_{\|\xi\|\geq\frac{1}{4}}|D^{\gamma}\widehat{\varphi}(\xi)|\,d\xi\leq
C<\infty.$

As in [10, p. 245], we introduce the following definition:

######  Definition 2.2.

Let $T_{m_{0}}$ denote the Taylor polynomial of the function $1/F$ of degree
$m_{0}$ at the origin, and let $P(x)=T_{m_{0}}(x)G(x)$. For each
${\alpha},{\beta}\in A$, define

(2.3)
$\mu_{{\alpha}{\beta}}:=\int_{{\mathbb{R}}^{d}}N_{\alpha}(x)P(iD)N_{\beta}(x)\,dx,$

where $\\{N_{\alpha}\\}_{{\alpha}\in A}$ is the sequence of functions given in
Lemma 2.1 with $k=2m_{1}+m_{0}+1$.

From the above definition and Lemma 2.1, it is clear that
$\mu_{{\alpha}{\beta}}=0$ if $\|{\alpha}-{\beta}\|\geq M$,
$\mu_{{\alpha}{\beta}}=\overline{\mu_{{\beta}{\alpha}}}$ for all
${\alpha},{\beta}\in A$, where $M$ is the positive constant given in Lemma 2.1
with $k=2m_{1}+m_{0}+1$. More importantly, the sequence
$\\{\mu_{{\alpha}{\beta}}\\}$ has the following important property, as was
shown in [10, Theorem 7]:

(2.4) $\sum_{{\beta}\in A}\mu_{{\alpha}{\beta}}q({\beta})=0,\ \
\forall{\alpha}\in A,\ \ \forall
q\in\text{ker}\,G(D)\cap\Pi_{2m_{1}+m_{0}+1}^{d}.$

Furthermore, in the case when $A={\mathbb{Z}}^{d}$,

(2.5)
$\mu_{{\alpha}{\beta}}=\mu_{{\beta}-{\alpha}}=\int_{{\mathbb{R}}^{d}}N(y-{\beta}+{\alpha})P(iD)N(y)\,dy,\
\ \ {\alpha},{\beta}\in{\mathbb{Z}}^{d},$

and the sequence satisfies ([8, 10])

(2.6) $\sum_{j\in{\mathbb{Z}}^{d}}\mu_{j}q(j)=P(iD)q(0),\ \ \ \forall
q\in\Pi_{2m_{1}+m_{0}+1}^{d}.$

The expression on the left-hand side of (2.4) or (2.6) is in fact a local
difference of the polynomial $q$ at the point ${\alpha}\in A$ which is closely
related to the derivative $P(iD)q({\alpha})$.

A remarkable fact is that the above defined sequence admits the mentioned
quasi-interpolation, central and useful for our application. More precisely,
under the above assumptions on the Fourier transform $\widehat{\varphi}$, the
following result [9] holds:

Theorem A. Under the above assumptions, the functions $\psi_{\alpha}$,
${\alpha}\in A$, defined by

(2.7) $\psi_{\alpha}(x):=\sum_{{\beta}\in
A}\mu_{{\alpha}{\beta}}\varphi(x-{\beta}),\ \ x\in{\mathbb{R}}^{d},$

have the decaying property

(2.8) $|\psi_{\alpha}(x)|\leq C(1+\|x-{\alpha}\|)^{-d-m_{2}},\ \
x\in{\mathbb{R}}^{d},\ \ {\alpha}\in A,$

where

(2.9) $m_{2}:=\begin{cases}m_{0}+{\theta},&\ \ \text{if $b=0$};\\\
\min\\{m_{0}+{\theta},n_{0}\\},&\ \ \text{if $b\neq 0$};\end{cases}$

and furthermore, the operator defined by (“quasi-interpolation”)

(2.10) $Qf:=\sum_{{\alpha}\in A}f({\alpha})\psi_{\alpha}$

reproduces all polynomials of total degree at most
$\ell_{0}:=\min\\{m_{0},2m_{1}-1\\}$; that is, $Qp=p$ for all
$p\in\Pi_{\ell_{0}}^{d}$.

Here and elsewhere in the paper, the letter $C$ denotes a constant that may
depend on $m_{1},m_{0}$, $n_{0}$, and $d$.

######  Remark 2.1.

  1. (i)

We would like to remark that, in fact, in the case of $b=0$, Theorem A  with
slightly weaker decaying estimates of the functions $\psi_{\alpha}$ was proved
in [10], where (2.8) with $m_{0}$ in place of $m_{2}$ was shown. Infinite
differentiability on ${\mathbb{R}}^{d}\setminus\\{0\\}$ and slightly stronger
pointwise estimates of the derivatives $D^{\gamma}\widehat{\varphi}(\xi)$ for
large $\xi$ were required in [10], but by looking carefully at the proofs
there, the assumptions can be slightly reduced as we did above. Concretely,
the aforementioned differentiability assumptions are used in that paper [10]
to obtain the correct asymptotic behaviour of the inverse Fourier transform of
the remainder term $\hat{r}_{\ell+1+\theta}(\omega)$. For this, no infinite
differentiability is required as indeed the said inverse Fourier transform
need not decay of arbitrary high negative order but only at the same rate as
the rest of the expression.

  2. (ii)

Here an additional term $b\log\|\xi\|$ has been added in the Fourier transform
of $\varphi$ in order to include the “shifted” versions of some important
radial basis functions, where a direct application of the general results of
[10, Theorem 8] normally would not yield the optimal decaying estimate (2.8) .
In fact, Theorem A of [9] for $b\in{\mathbb{C}}$, $A={\mathbb{Z}}^{d}$ and
$G(x)=\|x\|^{2m}$ was proved in [8].

The combination of localisation of the operator (by the decaying properties of
$\psi_{\alpha}$) and the polynomial reproduction admits the derivation of
approximation orders to sufficiently smooth approximands. This requires, of
course, a scaling of the given centres.

Indeed, given $h>0$, the following quasi-interpolation operator with scaling
was introduced and studied in [10]:

(2.11) $Q_{h}f(x):=\sum_{{\alpha}\in A}f(h{\alpha})\psi_{\alpha}(h^{-1}x),\ \
x\in{\mathbb{R}}^{d}.$

For the rest of the paper, we will set $\ell:=\min\\{m_{0}-1,2m_{1}-1\\}$.
Observe that condition (2.10) implies that we have the desirable polynomial
reproduction property

$Q_{h}q=q,\ \ \forall q\in\Pi_{\ell}^{d}.$

The following estimates were proved in [10] for the case of $b=0$: If $f\in
C^{\ell+1}({\mathbb{R}}^{d})$ has bounded partial derivatives of total orders
$\ell$ and $\ell+1$, then for any $h\in(0,1)$,

(2.12) $\|f-Q_{h}f\|_{\infty}\leq C_{f}h^{\ell+1}|\log h|,$

where

$C_{f}:=\|\nabla^{\ell}f\|_{L^{\infty}({\mathbb{R}}^{d})}+\|\nabla^{\ell+1}f\|_{L^{\infty}({\mathbb{R}}^{d})}.$

######  Remark 2.2.

These estimates are already reformulated slightly to suit the analysis in this
paper below, and in particular, here and in what follows, the notation
$\nabla^{k}f$ denotes the vector with components $D^{\alpha}f$,
$|{\alpha}|=k$, for a given positive integer $k$. For convenience, we also set
$\nabla^{0}f=f$.

######  Remark 2.3.

Due to the slightly faster decay (2.8), we can easily prove, whenever $b=0$,
that neither the log term in (2.12), nor the term
$\|\nabla^{\ell}f\|_{L^{\infty}({\mathbb{R}}^{d})}$ in $C_{f}$ is needed.

Using (2.8), and a straightforward calculation, we can deduce the following
useful estimates which shall be employed in the next section:

######  Proposition 2.3.

Let $A$ be a quasi-uniformly distributed subset of ${\mathbb{R}}^{d}$, and let
$h\in(0,1)$. Then for $0\leq a<m_{2}$,

(2.13) $\sup_{x\in{\mathbb{R}}^{d}}\sum_{{\alpha}\in
A}|\psi_{\alpha}(x/h)|(\|x-{\alpha}h\|+h)^{a}\leq C_{a}h^{a},$

and for any $\varepsilon>0$,

$\sup_{x\in{\mathbb{R}}^{d}}\sum_{{\alpha}\in
A}|\psi_{\alpha}(x/h)|(\|x-{\alpha}h\|+h)^{m_{2}}(1+\|x-{\alpha}h\|)^{-\varepsilon}\leq
C_{\varepsilon}h^{m_{2}}|\log h|.$

##  3\. Pointwise approximation by quasi-interpolation for functions of lower
smoothness in $L^{p}$

Error estimates where the approximands are rougher, i.e. from larger function
spaces with less smoothness required, than the approximating (radial) basis
functions or quasi-interpolants are essential in practical applications
because we cannot in general guarantee high order smoothness of the possibly
unknown functions which are to be approximated (i.e., they are only known e.g.
at a finite number of points). On the other hand, however, functions of lower
smoothness in $L^{p}$ (say, for instance, $f\in W_{p}^{r}$ with $r<d/p$) are
defined only almost everywhere on ${\mathbb{R}}^{d}$, and pointwise evaluation
functionals make no sense for such functions. Thus, the quasi-interpolation
operators $Q_{h}$ considered in the last two sections are no longer applicable
to functions of lower smoothness in $L^{p}$. In this section, we will modify
the definition of $Q_{h}f$ so that it is defined for every locally integrable
function. It turns out that such modified operators, although not as
convenient for practical implementation, is easier to handle. In fact, we will
establish stronger pointwise error estimates in this section, which will play
crucial roles in Section 4 when we consider compression in approximation by
radial basis functions.

We start with the definition of the modified quasi-interpolation. First,
consider the linear functional $S_{0}:\Pi_{\ell}^{d}\to{\mathbb{R}}$ given by
$S_{0}P=P(0)$. Since the space $\Pi_{\ell}^{d}$ is finite dimensional, it
follows that

$|S_{0}P|\leq\max_{y\in B_{1}(0)}|P(y)|\leq
C_{\ell,d}\int_{B_{1}(0)}|P(y)|\,dy,\ \ \forall P\in\Pi_{\ell}^{d}.$

By the Hahn-Banach theorem, this linear functional can be extended to a
bounded linear functional on the space $L^{1}(B_{1}(0))$ such that
$S_{0}P=P(0)$ for all $P\in\Pi_{\ell}^{d}$, and

(3.1) $|S_{0}f|\leq C\int_{B_{1}(0)}|f(y)|\,dy,\ \ \forall f\in
L^{1}(B_{1}(0)).$

For each ${\alpha}\in A$, we define

$S_{\alpha}f:=S_{0}\Bigl{(}f(\cdot+{\alpha})\Bigr{)},\ \ f\in
L^{1}(B_{1}({\alpha})).$

Hence, $S_{\alpha}P=P({\alpha})$ for all $P\in\Pi_{\ell}^{d}$, and by (3.1),

(3.2) $|S_{\alpha}f|\leq C\int_{B_{1}({\alpha})}|f(y)|\,dy,\ \ \forall f\in
L^{1}(B_{1}({\alpha})),\ \ \forall{\alpha}\in A.$

Now for $h>0$ and every locally integrable function $f$ on ${\mathbb{R}}^{d}$,
we define the modified quasi-interpolation $\widetilde{Q}_{h}f$ by

(3.3) $\widetilde{Q}_{h}f(x):=\sum_{{\alpha}\in
A}f^{h}({\alpha})\psi_{\alpha}(x/h),\ \ x\in{\mathbb{R}}^{d},$

where $f^{h}({\alpha}):=S_{{\alpha}}({\sigma}_{h}f)$ and
$\sigma_{h}f(\cdot)=f(h\cdot)$.

There are many smoothing techniques to construct the coefficients
$f^{h}({\alpha})$ in (3.3) explicitly via integrals. Next, we give several
examples of these techniques.

######  Example 3.1.

Let $\\{\phi_{j}\\}_{j=0}^{\text{dim}\,\Pi_{\ell}^{d}}$ be an orthonormal
basis of $\Pi_{\ell}^{d}$ with respect to the inner product of
$L^{2}(B_{1}(0))$, and let
$\Phi_{\ell}(y)=\sum_{j=0}^{\text{dim}\,\Pi_{\ell}^{d}}\phi_{j}(y)\phi_{j}(0)$.
Define $S_{0}f:=\int_{B_{1}(0)}f(y)\Phi_{\ell}(y)\,dy$ for $f\in
L^{1}(B_{1}(0)).$ Accordingly, we have

$f^{h}({\alpha}):=h^{-d}\int_{B_{h}({\alpha}h)}f(y)\Phi_{\ell}(h^{-1}y-{\alpha})\,dy,\
\ \ h>0,\ \ \ {\alpha}\in A.$

######  Example 3.2.

Let $N\in C^{2\ell+1}({\mathbb{R}}^{d})$ be a compactly supported multivariate
spline with $\text{supp}\,N\subset B_{c_{1}}(0)$ for some $c_{1}>0$ such that

$\sum_{j\in{\mathbb{Z}}^{d}}p(j)N(x-j)=p(x),\ \ \forall p\in\Pi_{\ell}^{d}.$

The Strang-Fix condition on $N$ then implies that (see, for instance, [10])

$p(0)=\int_{{\mathbb{R}}^{d}}p(x)N(x)\,dx,\ \ \forall p\in\Pi_{\ell}^{d}.$

Thus, we can define

$S_{0}(f):=\int_{B_{1}(0)}f(x)N_{c^{\prime}}(x)\,dx,\ \ \forall f\in
L^{1}(B_{1}(0)),$

where $c^{\prime}=c_{1}^{-1}$ and
$N_{\varepsilon}(\cdot)=\varepsilon^{-d}N(\varepsilon^{-1}\cdot)$ for
$\varepsilon>0$. Accordingly,

$f^{h}({\alpha}):=h^{-d}\int_{B_{h}({\alpha}h)}f(y)N_{c^{\prime}}(h^{-1}y-{\alpha})\,dy,\
\ \ h>0,\ \ \ {\alpha}\in A.$

The next example is due to Jia and Lei [20], who also obtained the order of
$L^{p}$-approximation by the associated quasi-interpolation with
$A={\mathbb{Z}}^{d}$.

######  Example 3.3.

Let $\eta\in C_{c}^{\infty}({\mathbb{R}}^{d})$ be such that $\text{supp}\
\eta\subset B_{1}(0)$ and $\int_{{\mathbb{R}}^{d}}\eta(x)\,dx=1$. Define

$S_{0}f:=\int_{B_{1}(0)}(f(0)-{\triangle}_{u}^{\ell+1}f(0))\eta(u)\,du,$

where ${\triangle}_{u}^{k}$ denotes the $k$-th order difference operator with
step $u$. Since ${\triangle}_{u}^{\ell+1}P=0$ for all $P\in\Pi_{\ell}^{d}$,
$S_{0}$ clearly satisfies the conditions stated above. In this case, the
$f^{h}$ can be expressed explicitly as in (5.1) in [9] with $k=\ell+1$: viz.

(3.4)
$f^{h}(x):=h^{-d}\int_{{\mathbb{R}}^{d}}(f(x)-{\triangle}_{u}^{k}f(x))\eta(u/h)\,du,\
\ x\in{\mathbb{R}}^{d},$

where ${\triangle}_{u}^{k}$ denotes the $k$-th order difference operator given
by

${\triangle}_{u}^{k}f(x):=\sum_{j=0}^{k}(-1)^{j}\binom{k}{j}f(x-ju),\ \
x\in{\mathbb{R}}^{d}.$

The main goal in this section is to prove the following pointwise error
estimate:

######  Theorem 3.4.

Let $f\in C^{r}({\mathbb{R}}^{d})$, $1\leq r\leq\ell+1$ and
$x\in{\mathbb{R}}^{d}$.

  1. (i)

If $r<m_{2}$, then for all $h>0$,

(3.5) $|f(x)-\widetilde{Q}_{h}f(x)|\leq
Ch^{r}\bigl{(}\|\nabla^{r}f\|\ast\Psi_{h}\bigr{)}(x)$

where $\Psi(z):=\|z\|^{-d+1}(1+\|z\|)^{-1-m_{2}+r}$ and
$\Psi_{h}(\cdot)=h^{-d}\Psi(h^{-1}\cdot)$.

  2. (ii)

If $r=m_{2}$, then for $h\in(0,1)$,

(3.6) $\displaystyle|f(x)-\widetilde{Q}_{h}f(x)|\leq$ $\displaystyle
Ch^{r}\Bigl{[}(\|\nabla^{r}f\|\ast\Phi^{h})(x)+\|\nabla^{r-1}f(x)\|\Bigr{]}$

where

$\Phi^{h}(z):=\|z\|^{-d+1}(\|z\|+h)^{-1}(1+\|z\|)^{-1}.$

A straightforward calculation shows that the convolutions on the right hand
sides of both (3.5) and (3.6) can be dominated by the Hardy-Littlewood maximal
functions of some derivatives of $f$. Thus, from Theorem 3.4, we deduce the
following useful corollary, which will play a crucial role in Section 4 when
we consider compressions in radial basis function approximation. The operator
$M$ used here is the Hardy–Littlewood maximal function

$Mf(x):=\sup_{\delta>0}{1\over|B_{\delta}(x)|}\int_{B_{\delta}(x)}|f(z)|\,dz.$

######  Corollary 3.5.

Let $r\in{\mathbb{N}}$, $1\leq r\leq\ell+1$, $f\in C^{r}({\mathbb{R}}^{d})$,
and $x\in{\mathbb{R}}^{d}$. If $r<m_{2}$, then

(3.7) $\displaystyle\ \ \ |f(x)-\widetilde{Q}_{h}f(x)|\leq
Ch^{r}M(\|\nabla^{r}f\|)(x),\ \ \ h>0,$

whereas if $r=m_{2}$, then for $h\in(0,1)$,

$\displaystyle\ \ \ |f(x)-\widetilde{Q}_{h}f(x)|\leq Ch^{r}\max\\{1,|\log
h|\\}\Bigl{(}M(\|\nabla^{r}f\|)(x)+\|\nabla^{r-1}f(x)\|\Bigr{)}.$

Corollary 3.5 together with the usual density argument also implies the
following rate of pointwise convergence of the modified quasi-interpolation.

######  Corollary 3.6.

If $1\leq p<\infty$, $w\in A_{p}$, $f\in W_{p}^{r}({\mathbb{R}}^{d},w)$ and
$1\leq r\leq\ell$, then for almost every $x\in{\mathbb{R}}^{d}$,

$\lim_{h\to 0}h^{-r}(f(x)-\widetilde{Q}_{h}f(x))=0.$

Another result that can be deduced directly from Theorem 3.4 via
straightforward calculations is the following.

######  Corollary 3.7.

Let $1\leq p\leq\infty$, $w\in A_{p}$, $1\leq r\leq\ell+1$, and $f\in
W_{p}^{r}({\mathbb{R}}^{d},w)$. Then for $h\in(0,1)$,

(3.8) $\displaystyle\|f-\widetilde{Q}_{h}f\|_{p,w}\leq
Ch^{r}\|f\|_{W_{p}^{r}({\mathbb{R}}^{d},w)},$

with $h^{r}|\log h|$ in place of $h^{r}$ in the case when $r=m_{2}$.

The rest of the section is devoted to the proof of Theorem 3.4.

###  3.1. Proof of Theorem 3.4

For simplicity, we will prove the result for the case of $1\leq r<m_{2}$ only.
The proof below with slight modifications works equally well for the case of
$r=m_{2}$. By the property of polynomial reproduction, we may write

(3.9) $\displaystyle|f(x)-\widetilde{Q}_{h}f(x)|\leq\sum_{{\alpha}\in
A}|S_{\alpha}(\sigma_{h}f)-T_{x}^{r-1}f({\alpha}h)||\psi_{\alpha}(x/h)|.$

Since $T_{x}^{r-1}f({\alpha}h)=T_{x/h}^{r-1}(\sigma_{h}f)({\alpha})$ and
$T_{x/h}^{r-1}(\sigma_{h}f)\in\Pi_{\ell}^{d}$, it follows by (3.2) that

$\displaystyle|S_{\alpha}(\sigma_{h}f)-T_{x}^{r-1}f({\alpha}h)|$
$\displaystyle=\Bigl{|}S_{\alpha}\Bigl{[}\sigma_{h}f-T_{x/h}^{r-1}(\sigma_{h}f)\Bigr{]}\Bigr{|}$
(3.10) $\displaystyle\leq
C\frac{1}{|B_{h}({\alpha}h)|}\int_{B_{h}({\alpha}h)}|f(y)-T_{x}^{r-1}f(y)|\,dy,$

which, using Theorem 3.1 of [9] with $r=m$, is bounded above by

(3.11) $\displaystyle Ch^{-d}$
$\displaystyle\int_{B_{h}({\alpha}h)}\|x-y\|^{r-1}\max_{u=x,y}\Bigl{[}\int_{B_{2\|x-y\|}(x)}\|\nabla^{r}f(z)\|\,\|z-u\|^{1-d}\,dz\Bigr{]}\,dy.$

Since $B_{2\|x-y\|}(x)\subset B_{2(\|x-{\alpha}h\|+h)}(x)$ whenever $y\in
B_{h}({\alpha}h)$, the term in (3.11) is bounded above by a constant multiple
of

$(h+\|x-{\alpha}h\|)^{r-1}L_{x,{\alpha},h}(x)+h^{-d}\int_{B_{h}({\alpha}h)}\|x-y\|^{r-1}L_{x,{\alpha},h}(y)\,dy,$

where

(3.12)
$L_{x,{\alpha},h}(u):=\int_{B_{2(\|x-{\alpha}h\|+h)}(x)}\|\nabla^{r}f(z)\|\|z-u\|^{-d+1}\,dz.$

Thus, the term on the right hand side of (3.9) is dominated by a constant
multiple of $\Sigma_{1}(x)+\Sigma_{2}(x)$, where

$\displaystyle\Sigma_{1}(x):=$ $\displaystyle\sum_{{\alpha}\in
A}\bigl{(}h+\|x-{\alpha}h\|\bigr{)}^{r-1}|\psi_{\alpha}(x/h)|L_{x,{\alpha},h}(x),$
$\displaystyle\Sigma_{2}(x):=$ $\displaystyle h^{-d}\sum_{{\alpha}\in
A}|\psi_{\alpha}(x/h)|\int_{B_{h}({\alpha}h)}\|x-y\|^{r-1}L_{x,{\alpha},h}(y)\,dy.$

By the proof of Lemma 4.4 in [9] with $m=r$, it is easily seen that

(3.13) $\Sigma_{1}(x)\leq
Ch^{r}\bigl{(}\|\nabla^{r}f\|\ast\Psi_{h}\bigr{)}(x).$

To estimate the sum $\Sigma_{2}(x)$, we decompose $A$ as
$A:=\cup_{j=0}^{\infty}A_{j,h}(x)$, where $A_{0,h}(x):=\\{{\alpha}\in A:\ \
\|{\alpha}-h^{-1}x\|\leq 2\\}$ and $A_{j,h}(x):=\\{{\alpha}\in A:\ \
2^{j}<\|{\alpha}-h^{-1}x\|\leq 2^{j+1}\\}$ for $j\geq 1$. Using (3.12), for
each ${\alpha}\in A_{j,h}$, we have

$\displaystyle\int_{B_{h}({\alpha}h)}\|x-y\|^{r-1}L_{x,{\alpha},h}(y)\,dy$
$\displaystyle\leq
C(2^{j}h)^{r-1}\int_{B_{2^{j+3}h}(x)}\|\nabla^{r}f(z)\|\Bigl{[}\int_{B_{h}({\alpha}h)}\|z-y\|^{-d+1}\,dy\Bigr{]}\,dz.$

Since $\cup_{{\alpha}\in A_{j,h}}B_{h}({\alpha}h)\subset B_{2^{j+2}h}(x)$ and
by quasi-uniformity,

$\sup_{x\in{\mathbb{R}}^{d}}\sup_{h\in(0,1)}\sum_{{\alpha}\in
A}\raisebox{2.0pt}{$\chi$}_{B_{h}({\alpha}h)}(x)\leq C<\infty,$

it follows that

$\displaystyle h^{-d}\sum_{{\alpha}\in
A_{j,h}(x)}|\psi_{\alpha}(x/h)|\int_{B_{h}({\alpha}h)}\|x-y\|^{r-1}L_{x,{\alpha},h}(y)\,dy$
$\displaystyle\leq
C2^{-jm_{2}}(2^{j}h)^{r-1-d}\int_{B_{2^{j+3}h}(x)}\|\nabla^{r}f(z)\|\Bigl{[}\int_{B_{2^{j+2}h}(x)}\|y-z\|^{-d+1}\,dy\Bigr{]}\,dz$
$\displaystyle\leq
C2^{-jm_{2}}(2^{j}h)^{r-d}\int_{B_{2^{j+3}h}(x)}\|\nabla^{r}f(z)\|dz,$

where the second step uses the fact that $B_{2^{j+3}h}(x)\subset
B_{2^{j+4}h}(z)$ whenever $z\in B_{2^{j+3}h}(x)$. Hence, by Fubini’s theorem,

$\displaystyle\Sigma_{2}(x)\leq
C\sum_{j=0}^{\infty}2^{-jm_{2}}(2^{j}h)^{r-d}\int_{B_{2^{j+3}h}(x)}\|\nabla^{r}f(z)\|dz$
$\displaystyle\leq
Ch^{r-d}\int_{{\mathbb{R}}^{d}}\|\nabla^{r}f(z)\|\Bigl{[}\sum_{2^{j}\geq
c^{\prime}(1+h^{-1}\|x-z\|)}2^{-j(m_{2}+d-r)}\Bigr{]}\,dz$ (3.14)
$\displaystyle\leq Ch^{r}(\|\nabla^{r}f\|\ast\Psi_{h})(x).$

Thus, combining (3.13) with (3.14), we obtain the desired estimate, and hence
complete the proof.

##  4\. Compression in the space $C({\mathbb{R}}^{d})$

One view of using compression for our approximation purposes is to limit the
number of terms in the expansions with radial basis functions. Compression
with radial basis functions in the very special way of using Gauß-kernels
turns up also in the paper [18].

Indeed, let $\varphi$ be a continuous function on ${\mathbb{R}}^{d}$, and let
$A\subset{\mathbb{R}}^{d}$ be quasi-uniformly distributed. For a positive
integer $n$, we define

$\Sigma_{n,\varphi,h}:=\Bigl{\\{}\sum_{j=1}^{n}c_{j}\varphi(h^{-1}\cdot-{\alpha}_{j}):\
\ {\alpha}_{j}\in A,\ x_{j}\in{\mathbb{R}}^{d},\ \
c_{j}\in{\mathbb{R}}\Bigr{\\}},\ \ h\in(0,1).$

Our main purpose in this section is to study the following $n$-term
approximation of a given continuous function $f$:

$\hat{\sigma}_{n,h}(f):=\inf_{g\in\Sigma_{n,\varphi,h}}\|f-g\|_{\infty}.$

We start with a negative result for compression in the space
$C({\mathbb{R}}^{d})$, which asserts that given any $h>0$, the quantity
$\hat{\sigma}_{n,h}(f)$ may not tend to zero as $n\to\infty$ for general
continuous functions $f$.

######  Theorem 4.1.

Let $\\{\psi_{j}\\}_{j\in{\mathbb{Z}}}$ be a sequence of continuous functions
on ${\mathbb{R}}^{d}$ with

$\lim_{\|x\|\to\infty}|\psi_{j}(x)|=0,\ \ \forall j\in{\mathbb{Z}}.$

Then for any $n\in{\mathbb{N}}$, and $r\in{\mathbb{N}}$,

$\sup_{\|f\|_{W_{\infty}^{r}}\leq
1}\inf_{g\in\Sigma_{n}}\|f-g\|_{L^{\infty}({\mathbb{R}}^{d})}\geq c_{r}>0,$

where

$\Sigma_{n}:=\Bigl{\\{}\sum_{j=1}^{n}c_{j}\psi_{j}(h_{j}^{-1}\cdot):\
c_{j}\in{\mathbb{R}},\ \ h_{j}>0\Bigr{\\}}.$

###### Proof.

Since for any $g\in\Sigma_{n}$,

$\lim_{\|x\|\to\infty}g(x)=0,$

it follows that

$\|f-g\|_{\infty}$

remains positive for any constant function $f$ or infinite sum $f$ of shifts
of a suitable compactly supported test-function. ∎

The above proposition shows that in order to study the $n$-term approximation
problem in $C({\mathbb{R}}^{d})$, one has to assume some decaying condition of
the function at infinity. For example, we have a positive result if we assume
that $f\in W_{p}^{r}$ with $r>\frac{d}{p}$ for some $1\leq p<\infty$. In fact,
a greedy algorithm can be constructed in this case. This is the theme of our
next theorem. We refer to the book [27] for recent development of greedy
approximation.

######  Theorem 4.2.

Assume that $1\leq p<\infty$, $r>\frac{d}{p}$ and $f\in
W_{p}^{r}({\mathbb{R}}^{d})$. Let $\beta:=\min\\{r-\frac{d}{p},\ell+1\\}$. For
$n\in{\mathbb{N}}$ define

$\mathcal{G}_{n}f(x)=\sum_{{\alpha}\in\Lambda}f(h{\alpha})\psi_{\alpha}(h^{-1}x)\
\ \ \text{with $h\sim n^{-\frac{1}{p{\beta}+d}}$},$

where $\Lambda\subset A$ satisfies that $\\#\Lambda=n$, and
$\min_{{\alpha}\in\Lambda}|f(h{\alpha})|\geq\max_{{\alpha}\in
A\setminus\Lambda}|f(h{\alpha})|$. Then

(4.1) $\|f-\mathcal{G}_{n}f\|_{L^{\infty}({\mathbb{R}}^{d})}\leq
Cn^{-\frac{{\beta}}{p{\beta}+d}}\log n\|f\|_{W_{p}^{r}({\mathbb{R}}^{d})}.$

The proof of Theorem 4.2 relies on the following straightforward lemma.

######  Lemma 4.3.

Given any $(a_{\alpha})_{\alpha\in A}\subset{\mathbb{R}}$, we have

$\Biggl{\|}\sum_{{\alpha}\in
A}a_{\alpha}\psi_{\alpha}\Biggr{\|}_{L^{p}({\mathbb{R}}^{d})}\leq
C\Bigl{(}\sum_{{\alpha}\in A}|a_{\alpha}|^{p}\Bigr{)}^{\frac{1}{p}},\ \ 1\leq
p\leq\infty,$

with the usual change when $p=\infty$.

###### Proof.

This lemma follows directly from the Hölder inequality and the first estimate
in Proposition 2.3 in [9] (i.e., (2.13)) with $i=0$. ∎

We are now in a position to prove Theorem 4.2.

Proof of Theorem 4.2. Using Lemma 6.4 of [9], we have

$\sum_{{\alpha}\in A}|f(h{\alpha})|^{p}\leq C^{p}h^{-d}\|f\|^{p}_{W_{p}^{r}}.$

This, in particular, implies that there are at most $n$ elements in the set
$A$ such that

$|f(h{\alpha})|\geq Ch^{-d/p}n^{-\frac{1}{p}}\|f\|_{W_{p}^{r}}.$

Thus, for the set $\Lambda$ defined in Theorem 4.2, we have

$|f(h{\alpha})|\leq Ch^{-d/p}n^{-\frac{1}{p}}\|f\|_{W_{p}^{r}},\ \
\forall{\alpha}\in A\setminus\Lambda.$

By Lemma 4.3, this in turn implies that

$|Q_{h}f(x)-\mathcal{G}_{n}f(x)|\leq\sum_{{\alpha}\in
A\setminus\Lambda}|f({\alpha}h)||\psi_{\alpha}(x/h)|\leq
Ch^{-d/p}n^{-\frac{1}{p}}\|f\|_{W_{p}^{r}}.$

On the other hand, using (5.7) in [9],

$\|f-Q_{h}f\|_{\infty}\leq Ch^{\beta}|\log h|\|f\|_{W_{p}^{r}}.$

Therefore, choosing $h\sim n^{-\frac{1}{{\beta}p+d}}$ so that $h^{\beta}\sim
n^{-\frac{1}{p}}h^{-d/p},$ we have that

$\|f-\mathcal{G}_{n}f\|_{\infty}\leq Cn^{-\frac{{\beta}}{{\beta}p+d}}\log
n\|f\|_{W_{p}^{r}}.$

$\Box$

In general, we have the following result:

######  Proposition 4.4.

Assume that $1\leq r\leq\ell+1$, and $f:{\mathbb{R}}^{d}\to{\mathbb{R}}$ has
bounded, continuous partial derivatives up to the order $r$. Assume, in
addition, that $f$ satisfies the decaying condition

(4.2) $\sup_{M\geq 1}M^{a}\Bigl{(}\int_{\|x\|\geq
M}|f(x)|^{p}\,dx\Bigr{)}^{\frac{1}{p}}\leq C_{1}<\infty$

for some $a\geq 0$, and $1\leq p<\infty$. For $n\in{\mathbb{N}}$, let
$h\in(0,1)$ be such that

$h\sim n^{-\frac{1}{d}\frac{ap+d}{d+(a+r)p}},$

and define

$\Lambda:=\Bigl{\\{}{\alpha}\in A:\ \|{\alpha}\|\leq n^{1/d}\ \text{\rm or}\ \
|S_{\alpha}(\sigma_{h}f)|\geq h^{r}\Bigr{\\}}.$

Then $\\#\Lambda\leq cn$, and the function

$\mathcal{G}_{n}f(x):=\sum_{{\alpha}\in\Lambda}(S_{\alpha}(\sigma_{h}f))\psi_{\alpha}(x/h)$

satisfies

(4.3) $\|f-\mathcal{G}_{n}f\|_{\infty}\leq
Cn^{-\frac{r}{d}\frac{a+d}{a+d+r}}\Bigl{[}C_{1}+\|\nabla^{r}f\|_{\infty}+\|\nabla^{\ell}f\|_{\infty}\Bigr{]}.$

We note that for compactly supported functions $f$, (4.2) is true for any
positive number $a$, with the constant $C_{1}$ depending on the diameter of
the support of $f$, and (4.3) then provides the optimal approximation order.

###### Proof.

Using (3.1), we have that

$\displaystyle h^{d}\sum_{\|{\alpha}\|\geq
n^{1/d}}|S_{\alpha}(\sigma_{h}f)|^{p}$ $\displaystyle\leq
C\sum_{\|{\alpha}\|\geq n^{1/d}}\int_{B_{h}({\alpha}h)}|f(y)|^{p}\,dy$
$\displaystyle\leq C\int_{\|y\|\geq n^{1/d}h/2}|f(y)|^{p}dy\leq
CC_{1}^{p}(n^{1/d}h)^{-ap}.$

This means that there exist at most $cn$ points ${\alpha}$ in the set $A$ such
that $\|{\alpha}\|\geq n^{1/d}$ and

$|S_{\alpha}(\sigma_{h}f)|\geq
C^{1/p}C_{1}n^{-\frac{a}{d}-\frac{1}{p}}h^{-a-\frac{d}{p}}.$

Since

$\\#\Bigl{\\{}{\alpha}\in A:\ \|{\alpha}\|\leq n^{1/d}\Bigr{\\}}\leq cn,$

it follows that $\\#\Lambda\leq c^{\prime}n$, and that

(4.4) $|S_{\alpha}(\sigma_{h}f)|\leq
C^{1/p}C_{1}n^{-\frac{a}{d}-\frac{1}{p}}h^{-a-\frac{d}{p}}\leq CC_{1}h^{r},\ \
\forall{\alpha}\in A\setminus\Lambda.$

Thus,

$\displaystyle\|f-\mathcal{G}_{n}f\|_{\infty}$
$\displaystyle\leq\|f-Q_{h}f\|_{\infty}+\|Q_{h}f-\mathcal{G}_{n}f\|_{\infty}$
$\displaystyle\leq C_{f}h^{r}|\log h|+C\sup_{{\alpha}\in
A\setminus\Lambda}|S_{\alpha}(\sigma_{h}f)|$ $\displaystyle\leq
C_{f}h^{r}|\log h|+CC_{1}h^{r}\leq
C_{f}^{\prime}n^{-\frac{r}{d}\frac{a+d}{a+d+r}}.$

∎

##  5\. Compression in $L^{p}$ with $1<p<\infty$

The main purpose in this section is to study compression with radial basis
functions for smooth functions in $L^{p}$. We will follow closely the argument
of DeVore and Ron [15] . The pointwise error estimates (i.e., Corollary 4.2 in
[9] and Corollary 3.5) will play crucial roles in our proof.

We begin with studying decompositions of locally integrable functions by
wavelets (see the aforementioned book by Daubechies). Later-on we shall use
these remarks for studying radial basis functions and quasi-interpolants.

###  5.1. Wavelet decomposition and the Triebel-Lizorkin spaces

Most materials in this subsection can be found in [23] and [15]. Let
$\mathcal{D}_{j}$ denote the set of dyadic cubes of side length $2^{-j}$, and
let $\mathcal{D}=\bigcup_{j\in{\mathbb{Z}}}\mathcal{D}_{j}$. Thus, each
$I\in\mathcal{D}_{j}$ can be written in the form

$I=2^{-j}(k+[0,1)^{d})\ \ \text{for some $k\in{\mathbb{Z}}^{d}$}.$

Write $\ell(I)=2^{-j}$ for each $I\in\mathcal{D}_{j}$. Let

$E:=\\{1,2,\ldots,2^{d}-1\\},\ \ \mathcal{V}=\mathcal{D}\times E.$

For each $v=(I_{v},e_{v})\in\mathcal{V}$ with $I_{v}\in\mathcal{D}$ and
$e_{v}\in E$, we denote

$\ell(v):=\ell(I_{v}),\ \ |v|=\ell(v)^{d}=|I_{v}|.$

Let $\\{w_{v}\\}_{v\in\mathcal{V}}$ be an orthogonal wavelet basis for
$L_{2}({\mathbb{R}}^{d})$ with the following properties:

  1. (i)

Each wavelet $w_{v}$ with $I_{v}:=2^{j}(k+[0,1]^{d})\in\mathcal{D}$, is
supported in the cube

$\bar{I}_{v}=2^{j}(k+A_{0}[0,1]^{d}),$

with $A_{0}$ being some fixed absolute constant.

  2. (ii)

The wavelets $w_{v}$ are $m_{2}$-times differentiable, and have $m_{2}$
vanishing moments for a sufficiently large positive integer $m_{2}$. Moreover,

(5.1) $|D^{\alpha}w_{v}(x)|\leq
C\ell(I_{v})^{-|{\alpha}|}\raisebox{2.0pt}{$\chi$}_{\bar{I}_{v}}(x),\ \
|{\alpha}|\leq m_{2},\ \ x\in{\mathbb{R}}^{d},$

and

$\|w_{v}\|_{p}\sim|I_{v}|^{\frac{1}{p}},\ \ \ \forall v\in\mathcal{V},\ \
1\leq p\leq\infty.$

  3. (iii)

Each locally integrable function $f$ defined on ${\mathbb{R}}^{d}$ has a
wavelet decomposition

$f=\sum_{v\in\mathcal{V}}f_{v}w_{v},\ \
f_{v}:=|I_{v}|^{-1}{\langle}f,w_{v}{\rangle},$

and many classical function spaces on ${\mathbb{R}}^{d}$ can be defined or
characterized equivalently in terms of the coefficients of these wavelet
decompositions. For example, given $s>0$ and $0<p,q<\infty$, the Triebel-
Lizorkin spaces $F_{p,q}^{s}({\mathbb{R}}^{d})$ can be equivalently defined to
be the space of all functions $f$ on ${\mathbb{R}}^{d}$ with

$|f|_{F_{p,q}^{s}}:=\|\Delta_{s,q}f\|_{L^{p}({\mathbb{R}}^{d})}<\infty,$

where

$\Delta_{s,q}f(x):=\Bigl{(}\sum_{v\in\mathcal{V}}\ell(v)^{-qs}|f_{v}|^{q}\raisebox{2.0pt}{$\chi$}_{\bar{I}_{v}}(x)\Bigr{)}^{1/q},$

The quasi-norm in $F_{p,q}^{s}({\mathbb{R}}^{d})$ is defined by

$\|f\|_{F_{p,q}^{s}({\mathbb{R}}^{d})}:=\|f\|_{L^{p}({\mathbb{R}}^{d})}+|f|_{F_{p,q}^{s}({\mathbb{R}}^{d})}.$

The definition of the Triebel-Lizorkin spaces $F_{p,q}^{s}$ extends naturally
to the $q=\infty$ case, with $\Delta_{s,\infty}f$ defined by

$\Delta_{s,\infty}f(x):=\sup_{v\in\mathcal{V}}\ell(v)^{-s}|f_{v}|\raisebox{2.0pt}{$\chi$}_{\bar{I}_{v}}(x).$

###  5.2. Nonlinear approximation

Let $\Sigma_{N}=\Sigma_{N}(\varphi)$ denote the set of all functions $S$ on
${\mathbb{R}}^{d}$ for which there exists a subset $\Lambda\subset A$ of
cardinality $\\#\Lambda=N$ such that

$S=\sum_{\alpha\in\Lambda}a_{\alpha}\psi_{\alpha}(h^{-1}\cdot)\ \ \ \text{for
some $h>0$ and $a_{\alpha}\in{\mathbb{R}}$},$

with the quasi-interpolants as above. Define

$\sigma_{N}(f)_{p}:=\inf_{S\in\Sigma_{N}}\|f-S\|_{L^{p}({\mathbb{R}}^{d})}.$

For the sake of simplicity, we will assume that $\ell+1<m_{2}$ in this section
so that there is no log term in (3.7).

######  Theorem 5.1.

Let $1<p<\infty$ be given, and let $f\in F_{\tau,q}^{s}$, with
$0<s\leq\ell+1$, $\tau:=(1/p+s/d)^{-1}$ and $q=(1+s/d)^{-1}$. Then

$\hat{\sigma}_{N}(f)_{p}\leq CN^{-s/d}\|f\|_{F_{\tau,q}^{s}}.$

The proof of Theorem 5.1 follows along the same line as that of Theorem 6.2 of
[15]. It relies on a series of lemmas with which we will begin.

######  Lemma 5.2.

For each $v\in\mathcal{V}$ and $N_{v}\in{\mathbb{Z}}_{+}$, there exists a
positive number $h\sim\ell(I_{v})(N_{v}+1)^{-1/d}$ such that

$S_{v,N_{v}}:=\widetilde{Q}_{h}w_{v}\in\Sigma_{N_{v}},$

and

(5.2) $\displaystyle R_{v}(x):$ $\displaystyle=|w_{v}(x)-S_{v,N_{v}}(x)|$
(5.3) $\displaystyle\leq
C(N_{v}+1)^{-(\ell+1)/d}\Bigl{[}M(\raisebox{2.0pt}{$\chi$}_{\bar{I_{v}}})(x)\Bigr{]}^{1+\frac{m_{2}}{d}},\
\ x\in{\mathbb{R}}^{d}.$

###### Proof.

By (5.1), the estimate holds trivially if $N_{v}=0$. For the rest of the
proof, we assume that $N_{v}\geq 1$. Let $h$ be a positive number to be
specified in a moment, and let

$\Lambda:=\Bigl{\\{}{\alpha}\in A:\ \ \|{\alpha}h-c_{v}\|\leq
CA_{0}\ell(I_{v})\Bigr{\\}},$

where $c_{v}$ denotes the centre of the dyadic cube $I_{v}$, and $C$ is a
large positive constant depending only on $d$. Then

$\\#\Lambda\leq C\Bigl{(}1+\frac{\ell(I_{v})}{h}\Bigr{)}^{d}.$

Thus, we may choose $h\sim\ell(I_{v})N_{v}^{-1/d}$ so that $\\#\Lambda\leq
N_{v}$ and

$\bigcup_{x\in\bar{I_{v}}}B_{4h}(x)\subset B_{CA_{0}\ell(I_{v})}(c_{v}).$

Since $w_{v}$ is supported in $\bar{I}_{v}$, it follows that $w_{v}$ is
identically zero on $\bigcup_{{\alpha}\in
A\setminus\Lambda}B_{2h}({\alpha}h)$. This in turn implies that

$\ell_{{\alpha}}[(w_{v})_{h}]=S_{0}[w_{v}(h\cdot+h{\alpha})]=0,\ \ \ \
\forall{\alpha}\in A\setminus\Lambda,$

and hence

$Q_{h}w_{v}=\sum_{{\alpha}\in\Lambda}\ell_{{\alpha}}[(w_{v})_{h}]\psi_{\alpha}(h^{-1}\cdot)\in\Sigma_{N_{v}}.$

Therefore, on one hand, using (3.7) and (5.1),

$\displaystyle|w_{v}(x)-\widetilde{Q}_{h}w_{v}(x)|\leq
Ch^{\ell+1}M(\|\nabla^{\ell+1}w_{v}\|)(x)$ (5.4) $\displaystyle\leq
C\Biggl{(}\frac{h}{\ell(I_{v})}\Biggr{)}^{\ell+1}\leq CN_{v}^{-(\ell+1)/d},\ \
x\in{\mathbb{R}}^{d}.$

On the other hand, if $\|x-c_{v}\|\geq 2CA_{0}\ell(I_{v})$, then $w_{v}(x)=0$,
and

$\displaystyle|w_{v}(x)-\widetilde{Q}_{h}w_{v}(x)|$ $\displaystyle\leq
C\sum_{{\alpha}\in\Lambda}|\ell_{{\alpha}}[(w_{v})_{h}]|\Bigl{(}1+h^{-1}\|x-{\alpha}h\|\Bigr{)}^{-m_{2}-d}$
$\displaystyle\leq
C\sum_{{\alpha}\in\Lambda}\Bigl{(}h^{-1}\|x-c_{v}\|\Bigr{)}^{-m_{2}-d}\frac{1}{|B_{h}({\alpha}h)|}\int_{B_{h}({\alpha}h)}|w_{v}(z)|\,dz$
$\displaystyle\leq
C\Biggl{(}\frac{\|x-c_{v}\|}{\ell(I_{v})}\Biggr{)}^{-m_{2}-d}\Bigl{(}\frac{\ell(I_{v})}{h}\Bigr{)}^{-m_{2}-d}\\#\Lambda$
(5.5) $\displaystyle\leq
C\Biggl{(}1+\frac{\|x-c_{v}\|}{\ell(I_{v})}\Biggr{)}^{-m_{2}-d}N_{v}^{-m_{2}/d}.$

Therefore, combining (5.4) with (5.5), and in view of the fact that
$m_{2}\geq\ell+1$, we deduce that

(5.6) $|w_{v}(x)-\widetilde{Q}_{h}w_{v}(x)|\leq
CN_{v}^{-\frac{\ell+1}{d}}\Bigl{(}1+\frac{\|x-c_{v}\|}{\ell(I_{v})}\Bigr{)}^{-m_{2}-d},\
\ x\in{\mathbb{R}}^{d}.$

Finally, to complete the proof, we just need to observe that

$M(\raisebox{2.0pt}{$\chi$}_{I_{v}})(x)\geq
C_{0}\Biggl{(}1+\frac{\|x-c_{v}\|}{\ell(I_{v})}\Biggr{)}^{-d},\ \ \forall
x\in{\mathbb{R}}^{d}.$

∎

######  Lemma 5.3.

Let $R_{v}(x)$ be as defined in (5.2). Then for $1<p<\infty$,

$\Bigl{\|}\sum_{v\in\mathcal{V}}|f_{v}|R_{v}\Bigr{\|}_{L^{p}({\mathbb{R}}^{d})}\leq
C\Bigl{\|}\sum_{v\in\mathcal{V}}(1+N_{v})^{-(\ell+1)/d}|f_{v}|\raisebox{2.0pt}{$\chi$}_{\bar{I_{v}}}\Bigr{\|}_{L^{p}({\mathbb{R}}^{d})}.$

###### Proof.

Using (5.3), and setting $q=1+\frac{m_{2}}{d}$, we have

$\displaystyle\Bigl{\|}\sum_{v\in\mathcal{V}}|f_{v}|R_{v}\Bigr{\|}_{L^{p}({\mathbb{R}}^{d})}$
$\displaystyle\leq
C\Bigl{\|}\Bigl{(}\sum_{v\in\mathcal{V}}|f_{v}|(N_{v}+1)^{-\frac{\ell+1}{d}}\Bigl{[}M\raisebox{2.0pt}{$\chi$}_{\bar{I_{v}}}(x)\Bigr{]}^{q}\Bigr{)}^{1/q}\Bigr{\|}^{q}_{L^{qp}({\mathbb{R}}^{d})},$

which, using the Fefferman-Stein inequality (see [26, p. 55, 1.3.1], is
estimated by

$\displaystyle
C\Bigl{\|}\sum_{v\in\mathcal{V}}|f_{v}|(N_{v}+1)^{-\frac{\ell+1}{d}}\raisebox{2.0pt}{$\chi$}_{\bar{I_{v}}}\Bigr{\|}_{L^{p}({\mathbb{R}}^{d})}.$

∎

######  Lemma 5.4.

[15, Lemma 6.3] Let $\\{z_{j}\\}_{j=-\infty}^{\infty}$ be a sequence of
nonnegative numbers with $Z:=\sum_{j\in{\mathbb{Z}}}z_{j}<\infty$. Then for
any $\varepsilon>0$,

$\sum_{j\in{\mathbb{Z}}}z_{j}\Biggl{(}\sum_{k=-\infty}^{j}z_{k}\Biggr{)}^{\varepsilon-1}\leq
C_{\varepsilon}Z^{\varepsilon},$

where it is understood that $0\cdot\infty=0$.

We are now in a position to prove Theorem 5.1.

Proof of Theorem 5.1. The proof of Theorem 5.1 follows along the same line as
that of Theorem 6.2 of [15]. Fix a nonzero function $f\in F_{\tau,q}^{s}$, and
a positive integer $N$. Given $x\in{\mathbb{R}}^{d}$, let $\mathcal{V}_{x}$
denote the set of all $v\in\mathcal{V}$ such that
$\raisebox{2.0pt}{$\chi$}_{I_{v}}(x)\neq 0$. Define for each
$x\in{\mathbb{R}}^{d}$ and each $v^{\prime}\in\mathcal{V}$,

$M_{q,v^{\prime}}(x):=\Biggl{(}\sum_{v\in\mathcal{V}_{x}:v\geq
v^{\prime}}|I_{v}|^{-qs/d}|f_{v}|^{q}\Biggr{)}^{1/q},$

where we say $v\geq v^{\prime}$ if either $|I_{v}|>|I_{v^{\prime}}|$ or
$|I_{v}|=|I_{v^{\prime}}|$ and $e_{v}\geq e_{v^{\prime}}$. Notice that if
$x\in I_{v^{\prime}}$, then

(5.7) $\displaystyle
M_{q,v^{\prime}}(x)^{q}=\Biggl{(}\sum_{v\in\mathcal{V}:I_{v}\supsetneqq
I_{v^{\prime}}}+\sum_{v\in\mathcal{V}:I_{v}=I_{v^{\prime}},e_{v}\geq
e_{v^{\prime}}}\Biggr{)}|I_{v}|^{-qs/d}|f_{v}|^{q}.$

Thus, $M_{q,v^{\prime}}(x)$ is actually a constant on $I_{v^{\prime}}$, which
we denote by $M_{q,v^{\prime}}$. Thus,

$M_{q,v^{\prime}}:=M_{q,v^{\prime}}(x)\leq\Delta_{s,q}(f)(x),\ \ x\in
I_{v^{\prime}}.$

Let

(5.8) $a_{v}=a|I_{v}|^{q}|f_{v}|^{q}M_{q,v}^{\tau-q},\ \ v\in\mathcal{V},$

where $a$ will be specified in a moment. Since $\tau-q>0$ and $q=1-qs/d$, it
follows that

$\displaystyle
a_{v}=\Bigl{\|}a|I_{v}|^{-qs/d}|f_{v}|^{q}M_{q,v}^{\tau-q}\raisebox{2.0pt}{$\chi$}_{I_{v}}\Bigr{\|}_{1}\leq\Bigl{\|}a|I_{v}|^{-qs/d}|f_{v}|^{q}(\Delta_{s,q}f)^{\tau-q}\raisebox{2.0pt}{$\chi$}_{I_{v}}\Bigr{\|}_{1}.$

Thus,

$\displaystyle\sum_{v\in\mathcal{V}}a_{v}$ $\displaystyle\leq
a\Bigl{\|}\Delta_{s,q}(f)^{\tau-q}\sum_{v\in\mathcal{V}}|I_{v}|^{-qs/d}|f_{v}|^{q}\raisebox{2.0pt}{$\chi$}_{I_{v}}\Bigr{\|}_{1}$
$\displaystyle\leq
a\|\Delta_{s,q}(f)^{\tau}\|_{1}=a\|\Delta_{s,q}(f)\|_{\tau}^{\tau}=a\|f\|_{F_{\tau,q}^{s}}^{\tau}.$

Now choose $a$ so that $a\|f\|_{F_{\tau,q}^{s}}^{\tau}=N$, and let $N_{v}$ be
equal to $\lceil a_{v}\rceil$, the greatest integer $\leq a_{v}$. Then
$\sum_{v\in\mathcal{V}}N_{v}\leq N$. Now for each $v\in\mathcal{V}$, let
$S_{v,N_{v}}\in\Sigma_{N_{v}}$ be as in Lemma 5.2, and let

$S:=\sum_{v\in\mathcal{V}}S_{v,N_{v}}f_{v}.$

Then $S\in\Sigma_{N}$, and using Lemma 5.3, we have that

$\displaystyle\|f-S\|_{p}$
$\displaystyle=\Bigl{\|}\sum_{v\in\mathcal{V}}f_{v}w_{v}-\sum_{v\in\mathcal{V}}f_{v}s_{v,N_{v}}\Bigr{\|}_{p}\leq\Bigl{\|}\sum_{v\in\mathcal{V}}|f_{v}||w_{v}-S_{v,N_{v}}|\Bigr{\|}_{p}$
$\displaystyle\leq
C\Bigl{\|}\sum_{v\in\mathcal{V}}(1+a_{v})^{-(\ell+1)/d}|f_{v}|\raisebox{2.0pt}{$\chi$}_{\bar{I_{v}}}\Bigr{\|}_{p}\leq
C\Bigl{\|}\sum_{v\in\mathcal{V}}(1+a_{v})^{-s/d}|f_{v}|\raisebox{2.0pt}{$\chi$}_{\bar{I_{v}}}\Bigr{\|}_{p}$
$\displaystyle=:C\|\sum_{v\in\mathcal{V}}E_{v}\|_{p},$

where

$E_{v}(x):=(1+a_{v})^{-s/d}|f_{v}|\raisebox{2.0pt}{$\chi$}_{\bar{I_{v}}}(x).$

If $a_{v}>0$, then using (5.8), for $x\in\bar{I_{v}}$,

$\displaystyle E_{v}(x)$ $\displaystyle\leq
a_{v}^{-s/d}|f_{v}|\raisebox{2.0pt}{$\chi$}_{\bar{I_{v}}}(x)=a^{-s/d}|I_{v}|^{-qs/d}|f_{v}|^{1-qs/d}M_{q,v}^{\frac{\tau}{p}-q}$
(5.9)
$\displaystyle=a^{-s/d}|I_{v}|^{-qs/d}|f_{v}|^{q}\Biggl{(}\sum_{v^{\prime}\in\mathcal{V}:v^{\prime}\geq
v}|I_{v^{\prime}}|^{-qs/d}|f_{v^{\prime}}|^{q}\Biggr{)}^{\frac{\tau}{pq}-1}.$

On the other hand, if $a_{v}=0$, then by (5.7) and (5.8), we have that
$f_{v}=0$, $E_{v}(x)=0$, and (5.9) remains true under the agreement that
$0\cdot\infty=0$. Thus, using Lemma 5.4, it follows that

$\displaystyle\sum_{v\in\mathcal{V}}E_{v}(x)$ $\displaystyle\leq
Ca^{-s/d}\sum_{v\in\mathcal{V}}|I_{v}|^{-qs/d}|f_{v}|^{q}\raisebox{2.0pt}{$\chi$}_{\bar{I_{v}}}(x)\Bigl{(}\sum_{v^{\prime}\in\mathcal{V}:v^{\prime}\geq
v}|I_{v^{\prime}}|^{-qs/d}|f_{v^{\prime}}|^{q}\raisebox{2.0pt}{$\chi$}_{\bar{I_{v^{\prime}}}}(x)\Bigr{)}^{\frac{\tau}{pq}-1}$
$\displaystyle\leq Ca^{-s/d}(\Delta_{s,q}(f)(x))^{\tau/p}.$

Recalling that $a=N\|f\|_{F_{\tau,q}^{s}}^{-\tau}$ and
$\frac{\tau}{p}+\frac{\tau s}{d}=1$, we conclude that

$\Bigl{\|}\sum_{v\in\mathcal{V}}E_{v}\Bigr{\|}_{p}\leq
Ca^{-s/d}\|\Delta_{s,q}(f)\|_{\tau}^{\tau/p}=CN^{-s/d}\|f\|_{F_{\tau,q}^{s}}.$

This completes the proof. $\Box$

## References

  * [1]
  * [2] C. de Boor, R. DeVore, A. Ron, Approximation from shift-invariant subspaces of $L^{2}({\mathbb{R}}^{d})$, Trans. AMS 341 (1994), 787–806.
  * [3] C. de Boor, K. Höllig and S. Riemenschneider, Box Splines, Springer, New York, 1993.
  * [4] S. C. Brenner and L.R. Scott, The Mathematical Theory of Finite Element Methods, Springer, New York, 1994.
  * [5] R. A. Brownlee and W.A. Light, Approximation orders for interpolation by surface splines to rough functions, IMA J. Numer. Anal. 24(2004), 179–192.
  * [6] M. D. Buhmann, Radial basis functions: theory and implementations, Cambridge Univ. Press, Cambridge, 2003.
  * [7] M. D. Buhmann, Multiquadric pre-wavelets on non-equally spaced knots in one dimension, Math. Comp. 64 (1995), 1611–1625.
  * [8] M. D. Buhmann, On quasi-interpolation with radial basis functions, J. Approx. Th. 72 (1993), 103–130.
  * [9] M. D. Buhmann and F. Dai, Pointwise Approximation with Quasi-Interpolation by Radial Basis Functions, J. Approx. Th. 192 (2015), 156–192.
  * [10] M. D. Buhmann, N. Dyn, D. Levin, On quasi-interpolation by radial basis functions with scattered centres, Constr. Approx. 11 (1995), no. 2, 239–254.
  * [11] M. D. Buhmann and C. A. Micchelli, Spline prewavelets on non-uniform knots, Numerische Mathematik 61 (1992), 455-474.
  * [12] M. D. Buhmann, E. Porcu, D. Daley and M. Bevilacqua, “Radial basis functions for multivariate geostatistics”, Stochastic Environmental Research and Risk Assessment 27 (4)(2013), 909–922.
  * [13] W. Cheney and W. Light, A course in approximation theory, Graduate Studies in Mathematics, 101. American Mathematical Society, Providence, RI, 2009.
  * [14] I. Daubechies, Ten Lectures on Wavelets, SIAM, Philadelphia, 1992.
  * [15] R. A. DeVore and A. Ron, Approximation using scattered shifts of a multivariate function, Trans. Amer. Math. Soc. 362 (2010), no. 12, 6205–6229.
  * [16] J. Duchon, Interpolation des fonctions de deux variables suivant le principe de la flexion des plaques minces, RAIRO 10 (1976), 5–12.
  * [17] R. Franke, Scattered data interpolation: Test of some methods, Math. Comp. 38 (1982), 181–200.
  * [18] T. Hangelbroek and A. Ron, Nonlinear approximation using Gaussian kernels, J. Funct. Anal. 259 (2010), no. 1, 203–219.
  * [19] T. Hangelbroek, W. Madych, F. Narcowich, J. D. Ward, Cardinal interpolation with Gaussian kernels, J. Fourier Anal. Appl. 18 (2012), no. 1, 67–86.
  * [20] Rongqing Jia and Junjiang Lei, Approximation by multi-integer translates of functions having global support, J. Approx. Theory 72 (1993), no. 1, 2–23.
  * [21] M. J. Johnson, Z. W. Shen, and Yuhong Xu, Scattered data reconstruction by regularization in B-spline and associated wavelet spaces, J. Approx. Theory 159 (2009), no. 2, 197–223.
  * [22] Junjiang Lei, Rong-Qing Jia and E.W. Cheney, Approximation from shift-invariant spaces by integral operators, SIAM J. Math. Anal. 28
  * [23] Yves Meyer, Ondelettes et opérateurs. I, Actualités Mathématiques. [Current Mathematical Topics], Hermann, Paris, 1990 (French). Ondelettes. [Wavelets].
  * [24] M. J. Johnson, The $L_{p}$-approximation order of surface spline interpolation for $1\leq p\leq 2$, Constr. Approx. 20 (2004), no. 2, 303–324.
  * [25] R. Schaback, and Z. Wu, Construction techniques for highly accurate quasi-interpolation operators, J. Approx. Theory 91 (1997), no. 3, 320–331.
  * [26] E. M. Stein, Harmonic analysis: real-variable methods, orthogonality, and oscillatory integrals. Princeton Mathematical Series, 43. Princeton University Press, Princeton, NJ, 1993\.
  * [27] V. Temlyakov, Greedy approximation. Cambridge Monographs on Applied and Computational Mathematics, 20. Cambridge University Press, Cambridge, 2011.
  * [28] H. Wendland, Scattered data approximation, Cambridge University Press, 2005.
  * [29] Z. Wu, and J. P. Liu, Generalized Strang-Fix condition for scattered data quasi-interpolation, Adv. Comput. Math.23 (2005), no. 1-2, 201–214.
  * [30] Z. Wu, and Z. Xiong, Multivariate quasi-interpolation in $L^{p}({\mathbb{R}}^{d})$ with radial basis functions for scattered data, Int. J. Comput. Math. 87 (2010), no. 1-3, 583–590.