# Natural Language Models for Data Visualization
Utilizing nvBench Dataset

Shuo Wang and Carlos Crespo-Quinones

(DATASCI 266: Natural Language Processing
UC Berkeley School of Information
{shuo.wang<EMAIL_ADDRESS>
##  1 Introduction

Data visualization is an integral part of data analysis and reporting, highly
skilled professionals spend a significant portion of their working hours
constructing data queries and turning them into charts and graphs. The
potential application of machine learning models to understand the underlying
data and translate natural language queries into data visualization would
greatly enhance the efficiency and productivity of many data analysis tasks.
Not only would such tools enhance our existing capability to understand and
communicate with our data, it could also help us uncover previously hidden
information.

Some immediate applications include: creating bar, line and scatter plots of
SQL tables, transform and group data within a table and display the aggregated
data, as well as joining and combining tables of data to extract information
and display them visually.

Previous research in this area has included explorations of transforming
natural language into SQL commands[1, 3] with deep learning models and natural
language to visualization interfaces[4]. NvBench is a new dataset created to
facilitate this type of research to further integrate the process of natural
language to data query and data query to visualizations[2] . Leveraging this
data set and the ncNet transformer model architecture[5], we further explore
the various modeling possibilty in our work.

In this paper, we have used the nvBench as our train, validation and test
dataset to create BERT encoder based multi-head attention transformer models
and compare the performance of the new models with the performance of the
ncNet model (also a sequence to sequence transformer model). Our goal is to
explore the possibility of a generalized natural language to visualization
process where the ability of the system to handle natural language inputs is
not limited by the input training data. We have provided below the main
results of our research and detailed description and analysis of the input
data, model architecture and model performance. From our reseach, the BERT
encoder based sequence to sequence transformer model was able to achieve an
overall accuracy of 79%, confirming our hypothesis of the possibility to
leverage transferred learning of BERT models to data visualization tasks.
Applying a pre-trained CodeT5 model realizes even more impressive results,
achieving an overall accuracy of 97%.

##  2 Background

Natural language to visualization research has been conducted for decades,
some of these efforts include early approaches to manually program rule-based
logic for the handling of anticipated user inputs in multi-model systems[4]
and more recent attempts to incorporate machine learning and optimization
techniques[6]. However these systems are limited in functionality by the
ability of the system designers to anticipate the possible universe of inputs
from users. But what if the user uses a word that the system has never seen?
What if the natural language input was written in an idiomatic way that was
not present in the training data? These limitations could potentially be
addressed with the recent advances in large language models such as BERT and
GPT through transfer learning.

Recent research exists for applying BERT model to the task of data
visualization[7] by converting natural language into vector representation
embeddings and use these embeddings to predict various ingredients needed for
the visualization of tabular data such as chart type, data columns and
aggregation type. However, the structured approach to the problem inherently
limits the expressive power of the system to generate complex visualizations.

A new dataset, nvBench[2], was made publicly available for research purposes
in 2021. The dataset contains pairs of natural language queries and data
visualization commands in vega zero syntax[5]. A self-contained sequence-to-
sequence model, ncNet[5], created for and trained on the dataset was also made
available. We base our research on this dataset and the ncNet transformer
model, modifying the architecture to use BERT and other language models to
train and test generalizable natural language to data visualization models,
eventually applying the pre-trained T5 model to the problem and achieving
superior results.

##  3 Methods

###  3.1 Data

####  3.1.1 nvBench

The data set contains 7247 visualization queries (labels). Each query contains
a visualization type and data retrieval command meant to be run against an
underlying database with multiple tables, which contain the actual data to be
displayed. Below is an example of a visualization query:

> Visualize BAR SELECT JOB_ID , SUM(MANAGER_ID) FROM employees WHERE salary
> BETWEEN 8000 AND 12000 AND commission_pct != "null" OR department_id != 40
> GROUP BY JOB_ID ORDER BY JOB_ID ASC

Figure 1: Rendering: Visualize BAR SELECT JOB_ID , SUM(MANAGER_ID) FROM
employees WHERE salary BETWEEN 8000 AND 12000 AND commission_pct != "null" OR
department_id != 40 GROUP BY JOB_ID ORDER BY JOB_ID ASC.

In this example, the chart type is “BAR”, followed by the SQL statement for
data retrieval. Figure 1 shows the rendering result of the query.

The example visualization query is mapped to several natural language queries,
from which we train our models:

> 1\. For those employees whose salary is in the range of 8000 and 12000 and
> commission is not null or department number does not equal to 40, show me
> about the distribution of job_id and the sum of manager_id , and group by
> attribute job_id in a bar chart, I want to sort in ascending by the bar.
>
> 2\. For those employees whose salary is in the range of 8000 and 12000 and
> commission is not null or department number does not equal to 40, a bar
> chart shows the distribution of job_id and the sum of manager_id , and group
> by attribute job_id, and could you order x axis in asc order?

In total, there are 25762 natural language queries, averaging 3.55 natural
language queries for every visualization query.

####  3.1.2 Augmented Data

Due to the complexity of SQL syntax, a simplified version of the visualization
query is used in place of the original query, called vega zero[5]:

> mark bar data employees encoding x hire_date y aggregate count hire_date
> transform filter salary between 8000 and 12000 and commission_pct != "null"
> or department_id != 40 bin x by month

Where the visualization query is flattened into a sentence with special
markers designating locations of information, please refer to [5] for complete
syntax. In our research, we follow the same syntax rules.

Since this syntax only supports single table queries, it is not possible to
predict queries where the joining of tables is necessary, so we only train and
test our models on a subset of nvBench dataset, with 2988 visualization
queries for training, 186 visualization queries for validation and 625
visualization queries for testing.

The natural language queries are also augmented to include the template of
vega zero queries:

> <N> For those employees whose salary is in the range of 8000 and 12000 and
> commission is not null or department number does not equal to 40 , draw a
> line chart about the change of department_id over hire_date , display by the
> X from low to high . </N> <C> mark [T] data employees encoding x [X] y
> aggregate [AggFunction] [Y] color [Z] transform filter [F] group [G] bin [B]
> sort [S] topk [K] </C> <D> employees <COL> hire_date salary department_id
> last_name first_name </COL> <VAL> Bull Lex Seo Bell Chen Lee Gee Banda King
> Baer Fay </VAL> </D>

The natural language query is enclosed in <N> </N> markers, the vega zero
template is enclosed in <C> </D> markers and the locations of vega zero query
fields are marked by special tokens: [T], [X], [Y], [Z], [F], [G], [B], [S]
and [K]. These are the syntax used by the original ncNet sequence to sequence
transformer models and we follow the same rules for our models as well.
Finally, every natural language and visualization query pair in the dataset is
augmented with two versions, one with the chart type kept as placeholder, [T],
and another with the chart type filled in (bar, line, etc). The motivation is
to train the model to predict the visualization query whether the chart type
is explicitly specified or not.

####  3.1.3 Data Loader

The augmented data were provided in the Github repo for the ncNet paper[5] ,
which we use unaltered. However, the original data loader no longer works the
latest version of Pytorch, we rewrote the data loader to be used for training
and testing the ncNet model and our own models.

###  3.2 Model

####  3.2.1 ncNet

The ncNet[5] model is a sequence to sequence multi-head transformer model,
where the encoder transforms the natural language queries into embeddings
combining position and token type information, and apply multiple layers of
multi-head attention transformers to incorporate contextual information into
the encoded embeddings. Shown in Figure 2, The decoder then takes in the
encoded embeddings and the embeddings of the previously predicted tokens to
further transform the predicted tokens with attention to the encoded
embeddings. We use the ncNet model as our baseline, and replace the encoder
with various different architectures.

One important fact to note is that the ncNet model uses all words occurring in
the training, testing and validation dataset as vocabulary. Therefore limiting
the range of possibilities of natural language query inputs.

We also removed the attention mask (referred to as attention forcing in Luo
2022[5]) used in ncNet to create another baseline for our experiments, since
attention masks are not applicable to our models.

####  3.2.2 BERT Model

We then proceeded to replace the ncNet encoder with the BERT model encoder, as
shown in Figure 3. Because the BERT model was pre-trained with a much larger
vocabulary, the hope was that this knowledge would transfer to the new model,
ncBERT, once we fine-tuned it. We trained an additional BERT encoder model
with convolutional layers added to the BERT embeddings, in order to distill
relevant information from BERT model embeddings before decoding, as the BERT
embedding has a much larger dimension that may contain information irrelevant
to the data visualization task. The convolutional layers incorporated model is
shown in Figure 4.

####  3.2.3 Combining ncNet and BERT Model

Furthermore, we created an encoder combining both the ncNet and BERT encoders,
we achieved this by reshaping the embeddings from BERT to the same dimension
as ncNet encoder and concatenating them together. The architecture of the
model could be found in Figure 5. The motivation of creating this model was to
analyze the effect of BERT embedding on the baseline model and explore the
potential of enhancing the original encoder without completely replacing it.
However, the implication of this approach was that words that did not exist in
the original ncNet encoder still could not be used, further research needs to
be done to remove this limitation.

####  3.2.4 CodeT5

Finally, a series of experiments were conducted by fine-tuning two different
families of the pre-trained T5 model on the nvBench dataset. The first set of
models was conducted using variations of the original T5 model [8] by Raffel
et al. and the second set of experiments was based on the Code-T5 model family
[9] by Wang et al., which is a variation of the T5 model pre-trained for code
specific tasks. The experiments included using models of different parameter
sizes and modifying the input by including or not, the query templates along
with the input NL request. The results are very encouraging, where we achieved
98% prediction accuracy and 88% guided search accuracy using the “large” (700M
parameter) version of the CodeT5 model and using the same input sequence as
the other models which included both the template and the NL request. Figure 6
shows the architecture of the model.

###  3.3 Evaluation

The models are trained and tested with training dataset of size 25238,
validation dataset of size 1430 and test dataset of size 4920. Each model is
run over at least 5 epochs with a learning rate of 0.0005 and the resulting
losses are recorded. Then the accuracy of the models are evaluated by running
predictions with the models over the test dataset, with the natural language
query tokens and the first n-1 tokens of the label as input (the label tokens
are masked so that successive predictions of the label are not affected by
future label tokens), counting the total number of correct predictions and
dividing it by the total number of predictions.

Finally, we evaluate the models one more time with a guide search algorithm
for prediction. The algorithm starts the prediction with the start of the
sentence token, then repeatedly predicts the next label token with guidance
until the end of the sentence token is reached. This evaluation provides a
more realistic measure of the model’s usability. The accuracy from this
evaluation is defined as the total number of complete label matches over the
total number of test labels.

##  4 Results and Discussion

###  4.1 Accuracy

After running 5 epochs with learning rate 0.0005 and keeping the model version
with the lowest validation loss, the test accuracy of the models are reported
in Table 1. The accuracy of a model is defined as the probability of
predicting the next word correctly given part of the label query.

Table 1: Model test accuracy. Model | Query | Query+Chart | Overall
---|---|---|---
ncNet | 95% | 96% | 96%
ncNet w/o AF | 95% | 96% | 96%
nvBERT | 79% | 79% | 79%
nvBERT_CNN | 79% | 79% | 79%
nvncNetBERT | 89% | 89% | 89%
codeT5 w/o TPT | 97% | n/a | 97%
codeT5 | 97% | 97% | 97%
codeT5 Large | 98% | 98% | 98%

The table shows three columns, the accuracy of the models on queries where
chart type is not specified (Query), the accuracy of the models on queries
where chart type is specified (Query+Chart) and the overall accuracy
(Overall).

As we can see from the results, the original ncNet models produced test
accuracies in excess of 95%. While the BERT based transformer models were able
to achieve close to 80% accuracy. This is attributable to the fact that the
BERT model contains a much larger vocabulary than the ncNet model trained only
on the vocabulary of tokens present in the dataset.

Furthermore, the removal of attention forcing in the ncNet model does not
appear to affect the test accuracy, suggesting that its absence in nvBERT
models had no bearing on the accuracy results of the nvBERT models. The
accuracy of nvBERT models with and without convolutional layers does not
appear to affect the accuracy at all, suggesting minimal impact of the
convolutional layers. Finally the combined ncNet and BERT encoder produced
results that improved upon the nvBERT only models, suggesting that were a
model able to combine the ncNET and BERT encoder while remaining
generalizable, the results would improve along with the benefits of transfer
learning.

CodeT5 models achieved superior results across the board, surpassing both the
original ncNet model as well as the BERT encoder integrated models. What is
more exciting is the fact that, even without templates as input, codeT5 models
are still able to achieve comparable results.

Besides the overall accuracy difference, the general trend is that the
accuracy for “query only tests are slightly” lower than accuracy for “query
and chart type” tests. This is expected since the query only tests require the
model to predict an additional field. However, given that the accuracy
differences are small, the chart type prediction is generally accurate.

###  4.2 Guided Search Accuracy

We next look at the accuracy of predicting the entire label query. The
algorithm of guided search, as used by the original ncNet model, proceeds as
follows: starting with the start of sentence token for the label, successively
predict the top five candidates. Within the top five candidates, the top
candidate is chosen unless it does not belong to the possible words for the
current position being predicted, in which case the rest of the candidates are
iterated over to find a suitable choice. The prediction is counted as correct
if the resulting sentence matches the label sentence completely. Table 2 shows
the results for each model.

Table 2: Model test accuracy with guided search. Model | Query | Query+Chart | Overall
---|---|---|---
ncNet (baseline) | 62% | 72% | 67%
ncNet w/o AF | 65% | 75% | 70%
nvBERT | 3% | 13% | 8%
nvBERT_CNN | 2% | 12% | 7%
nvncNetBERT | 21% | 33% | 27%
codeT5 w/o TPT | 83% | n/a | 83%
codeT5 | 86% | 87% | 86%
codeT5 Large | 89% | 88% | 88%

From looking at the results, it’s immediately clear that the lower accuracy in
the BERT based models are amplified through the guided search process,
resulting in a low overall accuracy of 7.8%. This effect also shows up in the
difference between query only and query with chart type accuracy, where the
small difference in Table 1 becomes much larger in Table 2.

The codeT5 models again show great results. Furthermore, the results for query
only and query plus template again show comparable results, demonstrating the
power of the codeT5 model decoder.

###  4.3 Sample Analysis

####  4.3.1 nvBERT

Given the large discrepancy between the overall accuracy and the guided search
accuracy due to the flaws of the respective metrics, we need a better
understanding of the true performance of the new models with BERT encoders.
One of the things to observe is that in the predicted query, many of the words
are part of the template and rarely changes. These words need to be separated
out because the correction prediction of them mostly requires the model to
simply be position aware. As an example:

> Query: <N> Plot how many booking start date by grouped by booking start date
> as a bar graph , order Y in ascending order . </N> <C> mark [T] data
> apartment_bookings  encoding x [X] y aggregate [AggFunction] [Y] color [Z]
> transform filter [F] group [G] bin [B] sort [S] topk [K] </C> <D>
> apartment_bookings <COL> booking_start_date </COL> <VAL> </VAL> </D>

> Label: mark bar data apartment_bookings encoding x booking_start_date y
> aggregate count booking_start_date transform sort y asc bin x by weekday
> <eos>

Words such as “mark”, “data”, “encoding”, “aggregate” and “transform” always
appear in the label and in fixed positions, the model is able to predict them
almost perfectly. Words that are also part of the template such as “x”, “y”,
“color”, “filter”, “group”, “bin”, “sort” and “topk” may not occur in the
label or may occur more than once, are harder to predict.

Table 3 shows the count of words that are part of template vs non-template, on
average, there are more template words than non-template words, which
partially account for why word prediction accuracy is much higher than guided
search accuracy.

Table 3: Count of words that are template and non-template. Count | TPT | Non-TPT | Total
---|---|---|---
mean | 10.5 | 8.5 | 18.9
min | 6 | 4 | 12
max | 13 | 22 | 34

Table 4 shows the summary statistics for the count of incorrect predictions
made by the nvBERT model on the easy template words, hard template words and
non-template words. The rate of incorrect prediction is much higher for hard
template words than easy template words, as expected. The third column shows
the statistics for incorrect prediction of non-template words, curiously the
minimum of incorrect prediction is 1, which indicates that every prediction
has at least one incorrectly predicted word, yet the guided search did result
in completely correct predictions. The cause behind this apparent discrepancy
is that for the guided search, predicted words are checked for whether it is
possible for the word to occupy the position. Below shows an example:

Table 4: Incorrect prediction for easy template, hard template, total template and non-template prediction count. Incorrect | Easy | Hard | TPT | Non-TPT
---|---|---|---|---
mean | 0 | 0.6 | 0.6 | 3.4
min | 0 | 0 | 0 | 1
max | 1 | 4 | 4 | 12

> Query: <N> List all the possible ways to get to attractions , together with
> the number of attractions accessible by these methods in a bar chart , and
> sort names in asc order please . </N> <C> mark [T] data tourist_attractions
> encoding x [X] y aggregate [AggFunction] [Y] color [Z] transform filter [F]
> group [G] bin [B] sort [S] topk [K] </C> <D> tourist_attractions <COL> name
> how_to_get_there </COL> <VAL> walk bus </VAL> </D>

> Label: mark bar data tourist_attractions encoding x how_to_get_there y
> aggregate count how_to_get_there transform group x sort x asc <eos>

> Prediction: mark bar data employees encoding x how_to_get_there y aggregate
> count how_to_get_there transform group x sort x asc <eos>

Although the prediction has incorrectly predicted “employees” instead of
“tourist_attractions”, “employees” is not the name of the table under
consideration, therefore guided search chose the word that matches the table
name instead, resulting in a correct prediction.

Table 5 shows the breakdown of nvBERT model prediction accuracy by category.
As expected, template words prediction accuracy is much higher than non-
template words.

Table 5: nvBERT prediction accuracy breakdown. Easy | Hard | TPT | Non-TPT | Total
---|---|---|---|---
100% | 89% | 94% | 60% | 79%

Finally, Table 6 shows the accuracy of the nvBERT model at predicting the
chart type, “arc”, “bar”, “line” or “point”. The accuracy is broken down by
whether the chart type is already provided by the source query, interestingly,
providing chart type in source query does not improve the accuracy of
predicting chart type, which is also reflected in Table 1. However, the
provided chart type does help guided search to determine whether the predicted
chart type is valid or not, thereby improving the guided search accuracy 2.

Table 6: nvBERT chart type prediction accuracy breakdown. Query | Query+Chart
---|---
19% | 19%

####  4.3.2 CodeT5

For inference, the standard model decoder was used. Even though certain words
such as table names and available column choices were encouraged via including
them with the model input, no output tokens were forced. With this in mind the
results from fine-tuning the CodeT5 model has been phenomenal, achieving a
final token accuracy of 98%. The model showed a good ability to predict the
general structure of the query with a 96% success rate predicting query
keywords (i.e. “count”, “group”, “transform”, etc.) and in 93% of the cases,
was able to correctly identify the column names. A results review shows that
in the majority of the cases, the error was semantic or abbreviation related.
For example, for a label column name of ‘market_val‘ the model would predict
‘market_value‘. In other cases the error was more related to the way the
question was asked and the column name. For instance the model would predict
“profit” instead of “profit_dollars” because the question would ask for
profits without mentioning dollars.

Table 7: CodeT5 performance breakdown by difficulty level. Hardness | Success | Failure | Success Rate
---|---|---|---
Easy | 1451 | 147 | 91%
Medium | 1869 | 233 | 89%
Hard | 605 | 135 | 81%
Extra Hard | 384 | 52 | 88%

When comparing exact query matches as shown in Table 7, the CodeT5 model
consistently achieved high performance across difficulty levels, suggesting
that the complexity of language and label query structure is not a significant
limiting factor in its performance. A quick examination of the results show
that in many of the cases the errors were systemic in nature and could easily
be corrected by a series of logical filters. Some of these errors involved
unmatched ‘%‘ signs which are used for wildcards. For instance, to match
values with the letter “a” the pattern would be ‘%a%‘. The other most common
error involved a lack of a white-space preceding the unequal operator ‘!=‘.
Please refer to the appendix for examples. In fact, fixing this one error
improved the query accuracy from 83% to 88% as can be seen in Table 8. The
rest of the errors were more nuanced in nature and involved commonly being
unable to correctly predict the transform sections which tended to be the most
complex. In this area the CodeT5 model only achieved a 90% success rate.

Table 8: CodeT5 success rate before and after error correction. Before Correction | After Correction
---|---
83% | 88%

##  5 Conclusion

Through our research and analysis, we have demonstrated the potential of
transfer learning through the use of the BERT model as encoder for natural
language to visualization tasks, specifically applied to the nvBench dataset.
With the result of the CodeT5 model trained and tested on the nvBench dataset
we see that the problem could be adequately modeled as a natural language to
code translation problem. With more sophisticated architecture and more
comprehensive data visualization language, it is clear that natural language
to data visualization translation could be done very effectively and in a
general manner with existing large language models.

Of course, there are still many areas that remain to be explored. First, a
more generic visualization language needs to be developed to accommodate more
complex requests, the design of this language should be guided by the
effectiveness with which it could be predicted by language models. Second,
more database design should take into account the need for visualization, and
integrate machine learning translation as part of the research and development
process. We hope our research would contribute to the progress of these
initiatives.

## References

  * [1] Victor. Zhong et al.  Seq2sql: Generating structured queries from natural language using reinforcement learning.  arXiv:1709.00103v7 [cs.CL], November 2017.
  * [2] Yuyu. Luo et al.  nvbench: A large-scale synthesized dataset for cross-domain natural language to visualization task.  arXiv:2112.12926v1 [cs.HC], December 2021.
  * [3] Tao. Yu et al.  Cosql: A conversational text-to-sql challenge towards cross-domain natural language interfaces to databases.  arXiv:1909.05378v1 [cs.CL], September 2019.
  * [4] Kenneth. Cox et al.  A multi-modal natural language interface to an information visualization environment.  International Journal of Speech Technology, 2001.
  * [5] Yuyu. Luo et al.  Natural language to visualization by neural machine translation.  IEEE Transactions on Visualization and Computer Graphics, vol. 28, no. 1, pp. 217-226, January 2022.
  * [6] Jillian. Aurisano et al.  Articulate2: Toward a conversational interface for visual data exploration.  IEEE VIS ’16 (Poster paper), January 2016.
  * [7] Can. Liu et al.  Advisor: Automatic visualization answer for natural-language question on tabular data.  2021 IEEE 14th Pacific Visualization Symposium (PacificVis), January 2021.
  * [8] Colin. Raffel et al.  Exploring the limits of transfer learning with a unified text-to-text transformer.  Journal of Machine Learning Research, 2020.
  * [9] Yue. Wang et al.  Codet5: Identifier-aware unified pre-trained encoder-decoder models for code understanding and generation.  Conference on Empirical Methods in Natural Language Processing, 2021\.

## APPENDIX

###  .1 Model Architectures

Figure 2: Architecture of ncNet model. Figure 3: Architecture of nvBERT model.
Figure 4: Architecture of nvBERT_CNN model. Figure 5: Architecture of
nvncNetBERT model. Figure 6: Architecture of CodeT5 models applied to nvBench.

###  .2 CodeT5 Error Examples

We further examine some of the cases where the codeT5 model fails to predict
the label exactly:

> Label: mark bar data customer encoding x cust_name y aggregate none acc_bal
> transform filter cust_name like ’%a%’ sort y desc

> Prediction: mark bar data customer encoding x cust_name y aggregate none
> acc_bal transform filter cust_name like ’%a’ sort y desc

In the first example, the predicted vega zero query is missing a “%” sign
after “%a”.

> Label: mark bar data employees encoding x hire_date y aggregate count
> hire_date transform filter salary between 8000 and 12000 and commission_pct
> != "null" or department_id != 40 sort y asc bin x by ’weekday

> Prediction: mark bar data employees encoding x hire_date y aggregate count
> hire_date transform filter salary between 8000 and 12000 and
> commission_pct!= "null" or department_id!= 40 sort y asc bin x by weekday

In the second example, a space is missing before “!=”. We have systematically
corrected these mistakes for our final success rate. Table 8 shows the
improvement of results.

###  .3 Training and Loss

Figure 7: Train and validation loss of models.

The results of train and validation loss for ncNet, ncNet without attention
forcing, nvBERT, nvBERT_CNN and nvncNetBERT are shown for the first 5 epochs
in Figure 7. The BERT encoder models show much smaller drop in train loss from
epoch to epoch, due to transfer learning that occurs. However the BERT encoder
models do not show significant drop in validation loss, suggesting that most
of the fine-tuning has happened in the first epoch.


# Larger greedy sums for reverse partially greedy bases

Hùng Việt Chu<EMAIL_ADDRESS>Department of Mathematics, University of
Illinois at Urbana-Champaign, Urbana, IL 61820, USA

###### Abstract.

An interesting result due to Dilworth et al. was that if we enlarge greedy
sums by a constant factor $\lambda>1$ in the condition defining the greedy
property, then we obtain an equivalence of the almost greedy property, a
strictly weaker property. Previously, the author of the present paper showed
that enlarging greedy sums by $\lambda$ in the condition defining the
partially greedy (PG) property also strictly weakens the property. However,
enlarging greedy sums in the definition of reverse partially greedy (RPG)
bases by Dilworth and Khurana again gives RPG bases. The companion of PG and
RPG bases suggests the existence of a characterization of RPG bases which,
when greedy sums are enlarged, gives an analog of a result that holds for
partially greedy bases. In this paper, we show that such a characterization
indeed exists, answering positively a question previously posed by the author.

###### Key words and phrases:

reverse partially greedy; greedy sum; bases.

###### 2020 Mathematics Subject Classification:

41A65; 46B15

The author is thankful to Timur Oikhberg for helpful comments on an earlier
draft of this paper.

###### Contents

  1. 1 Introduction
  2. 2 A characterization of RPG and PG bases
  3. 3 Larger greedy sums for RPG bases
  4. 4 ($\lambda$, RPGII) bases are weaker than RPG bases

##  1\. Introduction

Let $\mathbb{X}$ be an infinite-dimensional Banach space (with dual
$\mathbb{X}^{*}$) over the field $\mathbb{K}=\mathbb{R}$ or $\mathbb{C}$. We
define a basis to be any countable collection
$\mathcal{B}=(e_{n})_{n=1}^{\infty}$ such that i) the span of $(e_{n})_{n}$ is
norm-dense in $\mathbb{X}$; ii) there exist biorthogonal functionals
$(e^{*}_{n})_{n}\subset\mathbb{X}^{*}$ such that
$e^{*}_{n}(e_{m})=\delta_{n,m}$; and iii) there exist $c_{1},c_{2}>0$ such
that $c_{1}\leqslant\|e_{n}\|,\|e_{n}^{*}\|\leqslant c_{2}$ for all $n$. In
the literature, the condition of totality:
$\overline{\operatorname{span}(e^{*}_{n})}^{w^{*}}=X^{*}$ is sometimes called
for. While totality guarantees that for each $x$, the sequence
$(e_{n}^{*}(x))_{n=1}^{\infty}$ is unique, uniqueness is not important in this
paper, so we do not assume that our basis is total.

