# A Tale of Two Linkings: Dynamically Gating between Schema Linking and
Structural Linking for Text-to-SQL Parsing

Sanxing Chen♢ Aidan San♢ Xiaodong Liu♣ Yangfeng Ji♢
♢University of Virginia
♣Microsoft Research
{sc3hn, aws9xm<EMAIL_ADDRESS>
<EMAIL_ADDRESS>

###### Abstract

In Text-to-SQL semantic parsing, selecting the correct entities (tables and
columns) for the generated SQL query is both crucial and challenging; the
parser is required to connect the natural language (NL) question and the SQL
query to the structured knowledge in the database. We formulate two linking
processes to address this challenge: schema linking which links explicit NL
mentions to the database and structural linking which links the entities in
the output SQL with their structural relationships in the database schema.
Intuitively, the effectiveness of these two linking processes changes based on
the entity being generated, thus we propose to dynamically choose between them
using a gating mechanism. Integrating the proposed method with two graph
neural network-based semantic parsers together with BERT representations
demonstrates substantial gains in parsing accuracy on the challenging Spider
dataset. Analyses show that our proposed method helps to enhance the structure
of the model output when generating complicated SQL queries and offers more
explainable predictions.

##  1 Introduction

00footnotetext:  This work is licensed under a Creative Commons Attribution
4.0 International License. License details:
http://creativecommons.org/licenses/by/4.0/.

Semantic parsing, which aims at mapping natural language (NL) utterances to
computer understandable logic forms or programming languages, has been an
active research topic in the field of natural language processing (NLP) for
decades [zettlemoyer-2005-learning, liang-etal-2011-learning]. Although a
variety of logic forms have been studied by researchers, Text-to-SQL has
particularly attracted a large amount of attention due to the desire of
natural language interfaces to database (NLIDB) [warren-
pereira-1982-efficient, Zelle-1996-Learning, dong_learning_2019] for both
scientific and industrial reasons. Recently, there is a growing interest in
neural based Text-to-SQL semantic parsing, thanks to the development of new
evaluation paradigms and datasets [iyer-etal-2017-learning, zhongSeq2SQL2017,
yu-etal-2018-spider, yu-etal-2019-sparc].

Text-to-SQL parsing requires strict structured prediction due to its
application scenario where the output SQL will be sent to an executor program
directly. To enhance the capacity of an auto-regressive model to capture
structural information, current state-of-the-art semantic parsers usually
adopt a grammar-based decoder [xiao-etal-2016-sequence, yin-
neubig-2017-syntactic, krishnamurthy-etal-2017-neural]. Rather than directly
generating the tokens in a traditional sequence-to-sequence manner, grammar-
based decoders produce a sequence of production rules to construct an abstract
syntax tree (AST) of the corresponding SQL. As the grammar constraints narrows
down the search space to only grammatically valid ASTs, those parsers can
usually generate well-formed SQL skeletons [guo-etal-2019-towards, bogin-
etal-2019-representing].

1 |  Q: For each continent, list its id, name, and how many countries it has?
---|---
2 |  Q1: What is the average, minimum, and maximum age of all singers from France?
Q2: What is the average, minimum, and maximum age for all French singers?
3 |  Q: What is the first name and gender of the all the students who have more than one pet?

Table 1: Several examples that are taken from the Spider dataset. Entity
mentions are underlined in NL questions. Q1 and Q2 are paraphrases of each
other which should lead to the same SQL result. Wavy underline indicates the
mention can only be resolved by linking to a cell value or common sense
reasoning.

However, it is still difficult for current state-of-the-art models to fill in
the skeletons with semantically correct entities, especially when they are
required to generalize to unseen DB schemas [yu-etal-2018-spider, suhr-
etal-2020-exploring]. To predict the correct entity, the model should have a
database (DB) schema grounded understanding of the NL question, which means
that the model should be able to jointly learn the semantics in the NL
question and the structured knowledge in a given database. We formulate two
types of entity generation problems, which can be addressed by the following
two linking processes respectively.

Schema linking. Schema linking [guo-etal-2019-towards, wang-etal-2020-rat] is
an instance of entity linking [shen-2014-el] in the context of linking to
relational DB schema. Text-to-SQL semantic parsers should learn to recognize
an entity mention in the NL question and link it to the corresponding unique
entity in the DB schema. This task can be challenging due to the diversity and
ambiguity NL mentions. However, in practice, the solution is often relatively
easy when a particular entity is well realized with similar wording in both
the NL question and DB schema. As shown in section 1, in Spider [yu-
etal-2018-spider], the underlined mentions can almost exactly match the
corresponding schema entities. Therefore, current state-of-the-art parsers
normally address this problem with simple string matching or embedding
matching modules.

Structural linking. While some entities are generated because they are
mentioned in the NL question, others can be generated because of their role as
special functional components in SQL, e.g., contid and stuid in the ON clauses
of the first and third examples in section 1. These entities usually cannot
find their corresponding mentions in the NL question but can be induced by the
structural constraints of SQL. Such phenomenons are generally referred to as
the structural mismatch between NL and formal languages [Kwiatkowski-
etal-2013-scaling, Berant-liang-2014-semantic]. This process frequently occurs
when generating complex SQL queries. We propose to treat this entity
generation process as finding a structural link between current candidates and
past generated entities. Although previous work has considered some simple
structural constraints [guo-etal-2019-towards], to the best of our knowledge,
we are the first to formally describe this process.

While schema linking and structural linking can complement each other (e.g.,
the entity used by the GROUP BY clause needs to be a column in a previously
selected table and also has its mention in the NL question), they actually
address different types of problems. In most cases, e.g., the examples in
section 1 described before, a decoder may need to discriminate one from
another for better generation performance.

In this work, we propose to use a dynamic gating mechanism to serve as a
switch between the two linking processes. Schema linking can be implemented as
the decoder attending to the encoded representations of the NL question to
find an entity mention, then locating the corresponding entity from the
schema. On the other hand, in structural linking, our decoder performs self-
attention over those past decoder states where an entity was generated and
further makes a decision between copying one of the previously generated
entities or taking one of its linked entities (e.g., the foreign key of a
previously joined table) based on the schema structure. From the model’s
perspective, it can also be viewed as a memory pointer network that enhances
the structured prediction ability of an auto-regressive model, and the dynamic
gating determines when to emphasize this enhancement. Our proposed method can
be easily applied to most semantic parsers as long as their decoders
explicitly or implicitly have two modules that deal with schema linking and
structural linking.

We integrate the dynamic gating technique to two state-of-the-art Text-to-SQL
parsing models [bogin-etal-2019-representing, bogin-etal-2019-global] and
further augment them with pretrained BERT [devlin-etal-2019-bert] word
representations. We evaluate our model on the Spider dataset which is
challenging because of its cross-domain setting where a model needs to
generalize to not only complex SQL but also unseen DBs. Experimental results
show that our proposed method consistently yields an improvement of more than
3% on exact set matching accuracy and sees the most benefits when generating
complex SQL. Further analysis confirms that the models are dynamically
switching between the two linking processes.

##  2 Approach

Figure 1: An illustration of our proposed method when running the first
example shown in Table 1. This figure shows two independent entity generation
procedures, the top one favors schema linking while the bottom one favors
structural linking. Some details are omitted for the sake of simplicity.
Grammars are simplified to fit in the limited space, readers are encouraged to
refer to [krishnamurthy-etal-2017-neural] for details.

In this section, we first formulate the Text-to-SQL semantic parsing task in
section 2.1. We will then describe the details of our proposed method in
section 2.2.

###  2.1 Text-to-SQL Semantic Parsing

The task of Text-to-SQL semantic parsing is to predict a SQL query
$\mathcal{S}$ based on input $(\mathcal{Q},\mathcal{G})$ where
$\mathcal{Q}=\\{q_{1},\dots,q_{|\mathcal{Q}|}\\}$ is the NL question and
$\mathcal{G}=(\mathcal{V},\mathcal{E})$ is the DB schema being queried. In the
schema,
$\mathcal{V}=\\{(e_{1},t_{1}),\dots,(e_{|\mathcal{V}|},t_{|\mathcal{V}|})\\}$
is a set which usually contains two types of entities (i.e., tables and
columns111Note that columns may have more fine-grained types like binary,
numeric, string and date/time, primary/foreign etc.) and their textual
descriptions (i.e., table names and column names), while
$\mathcal{E}=\\{(e^{(s)}_{1},e^{(t)}_{1},l_{1}),\dots,(e^{(s)}_{|\mathcal{E}|},e^{(t)}_{|\mathcal{E}|},l_{|\mathcal{E}|})\\}$
contains the relations $l$ between source entity $e^{(s)}$ and target entity
$e^{(t)}$, e.g., table-column relationships, foreign-primary key
relationships,222In SQL, a foreign key in one table is used to refer to a
primary key in another table to link these two tables together for joint
queries. etc. The output $\mathcal{S}=\\{a_{1},\dots,a_{|\mathcal{S}|}\\}$ is
a sequence of decoder actions which further compose an AST of SQL.

Link gate NL encoder Schema linking Copy gate Link entity Copy entity
Structural linking Figure 2: An illustration of our gating mechanism.

Typical state-of-the-art Text-to-SQL parsers, consist of three components: a
NL encoder, a schema encoder and a grammar decoder [guo-etal-2019-towards,
bogin-etal-2019-representing].

The NL encoder takes the NL question tokens $\mathcal{Q}$ as input, maps them
to word embeddings $\bm{E}_{\mathcal{Q}}$, then feeds them to a Bi-LSTM
[hochreiter1997long]. The hidden states of the Bi-LSTM serve as the contextual
word representation of each token.

The schema encoder takes $\mathcal{G}$ as input and builds a relation-aware
entity representation for every entity in the schema. The initial
representation of an entity is a combination of its words embeddings and type
information. Then self-attention [zhang-etal-2019-editing, shaw-
etal-2019-generating] or graph-based models [bogin-etal-2019-representing,
wang-etal-2020-rat] are utilized to exploit the relational information between
each pair of entities from the DB schema, thus produce the final
representation of all entities
$\bm{H}_{\mathcal{V}}\in\mathbb{R}^{|\mathcal{V}|\times\operatorname{dim}}$.
We will detail this in section 3.

Finally, a grammar decoder [xiao-etal-2016-sequence, yin-
neubig-2017-syntactic, krishnamurthy-etal-2017-neural] generates an AST of
output SQL in a depth-first order. The decoder is typically an auto-regressive
model (e.g., LSTM) which estimates the probability of generating an action
sequence.

There are _two cases_ of using actions. Depending a specific case, an action
is either  (i) producing a new production rule to unfold the leftmost non-
terminal node in the AST, or  (ii) generating an entity (e.g., a table or a
column) from the DB schema if it is required by last output production rule.
In the former case, at step $t$, the decoder normally uses its hidden states
$\bm{h}_{t}$ to retrieve a context vector $\bm{c}_{t}$ from the NL encoder.
Then an action embedding $\bm{a}_{t}$ is produced based on the concatenation
of $\bm{h}_{t}$ and $\bm{c}_{t}$. This action embedding will directly predict
a production rule from the target vocabulary which is a subset of a fixed
number of production rules. For the latter case, the decoder needs to estimate
a probability distribution over a schema-specific vocabulary under grammatical
constraints which come from the structure of both the output SQL and the DB
schema, as well as semantic constraints implied in the NL question.

###  2.2 Dynamic Gating

In this paper, we focus on the decision made when the decoder is looking for
an entity to fill in a slot (i.e., case (ii) in the last paragraph). Our
decoder predicts the entity based on a mixed probability model consisting of
two processes:

  * •

Schema linking. The decoder attends to the output of the NL encoder (which can
be seen as selecting a most relevant NL mention), then finds the corresponding
entity based on string-matching or embedding-matching results.

  * •

Structural linking. The decoder self-attends to the output states from those
previous decoding steps which have generated entities, then finds another
entity which is structurally linked to the attended entity.

The choice between them is controlled by a gating mechanism called the link
gate.

Formally, the marginal probability of generating an entity $e$ is defined as
follows:

$\begin{split}\operatorname{Pr}(a_{t}=e)&=\operatorname{Pr}(e|\textsc{Schm})\operatorname{Pr}(\textsc{Schm})+\operatorname{Pr}(e|\textsc{Strct})\operatorname{Pr}(\textsc{Strct})\end{split}$
(1)

where $\operatorname{Pr}(\textsc{Schm})$ and
$\operatorname{Pr}(\textsc{Strct})$ are the probability of choosing schema
linking and structural linking respectively. They are further computed as:

$\displaystyle\rho_{\operatorname{link}}$
$\displaystyle=\operatorname{Sigmoid}(\operatorname{FF}(\bm{a}_{t}))$ (2)
$\displaystyle\operatorname{Pr}(\textsc{Schm})$
$\displaystyle=\rho_{\operatorname{link}}$ (3)
$\displaystyle\operatorname{Pr}(\textsc{Strct})$
$\displaystyle=1-\rho_{\operatorname{link}}$ (4)

Equation 2 stands for our proposed link gate which is computed by the action
embedding $\bm{a}_{t}$. The reason for purely basing the gate value on
$\bm{a}_{t}$ is that intuitively the choice between the two processes is about
the role of the current entity we want to generate. The role of an entity is
determined by the SQL clause that contains it. Since $\bm{a}_{t}$ is directly
used to predict a production rule in case (i), it should be able to capture
this information. The link gate allows the decoder to dynamically choose
between information from our two linking processes, and prevents them from
interfering each other.

In practice, we model the probability of the schema linking process generating
an entity mentioned in the NL question, namely
$\operatorname{Pr}(e|\textsc{Schm})$, as a multiplication of the attention
weights $\bm{\lambda}\in\mathbb{R}^{|\mathcal{Q}|}$ over the NL encoder
outputs and a schema linking matrix
$M\in\mathbb{R}^{|\mathcal{Q}|\times|\mathcal{V}|}$. The probability of the
structural linking process, namely $\operatorname{Pr}(e|\textsc{Strct})$, is
similarly computed by multiplying decoder self-attention weights and a
structural linking matrix $T\in\mathbb{R}^{|\mathcal{V}|\times|\mathcal{V}|}$.

The structural linking matrix $T$ captures the relationship between every pair
of entities given the relational DB schema. Common structural links include
relations between a table and its columns, a table and its primary/foreign
key, a primary key and one of its linked foreign keys in other tables, etc.
There are also multi-steps links which are the combinations of the one-step
links listed above. Note that there may not be a unique link between every
pair of entities and some entities may not have a link between them at all.
Meanwhile, an entity can link to itself which can be considered to be a
special zero-step structural link. It is the only structural link modeled in
most current Text-to-SQL semantic parsers.

We compute the structural linking score between an entity $e_{i}$ and $e_{j}$
by an additive attention mechanism [bahdanau2014neural], as follows:

$T_{i,j}=\mathbf{v}_{\alpha}^{\top}\tanh\left(\mathbf{W}_{\alpha}\left[\bm{e}_{i};\bm{e}_{j}\right]\right)$
(5)

where $\bm{e}_{i}$ and $\bm{e}_{j}$ are the corresponding entity
representations retrieved from $\bm{H}_{\mathcal{V}}$, while
$\mathbf{v}_{\alpha}$ and $\mathbf{W}_{\alpha}$ are both trainable parameters.
Compared to the dot-product attention used in ?) and ?), the additive
attention we used here is expected to capture more of the structural
relationship between entity pairs rather than only the similarity of entity
representations.

