# Google COVID-19 Vaccination Search Insights:
Anonymization Process Description (version 1.0)

Shailesh Bavadekar<EMAIL_ADDRESS>Adam Boulanger
<EMAIL_ADDRESS>John Davis  covid-19-search-
<EMAIL_ADDRESS>Damien Desfontaines  covid-19-search-trends-
<EMAIL_ADDRESS>Evgeniy Gabrilovich  covid-19-search-trends-
<EMAIL_ADDRESS>Krishna Gadepalli  covid-19-search-trends-
<EMAIL_ADDRESS>Badih Ghazi<EMAIL_ADDRESS>Tague Griffith<EMAIL_ADDRESS>Jai Gupta
<EMAIL_ADDRESS>Chaitanya Kamath  covid-19-search-
<EMAIL_ADDRESS>Dennis Kraft  covid-19-search-trends-
<EMAIL_ADDRESS>Ravi Kumar<EMAIL_ADDRESS>Akim Kumok<EMAIL_ADDRESS>Yael Mayer
<EMAIL_ADDRESS>Pasin Manurangsi  covid-19-search-
<EMAIL_ADDRESS>Arti Patankar  covid-19-search-trends-
<EMAIL_ADDRESS>Irippuge Milinda Perera  covid-19-search-trends-
<EMAIL_ADDRESS>Chris Scott<EMAIL_ADDRESS>Tomer Shekel<EMAIL_ADDRESS>Benjamin Miller
<EMAIL_ADDRESS>Karen Smith  covid-19-search-
<EMAIL_ADDRESS>Charlotte Stanton  covid-19-search-trends-
<EMAIL_ADDRESS>Mimi Sun<EMAIL_ADDRESS>Mark Young<EMAIL_ADDRESS>Gregory Wellenius
<EMAIL_ADDRESS>
(July 1, 2021)

###### Abstract

This report describes the aggregation and anonymization process applied to the
COVID-19 Vaccination Search Insights [1], a publicly available dataset showing
aggregated and anonymized trends in Google searches related to COVID-19
vaccination. The applied anonymization techniques protect every user’s daily
search activity related to COVID-19 vaccinations with
$(\varepsilon,\delta)$-differential privacy for $\varepsilon=2.19$ and
$\delta=10^{-5}$.

##  1 Introduction

The COVID-19 Vaccination Search Insights is a publicly available dashboard [1]
and dataset [2] that shows aggregated, anonymized trends in Google searches
related to COVID-19 Vaccination. The data provides a weekly time series for
each region showing the relative volume of searches across 3 categories:

  * •

COVID-19 Vaccination: All searches related to COVID-19 vaccination, indicating
overall search interest in the topic.

  * •

Vaccination Intent: Searches related to eligibility, availability, and
accessibility of vaccines.

  * •

Safety and Side Effects: Searches related to the safety and side effects of
the vaccines.

We are making this data available because we have heard from public health
organizations and researchers that they want access to localized and timely
data about what information their communities are seeking, so they can better
understand the vaccination needs of their communities and tailor their
communication to people not yet vaccinated.

To ensure strict privacy standards, all published data is aggregated and
anonymized, protecting each user’s search activity on a given day using a
differentially private mechanism. No personal data is included in the dataset.

The Vaccination Search Insights data reflect the (normalized) volume of Google
searches that may be associated with a particular COVID-19 vaccination search
topic. For this purpose, we count the weekly number of searches relating to
that topic within a given geographic region, and normalize this number based
on the total search activity in that region. The resulting data is a weekly
series showing the relative frequency of searches for that particular topic in
a particular region. The data covers the recent period and we plan to
gradually expand its range as part of regular updates.

Similar to the Google COVID-19 Community Mobility Reports [3] and Symptom
Search Dataset [4], and as explained in greater technical detail below, the
anonymization process of the Vaccination Search Insights data is based on
differential privacy [5], which is a well established approach for producing
data that provides formal privacy guarantees. For this purpose, we
intentionally perturb our data by adding random noise, and then drop data
points that are deemed to be unreliable. The Vaccination Search Insights are
designed to maintain the privacy of our users while releasing aggregated and
anonymized data that is as accurate and useful as possible.

The remainder of this report is structured as follows. First, we introduce
some basic concepts and terminology of the COVID-19 Vaccination Search
Insights. We then explain how differential privacy is used to produce
anonymized aggregates. Finally, we elaborate on how the published data is
built from the anonymized aggregates.

##  2 Definitions

The following definitions explain some common terms and concepts that are used
throughout this report.

  * •

User: A user who issued a search query on Google Search.

  * •

Search Categories: We classify Google search queries according to the
following 4 categories:

    * $\bullet$

[A0] Any: Contains all search queries.

    * $\bullet$

[A1] Vaccination Intent: Contains searches related to eligibility,
availability, and accessibility of COVID-19 vaccines.

    * $\bullet$

[A2] Safety and Side Effects: Contains searches related to the safety and side
effects of COVID-19 vaccines.

    * $\bullet$

[A3] Other: Contains all searches related to COVID-19 vaccination that are not
classified as Vaccination Intent or Safety and Side Effects.111The COVID-19
Vaccination category, which indicates the overall interest in the topic, is
derived from the union of the Vaccination Intent, Safety and Side Effects and
Other categories as described in the Post-processing section.

The classification is done via a machine learning model that was trained in a
semi-supervised fashion.

  * •

Geographic Regions: Search queries are aggregated based on the geographic
region where they are issued. We provide data for four geographic granularity
levels: Country222Country level data is not generated directly, instead we
aggregate it from anonymized State level data. Thus, we avoid spending privacy
budget at the Country level. and three levels of subdivision within each
country. In the US, these three levels are State, County, and Postal Code,
which we use as our running example in the remainder of this paper. All
reported geographic regions have an area of at least $3\textrm{km}^{2}$.

  * •

County and Postal Code Types: We distinguish between three types of counties
based on the size of their population, relying on the 2018 US Census Bureau
data:

    * $\bullet$

Small: Counties with a population of fewer than 100,000.

    * $\bullet$

Medium: Counties with a population between 100,000 and 500,000.

    * $\bullet$

Large: Counties with a population of greater than 500,000.

Moreover, we label postal codes with the same type, i.e., Small, Medium, and
Large, as the county they are part of.333If a postal code region stretches
across multiple counties, we match its type with the county with which it
shares most of its addresses. Note that this classification only depends on
the population size of the county, not on the population size of the postal
code.

  * •

Differential Privacy: Let $A$ be a randomized algorithm that takes a dataset
as input. We say that $A$ is $(\varepsilon,\delta)$-differentially private if
for any pair of neighboring datasets $D_{1}$ and $D_{2}$ and for all sets $S$
of the possible outputs of $A$, it holds that:

$\textrm{Pr}[A(D_{1})\in
S]\leq\textrm{exp}(\varepsilon)\cdot\textrm{Pr}[A(D_{2})\in S]+\delta.$

In the context of this report, we consider $D_{1}$ and $D_{2}$ neighboring
datasets if $D_{1}$ can be obtained from $D_{2}$ by adding or removing a
single user’s search activity on a given day.

##  3 Anonymization Process

The COVID-19 Vaccination Search Insights are based on anonymized search query
counts. The counts are grouped by the week in which a query was made, the
region from which it was issued and its category. This means that each count
can be uniquely associated with a $<$week, region, category$>$ triple.

As part of the anonymization process, we limit each user’s daily contribution
to the search query counts and add appropriately scaled Gaussian noise. The
resulting metrics protect each user’s daily search activity with
$(\varepsilon,\delta)$-differential privacy, where $\varepsilon=2.19$ and
$\delta=10^{-5}$.

###  3.1 Contribution Bounding and Constraints

A user’s contributions to the vaccination search counts are subject to the
following constraints:

  * •