In 1999, Konyagin and Temlyakov [11] introduced the notion of greedy bases as
follows: for each $x\in\mathbb{X}$, a finite set $\Lambda$ is a greedy set of
$x$ if

$\min_{n\in\Lambda}|e_{n}^{*}(x)|\ \geqslant\
\max_{n\notin\Lambda}|e_{n}^{*}(x)|.$

For $m\in\mathbb{N}$, let $G(x,m)$ denote the set of all greedy sets of $x$ of
cardinality $m$. A basis is said to be greedy if there exists a constant
$\mathbf{C}\geqslant 1$ such that

$\|x-P_{\Lambda}(x)\|\ \leqslant\ \mathbf{C}\sigma_{m}(x),\forall
x\in\mathbb{X},\forall m\in\mathbb{N},\forall\Lambda\in G(x,m),$ (1.1)

where

$\sigma_{m}(x)\ :=\ \inf\left\\{\left\|x-\sum_{n\in
A}a_{n}e_{n}\right\|\,:\,a_{n}\in\mathbb{K},|A|\leqslant m\right\\}.$

Later, Dilworth et al. [8] introduced the so-called almost greedy bases: a
basis is almost greedy if there exists a constant $\mathbf{C}\geqslant 1$ such
that

$\|x-P_{\Lambda}(x)\|\ \leqslant\
\mathbf{C}\inf\\{\|x-P_{A}(x)\|:|A|=m\\},\forall x\in\mathbb{X},\forall
m\in\mathbb{N},\forall\Lambda\in G(x,m),$ (1.2)