$T$ is expected to capture all types of relationships between entities, but it
can be overwhelmed by the large workload. So, we single out the zero-step
relationship (i.e., copying) and address it by another structural linking
matrix $T_{\operatorname{copy}}=\bm{I}$, which is trivially an identity matrix
in this case. To choose between copying and other types of links, a copy gate
($\rho_{\operatorname{copy}}$) is obtained in the same manner as to how we
compute the link gate in Equation 2.

We use decoder self-attention to find the past generated entity which could
have structural constraints on the entity that we currently want to generate.

$\displaystyle\bm{\beta}=\operatorname{Softmax}(\operatorname{Attention}(\bm{a}_{t},\bm{H}_{m}))$
(6) $\displaystyle\bm{H}_{m}=\\{\bm{a}_{i}|i<t,a_{i}\in e\\}$ (7)

$\bm{H}_{m}$ is a memory matrix consisting of the action embeddings from every
past decoding step which has generated an entity. In this way, we compute two
sets of attention weights $\bm{\beta}_{\operatorname{copy}}$ and
$\bm{\beta}_{\operatorname{link}}$ for copying and linking separately using
the additive attention [bahdanau2014neural] again. The motivation for separate
attention weights is that these two linking patterns might need to attend to
different generated entities.

Overall the probability of generating an entity via structural linking is
modeled as:

$\begin{split}\operatorname{Pr}(a_{t}=e_{i}|\textsc{Strct})=\rho_{\operatorname{copy}}(\bm{\beta}_{\operatorname{copy}}T_{\operatorname{copy}})_{i}+(1-\rho_{\operatorname{copy}})(\bm{\beta}_{\operatorname{link}}T)_{i}\end{split}$
(8)

Finally, this probability is mixed with the probability of schema linking
controlled by the link gate.

##  3 Model Implementation

In this section, we describe how we integrate our proposed method into a
grammar decoder and leverage the entity representation from a GNN module.

We use the type constrained grammar decoder from ?). To predict $a_{t}$ at
time step $t$, the decoder will first obtain the context vector $\bm{c}_{t}$
from the NL encoder by performing dot-product attention [luong-
etal-2015-effective]. Then the action embedding is generated by a feed-forward
network taking the concatenation of decoder hidden state and context vector as
input.

$\bm{a}_{t}=\operatorname{FF}([\bm{h}_{t};\bm{c}_{t}])$ (9)

$\bm{a}_{t}$ is used to predict the production rule or estimate the gate
values in the entity generation process.

We adopt the idea from [bogin-etal-2019-representing, bogin-etal-2019-global]
to learn a schema relation-aware entity representation $\bm{H}_{\mathcal{V}}$
by a GNN module.333We choose these models because of the ability of GNNs to
model various types of structural links, and they are among a few state-of-
the-art models that are publicly available at the time of writing. The initial
embedding of each entity $h_{e}^{(0)}$ is defined as a non-linear
transformation of the combination of its type embedding and the average over
the word embeddings of its neighbors in the schema graph. In later time steps,
the hidden state is updated by a gated recurrent unit [cho-etal-2014-learning,
li2015gated] as
$h_{e}^{(l)}=\operatorname{GRU}\left(h_{e}^{(l-1)},x_{e}^{(l)}\right)$, where
the input $x_{e}^{(l)}$ is defined as a weighted summation over the hidden
states of its neighbor entities: x_e^(l)=∑_t∈{←, →,↔} ∑_(s, e, l) ∈E, l=t W_t
h_s^(l-1)+b_t They consider three edge types, i.e., bidirectional edges
between a table and its contained columns $\leftrightarrow$, unidirectional
edges between a foreign key and a connected primary key $\leftarrow$ and its
reverse version $\rightarrow$. Given a fixed GNN recurrence step $L$, we have
the final hidden states of all the entities in the graph as the entity
representation $\bm{H}_{\mathcal{V}}=\\{h_{e}^{(L)}|(e,t)\in\mathcal{V}\\}$.
We also adopt their schema linking module to create a schema linking matrix
$M$ based on word embedding similarity and some simple manually design
features (e.g., editing distance and lemma). In their GlobalGNN [bogin-
etal-2019-global], an additional GNN and an auxiliary training loss are added
to filter out irrelevant nodes in the graph, thus producing a better entity
representation.

To augment our model with pretrained BERT embeddings, we follow ?) and ?) to
feed the concatenation of NL question and the textual descriptions of DB
entities to BERT and use the top layer hidden states of BERT as the input
embeddings.

##  4 Experiments

We evaluate the effectiveness of our proposed method by integrating it into
two state-of-the-art semantic parsers on the Spider dataset and further ablate
out some components to understand their contributions.

###  4.1 Experiment Setup

We implement our model using PyTorch [NEURIPS2019_9015] and AllenNLP [gardner-
etal-2018-allennlp]. For the GNN and GlobalGNN models we revise and build upon
the code released in [bogin-etal-2019-representing, bogin-etal-2019-global].
We re-ran the experiment and report the results on our re-implementation and
found our results slightly improves upon their reported results. In BERT
experiments, we use the base uncased BERT model with 768 hidden size provided
by HuggingFace’s Transformers library [Wolf2019HuggingFacesTS]. We follow the
database split setting of Spider, where any databases that appear at testing
time are ensured to be unseen at training time. Our code and models are
available at https://github.com/sanxing-chen/linking-tale.

Hardness | # Example
---|---
Easy | 250
Medium | 440
Hard | 174
Extra | 170
All | 1034
Table 2: Number of examples in the development set of Spider with different
hardness levels associated with the SQL need to be generated.

Model | Acc. | Easy | Medium | Hard | Extra
---|---|---|---|---|---
GNN | 47.7% | 68.8% | 51.8% | 31.2% | 22.9%
\+ Ours | 50.7% | 66.4% | 54.8% | 42.8% | 25.3%
GlobalGNN | 49.3% | 69.2% | 53.0% | 32.8% | 27.6%
\+ Ours | 52.8% | 70.4% | 55.7% | 46.6% | 25.9%
\+ BERT | 53.5% | 76.0% | 57.3% | 36.2% | 28.3%
\+ BERT + Ours | 57.6% | 73.6% | 61.6% | 48.9% | 32.9%
Table 3: Exact Set Matching Accuracy on SQL queries with different hardness
levels in the development set of Spider. Greatest improvements in the Hard
level; small fluctuation in Easy level due to gate bias.

###  4.2 Experimental Results

The experimental results in Table 3 show that our proposed gating mechanism
leads a substantial improvement on all the GNN, GlobalGNN, and BERT baselines.
Spider questions are divided into different levels of difficulty (hardness).
Most of the improvements come from gains in complicated (i.e., Medium, Hard
and Extra Hard) SQL generation. Specially, we observe up to $13.8\%$ gains in
the Hard set when applying our method on the GlobalGNN baseline. One major
contribution comes from the partial matching F1 score of IUEN (i.e., SQL
clauses INTERSECT, UNION, EXCEPT, NESTED which only appear in Hard and Extra
Hard levels) increasing from $25.4\%$ to $39.7\%$. We also notice that the SQL
output well-formedness is improved. For instance, before applying our method
the decoder would occasionally select the same columns twice to perform the ON
clause.444This is different from the case of intentionally self join. After
applying our dynamic gating, this issue is virtually eliminated (error rate
from $2\%$ to $0.2\%$).555Although this issue can be resolved by engineering
more grammar rules, we leave it as an indicator of the improvement of the
well-formedness of the output SQL.

Figure 3: Value distributions of the link gate and copy gate measured in dev
set of Spider using the GlobalGNN model. Values of copy gate are considered
when the corresponding link gate value is small
($\rho_{\operatorname{link}}<0.1$).

As shown in Figure 3, the values of both gates are polarized to $0$ or $1$,
thus making the gating mechanism act as a binary gate. These statistics
coincide with our hypothesis that _most entity generation decisions in Text-
to-SQL can be solely made by evidence from either schema linking or structural
linking_. In addition, among all the cases where structural linking is chosen
and the copy gate takes control, fewer than 20% of cases favor copying. This
suggests that there are lots of circumstances where different kinds of
structural linking are adopted.

###  4.3 Alternative Approaches and Ablation

We also conduct several experiments to examine several design choices in our
proposed method.

Sharing Action Embedding. In the design of our gating mechanism, one critical
decision is to use the action embedding $\bm{a}_{t}$ to perform decoder self-
attention and produce the gating values. This is based on our intuition that
the action embedding captures the structural information of the output SQL at
the current position. To verify this decision, we conduct an ablation
experiment by using a dedicated embedding to produce the gating value. This
dedicated embedding is produced in exactly same way as we generated
$\bm{a}_{t}$ in Equation 9, but uses a different set of parameters for the
feed-forward network. As we can see from Table 4 (“dedicated embed”), sharing
the parameters with the action embedding is important.

Keeping entities. ?) also uses a memory-augmented pointer network to perform a
copy mechanism which assists column selection. In contrast with our memory
matrix consisting of action embeddings (Equation 7), their memory matrix
consists of the entity embeddings of columns that have been selected
previously. They further remove the columns from the candidates in the schema
linking process once they are generated to prevent the decoder from repeatedly
generating the same columns. To determine if our dynamic gating and structural
linking module can add enough structural constraints to the decoding process
to resolve this kind of problem, we conduct an experiment where we also remove
the entities in the schema linking process after they are generated (i.e.,
“removing entity” in Table 4) to see if it further improves the model. Our
results shows that this change can actually hurts the model. Specifically, we
observe a drop in accuracy of the WHERE and IUEN clauses, which suggests that
in our context, the information about a specific entity in the schema linking
process is still useful even after the entity has been generated once.

Model | Dev Acc. (%)
---|---
GlobalGNN | GlobalBERT
Base | 49.3 | 53.5
Ours | 52.8 | 57.6
dedicated embed | 50.0 | 55.4
removing entity | 49.4 | 57.1
without copy | 50.9 | 55.8

Table 4: Alternative approaches and ablation results.

Copy Gate. In addition, removing the copy gate and copy mechanism also harms
the performance of our model (i.e., “without copy” in Table 4). This result
confirms that it is beneficial to handle different types of structural links
separately. We hypothesize that different types of structural links conflict
with each other, so they are hard to fit in one structural linking matrix.
Overall, these two results further supports our claim that the copy gate can
determine when to copy or link to an entity by itself.

NL |  Show the stadium name and the number of concerts in each stadium.
---|---
SQL |


# Sharp Convergence Rates for Matching Pursuit

Jason M. Klusowski
Department of Operations Research
and Financial Engineering
Princeton University
Princeton, NJ 08544
<EMAIL_ADDRESS>&Jonathan W. Siegel
Department of Mathematics
Texas A&M University
College Station, TX 77843
<EMAIL_ADDRESS>
###### Abstract

We study the fundamental limits of matching pursuit, or the pure greedy
algorithm, for approximating a target function by a sparse linear combination
of elements from a dictionary. When the target function is contained in the
variation space corresponding to the dictionary, many impressive works over
the past few decades have obtained upper and lower bounds on the error of
matching pursuit, but they do not match. The main contribution of this paper
is to close this gap and obtain a sharp characterization of the decay rate of
matching pursuit. Specifically, we construct a worst case dictionary which
shows that the existing best upper bound cannot be significantly improved. It
turns out that, unlike other greedy algorithm variants, the converge rate is
suboptimal and is determined by the solution to a certain non-linear equation.
This enables us to conclude that _any_ amount of shrinkage improves matching
pursuit in the worst case.

##  1 Introduction

Matching pursuit [17] is a widely used algorithm in signal processing that
approximates a target signal by selecting a sparse linear combination of
elements from a given dictionary.

Over the years, matching pursuit has garnered significant attention due to its
effectiveness in capturing essential features of a signal with a parsimonious
representation, offering reduced storage requirements, efficient signal
reconstruction, and enhanced interpretability of the underlying signal
structure. Because of this, its applications span various domains, including
image, video, and audio processing and compression [2, 19].

While previous works have explored the convergence properties of matching
pursuit, several open questions and challenges remain. In particular, the
relationship between the characteristics of the target signal, the chosen
dictionary, and the convergence rate warrants further investigation. The main
objective of this paper is to provide a comprehensive analysis of the
convergence properties of matching pursuit. Understanding the convergence rate
is crucial for assessing the algorithm’s efficiency and determining the number
of iterations required to achieve a desired level of approximation accuracy.

Let $H$ be a Hilbert space and $\mathbb{D}\subset H$ be a symmetric collection
of unit vectors, i.e., $\|d\|=1$ for $d\in\mathbb{D}$ and $d\in\mathbb{D}$
implies $-d\in\mathbb{D}$, called a dictionary. Non-linear dictionary
approximation methods, which attempt to approximate a target function $f$ by a
sparse linear combination

$f\approx\sum_{n=1}^{s}a_{n}d_{n},$ (1)

where both the sequence of dictionary elements $d_{i}\in\mathbb{D}$ and the
coefficients $a_{i}$ depend upon the function $f$ to be approximated, are
common method in machine learning and signal processing. Such methods aim to
generate an approximation of the form (1) with a small number of terms $s$,
and include gradient boosting [9], $L^{2}$-boosting [4], basis pursuit [5],
and matching pursuit [17].

In this work, we consider matching pursuit [17], which is a classical method
for algorithmically generating a convergent non-linear dictionary expansion of
the form

$f=\sum_{n=1}^{\infty}a_{n}d_{n}.$ (2)

Matching pursuit is also known as the pure greedy algorithm [7], and is given
by

$f_{0}=0,~{}d_{n}\in\operatorname*{arg\,max}_{d\in\mathbb{D}}\langle
r_{n-1},d\rangle,~{}f_{n}=f_{n-1}-\langle r_{n-1},d_{n}\rangle d_{n},$ (3)

where $r_{n}=f-f_{n}$ is the residual at step $n$. An equivalent way of
writing this method, which explains the name pure greedy algorithm, is

$(a_{n},d_{n})=\operatorname*{arg\,min}_{a\in\mathbb{R},d\in\mathbb{D}}\left\|f-\left(\sum_{i=1}^{n-1}a_{i}d_{i}+ad\right)\right\|=\operatorname*{arg\,min}_{a\in\mathbb{R},d\in\mathbb{D}}\left\|r_{n-1}-ad\right\|.$
(4)

In each step we add the single term which minimizes the error the most, hence
the name pure greedy algorithm. In other words, we fit a single term to the
residual in each step.

An important variant of this algorithm is the pure greedy algorithm which
shrinkage $0<s\leq 1$, see [29, p. 375], given by

$f_{0}=0,~{}d_{n}\in\operatorname*{arg\,max}_{d\in\mathbb{D}}\langle
r_{n-1},d\rangle,~{}f_{n}=f_{n-1}-s\langle r_{n-1},d_{n}\rangle d_{n}.$ (5)

Here we scale down the greedy term by a factor $s$, called the shrinkage
factor, in each step.