[X1] Cross-Count Bounding: A user can contribute to at most 1 count per day,
geographic level, and category.

  * •

[X2] Per-Count Bounding: A user can increment each count by at most 1 per day.

  * •

[X3] Small Postal Code Constraint: We do not report on Postal Code counts of
type Small.444The motivation behind this constraint is to reduce the relative
error differential privacy introduces to County level counts. Using population
size as a proxy for the relative error, the omitted counts free up privacy
budget at Postal Code level that we then use to reduce the noise added at the
County level.

  * •

[X4] County / Postal Code Synchronization: A user cannot contribute to counts
of different County and Postal Code types on the same day.555This constraint
is intended to keep our privacy budget accounting consistent, which is
necessary because we use different noise parameterizations for different
County and Postal Code types.

Similar to the process described by Wilson et al. [6], we arbitrarily drop
search queries that violate these constraints. Note that none of these
contribution bounds apply to more than a single day, so we can consider each
day’s data separately when enforcing them.

To give an example, imagine a user who makes the following searches during the
10th week of 2021:

  * •

Search 1: Unrelated to COVID-19 Vaccinations, made on March 9th, 2021 from
Postal Code 94103, San Francisco County, California.

  * •

Search 2: Related to the safety of COVID-19 Vaccinations, made on March 9th,
2021 from Postal Code 95023, San Benito County, California.

  * •

Search 3: Related to the eligibility of COVID-19 Vaccinations, made on March
11th, 2021 from Postal Code 95023, San Benito County, California.

Table 1 shows how the user’s searches are mapped to the counts. Note that the
resulting mapping violates some of the constraints we established earlier. To
resolve these conflicts, we go step by step through the constraints and drop
contributions. The choice of contributions we drop and the order in which we
drop them is arbitrary and only intended for illustration purposes. We begin
with March 9th, when the user made search queries 1 and 2:

Count ($<$week, category, region$>$) | Search | Geographic Level | Region Type
---|---|---|---
$<$10, Any, 94103$>$ | 1${}^{\textrm{X4}}$ | Postal Code | Large
$<$10, Any, 95023$>$ | 2${}^{\textrm{X1}}$, 3${}^{\textrm{X3}}$ | Postal Code | Small
$<$10, Any, San Francisco$>$ | 1${}^{\textrm{X4}}$ | County | Large
$<$10, Any, San Benito$>$ | 2${}^{\textrm{X1}}$, 3 | County | Small
$<$10, Any, California$>$ | 1, 2${}^{\textrm{X2}}$, 3 | State | N/A
$<$10, Safety and Side Effects, 95023$>$ | 2${}^{\textrm{X3}}$ | Postal Code | Small
$<$10, Safety and Side Effects, San Benito$>$ | 2 | County | Small
$<$10, Safety and Side Effects, California$>$ | 2 | State | N/A
$<$10, Vaccination Intent, 95023$>$ | 3${}^{\textrm{X3}}$ | Postal Code | Small
$<$10, Vaccination Intent, San Benito$>$ | 3 | County | Small
$<$10, Vaccination Intent, California$>$ | 3 | State | N/A
Table 1: Mapping of search queries 1, 2, and 3 to the respective counts before
constraint violations are resolved. Searches that will be dropped because of a
violation are marked with X1, X2, X3, or X4 according to the violated
constraint. Columns 3 and 4 provide auxiliary information for identifying
violations.

  * •

[X1] Cross-Count Bounding:

    * $\bullet$

Conflict: In the Any category at the Postal Code level the user contributed
from both 94103 and 95023. In the Any category at the County level, the user
contributed from both San Francisco and San Benito.

    * $\bullet$

Fix: Drop search 2 from $<$Week 10, Any, 95023$>$ and $<$Week 10, Any, San
Benito$>$.

  * •

[X2] Per-Count Bounding:

    * $\bullet$

Conflict: In the Any category, at State level, the user contributed two
searches.

    * $\bullet$

Fix: Drop search 2 from $<$Week 10, Any, California$>$.

  * •

[X3] Small Postal Code Constraint:

    * $\bullet$

Conflict: The user contributed to Postal Code 95023, which is Small.

    * $\bullet$

Fix: Drop search 2 from $<$Week 10, Safety and Side Effects, 95023$>$.

  * •

[X4] County / Postal Code Synchronization:

    * $\bullet$

Conflict: The user contributed to San Francisco and Postal Code 94103, which
are both Large, in the Any category. The user also contributed to San Benito,
which is Small, in the Safety and Side Effects category.

    * $\bullet$

Fix: Drop search 1 from $<$10, Any, 94103$>$ and $<$10, Any, San
Francisco$>$.666We already resolved a conflict between 94103 and 95023 in the
Any category in the cross-count bounding step by removing the contributions to
95023, but that still leaves a synchronization conflict between the remaining
Any values for 94103 and the Safety and Side Effects values for 95023. In
light of both conflicts, it might have been more efficient to solve both by
dropping the 94103 values. Our goal in this example is to demonstrate all
possible types of constraint violations. It does not directly correspond to
the way we resolve conflicts in practice.

Next, we consider March 11th when the user made search query 3. Because this
query was made on a different day, it does not conflict with 1 and 2.
Moreover, a single query in a day can only violate the Small Postal Code
Constraint. As it turns out, this constraint is indeed violated and therefore
we drop search 3 from $<$Week 10, Any, 95023$>$ and $<$Week 10, Vaccination
Intent, 95023$>$. Table 2 shows the resulting contributions, which now satisfy
all constraints:

Count ($<$week, category, region$>$) | Search | Geographic Level | Region Type
---|---|---|---
$<$10, Any, San Benito$>$ | 3 | County | Small
$<$10, Any, California$>$ | 1, 3 | State | N/A
$<$10, Safety and Side Effects, San Benito$>$ | 2 | County | Small
$<$10, Safety and Side Effects, California$>$ | 2 | State | N/A
$<$10, Vaccination Intent, San Benito$>$ | 3 | County | Small
$<$10, Vaccination Intent, California$>$ | 3 | State | N/A
Table 2: Mapping of search queries 1, 2, and 3 to the respective counts after
constraint violations are resolved. Columns 3 and 4 provide auxiliary
information for identifying violations.

###  3.2 Noise Addition and Privacy Budget Accounting

The standard deviation $\sigma$ of the Gaussian noise we add to each search
query count depends on the population size type and geographic level of the
region as well as the search category. Table 3 lists all standard deviation
values we use:

Population | Level | Search Category | Standard Deviation
---|---|---|---
Large | Postal Code | A0 | $\sigma=35.0$
Large | Postal Code | A1, A2, A3 | $\sigma=3.25$
Large | County | A0 | $\sigma=180.0$
Large | County | A1, A2, A3 | $\sigma=20.0$
Medium | Postal Code | A0 | $\sigma=40.0$
Medium | Postal Code | A1, A2, A3 | $\sigma=3.5$
Medium | County | A0 | $\sigma=100.0$
Medium | County | A1, A2, A3 | $\sigma=8.0$
Small | County | A0 | $\sigma=28.0$
Small | County | A1, A2, A3 | $\sigma=3.21$
N/A | State | A0 | $\sigma=450.0$
N/A | State | A1, A2, A3 | $\sigma=35.0$
Table 3: Standard deviation of the Gaussian noise added to the search query
counts.

To establish the total $\varepsilon$ and $\delta$ provided by the Gaussian
noise, we consider 3 cases based on the difference between the neighbouring
data sets $D_{1}$ and $D_{2}$ from the definition of
$(\varepsilon,\delta)$-differentially privacy (i.e. the contributions that are
in $D_{1}$ but not $D_{2}$ or vice versa):

  * •

Case 1: The differing contributions at County and Postal Code level are from
Large regions.

  * •