where $P_{A}(x)=\sum_{n\in A}e_{n}^{*}(x)e_{n}$. By definition, a greedy basis
is almost greedy, but an almost greedy basis is not necessarily greedy (see
[3, Example 10.2.9]). Among other results, Dilworth et al. showed a suprising
equivalence of almost greedy bases. In particular, for any fixed $\lambda>1$,
if we enlarge greedy sums from size $m$ to $\lceil\lambda m\rceil$ in (1.1) to
have

$\|x-P_{\Lambda}(x)\|\ \leqslant\ \mathbf{C}\sigma_{m}(x),\forall
x\in\mathbb{X},\forall m\in\mathbb{N},\forall\Lambda\in G(x,\lceil\lambda
m\rceil),$ (1.3)

then the condition (1.3) is equivalent to the condition (1.2) (with possibly
different constants). That is, by increasing the size of greedy sums, we move
from the realm of greedy bases to a strictly weaker realm of almost greedy
bases.

Continuing the work, the author of the present paper [7] investigated the
situation for partially greedy (PG) bases (also introduced by Dilworth et al.
for Schauder bases [8] and by Berasategui et al. for general bases [6]), which
are defined to satisfy the condition: there exists a constant
$\mathbf{C}\geqslant 1$ such that

$\|x-P_{\Lambda}(x)\|\ \leqslant\ \mathbf{C}\inf_{k\leq
m}\left\|x-\sum_{n=1}^{k}e_{n}^{*}(x)e_{n}\right\|,\forall
x\in\mathbb{X},\forall m\in\mathbb{N},\forall\Lambda\in G(x,m).$ (1.4)

According to [7, Theorem 1.5], if we enlarge the size of greedy sums from $m$
to $\lceil\lambda m\rceil$ in (1.4), we obtain strictly weaker greedy-type
bases. Therefore, similar to Dilworth et al.’s result, enlarging greedy sums
in the PG property strictly weakens the property.

To complete the picture, let us consider reverse partially greedy (RPG) bases
introduced by Dilworth and Khurana [9]. The original definition of RPG [9] is
relatively more technical: first, given two sets $A,B\subset\mathbb{N}$, we
write $A>B$ if for all $a\in A$ and $b\in B$, we have $a>b$. Respective
definitions hold for other inequalities $<,\geqslant$, and $\leqslant$. Also,
it holds vacuously that $\emptyset>A$ and $\emptyset<A$ for all sets $A$. A
basis is RPG if there exists a constant $\mathbf{C}\geqslant 1$ such that

$\|x-P_{\Lambda}(x)\|\ \leqslant\
\mathbf{C}\widetilde{\sigma}^{R,\Lambda}_{m}(x),\forall x\in\mathbb{X},\forall
m\in\mathbb{N},\forall\Lambda\in G(x,m),$ (1.5)

where

$\widetilde{\sigma}^{R,\Lambda}_{m}(x)\ =\
\inf\\{\|x-P_{A}(x)\|\,:\,|A|\leqslant m,A>\Lambda\\}.$

Recent work has confirmed that RPG bases are truly companions of PG bases (see
[7, 9, 10]). That is, if a result holds true for PG bases, there is a
corresponding result that holds for RPG bases. We, therefore, suspect that as
in the case of PG bases, if we enlarge the size of greedy sums in a condition
that defines RPG bases, we would then obtain a strictly weaker greedy-type
bases. However, by [7, Theorem 6.4], enlarging greedy sums in (1.5) still
gives us RPG bases. This hints us at the existence of an equivalent
reformulation of RPG bases such that when we enlarge greedy sums in the
reformulation, we strictly weaken the RPG property. The main results in this
paper show that such an equivalent reformulation indeed exists.

Given a set $A\subset\mathbb{N}$, define

$\widecheck{\sigma}^{A}_{m}(x)\ :=\ \inf\\{\|x-P_{I}(x)\|\,:\,\mbox{either
}I=\emptyset\mbox{ or }I\mbox{ is an interval},A\leqslant\max I,|I|\leqslant
m\\}.$

Our first result gives an equivalence of the notion of RPG bases.

######  Theorem 1.1.

A basis $\mathcal{B}$ is RPG if and only if there exists $\mathbf{C}\geqslant
1$ such that

$\|x-P_{\Lambda}(x)\|\ \leqslant\
\mathbf{C}\widecheck{\sigma}^{\Lambda}_{m}(x),\forall x\in\mathbb{X},\forall
m\in\mathbb{N},\forall\Lambda\in G(x,m).$ (1.6)