Finding the optimal term $d_{n}$ in (5) could potentially involve solving a
high-dimensional, non-convex optimization problem. To address this
computational issue, gradient tree boosting [9] (i.e., $L^{2}$ boosting)
features an additional step in which $\langle r_{n-1},d\rangle$ is itself
greedily optimized. Here the dictionary consists of normalized piecewise
constant functions (or decision trees), which are fit to the residuals
$r_{n-1}$ via the _CART algorithm_ [3]. While CART is usually not motivated as
a greedy way to optimize the inner product $\langle r_{n-1},d\rangle$ over a
collection of normalized piecewise constant functions, it can be equivalently
formulated as such. To begin, we first find the pair
$(t,j)\in\mathbb{R}\times\mathbb{N}$ such that $\langle r_{n-1},\psi\rangle$
is maximized among all functions, or _decision stumps_ , of the form

$\psi(x)=b_{1}\mathbf{1}(x_{j}\leq t)+b_{2}\mathbf{1}(x_{j}>t),$

where $b_{1}$ and $b_{2}$ are chosen so that $\|\psi\|^{2}=1$ and
$\langle\psi,1\rangle=0$. The splitting of $x$ along the $j$-th direction,
$x_{j}$, at the split point $t$ creates a partition of the $x$-space, or the
root node, into two subcells, or child nodes, namely, $R=\\{x:x_{j}\leq t\\}$
and $R^{\prime}=\\{x:x_{j}>t\\}$. Next, we perform the same step as before,
but this time we restrict $x$ to be in either $R$ or $R^{\prime}$, in turn.
More generally, we divide a cell $R$, or a parent node, into two subcells, or
child nodes, by finding $(t,j)$ such that $\langle r_{n-1},\psi\rangle$ is
maximized among all functions of the form $\psi(x)=b_{1}\mathbf{1}(x_{j}\leq
t,\;x\in R)+b_{2}\mathbf{1}(x_{j}>t,\;x\in R)$, where $b_{1}$ and $b_{2}$ are
chosen so that $\|\psi\|^{2}=1$ and $\langle\psi,1\rangle=0$. This process is
terminated when a desired level of granularity in the partition (or a certain
number of leaf nodes) is reached, yielding a collection of orthonormal
functions $\Psi$, including the constant function $\psi\equiv 1$. The decision
tree output $d_{n}\in\mathbb{D}$ admits the orthogonal expansion

$d_{n}(x)\propto\sum_{\psi\in\Psi}\langle
r_{n-1},\psi\rangle\psi(x),\;\;\text{where}\;\;\langle
r_{n-1},d_{n}\rangle=\sqrt{\sum_{\psi\in\Psi}|\langle
r_{n-1},\psi\rangle|^{2}}.$

Except for decision stumps (or depth-one trees) which involve only a
2-dimensional optimization, understanding the optimization gap for this greedy
heuristic (CART) in general is currently an open problem, one that we do not
address in the present paper. That is, we assume herein that the optimization
problem is solved _exactly_ in (5).

Despite the practical success and great interest generated by the method of
matching pursuit, the precise convergence properties of the algorithm (3) for
general dictionaries $\mathbb{D}$ have not been precisely determined. To
describe this problem, we introduce the variation norm [13, 6] with respect
the the dictionary $\mathbb{D}$, defined by

$\|f\|_{\mathcal{K}_{1}(\mathbb{D})}=\inf\\{t>0:~{}f\in
tB_{1}(\mathbb{D})\\},$ (6)

where the set $B_{1}(\mathbb{D})$ is the closed convex hull of $\mathbb{D}$,
i.e.

$B_{1}(\mathbb{D})=\overline{\left\\{\sum_{i=1}^{N}a_{i}d_{i},~{}a_{i}\geq
0,~{}\sum_{i=1}^{N}a_{i}=1,~{}d_{i}\in\mathbb{D}\right\\}}.$ (7)

This norm is a common measure of complexity when studying non-linear
dictionary approximation, since it is well-defined and useful for any abstract
dictionary $\mathbb{D}\subset H$ [6, 29]. Results for the variation space
$\mathcal{K}_{1}(\mathbb{D})$ can also often be extended to interpolation
spaces which allow an even wider class of target functions to be analyzed [1].

For some context, let us give a few examples of dictionaries $\mathbb{D}$ of
interest and their corresponding variation spaces. For specific dictionaries
of interest, the variation spaces have often been characterized and other
descriptions are available, for instance the Besov space $B^{1}_{1,1}$ is
equivalent to $\mathcal{K}_{1}(\mathbb{D})$ for the dictionary

$\mathbb{D}=\\{e^{(x-c)^{2}/(2\sigma^{2})},~{}c\in\mathbb{R},~{}\sigma>0\\}$
(8)

of Gaussian bumps [18]. Another example are the spaces
$\mathcal{K}_{1}(\mathbb{D})$ for the dictionaries of ridge functions

$\mathbb{D}=\\{\sigma(\omega\cdot x+b),~{}\omega\in
S^{d-1},~{}b\in\mathbb{R}\\}$ (9)

which correspond to shallow neural networks have been characterized and
intensively studied [21, 22, 23, 27, 25, 11, 8]. Here $\sigma=\max(0,x)^{k}$
is the popular ReLUk activation function.

Typically the convergence of abstract greedy algorithms is studied on the
variation space $\mathcal{K}_{1}(\mathbb{D})$ [29]. For instance, it is shown
in [7] that the pure greedy algorithm (3) satisfies

$\|f-f_{n}\|\leq\|f\|_{\mathcal{K}_{1}(\mathbb{D})}n^{-1/6}.$ (10)

This was subsequently improved by Konyagin and Temylakov [12] to

$\|f-f_{n}\|\leq C\|f\|_{\mathcal{K}_{1}(\mathbb{D})}n^{-11/62},$ (11)

and finally by Sil’nichenko [28] to

$\|f-f_{n}\|\leq C\|f\|_{\mathcal{K}_{1}(\mathbb{D})}n^{-\alpha},$ (12)

where $\alpha=\gamma/(2(2+\gamma))\approx 0.182$ and $\gamma>1$ is a root of
the non-linear equation

$(1+\gamma)^{\frac{1}{2+\gamma}}\left(1+\frac{1}{1+\gamma}\right)-1-\frac{1}{\gamma}=0.$
(13)

For the pure greedy algorithm with shrinkage (5) the method of Sil’nichenko
implies that

$\|f-f_{n}\|\leq C\|f\|_{\mathcal{K}_{1}(\mathbb{D})}n^{-\alpha},$ (14)

where $\alpha=\gamma/(2(2+\gamma))$ and $\gamma>1$ is a root of the non-linear
equation

$(1+\gamma)^{\frac{1}{2+\gamma}}\left(1+\frac{1}{1+\gamma}\right)-1-\frac{2-s}{\gamma}=0.$
(15)

As $s\rightarrow 0$, the exponent $\alpha\approx 0.305$ (c.f., the exponent
$2/7\approx 0.285$ obtained in [20]). On the other hand, for functions
$f\in\mathcal{K}_{1}(\mathbb{D})$ it is known [24, 10] that for each $n$ there
exists an approximation

$f_{n}=\sum_{i=1}^{n}a_{i}d_{i},$ (16)

such that $\|f-f_{n}\|\leq\|f\|_{\mathcal{K}_{1}(\mathbb{D})}n^{-1/2}$, and
that the exponent $n^{-1/2}$ is optimal for all dictionaries and
$f\in\mathcal{K}_{1}(\mathbb{D})$ [13].

Thus, in general the best we could hope for in the convergence of matching
pursuit is a convergence rate like $n^{-1/2}$, which is attained by other
greedy algorithms such as the orthogonal or related greedy algorithm [7, 10]
(in fact, the orthogonal greedy algorithm has been shown to converge even
faster for compact dictionaries [26, 14]). Remarkably, the convergence of
matching pursuit is strictly worse. Specifically, it was shown in [16] that
there exists a dictionary $\mathbb{D}\subset H$ and an
$f\in\mathcal{K}_{1}(\mathbb{D})$ such that the iterates of the pure greedy
algorithm (3) satisfy

$\|f-f_{n}\|\geq C\|f\|_{\mathcal{K}_{1}(\mathbb{D})}n^{-0.27}.$ (17)

This estimate was finally improved in [15] to

$\|f-f_{n}\|\geq C\|f\|_{\mathcal{K}_{1}(\mathbb{D})}n^{-0.1898}.$ (18)

Comparing the estimates (12) and (18) we see that there is a still a
significant, though small, gap between the best upper and lower bounds. The
goal of this work is to close this gap nearly completely. We show the
following.

######  Theorem 1.

Let $\gamma>1$ be the root of the equation (13). Then for every
$\alpha>\gamma/(2(2+\gamma))$, there exists a dictionary $\mathbb{D}\subset H$
and a function $f\in\mathcal{K}_{1}(\mathbb{D})$ such that the iterates of the
pure greedy algorithm (i.e., matching pursuit) (3) satisfy

$\|f-f_{n}\|\geq C\|f\|_{\mathcal{K}_{1}(\mathbb{D})}n^{-\alpha}.$ (19)

Combined with the upper bound (12), this gives a precise characterization of
the exponent in the convergence rate of matching pursuit and therefore makes
significant progress towards solving an open problem posed in [29], that is,
to find the order of decay of the pure greedy algorithm. Additionally, this
shows that the rate of convergence with shrinkage $s<1$ is strictly better
than for $s=1$, i.e., that any amount of shrinkage improves the algorithm in
the worst case, lending theoretical support to the empirical observation that
some shrinkage in gradient tree boosting can result in significant performance
improvements.

Although we do not give all of the details, our method shows that the rate
obtained by Sil’nichenko (14) is optimal also for shrinkage $s_{0}<s<1$ for a
numerically computable value $s_{0}$. However, for sufficiently small
shrinkage $s$ our method breaks down and it is an open problem to determine
the rate of convergence as $s\rightarrow 0$.

##  2 Construction of the Worst-Case Dictionary

In this section, we give the proof of Theorem 1. This is based upon an
extension and optimization of the constructions developed in [16, 15].

###  2.1 Basic Construction

We let $H=\ell^{2}$ and denote by $\\{e_{n}\\}_{n=1}^{\infty}$ its standard
basis. Let $0<\beta<\frac{1}{2}$. We will attempt to construct a realization
of the pure greedy algorithm (3), i.e., a dictionary $\mathbb{D}\subset H$ and
an initial iterate $f\in\mathcal{K}_{1}(\mathbb{D})$, for which the
convergence rate is bounded below by

$\|f-f_{n}\|\geq Cn^{-\frac{1}{2}+\beta}.$

We will show that this construction succeeds as long as

$\left(\frac{\beta}{1-\beta}\right)^{\beta}\left(\frac{(1-\beta)^{2}}{1-2\beta}\right)<1.$
(20)

Let us begin by verifying that this implies Theorem 1. It suffices to show
that with equality in (20), we have

$\alpha=\frac{1}{2}-\beta=\frac{\gamma}{(2(2+\gamma))},$ (21)

where $\gamma$ is the root of (13). Solving the relation (21) for $\gamma$ in
terms of $\beta$ we get

$\gamma=\frac{1-2\beta}{\beta}.$ (22)

Plugging this into (13), we readily see that (13) is equivalent to equality in
(20).

Let us proceed with the lower bound construction. It will be convenient in
what follows to work with the residual form of the pure greedy algorithm,
given by

$r_{0}=f_{0},~{}d_{n}\in\operatorname*{arg\,min}_{d\in\mathbb{D}}\langle
r_{n-1},d\rangle,~{}r_{n}=r_{n-1}-\langle r_{n-1},d_{n}\rangle d_{n}.$ (23)

To begin the construction, let $K>1$ be an integer to be determined later. Let
$\\{h_{n}\\}_{n=K}^{\infty}\subset H$ be a sequence of elements of $H$ which
satisfy $h_{n}\in\text{span}(e_{1},...,e_{n-1})$, which are a parameter of the
construction that we leave unspecified for now. Define two sequences of
elements $\\{r_{n}\\}_{n=K-1}^{\infty}\subset H$ and
$\\{d_{n}\\}_{n=K}^{\infty}\subset H$ inductively by

$\begin{split}r_{K-1}&=-\frac{C_{K}}{\sqrt{K-1}}\sum_{i=1}^{K-1}e_{i},\\\
d_{n}&=\gamma_{n}r_{n-1}+h_{n}+\xi_{n}e_{n},\\\
r_{n}&=r_{n-1}-q_{n}d_{n}.\end{split}$ (24)

Here $C_{K},\gamma_{n},\xi_{n}$ and $q_{n}$ are parameters, which are chosen
so that

$\|r_{n}\|=(n+1)^{-\frac{1}{2}+\beta},~{}q_{n}=\langle
r_{n-1},d_{n}\rangle,~{}\text{and}~{}\|d_{n}\|=1.$ (25)

These conditions immediately determine $C_{K}$ and $q_{n}$. Specifically, we
calculate $C_{K}=\|r_{K-1}\|=K^{-\frac{1}{2}+\beta}$ and

$\|r_{n}\|^{2}=\|r_{n-1}\|^{2}-q_{n}^{2}.$ (26)

This implies that

$q_{n}^{2}=\|r_{n-1}\|^{2}-\|r_{n}\|^{2}=n^{-1+2\beta}-(n+1)^{-1+2\beta}.$
(27)

Further, we set $\gamma_{n}=(q_{n}^{-1}-q_{n-1}^{-1})$. The conditions (25)
and the construction (24) imply that

$q_{n}=\langle r_{n-1},g_{n}\rangle=\gamma_{n}\|r_{n-1}\|^{2}+\langle
r_{n-1},h_{n}\rangle=\gamma_{n}n^{-1+2\beta}+\langle r_{n-1},h_{n}\rangle,$
(28)

which means that we must ensure that our choice of $h_{n}$ satisfies

$\langle r_{n-1},h_{n}\rangle=q_{n}-\gamma_{n}n^{-1+2\beta}.$ (29)

Next, since we require that $h_{n}\in\text{span}(e_{1},...,e_{n-1})$, we see
by induction that $d_{n},r_{n}\in\text{span}(e_{1},...,e_{n-1})$. Using the
construction (24) this implies that

$1=\|d_{n}\|^{2}=\|\gamma_{n}r_{n-1}+h_{n}\|^{2}+\xi_{n}^{2}.$ (30)

This means that our parameter $h_{n}$ must satisfy
$\|\gamma_{n}r_{n-1}+h_{n}\|\leq 1$. We now solve equation (30) for $\xi_{n}$
and choose $\xi_{n}=\sqrt{1-\|\gamma_{n}r_{n-1}+h_{n}\|^{2}}$ to be the
positive root.

Finally, we choose parameters $N>K$ sufficiently large and $\epsilon>0$
sufficiently small, and set

$\begin{split}f&=r_{N},\\\
\tilde{d}_{N}&=\epsilon\frac{r_{N}}{\|r_{N}\|}+\sqrt{1-\epsilon^{2}}d_{N},\\\
\mathbb{D}&=\\{\tilde{d}_{N}\\}\cup\\{d_{n}\\}_{n\geq N}.\end{split}$ (31)

From (24) and (25), we see that $\langle r_{N},d_{N}\rangle=\langle
r_{N-1}-q_{N}d_{N},d_{N}\rangle=0$. This implies that $\|\tilde{d}_{N}\|=1$
and that