Case 2: The differing contributions at County and Postal Code level are from
Medium regions.

  * •

Case 3: The differing contributions at County level are from Small counties
and there are no differing contributions at Postal Code level.

As a result of the County / Postal Code Synchronization and the Small Postal
Code Constraint, exactly one of the three cases applies. For each case, we use
our open source privacy accounting library [7], to compute $\varepsilon$ and
$\delta$ values that satisfy

$\textrm{Pr}[A(D_{1})\in
S]\leq\textrm{exp}(\varepsilon)\cdot\textrm{Pr}[A(D_{2})\in S]+\delta.$

  * •

Case 1: The Cross-Count Bounding and Per-Count Bounding implies that the
distinguishing contributions are made to at most 12 Gaussian Mechanisms with
standard deviations

$\delta_{1,...,12}=(3.25,3.25,3.25,35.0,20.0,20.0,20.0,180.0,35.0,35.0,35.0,450.0)$

and a sensitivity of 1 each. For a fixed $\delta=10^{-5}$, this yields
$\epsilon\approx 2.186$.

  * •

Case 2: Similar to the previous case, the distinguishing contributions are
made to at most 12 Gaussian Mechanisms with standard deviations

$\delta_{1,...,12}=(3.5,3.5,3.5,40.0,8.0,8.0,8.0,100.0,35.0,35.0,35.0,450.0)$

and sensitivities 1 each. For a fixed $\delta=10^{-5}$, this yields
$\epsilon\approx 2.187$.

  * •

Case 3: The distinguishing contributions are now made to at most 8 Gaussian
Mechanisms (because Postal Code level contributions are omitted) with standard
deviations

$\delta_{1,...,12}=(3.21,3.21,3.21,28.0,35.0,35.0,35.0,450.0)$

and sensitivities 1 each. For a fixed $\delta=10^{-5}$, this yields
$\epsilon\approx 2.186$.

Independent of which case applies, we can bound the overall $\varepsilon$ by

$\varepsilon\leq\textrm{max}\\{\varepsilon_{1},\varepsilon_{2},\varepsilon_{3}\\}\leq
2.19,$

which yields the advertised $(2.19,10^{-5})$-differential privacy guarantee.

##  4 Post-processing

We report search trends in the following categories:

  * •

[C1] Vaccination Intent: A subset of queries about COVID-19 vaccination that
are related to eligibility, availability, and accessibility of vaccines.

  * •

[C2] Safety and Side Effects: A subset of queries about COVID-19 vaccination
that are related to the safety and side effects of vaccines.

  * •

[C3] COVID-19 Vaccination: All queries related to COVID-19 vaccination.

Obviously, these 3 categories are not mutually exclusive. To make it easier to
implement contribution bounding, we chose to manipulate categories that are
mutually exclusive, which led us to introduce categories A1, A2, and A3
earlier in this document. We derive the final categories C1, C2, and C3 from
those introduced earlier like this:

  * •

Count(C1) = Count(A1)

  * •

Count(C2) = Count(A2)

  * •

Count(C3) = Count(A1) + Count(A2) + Count(A3)

###  4.1 Normalizing the Counts

The statistics described in the previous step are in the form of raw counts
with added differential privacy (Gaussian) noise. The first transformation we
apply is to normalize these counts by the total search volume in each region,
i.e., Count(A0), which will offer a probabilistic interpretation. For example,
Count(C3) / Count(A0) can serve as a proxy for the probability of a random
query to be related to COVID-19 vaccination. We refer to the resulting ratios
as normalized popularity of each category. This normalization is performed at
every level of geographic granularity (Postal Code, County, etc.)

Since the normalized popularity values have a probabilistic interpretation,
they can be compared across time intervals and geographic regions.

###  4.2 Removing Unreliable Data

In some geographic regions, the noise added to the data by the differentially
private mechanism can introduce a disproportionate amount of uncertainty.
Typically, this happens when the respective count is 0 or small. To limit the
amount of uncertainty, we only keep the noisy value of a metric if it has a
chance of 80% or more to be within 15% of its original value, i.e., the value
before the addition of noise.

More precisely, let $X$ be a noisy count obtained after adding Gaussian noise
to the original count $x^{*}$. Note that $x*$ is not noisy but still subject
to contribution bounding. Similarly, let $Y$ be the corresponding noisy
normalization count computed from the raw count $y*$. To decide whether the
data associated with $X$ will be kept or dropped:

We first compute a confidence interval $[l,r]$ based on $X$ and $Y$ that
contains $x^{*}/y^{*}$ with a probability of at least 80%. We then keep the
data if the following inequalities all hold:

  * •

$X/Y>0$

  * •

$(X/Y)-l\leq 0.15\cdot X/Y$

  * •

$r-(X/Y)\leq 0.15\cdot X/Y$

Otherwise, we drop this data point.

The confidence interval $[l,r]$ is entirely based on the anonymized counts $X$
and $Y$. As a result, no privacy budget is spent on removing unreliable data.

###  4.3 Empty Data Points

Note that the volume of search traffic related to the different topical
categories has varied widely throughout the course of the pandemic.
Consequently, on some weeks some small locations might not have received any
search traffic in a given category. In other cases, the volume of search
traffic was small, and the corresponding data point was removed as unreliable
(cf. the previous section). As a result, some weekly data points may be
missing, especially in less populated regions, and some regions might exhibit
data sparseness. Although data points that have not been filtered out are
generally reliable, we remove regions that have extreme data sparsity, namely,
those that have 3 data points or fewer during the period January - May 2021
(which corresponds to over 85% of data points missing).

###  4.4 Scaling the Normalized Counts

The normalized counts can be seen as a proxy for the probability of a query to
belong to a given category, and these numbers are generally very small (users
search on a large variety of topics, and a relatively small fraction of the
queries are related to COVID-19 vaccination, let alone its sub-categories). To
make the numbers easier to manipulate and visualize, we scale the normalized
popularity values as explained below.

First, we identify the maximum value of the normalized popularity of the
COVID-19 vaccination category (C3), across the entire initially-published US
national time series. We scale this maximum value to 100. You can think of
this as the highest weekly interest in COVID-19 vaccination, at the US
national level, at the time of the initial data release.

Using the same scaling factor, we linearly scale all the other values, across
regions, categories, and time (the resulting values may be higher or lower
than 100). We store the scaling factor computed in the initial release and use
it to scale the values across all regions and categories in subsequent
releases.

Observe that the scaling factor is determined purely based on the noisy search
counts and normalization counts, so no privacy budget is spent on its
computation. Observe also that a single scaling factor is applied across data
from all locations, weeks, and categories. As a result, the scaled data points
are still comparable across all of these dimensions.

## References

  * [1] Google covid-19 vaccination search insights.  http://goo.gle/covid19vaccinationinsights.
  * [2] Google covid-19 vaccination search insights dataset.  https://github.com/GoogleCloudPlatform/covid-19-open-data/blob/main/docs/table-vaccination-search-insights.md.
  * [3] Ahmet Aktay, Shailesh Bavadekar, Gwen Cossoul, et al.  Google covid-19 community mobility reports: Anonymization process description (version 1.0).  Technical report, Google, 2020.
  * [4] Shailesh Bavadekar, Andrew Dai, John Davis, et al.  Google covid-19 search trends symptoms dataset: Anonymization process description (version 1.0).  Technical report, Google, 2020.
  * [5] Differential privacy.  https://en.wikipedia.org/wiki/Differential_privacy.
  * [6] Royce J. Wilson, Celia Yuxin Zhang, William Lam, Damien Desfontaines, Daniel Simmons-Marengo, and Bryant Gipson.  Differentially private sql with bounded user contribution.  Proceedings on Privacy Enhancing Technologies, 2020(2):230 – 250, 2020.
  * [7] Google differential privacy accounting library.  https://github.com/google/differential-privacy/tree/main/python/dp_accounting.