To the author’s knowledge, (1.6) is the first characterization of RPG bases
such that the right side of (1.6) involves a projection onto consecutive
elements of the basis. This resembles (1.4), which defines partially greedy
bases. Indeed, (1.6) highlights the correspondence between partially greedy
bases and RPG bases by revealing the relative position of the interval $I$
with respect to the greedy set $\Lambda$. Specifically, for partially greedy
bases, since we project onto the first elements of $\mathcal{B}$, we have
$\min I\leqslant\Lambda$, while for RPG bases, $\Lambda\leqslant\max I$. We
also have a new characterization of partially greedy bases.

######  Theorem 1.2.

A basis $\mathcal{B}$ is PG if and only if there exists $\mathbf{C}\geqslant
1$ such that

$\|x-P_{\Lambda}(x)\|\ \leqslant\
\mathbf{C}\widehat{\sigma}^{\Lambda}_{m}(x),\forall x\in\mathbb{X},\forall
m\in\mathbb{N},\forall\Lambda\in G(x,m),$

where

$\widehat{\sigma}^{\Lambda}_{m}(x)\ :=\ \inf\\{\|x-P_{I}(x)\|\,:\,\mbox{either
}I=\emptyset\mbox{ or }I\mbox{ is an interval},\Lambda\geqslant\min
I,|I|\leqslant m\\}.$

Next, for any fixed $\lambda\geqslant 1$, we study the following condition:
there exists $\mathbf{C}\geqslant 1$ such that

$\|x-P_{\Lambda}(x)\|\ \leqslant\
\mathbf{C}\widecheck{\sigma}_{m}^{\Lambda}(x),\forall x\in\mathbb{X},\forall
m\in\mathbb{N},\forall\Lambda\in G(x,\lceil\lambda m\rceil).$ (1.7)

As stated above, our goal is to show that (1.7) is strictly weaker than the
RPG property to have an analog of Dilworth et al.’s theorem for RPG bases.
First, we give bases that satisfy (1.7) a name.

######  Definition 1.3.

A basis $\mathcal{B}$ is said to be ($\lambda$, RPG) of type II (or
($\lambda$, RPGII), for short) if $\mathcal{B}$ satisfies (1.7). In this case,
the least constant in (1.7) is denoted by $\mathbf{C}_{\lambda,rp}$.

Here we use “of type II" to not confuse ourselves with ($\lambda$, RPG) bases
in [7, Definition 6.1]. A basis is ($\lambda$, RPG) of type I if we enlarge
the size of greedy sums in (1.5) from $m$ to $\lceil\lambda m\rceil$. For all
$\lambda\geqslant 1$, the ($\lambda$, RPG) property in [7, Definition 6.1] is
equivalent to RPG property (see [7, Theorem 6.4]). We shall show that this is
not the case for the ($\lambda$, RPGII) property.

######  Theorem 1.4.

Let $\lambda>1$. The following hold.

  1. i)

If $\mathcal{B}$ is RPG, then $\mathcal{B}$ is ($\lambda$, RPGII).

  2. ii)

There exists an unconditional basis $\mathcal{B}$ that is ($\lambda$, RPGII)
but is not RPG.

To prove Theorem 1.4, we need to characterize characterize ($\lambda$, RPGII)
bases with the introduction of the so-called reverse partial symmetry for
largest coefficients (Definition 3.2). As a corollary of our characterization,
we characterize bases that satisfy (1.6) with constant $\mathbf{C}=1$ (or
$1$-($1$, RPGII) bases) in the same manner as Berasategui et al. characterized
$1$-strong partially greedy bases [6].

######  Corollary 1.5.

A basis satisfies (1.5) with $\mathbf{C}=1$ if and only if it satisfies (1.6)
with $\mathbf{C}=1$.

For the full statement, see Corollary 3.12.

##  2\. A characterization of RPG and PG bases

We recall some well-known results that will be used in due course.

######  Definition 2.1 (Konyagin and Temlyakov [11]).

A basis $\mathcal{B}$ is quasi-greedy if there exists $\mathbf{C}>0$ such that

$\|P_{\Lambda}(x)\|\ \leqslant\ \mathbf{C}\|x\|,\forall
x\in\mathbb{X},m\in\mathbb{N},\forall\Lambda\in G(x,m).$

The least such $\mathbf{C}$ is denoted by $\mathbf{C}_{q}$, called the quasi-
greedy constant. Also when $\mathcal{B}$ is quasi-greedy, let
$\mathbf{C}_{\ell}$ be the least constant such that

$\|x-P_{\Lambda}(x)\|\ \leqslant\
\mathbf{\mathbf{missing}}\mathbf{C}_{\ell}\|x\|,\forall
x\in\mathbb{X},m\in\mathbb{N},\forall\Lambda\in G(x,m).$

We call $\mathbf{C}_{\ell}$ the suppression quasi-greedy constant.

A sequence $\varepsilon=(\varepsilon_{n})_{n}$ is called a sign if
$\varepsilon_{n}\in\mathbb{K}$ and $|\varepsilon_{n}|=1$. For $x\in\mathbb{X}$
and a finite set $A\subset\mathbb{N}$, let

$1_{A}\ =\ \sum_{n\in A}e_{n},1_{\varepsilon A}\ =\ \sum_{n\in
A}\varepsilon_{n}e_{n},\mbox{ and }P_{A^{c}}(x)\ =\ x-P_{A}(x).$

Two important properties of quasi-greedy bases are the UL property and the
uniform boundedness of the truncation operators.

  1. i)

UL property: for all finite $A\subset\mathbb{N}$ and scalars $(a_{n})$, we
have

$\frac{1}{2\mathbf{C}_{q}}\min|a_{n}|\|1_{A}\|\ \leqslant\ \left\|\sum_{n\in
A}a_{n}e_{n}\right\|\ \leqslant\ 2\mathbf{C}_{q}\max|a_{n}|\|1_{A}\|,$

which was first proved in [8].

  2. ii)

the uniform boundedness of the truncation operator: for each $\alpha>0$, we
define the truncation function $T_{\alpha}$ as follows: for $b\in\mathbb{K}$,

$T_{\alpha}(b)\ =\ \begin{cases}\operatorname{sgn}(b)\alpha,&\mbox{ if
}|b|>\alpha,\\\ b,&\mbox{ if }|b|\leqslant\alpha.\end{cases}$

We define the truncation operator $T_{\alpha}:\mathbb{X}\rightarrow\mathbb{X}$
as

$T_{\alpha}(x)\ =\ \sum_{n=1}^{\infty}T_{\alpha}(e_{n}^{*}(x))e_{n}\ =\ \alpha
1_{\varepsilon\Lambda_{\alpha}(x)}+P_{\Lambda_{\alpha}^{c}(x)}(x),$

where $\Lambda_{\alpha}(x)=\\{n:|e_{n}^{*}(x)|>\alpha\\}$ and
$\varepsilon_{n}=\operatorname{sgn}(e_{n}^{*}(x))$ for all
$n\in\Lambda_{\alpha}(x)$.

######  Theorem 2.2.

[5, Lemma 2.5] Let $\mathcal{B}$ be $\mathbf{C}_{\ell}$-suppression quasi-
greedy. Then for any $\alpha>0$, $\|T_{\alpha}\|\leqslant\mathbf{C}_{\ell}$.

Now we recall a characterization of RPG bases due to Dilworth and Khurana [9].

######  Definition 2.3.

A basis $\mathcal{B}$ is said to be reverse conservative if for some constant
$\mathbf{C}>0$, we have

$\|1_{A}\|\ \leqslant\ \mathbf{C}\|1_{B}\|,$

for all finite sets $A,B\subset\mathbb{N}$ with $|A|\leqslant|B|$ and $B<A$.
In this case, the least constant $\mathbf{C}$ is denoted by $\Delta_{rc}$.

######  Theorem 2.4.

[9, Theorem 2.7] A basis is RPG if and only if it is reverse conservative and
quasi-greedy.

We are ready to prove our first main result.

###### Proof of Theorem 1.1.

Assume (1.6). By Theorem 2.4, we need to show that $\mathcal{B}$ is both
quasi-greedy and reverse conservative. First, we observe that $\mathcal{B}$ is
$\mathbf{C}$-suppression quasi-greedy since by definition,
$\widecheck{\sigma}^{\Lambda}_{m}(x)\leqslant\|x\|$ for all $x\in\mathbb{X}$,
$m\in\mathbb{N}$ and $\Lambda\in G(x,m)$. Next, we show that $\mathcal{B}$ is
reverse conservative. Let $A,B\subset\mathbb{N}$ be finite with $B<A$ and
$|A|\leqslant|B|$. If $A=\emptyset$, there is nothing to prove. Suppose
$A\neq\emptyset$. Define $x=1_{A}+1_{B}+1_{D}$, where $D=[\min A,\max
A]\backslash A$. Since $B\cup D$ is a greedy set of $x$ and $A\cup D$ is an
interval of length $|A\cup D|\leqslant|B\cup D|$ with $B\cup D<\max(A\cup D)$,
we have

$\|1_{A}\|\ =\ \|x-P_{B\cup D}(x)\|\ \leqslant\
\mathbf{C}\widecheck{\sigma}^{B\cup D}_{|B\cup D|}(x)\ \leqslant\
\mathbf{C}\|x-P_{A\cup D}(x)\|\ =\ \mathbf{C}\|1_{B}\|.$

Now we assume that $\mathcal{B}$ is RPG. According to Theorem 2.4,
$\mathcal{B}$ is $\mathbf{C}_{q}$-quasi-greedy and $\Delta_{rc}$-reverse
conservative for some $\mathbf{C}_{q},\Delta_{rc}>0$. Fix $x\in\mathbb{X}$,
$m\in\mathbb{N}$, $\Lambda\in G(x,m)$, and a nonempty interval $I$ with
$|I|\leqslant m$, $\Lambda\leqslant\max I$. We shall show that

$\|x-P_{\Lambda}(x)\|\ \leqslant\
(1+\mathbf{C}_{q}+4\mathbf{C}^{3}_{q}\Delta_{rc})\|x-P_{I}(x)\|.$

Write

$\|x-P_{\Lambda}(x)\|\ \leqslant\ \|x-P_{I}(x)\|+\|P_{\Lambda\backslash
I}(x)\|+\|P_{I\backslash\Lambda}(x)\|.$ (2.1)

Since $\Lambda\backslash I$ is a greedy set of $x-P_{I}(x)$, we get

$\|P_{\Lambda\backslash I}(x)\|\ \leqslant\ \mathbf{C}_{q}\|x-P_{I}(x)\|.$
(2.2)

Let us estimate $\|P_{I\backslash\Lambda}(x)\|$. Note that $\Lambda\backslash
I<I\backslash\Lambda$. Otherwise, there exists $a\in\Lambda\backslash I$,
$b\in I\backslash\Lambda$ such that $a\geqslant b$. Then $a\geqslant\min I$
and $a\leqslant\max\Lambda\leqslant\max I$. Hence, $a\in I$, which contradicts
$a\in\Lambda\backslash I$. Furthermore,
$|I\backslash\Lambda|\leqslant|\Lambda\backslash I|$ because
$|I|\leqslant|\Lambda|$. Since $\mathcal{B}$ is $\Delta_{rc}$-reverse
conservative, we get