$\langle f,\tilde{d}_{N}\rangle=\epsilon\|r_{N}\|.$ (32)

It is also clear that $f\in\text{span}(\tilde{g}_{N},g_{N})$, so that
$\|f\|_{\mathcal{K}_{1}(\mathbb{D})}<\infty$.

Note that everything has been determined up until this point except the
sequence $h_{n}$ and the parameters $K,N$, and $\epsilon$. The proof will
proceed as follows. First, we will choose a sequence $h_{n}$ which is
parameterized by a function $\phi$. Then, we will show that for sufficiently
large $K$ conditions (29) and (30) are satisfied, which implies that the
recursive construction (24) can be carried out. Next, we will derive
conditions on $\phi$ which guarantee that for sufficiently large $N$ and
sufficiently small $\epsilon$ we have

$|\langle r_{n-1},\tilde{d}_{N}\rangle|<q_{n}~{}\text{and}~{}|\langle
r_{n-1},d_{k}\rangle|<q_{n}$ (33)

for each $n>N$ and $k\geq N$ with $k\neq n$. This implies that $r_{n}$ for
$n\geq N$ is a realization of the pure greedy algorithm (23) with step size
$s$ for the dictionary $\mathbb{D}$ and the target function $f$. Finally, we
will optimize the parameter $\beta$ subject to the existence of a function
$\phi$ which satisfies the required conditions.

###  2.2 Inner Product Formulas

We begin by deriving formulas for the inner products in (33), following [15,
16]. Consider the case $k<n$. Combining the last two equations in (24) we see
that

$r_{m}=(1-q_{m}\gamma_{m})r_{m-1}-q_{m}h_{m}-q_{m}\xi_{m}e_{m}.$ (34)

Plugging the choice $\gamma_{m}=q_{m}^{-1}-q_{m-1}^{-1}$ into this, we get

$r_{m}=\frac{q_{m}}{q_{m-1}}r_{m-1}-q_{m}h_{m}-q_{m}\xi_{m}e_{m}.$ (35)

Taking the inner product with $d_{k}$, noting that
$d_{k}\in\text{span}(e_{0},...,e_{k})$, and assuming that $k<m$, we get

$\langle r_{m},d_{k}\rangle=\frac{q_{m}}{q_{m-1}}\langle r_{m-1},d_{k}\rangle-
q_{m}\langle h_{m},d_{k}\rangle.$ (36)

Using (25) and the last line in (24), we see that by construction $\langle
r_{k},d_{k}\rangle=0$. From this and the preceding equation we see by
induction on $m$ that

$\langle r_{n-1},d_{k}\rangle=-q_{n-1}\left(\sum_{i=k+1}^{n-1}\langle
h_{i},d_{k}\rangle\right)$ (37)

for $k<n$.

The case of $\langle r_{n-1},\tilde{d}_{N}\rangle$ is a bit more complicated.
We use the relation (32) as a base case in the induction to get

$\langle r_{n-1},\tilde{d}_{N}\rangle=-q_{n-1}\left(\sum_{i=N+1}^{n-1}\langle
h_{i},\tilde{d}_{N}\rangle-\epsilon\frac{\|r_{N}\|}{q_{N}}\right).$ (38)

Next, we consider the case $k>n$. In this case the relations (24) give, for
$k>n$

$\langle r_{n-1},d_{k}\rangle=\gamma_{k}\langle r_{n-1},r_{k-1}\rangle+\langle
r_{n-1},h_{k}\rangle,$ (39)

since $r_{n-1}\in\text{span}(e_{0},...,e_{n-1})$. Further, we see that

$\langle r_{n-1},r_{k-1}\rangle=\langle r_{n-1},r_{k-2}\rangle-q_{k-1}\langle
r_{n-1},d_{k-1}\rangle.$ (40)

Shifting the indices in (39) we also get

$\langle r_{n-1},d_{k-1}\rangle=\gamma_{k-1}\langle
r_{n-1},r_{k-2}\rangle+\langle r_{n-1},h_{k-1}\rangle.$ (41)

Solving this equation for $\langle r_{n-1},r_{k-2}\rangle$ and plugging that
back into equations (39) and (40), we get the inductive relation

$\langle r_{n-1},d_{k}\rangle=(\gamma_{k-1}^{-1}-q_{k-1})\gamma_{k}\langle
r_{n-1},d_{k-1}\rangle+\left\langle
r_{n-1},h_{k}-\frac{\gamma_{k}}{\gamma_{k-1}}h_{k-1}\right\rangle.$ (42)

###  2.3 Initial Asymptotics

Our goal will be to show that the construction detailed in (31) is valid and
satisfies the conditions (33) for sufficiently large $K,N$ and sufficiently
small $\epsilon$. For this purpose, we will evaluate asymptotics of some of
the parameters introduced so far, which we collect here. These asymptotics
were first derived in [15, 16].

We use the notation from [15]. In particular, for a sequence $y_{n}$ we write
$y_{n}\eqsim bn^{\alpha}$ if $y_{n}=bn^{\alpha}(1+c/n+O(n^{-2}))$ for some
$c$. We have from (27) that

$q_{n}^{2}\eqsim(1-2\beta)n^{-2+2\beta}.,$ (43)

which implies that

$q_{n}\eqsim\sqrt{1-2\beta}n^{\beta-1}.$ (44)

From this, we obtain the following asymptotics for $\gamma_{n}$,

$\gamma_{n}=(q_{n}^{-1}-q_{n-1}^{-1})\eqsim\frac{(1-\beta)}{\sqrt{1-2\beta}}n^{-\beta}(1+O(n^{-1})).$
(45)

These two formulas give us the asymptotics of the right hand side of (29)

$q_{n}-\gamma_{n}n^{-1+2\beta}=\left(\sqrt{1-2\beta}-\frac{(1-\beta)}{\sqrt{1-2\beta}}\right)n^{\beta-1}(1+O(n^{-1}))=\frac{-\beta}{\sqrt{1-2\beta}}n^{\beta-1}(1+O(n^{-1})).$
(46)

Finally, we will also need the asymptotics for the inductive factor in (42)

$(\gamma_{m-1}^{-1}-sq_{m-1})\gamma_{m}=\frac{\gamma_{m}}{\gamma_{m-1}}(1-s\gamma_{m-1}q_{m-1})=\frac{\gamma_{m}}{\gamma_{m-1}}\frac{q_{m-1}}{q_{m-2}}.$
(47)

The asymptotics for $\gamma_{m}$ (45) and the asymptotics for $q_{n}$ (44)
imply that

$\frac{\gamma_{m}}{\gamma_{m-1}}=\left(1-\frac{\beta}{m}+o(m^{-1})\right),~{}\frac{q_{m-1}}{q_{m-2}}=\left(1+\frac{\beta-1}{m}+o(m^{-1})\right).$
(48)

Multiplying these, we get

$(\gamma_{m-1}^{-1}-sq_{m-1})\gamma_{m}=(1-(1+o_{m}(1))m^{-1}).$ (49)

Note that here and in the following, we use the notation $o_{k}(1)$ to denote
a quantity depending upon the parameter $k$ whose limit is $0$ as
$k\rightarrow\infty$. We also adopt the convention that the constants in
big-$O$ expressions and the rate of decay to $0$ in little-$o$ expressions
will be uniform in any lower case indices $n,m,k,$ or $l$ which do not appear
in the argument (or the subscript if the argument is $1$), but may depend upon
other parameters of the construction.

Finally, we recall the basic fact, which we will use without reference in the
following, that (using this convention)

$\frac{1}{n}\sum_{k=1}^{n}o_{k}(1)=o_{n}(1).$ (50)

###  2.4 Choice of Main Parameter

So far we have specified all parameters in the construction except the
sequence $h_{n}$, which we proceed to describe in this section. Recalling the
preceding construction, in doing so we must ensure that
$h_{n}\in\text{span}(e_{0},...,e_{n-1})$, that condition (29) is satisfied,
and that $\|\gamma_{n}r_{n-1}+h_{n}\|\leq 1$ in order to define $\xi_{n}$ via
(30).

Let $\phi:[0,1]\rightarrow\mathbb{R}_{\geq 0}$ be a non-zero $C^{\infty}$
function such that for some $\delta>0$, we have $\phi(x)=0$ on $[0,\delta]$.
Define $h_{n}$ by the relation

$h_{n}=\sum_{i=1}^{n-1}\frac{\alpha_{n}}{n}\phi\left(\frac{i}{n}\right)e_{i}.$
(51)

Here the parameters $\alpha_{n}$ are chosen so that the relation (29) is
satisfied, i.e., such that $\langle
r_{n-1},h_{n}\rangle=q_{n}-\gamma_{n}n^{-1+2\beta}$.

We must ensure that (51) and (29) can always be solved for $\alpha_{n}$ and
that the resulting value satisfies $\|\gamma_{n}r_{n-1}+h_{n}\|\leq 1$, so
that we can define $\xi_{n}$ via (30). We proceed to show that for
sufficiently large $K$, this will always be the case. For this, we will need
the following formula for the coefficients of $r_{n}$, which will also be
useful later.

######  Lemma 1.

The following formula holds for $K\leq k\leq n$

$\langle r_{n},e_{k}\rangle=-sq_{n}\left(\xi_{k}+\sum_{j=k+1}^{n}\langle
h_{j},e_{k}\rangle\right).$ (52)

Further, for $0<k\leq K-1\leq n$, we have

$\langle
r_{n},e_{k}\rangle=-q_{n}\left(\frac{C_{K-1}}{q_{K-1}\sqrt{K-1}}+\sum_{j=K}^{n}\langle
h_{j},e_{k}\rangle\right).$ (53)

Since we also have $\langle r_{n},e_{k}\rangle=0$ for $k>n$, this lemma gives
the components of all of the iterates $r_{n}$.

###### Proof.

We prove this formula for any fixed $k>0$ by induction on $n$. The base case
follows in the case where $k\geq K$ from

$\langle r_{k},e_{k}\rangle=\langle
r_{k-1}-q_{k}d_{k},e_{k}\rangle=-q_{k}\langle
g_{k},e_{k}\rangle=-q_{k}\xi_{k}$ (54)

since $r_{k-1},h_{k}\in\text{span}(e_{0},...,e_{n-1})$. For $k\leq K-1$, we
use the definition of $r_{K-1}$ to get (53) in the case $n=K-1$.

The inductive step follows from (35) since

$\langle r_{n},e_{k}\rangle=\frac{q_{n}}{q_{n-1}}\langle r_{n-1},e_{k}\rangle-
q_{n}\langle h_{n},e_{k}\rangle.$ (55)

Using the inductive hypothesis, this gives

$\langle
r_{n},e_{k}\rangle=-\frac{q_{n}}{q_{n-1}}q_{n-1}\left(\xi_{k}+\sum_{j=k+1}^{n-1}\langle
h_{j},e_{k}\rangle\right)-q_{n}\langle
h_{n},e_{k}\rangle=-q_{n}\left(\xi_{k}+\sum_{j=k+1}^{n}\langle
h_{j},e_{k}\rangle\right),$ (56)

when $k\geq K$, and similarly when $k\leq K-1$.

∎

Using this, we prove the following fundamental result showing that the given
choice of $h_{n}$ results in a valid construction for sufficiently large $K$.

######  Proposition 1.

Let $\phi:[0,1]\rightarrow\mathbb{R}_{\geq 0}$ be a non-zero $C^{\infty}$
function. Then for sufficiently large $K$, we will be able to solve equations
(51) and (29) for $\alpha_{n}$. In addition, $\alpha_{n}$ will be non-negative
and that the resulting value of $h_{n}$ will satisfy
$\|\gamma_{n}r_{n-1}+h_{n}\|\leq 1$, so that we can define $\xi_{n}$ via (30).
Moreover, the construction will also satisfy

$\lim_{n\rightarrow\infty}\xi_{n}=1.$ (57)

###### Proof.

Note that since $\phi\neq 0$, we have

$\int_{0}^{1}\phi(x)dx=C_{\phi}>0.$ (58)

We begin by calculating the inner product $\langle r_{n-1},h_{n}\rangle$ for
$n\geq K$ using Lemma 1 and the definition of $h_{n}$ in (51). We get

$\begin{split}\langle r_{n-1},h_{n}\rangle=\sum_{k=1}^{n-1}\langle
r_{n-1},e_{k}\rangle\langle
h_{n},e_{k}\rangle=&-\frac{q_{n-1}\alpha_{n}}{n}\left(\sum_{k=1}^{n-1}\sum_{j=\max(k+1,K)}^{n-1}\frac{\alpha_{j}}{j}\phi\left(\frac{k}{n}\right)\phi\left(\frac{k}{j}\right)\right.\\\
&+\left.\frac{C_{K-1}}{q_{K-1}\sqrt{K-1}}\sum_{k=1}^{K-1}\phi\left(\frac{k}{n}\right)+\sum_{k=K}^{n-1}\xi_{k}\phi\left(\frac{k}{n}\right)\right).\end{split}$
(59)

Next, since $C_{K-1}=K^{-\frac{1}{2}+\beta}$, we use the asymptotics (44) to
see that

$\lim_{K\rightarrow\infty}\frac{C_{K-1}}{q_{K-1}\sqrt{K-1}}=\frac{1}{\sqrt{1-2\beta}}>1.$
(60)

In addition, by assumption $\phi$ is Riemann integrable. Thus we have

$\lim_{K\rightarrow\infty}\frac{1}{K}\sum_{k=1}^{K-1}\phi\left(\frac{k}{K}\right)=C_{\phi}.$
(61)

Using these facts, that $\|r_{n-1}\|=n^{-\frac{1}{2}+\beta}$ by construction,
and the asymptotics in (44), (45) and (46), we see that we can choose $K$
large enough such that the following conditions hold:

  1. 1.

$\frac{C_{K-1}}{q_{K-1}\sqrt{K-1}}\geq\frac{1}{2}$.

  2. 2.

For some $C_{q}>0$ and any $n\geq K$, we have $q_{n}\geq C_{q}n^{\beta-1}$.

  3. 3.

For some $C_{\gamma}>0$ and any $n\geq K$, we have $0\geq
q_{n}-\gamma_{n}n^{-1+2\beta}\geq-C_{\gamma}n^{\beta-1}$.

  4. 4.

For any $n\geq K$, we have

$\frac{1}{n}\sum_{k=1}^{n-1}\phi\left(\frac{k}{n}\right)\geq\frac{C_{\phi}}{2}.$
(62)

  5. 5.

For any $n\geq K$, we have

$\gamma_{n}\|r_{n-1}\|+\frac{4C_{\gamma}}{C_{\phi}C_{q}}\left[\sup_{x\in[0,1]}\phi(x)\right]n^{-\frac{1}{2}}\leq\frac{\sqrt{3}}{2}.$
(63)

We proceed to show by induction on $n\geq K$ that we can solve (51) and (29)
for $\alpha_{n}\geq 0$, and that the resulting $h_{n}$ will satisfy (29) and
$\|\gamma_{n}r_{n-1}+h_{n}\|\leq\frac{\sqrt{3}}{2}$, which implies that for
the $\xi_{n}$ satisfying (30) we will have $\xi_{n}\geq\frac{1}{2}$.