# A recipe based on Lebesgue functions for learning Variably Scaled Kernels
via Discontinuous Neural Networks ($\delta$NN-VSKs)

G. Audone F. Della Santa∗ E. Perracchione∗ S. Pieraccini∗
<EMAIL_ADDRESS><EMAIL_ADDRESS>
<EMAIL_ADDRESS><EMAIL_ADDRESS>Dipartimento di
Scienze Matematiche “Giuseppe Luigi Lagrange”, Politecnico di Torino, Italy

## Abstract

The efficacy of interpolating via Variably Scaled Kernels (VSKs) is known to
be dependent on the definition of a _proper_ scaling function, but no
numerical recipes to construct it are available. Previous works suggest that
such a function should mimic the target one, but no theoretical evidence is
provided. This paper fills both the gaps: it proves that a scaling function
reflecting the target one may lead to enhanced approximation accuracy, and it
provides a user-independent tool for learning the scaling function by means of
Discontinuous Neural Networks ($\delta$NN), i.e., NNs able to deal with
possible discontinuities. Numerical evidence supports our claims, as it shows
that the key features of the target function can be clearly recovered in the
learned scaling function.

##  1 Introduction

Variably Scaled Kernels (VSKs) were introduced in 2015 [1] with the main
purpose of improving the stability of kernel interpolants thanks to the
definition of a scaling function which was originally thought of as a
continuous version of the shape parameter whose value affects accuracy and
stability indicators. Later works show that the use of VSKs might be valuable
when the target function of the scattered data interpolation problem is
characterized by discontinuities. Indeed in such cases, defining a scaling
function with the same key features of the target one, e.g. the same
discontinuities, results in a VSK basis sharing the same discontinuities with
the target; we refer the reader e.g. to [2]. This fact suggests to use the
VSKs with scaling functions able to somehow mimic the target ones as,
intuitively, this allows to directly insert into the kernel basis itself some
prior information about the sought solution, and especially in applied fields,
this turns out to be a relevant issue [3]. Nevertheless, this intuition lacks
both theoretical and numerical evidence.

This work addresses these issues by providing theoretical justification for
the claim, demonstrating by means of the Lebesgue function that a scale
function reflecting the behaviour of the target may lead to enhanced
approximation accuracy. As a further confirmation of our claim, we propose a
user independent way of choosing the scaling function by training a
Discontinuous Neural Network ($\delta$NN) able to learn also possibly
discontinuous scaling functions directly from data [4]. Our results confirm
the theoretical findings: the learned scaling function closely resembles the
target function. This data-driven approach, namely in what follows $\delta$NN-
VSKs, offers a user-independent and adaptive solution for meshfree
approximation tasks.

The paper is organised as follow. In Section 2 we recall the basics of kernel-
based approximation. Section 3 is the core of the paper presenting the theory
and the numeric intuition behind the $\delta$NN-VSKs. Experiments and
conclusions are offered in Section 4.

##  2 Brief review of kernel-based interpolation

We consider symmetric reproducing kernels
$\kappa:\Omega\times\Omega\longrightarrow\mathbb{R}$ for

$H_{\kappa}=\mathrm{span}\left\\{\kappa(\cdot,\bm{x}),\hskip
5.69046pt\bm{x}\in\Omega\subset\mathbb{R}^{d}\right\\},$

which is a pre-Hilbert space equipped with an inner product
$\left(\cdot,\cdot\right)_{H_{\kappa}}$. Those are kernels so that (refer e.g.
to [5, Definition 2.6, p. 32]) $\kappa(\bm{x},\bm{z})=\kappa(\bm{z},\bm{x})$,
and $\left(f,\kappa(\cdot,\bm{x})\right)_{H_{\kappa}}=f(\bm{x})$, for all
$\bm{x},\bm{z}\in\Omega$, and $\kappa(\cdot,\bm{x})\in H_{\kappa}$. The native
space ${\cal N}_{\kappa}$ of the kernel $\kappa$ is then defined as the
completion of $H_{\kappa}$ with respect to the norm
$||\cdot||_{H}=\sqrt{(\cdot,\cdot)_{H}}$, and hence for all $f\in H_{\kappa}$
we have that $||f||_{{\cal N}_{\kappa}}=||f||_{H_{\kappa}}$; here and
throughout all this section we refer the reader to the monographs [5, 6] for
more details.

A common subclass of reproducing kernels, which is frequently used in the
framework of scattered data interpolation problems, is given by radial
kernels. To any radial kernel, we are able to uniquely associate a Radial
Basis Function (RBF) $\varphi:\mathbb{R}_{+}\longrightarrow\mathbb{R}$, where
$\mathbb{R}_{+}=[0,\infty)$, and (possibly) a shape parameter $\varepsilon>0$
such that, for all $\bm{x},\bm{z}\in\Omega$,

$\kappa(\bm{x},\bm{z})=\kappa_{\varepsilon}(\bm{x},\bm{z})=\varphi_{\varepsilon}(\varepsilon||\bm{x}-\bm{z}||_{2})=\varphi_{\varepsilon}(||\bm{x}-\bm{z}||_{2})=\varphi(r),$

where $r=||\bm{x}-\bm{z}||_{2}$. For the sake of notation simplicity, we may
omit the dependence of the kernel on the shape parameter, which is also
referred to as scale parameter in the machine learning literature.

In order to formally introduce the scattered data interpolation problem, we
consider a function $f:\Omega\longrightarrow\mathbb{R}$, with
$\Omega\subset\mathbb{R}^{d}$, and an associated set of functional values
${F}_{n}=\\{f(\bm{x_{i}})\\}_{i=1}^{n}$ sampled at a data nodes set
${{X}_{n}=\\{\bm{x}_{i}\\}_{i=1}^{n}\subset\Omega}$. Given these sets, the
goal consists in computing an approximation of the unknown function $f$,
called $P_{f}$, by imposing the $n$ interpolation constraints, i.e.
$P_{f}(\bm{x}_{i})=f(\bm{x_{i}}),$ $i=1,\ldots,n.$ Assuming that the
interpolating function $P_{f}$ can be written as

$P_{f}\left(\bm{x}\right)=\sum_{k=1}^{n}c_{k}\kappa\left(\bm{x},\bm{x}_{k}\right),\quad\bm{x}\in\Omega,$
(1)

the coefficients $\\{c_{i}\\}_{i=1}^{n}$ are the solution of the linear system
$\mathsf{K}\bm{c}=\bm{f}$, where
$\bm{c}=\left(c_{1},\ldots,c_{n}\right)^{\intercal}$,
$\bm{f}=\left(f_{1},\ldots,f_{n}\right)^{\intercal}$, being
$f_{i}=f(\bm{x}_{i})$, and
$\mathsf{K}_{ik}=\kappa\left(\bm{x}_{i},\bm{x}_{k}\right),$ $i,k=1,\ldots,n$.
Letting $\kappa$ be a symmetric and strictly positive definite kernel, the
collocation matrix is positive definite, and equivalently to (1), we may write
the nodal form of the interpolant as

$P_{f}\left(\bm{x}\right)=\bm{\kappa}^{\intercal}({\bm{x}})\mathsf{K}^{-1}\bm{f},\quad\bm{x}\in\Omega,$

being
$\bm{\kappa}^{\intercal}({\bm{x}})=\left(\kappa(\bm{x},\bm{x}_{1}),\ldots,\kappa(\bm{x},\bm{x}_{n})\right).$

##  3 Investigating and learning the scaling function for VSKs