$\|1_{I\backslash\Lambda}\|\ \leqslant\ \Delta_{rc}\|1_{\Lambda\backslash
I}\|.$

We have

$\displaystyle\left\|\sum_{n\in I\backslash\Lambda}e_{n}^{*}(x)e_{n}\right\|$
$\displaystyle\ \leqslant\ \max_{n\in
I\backslash\Lambda}|e_{n}^{*}(x)|\sup_{\varepsilon}\left\|1_{\varepsilon(I\backslash\Lambda)}\right\|\mbox{
by convexity}$ $\displaystyle\ \leqslant\
2\mathbf{C}_{q}\min_{n\in\Lambda\backslash
I}|e_{n}^{*}(x)|\left\|1_{I\backslash\Lambda}\right\|\mbox{ by the UL
property}$ $\displaystyle\ \leqslant\
2\mathbf{C}_{q}\Delta_{rc}\min_{n\in\Lambda\backslash
I}|e_{n}^{*}(x)|\left\|1_{\Lambda\backslash I}\right\|\mbox{ by reverse
conservativeness}$ $\displaystyle\ \leqslant\
4\mathbf{C}^{2}_{q}\Delta_{rc}\|P_{\Lambda\backslash I}(x)\|\mbox{ by the UL
property}.$ (2.3)

From (2.1), (2.2), and (2), we obtain

$\|x-P_{A}(x)\|\ \leqslant\
(1+\mathbf{C}_{q}+4\mathbf{C}^{3}_{q}\Delta_{rc})\|x-P_{I}(x)\|,$

as desired. ∎

The proof of Theorem 1.2 is the same as the proof of Theorem 1.1 with obvious
modifications. The proof is left for interested readers.

##  3\. Larger greedy sums for RPG bases

Throughout this section, let $\lambda$ be a real number at least $1$. First,
we define the notion of reverse partial symmetry for largest coefficients
(RPSLC). For a finite set $A\subset\mathbb{N}$, let $s(A)=0$ if $A=\emptyset$;
otherwise, $s(A)=\max A-\min A+1$. For a collection of sets $(A_{i})_{i\in
I}$, we write $\sqcup_{i}A_{i}$ to mean $A_{j}\cap A_{k}=\emptyset$ for any
$j,k\in I$. Finally, $\|x\|_{\infty}:=\max_{n}|e_{n}^{*}(x)|$.

######  Definition 3.1.

A vector $x\in\mathbb{X}$ is said to surround a finite set
$A\subset\mathbb{N}$ if either $A=\emptyset$ or
$\operatorname{supp}(x)\cap[\min A,\max A]=\emptyset$.

######  Definition 3.2.

A basis is said to be ($\lambda$, RPSLC) if there exists a constant
$\mathbf{C}\geqslant 1$ such that

$\|x+1_{\varepsilon A}\|\ \leqslant\ \mathbf{C}\|x+1_{\delta B}\|,$

for all $x\in\mathbb{X}$ with $\|x\|_{\infty}\leqslant 1$, for all signs
$\varepsilon,\delta$, and for all finite sets $A,B\subset\mathbb{N}$ such that
$(\lambda-1)s(A)+|A|\leqslant|B|$, $B\sqcup\operatorname{supp}(x)$, $B<A$, and
$x$ surrounds $A$. In this case, the least such $\mathbf{C}$ is denoted by
$\Delta_{\lambda,rpl}$.

######  Remark 3.3.

While the definition of ($\lambda$, RPSLC) seems unnatural and technical, we
shall use it in proving Corollary 3.12 and eventually Theorem 1.4, both of
which are relevant to the literature on greedy-type bases.

We have an easy but useful reformulation of ($\lambda$, RPSLC).

######  Proposition 3.4.

A basis $\mathcal{B}$ is $\Delta_{\lambda,rpl}$-($\lambda$, RPSLC) if and only
if

$\|x\|\ \leqslant\ \Delta_{\lambda,rpl}\|x-P_{A}(x)+1_{\varepsilon B}\|,$
(3.1)

for all $x\in\mathbb{X}$ with $\|x\|_{\infty}\leqslant 1$, for all sign
$\varepsilon$, and for all finite sets $A,B\subset\mathbb{N}$ such that
$(\lambda-1)s(A)+|A|\leqslant|B|$, $B\sqcup\operatorname{supp}(x-P_{A}(x))$,
$B<A$, and $x-P_{A}(x)$ surrounds $A$.

###### Proof.

Assume that $\mathcal{B}$ is $\Delta_{\lambda,rpl}$-($\lambda$, RPSLC). Let
$x,A,B,\varepsilon$ be chosen as in (3.1). We have

$\displaystyle\|x\|\ =\ \left\|x-P_{A}(x)+\sum_{n\in
A}e_{n}^{*}(x)e_{n}\right\|$ $\displaystyle\ \leqslant\
\sup_{\delta}\left\|x-P_{A}(x)+1_{\delta A}\right\|$ $\displaystyle\
\leqslant\ \Delta_{\lambda,rpl}\|x-P_{A}(x)+1_{\varepsilon B}\|.$

Next, assume that $\mathcal{B}$ satisfies (3.1). Let
$x,A,B,\varepsilon,\delta$ be chosen as in Definition 3.2. Let
$y=x+1_{\varepsilon A}$. By (3.1),

$\displaystyle\|x+1_{\varepsilon A}\|\ =\ \|y\|\ \leqslant\
\Delta_{\lambda,rpl}\|y-P_{A}(y)+1_{\delta B}\|\ =\
\Delta_{\lambda,rpl}\|x+1_{\delta B}\|.$

This completes our proof. ∎

The next theorem characterizes ($\lambda$, RPGII) bases.

######  Theorem 3.5.

A basis $\mathcal{B}$ is ($\lambda$, RPGII) if and only it is quasi-greedy and
($\lambda$, RPSLC).

######  Theorem 3.6 (Analog of Theorem 3.1 in [7]).

Let $\mathcal{B}$ be a $\mathbf{C}_{\ell}$-suppression quasi-greedy basis. The
following hold.

  * i)

If $\mathcal{B}$ is $\mathbf{C}_{1,rp}$-($1$, RPGII), then $\mathcal{B}$ is
$\mathbf{C}_{1,rp}$-($1$, RPSLC).

  * ii)

If $\mathcal{B}$ is $\mathbf{C}_{\lambda,rp}$-($\lambda$, RPGII), then
$\mathcal{B}$ is $\mathbf{C}_{\ell}\mathbf{C}_{\lambda,rp}$-($\lambda$,
RPSLC).

  * iii)

If $\mathcal{B}$ is $\Delta_{\lambda,rpl}$-($\lambda$, RPSLC), then
$\mathcal{B}$ is $\mathbf{C}_{\ell}\Delta_{\lambda,rpl}$-($\lambda$, RPGII).

###### Proof.

i) Let $x,A,B,\varepsilon,\delta$ be as in Definition 3.2. We need to show
that

$\|x+1_{\varepsilon A}\|\ \leqslant\ \mathbf{C}_{1,rp}\|x+1_{\delta B}\|.$

If $A=\emptyset$, then

$\|x+1_{\varepsilon A}\|\ =\ \|x\|\ \leqslant\ \mathbf{C}_{\ell}\|x+1_{\delta
B}\|\ \leqslant\ \mathbf{C}_{1,rp}\|x+1_{\delta B}\|,$

where the last inequality is due to the proof of Theorem 1.1. If
$A\neq\emptyset$, form $y=x+1_{\varepsilon A}+1_{\delta B}+1_{D}$, where
$D=[\min A,\max A]\backslash A$. We have

$|D\cup A|\ \leqslant\ |D\cup B|\mbox{ and }D\cup B\leqslant\max(D\cup A).$

Hence, we obtain

$\displaystyle\|x+1_{\varepsilon A}\|\ =\ \|y-P_{B\cup D}(y)\|\ \leqslant\
\mathbf{C}_{1,rp}\widecheck{\sigma}^{B\cup D}_{|B\cup D|}(y)$ $\displaystyle\
\leqslant\ \mathbf{C}_{1,rp}\|y-P_{A\cup D}(y)\|$ $\displaystyle\ =\
\mathbf{C}_{1,rp}\|x+1_{\delta B}\|,$

as desired.

ii) Let $x,A,B,\varepsilon,\delta$ be as in Definition 3.2. If $A=\emptyset$,
then by the proof of item i), we are done. If $A\neq\emptyset$, form
$y=x+1_{\varepsilon A}+1_{\delta B}+1_{D}$, where $D=[\min A,\max A]\backslash
A$. Observe that $B\cup D$ is a greedy set of $y$ and

$|B\cup D|\ =\ |B|+|D|\ \geqslant\ (\lambda-1)s(A)+|A|+(s(A)-|A|)\ =\ \lambda
s(A).$

Choose $\Lambda\subset B\cup D$ such that $|\Lambda|=\lceil\lambda
s(A)\rceil$. Clearly,

$|A\cup D|\ =\ s(A)\mbox{ and }\Lambda\ \leqslant\ \max(A\cup D).$

We obtain

$\displaystyle\|x+1_{\varepsilon A}\|\ =\ \|y-P_{B\cup D}(y)\|\ \leqslant\
\mathbf{C}_{\ell}\|y-P_{\Lambda}(y)\|$ $\displaystyle\ \leqslant\
\mathbf{C}_{\ell}\mathbf{C}_{\lambda,rp}\widecheck{\sigma}^{\Lambda}_{s(A)}(y)$
$\displaystyle\ \leqslant\
\mathbf{C}_{\ell}\mathbf{C}_{\lambda,rp}\|y-P_{A\cup D}(y)\|$ $\displaystyle\
=\ \mathbf{C}_{\ell}\mathbf{C}_{\lambda,rp}\|x+1_{\delta B}\|.$

Therefore, $\mathcal{B}$ is
$\mathbf{C}_{\ell}\mathbf{C}_{\lambda,rp}$-($\lambda$, RPSLC).

iii) Assume that $\mathcal{B}$ is $\mathbf{C}_{\ell}$-suppression quasi-greedy
and $\Delta_{\lambda,rpl}$-($\lambda$, RPSLC). Let $x\in\mathbb{X}$,
$m\in\mathbb{N}$, $\Lambda\in G(x,\lceil\lambda m\rceil)$, and a nonempty
interval $I$ with $|I|\leqslant m$ and $\Lambda\leqslant\max I$. We need to
show that

$\|x-P_{\Lambda}(x)\|\ \leqslant\
\mathbf{C}_{\ell}\Delta_{\lambda,rpl}\|x-P_{I}(x)\|.$

If $\alpha:=\min_{n\in\Lambda}|e_{n}^{*}(x)|$, then
$\|x-P_{\Lambda}(x)\|_{\infty}\leqslant\alpha$. We have