So assume inductively that for all $K\leq k<n$ we have
$\xi_{k}\geq\frac{1}{2}$ and $\alpha_{k}\geq 0$. (Note that in the base case
$n=K$ there is nothing to prove.) Since $\phi\geq 0$, we use the inductive
assumption on $\alpha_{k}$ to remove the initial double sum on the right hand
side of (59) and get the inequality

$\langle
r_{n-1},h_{n}\rangle\leq-\frac{q_{n-1}\alpha_{n}}{n}\left(\frac{C_{K-1}}{q_{K-1}\sqrt{K-1}}\sum_{k=1}^{K-1}\phi\left(\frac{k}{n}\right)+\sum_{k=K}^{n-1}\xi_{k}\phi\left(\frac{k}{n}\right)\right).$
(64)

We see from (64), the inductive hypothesis on $\xi_{k}$, and conditions 1, 2,
and 62 that

$\langle r_{n-1},h_{n}\rangle\leq-\alpha_{n}\frac{C_{\phi}C_{q}}{4}.$ (65)

This, combined with condition 3 implies that we solve (51) and (29) for
$\alpha_{n}$ which satisfies the bound

$0\leq\alpha_{n}\leq\frac{4C_{\gamma}}{C_{\phi}C_{q}}.$ (66)

Next, we estimate, using the definition of $h_{n}$ (51),

$\|\gamma_{n}r_{n-1}+h_{n}\|\leq\gamma_{n}\|r_{n-1}\|+\|h_{n}\|\leq\gamma_{n}\|r_{n-1}\|+\alpha_{n}\left[\sup_{x\in[0,1]}\phi(x)\right]n^{-\frac{1}{2}}.$
(67)

Finally, using condition 63 and (66), we get that

$\|\gamma_{n}r_{n-1}+h_{n}\|\leq\frac{\sqrt{3}}{2},$ (68)

which completes the inductive step. Moreover, the bound on $\alpha_{n}$ (66)
and the estimate (67) imply that

$\lim_{n\rightarrow\infty}\|\gamma_{n}r_{n-1}+h_{n}\|=0,$ (69)

from which it follows that $\lim_{n\rightarrow\infty}\xi_{n}=1$. This
completes the proof. ∎

Finally, we will need an estimate relating sums to integrals of $\phi$ in the
following, which we collect here.

######  Lemma 2.

Suppose that $\phi:[0,1]\rightarrow\mathbb{R}_{\geq 0}$ is a $C^{\infty}$
function such that for some $\delta>0$, we have $\phi(x)=0$ on $[0,\delta]$.
Let $n\geq l\geq k$, then we have

$\sum_{j=l}^{n-1}\frac{1}{j}\phi\left(\frac{k}{j}\right)=\int_{\frac{k}{n}}^{\frac{k}{l}}\phi(x)\frac{dx}{x}+O(k^{-1}).$
(70)

Recall that by our convention the constant in $O(k^{-1})$ only depends upon
$\phi$ and not upon $n$ and $l$.

###### Proof.

Consider the sequence of $n-l$ points

$x_{0}:=\frac{k}{n}<x_{1}:=\frac{k}{n-1}<\cdots<x_{n-l-1}:=\frac{k}{l+1}<x_{n-l}:=\frac{k}{l}.$
(71)

This sequence of points forms a partition $\Delta$ of the interval
$[\frac{k}{n},\frac{k}{l}]$ and the gap (or mesh/norm) of $\Delta$ satisfies

$|\Delta|:=\sup_{i}|x_{i+1}-x_{i}|\leq\frac{k}{l}-\frac{k}{l+1}=\frac{k}{l(l+1)}<\frac{1}{k}.$
(72)

Moreover, we have the following estimate

$\log\left(\frac{k}{j}\right)-\log\left(\frac{k}{j+1}\right)=\log\left(\frac{j+1}{j}\right)=\log\left(1+\frac{1}{j}\right)=\frac{1}{j}+O\left(\frac{1}{j^{2}}\right).$
(73)

Since $\phi$ is bounded, we obtain

$\begin{split}\sum_{j=l}^{n-1}\frac{1}{j}\phi\left(\frac{k}{j}\right)&=\sum_{i=1}^{n-l}\phi\left(\frac{k}{j}\right)\left[\log\left(\frac{k}{j}\right)-\log\left(\frac{k}{j+1}\right)\right]+O\left(\sum_{j=l}^{n-1}\frac{1}{j^{2}}\right)\\\
&=\sum_{i=1}^{n-l}\phi(x_{i})[\log(x_{i})-\log(x_{i-1})]+O(k^{-1}).\end{split}$
(74)

Finally, since $\phi$ is smooth and $\log(x)$ is increasing and bounded on
$[\delta,1]$, we obtain, by comparing with the Riemann-Stieltjes integral and
using that the mesh $\Delta$ satisfies $|\Delta|<k^{-1}$,

$\sum_{i=1}^{n-l}\phi(x_{i})[\log(x_{i})-\log(x_{i-1})]=\int_{\frac{k}{n}}^{\frac{k}{l}}\phi(x)d\log(x)+O(k^{-1})=\int_{\frac{k}{n}}^{\frac{k}{l}}\phi(x)\frac{dx}{x}+O(k^{-1}).$
(75)

∎

###  2.5 Main Estimates

In the following analysis, we assume that $K$ has been chosen sufficiently
large so that the conclusion of Proposition 1 holds.

Similar to the argument given in [15], the next step will be to study the
asymptotics of the sequence $\alpha_{n}$. We also give an asymptotic formula
for the coefficients of $r_{n}$.

######  Proposition 2.

Suppose that $\phi$ satisfies

$\left(\int_{0}^{1}\phi(x)\left(1+\int_{x}^{1}\phi(z)\frac{dz}{z}\right)dx\right)=\frac{\beta}{1-2\beta}.$
(76)

Then, in the preceding construction, with $K$ chosen large enough such that
the conclusion of Proposition 1 holds, the sequence $\alpha_{n}$ in (51) will
satisfy

$\lim_{n\rightarrow\infty}\alpha_{n}=1.$ (77)

Moreover, the sequence $\alpha_{n}$ will satisfy

$\lim_{n\rightarrow\infty}\frac{\alpha_{n+1}}{\alpha_{n}}=1+o(n^{-1}).$ (78)

In addition, under these conditions as $k\rightarrow\infty$ we will have the
following asymptotics for the coefficients of $r_{n}$

$\langle
r_{n},e_{k}\rangle=-q_{n}\left(1+\int_{\frac{k}{n}}^{1}\phi(z)\frac{dz}{z}+o_{k}(1)\right)$
(79)

for any $n\geq k$. (Recall that by our convention $o_{k}(1)$ goes to $0$ as
$k\rightarrow\infty$ uniformly in $n$.)

###### Proof.

The proof is quite similar to the proof of Lemma 2 in [15]. Suppose that

$\liminf_{n\rightarrow\infty}\alpha_{n}\geq\alpha_{0}.$ (80)

Using the formula (59), we see that

$\begin{split}\liminf_{n\rightarrow\infty}\frac{-\langle
r_{n-1},h_{n}\rangle}{q_{n-1}\alpha_{n}}\geq&\left(\alpha_{0}\lim_{n\rightarrow\infty}\frac{}{n}\left[\sum_{k=1}^{n-1}\sum_{j=\max(k+1,K)}^{n-1}\frac{1}{j}\phi\left(\frac{k}{n}\right)\phi\left(\frac{k}{j}\right)\right]\right.\\\
&+\left.\lim_{n\rightarrow\infty}\frac{1}{n}\left[\frac{C_{K-1}}{q_{K-1}\sqrt{K-1}}\sum_{k=1}^{K-1}\phi\left(\frac{k}{n}\right)+\sum_{k=K}^{n-1}\xi_{k}\phi\left(\frac{k}{n}\right)\right]\right).\end{split}$
(81)

We proceed to evaluate the limits in the above equation. Using the fact that
$\phi$ is Riemann integrable, that $K$ is fixed and that $\xi_{k}\rightarrow
1$ as $k\rightarrow\infty$, we easily see that

$\lim_{n\rightarrow\infty}\frac{1}{n}\left[\frac{C_{K-1}}{q_{K-1}\sqrt{K-1}}\sum_{k=1}^{K-1}\phi\left(\frac{k}{n}\right)+\sum_{k=K}^{n-1}\xi_{k}\phi\left(\frac{k}{n}\right)\right]=\int_{0}^{1}\phi(x)dx.$
(82)

Further, applying Lemma 2 to $\phi$, we see that

$\sum_{j=\max(k+1,K)}^{n-1}\frac{1}{j}\phi\left(\frac{k}{j}\right)=\int_{\frac{k}{n}}^{\min\left(1,\frac{k}{K}\right)}\phi\left(z\right)\frac{dz}{z}+O(k^{-1}).$
(83)

From this, by comparing a Riemann sum with an integral, we see that

$\begin{split}\lim_{n\rightarrow\infty}\frac{1}{n}\left[\sum_{k=1}^{n-1}\sum_{j=\max(k+1,K)}^{n-1}\frac{1}{j}\phi\left(\frac{k}{n}\right)\phi\left(\frac{k}{j}\right)\right]&=\lim_{n\rightarrow\infty}\frac{1}{n}\left[\sum_{k=1}^{n-1}\phi\left(\frac{k}{n}\right)\left[\int_{\frac{k}{n}}^{\min\left(1,\frac{k}{K}\right)}\phi\left(z\right)\frac{dz}{z}\right]+O\left(\sum_{k=1}^{n-1}k^{-1}\right)\right]\\\
&=\lim_{n\rightarrow\infty}\left[\frac{1}{n}\sum_{k=1}^{n-1}\phi\left(\frac{k}{n}\right)\left[\int_{\frac{k}{n}}^{\min\left(1,\frac{k}{K}\right)}\phi\left(z\right)\frac{dz}{z}\right]+O\left(\frac{\log{n}}{n}\right)\right]\\\
&=\lim_{n\rightarrow\infty}\left[\frac{1}{n}\sum_{k=1}^{n-1}\phi\left(\frac{k}{n}\right)\left[\int_{\frac{k}{n}}^{1}\phi\left(z\right)\frac{dz}{z}\right]-\frac{1}{n}\sum_{k=1}^{K}\phi\left(\frac{k}{n}\right)\int_{\frac{k}{K}}^{1}\phi(z)\frac{dz}{z}\right]\\\
&=\int_{0}^{1}\phi(x)\left(\int_{x}^{1}\phi(z)\frac{dz}{z}\right)dx,\end{split}$
(84)

since for large enough $n$, $\phi(k/n)=0$ for $k=1,...,K$ (recall that $\phi$
is assumed to vanish on $[0,\delta]$ for some $\delta$).

Plugging this into (81), we get

$\liminf_{n\rightarrow\infty}\frac{-\langle
r_{n-1},h_{n}\rangle}{q_{n-1}\alpha_{n}}\geq\left(\int_{0}^{1}\phi(x)\left(1+\alpha_{0}\int_{x}^{1}\phi(z)\frac{dz}{z}\right)dx\right).$
(85)

Utilizing the asymptotics (44) and (46), we obtain that

$\lim_{n\rightarrow\infty}\frac{-\langle
r_{n-1},h_{n}\rangle}{q_{n-1}}=\frac{\beta}{1-2\beta}.$ (86)

Together with (85), this implies that

$\limsup_{n\rightarrow\infty}\alpha_{n}\leq\left[\frac{\beta}{1-2\beta}\right]\left(\int_{0}^{1}\phi(x)\left(1+\alpha_{0}\int_{x}^{1}\phi(z)\frac{dz}{z}\right)dx\right)^{-1}.$
(87)

In an entirely analogous manner, we prove that
$\limsup_{n\rightarrow\infty}\alpha_{n}\leq\alpha_{0}$ implies that

$\liminf_{n\rightarrow\infty}\alpha_{n}\geq\left[\frac{\beta}{1-2\beta}\right]\left(\int_{0}^{1}\phi(x)\left(1+\alpha_{0}\int_{x}^{1}\phi(z)\frac{dz}{z}\right)dx\right)^{-1}.$
(88)

We proceed to use the same fixed point argument from [15] to complete the
proof. Define $F_{\phi,s}$ by

$F_{\phi,s}(\alpha)=\left[\frac{\beta}{1-2\beta}\right]\left(\int_{0}^{1}\phi(x)\left(1+\alpha\int_{x}^{1}\phi(z)\frac{dz}{z}\right)dx\right)^{-1}.$
(89)

Proposition 1 implies that $\liminf_{n\rightarrow\infty}\alpha_{n}\geq 0$.
Iterating the relations (87) and (88) we see that for any $n\geq 1$

$\limsup_{n\rightarrow\infty}\alpha_{n}\leq
F_{\phi,s}^{2n-1}(0),~{}\liminf_{n\rightarrow\infty}\alpha_{n}\geq
F_{\phi,s}^{2n}(0).$ (90)

Note here that the exponent represents composition. Thus (77) will be proved
if we can show that $\lim_{n\rightarrow\infty}F_{\phi,s}^{n}(0)=1$. To see
this, rewrite $F_{\phi,s}$ as

$F_{\phi,s}(\alpha)=\frac{A}{B+C\alpha},$ (91)

where $A=\frac{\beta}{1-2\beta}>0$, $B=\int_{0}^{1}\phi(x)dx>0$, and
$C=\int_{0}^{1}\phi(x)\left(\int_{x}^{1}\phi(z)\frac{dz}{z}\right)dx>0$.

Further, the assumption (76) implies that $F_{\phi,s}(1)=1$, i.e., that
$A=B+C$. We wish to show that iterating the map $F_{\phi,s}$ converges to this
fixed point. This follows from the following simple calculation

$|F^{2}_{\phi,s}(\alpha)-1|=\left|\frac{C^{2}}{C^{2}+B^{2}+BC\alpha+BC}(\alpha-1)\right|\leq\frac{C^{2}}{C^{2}+B^{2}}|\alpha-1|,$
(92)

since $\frac{C^{2}}{C^{2}+B^{2}}<1$. This completes the proof of (77).

Next, we prove the asymptotic formula (79). We may assume that $k>K$ and use
Lemma 1 and the fact that $\xi_{k}$ approaches $1$, see Proposition 1, to get

$\langle r_{n},e_{k}\rangle=-q_{n}\left(1+\sum_{j=k+1}^{n}\langle
h_{j},e_{k}\rangle+o_{k}(1)\right).$ (93)

Using the definition of $h_{n}$ (51), we get

$\langle
r_{n},e_{k}\rangle=-q_{n}\left(1+\sum_{j=k+1}^{n}\frac{\alpha_{j}}{j}\phi\left(\frac{k}{j}\right)+o_{k}(1)\right)=-q_{n}\left(1+\sum_{j=k+1}^{n}\frac{1+o_{k}(1)}{j}\phi\left(\frac{k}{j}\right)+o_{k}(1)\right).$
(94)

Using Lemma 2 and noting that $\int_{0}^{1}\frac{\phi(z)}{z}dz<\infty$ (since
$\phi=0$ on $[0,\delta]$), we get

$\langle
r_{n},e_{k}\rangle=-q_{n}\left(1+\int_{\frac{k}{n}}^{1}\phi(z)\frac{dz}{z}+o_{k}(1)\right),$
(95)