The idea behind the VSKs, first introduced in the interpolation context in [1]
and later adapted to least squares approximation [7], is to introduce a new
kernel basis as follows. Let $\Sigma\subset\mathbb{R}^{m}$,
$m>0,m\in\mathbb{N}$, and let
$\kappa:\tilde{\Omega}\times\tilde{\Omega}\longrightarrow{\mathbb{R}}$,
$\tilde{\Omega}=\Omega\times\Sigma\subset\mathbb{R}^{d+m}$, be a continuous
radial positive definite kernel. Given a scaling function
$\bar{f}:\Omega\longrightarrow\Sigma,$ a VSK
$\kappa_{\bar{f}}:\Omega\times\Omega\longrightarrow\mathbb{R}$ is defined as

$\kappa_{\bar{f}}(\bm{{x}},\bm{{z}})=\kappa((\bm{{x}},\bar{f}(\bm{x})),(\bm{z},\bar{f}(\bm{z}))={\color[rgb]{0,1,0}:}\kappa(\tilde{\bm{{x}}},\tilde{\bm{{z}}}),$

for $\bm{x},\bm{z}\in\Omega$. Then, the VSK interpolant is simply given by
$P^{{\bar{f}}}_{f}\left({\bm{x}}\right):=P_{f}\left(\tilde{\bm{{x}}}\right)$,
or, equivalently,

$P^{{\bar{f}}}_{f}\left({\bm{x}}\right):=\sum_{k=1}^{n}c_{k}\kappa_{{\bar{f}}}({\bm{x}},{\bm{x}}_{k})=\sum_{k=1}^{n}c_{k}\kappa(\tilde{\bm{{x}}},\tilde{\bm{{x}}}_{k}).$

The VSK interpolant turns out to be easy to implement. Indeed, the
coefficients $c_{1},\ldots,c_{n}$ of the interpolant
$P_{f}^{{\bar{f}}}(\bm{x})$ are computed by solving
$\mathsf{K}_{{\bar{f}}}\bm{c}=\bm{f}$, where
$\bm{c}=\left(c_{1},\ldots,c_{n}\right)^{\intercal}$,
$\bm{f}=\left(f_{1},\ldots,f_{n}\right)^{\intercal}$, and
${(\mathsf{K}_{{\bar{f}}})}_{ik}=\kappa(({\bm{x}_{i}},{\bar{f}}(\bm{x}_{i})),({\bm{x}_{k}},{\bar{f}}(\bm{x}_{k})))$
$i,k=1,\ldots,n$.

###  3.1 VSKs: Investigating the scaling function via Lagrange bases

In previous papers, see e.g. [2, 3, 8], the authors claim that if the scaling
function ${\bar{f}}$ _somehow mimics_ the target one ${{f}}$ or some of its
key features (e.g. its discontinuities), then the VSK interpolant outperforms
the standard one. Nevertheless, no theoretical evidence has been provided and
no numerical tests devoted to find the _optimal_ scaling function has been
performed. For the first item, we point out that for any set of distinct
points $\\{\bm{x}_{i}\\}_{i=1}^{n}$, there exist functions (known as Lagrange
or cardinal bases)
$\varphi^{\bar{f}}_{j}\in\textrm{span}\\{\kappa(\cdot,\tilde{\bm{x}}_{j}),j=1,\ldots,n\\}$
so that the VSK interpolant can be written as

$\displaystyle
P_{f}^{\bar{f}}(\bm{x})=\sum_{j=1}^{n}f_{j}\varphi_{j}^{\bar{f}}(\bm{x}),$

being $\varphi_{j}^{\bar{f}}(\bm{x}):=\varphi_{j}(\tilde{\bm{x}})$. This
allows us to formally introduce error bounds for the VSK interpolant that
depend on the _similarities_ between $\bar{f}$ and $f$.

###### Proposition 3.1

Let $\kappa_{\bar{f}}:\Omega\times\Omega\longrightarrow{\mathbb{R}}$ be the
VSK associated to the strictly positive definite and symmetric kernel
$\kappa:\tilde{\Omega}\times\tilde{\Omega}\longrightarrow{\mathbb{R}}$. Then,
the following point-wise error bound holds true

$\displaystyle\left|\left(f-P_{f}^{\bar{f}}\right)(\bm{x})\right|$
$\displaystyle\leq\left|\left(f-P_{\bar{f}}^{\bar{f}}\right)(\bm{x})\right|+\|\bm{f}-\bm{\bar{f}}\|_{\infty}\lambda_{\bar{f}}(\bm{x}),$
(2)

where
$\lambda_{\bar{f}}(\bm{x})=\sum_{j=1}^{n}|\varphi^{\bar{f}}_{j}(\bm{x})|$ is
the Lebesgue function for the VSK interpolant.

###### Proof.

We trivially have that

$\begin{split}\left|\left(f-P_{f}^{\bar{f}}\right)(\bm{x})\right|&=\left|\left(f-P_{\bar{f}}^{\bar{f}}\right)(\bm{x})+\left(P_{\bar{f}}^{\bar{f}}-P_{f}^{\bar{f}}\right)(\bm{x})\right|\\\
&\leq\left|\left(f-P_{\bar{f}}^{\bar{f}}\right)(\bm{x})\right|+\left|\left(P_{{f}}^{\bar{f}}-P_{\bar{f}}^{\bar{f}}\right)(\bm{x})\right|.\end{split}$

To bound the second term in the above inequality, we observe that

$\displaystyle\left|\left(P_{{f}}^{\bar{f}}-P_{\bar{f}}^{\bar{f}}\right)(\bm{x})\right|$
$\displaystyle=\left|P^{\bar{f}}_{f-{\bar{f}}}(\bm{x})\right|=\sum_{j=1}^{n}|(f_{j}-{\bar{f}}_{j})\varphi^{\bar{f}}_{j}(\bm{x})|\leq\|\bm{f}-\bm{\bar{f}}\|_{\infty}\lambda_{\bar{f}}(\bm{x}),$

and the thesis follows. ∎

Proposition 3.1 states that to get rid of the second term in the right-hand
side of (2), we only need to set the nodal values of $\bar{f}$ equal to the
ones of $f$. Nevertheless, the first term, suggests that the scaling function
$\bar{f}$ should be close to $f$ on the whole domain $\Omega$, as in this way
$P_{\bar{f}}^{\bar{f}}$ should approach $P_{f}^{\bar{f}}$ and $f$ in turn.
Moreover, in terms of native spaces error bounds, we have the following
corollary.

###### Corollary 3.1

Let $\kappa_{\bar{f}}:\Omega\times\Omega\longrightarrow{\mathbb{R}}$ be the
VSK associated to
$\kappa:\tilde{\Omega}\times\tilde{\Omega}\longrightarrow{\mathbb{R}}$ and
$f\in N_{\kappa}^{\bar{f}}$, then

$\displaystyle\left|\left(f-P_{f}^{\bar{f}}\right)(\bm{x})\right|$
$\displaystyle\leq\left(\|f\|_{N_{\kappa}^{\bar{f}}}+\bm{\bar{f}}^{\intercal}\mathsf{K}_{{\bar{f}}}^{-1}\bm{\bar{f}}\right)\|\kappa_{\bar{f}}\|_{N_{\kappa}^{\bar{f}}}+\|\bm{f}-\bm{\bar{f}}\|_{\infty}\lambda_{\bar{f}}(\bm{x}).$

###### Proof.

We point out that in [1, Theorem 2] the authors proved that the native spaces
$N_{\kappa}$ and $N_{\kappa}^{\bar{f}}$ are isometric. Then, by the Cauchy-
Schwarz inequality and the reproducing property, we have that

$\begin{split}\left|\left(f-P_{\bar{f}}^{\bar{f}}\right)(\bm{x})\right|&=\left(f-P_{\bar{f}}^{\bar{f}}\
,\ \kappa_{\bar{f}}(\cdot,\bm{x})\right)_{N_{\kappa}^{\bar{f}}}\\\
&\leq\|f-P_{\bar{f}}^{\bar{f}}\|_{N_{\kappa}^{\bar{f}}}\|\kappa_{\bar{f}}\|_{N_{\kappa}^{\bar{f}}}\\\
&\leq\left(\|f\|_{N_{\kappa}^{\bar{f}}}+\|P_{\bar{f}}^{\bar{f}}\|_{N_{\kappa}^{\bar{f}}}\right)\|\kappa_{\bar{f}}\|_{N_{\kappa}^{\bar{f}}},\end{split}$
(3)

and as
$\|P_{\bar{f}}^{\bar{f}}\|_{N_{\kappa}^{\bar{f}}}=\bm{\bar{f}}^{\intercal}\mathsf{K}_{{\bar{f}}}^{-1}\bm{\bar{f}}$,
the thesis follows. ∎

Once more, the equation (3) in Corollary 3.1 shows that
$P_{\bar{f}}^{\bar{f}}$ should tend point-wise to $f$, indeed
$\|f-P_{\bar{f}}^{\bar{f}}\|_{N_{\kappa}^{\bar{f}}}=0$ if and only if
$(f-P_{\bar{f}}^{\bar{f}})(\bm{x})=0$, for all $\bm{x}\in\Omega$.

We conclude this section by pointing out that we have some theoretical
evidence of the fact that the function $\bar{f}$ should approximate ${f}$.
Nevertheless, no optimal properties have been proved and, as the function $f$
is in practice unknown, we do not have any criteria or algorithm to
automatically define the _best_ scaling function. Hence we implement a NN that
confirms our theoretical findings and returns an _optimal_ , i.e. safe,
$\bar{f}$. Indeed, numerically we will observe that for the practical
implementation of the $\delta$NN-VSKs the demanding pointwise convergence of
the function $\bar{f}$ to ${f}$ can typically be relaxed, as reproducing some
of the key features of the target usually leads to accurate approximations.
Further comments are provided later in Remark 3.1.

###  3.2 VSKs: Learning the scaling function via $\delta$NN

The NN that we consider is referred to as $\delta$NN and its first usage [4]
was devoted to detect the discontinuity interfaces while approximating
discontinuous functions. Such NN is characterized by the introduction of
learnable discontinuities in the layers, legitimated by the universal
approximation theorems [9], and hence might return a discontinuous output. The
reason why we are interested in these NNs lies in the fact that, in principle,
the function $\bar{f}$ could be discontinuous, and we already have numerical
evidence of the fact that if $\bar{f}$ mimics the discontinuities of $f$ then
the Gibbs phenomenon observed in the approximations is drastically reduced;
refer e.g. to [2]. The novelty in this case is that we do not learn the
discontinuities of $f$, we learn directly the function $\bar{f}$ without
imposing any constraints on its discontinuities.

We define the $\delta$NN as a parametric scaling function for the VSKs, aiming
to find the _optimal_ one for the interpolant of $f$. Specifically, we train a
$\delta$NN $\bar{f}_{\bm{\theta}}:{\mathbb{R}}^{d}\rightarrow{\mathbb{R}}$,
with trainable parameters denoted by $\bm{\theta}\in{\mathbb{R}}^{p}$, and we
adapt the interpolation coefficients $\bm{c}\in{\mathbb{R}}^{n}$ by minimizing
the interpolation error of the VSK interpolant. In other words, we build a NN
model $(\bar{f}_{\bm{\theta}},\bm{c})$, pairing $\bar{f}_{\bm{\theta}}$ and
$\bm{c}$, by minimizing the loss

$\begin{split}\mathcal{L}_{X_{n}}(\bm{\theta},\bm{c})&:=\frac{1}{n}\|{\bm{f}-\mathsf{K}_{\bar{f}_{\bm{\theta}}}\bm{c}}\|_{2}^{2}\\\
&=\frac{1}{n}\sum_{i=1}^{n}\left(f_{i}-\sum_{k=1}^{n}c_{k}\kappa\left((\bm{x}_{i},\bar{f}_{\bm{\theta}}(\bm{x}_{i}))\
,\
(\bm{x}_{k},\bar{f}_{\bm{\theta}}(\bm{x}_{k}))\right)\right)^{2},\end{split}$
(4)

where a global minimum
$(\bm{\theta}^{*},\bm{x}^{*})\in{\mathbb{R}}^{p}\times{\mathbb{R}}^{n}$ for
(4) is such that $\mathcal{L}_{X_{n}}(\bm{\theta}^{*},\bm{c}^{*})=0$ (i.e.,
interpolation satisfied).

We drive the reader attention towards the fact that (4) is defined using the
whole training data $\\{(\bm{x}_{i},f_{i})\\}_{i=1}^{n}$ and not with respect
to random mini-batches sampled from it; indeed, since the main task is
interpolation, we prefer a deterministic training procedure instead of a
stochastic one.

######  Remark 3.1 (Comments on the loss optimization)

Concerning the model $(\bar{f}_{\bm{\theta}}^{*},\bm{c}^{*})$ obtained at the
end of the training, we suggest to further recompute the coefficients. Indeed,
by minimizing (4) with respect to both $\bm{\theta}$ and $\bm{c}$, we may
encounter difficulties in satisfying the interpolation conditions. Therefore,
a good practice could be the following one: use the model
$(\bar{f}_{\bm{\theta}}^{*},\widetilde{\bm{c}}^{*})$ instead of
$(\bar{f}_{\bm{\theta}}^{*},\bm{c}^{*})$, where
$(\bar{f}_{\bm{\theta}}^{*},\widetilde{\bm{c}}^{*})$ is the solution of the
linear system $\mathsf{K}_{\bar{f}_{\bm{\theta}_{\rm
fin}}}\widetilde{\bm{c}}^{*}=\bm{f}$ which is solved with an iterative
procedure (e.g., conjugate gradient), starting from the coefficients
$\bm{c}^{*}$. Another consequence of the fact that in order to minimize (4) we
need to optimize both $\bm{\theta}$ and $\bm{c}$ that are dependent on
$\bar{f}$, is that the solution of the optimization problem is not unique.
Nevertheless, we will provide numerical evidence that the function
${\bar{f}}=\bar{f}_{\bm{\theta}_{\rm fin}}$ returned by the $\delta$NN at the
end of the training procedure is close to $f$, as suggested by the theory. To
be more precise, the function ${\bar{f}}$ is so that $\bar{f}\approx\gamma f$,
$\gamma:\mathbb{R}^{d}\longrightarrow\mathbb{R}$ continuous function. This is
coherent with our implementation of the $\delta$NN and its loss, as further
explained in the following. Let us write the VSKs with their explicit
dependence on the shape parameter and the radial distance, i.e., for
$\bm{x},\bm{z}\in\Omega$:

$\begin{split}\kappa_{\gamma{f}}(\bm{x},\bm{z})&=\varphi\left(\varepsilon\sqrt{\sum_{k=1}^{d}(\bm{x}^{(k)}-\bm{z}^{(k)})^{2}+((\gamma{f})(\bm{x})-(\gamma{f})(\bm{z}))^{2}}\right)\\\
&=\varphi\left(\sqrt{\sum_{k=1}^{d}\varepsilon^{2}(\bm{x}^{(k)}-\bm{z}^{(k)})^{2}+\varepsilon^{2}(\gamma(\bm{x}){f}(\bm{x})-\gamma(\bm{x}){f}(\bm{z}))^{2}}\right).\end{split}$

Then, the fact that the function $\bar{f}$ mimics the shape of the function
$f$ but sometimes possibly out of scale is a consequence of the fact that the
$\delta$NN itself tries to _adjust_ , via the function $\gamma$, the fixed
shape parameter $\varepsilon$. In principle we could optimize the shape
parameter too, but we think that learning $\bar{f}$ is the novelty, while
there are many papers (see e.g. [10, 11, 12]) and methods for optimizing
$\varepsilon$ which could be integrated in future with our scheme.

##  4 Numerical experiments and conclusions

In the numerical experiments that follow we take as test functions the well-
known _Franke’s_ function

$\begin{split}f_{1}(x_{1},x_{2})=&\dfrac{3}{4}{\rm
e}^{-[(9x_{1}-2)^{2}+(9x_{2}-2)^{2}]/4}+\dfrac{3}{4}{\rm
e}^{-(9x_{1}+1)^{2}/49-(9x_{2}+1)/10}\\\ &+\dfrac{3}{4}{\rm
e}^{-[(9x_{1}-2)^{2}+(9x_{2}-2)^{2}]/4}+\dfrac{3}{4}{\rm
e}^{-(9x_{1}+1)^{2}/49-(9x_{2}+1)/10},\end{split}$

which is continuous being the sum of exponential terms and the discontinuous
test function

$\displaystyle f_{2}(x_{1},x_{2})=\begin{cases}{\rm
e}^{(-(x_{1}-0.5)^{2}+(x_{2}-0.5)^{2})},\quad\textrm{if}\quad||\bm{x}-(0.5,0.5)||_{2}^{2}\geq
0.08\\\ \sin(x_{1})+4\sin(x_{2}),\quad\textrm{otherwise}.\end{cases}$

We sample them at $N=[27^{2},33^{2},39^{2}]$ scattered Halton data in
$[0,1]^{2}$ and we compute, as accuracy indicators, both the Mean Squared
Error (MSE) and the Structure Similarity Index (SSIM) which is in between 0
and 1 and it is an indicator of similarity between two images (the largest the
better). The kernel used to approximate the function $f_{1}$ is the Gaussian
$C^{\infty}$, while the for $f_{2}$ we use the Matérn $C^{2}$ kernel.

###  4.1 Experiments outline

As Proposition 3.1 suggests that a good approximation of the target can be
used as scaling function, our $\delta$NN-VSKs method, where the NN is trained
to learn the scaling function, will be compared also with what is referred to
as VSKs-$f$. In the latter approach the NN learns directly the target function
and the output is used as scaling function. Both will be compared to a
classical Fixed Scale Kernel approximation (FSK) and to the $\delta$NN method
used to directly learn $f_{1}$ and $f_{2}$. The results are reported in Tables
1–2. All results are reproducible as the Python code is free available at
https://github.com/Fra0013To/VSKlearning.

###  4.2 Conclusions and comments on the results

For both $f_{1}$ and $f_{2}$ we can observe that the $\delta$NN-VSKs and
VSKs-$f$ behave better than FSK and $\delta$NN, coherently with Proposition
3.1 and Remark 3.1. For the discontinuous function $f_{2}$ the improvement in
terms of SSIM of the VSKs-based methods is evident, however, the most relevant
result is the one reported in Figure 1. Here we report the reconstructions of
the two target functions $f_{1}$ and $f_{2}$ together with the learned scaling
functions. Because of the similarity between the targets and the recovered
scaling functions, on the one hand, the $\delta$NN-VSKs method supports our
theoretical claims and, on the other one, offers the opportunity to
automatically define a scaling function for the VSKs.

As future work, we plan to learn simultaneously both the scaling function for
VSKs and the _optimal_ sampling locations producing in that way sparse models
(see e.g. [13, 14, 15]).

|  | MSE
---|---|---
| $n$ | FSK |  $\delta$NN |  $\delta$NN-VSKs | VSKs-$f$
$f_{1}$ | 729 | 4.2498e-3 | 2.6381e-5 | 1.4246e-4 | 2.4368e-5
1089 | 9.8816e-4 | 1.2737e-5 | 2.3377e-5 | 8.2578e-6
1521 | 3.8427e-7 | 1.0050e-5 | 3.8392e-7 | 2.7049e-7
$f_{2}$ | 729 | 3.7403e-2 | 4.9117e-3 | 3.8652e-3 | 4.5955e-3
1089 | 2.1595e-2 | 3.0441e-3 | 2.7193e-3 | 3.0060e-3
1521 | 9.2245e-3 | 2.0504e-3 | 1.1860e-3 | 1.3208e-3
Table 1: MAEs for the test functions $f_{1}$ and $f_{2}$. |  | SSIM
---|---|---
| $n$ | FSK |  $\delta$NN |  $\delta$NN-VSKs | VSKs-$f$
$f_{1}$ | 729 | 0.8712 | 0.9939 | 0.9820 | 0.9943
1089 | 0.9533 | 0.9971 | 0.9969 | 0.9980
1521 | 0.9997 | 0.9971 | 0.9997 | 0.9999
$f_{2}$ | 729 | 0.6118 | 0.8891 | 0.9113 | 0.8901
1089 | 0.6072 | 0.9254 | 0.9300 | 0.9482
1521 | 0.6676 | 0.9226 | 0.9715 | 0.9633
Table 2: SSIMs for the test functions $f_{1}$ and $f_{2}$.

Figure 1: Top and bottom: results for the function $f_{1}$ and $f_{2}$. Left
to right: target function, scaling function, approximation with FSK and
$\delta$NN-VSKs.

## Acknowledgements

Gianluca Audone and Emma Perracchione kindly acknowledge the support of the
Fondazione Compagnia di San Paolo within the framework of the Artificial
Intelligence Call for Proposals, AIxtreme project (ID Rol: 71708). Sandra
Pieraccini acknowledge the support of the FaReX project (”Full and Reduced
order modelling of coupled systems: focus on non-matching methods and
automatic learning”) – funded by the Ministero dell’Università e della Ricerca
– within the PRIN 2022 program (D.D.104 - 02/02/2022). All authors acknowledge
the Gruppo Nazionale per il Calcolo Scientifico - Istituto Nazionale di Alta
Matematica (GNCS - INdAM). Francesco Della Santa and Sandra Pieraccini
acknowledge that this study was carried out within the FAIR-Future Artificial
Intelligence Research and received funding from the European Union Next-
GenerationEU (PIANO NAZIONALE DI RIPRESA E RESILIENZA (PNRR)–MISSIONE 4
COMPONENTE 2, INVESTIMENTO 1.3 - D.D. 1555 11/10/ 2022, PE00000013). This
manuscript reflects only the authors’ views and opinions; neither the European
Union nor the European Commission can be considered responsible for them.

## References

  * [1] M. Bozzini, L. Lenarduzzi, M. Rossini, R. Schaback, Interpolation with variably scaled kernels, IMA J. Numer. Anal. 35 (1) (2015) 199–219.
  * [2] S. De Marchi, W. Erb, F. Marchetti, E. Perracchione, M. Rossini, Shape-driven interpolation with discontinuous kernels: Error analysis, edge extraction, and applications in magnetic particle imaging, SIAM J. Sci. Comput. 42 (2) (2020) B472–B491.
  * [3] E. Perracchione, F. Camattari, A. Volpara, P. Massa, A. M. Massone, M. Piana, Unbiased clean for stix in solar orbiter, Astrophys. J. Suppl. S. 268 (2) (2023).
  * [4] F. Della Santa, S. Pieraccini, Discontinuous neural networks and discontinuity learning, J. Comput. Appl. Math. 419 (2023).
  * [5] G. E. Fasshauer, M. McCourt, Kernel-based Approximation Methods using MATLAB, World scientific, 2015.
  * [6] H. Wendland, Scattered Data Approximation, Cambridge University Press, 2004.
  * [7] M. K. Esfahani, S. De Marchi, F. Marchetti, Moving least squares approximation using variably scaled discontinuous weight function, Constr. Math. Anal. 6 (1) (2023) 38–54.
  * [8] M. Rossini, Interpolating functions with gradient discontinuities via Variably Scaled Kernels, Dolomites Res. Notes Approx. 17 (2018) 3–14.
  * [9] P. Kidger, T. Lyons, Universal approximation with deep narrow networks, Vol. 125, 2020, pp. 2306–2327.
  * [10] T. A. Driscoll, B. Fornberg, Interpolation in the limit of increasingly flat radial basis functions, Comput. Math. Appl. 43 (3-5) (2002) 413–422.
  * [11] L. Ling, F. Marchetti, A stochastic extended Rippa’s algorithm for LpOCV, Appl. Math. Letters 129 (2022) 107955.
  * [12] T. Wenzel, F. Marchetti, E. Perracchione, Data-driven kernel designs for optimized greedy schemes: A machine learning perspective, SIAM J. Sci. Comput. 46 (1) (2024) C101–C126.
  * [13] F. Camattari, S. Guastavino, F. Marchetti, M. Piana, E. Perracchione, Classifier-dependent feature selection via greedy methods, Statist. Comput. 34 (151) (2024) 1–12.
  * [14] S. De Marchi, R. Schaback, H. Wendland, Near-optimal data-independent point locations for radial basis function interpolation, Adv. Comput. Math. 23 (3) (2005) 317–330.
  * [15] T. Wenzel, G. Santin, B. Haasdonk, Analysis of Target Data-Dependent Greedy Kernel Algorithms: Convergence Rates for $f$-, $f\cdot{P}$\- and $f/{P}$-Greedy, Constr. Approx. (2022).


* [C] X. Chen, A simple proof that rational curves on K3 are nodal, Math. Ann. 324 (2002), 71-104.
  * [CFHR] F. Catanese, M. Franciosi, K. Hulek and M. Reid, Embeddings of curves and surfaces, Nagoya Math. J. 154 (1999), 185-220.
  * [CK] C. Ciliberto and A. L. Knutsen, On k-gonal loci in Severi varieties on general K3 surfaces and rational curves on hyperkähler manifolds, J. Math. Pures App. 101 (2014), 473-494.
  * [E] D. Eisenbud, Green’s conjecture: an orientation for algebraists, Free resolutions in commutative algebra and algebraic geometry (Sundance, UT, 1990) (1992), 51-78.
  * [EG] D. Eisenbud and S. Goto, Linear free resolutions and minimal multiplicity, J. Algebra 88 (1984), 89-133.
  * [EH] D. Eisenbud and J. Harris, On varieties of minimal degree (A centennial account), Proc. Sympos. Pure Math. 46 (1987), 3–13.
  * [EL] L. Ein and R. Lazarsfeld, Asymptotic Syzygies of Algebraic Varieties, Inventiones Math. 190 (2012), 603-646.
  * [F] G. Farkas, Progress on syzygies of algebraic curves, Lecture Notes of the Unione Matematica Italiana 21 (Moduli of Curves, Guanajuato 2016), 107-138.
  * [FK1] G. Farkas and M. Kemeny, The generic Green–Lazarsfeld Secant Conjecture, Inventiones Math. 203 (2016), 265-301.
  * [FK2] G. Farkas and M. Kemeny, Linear syzygies for curves of prescribed gonality. Advances in Math. 356 (2019), 106810.
  * [FuLa] W. Fulton and R. Lazarsfeld, On the connectedness of degeneracy loci and special divisors, Acta Math. 146 (1981), 271-283.
  * [GH] P. Griffiths and J. Harris, On the variety of special linear systems on a general algebraic curve, Duke Math. J. 47(1980), 233-272.
  * [Gi] D. Gieseker, Stable curves and special divisors: Petri’s conjecture, Inventiones Math. 66(1982), 251-275.
  * [Go] T. Gómez, Brill–Noether theory on singular curves and torsion-free sheaves on surfaces, Communications in Analysis and Geometry 9 (2001), 725-756.
  * [Gr1] M. Green, The canonical ring of a variety of general type, Duke Math. J. 49 (1982), 1087-1113.
  * [Gr2] M. Green, Koszul cohomology and the cohomology of projective varieties, J. Differential Geo. 19 (1984), 125-171.
  * [Gr3] M. Green, Quadrics of rank four in the ideal of a canonical curve, Inventiones Math. 75 (1984), 85-104.
  * [H1] R. Hartshorne, Algebraic Geometry, Graduate Texts in Mathematics 52, Springer-Verlag, New York, 1977.
  * [H2] R. Hartshorne, Generalized divisors on Gorenstein curves and a theorem of Noether, J. Math. Kyoto Univ 26 (1986), 375-386.
  * [Hu] D. Huybrechts, Lectures on K3 surfaces., Cambridge University Press 158, 2016.
  * [HL] D. Huybrechts and M. Lehn, The geometry of moduli spaces of sheaves, Cambridge University Press, 2010.
  * [HLMP] K. Han, W. Lee, H. Moon and E. Park, Rank 3 Quadratic Generations of Veronese Embeddings, to appear in Compositio Math.
  * [Ka] J. Kass, Singular curves and their compactified Jacobians, A Celebration of Algebraic Geometry, Clay Math Proc. 18(2013), 391-428.
  * [Ke1] M. Kemeny, The moduli of singular curves on K3 surfaces, J. Math. Pures App. 104 (2015), 882-920.
  * [Ke2] M. Kemeny, Projecting Syzygies of Curves, Algebraic Geometry 7 (2020), 561-580.
  * [Ke3] M. Kemeny, Universal Secant Bundles and Syzygies of Canonical Curves, Inventiones Math. 223 (2021), 995-1026.
  * [KS] J. Koh, and M. Stillman, Linear syzygies and line bundles on an algebraic curve, J. Algebra 125 (1989), 120-132.
  * [L1] R. Lazarsfeld, Brill-Noether-Petri without degenerations, J. Differential Geo. 23 (1986), 299-307.
  * [L2] R. Lazarsfeld, Lectures on linear series, arXiv:alg-geom/9408011.
  * [O] K. O’Grady, Moduli of sheaves and the Chow group of K3 surfaces, J. Math. Pures App. 100(2013), 701-718.
  * [M] D. Mumford, Varieties defined by quadratic equations. Corso C.I.M.E. 1969 (Questions on algebraic varieties). Roma: Cremonese 1970.
  * [Kn] A. Knutsen, On $k$-th order embeddings of K3 surfaces and Enriques surfaces, Manuscripta Math. 104 (2001), 211-237.
  * [P] I. Peeva, Graded syzygies, Springer, 2010.
  * [R] C. J. Rego, The compactified Jacobian, Ann. Sci. Éc. Norm. Sup. 13 (1980), 211-223.
  * [SP] The Stacks Project Authors, Stacks Project, http://stacks.math.columbia.edu, 2019.
  * [Sch] F.-O. Schreyer, Syzygies of canonical curves and special linear series, Math. Ann. 275 (1986), 105-137.
  * [SS] J. Sidman and G. Smith, Linear determinantal equations for all projective schemes, Algebra and Number Theory 5 (2011), 1041-1061.
  * [SSW] J. Schicho, F.-O. Schreyer and M. Weimann, Computational aspects of gonal maps and radical parametrization of curves, Appl. Algebra Engrg. Comm. Comput. 24 (2013), 313-341.
  * [Ta] A. Tannenbaum, Families of curves with nodes on K3 surfaces, Math. Ann. 260 (1982), 239-253.
  * [V1] C. Voisin, Green’s generic syzygy conjecture for curves of even genus lying on a $K3$ surface, J. European Math. Society 4 (2002), 363-404.
  * [V2] C. Voisin, Green’s canonical syzygy conjecture for generic curves of odd genus, Compositio Math. 141 (2005), 1163-1190.
  * [W1] J. Weyman, Resolutions of the exterior and symmetric powers of a module, J. Algebra 58 (1979), 333-341.
  * [W2] J. Weyman, Cohomology of vector bundles and syzygies, Cambridge University Press, 2003.