$\displaystyle|\Lambda\backslash I|\ =\ |\Lambda|-|\Lambda\cap I|\ \geqslant\
\lambda m-|\Lambda\cap I|$ $\displaystyle\ =\ \lambda m+(|I|-|\Lambda\cap
I|)-|I|$ $\displaystyle\ \geqslant\ \lambda m+|I\backslash\Lambda|-m$
$\displaystyle\ =\ (\lambda-1)m+|I\backslash\Lambda|$ $\displaystyle\
\geqslant\ (\lambda-1)s(I\backslash\Lambda)+|I\backslash\Lambda|,$

and

$\Lambda\backslash I\ <\ I\backslash\Lambda\mbox{ and }(\Lambda\backslash
I)\sqcup\operatorname{supp}(x-P_{\Lambda}(x)-P_{I\backslash\Lambda}(x)).$

Furthermore, $x-P_{\Lambda}(x)-P_{I\backslash\Lambda}(x)$ surrounds
$I\backslash\Lambda$. Setting $\varepsilon=(\operatorname{sgn}(e_{n}^{*}(x))$,
we can apply Proposition 3.4 to obtain

$\displaystyle\|x-P_{\Lambda}(x)\|$ $\displaystyle\ \leqslant\
\Delta_{\lambda,rpl}\|x-P_{\Lambda}(x)-P_{I\backslash\Lambda}(x)+\alpha
1_{\varepsilon\Lambda\backslash I}\|$ $\displaystyle\ \leqslant\
\Delta_{\lambda,rpl}\|T_{\alpha}(x-P_{\Lambda}(x)-P_{I\backslash\Lambda}(x)+P_{\Lambda\backslash
I}(x))\|$ $\displaystyle\ \leqslant\
\mathbf{C}_{\ell}\Delta_{\lambda,rpl}\|x-P_{I}(x)\|\mbox{ by Theorem
\ref{bto}.}$

We finish the case when $I\neq\emptyset$. If $I=\emptyset$, then we simply
have
$\|x-P_{\Lambda}(x)\|\leqslant\mathbf{C}_{\ell}\|x\|=\mathbf{C}_{\ell}\|x-P_{I}(x)\|$.
∎

###### Proof of Theorem 3.5.

By Theorem 3.6, we need only to show that a ($\lambda$, RPGII) basis is quasi-
greedy. Indeed, a ($\lambda$, RPGII) basis satisfies (1.7), which implies that

$\|x-P_{\Lambda}(x)\|\ \leqslant\ \mathbf{C}\|x\|,\forall
x\in\mathbb{X},\forall m\in\mathbb{N},\forall\Lambda\in G(x,\lceil\lambda
m\rceil).$

By [7, Lemma 2.3], we know that $\mathcal{B}$ is quasi-greedy. ∎

######  Definition 3.7.

A basis is said to be ($\lambda$, reverse conservative of type II)111For the
definition of ($\lambda$, reverse conservative of type I), see [7, Definition
6.2]. if for some constant $\mathbf{C}>0$, we have

$\|1_{A}\|\ \leqslant\ \mathbf{C}\|1_{B}\|,$

for all finite sets $A,B\subset\mathbb{N}$ with
$(\lambda-1)s(A)+|A|\leqslant|B|$ and $B<A$. In this case, the least constant
$\mathbf{C}$ is denoted by $\Delta_{\lambda,rc}$.

######  Proposition 3.8.

Let $\mathcal{B}$ be a quasi-greedy basis. Then $\mathcal{B}$ is ($\lambda$,
reverse conservative of type II) if and only if it is ($\lambda$, RPSLC).

###### Proof.

Setting $x=0$ and $\varepsilon\equiv\delta\equiv 1$ in Definition 3.2, we see
that a ($\lambda$, RPSLC) basis is ($\lambda$, reverse conservative of type
II). Assume that $\mathcal{B}$ is $\Delta_{\lambda,rc}$-($\lambda$, reverse
conservative of type II) and $\mathbf{C}_{\ell}$-suppression quasi-greedy (and
$\mathbf{C}_{q}$-quasi-greedy). Let $x,A,B,\varepsilon,\delta$ be chosen as in
Definition 3.2. We have

$\|1_{\varepsilon A}\|\ \stackrel{{\scriptstyle\mbox{UL}}}{{\leqslant}}\
2\mathbf{C}_{q}\|1_{A}\|\ \leqslant\
2\mathbf{C}_{q}\Delta_{\lambda,rc}\|1_{B}\|\
\stackrel{{\scriptstyle\mbox{UL}}}{{\leqslant}}\
4\mathbf{C}_{q}^{2}\Delta_{\lambda,rc}\|1_{\delta B}\|\ \leqslant\
4\mathbf{C}_{q}^{3}\Delta_{\lambda,rc}\|x+1_{\delta B}\|.$

Furthermore,

$\|x\|\ \leqslant\ \mathbf{C}_{\ell}\|x+1_{\delta B}\|.$

Therefore,

$\|x+1_{\varepsilon A}\|\ \leqslant\ \|x\|+\|1_{\varepsilon A}\|\ \leqslant\
(4\mathbf{C}_{q}^{3}\Delta_{\lambda,rc}+\mathbf{C}_{\ell})\|x+1_{\delta B}\|.$

This completes our proof. ∎

######  Theorem 3.9.

Let $\mathcal{B}$ be a basis. The following are equivalent

  1. i)

$\mathcal{B}$ is ($\lambda$, RPGII).

  2. ii)

$\mathcal{B}$ is quasi-greedy and ($\lambda$, RPSLC).

  3. iii)

$\mathcal{B}$ is quasi-greedy and ($\lambda$, reverse conservative of type
II).

###### Proof.

That i) $\Longleftrightarrow$ ii) is due to Theorem 3.5, and that ii)
$\Longleftrightarrow$ iii) is due to Proposition 3.8. ∎

The problem of characterizing $1$-greedy-type bases has been of great interest
as can be seen in [1, 2, 4, 6, 9]. As a corollary of Theorem 3.6, let us
characterize bases that satisfies (1.6) with constant $\mathbf{C}=1$.

######  Theorem 3.10.

A basis $\mathcal{B}$ satisfies (1.6) with constant $\mathbf{C}=1$ if and only
if $\mathcal{B}$ is $1$-($1$, RPSLC).

###### Proof.

By Theorem 3.6 items i) and iii), it suffices to show that if a basis
$\mathcal{B}$ is $1$-($1$, RPSLC), then it is $1$-suppression quasi-greedy.
This follows immediately from Definition 3.2 by setting $A=\emptyset$ to have

$\|x\|\ \leqslant\ \|x+e_{k}\|,$

for all $x\in\mathbb{X}$ with $\|x\|_{\infty}\leqslant 1$ and for all
$k\notin\operatorname{supp}(x)$. By induction, $\mathcal{B}$ is
$1$-suppression quasi-greedy. ∎

In the spirit of [6, Proposition 4.2], we offer yet another characterization
of $1$-($1$, RPGII) bases.

######  Theorem 3.11.

A basis $\mathcal{B}$ is $1$-($1$, RPGII) if and only if $\mathcal{B}$
satisfies simultaneously two following conditions

  1. i)

for all $x\in\mathbb{X}$ with $\|x\|_{\infty}\leqslant 1$ and for all
$k\notin\operatorname{supp}(x)$, we have

$\|x\|\ \leqslant\ \|x+e_{k}\|.$ (3.2)

  2. ii)

for $x\in\mathbb{X}$ with $\|x\|_{\infty}\leqslant 1$, for $s,t\in\mathbb{K}$
with $|s|=|t|=1$, and for $j<k$, both of which are not in
$\operatorname{supp}(x)$, we have

$\|x+te_{k}\|\ \leqslant\ \|x+se_{j}\|.$ (3.3)

###### Proof.

Due to Theorem 3.10, it suffices to show that a basis is $1$-($1$, RPSLC) if
and only if it satisfies both (3.2) and (3.3). It follows immediately from
Definition 3.2, that a $1$-($1$, RPSLC) basis must satisfy (3.2) and (3.3).
Conversely, suppose that $\mathcal{B}$ satisfies both (3.2) and (3.3). Choose
$x,A,B,\varepsilon,\delta$ as in Definition 3.2. We show that

$\|x+1_{\varepsilon A}\|\ \leqslant\ \|x+1_{\delta B}\|$ (3.4)

inductively on $|B|$.

Base case: $|B|=1$. If $A=\emptyset$, then (3.2) implies (3.4); if $|A|=1$,
then (3.3) implies (3.4).

Inductive hypothesis (I.H.): assume that for some $\ell\in\mathbb{N}$, (3.4)
holds for $|B|\leqslant\ell$. We show that (3.4) holds for $|B|=\ell+1$. If
$A=\emptyset$, then we use (3.2) inductively to obtain (3.4). For
$|A|\geqslant 1$, let $p=\max A$, $q\in B$, $A^{\prime}=A\backslash\\{p\\}$,
and $B^{\prime}=B\backslash\\{q\\}$. We have

$\displaystyle\|x+1_{\varepsilon A}\|\ =\
\|(x+\varepsilon_{p}e_{p})+1_{\varepsilon A^{\prime}}\|$ $\displaystyle\
\leqslant\ \|(x+\varepsilon_{p}e_{p})+1_{\delta B^{\prime}}\|\mbox{ by I.H.}$
$\displaystyle\ \leqslant\ \|(x+\delta_{q}e_{q})+1_{\delta B^{\prime}}\|\mbox{
by \eqref{e16}}$ $\displaystyle\ =\ \|x+1_{\delta B}\|.$

This shows that $\mathcal{B}$ is $1$-($1$, RPSLC). ∎

######  Corollary 3.12.

The following are equivalent

  1. i)

$(e_{n})_{n}$ is $1$-($1$, RPGII).

  2. ii)

$(e_{n})_{n}$ is $1$-($1$, RPSLC).

  3. iii)

$(e_{n})_{n}$ satisfies (3.2) and (3.3).

  4. iv)

$(e_{n})_{n}$ satisfies (1.5) with constant $1$.

###### Proof.

The equivalence between i), ii), and iii) is due to Theorems 3.10 and 3.11.
That iii) $\Longleftrightarrow$ iv) is due to [9, Theorem 3.4]. ∎

##  4\. ($\lambda$, RPGII) bases are weaker than RPG bases

The goal of this section is to prove the following Theorem 1.4.

###### Proof.

i) If $\mathcal{B}$ is RPG, then it is quasi-greedy and reverse conservative.
By definition, a reverse conservative basis is ($\lambda$, reverse
conservative of type II). By Theorem 3.9, $\mathcal{B}$ is ($\lambda$, RPGII).

ii) For each $\lambda>1$, we now construct an unconditional basis
$\mathcal{B}$ that is ($\lambda$, RPGII) but is not RPG. Let
$D=\\{2^{n}\,:\,n\in\mathbb{N}_{0}\\},u_{n}=\frac{1}{\sqrt{n}},v_{n}=\frac{1}{n}$
for all $n\geqslant 1$. Let $\mathbb{X}$ be the completion of $c_{00}$ with
respect to the following norm: for $x=(x_{1},x_{2},\ldots)$, define

$\|x\|\ =\ \sup_{\pi,\pi^{\prime}}\left(\sum_{n\in
D}u_{\pi(n)}|x_{n}|+\sum_{n\notin D}v_{\pi^{\prime}(n)}|x_{n}|\right),$