as desired.

Finally, we will prove (78). For this, we note that (29), combined with the
asymptotics (46) implies that

$\frac{\langle r_{n},h_{n+1}\rangle}{\langle
r_{n-1},h_{n}\rangle}=1+\frac{\beta-1}{n}+o(n^{-1}).$ (96)

Using the formula (35) to rewrite this as

$\frac{\langle r_{n},h_{n+1}\rangle}{\langle
r_{n-1},h_{n}\rangle}=\frac{\langle\frac{q_{n}}{q_{n-1}}r_{n-1}-q_{n}h_{n}-q_{n}\xi_{n}e_{n},h_{n+1}\rangle}{\langle
r_{n-1},h_{n}\rangle}=\frac{q_{n}}{q_{n-1}}\frac{\langle
r_{n-1},h_{n+1}\rangle}{\langle r_{n-1},h_{n}\rangle}-q_{n}\frac{\langle
h_{n}+\xi_{n}e_{n},h_{n+1}\rangle}{\langle r_{n-1},h_{n}\rangle}$ (97)

Using the asymptotics (44) and (46), we see that

$\frac{q_{n}}{\langle r_{n-1},h_{n}\rangle}=c^{\prime}+O(n^{-1})$ (98)

for a constant $c^{\prime}$. In addition, using the definition of $h_{n}$, the
fact that $\xi_{n}\rightarrow 1$, and that $\phi$ is smooth, we see that

$\langle
h_{n}+\xi_{n}e_{n},h_{n+1}\rangle=\frac{1}{n+1}\left(\frac{1}{n}\sum_{i=1}^{n-1}\phi\left(\frac{i}{n}\right)\phi\left(\frac{i}{n+1}\right)+\phi\left(\frac{n}{n+1}\right)+o_{n}(1)\right)=c^{\prime\prime}n^{-1}+o(n^{-1}),$
(99)

for a constant $c^{\prime\prime}=\phi(1)+\int_{0}^{1}\phi^{2}(x)dx$. This
means that the last term in (97) is

$q_{n}\frac{\langle h_{n}+\xi_{n}e_{n},h_{n+1}\rangle}{\langle
r_{n-1},h_{n}\rangle}=cn^{-1}+o(n^{-1}),$ (100)

for a constant $c$.

Now, we calculate, using the definition of $h_{n}$,

$\langle r_{n-1},h_{n}\rangle=\sum_{k=1}^{n-1}\langle
r_{n-1},e_{k}\rangle\langle
h_{n},e_{k}\rangle=\frac{\alpha_{n}}{n}\sum_{k=1}^{n-1}\langle
r_{n-1},e_{k}\rangle\phi\left(\frac{k}{n}\right).$ (101)

Similarly, we obtain

$\langle r_{n-1},h_{n+1}\rangle=\sum_{k=1}^{n-1}\langle
r_{n-1},e_{k}\rangle\langle
h_{n},e_{k}\rangle=\frac{\alpha_{n+1}}{n+1}\sum_{k=1}^{n-1}\langle
r_{n-1},e_{k}\rangle\phi\left(\frac{k}{n+1}\right).$ (102)

Next, we observe that

$\sum_{k=1}^{n-1}\langle
r_{n-1},e_{k}\rangle\phi\left(\frac{k}{n+1}\right)=\sum_{k=1}^{n-1}\langle
r_{n-1},e_{k}\rangle\phi\left(\frac{k}{n}\right)+\sum_{k=1}^{n-1}\langle
r_{n-1},e_{k}\rangle\left[\phi\left(\frac{k}{n}\right)-\phi\left(\frac{k}{n+1}\right)\right].$
(103)

Using that $\phi$ is smooth, we see that

$\sum_{k=1}^{n-1}\langle
r_{n-1},e_{k}\rangle\left[\phi\left(\frac{k}{n}\right)-\phi\left(\frac{k}{n+1}\right)\right]=\sum_{k=1}^{n-1}\langle
r_{n-1},e_{k}\rangle\left[\frac{k}{n(n+1)}\phi^{\prime}\left(\frac{k}{n}\right)+O\left(\frac{k^{2}}{n^{4}}\right)\right].$
(104)

Applying the asymptotics (79) and comparing the Riemann sum with an integral,
we get

$\sum_{k=1}^{n-1}\langle
r_{n-1},e_{k}\rangle\left[\phi\left(\frac{k}{n}\right)-\phi\left(\frac{k}{n+1}\right)\right]=-q_{n-1}\left(\int_{0}^{1}x\phi^{\prime}(x)\int_{x}^{1}\phi(z)\frac{dz}{z}dx+o_{n}(1)\right).$
(105)

Similarly, we obtain

$\sum_{k=1}^{n-1}\langle
r_{n-1},e_{k}\rangle\phi\left(\frac{k}{n}\right)=-q_{n-1}n\left(\int_{0}^{1}\phi(x)\int_{x}^{1}\phi(z)\frac{dz}{z}dx+o_{n}(1)\right).$
(106)

Using all of this, we obtain

$\frac{\langle r_{n-1},h_{n+1}\rangle}{\langle
r_{n-1},h_{n}\rangle}=\frac{\alpha_{n+1}}{\alpha_{n}}\frac{n}{n+1}\left(1+n^{-1}\frac{\int_{0}^{1}x\phi^{\prime}(x)\int_{x}^{1}\phi(z)\frac{dz}{z}dx+o_{n}(1)}{\int_{0}^{1}\phi(x)\int_{x}^{1}\phi(z)\frac{dz}{z}dx+o_{n}(1)}\right).$
(107)

Since $\phi\neq 0$ is non-negative, the integral in the denominator above is
non-zero and we obtain

$\frac{\langle r_{n-1},h_{n+1}\rangle}{\langle
r_{n-1},h_{n}\rangle}=\frac{\alpha_{n+1}}{\alpha_{n}}\frac{n}{n+1}\left(1+cn^{-1}+o(n^{-1})\right)$
(108)

for a constant $c$. Using that $\frac{n}{n+1}=1-n^{-1}+o(n^{-1})$ and
combining the above estimates with (97) and (96), we get

$\frac{\alpha_{n+1}}{\alpha_{n}}=1+\kappa n^{-1}+o(n^{-1}),$ (109)

for some constant $\kappa$. Finally, since

$\prod_{k=n}^{T}\frac{\alpha_{k+1}}{\alpha_{k}}=\frac{\alpha_{T+1}}{\alpha_{n}}$
(110)

is uniformly bounded in $T$ (since the sequence $\alpha_{k}$ converges to
$1$), we must in fact have $\kappa=0$, which completes the proof.

∎

Next, we determine conditions on $\phi$ which guarantee that for sufficiently
large $N$, the conditions (33) will be satisfied. We consider first the case
$k>n$. We have the following result.

######  Proposition 3.

Suppose that $\phi$ satisfies the condition of Proposition 2 and also the
inequality

$\sup_{a\in[0,1]}\left|\int_{0}^{a}(\phi^{\prime}(x)x-(\beta-1)\phi(x))\left(1+\int_{a^{-1}x}^{1}\phi(z)\frac{dz}{z}\right)dx\right|<1.$
(111)

Then there is a sufficiently large $N$ such that for $k>n>N$ we have $|\langle
r_{n-1},g_{k}\rangle|<q_{n}$.

###### Proof.

We utilize the formula (42). If we can show that for some $\delta>0$, we have

$\left|\left\langle
r_{n-1},h_{k}-\frac{\gamma_{k}}{\gamma_{k-1}}h_{k-1}\right\rangle\right|<(1-\delta)q_{n}k^{-1}$
(112)

for every $k>n>N$, then the asymptotics (49) combined with the base case
$\langle r_{n-1},g_{n}\rangle=q_{n}$ (which holds by construction) will imply
the desired result by induction.

Define $p_{k}=h_{k}-\frac{\gamma_{k}}{\gamma_{k-1}}h_{k-1}$. From the
definition of $h_{k}$, we see that

$\langle
p_{k},e_{m}\rangle=\frac{\alpha_{k}}{k}\phi\left(\frac{m}{k}\right)-\frac{\gamma_{k}}{\gamma_{k-1}}\frac{\alpha_{k-1}}{k-1}\phi\left(\frac{m}{k-1}\right).$
(113)

Using (78), (77), and that $\phi$ is bounded, we get

$\langle
p_{k},e_{m}\rangle=(1+o_{k}(1))\left(\frac{1}{k}\phi\left(\frac{m}{k}\right)-\frac{\gamma_{k}}{\gamma_{k-1}}\frac{1}{k-1}\phi\left(\frac{m}{k-1}\right)\right)+o(k^{-2}).$
(114)

We rewrite the term in parenthesis as

$\left(\frac{1}{k}-\frac{\gamma_{k}}{\gamma_{k-1}}\frac{1}{k-1}\right)\phi\left(\frac{m}{k}\right)+\frac{\gamma_{k}}{\gamma_{k-1}}\frac{1}{k-1}\left(\phi\left(\frac{m}{k}\right)-\phi\left(\frac{m}{k-1}\right)\right).$
(115)

Utilizing the asymptotics (48) and the boundedness of $\phi$, this can be
rewritten as

$\frac{(\beta-1)}{k^{2}}\phi\left(\frac{m}{k}\right)+\left(1-\frac{\beta}{k}\right)\frac{1}{k-1}\left(\phi\left(\frac{m}{k}\right)-\phi\left(\frac{m}{k-1}\right)\right)+o(k^{-2}).$
(116)

Next, we use that $\phi$ is infinitely differentiable and that
$\frac{m}{k}-\frac{m}{k-1}=-\frac{m}{k(k-1)}$ to obtain

$\phi\left(\frac{m}{k}\right)-\phi\left(\frac{m}{k-1}\right)=-\phi^{\prime}\left(\frac{m}{k}\right)\frac{m}{k(k-1)}+O\left(\frac{m^{2}}{k^{4}}\right).$
(117)

Restricting $m\leq n-1<k$ (since otherwise $\langle r_{n-1},e_{m}\rangle=0$),
we get

$\langle
p_{k},e_{m}\rangle=(1+o_{k}(1))\left(\frac{(\beta-1)}{k^{2}}\phi\left(\frac{m}{k}\right)-\frac{1}{k^{2}}\phi^{\prime}\left(\frac{m}{k}\right)\frac{m}{k}\right)+o(k^{-2}).$
(118)

Since $\phi$ is smooth (and thus $\phi^{\prime}$ is bounded), we get

$\langle
p_{k},e_{m}\rangle=\frac{(\beta-1)}{k^{2}}\phi\left(\frac{m}{k}\right)-\frac{1}{k^{2}}\phi^{\prime}\left(\frac{m}{k}\right)\frac{m}{k}+o(k^{-2}).$
(119)

We finally calculate, using the asymptotic formula (79) for the components of
$r_{n-1}$ to get

$\begin{split}\langle r_{n-1},p_{k}\rangle&=\sum_{m=1}^{n-1}\langle
r_{n-1},e_{m}\rangle\langle p_{k},e_{m}\rangle\\\
&=k^{-1}q_{n-1}\left(\frac{1}{k}\sum_{m=1}^{n-1}\left[\phi^{\prime}\left(\frac{m}{k}\right)\frac{m}{k}-(\beta-1)\phi\left(\frac{m}{k}\right)+o_{k}(1)\right]\left(1+\int_{\frac{m}{n-1}}^{1}\phi(z)\frac{dz}{z}+o_{m}(1)\right)\right).\end{split}$
(120)

Comparing this Riemann sum with an integral, setting $a=\frac{n-1}{k}$, using
that $\phi$ (and thus the integrand) is $C^{\infty}$, we get

$\langle
r_{n-1},p_{k}\rangle=k^{-1}q_{n-1}\left[\int_{0}^{a}(\phi^{\prime}(x)x-(\beta-1)\phi(x))\left(1+\int_{a^{-1}x}^{1}\phi(z)\frac{dz}{z}\right)dx+o_{n}(1)\right].$
(121)

Combined with the assumption (111), this completes the proof, since for
sufficiently large $n>N$ the term in brackets above will be strictly less than
$1$ in magnitude uniformly in $a$. ∎

Next, we consider the case where $k<n$.

######  Proposition 4.

Suppose that $\phi$ satisfies the condition of Proposition 2 and also the
inequality

$\sup_{a\in[0,1]}\left|\int_{0}^{1}\left((\beta-1)+(\beta-1)\int_{x}^{1}\phi(z)\frac{dz}{z}+\phi(x)\right)\left(\int_{ax}^{x}\phi(z)\frac{dz}{z}\right)dx+\int_{a}^{1}\phi(x)\frac{dx}{x}\right|<1.$
(122)

Then there is a sufficiently large $N$ such that for $n>k\geq N$ we have
$|\langle r_{n-1},g_{k}\rangle|<q_{n}$. Further, by increasing $N$ if
necessary, the denominator in the definition of $\tilde{g}_{N}$ will be non-
zero and we can choose $\epsilon>0$ small enough so that we also have
$|\langle r_{n-1},\tilde{g}_{N}\rangle|<q_{n}$ for all $n>N$.

###### Proof.

We will need to use the formulas (37) and (38). For this, we will need to
estimate

$\sum_{i=k+1}^{n-1}\langle h_{i},g_{k}\rangle.$ (123)

Utilizing the the inductive definition of $g_{k}$ (24), we get

$\sum_{i=k+1}^{n-1}\langle
h_{i},g_{k}\rangle=\gamma_{k}\sum_{i=k+1}^{n-1}\langle
h_{i},r_{k-1}\rangle+\sum_{i=k+1}^{n-1}\langle
h_{i},h_{k}\rangle+\xi_{k}\sum_{i=k+1}^{n-1}\langle h_{i},e_{k}\rangle.$ (124)

We consider the last term above first. From the definition of $h_{i}$ (51) we
get

$\xi_{k}\sum_{i=k+1}^{n-1}\frac{\alpha_{i}}{i}\phi\left(\frac{k}{i}\right).$
(125)

Since $\lim_{k\rightarrow\infty}\xi_{k}=1$ by Proposition 1 and
$\lim_{k\rightarrow\infty}\alpha_{k}=1$ by Proposition 2, we see that

$\xi_{k}\sum_{i=k+1}^{n-1}\frac{\alpha_{i}}{i}\phi\left(\frac{k}{i}\right)=(1+o_{k}(1))\sum_{i=k+1}^{n-1}\frac{1}{i}\phi\left(\frac{k}{i}\right).$
(126)

Applying Lemma 2, we see that

$\xi_{k}\sum_{i=k+1}^{n-1}\frac{\alpha_{i}}{i}\phi\left(\frac{k}{i}\right)=\int_{\frac{k}{n}}^{1}\phi(z)\frac{dz}{z}+o_{k}(1).$
(127)

Setting $a=\frac{k}{n}$ we write this as

$\xi_{k}\sum_{i=k+1}^{n-1}\frac{\alpha_{i}}{i}\phi\left(\frac{k}{i}\right)=\int_{a}^{1}\phi(z)\frac{dz}{z}+o_{k}(1).$
(128)

Next, we consider the term

$\sum_{i=k+1}^{n-1}\langle
h_{i},h_{k}\rangle=\sum_{i=k+1}^{n-1}\sum_{j=1}^{k-1}\langle
h_{i},e_{j}\rangle\langle
h_{k},e_{j}\rangle=\sum_{i=k+1}^{n-1}\sum_{j=1}^{k-1}\frac{\alpha_{i}}{i}\phi\left(\frac{j}{i}\right)\frac{\alpha_{k}}{k}\phi\left(\frac{j}{k}\right).$
(129)

Using again (77), we get

$\sum_{i=k+1}^{n-1}\langle
h_{i},h_{k}\rangle=(1+o_{k}(1))\sum_{i=k+1}^{n-1}\sum_{j=1}^{k-1}\frac{1}{i}\phi\left(\frac{j}{i}\right)\frac{1}{k}\phi\left(\frac{j}{k}\right),$
(130)

and Lemma 2 implies (recalling the choice $a=\frac{k}{n}$)

$\begin{split}\sum_{i=k+1}^{n-1}\langle
h_{i},h_{k}\rangle&=(1+o_{k}(1))\frac{1}{k}\sum_{j=1}^{k-1}\left[\phi\left(\frac{j}{k}\right)\int_{\frac{j}{n}}^{\frac{j}{k}}\phi(z)\frac{dz}{z}+O(j^{-1})\right]\\\
&=(1+o_{k}(1))\frac{1}{k}\sum_{j=1}^{k-1}\phi\left(\frac{j}{k}\right)\int_{a\frac{j}{k}}^{\frac{j}{k}}\phi(z)\frac{dz}{z}+O\left(\frac{\log{k}}{k}\right).\end{split}$
(131)

Comparing a Riemann sum with an integral finally yields

$\sum_{i=k+1}^{n-1}\langle
h_{i},h_{k}\rangle=\int_{0}^{1}\phi(x)\int_{ax}^{x}\phi(z)\frac{dz}{z}+o_{k}(1).$
(132)

Finally, we consider the first term in (124). Using (79), we get

$\gamma_{k}\sum_{i=k+1}^{n-1}\sum_{j=1}^{k-1}\langle h_{i},e_{j}\rangle\langle
r_{k-1},e_{j}\rangle=-\gamma_{k}q_{k-1}\sum_{i=k+1}^{n-1}\sum_{j=1}^{k-1}\frac{\alpha_{i}}{i}\phi\left(\frac{j}{i}\right)\left(1+\int_{\frac{j}{k}}^{1}\phi(z)\frac{dz}{z}+o_{k}(1)\right).$
(133)

Utilizing the asymptotics (44), (45), and (77), we get

$\gamma_{k}\sum_{i=k+1}^{n-1}\sum_{j=1}^{k-1}\langle h_{i},e_{j}\rangle\langle
r_{k-1},e_{j}\rangle=(\beta-1+o_{k}(1))\frac{1}{k}\sum_{i=k+1}^{n-1}\sum_{j=1}^{k-1}\frac{1}{i}\phi\left(\frac{j}{i}\right)\left(1+\int_{\frac{j}{k}}^{1}\phi(z)\frac{dz}{z}+o_{k}(1)\right).$
(134)

Proceeding as before, using Lemma 2, recalling the choice $a=\frac{k}{n}$, and
comparing a Riemann sum with an integral, we finally obtain

$\gamma_{k}\sum_{i=k+1}^{n-1}\sum_{j=1}^{k-1}\langle h_{i},e_{j}\rangle\langle
r_{k-1},e_{j}\rangle=(\beta-1)\int_{0}^{1}\left(\int_{ax}^{x}\phi(z)\frac{dz}{z}\right)\left(1+\int_{x}^{1}\phi(z)\frac{dz}{z}\right)dx+o_{k}(1).$
(135)

Combining the estimates (135), (132), and (128), we get

$\sum_{i=k+1}^{n-1}\langle
h_{i},g_{k}\rangle=\int_{0}^{1}\left((\beta-1)+(\beta-1)\int_{x}^{1}\phi(z)\frac{dz}{z}+\phi(x)\right)\left(\int_{ax}^{x}\phi(z)\frac{dz}{z}\right)dx+\int_{a}^{1}\phi(x)\frac{dx}{x}+o_{k}(1).$
(136)

Our assumption (122) on $\phi$ now imply that for sufficiently large $k$, the
sum $\sum_{i=k+1}^{n-1}\langle h_{i},g_{k}\rangle$ will satisfy the bounds

$-1<\sum_{i=k+1}^{n-1}\langle h_{i},g_{k}\rangle<1$ (137)

uniformly in $n$ and $k$. So choose $N$ large enough to guarantee this. We now
use equation (37) to see that

$|\langle r_{n-1},g_{k}\rangle|=|q_{n-1}|\left|\sum_{i=k+1}^{n-1}\langle
h_{i},g_{k}\rangle\right|\leq|q_{n}|(1+O(n^{-1}))|\left|\sum_{i=k+1}^{n-1}\langle
h_{i},g_{k}\rangle\right|.$ (138)

The bound (137) implies that the final absolute value above is strictly
smaller than $1$ uniformly in $n$ and $k$. Thus, by increasing $N$ if
necessary, we get that for all $n>k\geq N$

$|\langle r_{n-1},g_{k}\rangle|<q_{n},$ (139)

as desired.

Finally, we bound $\langle r_{n-1},\tilde{g}_{N}\rangle$. Consider the inner
product formula (38). Utilizing the definition of $\tilde{g}_{N}$, we obtain

$\sum_{i=N+1}^{n-1}\langle
h_{i},\tilde{g}_{N}\rangle=C_{\epsilon}\sum_{i=N+1}^{n-1}\langle
h_{i},g_{N}\rangle+c_{\epsilon}\sum_{i=N+1}^{n-1}\langle h_{i},r_{N}\rangle,$
(140)

where

$C_{\epsilon}=\sqrt{1-\epsilon^{2}}$

and

$c_{\epsilon}=\epsilon\|r_{N}\|^{-1}.$

We note that since $r_{N}\in\text{span}(e_{1},...,e_{N})$, we get

$\sum_{i=N+1}^{n-1}\langle
h_{i},r_{N}\rangle=\sum_{i=N+1}^{n-1}\sum_{j=1}^{N}\langle
h_{i},e_{j}\rangle\langle r_{N},e_{j}\rangle=\sum_{j=1}^{N}\langle
r_{N},e_{j}\rangle\sum_{i=N+1}^{n-1}\frac{\alpha_{i}}{i}\phi\left(\frac{j}{i}\right).$
(141)

Since $\phi$ is assumed to vanish on $[0,\delta]$ we get that

$\sum_{i=N+1}^{n-1}\langle h_{i},r_{N}\rangle\leq\sum_{j=1}^{N}\langle
r_{N},e_{j}\rangle\sum_{i=N+1}^{\delta^{-1}N}\frac{\alpha_{i}}{i}\phi\left(\frac{j}{i}\right)<\infty,$
(142)

and so this sum is bounded uniformly in $n$.

Plugging these facts into (38) we see that

$|\langle r_{n-1},\tilde{g}_{N}\rangle|\leq
q_{n}(1+O(n^{-1}))\left|C_{\epsilon}\sum_{i=k+1}^{n-1}\langle
h_{i},g_{N}\rangle+K\epsilon\right|,$ (143)

for a large enough constant $K$. The bound (137) together with the estimate
(143) implies that for small enough $\epsilon>0$ the absolute value above can
be made smaller than $1$ uniformly in $n$. Increasing $N$ again if necessary,
we then have

$|\langle r_{n-1},\tilde{g}_{N}\rangle|<q_{n}$ (144)

for all $n>N$. This completes the proof. ∎

###  2.6 Completion of the Construction

Finally, to complete the construction, we will specify how to choose the
function $\phi$, which must satisfy the conditions (76), (111), and (122).

To construct such a function $\phi$, let $\nu\geq 0$ be a $C^{\infty}$ bump
function which is supported on $[-1,1]$ and satisfies

$\int_{-\infty}^{\infty}\nu(x)dx=1.$

Let $t>0$ and write $\nu_{t}=t^{-1}\nu\left(t^{-1}x\right)$.

Fix a parameter $\tau\in(0,1)$ to be determined later. For a continuously
differentiable function $f:[\tau,1]\rightarrow\mathbb{R}_{+}$, we extend $f$
to the whole real line by setting $f(x)=0$ for $x<\tau$ and $f(x)=f(1)$ for
$x>1$. Then, we smooth $f$ using the bump function $\nu$ and normalize so that
(76) is satisfied. Specifically, we set

$\bar{\phi}_{t}(x)=\int_{-\infty}^{\infty}f(x-y)\nu_{t}(y)dy,$ (145)

and $\phi(x)=C_{t}\bar{\phi}_{t}$, where the constant $C_{t}$ is chosen to
satisfy (76).

Since $\bar{\phi}_{t}\rightarrow f$ in $L^{1}$ as $t\rightarrow 0$ and both
functions vanish in a neighborhood of $0$ for $t<\tau$, we see that

$\lim_{t\rightarrow
0}\left(\int_{0}^{1}\bar{\phi}_{t}(x)\left(1+\int_{x}^{1}\bar{\phi}_{t}(z)\frac{dz}{z}\right)dx\right)=\left(\int_{\tau}^{1}f(x)\left(1+\int_{x}^{1}f(z)\frac{dz}{z}\right)dx\right).$
(146)

This means that if $f$ satisfies

$\left(\int_{\tau}^{1}f(x)\left(1+\int_{x}^{1}f(z)\frac{dz}{z}\right)dx\right)=\frac{\beta}{1-2\beta},$
(147)

then the normalizing constant will satisfy $C_{t}\rightarrow 1$ as
$t\rightarrow 0$.

Using this, we calculate that if $f$ satisfies

$\sup_{a\in[\tau,1]}\left|f(\tau)\tau\left(1+\int_{a^{-1}\tau}^{1}f(z)\frac{dz}{z}\right)+\int_{\tau}^{a}(f^{\prime}(x)x-(\beta-1)f(x))\left(1+\int_{a^{-1}x}^{1}f(z)\frac{dz}{z}\right)dx\right|<1$
(148)

and

$\sup_{a\in[\tau,1]}\left|\int_{\tau}^{1}\left((\beta-1)+(\beta-1)\int_{x}^{1}f(z)\frac{dz}{z}+f(x)\right)\left(\int_{ax}^{x}f(z)\frac{dz}{z}\right)dx+\int_{a}^{1}f(x)\frac{dx}{x}\right|<1,$
(149)

in addition to (147), then for sufficiently small $t>0$, $\phi$ will satisfy
(76), (111), and (122).

Indeed, for any $t<\tau$, we clearly have $\phi\in C^{\infty}$ and $\phi(x)=0$
on $[0,\delta]$ if $\delta<\tau-t$. Now, since $\phi$ vanishes in a
neighborhood of $0$, we see that the integral in (122) converges to the
corresponding integral for $f$ uniformly in $a$. For the condition (111), we
note that

$1+\int_{x}^{1}\phi_{t}(z)\frac{dz}{z}\rightarrow
1+\int_{x}^{1}f(z)\frac{dz}{z}$ (150)

as $t\rightarrow 0$ uniformly in $x$. Further, $\phi_{t}$ converges to $f$ in
$L^{1}$, so that the only problematic term arises from the
$x\phi_{t}^{\prime}(x)$ term in (111). However, $\phi_{t}^{\prime}(x)$
converges uniformly to $f^{\prime}(x)$ for $x$ outside of $[\tau-t,\tau+t]$.
For this term, we note that

$x\left(1+\int_{a^{-1}x}^{1}\phi_{t}(z)\frac{dz}{z}\right)$ (151)

is uniformly continuous in $x,t$ and $a\geq\tau-t$ (for smaller values of $a$
the entire integral in (111) vanishes). On the interval $[\tau-t,\tau+t]$ the
function $\phi_{t}$ increases rapidly from $0$ to $f(\tau)$, so the
contribution from the integral of this term over $[\tau-t,\tau+t]$ converges
to

$f(\tau)\tau\left(1+\int_{a^{-1}\tau}^{1}f(z)\frac{dz}{z}\right)$ (152)

uniformly in $a\geq\tau+t$ as $t\rightarrow 0$. For $a\in[\tau-t,\tau+t]$, the
integral in (111) reduces to

$\int_{\tau-t}^{a}x\phi_{t}^{\prime}(x)\left(1+\int_{a^{-1}x}^{1}\phi_{t}(z)\frac{dz}{z}\right)dx-(\beta-1)\int_{\tau-t}^{a}\phi_{t}(x)\left(1+\int_{a^{-1}x}^{1}\phi_{t}(z)\frac{dz}{z}\right)dx.$
(153)

Since $\phi_{t}$ is bounded and $a\in[\tau-t,\tau+t]$ we see that this
converges to

$\tau\int_{\tau-t}^{a}\phi_{t}^{\prime}(x)dx=\tau\phi_{t}(a)$ (154)

as $t\rightarrow 0$ uniformly in $a\in[\tau-t,\tau+t]$. Since $|\tau
f(\tau)|<1$ (setting $a=\tau$ in (148)), for sufficiently small $t$ we will
have $|\tau\phi_{t}(a)|\leq\tau f(\tau)+\epsilon<1$ for all
$a\in[\tau-t,\tau+t]$ (as $\phi_{t}$ increases to $\phi_{t}(\tau+t)$ on the
interval $[\tau-t,\tau+t]$ and $|\phi_{t}(\tau+t)-f(\tau)|\rightarrow 0$).
Thus $\phi$ satisfies all of the conditions in our construction. The task now
is to choose $\tau$ appropriately and to find such an $f$.

We remark that the method in [15] essentially corresponds to choosing

$f(x)=\begin{cases}c&x\geq\tau\\\ 0&x<\tau,\end{cases}$ (155)

for a constant $c$ and then optimizing over $c$, $\tau$, and $\beta$. We
improve this method by allowing general functions $f$, which enables us to
match the upper bound from [28].

The key to this is to introduce the function

$F(a)=\int_{\tau}^{a}f(x)\left(1+\int_{a^{-1}x}^{1}f(z)\frac{dz}{z}\right)dx,$
(156)

and to rewrite the conditions on $f$ in terms of $F$. The condition (147) then
becomes

$F(1)=\frac{\beta}{(1-2\beta)}.$ (157)

Integrating by parts to remove the $f^{\prime}$ term in (148) and observing
that

$F^{\prime}(a)=f(a)+a^{-1}\int_{\tau}^{a}f(x)f(a^{-1}x)dx,$ (158)

we obtain

$\sup_{a\in[\tau,1]}|aF^{\prime}(a)-\beta F(a)|<1.$ (159)

To determine the function $F$, we choose to set (note that this is also what
is needed to make Sil’nichenko’s analysis tight)

$aF^{\prime}(a)-\beta F(a)=c,$ (160)

for a positive constant $c<1$. Combined with the definition (156), which
implies that $F(\tau)=0$, and the endpoint condition (157), this forces

$c=\frac{\beta^{2}}{(1-2\beta)(\tau^{-\beta}-1)},$ (161)

and

$F(a)=\frac{c}{\beta}\left(\tau^{-\beta}a^{\beta}-1\right).$ (162)

Since $c<1$ must hold, we obtain the following condition on $\beta$ and $\tau$