where $\pi:D\rightarrow\mathbb{N}$ and $\pi^{\prime}:\mathbb{N}\backslash
D\rightarrow\mathbb{N}$ are bijections. Clearly, the canonical basis
$\mathcal{B}$ is an $1$-unconditional normalized basis of $\mathbb{X}$.

######  Claim 4.1.

The basis $\mathcal{B}$ is not reverse conservative and thus, is not RPG.

###### Proof.

We use the notation $\sim$ to indicate the order of a number. For each
$N\in\mathbb{N}$, let $A_{N}=\\{2^{2N+1},2^{2N+2},\ldots,2^{3N}\\}$ and
$B_{N}=\\{3,3^{2},\ldots,3^{N}\\}$. Then $|A_{N}|=|B_{N}|=N$ and
$B_{N}<A_{N}$. However,

$\|1_{A_{N}}\|\ =\ \sum_{n=1}^{N}\frac{1}{\sqrt{n}}\ \sim\ \sqrt{N}\mbox{ and
}\|1_{B_{N}}\|\ =\ \sum_{n=1}^{N}\frac{1}{n}\ \sim\ \ln N,$

which imply that $\|1_{A_{N}}\|/\|1_{B_{N}}\|\rightarrow\infty$ as
$N\rightarrow\infty$. Therefore, $\mathcal{B}$ is not reverse conservative. ∎

######  Claim 4.2.

The basis $\mathcal{B}$ is ($\lambda$, reverse conservative of type II) and
thus, is ($\lambda$, RPGII).

###### Proof.

Pick nonempty, finite sets $A,B\subset\mathbb{N}$ with
$(\lambda-1)s(A)+|A|\leqslant|B|$ and $B<A$. Then

$\|1_{A}\|\ =\ \sum_{n=1}^{|A\cap
D|}\frac{1}{\sqrt{n}}+\sum_{n=1}^{|A\backslash D|}\frac{1}{n}\mbox{ and
}\|1_{B}\|\ =\ \sum_{n=1}^{|B\cap
D|}\frac{1}{\sqrt{n}}+\sum_{n=1}^{|B\backslash D|}\frac{1}{n}.$

We proceed by case analysis.

Case 1: $\sum_{n=1}^{|A\cap D|}\frac{1}{\sqrt{n}}\ \leqslant\
\sum_{n=1}^{|A\backslash D|}\frac{1}{n}$. We get

$\|1_{A}\|\ \leqslant\ 2\sum_{n=1}^{|A\backslash D|}\frac{1}{n}\ \leqslant\
2\sum_{n=1}^{|B|}\frac{1}{n}\ \leqslant\ 2\left(\sum_{n=1}^{|B\cap
D|}\frac{1}{\sqrt{n}}+\sum_{n=1}^{|B\backslash D|}\frac{1}{n}\right)\ =\
2\|1_{B}\|.$

Case 2: $\sum_{n=1}^{|A\cap D|}\frac{1}{\sqrt{n}}\ >\ \sum_{n=1}^{|A\backslash
D|}\frac{1}{n}$. Then $\|1_{A}\|\sim\sqrt{|A\cap D|}$. If $|B\cap
D|\geqslant|A\cap D|$, then we are done because

$\|1_{B}\|\ \geqslant\ \sum_{n=1}^{|B\cap D|}\frac{1}{\sqrt{n}}\ \sim\
\sqrt{|B\cap D|}\ \geqslant\ \sqrt{|A\cap D|}\ \sim\ \|1_{A}\|.$

Suppose that $|B\cap D|<|A\cap D|$. Let $N=|A\cap D|$ and write $A\cap
D=\\{2^{k_{1}},2^{k_{2}},\ldots,2^{k_{N}}\\}$ to obtain
$\|1_{A}\|\sim\sqrt{N}$.

  1. i)

Case 2.1: $N=1$. Then $\sum_{n=1}^{|A\cap D|}\frac{1}{\sqrt{n}}\ >\
\sum_{n=1}^{|A\backslash D|}\frac{1}{n}$ implies that $|A\backslash D|=0$ and
$|A|=1$. Clearly, $\|1_{A}\|\leqslant\|1_{B}\|$.

  2. ii)

Case 2.2: $N\geqslant 2$. We have

$|B|\ \geqslant\ (\lambda-1)s(A)\ \geqslant\
(\lambda-1)(2^{k_{N}}-2^{k_{1}}+1)\ \geqslant\ (\lambda-1)2^{k_{N}-1}.$

Hence,

$\ln|B|\ \geqslant\ \ln(\lambda-1)+(N-1)\ln 2.$

If $\ln(\lambda-1)+0.5(N-1)\geqslant 0$, then

$\|1_{B}\|\ \gtrsim\ \ln|B|\ \geqslant\ (\ln 2-0.5)(N-1)\ \gtrsim\ \sqrt{N}\
\sim\ \|1_{A}\|.$

If $\ln(\lambda-1)+0.5(N-1)<0$, then $N<1-2\ln(\lambda-1)$. In this case,

$\|1_{A}\|\ \sim\ \sqrt{N}\ <\ \sqrt{1-2\ln(\lambda-1)}\ \leqslant\
\sqrt{1-2\ln(\lambda-1)}\|1_{B}\|.$

We have shown that in all cases, there exists a constant
$\mathbf{C}=\mathbf{C}(\lambda)$ such that
$\|1_{A}\|\leqslant\mathbf{C}\|1_{B}\|$. Therefore, $\mathcal{B}$ is
($\lambda$, reverse consecutive of type II). ∎

We conclude that our basis $\mathcal{B}$ is $1$-unconditional and ($\lambda$,
RPGII) but is not RPG. ∎

## References

  * [1] F. Albiac and J. L. Ansorena, Characterization of $1$-quasi-greedy bases, J. Approx. Theory 201 (2016), 7–12.
  * [2] F. Albiac and J. L. Ansorena, Characterization of $1$-almost greedy bases, Rev. Mat. Complut. 30 (2017), 13–24.
  * [3] F. Albiac and N. Kalton, Topics in Banach Space Theory, second edition, ISBN 978-3-319-31555-3 (2016).
  * [4] F. Albiac and P. Wojtaszczyk, Characterization of $1$-greedy bases, J. Approx. Theory 138 (2006), 65–86.
  * [5] P. M. Berná, O. Blasco, and G. Garrigós, Lebesgue inequalities for greedy algorithm in general bases, Rev. Mat. Complut. 30 (2017), 369–392.
  * [6] M. Berasategui, P. M. Berná, and S. Lassalle, Strong partially greedy bases and Lebesgue-type inequalities, Constr. Approx. 54 (2021), 507–528.
  * [7] H. V. Chu, Performance of the thresholding greedy algorithm with larger greedy sums, preprint (2022). Available at: https://arxiv.org/abs/2205.00268.
  * [8] S. J. Dilworth, N. J. Kalton, D. Kutzarova, and V. N. Temlyakov, The thresholding greedy algorithm, greedy bases, and duality, Constr. Approx. 19 (2003), 575–597.
  * [9] S. J. Dilworth and D. Khurana, Characterizations of almost greedy and partially greedy bases, Jaen J. Approx. 11 (2019), 115–137.
  * [10] D. Khurana, Weight-partially greedy bases and weight-property (A), Ann. Funct. Anal. 11 (2020), 101–117.
  * [11] S. V. Konyagin and V. N. Temlyakov, A remark on greedy approximation in Banach spaces, East J. Approx. 5 (1999), 365–379.