$\frac{\beta^{2}}{(1-2\beta)(\tau^{-\beta}-1)}<1.$ (163)

Differentiating the integrand in (149) with respect to $a$, rewriting in terms
of $F$, and noting that for $a=1$ the integrals vanish, we see that the
condition (149) becomes

$\sup_{b\in[\tau,1]}\left|\int_{b}^{1}a^{-2}(c-(1-2\beta)F(a))da\right|<1.$
(164)

Plugging (162) into these conditions and noting that the integral above is
minimized in $b$ when the integrand is $0$, which occurs for

$b=\tau\left(\frac{1-\beta}{1-2\beta}\right)^{\frac{1}{\beta}},$

and is maximized when $b=\tau$, we obtain the following two conditions on
$\beta$, and $\tau$

$\frac{\beta}{(1-2\beta)(\tau^{-\beta}-1)}\left(\beta-1+\frac{\tau^{-\beta}(1-2\beta)}{1-\beta}-\beta\tau^{-1}\left(\frac{1-2\beta}{1-\beta}\right)^{\frac{1}{\beta}}\right)>-1,$
(165)
$\frac{\beta}{(1-2\beta)(\tau^{-\beta}-1)}\left(\beta-1+\frac{\tau^{-\beta}(1-2\beta)}{1-\beta}+\frac{\tau^{-1}\beta^{2}}{(1-\beta)}\right)<1.$
(166)

A routine calculation shows that condition (163) means that $\tau$ must be
chosen so that

$\frac{(1-\beta)^{2}}{1-2\beta}<\tau^{-\beta}.$ (167)

Let $\tau^{*}$ be the value of $\tau$ which gives equality in the above bound.
By choosing $\tau<\tau^{*}$, we see that it suffices for the inequalities
(165) and (166) to hold (strictly, of course) for $\tau=\tau^{*}$. Plugging in
this value and performing a routine, yet tedious, calculation, we see that
(165) becomes

$\beta(1-\beta)^{\frac{1}{\beta}}<1,$ (168)

and (166) becomes

$\left(\frac{\beta}{1-\beta}\right)^{\beta}\left(\frac{(1-\beta)^{2}}{1-2\beta}\right)<1.$
(169)

We see that (168) holds for any $\beta\in(0,\frac{1}{2})$ since the left hand
side is $<1$ and the right hand side is $\geq 1$. Thus the only condition on
$\beta$ which must be satisfied is (169), which is exactly the relation (20).

The only step left in the proof of Theorem 1 is to show that the equation
(156) can be solved for $f$ when $F$ is given by (162). Differentiating (156)
with respect to $a$, we obtain the integral differential equation on
$[\tau,1]$

$f(a)+a^{-1}\int_{\tau}^{a}f(x)f(a^{-1}x)dx=G(a):=F^{\prime}(a)=c\tau^{-\beta}a^{\beta-1}.$
(170)

We will use the following Lemma, based on the Schauder fixed point theorem, to
solve this equation.

######  Lemma 3.

Suppose that $G(x)$ is continuously differentiable and satisfies the bound

$R_{G}:=\sup_{a\in[\tau,1]}a^{-2}\int_{\tau}^{a}G(a^{-1}x)dx<1.$ (171)

In addition, assume that there exist functions $0\leq g_{1}(x)\leq
g_{2}(x)\leq G(x)$ on $[\tau,1]$ such that

$G(a)-a^{-1}\int_{\tau}^{a}g_{1}(x)g_{1}(a^{-1}x)dx\leq g_{2}(a),$ (172)

and

$G(a)-a^{-1}\int_{\tau}^{a}g_{2}(x)g_{2}(a^{-1}x)dx\geq g_{1}(a).$ (173)

Then the equation (170) has a continuously differentiable solution $f\geq 0$.

###### Proof.

Consider the map $T_{G}:C([\tau,1])\rightarrow C([\tau,1])$ defined by

$T_{G}(f)(a)=G(a)-a^{-1}\int_{\tau}^{a}f(x)f(a^{-1}x)dx.$ (174)

For a fixed $M$ to be determined later, define the set

$S_{M}:=\\{f\in C^{1}([\tau,1]),~{}g_{1}(x)\leq f(x)\leq
g_{2}(x),~{}|f^{\prime}(x)|\leq M\\}\subset C([\tau,1]).$ (175)

By the Arzela-Ascoli theorem, $S_{M}$ is a compact subset of $C([\tau,1])$. We
will show that for sufficiently large $M$, $T_{G}$ maps $S_{M}$ into itself.
Indeed, if $g_{1}(x)\leq f(x)\leq g_{2}(x)$, then we clearly have (since
$g_{1},g_{2}$ and thus $f$ are non-negative)

$T_{G}(f)(a)=G(a)-a^{-1}\int_{\tau}^{a}f(x)f(a^{-1}x)dx\leq
G(a)-a^{-1}\int_{\tau}^{a}g_{1}(x)g_{1}(a^{-1}x)dx\leq g_{2}(a)$ (176)

and

$T_{G}(f)(a)=G(a)-a^{-1}\int_{\tau}^{a}f(x)f(a^{-1}x)dx\geq
G(a)-a^{-1}\int_{\tau}^{a}g_{2}(x)g_{2}(a^{-1}x)dx\geq g_{1}(a),$ (177)

by assumption on $g_{1}$ and $g_{2}$. Further, taking derivates, we see that

$T_{G}(f)^{\prime}(a)=G^{\prime}(a)+a^{-2}\int_{\tau}^{a}f(x)f(a^{-1}x)dx-a^{-1}f(a)f(1)+a^{-3}\int_{\tau}^{a}f(x)f^{\prime}(a^{-1}x)dx.$
(178)

We now integrate the last integral above by parts to obtain

$\begin{split}a^{-3}\int_{\tau}^{a}f(x)f^{\prime}(a^{-1}x)dx&=a^{-2}\int_{\tau}^{a}f(x)\frac{d}{dx}f(a^{-1}x)dx\\\
&=a^{-2}(f(a)f(1)-f(\tau)f(a^{-1}\tau))-a^{-2}\int_{\tau}^{a}f^{\prime}(x)f(a^{-1}x)dx.\end{split}$
(179)

Since $G$ is fixed, $f\leq g_{2}\leq G$ and $|f^{\prime}(x)|\leq M$ by
assumption, collecting the preceding equations gives a bound of

$|T_{G}(f)^{\prime}(a)|\leq K+R_{G}M,$ (180)

where $K$ is a constant only depending upon $G$ and not upon the bound $M$. If
$R_{G}<1$, we can choose $M>K(1-R_{G})^{-1}$ to guarantee that
$|T_{G}(f)^{\prime}(a)|\leq M$ as well. This proves that $T_{G}$ maps $S_{M}$
to itself. The proof is now completed by invoking the Schauder fixed point
theorem. ∎

Finally, we verify the assumptions of Lemma 3 for the function $G$ in (170) in
the case where $s=1$. A straightforward calculation gives that the integral in
(171) is maximized when $a=\min(1,\tau(1+\beta)^{\frac{1}{\beta}})$ and its
value is given by

$\frac{ca^{-(\beta+1)}}{\beta}\left(\left(\frac{a}{\tau}\right)^{\beta}-1\right).$
(181)

Plugging in the values $\beta=\beta^{*}$ and $\tau=\tau^{*}$ which give
equality in equations (169) and (167) for $s=1$, a straightforward numerical
calculation gives that $R_{G}<1$. Since this value is continuous in $\beta$
and $\tau$, the same holds for close enough $\beta$ and $\tau$.

Finally, we verify the existence of the functions $g_{1}$ and $g_{2}$ in Lemma
3. We consider the modified map

$\tilde{T}_{G}(f)(a)=\max\left(0,G(a)-a^{-1}\int_{\tau}^{a}f(x)f(a^{-1}x)dx\right).$
(182)

Starting with the function $f_{0}=G$, we iterate to obtain the sequence
$f_{k}=\tilde{T}_{G}(f_{k-1})$. The map $\tilde{T}_{G}$ is monotone, so that
$f_{0}\geq f_{2}\geq f_{4}\cdots$ and $f_{1}\leq f_{3}\leq f_{5}\cdots$.
Consequently, if $f_{2n+1}>0$ for some $n$, then $g_{1}=f_{2n+1}$ and
$g_{2}=f_{2n}$ will satisfy the conditions of Lemma 3. This follows since by
the monotonicity of $\tilde{T}_{G}$, $f\leq f_{2n}$ implies that
$\tilde{T}_{G}(f)\geq f_{2n+1}$ and $f\geq f_{2n+1}$ implies that
$\tilde{T}_{G}(f)\leq f_{2n+2}\leq f_{2n}$. Finally, $\tilde{T}_{G}(f)\geq
f_{2n+1}>0$ implies that $\tilde{T}_{G}$ and $T_{G}$ coincide, which shows
that the conditions of the Lemma are satisfied.

We verify numerically for $G(x)=c\tau^{-\beta}x^{\beta-1}$ given in (170),
with $\beta=\beta^{*}$ and $\tau=\tau^{*}$ (the optimal values for $s=1$),
that the iterates satisfy $f_{3}>0$. A plot of $f_{0},f_{1},f_{2}$, and
$f_{3}$ is shown in Figure 1. Since $f_{3}$ depends continuously on $G$ (and
thus on $\beta$ and $\tau$), this completes the proof of Theorem 1. Finally,
in Figure 1 we solve equation (170) numerically to give an idea of what the
optimal $f$ looks like.

Figure 1: Left: The first $3$ iterates of $\tilde{T}_{G}$, which demonstrate
that $f_{3}>0$. Right: The numerically calculated solution to (170) for the
$G$ corresponding to $\beta^{*}$ and $\tau^{*}$ for $s=1$.

##  3 Acknowledgements

We would like to thank Andrew Barron, Ron DeVore, Jinchao Xu, Vladimir
Temlyakov, and Matias Cattaneo for helpful discussions. JWS was supported in
part by the National Science Foundation through DMS-2111387 and CCF-2205004.
JMK was supported in part by the National Science Foundation through CAREER
DMS-2239448, DMS-2054808, and HDR TRIPODS CCF-1934924.

## References

  * [1] Barron, A.R., Cohen, A., Dahmen, W., DeVore, R.A.: Approximation and learning by greedy algorithms.  The Annals of Statistics 36(1), 64–94 (2008)
  * [2] Bergeaud, F., Mallat, S.: Matching pursuit of images.  In: Proceedings., International Conference on Image Processing, vol. 1, pp. 53–56. IEEE (1995)
  * [3] Breiman, L., Friedman, J., Olshen, R., Stone, C.: Classification and Regression Trees.  Belmont, Calif.: Wadsworth International Group, c1984. (1984).  DOI https://doi.org/10.1201/9781315139470
  * [4] Bühlmann, P., Yu, B.: Boosting with the L2 loss: regression and classification.  Journal of the American Statistical Association 98(462), 324–339 (2003)
  * [5] Chen, S.S., Donoho, D.L., Saunders, M.A.: Atomic decomposition by basis pursuit.  SIAM Review 43(1), 129–159 (2001)
  * [6] DeVore, R.A.: Nonlinear approximation.  Acta Numerica 7, 51–150 (1998)
  * [7] DeVore, R.A., Temlyakov, V.N.: Some remarks on greedy algorithms.  Advances in Computational Mathematics 5(1), 173–187 (1996)
  * [8] E, W., Ma, C., Wu, L.: The barron space and the flow-induced function spaces for neural network models.  Constructive Approximation 55(1), 369–406 (2022)
  * [9] Friedman, J.H.: Greedy function approximation: A gradient boosting machine.  The Annals of Statistics 29(5), 1189 – 1232 (2001).  DOI 10.1214/aos/1013203451.  URL https://doi.org/10.1214/aos/1013203451
  * [10] Jones, L.K.: A simple lemma on greedy approximation in hilbert space and convergence rates for projection pursuit regression and neural network training.  The Annals of Statistics 20(1), 608–613 (1992)
  * [11] Klusowski, J.M., Barron, A.R.: Approximation by combinations of ReLU and squared ReLU ridge functions with $\ell_{0}$ and $\ell_{1}$ controls.  IEEE Transactions on Information Theory 64(12), 7649–7656 (2018)
  * [12] Konyagin, S., Temlyakov, V.: Rate of convergence of pure greedy algorithm.  East J. Approx 5(4), 493–499 (1999)
  * [13] Kurková, V., Sanguineti, M.: Bounds on rates of variable-basis and neural-network approximation.  IEEE Transactions on Information Theory 47(6), 2659–2665 (2001)
  * [14] Li, Y., Siegel, J.: Entropy-based convergence rates of greedy algorithms.  arXiv preprint arXiv:2304.13332 (2023)
  * [15] Livshits, E.D.: Lower bounds for the rate of convergence of greedy algorithms.  Izvestiya: Mathematics 73(6), 1197 (2009)
  * [16] Livshitz, E., Temlyakov, V.: Two lower estimates in greedy approximation.  Constructive Approximation 19(4), 509–523 (2003)
  * [17] Mallat, S.G., Zhang, Z.: Matching pursuits with time-frequency dictionaries.  IEEE Transactions on Signal Processing 41(12), 3397–3415 (1993)
  * [18] Meyer, Y.: Wavelets and Operators: Volume 1.  37\. Cambridge University Press (1992)
  * [19] Neff, R., Zakhor, A.: Very low bit-rate video coding based on matching pursuits.  IEEE Transactions on Circuits and Systems for Video Technology 7(1), 158–171 (1997)
  * [20] Nelson, J.L., Temlyakov, V.N.: Greedy expansions in Hilbert spaces.  Proceedings of the Steklov Institute of Mathematics 280(1), 227–239 (2013)
  * [21] Ongie, G., Willett, R., Soudry, D., Srebro, N.: A function space view of bounded norm infinite width ReLU nets: The multivariate case.  In: International Conference on Learning Representations (ICLR 2020) (2019)
  * [22] Parhi, R., Nowak, R.D.: Banach space representer theorems for neural networks and ridge splines.  The Journal of Machine Learning Research 22(1), 1960–1999 (2021)
  * [23] Parhi, R., Nowak, R.D.: What kinds of functions do deep neural networks learn? Insights from variational spline theory.  SIAM Journal on Mathematics of Data Science 4(2), 464–489 (2022)
  * [24] Pisier, G.: Remarques sur un résultat non publié de B. Maurey.  Séminaire Analyse fonctionnelle (dit “Maurey-Schwartz") pp. 1–12 (1981)
  * [25] Siegel, J.W., Xu, J.: Characterization of the variation spaces corresponding to shallow neural networks.  arXiv preprint arXiv:2106.15002 (2021)
  * [26] Siegel, J.W., Xu, J.: Optimal convergence rates for the orthogonal greedy algorithm.  IEEE Transactions on Information Theory 68(5), 3354–3361 (2022)
  * [27] Siegel, J.W., Xu, J.: Sharp bounds on the approximation rates, metric entropy, and $n$-widths of shallow neural networks.  Foundations of Computational Mathematics pp. 1–57 (2022)
  * [28] Sil’nichenko, A.: Rate of convergence of greedy algorithms.  Mathematical Notes 76(3), 582–586 (2004)
  * [29] Temlyakov, V.: Greedy approximation, vol. 20.  Cambridge University Press (2011)