* Ma, S., Deng, Z.-H., and Yang, Y. (2016).  An unsupervised multi-document summarization framework based on neural document model.  In Proceedings of COLING 2016, the 26th International Conference on Computational Linguistics: Technical Papers, pp. 1514–1523.
  * Mani, K., Verma, I., Meisheri, H., and Dey, L. (2018).  Multi-document summarization using distributed bag-of-words model.  In 2018 IEEE/WIC/ACM International Conference on Web Intelligence (WI), pp. 672–675. IEEE.
  * Marcos, Diego, V. (2016).  Learning rotation invariant convolutional filters for texture classification.  In 2016 23rd International Conference on Pattern Recognition, pp. 2012–2017. IEEE.
  * Meister, C., Vieira, T., and Cotterell, R. (2020).  If beam search is the answer, what was the question?.  Preprint arXiv:2010.02650, ArXiv.
  * Mena, G., Belanger, D., Linderman, S., and Snoek, J. (2018).  Learning latent permutations with gumbel-sinkhorn networks.  In International Conference on Learning Representations 2018.
  * Meng, C., Yang, J., Ribeiro, B., and Neville, J. (2019).  HATS: A hierarchical sequence-attention framework for inductive set-of-sets embeddings.  In Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2019, pp. 783–792.
  * Merity, S., Xiong, C., Bradbury, J., and Socher, R. (2016).  Pointer sentinel mixture models.  In 5th International Conference on Learning Representations, ICLR 2017 - Conference Track Proceedings.
  * Mitra, B., Craswell, N., et al. (2018).  An introduction to neural information retrieval.  Foundations and Trends® in Information Retrieval, 13(1), 1–126.
  * Moore, J., and Neville, J. (2017).  Deep collective inference.  In AAAI.
  * Murphy, R. L., Srinivasan, B., Ribeiro, B., and Rao, V. (2019).  Janossy pooling: Learning deep permutation-invariant functions for variable-size inputs.  In 7th International Conference on Learning Representations, ICLR 2019, pp. 1–21.
  * Nazari, M., Oroojlooy, A., Takáč, M., and Snyder, L. V. (2018).  Reinforcement learning for solving the vehicle routing problem.  Advances in Neural Information Processing Systems, 2018-December, 9839–9849.
  * Niepert, M., Ahmed, M., and Kutzkov, K. (2016).  Learning convolutional neural networks for graphs.  In International conference on machine learning, pp. 2014–2023.
  * Nishida, N., and Nakayama, H. (2017).  Word ordering as unsupervised learning towards syntactically plausible word representations.  In Proceedings of the 8th International Joint Conference on Natural Language Processing (IJCNLP 2017), pp. 70–79.
  * Noreen, N., Palaniappan, S., Qayyum, A., Ahmad, I., Imran, M., and Shoaib, M. (2020).  A deep learning model based on concatenation approach for the diagnosis of brain tumor.  IEEE Access, 8, 55135–55144.
  * Ntampaka, M., Trac, H., Sutherland, D., Fromenteau, S., Poczos, B., and Schneider, J. (2016).  Dynamical mass measurements of contaminated galaxy clusters using machine learning.  The Astrophysical Journal, 831.
  * Oladosu, A., Xu, T., Ekfeldt, P., Kelly, B. A., Cranmer, M., Ho, S., Price-Whelan, A. M., and Contardo, G. (2020).  Meta-learning one-class classification with deepsets: Application in the milky way.  Preprint arXiv:2007.04459, ArXiv.
  * Oliveira, H., Silva, C., Machado, G. L., Nogueira, K., and Santos, J. A. d. (2020).  Fully convolutional open set segmentation.  Preprint arXiv:2006.14673, ArXiv.
  * Pang, L., Xu, J., Ai, Q., Lan, Y., Cheng, X., and Wen, J. (2020).  Setrank: Learning a permutation-invariant ranking model for information retrieval.  In Proceedings of the 43rd International ACM SIGIR Conference on Research and Development in Information Retrieval, pp. 499–508.
  * Pfannschmidt, K., Gupta, P., and Hüllermeier, E. (2018).  Deep architectures for learning context-dependent ranking functions.  ArXiv, abs/1803.05796.
  * Pihera, J., and Musliu, N. (2014).  Application of machine learning to algorithm selection for tsp.  In 2014 IEEE 26th International Conference on Tools with Artificial Intelligence, pp. 47–54. IEEE.
  * Puduppully, R., Dong, L., and Lapata, M. (2019).  Data-to-Text Generation with Content Selection and Planning.  Proceedings of the AAAI Conference on Artificial Intelligence, 33, 6908–6915.
  * Qi, C. R., Su, H., Mo, K., and Guibas, L. J. (2017).  PointNet: Deep learning on point sets for 3D classification and segmentation.  In Proceedings - 30th IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2017, pp. 77–85.
  * Rang, B., and Thomas, W. (1981).  Zermelo’s discovery of the “russell paradox”.  Historia Mathematica, 8(1), 15–22.
  * Rocktäschel, T., Grefenstette, E., Hermann, K., Kociský, T., and Blunsom, P. (2016).  Reasoning about entailment with neural attention.  CoRR, abs/1509.06664.
  * Rolínek, M., Musil, V., Paulus, A., Vlastelica, M., Michaelis, C., and Martius, G. (2020).  Optimizing rank-based metrics with blackbox differentiation.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 7620–7630.
  * Saito, Y., Nakamura, T., Hachiya, H., and Fukumizu, K. (2019).  Deep set-to-set matching and learning.  ArXiv, abs/1910.09972.
  * Sarwar, B., Karypis, G., Konstan, J., and Riedl, J. (2001).  Item-based collaborative filtering recommendation algorithms.  In Proceedings of the 10th International Conference on World Wide Web, WWW ’01, p. 285–295, New York, NY, USA. Association for Computing Machinery.
  * Schafer (2007).  Recurrent neural networks are universal approximators.  International Journal of Neural Systems, Vol. 17, No. 4 (2007) 253–263, World Scientific Publishing Company Int., 17(4), 253–263.
  * See, A., Liu, P., and Manning, C. (2017).  Get to the point: Summarization with pointer-generator networks.  In Association for Computational Linguistics.
  * Serviansky, H., Segol, N., Shlomi, J., Cranmer, K., Gross, E., Maron, H., and Lipman, Y. (2020).  Set2graph: Learning graphs from sets.  Preprint arXiv:2002.08772, ArXiv.
  * Skianis, K., Nikolentzos, G., Limnios, S., and Vazirgiannis, M. (2020).  Rep the Set: Neural Networks for Learning Set Representations.  AISTATS, 1(23rd).
  * Smith, K. A. (1999).  Neural networks for combinatorial optimization: A review of more than a decade of research.  INFORMS Journal on Computing, 11(1), 15–34.
  * Spearman, C. (1904).  The proof and measurement of association between two things..  In American Journal of Psychology.
  * Stuart, J. L., and Weaver, J. R. (1991).  Matrices that commute with a permutation matrix.  Linear Algebra and its Applications, 150, 255 – 265.
  * Sun, Z., Tang, J., Du, P., Deng, Z. H., and Nie, J. Y. (2019).  DivGraphPointer: A graph pointer network for extracting diverse keyphrases.  In SIGIR 2019 - Proceedings of the 42nd International ACM SIGIR Conference on Research and Development in Information Retrieval, pp. 755–764.
  * Sunehag, P., Lever, G., Gruslys, A., Czarnecki, W. M., Zambaldi, V., Jaderberg, M., Lanctot, M., Sonnerat, N., Leibo, J. Z., Tuyls, K., and Graepel, T. (2018).  Value-decomposition networks for cooperative multi-agent learning based on team reward.  Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS, 3, 2085–2087.
  * Sutskever, I., Vinyals, O., and Le, Q. V. (2014).  Sequence to sequence learning with neural networks.  Advances in Neural Information Processing Systems, 4(January), 3104–3112.
  * Szegedy, C., Vanhoucke, V., Ioffe, S., Shlens, J., and Wojna, Z. (2016).  Rethinking the inception architecture for computer vision.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 2818–2826.
  * Takeuti, G., and Zaring, W. M. (2013).  Axiomatic set theory, Vol. 8.  Springer Science & Business Media.
  * Taylor, L., and Nitschke, G. (2018).  Improving deep learning with generic data augmentation.  In 2018 IEEE Symposium Series on Computational Intelligence (SSCI), pp. 1542–1547.
  * Vartak, M., and Thiagarajan, A. (2017).  A Meta-Learning Perspective on Cold-Start Recommendations for Items Manasi.  31st Conference on Neural Information Processing Systems (NIPS 2017), 29(3), 171–180.
  * Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A. N., Kaiser, Ł., and Polosukhin, I. (2017).  Attention is all you need.  Advances in Neural Information Processing Systems, 2017-Decem(Nips), 5999–6009.
  * Veličković, P., Cucurull, G., Casanova, A., Romero, A., Liò, P., and Bengio, Y. (2018).  Graph Attention Networks.  In International Conference on Learning Representations (2018).  Accepted as poster.
  * Vinyals, O., Babuschkin, I., Czarnecki, W. M., and Mathieu (2019).  Grandmaster level in StarCraft II using multi-agent reinforcement learning.  Nature, 575(7782), 350–354.
  * Vinyals, O., Bengio, S., and Kudlur, M. (2016).  Order matters: Sequence to sequence for sets.  In 4th International Conference on Learning Representations, ICLR 2016 - Conference Track Proceedings, pp. 1–11.
  * Vinyals, O., Fortunato, M., and Jaitly, N. (2015).  Pointer networks.  In Advances in Neural Information Processing Systems, Vol. 2015-January, pp. 2692–2700.
  * Volkovs, M. N., and Zemel, R. S. (2009).  Boltzrank: learning to maximize expected ranking gain.  In Proceedings of the 26th Annual International Conference on Machine Learning, pp. 1089–1096.
  * Wagstaff, E., Fuchs, F. B., Engelcke, M., Posner, I., and Osborne, M. (2019).  On the limitations of representing functions on sets.  36th International Conference on Machine Learning, ICML 2019, 2019-June, 11285–11298.
  * Wang, J., Song, Y., Leung, T., Rosenberg, C., Wang, J., Philbin, J., Chen, B., and Wu, Y. (2014).  Learning fine-grained image similarity with deep ranking.  In Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition, pp. 1386–1393.
  * Wang, T., and Wan, X. (2019).  Hierarchical Attention Networks for Sentence Ordering.  Proceedings of the AAAI Conference on Artificial Intelligence, 33, 7184–7191.
  * Weston, J., Chopra, S., and Bordes, A. (2015).  Memory Networks.  In International Conference on Learning Represen- tations, ICLR, 2015, pp. 1–15.
  * Williams, R. J. (1992).  Simple statistical gradient-following algorithms for connectionist reinforcement learning.  Machine learning, 8(3-4), 229–256.
  * Wiseman, S., and Rush, A. M. (2016).  Sequence-to-sequence learning as beam-search optimization.  In Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing, pp. 1296–1306, Austin, Texas. Association for Computational Linguistics.
  * Wolf, T., Sanh, V., Chaumond, J., and Delangue, C. (2019).  TransferTransfo: A Transfer Learning Approach for Neural Network Based Conversational Agents.  Association for the Advancement of Artificial Intelligence, 1(ii).
  * Wu, Y., Riedel, S., Minervini, P., and Stenetorp, P. (2020).  Don’t read too much into it: Adaptive computation for open-domain question answering.  Preprint arXiv:2011.05435, ArXiv.
  * Wu, Z., Song, S., Khosla, A., Yu, F., Zhang, L., Tang, X., and Xiao, J. (2015).  3d shapenets: A deep representation for volumetric shapes.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 1912–1920.
  * Xia, F., Liu, T.-Y., Wang, J., Zhang, W., and Li, H. (2008).  Listwise approach to learning to rank: theory and algorithm.  In Proceedings of the 25th international conference on Machine learning, pp. 1192–1199.
  * Xu, K., Ba, J., Kiros, R., Cho, K., Courville, A., Salakhudinov, R., Zemel, R., and Bengio, Y. (2015).  Show, attend and tell: Neural image caption generation with visual attention.  In International conference on machine learning, pp. 2048–2057.
  * Xu, K., Jegelka, S., Hu, W., and Leskovec, J. (2019).  How powerful are graph neural networks?.  In 7th International Conference on Learning Representations, ICLR 2019, pp. 1–17.
  * Xu, Z., Zhu, L., and Yang, Y. (2017).  Few-shot object recognition from machine-labeled web images.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 1164–1172.
  * Yang, B., Wang, S., Markham, A., and Trigoni, N. (2020).  Robust attentional aggregation of deep feature sets for multi-view 3d reconstruction.  International Journal of Computer Vision, 128(1), 53–73.
  * Ying, Z., You, J., Morris, C., Ren, X., Hamilton, W., and Leskovec, J. (2018).  Hierarchical graph representation learning with differentiable pooling.  In Advances in neural information processing systems, pp. 4800–4810.
  * Yu, T., Meng, J., and Yuan, J. (2018).  Multi-view harmonized bilinear network for 3d object recognition.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 186–194.
  * Zaheer, M., Kottur, S., Ravanbhakhsh, S., Póczos, B., Salakhutdinov, R., and Smola, A. J. (2017).  Deep sets.  Advances in Neural Information Processing Systems, 2017-December(ii), 3392–3402.
  * Zhang, M., Cui, Z., Neumann, M., and Chen, Y. (2018).  An end-to-end deep learning architecture for graph classification.  In AAAI.
  * Zhang, Y., Hare, J., and Prügel-Bennett, A. (2019).  Deep Set Prediction Networks.  In NeurIPS 2019.
  * Zhang, Y., Hare, J., and Prügel-Bennett, A. (2020).  FSPool: Learning Set Representations with Featurewise Sort Pooling.  In ICLR 2020.
  * Zhang, Y., Prügel-Bennett, A., and Hare, J. (2019).  Learning representations of sets through optimized permutations.  In 7th International Conference on Learning Representations, ICLR 2019.
  * Zhao, Z.-Q., tao Xu, S., Liu, D., Tian, W., and Jiang, Z.-D. (2019a).  A review of image set classification.  Neurocomputing, 335, 251–260.
  * Zhao, Z. Q., Zheng, P., Xu, S. T., and Wu, X. (2019b).  Object Detection with Deep Learning: A Review..
  * Zheng, L., Shen, L., Tian, L., Wang, S., Wang, J., and Tian, Q. (2015).  Scalable person re-identification : A benchmark university of texas at san antonio.  In ICCV 2015, pp. 1116–1124.
  * Zhong, V., Xiong, C., and Socher, R. (2018).  Seq2sql: Generating structured queries from natural language using reinforcement learning.  In 6th International Conference on Learning Representations, ICLR 2018 - Conference Track Proceedings.