#  Curse of “Low” Dimensionality in Recommender Systems

Naoto Ohsaka  CyberAgent, Inc.TokyoJapan<EMAIL_ADDRESS>0000-0001-9584-4764 and  Riku Togashi  CyberAgent, Inc.TokyoJapan
<EMAIL_ADDRESS>0000-0001-9026-0495

(2023)

###### Abstract.

Beyond accuracy, there are a variety of aspects to the quality of recommender
systems, such as diversity, fairness, and robustness. We argue that many of
the prevalent problems in recommender systems are partly due to _low-
dimensionality_ of user and item embeddings, particularly when dot-product
models, such as matrix factorization, are used.

In this study, we showcase empirical evidence suggesting the necessity of
sufficient dimensionality for user/item embeddings to achieve diverse, fair,
and robust recommendation. We then present theoretical analyses of the
expressive power of dot-product models. Our theoretical results demonstrate
that the number of possible rankings expressible under dot-product models is
exponentially bounded by the dimension of item factors. We empirically found
that the low-dimensionality contributes to a popularity bias, widening the gap
between the rank positions of popular and long-tail items; we also give a
theoretical justification for this phenomenon.

recommender systems; dot-product models; fairness; diversity;

††journalyear: 2023††copyright: rightsretained††conference: Proceedings of the
46th International ACM SIGIR Conference on Research and Development in
Information Retrieval; July 23–27, 2023; Taipei, Taiwan††booktitle:
Proceedings of the 46th International ACM SIGIR Conference on Research and
Development in Information Retrieval (SIGIR ’23), July 23–27, 2023, Taipei,
Taiwan††doi: 10.1145/3539618.3591659††isbn: 978-1-4503-9408-6/23/07††ccs:
Information systems Collaborative filtering

##  1\. Introduction

Matrix factorization (MF) (Hu et al., 2008) is a standard tool in recommender
systems. MF can learn compact, retrieval-efficient representation and thus is
easy-to-use, particularly in large-scale applications. On the other hand, due
to the advancement of deep learning-based methods, complex nonlinear models
have also been adopted to enhance recommendation quality (Steck et al., 2021).
However, despite the advances in model architecture, most models share a
common structure, i.e., _dot-product models_ (Rendle et al., 2020). Dot-
product models are a class of models that estimate the preference for a user-
item pair by computing a dot-product (inner product) between the user and item
embeddings; MF is the simplest model in this class. This structure is
essential for large-scale applications due to its computationally efficient
retrieval through vector search algorithms (Jegou et al., 2010; Shrivastava
and Li, 2014; Malkov and Yashunin, 2018).

The _dimensionality_ of user/item embeddings characterizes dot-product models.
One interpretation of dimensionality is that it refers to the ranks of
user/item embedding matrices that minimize the errors between true and
estimated preferences. In the extreme case where the dimensionality is one,
the embedding of each user and item degenerates into a scalar. Notice here
that the rankings estimated from a feedback matrix also degenerate into two
unique rankings, namely, the popularity ranking and its reverse; for ranking
prediction, a one-dimensional user embedding determines only the signatures of
preference scores. Generalizing this, we arrive at a curious question: When
the dimensionality in a dot-product model is low or high, what do the rankings
look like?

Previous studies (Zhou et al., 2008; Pilászy et al., 2010; Koren et al., 2022)
have reported the effectiveness of large dimensionalities in rating prediction
tasks. Rendle et al. (2022) also recently showed that high-dimensional models
can achieve very high ranking accuracy under appropriate regularization.
Furthermore, successful models in top-$K$ item recommendation, such as
variational autoencoder (VAE)-based models (Liang et al., 2018), often use
large dimensions. These observations are somewhat counterintuitive since user
feedback data are typically sparse and thus may lead to overfitting under
large dimensionality. On the other hand, conventional studies of state-of-the-
art methods often omit the investigation of dimensionality in models (e.g.,
(Liang et al., 2018; Sachdeva et al., 2019; He et al., 2020; Shenbin et al.,
2020; Xie et al., 2021)). Although exhaustive tuning of hyperparameters for
model sizes (e.g., the number of hidden layers and the size of each layer) is
unrealistic due to the experimental burden, the dimensionality of user and
item embeddings is rather unnoticed compared with other hyperparameters, such
as learning rates and regularization weights. This further stimulates our
interest above.

In this study, we investigate the effect of dimensionality in recommender
systems based on dot-product models. We first present empirical observations
from various viewpoints on recommendation quality, i.e., personalization,
diversity, fairness, and robustness. Our results reveal a hidden side effect
of low-dimensionality: low-dimensional models incur a low model capacity with
respect to these quality requirements even when the ranking quality seems to
be maintained. In the convention of machine learning, we can often avoid model
overfitting by using low-dimensional models. However, such models would suffer
from potential long-term negative effects, namely, overfitting toward
popularity bias. Consequently, low-dimensionality leads to nondiverse, unfair
recommendation results and thus insufficient data collection for producing
models that can properly delineate users’ individual tastes. Furthermore, we
theoretically explain the cause of the observed phenomenon, _curse of low
dimensionality_. Our theoretical results—which apply to dot-product
models—provide evidence that increasing dimensionality exponentially improves
the expressive power of dot-product models in terms of the number of
expressible rankings, and that we may not completely circumvent popularity
bias. Finally, we discuss possible research directions based on the lessons
learned.

Figure 1. Effect of the dimensionality of iALS on popularity bias in
recommendation results.

##  2\. Preliminary: Dot-Product Models

In this section, we briefly describe dot-product models. Many practical models
are classified as dot-product models (Rendle et al., 2020) (also known as two-
tower models (Yang et al., 2020)), which estimate the preference
$r_{u,v}\in\mathbb{R}$ of a user $u\in\mathcal{U}$ for an item
$v\in\mathcal{V}$ by an inner-product between the embeddings of $u$ and $v$ as
follows:

$\displaystyle\hat{r}_{u,v}=\langle\phi(u),\psi(v)\rangle,$

where $\phi(u)\in\mathbb{R}^{d}$ and $\psi(v)\in\mathbb{R}^{d}$ are the
embeddings of $u$ and $v$, respectively. The design of the feature mappings
$\phi\colon\mathcal{U}\to\mathbb{R}^{d}$ and
$\psi\colon\mathcal{V}\to\mathbb{R}^{d}$ depends on the overall model
architecture; $\phi$ and $\psi$ can be arbitrary models, such as MF and neural
networks.

(V)AEs can also be interpreted as dot-product models (Liang et al., 2018;
Shenbin et al., 2020). Most AE-based models take partial user feedback
($|\mathcal{V}|$-dimensional multi-hot vector) corresponding to one user as
input and have a fully-connected layer to make a final score prediction for
$|\mathcal{V}|$ items. Denoting the $d$-dimensional intermediate
representation of a partial user feedback simply by
$\mathbf{q}\in\mathbb{R}^{d}$, the $|\mathcal{V}|$-dimensional structured
prediction $\mathbf{z}\in\mathbb{R}^{|\mathcal{V}|}$ can be expressed as
follows:

$\displaystyle\mathbf{z}=\mathbf{f}(\mathbf{W}\mathbf{q}+\mathbf{b}),$

where $\mathbf{W}\in\mathbb{R}^{|\mathcal{V}|\times d}$ and
$\mathbf{b}\in\mathbb{R}^{|\mathcal{V}|}$ are the weight matrix and the bias
in the fully-connected layer, respectively. Here,
$\mathbf{f}\colon\mathbb{R}^{|\mathcal{V}|}\to\mathbb{R}^{|\mathcal{V}|}$ is
the activation function (e.g., softmax) that is order-preserving111Formally,
we can say $\mathbf{f}$ is order-preserving if $\mathbf{f}$ satisfies, for any
$\mathbf{x}\in\mathbb{R}^{|\mathcal{V}|}$ and $\forall i,j\in\mathcal{V}$ such
that $i\neq j$, it holds that
$\mathbf{x}_{i}>\mathbf{x}_{j}\Longrightarrow\mathbf{f}(\mathbf{x})_{i}>\mathbf{f}(\mathbf{x})_{j}$..
Given an auxiliary vector $\phi(u)=[\mathbf{q};1]\in\mathbb{R}^{d+1}$ with an
additional dimension of $1$ and an auxiliary matrix
$\mathbf{W}^{\prime}=[\mathbf{W}\,\,\mathbf{b}]\in\mathbb{R}^{|\mathcal{V}|\times(d+1)}$
with an additional column of $\mathbf{b}$, the predicted ranking is derived by
the order of $\mathbf{W}^{\prime}\phi(u)\in\mathbb{R}^{|\mathcal{V}|}$ because
$\mathbf{f}$ is order-preserving and does not affect the ranking prediction.
Therefore, each row of $\mathbf{W}^{\prime}$ can be viewed as the
corresponding item embedding $\psi(v)$, and thus the prediction for $u$ is
also derived from the order of the dot products
$\\{\langle\phi(u),\psi(v)\rangle\mid v\in\mathcal{V}\\}$. This point is often
unregarded in empirical evaluation; for example, Liang et al. (2018) used a
large dimensionality of $600$ for VAE-based models for the Million Song
Dataset and Netflix Prize; by comparison, the MF-based baseline (Hu et al.,
2008) employed a dimensionality of only $200$.

##  3\. Empirical Observation

We first present empirical observations that establish the motivation behind
our theoretical analysis and discuss the possible effects of dimensionality on
recommendation quality in terms of various aspects, such as personalization,
diversity, item fairness, and robustness to biased feedback.

###  3.1. Experimental Setting

For our experiments, we use implicit alternating least squares (iALS) (Hu et
al., 2008; Koren et al., 2009; Rendle et al., 2022), which is widely used in
practical applications and implemented in distributed frameworks, such as
Apache Spark (Meng et al., 2016). Because iALS slows down in high-dimensional
settings222This point is discussed in Section 5, we use a recently developed
block coordinate descent solver (Rendle et al., 2021).

We conduct experiments on three real-world datasets from various applications,
i.e., MovieLens 20M (ML-20M) (Harper and Konstan, 2015), Million Song Dataset
(MSD) (Bertin-Mahieux et al., 2011), and Epinions (Massa and Avesani, 2007).
To create implicit feedback datasets, we binarize explicit data by keeping
observed user-item pairs with ratings larger than four for ML-20M and
Epinions. We utilize all user-item pairs for MSD. For Epinions, we keep the
users and items with more than 20 interactions as in conventional studies
(Abdollahpouri et al., 2017, 2019). We also strictly follow the evaluation
protocol of Liang et al. (2018) based on a strong generalization setting.

Figure 3. Effect of the dimensionality of iALS on catalog coverage and item
fairness on ML-20M. Each line indicates the Pareto frontier of R@$K$ vs.
Cov@$K$ (top row) or R@$K$ vs. Negative Gini@$K$ (bottom row) of models with
fixed dimensionality.

###  3.2. Personalization and Popularity Bias

Personalization is the primary aim of a recommendation system, which requires
a system to adapt its predictions for the users considering their individual
tastes. By contrast, the most-popular recommender is known to be an
empirically strong yet _anti-personalized_ baseline; that is, it recommends an
identical ranking of items for all users (Ferrari Dacrema et al., 2019).
Therefore, the degree of personalization in the predicted rankings may be
considered as that of popularity bias (Celma and Cano, 2008; Yin et al., 2012;
Abdollahpouri et al., 2017, 2019).

Figure 1 shows the personalization measure (i.e., Recall@$K$) and the average
recommendation popularity (ARP@$K$) (Yin et al., 2012) for iALS models with
various embedding sizes. Here, ARP@$K$ is the average of item popularity
(i.e., empirical frequency in the training split) for a top-$K$ list. We tune
$d\in\\{64,128,\dots,4{,}096\\}$ for ML-20M and MSD and
$d\in\\{8,16,\dots,512\\}$; because the numbers of items after preprocessing
are $20{,}108$ for ML-20M, $41{,}140$ for MSD, and $3{,}423$ for Epinions, we
tune $d$ in different ranges to ensure the low-rank condition of MF. It can be
observed that, for all settings, the models with small dimensionalities
exhibit extremely large ARP@$K$ values (see blue lines). Particularly, at the
top of the rankings, the popularity bias in the prediction is severe (shown by
the leftmost figures in the top and bottom rows). These results suggest that
low-dimensional models recommend many popular items and, therefore, suffer
from anti-personalization. Furthermore, insufficient dimensionality leads to
low achievable ranking quality.

On the other hand, the trends exhibited by high-dimensional models are rather
different for ML-20M vs. for MSD and Epinions. Although the ranking quality
becomes saturated at a relatively low dimensionality of $1{,}024$ in ML-20M
for all $K$, the quality on MSD and Epinions can be further improved with high
dimensionality. Moreover, the popularity bias in ML-20M is the lowest with
$d=512$, which is not optimal in terms of ranking quality, whereas the best
one in terms of ranking quality for MSD also performs the best in terms of
popularity bias. This is possibly because the popularity bias is more severe
for ML-20M than for MSD; thus, reconciling high quality and low bias is
difficult for ML-20M. To confirm this, Figure 2 illustrates the distribution
of item popularity in ML-20M, MSD, and Epinions. The y-axis represents the
normalized frequency of each item (i.e., relative item popularity) in the
training dataset. The popularity bias in ML-20M is more intense than that in
MSD; there are many “long-tail” items in ML-20M. Remarkably, although the
results differ between ML-20M and MSD, we can draw the same conclusion:
sufficient dimensionality is necessary to alleviate the existing popularity
bias in ML-20M or to represent highly personalized recommendation results for
MSD and Epinions.

Figure 2. Distributions of relative item popularity. Figure 4. Effect of the
dimensionality on data collection efficiency. Figure 5. Improvement of models
with $d=128,256$ from that with $d=64$ in terms of mean recall for users.

###  3.3. Diversity and Item Fairness

Catalog coverage is one of the concepts related to the diversity of
recommendation results (i.e., aggregate diversity) (Herlocker et al., 2004;
Adomavicius and Kwon, 2009, 2011, 2014) and refers to the proportion of items
to be recommended. This can be viewed as the capacity of an effective item
catalog under a recommender system. On the other hand, item fairness is an
emerging concept similar to catalog coverage, yet it applies to different
situations and requirements (Burke, 2017). When each item belongs to a certain
user, the recommendation opportunity for the items is part of the user
utility; for instance, in an online dating application where each user
corresponds to an item, users (as items) can obtain more chances of success
when they are recommended more frequently.

Figure 3 shows the effect of dimensionality on catalog coverage and item
fairness for ML-20M and Epinions. Each curve indicates the Pareto frontier of
an iALS model that corresponds to a certain dimensionality with various
hyperparameter settings; we omitted this experiment for the large-scale MSD
because of the experimental burden. We use Coverage@$K$ (Cov@$K$) and Negative
Gini@$K$ as the measures of catalog coverage and item fairness, respectively.
Cov@$K$ is the proportion of items retrieved that are in the top-$K$ results
at least once (Herlocker et al., 2004), and Negative Gini@$K$ is the negative
Gini index (Atkinson, 1970) of items’ frequencies in the top-$K$ results333It
can be defined as $\text{Negative
Gini@}K=(2\left\lVert\mathbf{c}\right\rVert_{1}|\mathcal{V}|^{2})^{-1}\sum_{(j,l)\in\mathcal{V}\times\mathcal{V}}|c_{j}-c_{l}|$,
where $\mathbf{c}\in\mathbb{Z}_{+}^{|\mathcal{V}|}$ is the vector of item
frequencies in the top-$K$ list, and $c_{j}$ is the frequency of item
$j\in\mathcal{V}$..

A clear trend can be observed for all settings: models with larger dimensions
achieve higher capacities in terms of both catalog coverage and item fairness.
This result implies that low-dimensional models cannot produce diverse or fair
recommendation results. Notably, there exists a pair of models that are almost
equivalent in terms of ranking quality (i.e., R@$K$) but substantially
different in catalog coverage or item fairness. This suggests a serious
potential pitfall in practice. When developers evaluate and select models
based only on ranking quality, a reasonable choice may be to use a low-
dimensional model due to the space cost efficiency. However, such a model can
lead to extremely nondiverse and unfair recommendation results. Even when
developers select models based on both ranking quality and diversity, the
versatility of models is severely limited if the dimensionality parameter is
tuned for a narrow range of values owing to computational resource
constraints.

###  3.4. Self-Biased Feedback Loop

To capture the dynamic nature of user interests, a system usually retrains a
model after observing data within a certain time interval. By contrast,
hyperparameters are often fixed for model retraining because hyperparameter
tuning is a costly process, particularly when models are frequently updated.
Hence, the robustness of deployed models (including hyperparameters) to
dynamic changes in user behavior is critical. This may also be related to
unbiased recommendation (Chen et al., 2020) or batch learning from logged
bandit feedback (Swaminathan and Joachims, 2015). Because user feedback is
collected under the currently deployed system, item popularity is formed in
part by the system itself. Therefore, when a system narrows down its effective
item catalog, as demonstrated in Section 3.3, the data observed in the future
concentrate on items that are frequently recommended by the system. This
phenomenon accelerates popularity bias in the data and further increases the
number of cold-start items.

To observe the effect of dimensionality on data collection in a training and
observation loop, we repeatedly train and evaluate an iALS model with
different dimensionalities on ML-20M and MSD. Following a weak generalization
setting, we first observe 50% of the feedback for each user in the original
dataset. We then train a model using all samples in the observed dataset and
predict the top-50 rankings for all users, removing the observed user-item
pairs from the rankings. Subsequently, we observe the positive pairs in the
predicted rankings as an additional dataset for the next model training. In
the evaluation phase, we compute the proportion of observed samples for each
user; we simply call this measure _recall_ for users. Furthermore, we also
compute this recall measure for items to determine the degree to which the
system can collect data for each item.

Figure 4 shows the evolution of the recall measures for users and items. For
both ML-20M and MSD, models with higher dimensionalities achieve more
efficient data collection for both users and items. Remarkably, the difference
is substantial in the data collection for items; in the figures in the second
and fourth columns, a much larger efficiency gap can be observed between the
high- and low-dimensional models. Furthermore, this trend is emphasized for
MSD, which has a larger item catalog than ML-20M (as shown by the figure in
the fourth column of the bottom row). The results with $d=64$ for MSD in terms
of _median_ recall for users and items are remarkable, as shown by the red
lines in the third and fourth columns of the bottom row. The model with $d=64$
can collect data from users to some extent (third column), whereas the data
come from a small proportion of items (fourth column). Here, Figure 5
illustrates the performance gap (mean recall for users) between models with
$d=64$ and $d=128,256$. Although the gap in the first epoch is relatively
small for each setting, it grows in the next few epochs owing to the different
efficiency of data collection; interestingly, in ML-20M, the models with
$d=128,256$ deteriorate from that with $d=64$ only in the first epoch. The
performance gain is emphasized particularly with larger $d$ values. These
results imply that the gap between low- and high-dimensional models may become
tangible, particularly in a training and observation loop, whereas the
evaluation protocol in academic research simulates only the first epoch.

In summary, the results obtained in this part of the study are in good
agreement with those presented in the previous sections. Dimensionality
determines the capacity in terms of various aspects of recommendation quality
beyond accuracy. As demonstrated earlier, deterioration in diversity, item
fairness, and data collection ultimately affect long-term accuracy.

###  3.5. Summary of Empirical Results

Here, we summarize the empirical results obtained thus far. We first evaluated
the MF models (i.e., the simplest dot-product models) in the standard setting
of item recommendation in Section 3.2. We observed that high-dimensional
models tend to achieve high-ranking quality and low popularity bias in their
predicted rankings. To examine this phenomenon in depth, Section 3.3
investigated the relationship between dimensionality and diversity/fairness.
We obtained a clear trend showing that low-dimensionality limits the
versatility of models in terms of diversity and item fairness rather than
ranking quality; even when the other hyperparameters are tuned, the achievable
performance in terms of diversity/fairness is in a narrow range. In Section
3.4, we further investigated the effect of such a limited model space on data
collection and long-term accuracy. We simulated a practical situation wherein
a system re-trains models by using incrementally observed data under its own
recommendation policy. The results suggest that the data collected under low-
dimensional models are severely biased by the model itself and thus impede
accuracy improvement in the future. In the following section, we shall dive
into the mechanism of this “curse of low-dimensionality” phenomenon.

$\mathbf{v}_{1}$$\mathbf{v}_{2}$$\mathbf{v}_{3}$$\mathbf{v}_{4}$$O$$\langle\mathbf{q},\mathbf{v}_{1}\rangle>\langle\mathbf{q},\mathbf{v}_{4}\rangle$$\langle\mathbf{q},\mathbf{v}_{4}\rangle>\langle\mathbf{q},\mathbf{v}_{1}\rangle$

Figure 6.  Illustration of the proof idea of Theorem 4.1, which characterizes
representable rankings of size $n$ by regions in hyperplane arrangements.
There are four item vectors
$\mathbf{v}_{1},\mathbf{v}_{2},\mathbf{v}_{3},\mathbf{v}_{4}$ on
$\mathbb{R}^{2}$. Each dashed line connects a pair of the four vectors; each
bold line is orthogonal to some dashed line and intersects the origin. These
bold lines generate twenty regions in total, each corresponds to a distinct
ranking.

##  4\. Theoretical Investigation

We present (a summary of) theoretical analyses on the expressive power of dot-
product models to support the empirical results provided in Section 3, whose
formal statements and proofs are deferred to Appendix A. Our results are
twofold and highly specific to dot-product models:

#### Bounding the Number of Representable Rankings (cf. Section A.1)

First, we investigate how many different rankings may be expressed over a
fixed list of item vectors. Our hypothesis is that we suffer from popularity
bias and/or cannot achieve diversity and fairness satisfactorily owing to low
expressive power. In particular, we are interested in the number of
representable rankings parameterized by the number of items $n$,
dimensionality $d$, and size of rankings $K$.

Slightly formally, we say that a ranking $\pi$ of size $K$ is _representable_
over $n$ item vectors $\mathbf{v}_{1},\ldots,\mathbf{v}_{n}$ in
$\mathbb{R}^{d}$ if there exists a _query vector_
$\mathbf{q}\in\mathbb{R}^{d}$ (e.g., a user embedding) such that $\pi$ is
consistent with a ranking uniquely obtained by arranging $n$ items in
descending order of $\langle\mathbf{q},\mathbf{v}_{i}\rangle$. We devise upper
and lower bounds on the number of representable rankings, informally stated
as:

###### Theorem 4.1 (informal; see Theorems A.1 and A.2).

The following holds:

  * •

Upper bound: For every $n$ item vectors in $\mathbb{R}^{d}$, the number of
representable rankings of size $K$ over them is at most $n^{\min\\{K,2d\\}}$.

  * •

Lower bound: There exist $n$ item vectors in $\mathbb{R}^{d}$ such that the
number of representable rankings of size $d$ over them is $n^{\Theta(d)}$.

Our upper and lower bounds imply that the maximum possible number of
representable rankings of size $K$ is essentially $n^{\Theta(\min\\{K,d\\})}$,
offering the following insight: _increasing the dimensionality $d$
“exponentially” improves the expressive power of dot-product models_. Figures
6 and 7 illustrate the proof idea of our upper and lower bounds, which
characterize representable rankings by hyperplane arrangement and facets of a
polyhedron, respectively.

$\mathbf{v}_{1}$$\mathbf{v}_{2}$$\mathbf{v}_{3}$$\mathbf{v}_{4}$$\mathbf{v}_{5}$$\mathbf{v}_{6}$$O$$\mathcal{P}=\operatorname{conv}(\\{\mathbf{v}_{1},\mathbf{v}_{2},\mathbf{v}_{3},\mathbf{v}_{4},\mathbf{v}_{5},\mathbf{v}_{6}\\})$

Figure 7.  Illustration of the proof idea of Theorem 4.1, which partially
characterizes representable rankings of size $d$ by facets of a polyhedron.
There are six item vectors
$\mathbf{v}_{1},\mathbf{v}_{2},\mathbf{v}_{3},\mathbf{v}_{4},\mathbf{v}_{5},\mathbf{v}_{6}$
on $\mathbb{R}^{2}$, of which convex hull $\mathcal{P}$ has
$\mathbf{v}_{1},\mathbf{v}_{2},\mathbf{v}_{3},\mathbf{v}_{4}$ as its vertices;
each dashed segment represents a facet of $\mathcal{P}$. For each facet, there
exists a ranking of size $2$ dominated by any two item vectors on the facet.

#### Mechanism behind Popularity Bias (cf. Section A.2)

We then study the mechanism behind popularity bias and its effect on the space
of representable rankings. Consider first that there exists a pair of sets
consisting of _popular_ and _long-tail_ items. Usually, many users prefer
popular items than long-tail ones, which turns out to restrict the space from
which user embeddings are chosen; we can thus easily infer that some similar-
to-popular items rank higher than long-tail items as well.

Slightly formally, given a pair of sets,
$P=\\{\mathbf{p}_{1},\ldots,\mathbf{p}_{|P|}\\}$ and
$L=\\{\mathbf{l}_{1},\ldots,\mathbf{l}_{|L|}\\}$, consisting of popular and
long-tail items, we force a query vector $\mathbf{q}$ (e.g., a user embedding)
to always ensure that items of $P$ rank higher than items of $L$. Under this
setting, we establish a structural characterization of such “near-popular”
items that are ranked higher than $L$, informally stated as:

###### Theorem 4.2 (informal; see Theorems A.8 and A.9).

Suppose that a query vector $\mathbf{q}$ ranks all items of $P$ higher than
all items of $L$. Then, if an item vector $\mathbf{s}$ is included in a
particular convex cone that contains the convex hull of $P$, then $\mathbf{s}$
ranks higher than every item of $L$ (i.e., $\mathbf{s}$ is popular).

Moreover, this cone becomes bigger as more popular or long-tail items are
added (i.e., $|P|$ or $|L|$ is increased).

###### Example 4.3.

Figure 8 shows an illustration of Theorem 4.2. We are given three popular
items $P=\\{\mathbf{p}_{1},\mathbf{p}_{2},\mathbf{p}_{3}\\}$ and two long-tail
items $\mathbf{l}_{1},\mathbf{l}_{2}$. Given that a query vector $\mathbf{q}$
ranks the three popular items higher than $\mathbf{l}_{1}$ _only_ ,
$\mathbf{q}$ ranks another item $\mathbf{s}$ higher than $\mathbf{l}_{1}$
whenever $\mathbf{s}$ is in $\mathcal{S}(P,\\{\mathbf{l}_{1}\\})$, which is a
convex cone denoted by northeast blue lines. Similarly, if $\mathbf{q}$ ranks
$P$ higher than $\mathbf{l}_{2}$, $\mathbf{s}$ in
$\mathcal{S}(P,\\{\mathbf{l}_{2}\\})$, denoted by northwest red lines, ranks
higher than $\mathbf{l}_{2}$.

Consider now the case that popular items of $P$ rank higher than _both_
$\mathbf{l}_{1}$ and $\mathbf{l}_{2}$. Then, an item $\mathbf{s}$ ranks higher
than $\mathbf{l}_{1}$ and $\mathbf{l}_{2}$ if $\mathbf{s}$ is included in
$\mathcal{S}(P,\\{\mathbf{l}_{1},\mathbf{l}_{2}\\})$, which is a convex cone
denoted by two arrows. This convex cone is larger than
$\mathcal{S}(P,\\{\mathbf{l}_{1}\\})$ and
$\mathcal{S}(P,\\{\mathbf{l}_{2}\\})$.

The above theorem suggests that the existence of a small number of popular and
long-tail items makes other near-popular items superior to long-tail ones,
reducing the number of representable rankings, and thus we may not completely
avoid popularity bias.

In conclusion, our theoretical results justify the empirical observations: The
limited catalog coverage with low dimensionality in Section 3.3 is due to lack
of the number of representable rankings as in Theorem 4.1, and the popularity
bias (a large value of ARP@$K$) observed in Section 3.2 is partially explained
by Theorem 4.2 and the discussion in Section A.2. Furthermore, as our
theoretical methodology only assumes that the underlying architecture follows
dot-product models, the counter-intuitive phenomena of low-dimensionality
would be applied to not only for iALS but also for any dot-product models.

$\mathbf{l}_{1}$$\mathbf{l}_{2}$$\mathbf{p}_{1}$$\mathbf{p}_{2}$$\mathbf{p}_{3}$$\mathbf{s}$$O$$\mathcal{S}(P,\\{\mathbf{l}_{1}\\})$$\mathcal{S}(P,\\{\mathbf{l}_{2}\\})$$\mathcal{S}(P,\\{\mathbf{l}_{1},\mathbf{l}_{2}\\})$intersection$\rightarrow$

Figure 8.  Illustration of Theorem 4.2. Let
$P=\\{\mathbf{p}_{1},\mathbf{p}_{2},\mathbf{p}_{3}\\}$ be a set of three
popular items and $L=\\{\mathbf{l}_{1},\mathbf{l}_{2}\\}$ be a set of two
long-tail items. Any item in $\mathcal{S}(P,\\{\mathbf{l}_{1}\\})$ (resp.
$\mathcal{S}(P,\\{\mathbf{l}_{2}\\})$) denoted northeast blue (resp. northwest
red) lines, ranks higher than $\mathbf{l}_{1}$ (resp. $\mathbf{l}_{2}$)
whenever all popular items of $P$ rank higher than $\mathbf{l}_{1}$ (resp.
$\mathbf{l}_{2}$). The intersection of $\mathcal{S}(P,\\{\mathbf{l}_{1}\\})$
and $\mathcal{S}(P,\\{\mathbf{l}_{2}\\})$ is crosshatched.
$\mathcal{S}(P,\\{\mathbf{l}_{1},\mathbf{l}_{2}\\})$ is a convex cone defined
by two arrows, which includes
$\mathcal{S}(P,\\{\mathbf{l}_{1}\\})\cap\mathcal{S}(P,\\{\mathbf{l}_{2}\\})$.
Any item in $\mathcal{S}(P,\\{\mathbf{l}_{1},\mathbf{l}_{2}\\})$ ranks higher
than both $\mathbf{l}_{1}$ and $\mathbf{l}_{2}$ whenever all items of $P$ rank
higher than all items of $L$.

##  5\. Discussion and Future Direction

#### Efficient Solvers for High Dimensionality

High-dimensional models are often computationally costly. Even in the most
efficient methods based on MF, the optimization involves cubic dependency on
$d$ and thus does not scale well for high-dimensional models. Motivated by
this, previous studies have explored efficient methods for high-dimensional
models (He et al., 2016; Bayer et al., 2017; Rendle et al., 2021). Because the
traditional ALS solver for MF is in the class of block coordinate descent
(CD), conventional methods can be derived by designing the choice of blocks
(Rendle et al., 2021). It is hence interesting to design block CD methods for
high-dimensional models considering efficiency on modern computer
architectures (e.g., CPU with SIMD, GPU, and TPU (Mehta et al., 2021)).
Developing solvers for more complex models, such as factorization machines
(Rendle, 2012; Bayer et al., 2017), is useful to leverage side information.
Since deep learning-based models are also employed, efficient solvers for such
non-linear models (Yang et al., 2020) will be beneficial for enhancing the
ranking quality. The extension of conventional algorithms to stochastic
optimization, which uses a subset of data samples in a single update, is also
important for using memory-intensive complex models and large-scale data. To
reduce the memory footprint of embeddings, sparse representation may also be
promising (Ning and Karypis, 2011). As sparsity constraints introduce another
difficulty in optimization, some techniques, such as the alternating direction
method of multipliers (ADMM) (Boyd et al., 2011), would be required. ADMM is a
recent prevalent approach to enable parallel and scalable optimization under
constraints (Yu et al., 2014; Steck et al., 2020; Steck and Liang, 2021;
Togashi and Abe, 2022). Improving the serving cost of high-dimensional models
is also essential by using maximum inner-product search (MIPS) (Jegou et al.,
2010; Shrivastava and Li, 2014; Malkov and Yashunin, 2018).

#### Efficient Methods for Diversity and Item Fairness

Our empirical results suggest that diversity and item fairness may also be
beneficial for efficient data collection and long-term accuracy. We can also
infer from our results that directly optimizing diversity and item fairness is
a promising approach to enhancing long-term recommendation quality. From a
practical point of view, however, diverse and fair item recommendation is
often computationally costly because of combinatorial explosions in large-
scale settings. Hence, it is an important direction to develop efficient
diversity-aware recommendation (Yao et al., 2016; Chen et al., 2017, 2018;
Wilhelm et al., 2018; Warlop et al., 2019). In the same spirit as dot-product
models, efficient sampling techniques based on MIPS are essential for real-
time retrieval (Han and Gillenwater, 2020; Hirata et al., 2022). On the other
hand, fairness-aware item recommendation is a challenging task in terms of its
computational efficiency. Because fairness requires controlling item exposure
while considering all rankings for users, it is relatively complex in both
optimization and prediction phases compared to fairness-agnostic top-$K$
ranking problems. There exist a variety of approaches to implementing fair
recommender systems based on constraint optimization (Celis et al., 2018;
Singh and Joachims, 2018; Patro et al., 2020; Memarrast et al., 2021; Togashi
and Abe, 2022). Although we focus on offline collaborative filtering, online
recommendation methods based on bandit algorithms (Li et al., 2016; Korda et
al., 2016; Mahadik et al., 2020; Patil et al., 2021; Wang et al., 2021; Jeunen
and Goethals, 2021) are also promising for directly integrating accuracy
optimization and data collection.

#### Further Theoretical Analysis on Dot-product Models

Our theoretical results might help us gain a deeper understanding of the
expressive power of dot-product models. Besides the open problems described in
Section 4, there is still much room for further investigation of its
expressive power. We may consider a fine-grained analysis of representable
$K$-permutations for $K\not\in\\{d,n\\}$; e.g., to establish the exact upper
or lower bounds of $\operatorname{\mathsf{nperm}}_{K}$. One major limitation
of Theorem 4.1 is that they do not promise that _every_ $n^{\Theta(d)}$
ranking is representable (over some $n$ $d$-dimensional item vectors); i.e.,
we cannot rule out the existence of a small set of rankings that cannot be
expressed under dot-product models. Thus, a possible direction is to analyze
the representability of an input set $\Pi$ of rankings: Can we construct $n$
item vectors over which each ranking of $\Pi$ is representable? This question
may be thought of as an _inverse problem_ to that discussed in Section A.1.

##  6\. Conclusion

In this paper, we presented empirical results that reveal the necessity of
sufficient dimensionality in dot-product models. Our results suggest that low-
dimensionality leads to overfitting to existing popularity bias and further
amplifies the bias in future data. This phenomenon, referred to as _curse of
low dimensionality_ , partly causes modern problems in recommender systems,
such as personalization, diversity, fairness, and robustness to biased
feedback. Then, we theoretically discussed the phenomenon from the viewpoint
of _representable rankings_ , which are the rankings that a model can
represent. We showed the bound on the number of representable rankings for
$d$-dimensional models. This result suggests that low-dimensionality leads to
an exponentially small number of representable rankings. We also explained the
effect of popular items on representable rankings. Finally, we established a
structural characterization of near-popular items, suggesting a mechanism
behind popularity bias under dot-product models.

##  Appendix A Formal Statements and Proofs

###  A.1. Number of Representable Rankings

We devise lower and upper bounds on the number of representable rankings
parameterized by the number of items, dimensionality, and size of rankings.
Hereafter, we identify the set $\mathcal{V}$ of $n$ items with
$[n]\triangleq\\{1,2,\ldots,n\\}$. For nonnegative integers $n\in\mathbb{N}$
and $K\in[n]$, let $\mathfrak{S}_{n}$ denote the set of all permutations over
$[n]$, and let $\mathfrak{S}_{n}^{K}$ denote the set of all $K$-permutations
of $[n]$ (also known as partial permutations); e.g.,
$\mathfrak{S}_{3}^{2}=\\{(1,2),\allowbreak(1,3),\allowbreak(2,1),\allowbreak(2,3),\allowbreak(3,1),\allowbreak(3,2)\\}$.
Note that $\mathfrak{S}_{n}^{n}=\mathfrak{S}_{n}$, $|\mathfrak{S}_{n}|=n!$,
and $|\mathfrak{S}_{n}^{K}|=n^{\underline{K}}$, where
$n^{\underline{K}}\triangleq\frac{n!}{(n-K)!}$ denotes the falling factorial.
We consider each $K$-permutation $\pi\in\mathfrak{S}_{n}^{K}$ as a ranked list
of $K$ items such that item $\pi(i)$ ranks in the $i$-th place.

We now define the representability of $K$-permutations. For $n$ items, let
$\mathbf{v}_{1},\ldots,\mathbf{v}_{n}$ be vectors in $\mathbb{R}^{d}$
representing their embeddings. Without much loss of generality, we assume that
they are in _general position_ ; i.e., no $d+1$ vectors lie on a hyperplane.
Given a _query vector_ $\mathbf{q}\in\mathbb{R}^{d}$ (e.g., a user embedding),
we generally produce a ranking obtained by arranging $n$ items in descending
order of $\langle\mathbf{q},\mathbf{v}_{i}\rangle$. We thus say that
$\mathbf{q}$ over $\mathbf{v}_{1},\ldots,\mathbf{v}_{n}$ _represents_ a
$K$-permutation $\pi\in\mathfrak{S}_{n}^{K}$ if
$\langle\mathbf{q},\mathbf{v}_{\pi(i)}\rangle>\langle\mathbf{q},\mathbf{v}_{\pi(j)}\rangle$
for all $1\leq i<j\leq K$ and
$\langle\mathbf{q},\mathbf{v}_{\pi(K)}\rangle>\langle\mathbf{q},\mathbf{v}_{\pi(i)}\rangle$
for all $K+1\leq i\leq n$, and that $\pi$ is _representable_ if such
$\mathbf{q}$ exists. Here, we emphasize that “ties” are not allowed; i.e.,
$\mathbf{q}$ does not represent $\pi$ whenever
$\langle\mathbf{q},\mathbf{v}_{i}\rangle=\langle\mathbf{q},\mathbf{v}_{j}\rangle$
for some $i\neq j$. We let
$\operatorname{\mathsf{nperm}}_{K}(\mathbf{v}_{1},\ldots,\mathbf{v}_{n})$ be
the number of representable $K$-partial permutations over
$\mathbf{v}_{1},\ldots,\mathbf{v}_{n}$; namely,

$\displaystyle\operatorname{\mathsf{nperm}}_{K}(\mathbf{v}_{1},\ldots,\mathbf{v}_{n})\triangleq|\\{\pi\in\mathfrak{S}_{n}^{K}:\pi\text{
is representable over }\mathbf{v}_{i}\text{'s}\\}|.$

By definition,
$\operatorname{\mathsf{nperm}}_{K}(\mathbf{v}_{1},\ldots,\mathbf{v}_{n})\leq
n^{\underline{K}}\leq n^{K}$. Our first result is an upper bound on
$\operatorname{\mathsf{nperm}}_{n}$.

###### Theorem A.1.

For any $n$ vectors $\mathbf{v}_{1},\ldots,\mathbf{v}_{n}$ in $\mathbb{R}^{d}$
in general position,
$\operatorname{\mathsf{nperm}}_{n}(\mathbf{v}_{1},\ldots,\mathbf{v}_{n})\leq
n^{2d}.$ In particular,
$\operatorname{\mathsf{nperm}}_{n}(\mathbf{v}_{1},\ldots,\mathbf{v}_{n})\leq
n^{\min\\{K,2d\\}}$ for every $K\in[n]$.

The proof uses a characterization of representable permutations by hyperplane
arrangements, which is illustrated in Figure 6.

Subsequently, we provide a lower bound on $\operatorname{\mathsf{nperm}}_{d}$
in terms of the number of facets of a polyhedron. Let
$\mathcal{P}\triangleq\operatorname{conv}(\\{\mathbf{v}_{1},\ldots,\mathbf{v}_{n}\\})\subset\mathbb{R}^{d}$
be a _convex hull_ of $\mathbf{v}_{1},\ldots,\mathbf{v}_{n}$; every vertex of
$\mathcal{P}$ corresponds to some $\mathbf{v}_{i}$. For a vector
$\mathbf{a}\in\mathbb{R}^{d}$ and scalar $z\in\mathbb{R}$, a linear inequality
$\langle\mathbf{a},\mathbf{x}\rangle\leq b$ is said to be _valid_ if
$\langle\mathbf{a},\mathbf{x}\rangle\leq b$ for all
$\mathbf{x}\in\mathcal{P}$. A subset $\mathcal{F}$ of $\mathcal{P}$ is called
a _face_ of $\mathcal{P}$ if
$\mathcal{F}=\mathcal{P}\cup\\{\mathbf{x}:\langle\mathbf{a},\mathbf{x}\rangle=b\\}$
for some valid linear inequality $\langle\mathbf{a},\mathbf{x}\rangle\leq b$.
In particular, $(d-1)$-dimensional faces are called _facets_. Every facet
includes exactly $d$ vertices of $\mathcal{P}$ by definition (whenever $n$
vectors are in general position). Our second result is as follows.

###### Theorem A.2.

For any $n$ vectors $\mathbf{v}_{1},\ldots,\mathbf{v}_{n}$ in $\mathbb{R}^{d}$
in general position,
$\operatorname{\mathsf{nperm}}_{d}(\mathbf{v}_{1},\ldots,\mathbf{v}_{n})$ is
at least the number of facets of $\mathcal{P}$. Moreover, there exist $n$
vectors $\mathbf{v}_{1},\ldots,\mathbf{v}_{n}$ in $\mathbb{R}^{d}$ such that

$\displaystyle\operatorname{\mathsf{nperm}}_{d}(\mathbf{v}_{1},\ldots,\mathbf{v}_{n})\geq{n\choose\left\lceil
d/2\right\rceil}\geq\left(\frac{n}{d/2}\right)^{d/2}.$

By Theorems A.1 and A.2, the maximum possible number of representable
$K$-permutations over $n$ vectors in $\mathbb{R}^{d}$ is
$n^{\Theta(\min\\{K,d\\})}$ for all $K\in[n]$ and $d=\mathcal{O}(1)$.

What remains to be done is the proof of Theorems A.1 and A.2.

###### Proof of Theorem A.1.

For each $1\leq i<j\leq n$, we introduce a _pairwise preference_
$\delta_{i,j}\in\\{\pm 1\\}$ between $i$ and $j$. We wish for a query vector
$\mathbf{q}\in\mathbb{R}^{d}$ to ensure that item $i$ (resp. $j$) ranks higher
than item $j$ (resp. $i$) if $\delta_{i,j}$ is $+1$ (resp. $-1$). This
requirement is equivalent to
$\langle\mathbf{q},\mathbf{v}_{i}-\mathbf{v}_{j}\rangle\cdot\delta_{i,j}>0$.
Thus, if the following system of linear inequalities is feasible, any of its
solutions $\mathbf{q}$ represents a unique permutation consistent with
$\delta_{i,j}$’s:444 Note that for Eq. 1 to be feasible, $\delta_{i,j}$’s
should be _transitive_ ; i.e., $\delta_{i,j}=+1$ and $\delta_{j,k}=+1$ imply
$\delta_{i,k}=+1$.

(1)
$\displaystyle\langle\mathbf{q},\mathbf{v}_{i}-\mathbf{v}_{j}\rangle\cdot\delta_{i,j}>0\quad\text{
for all }1\leq i<j\leq n.$

On one hand, for any representable permutation $\pi\in\mathfrak{S}_{n}$, Eq. 1
defined by

$\displaystyle\delta_{i,j}=\begin{cases}+1&\text{if }i\text{ ranks higher than
}j,\\\ -1&\text{if }j\text{ ranks higher than }i,\\\ \end{cases}$

must be feasible. On the other hand, two different sets of pairwise
preferences derive distinct permutations (if they exist). Hence,
$\operatorname{\mathsf{nperm}}_{n}(\mathbf{v}_{1},\ldots,\mathbf{v}_{n})$ is
equal to the number of $\delta_{i,j}$’s for which Eq. 1 has a solution.

Observe now that Eq. 1 is feasible _if and only if_ the intersection of
$\mathcal{H}_{i,j}$’s for all $1\leq i<j\leq n$ is nonempty, where
$\mathcal{H}_{i,j}$ is an open half-space defined as

$\displaystyle\mathcal{H}_{i,j}\triangleq\\{\mathbf{q}\in\mathbb{R}^{d}:\langle\mathbf{q},\mathbf{v}_{i}-\mathbf{v}_{j}\rangle\cdot\delta_{i,j}>0\\}.$

Because $\mathcal{H}_{i,j}$ is obtained via the division of $\mathbb{R}^{d}$
by a unique hyperplane that is orthogonal to $\mathbf{v}_{i}-\mathbf{v}_{j}$
and intersects the origin, the number of $\delta_{i,j}$’s for which Eq. 1 is
feasible is equal to _the number of regions generated by hyperplane
arrangement_ , which has been investigated in geometric combinatorics. By (Ho
and Zimmerman, 2006; Winder, 1966), the number of regions generated by
${n\choose 2}$ $(d-1)$-dimensional hyperplanes that have a common point is at
most

(2) $\displaystyle 2\sum_{0\leq i\leq d-1}{{n\choose 2}-1\choose i}\leq
2\cdot{n\choose 2}^{d-1}\leq n^{2d},$

thereby completing the proof. ∎

###### Remark A.3.

Figure 6 illustrates the equivalence between representable permutations and
regions of hyperplane arrangements. There are four vectors
$\mathbf{v}_{1},\mathbf{v}_{2},\mathbf{v}_{3},\mathbf{v}_{4}$ on
$\mathbb{R}^{2}$. Each dashed line connects a pair of the four vectors; each
bold line is orthogonal to some dashed line and intersects the origin. These
hyperplanes generate twenty regions, each of which expresses a distinct
permutation. The number “$12$” is tight because the left-hand side of Eq. 2 is
$2\left({{4\choose 2}-1\choose 0}+{{4\choose 2}-1\choose 1}\right)=12$. On the
other hand, a ranking
$(\mathbf{v}_{1},\mathbf{v}_{3},\mathbf{v}_{2},\mathbf{v}_{4})$ is not
representable.

Before going into the proof of Theorem A.2, we prove the following, which
partially characterizes representable $d$-permutations and is illustrated in
Figure 7:

###### Claim A.4.

For any set $I\in{[n]\choose d}$ of $d$ items, if there exists a facet
$\mathcal{F}$ of $\mathcal{P}$ including $\mathbf{v}_{i}$ for every $i\in I$,
there is a query vector $\mathbf{q}\in\mathbb{R}^{d}$ that represents a
$d$-permutation consisting only of $I$.

###### Proof of Claim A.4.

By the definition of facets, there exist $\mathbf{a}\in\mathbb{R}^{d}$ and
$b\in\mathbb{R}$ such that $\langle\mathbf{v}_{i},\mathbf{a}\rangle=b$ for all
$i\in I$ while $\langle\mathbf{v}_{i},\mathbf{a}\rangle<b$ for all $i\not\in
I$. Thus, letting $\mathbf{q}\triangleq\mathbf{a}$ completes the proof. ∎

###### Remark A.5.

Figure 7 gives an illustration of Claim A.4. There are six vectors
$\mathbf{v}_{1},\mathbf{v}_{2},\mathbf{v}_{3},\mathbf{v}_{4},\mathbf{v}_{5},\mathbf{v}_{6}$
on $\mathbb{R}^{2}$. The convex hull $\mathcal{P}$ of them has
$\mathbf{v}_{1},\mathbf{v}_{2},\mathbf{v}_{3},\mathbf{v}_{4}$ as its vertices;
each dashed segment represents a facet of $\mathcal{P}$. Taking an outward
normal vector to a facet, denoted a bold arrow, as a query vector, we obtain a
$2$-permutation dominated by two vectors on the facet.

###### Proof of Theorem A.2.

Because of Claim A.4, the number of representable $d$-permutation is at least
the number of facets of $\mathcal{P}$. By the _upper bound theorem_ due to
McMullen (Motzkin, 1957; McMullen, 1970), the maximum possible number of
facets of a convex polytope consisting of $n$ vertices in $\mathbb{R}^{d}$ is
${n\choose\left\lceil d/2\right\rceil}.$ This upper bound can be achieved when
$\mathcal{P}$ is a cyclic polytope,555 The _cyclic polytope_ is defined as
$\operatorname{conv}(\\{\mathbf{\alpha}_{d}(t_{1}),\ldots,\mathbf{\alpha}_{d}(t_{n})\\})$
for distinct $t_{i}$’s, where
$\mathbf{\alpha}_{d}(t)\triangleq(t,t^{2},\ldots,t^{d})$ is the moment curve.
thus completing the proof. ∎

###### Example A.6.

Finally, we show by a simple example that facets do not fully characterize
representable $d$-permutations; i.e., Claim A.4 is not tight. Four item
vectors $\mathbf{v}_{1},\mathbf{v}_{2},\mathbf{v}_{3},\mathbf{v}_{4}$ in
$\mathbb{R}^{2}$ are defined as:

$\displaystyle\mathbf{v}_{1}=(+1,0),\mathbf{v}_{2}=(-1,0),\mathbf{v}_{3}=(0,+1),\mathbf{v}_{4}=(0,+\tfrac{1}{2}).$

The convex hull $\mathcal{P}$ is clearly a triangle formed by
$\\{\mathbf{v}_{1},\mathbf{v}_{2},\mathbf{v}_{3}\\}$. By Claim A.4, for each
facet of $\mathcal{P}$, there is a representable $2$-permutation dominated by
the vectors on the facet. However, the query vector $\mathbf{q}=(0,1)$
produces a $2$-permutation dominated by $\mathbf{v}_{3}$ and $\mathbf{v}_{4}$,
even though $\mathbf{v}_{4}$ lies on no facet of $\mathcal{P}$. We leave the
complete characterization of representable $d$-permutations as an open
problem.

###  A.2. Mechanism behind Popularity Bias

Subsequently, we study the mechanism behind popularity bias and its effect on
the space of representable rankings. Suppose we wish a query vector
$\mathbf{q}\in\mathbb{R}^{d}$ to ensure that the embedding of $|P|$ popular
items denoted
$P\triangleq\\{\mathbf{p}_{1},\ldots,\mathbf{p}_{|P|}\\}\subset\mathbb{R}^{d}$
ranks higher than the embedding of $|L|$ long-tail items denoted
$L\triangleq\\{\mathbf{l}_{1},\ldots,\mathbf{l}_{|L|}\\}\subset\mathbb{R}^{d}$;
that is, it must hold that
$\langle\mathbf{q},\mathbf{p}_{i}\rangle>\langle\mathbf{q},\mathbf{l}_{j}\rangle\text{
for all }i\in[|P|],j\in[|L|].$ Let $\mathcal{Q}(P,L)$ be the closure of the
set of all such vectors;666 We take the closure for the sake of analysis.
namely,

$\displaystyle\mathcal{Q}(P,L)\triangleq\\{\mathbf{q}\in\mathbb{R}^{d}:\langle\mathbf{q},\mathbf{p}_{i}\rangle\geq\langle\mathbf{q},\mathbf{l}_{j}\rangle,\;\forall
i\in[|P|],j\in[|L|]\\}.$

We can easily decide whether $\mathcal{Q}(P,L)$ is empty or not as follows.

###### Observation A.7.

$\mathcal{Q}(P,L)\neq\emptyset$ if and only if there exists a hyperplane that
divides $P$ and $L$.

Now, it is considered that the query vectors are chosen only from
$\mathcal{Q}(P,L)$. What type of item vector would always rank higher than
$L$? We define $\mathcal{S}(P,L)$ as the closure of the set of vectors in
$\mathbb{R}^{d}$ that rank higher than all vectors of $L$ provided that
$\mathbf{q}\in\mathcal{Q}(P,L)$; namely,

$\displaystyle\mathcal{S}(P,L)\triangleq\\{\mathbf{s}\in\mathbb{R}^{d}:\langle\mathbf{q},\mathbf{s}\rangle\geq\langle\mathbf{q},\mathbf{l}_{j}\rangle,\;\forall
j\in[|P|],\mathbf{q}\in\mathcal{Q}(P,U)\\}.$

First, it is observed that $\mathcal{S}(P,L)$ is convex; in fact, for any
vector $\mathbf{s}=\mu\mathbf{s}_{1}+(1-\mu)\mathbf{s}_{2}$ such that
$\mathbf{s}_{1},\mathbf{s}_{2}\in\mathcal{S}(P,L)$ and $\mu\in[0,1]$, we have

$\displaystyle\langle\mathbf{q},\mathbf{s}\rangle$
$\displaystyle=\mu\langle\mathbf{q},\mathbf{s}_{1}\rangle+(1-\mu)\langle\mathbf{q},\mathbf{s}_{2}\rangle$
$\displaystyle\geq\mu\max_{j\in[|P|]}\langle\mathbf{q},\mathbf{l}_{j}\rangle+(1-\mu)\max_{j\in[|P|]}\langle\mathbf{q},\mathbf{l}_{j}\rangle=\max_{j\in[|P|]}\langle\mathbf{q},\mathbf{l}_{j}\rangle$

whenever $\mathbf{q}\in\mathcal{Q}(P,L)$. In particular, any convex
combination of $P$ ranks higher than $L$ if $\mathbf{q}\in\mathcal{Q}(P,L)$.

To characterize the structure of $\mathcal{S}(P,L)$, we further introduce some
definitions and notations. For two subsets $\mathcal{A}$ and $\mathcal{B}$ of
$\mathbb{R}^{d}$, the _Minkowski sum_ , denoted
$\mathcal{A}\oplus\mathcal{B}$, is defined as the set of all sums of a vector
from $\mathcal{A}$ and a vector from $\mathcal{B}$; namely,
$\mathcal{A}\oplus\mathcal{B}\triangleq\\{\mathbf{a}+\mathbf{b}:\mathbf{a}\in\mathcal{A},\mathbf{b}\in\mathcal{B}\\}.$
The _half-line_ for a vector $\mathbf{v}\in\mathbb{R}^{d}$ is defined as
$\overrightarrow{\mathbf{v}}\triangleq\\{\lambda\mathbf{v}:\lambda\geq 0\\}.$
The _polyhedral cone_ generated by $k$ vectors
$\mathbf{v}_{1},\ldots,\mathbf{v}_{k}\in\mathbb{R}^{d}$ is defined as the
conical hull of $\mathbf{v}_{1},\ldots,\mathbf{v}_{k}$; namely,

$\displaystyle\operatorname{\mathcal{PC}}(\mathbf{v}_{1},\ldots,\mathbf{v}_{k})\triangleq\Bigl{\\{}\sum_{i\in[k]}\lambda_{i}\mathbf{v}_{i}:\forall\lambda_{i}\geq
0\Bigr{\\}}=\bigoplus_{i\in[k]}\overrightarrow{\mathbf{v}_{i}}.$

Note that $\operatorname{\mathcal{PC}}(\mathbf{v}_{1},\ldots,\mathbf{v}_{k})$
is a convex cone. For $k+1$ vectors
$\mathbf{v}_{1},\ldots,\mathbf{v}_{k},\allowbreak\mathbf{e}\in\mathbb{R}^{d}$,
the polyhedral cone generated by $\mathbf{v}_{1},\ldots,\mathbf{v}_{k}$ with
$\mathbf{e}$ as an extreme point is defined as

$\displaystyle\operatorname{\mathcal{PC}}(\mathbf{v}_{1},\ldots,\mathbf{v}_{k};\mathbf{e})$
$\displaystyle\triangleq\mathbf{e}\oplus\operatorname{\mathcal{PC}}(\mathbf{v}_{1},\ldots,\mathbf{v}_{k}).$

By the Minkowski–Weyl theorem (Minkowski, 1896; Weyl, 1935), any polyhedral
cone can be represented as the intersection of a finite number of half-spaces
with $\mathbf{e}$ on their boundary.

We first establish a complete characterization of $\mathcal{S}(P,L)$ when $L$
is a singleton consisting of a vector $\mathbf{l}\in\mathbb{R}^{d}$; see also
Figure 8.

###### Theorem A.8.

It holds that
$\mathcal{S}(P,\\{\mathbf{l}\\})=\operatorname{\mathcal{PC}}(\\{\mathbf{p}_{1}-\mathbf{l},\ldots,\mathbf{p}_{k}-\mathbf{l}\\};\mathbf{l}).$

We further show that $\mathcal{S}(P,L)$ becomes very large as $P$ or $L$
grows.

###### Theorem A.9.

It holds that

(3) $\displaystyle\mathcal{S}(P,L)$
$\displaystyle\supseteq\Bigl{(}\bigcap_{j\in[|L|]}\mathcal{S}(P,\\{\mathbf{l}_{j}\\})\Bigr{)}\oplus\bigoplus_{i\in[|P|],j\in[|L|]}\overrightarrow{\mathbf{p}_{i}-\mathbf{l}_{j}}$
(4)
$\displaystyle\supseteq\operatorname{conv}(\\{\mathbf{p}_{1},\ldots,\mathbf{p}_{|P|}\\})\oplus\bigoplus_{i\in[|P|],j\in[|L|]}\overrightarrow{\mathbf{p}_{i}-\mathbf{l}_{j}}.$

###### Remark A.10.

Figure 8 gives an example of Theorems A.8 and A.9. Let
$P=\\{\mathbf{p}_{1},\mathbf{p}_{2},\mathbf{p}_{3}\\}$ and
$L=\\{\mathbf{l}_{1},\mathbf{l}_{2}\\}$. $\mathcal{S}(P,\\{\mathbf{l}_{1}\\})$
and $\mathcal{S}(P,\\{\mathbf{l}_{2}\\})$ are denoted by northeast (blue)
lines and northwest (red) lines, respectively. The intersection of
$\mathcal{S}(P,\\{\mathbf{l}_{1}\\})$ and
$\mathcal{S}(P,\\{\mathbf{l}_{2}\\})$ is crosshatched. $\mathcal{S}(P,L)$ is a
convex cone defined by two arrows, which includes
$\mathcal{S}(P,\\{\mathbf{l}_{1}\\})\cap\mathcal{S}(P,\\{\mathbf{l}_{2}\\})$.

$\mathcal{S}(P,L)$ particularly contains
$\operatorname{conv}(\\{\mathbf{p}_{1},\ldots,\mathbf{p}_{|P|}\\})$, and a
polyhedral cone defined by
$\bigoplus_{i\in[|P|],j\in[|L|]}\overrightarrow{\mathbf{p}_{i}-\mathbf{l}_{j}}$
becomes bigger as either the number of popular items or the number of long-
tail items is increased. In particular, Eq. 4 is _monotone_ in $P$ and $L$
(with respect to the inclusion property). We leave as open whether the
inclusion in Eq. 3 is strict or not.

Here, we discuss the dimensionality of $\mathcal{S}(P,L)$. If
$\dim(\mathcal{S}(P,L))$ is less than $d$, a vector randomly taken from
$\mathbb{R}^{d}$ lies on $\mathcal{S}(P,L)$ with probability $0$; thus, we
would not be concerned about popularity bias. Unfortunately,
$\dim(\mathcal{S}(P,L))$ can be bounded only by

$\displaystyle\dim\Bigl{(}\bigcap_{j}\mathcal{S}(P,\\{\mathbf{l}_{j}\\})\Bigr{)}+\dim\Bigl{(}\bigoplus_{i,j}\overrightarrow{\mathbf{p}_{i}-\mathbf{l}_{j}}\Bigr{)}\leq(|P|+1)|L|,$

if the inclusion in Eq. 3 is an equality. Thus, we cannot inherently avoid
popularity bias under dot-product models.

However, a characterization of $\mathcal{S}(P,L)$ by a cone-like structure
implies the effect of increasing the dimensionality on popularity bias
reduction. Suppose that $\mathcal{S}(P,L)$ is a $d$-dimensional right circular
cone of half-angle $\theta$. Then, the event in which _a random item vector
uniformly chosen from $\mathbb{R}^{d}$ belongs to $\mathcal{S}(P,L)$_ occurs
with a probability equal to the area ratio of a spherical cap of polar angle
$\theta$ in the $(d-1)$-dimensional unit sphere to the $(d-1)$-dimensional
unit sphere. By (Li, 2011), this ratio is $\frac{\frac{1}{2}A_{d-1}\cdot
I_{\sin^{2}\theta}\left(\frac{d-1}{2},\frac{1}{2}\right)}{A_{d-1}}=\frac{1}{2}I_{\sin^{2}\theta}\left(\frac{d-1}{2},\frac{1}{2}\right),$
where $A_{d-1}$ is the area of the $(d-1)$-dimensional unit sphere and
$I_{x}(a,b)$ is the regularized incomplete beta function. By using the
asymptotic expansion of $I_{x}(a,b)$ for fixed $b$ and $x$ (Temme, 1996) and

an approximation of the beta function $\mathrm{B}(a,b)\approx\Gamma(b)\cdot
a^{-b}$, we have
$I_{\sin^{2}\theta}\left(\frac{d-1}{2},\frac{1}{2}\right)\approx\frac{(\sin^{2}\theta)^{\frac{d-1}{2}}\cdot(\cos^{2}\theta)^{-\frac{1}{2}}}{\frac{d-1}{2}\cdot\Gamma(\frac{1}{2})(\frac{d-1}{2})^{-\frac{1}{2}}}=\Theta\left(\frac{(\sin\theta)^{d-1}}{\sqrt{d-1}}\right);$
i.e., the probability of this event decays _exponentially_ in $d$.

In the remainder of this section, we prove Theorems A.8 and A.9.

###### Proof of Theorem A.8.

We first show
$\operatorname{\mathcal{PC}}(\\{\mathbf{p}_{1}-\mathbf{l},\ldots,\mathbf{p}_{|P|}-\mathbf{l}\\};\mathbf{l})\subseteq\mathcal{S}(P,\\{\mathbf{l}\\})$.
Let $\mathbf{s}$ be any vector in
$\operatorname{\mathcal{PC}}(\\{\mathbf{p}_{1}-\mathbf{l},\ldots,\mathbf{p}_{|P|}-\mathbf{l}\\};\mathbf{l})$;
hence,
$\mathbf{s}=\mathbf{l}+\sum_{i\in[|P|]}\lambda_{i}(\mathbf{p}_{i}-\mathbf{l})$
for some $\lambda_{i}\geq 0$. We then have that for every
$\mathbf{q}\in\mathcal{Q}(P,\\{\mathbf{l}\\})$,

$\displaystyle\langle\mathbf{q},\mathbf{s}\rangle=\langle\mathbf{q},\mathbf{l}\rangle+\sum_{i\in[|P|]}\lambda_{i}\cdot\Bigl{(}\underbrace{\langle\mathbf{q},\mathbf{p}_{i}\rangle-\langle\mathbf{q},\mathbf{l}\rangle}_{\geq
0}\Bigr{)}\geq\langle\mathbf{q},\mathbf{l}\rangle.$

Thus, $\mathbf{s}\in\mathcal{S}(P,\\{\mathbf{l}\\})$.

We then show (the contraposition of) that
$\mathcal{S}(P,\\{\mathbf{l}\\})\subseteq\operatorname{\mathcal{PC}}(\\{\mathbf{p}_{1}-\mathbf{l},\ldots,\mathbf{p}_{|P|}-\mathbf{l}\\};\mathbf{l})$.
Let $\mathbf{s}$ be a vector not in
$\operatorname{\mathcal{PC}}(\\{\mathbf{p}_{1}-\mathbf{l},\ldots,\mathbf{p}_{|P|}-\mathbf{l}\\};\mathbf{l})$.
By the Minkowski–Weyl theorem, there must be a half-space $\mathcal{H}$ that
has $\mathbf{l}$ on its boundary, contains
$\operatorname{\mathcal{PC}}(\\{\mathbf{p}_{1}-\mathbf{l},\ldots,\mathbf{p}_{|P|}-\mathbf{l}\\};\mathbf{l})$,
and does not include $\mathbf{s}$. Note that the boundary of $\mathcal{H}$
forms a supporting hyperplane. Letting $\mathbf{n}$ be an outward normal
vector to $\mathcal{H}$, we can express $\mathbf{s}$ as
$\mathbf{s}=\mathbf{h}+\lambda\mathbf{n}$, where $\lambda>0$ and $\mathbf{h}$
is a vector lying on the boundary of $\mathcal{H}$. By the definition of
$\mathcal{H}$ and $\mathbf{n}$, it holds that
$\langle-\mathbf{n},\mathbf{l}\rangle\leq\langle-\mathbf{n},\mathbf{p}_{i}\rangle$
for all $i\in[|P|]$; i.e., $-\mathbf{n}\in\mathcal{Q}(P,\\{\mathbf{l}\\})$.
Thinking of $-\mathbf{n}$ as a query vector, we obtain

$\displaystyle\langle-\mathbf{n},\mathbf{s}\rangle=\langle-\mathbf{n},\mathbf{h}\rangle+\lambda\cdot\langle-\mathbf{n},\mathbf{n}\rangle<\langle-\mathbf{n},\mathbf{h}\rangle=\langle-\mathbf{n},\mathbf{l}\rangle,$

where the last equality is because both $\mathbf{h}$ and $\mathbf{l}$ lie on
the boundary of $\mathcal{H}$, implying that
$\mathbf{s}\not\in\mathcal{S}(P,\\{\mathbf{l}\\})$. This completes the proof.
∎

###### Proof of Theorem A.9.

First, we show that $\mathcal{S}(P,L)$ contains
$\bigcap_{j\in[|L|]}\mathcal{S}(P,\\{\mathbf{l}_{j}\\})$. Observing that
$\mathcal{Q}(P,L)=\bigcap_{j\in[|L|]}\mathcal{Q}(P,\\{\mathbf{l}_{j}\\})$, we
derive the following:

$\displaystyle\bigcap_{j\in[|L|]}\mathcal{S}(P,\\{\mathbf{l}_{j}\\})$
$\displaystyle=\bigcap_{j\in[|L|]}\\{\mathbf{s}:\langle\mathbf{q},\mathbf{s}\rangle\geq\langle\mathbf{q},\mathbf{l}_{j}\rangle,\;\forall\mathbf{q}\in\mathcal{Q}(P,\\{\mathbf{l}_{j}\\})\\}$
$\displaystyle\subseteq\bigcap_{j\in[|L|]}\\{\mathbf{s}:\langle\mathbf{q},\mathbf{s}\rangle\geq\langle\mathbf{q},\mathbf{l}_{j}\rangle,\;\forall\mathbf{q}\in\mathcal{Q}(P,L)\\}$
$\displaystyle=\\{\mathbf{s}:\langle\mathbf{q},\mathbf{s}\rangle\geq\langle\mathbf{q},\mathbf{l}_{j}\rangle,\;\forall
j\in[|L|],\forall\mathbf{q}\in\mathcal{Q}(P,L)\\},$

which is equal to $\mathcal{S}(P,L)$. Now, let $\mathbf{s}$ be in the right-
hand side of Eq. 3; i.e., it holds that
$\mathbf{s}=\mathbf{s}^{\prime}+\sum_{i,j}\lambda_{i,j}(\mathbf{p}_{i}-\mathbf{l}_{j})$
for some
$\mathbf{s}^{\prime}\in\bigcap_{j\in[|L|]}\mathcal{S}(P,\\{\mathbf{l}_{j}\\})$
and $\lambda_{i,j}\geq 0$. For any $\mathbf{q}\in\mathcal{Q}(P,L)$, we have

$\displaystyle\langle\mathbf{q},\mathbf{s}\rangle=\langle\mathbf{q},\mathbf{s}^{\prime}\rangle+\sum_{i,j}\lambda_{i,j}\cdot\Bigl{(}\underbrace{\langle\mathbf{q},\mathbf{p}_{i}\rangle-\langle\mathbf{q},\mathbf{l}_{j}\rangle}_{\geq
0}\Bigr{)}\geq\langle\mathbf{q},\mathbf{s}^{\prime}\rangle\geq\max_{j\in[|L|]}\\{\langle\mathbf{q},\mathbf{l}_{j}\rangle\\},$

implying $\mathbf{s}\in\mathcal{S}(P,L)$, which concludes the proof. ∎

## References

  * (1)
  * Abdollahpouri et al. (2017) Himan Abdollahpouri, Robin Burke, and Bamshad Mobasher. 2017\.  Controlling popularity bias in learning-to-rank recommendation. In _ACM Conference on Recommender Systems_. 42–46.
  * Abdollahpouri et al. (2019) Himan Abdollahpouri, Robin Burke, and Bamshad Mobasher. 2019\.  Managing popularity bias in recommender systems with personalized re-ranking. In _International FLAIRS Conference_.
  * Adomavicius and Kwon (2009) Gediminas Adomavicius and YoungOk Kwon. 2009.  Toward more diverse recommendations: Item re-ranking methods for recommender systems. In _Workshop on Information Technologies and Systems_. Citeseer, 79–84.
  * Adomavicius and Kwon (2011) Gediminas Adomavicius and YoungOk Kwon. 2011.  Improving aggregate recommendation diversity using ranking-based techniques.  _IEEE Transactions on Knowledge and Data Engineering_ 24, 5 (2011), 896–911.
  * Adomavicius and Kwon (2014) Gediminas Adomavicius and YoungOk Kwon. 2014.  Optimization-based approaches for maximizing aggregate recommendation diversity.  _INFORMS Journal on Computing_ 26, 2 (2014), 351–369.
  * Atkinson (1970) Anthony B. Atkinson. 1970\.  On the measurement of inequality.  _Journal of Economic Theory_ 2, 3 (1970), 244–263.
  * Bayer et al. (2017) Immanuel Bayer, Xiangnan He, Bhargav Kanagal, and Steffen Rendle. 2017.  A generic coordinate descent framework for learning from implicit feedback. In _The World Wide Web Conference_. 1341–1350.
  * Bertin-Mahieux et al. (2011) Thierry Bertin-Mahieux, Daniel P. W. Ellis, Brian Whitman, and Paul Lamere. 2011.  The million song dataset. In _International Society for Music Information Retrieval Conference_. 591–596.
  * Boyd et al. (2011) Stephen Boyd, Neal Parikh, Eric Chu, Borja Peleato, and Jonathan Eckstein. 2011.  Distributed optimization and statistical learning via the alternating direction method of multipliers.  _Foundations and Trends® in Machine Learning_ 3, 1 (2011), 1–122.
  * Burke (2017) Robin Burke. 2017\.  Multisided fairness for recommendation.  _arXiv preprint arXiv:1707.00093_ (2017).
  * Celis et al. (2018) L. Elisa Celis, Damian Straszak, and Nisheeth K. Vishnoi. 2018\.  Ranking with fairness constraints. In _International Colloquium on Automata, Languages, and Programming_. 28:1–28:15.
  * Celma and Cano (2008) Òscar Celma and Pedro Cano. 2008.  From hits to niches? or how popular artists can bias music recommendation and discovery. In _Proceedings of the 2nd KDD Workshop on Large-Scale Recommender Systems and the Netflix Prize Competition_. 1–8.
  * Chen et al. (2020) Jiawei Chen, Hande Dong, Xiang Wang, Fuli Feng, Meng Wang, and Xiangnan He. 2020\.  Bias and debias in recommender system: A survey and future directions.  _arXiv preprint arXiv:2010.03240_ (2020).
  * Chen et al. (2018) Laming Chen, Guoxin Zhang, and Eric Zhou. 2018.  Fast greedy MAP inference for determinantal point process to improve recommendation diversity. In _Advances in Neural Information Processing Systems_. 5627–5638.
  * Chen et al. (2017) Laming Chen, Guoxin Zhang, and Hanning Zhou. 2017\.  Improving the diversity of top-N recommendation via determinantal point process. In _Large Scale Recommendation Systems Workshop_.
  * Ferrari Dacrema et al. (2019) Maurizio Ferrari Dacrema, Paolo Cremonesi, and Dietmar Jannach. 2019\.  Are we really making much progress? A worrying analysis of recent neural recommendation approaches. In _ACM Conference on Recommender Systems_. 101–109.
  * Han and Gillenwater (2020) Insu Han and Jennifer Gillenwater. 2020.  MAP inference for customized determinantal point processes via maximum inner product search. In _International Conference on Artificial Intelligence and Statistics_. 2797–2807.
  * Harper and Konstan (2015) F. Maxwell Harper and Joseph A. Konstan. 2015.  The MovieLens datasets: history and context.  _ACM Transactions on Interactive Intelligent Systems_ 5, 4 (2015), 19:1–19:19.
  * He et al. (2020) Xiangnan He, Kuan Deng, Xiang Wang, Yan Li, Yongdong Zhang, and Meng Wang. 2020\.  LightGCN: Simplifying and powering graph convolution network for recommendation. In _International ACM SIGIR Conference on Research and Development in Information Retrieval_. 639–648.
  * He et al. (2016) Xiangnan He, Hanwang Zhang, Min-Yen Kan, and Tat-Seng Chua. 2016.  Fast matrix factorization for online recommendation with implicit feedback. In _International ACM SIGIR Conference on Research and Development in Information Retrieval_. 549–558.
  * Herlocker et al. (2004) Jonathan L. Herlocker, Joseph A. Konstan, Loren G. Terveen, and John T. Riedl. 2004.  Evaluating collaborative filtering recommender systems.  _ACM Transactions on Information Systems_ 22, 1 (2004), 5–53.
  * Hirata et al. (2022) Kohei Hirata, Daichi Amagata, Sumio Fujita, and Takahiro Hara. 2022.  Solving diversity-aware maximum inner product search efficiently and effectively. In _ACM Conference on Recommender Systems_. 198–207.
  * Ho and Zimmerman (2006) Chungwu Ho and Seth Zimmerman. 2006.  On the number of regions in an $m$-dimensional space cut by $n$ hyperplanes.  _Australian Mathematical Society Gazette_ 33, 4 (2006), 260–264.
  * Hu et al. (2008) Yifan Hu, Yehuda Koren, and Chris Volinsky. 2008.  Collaborative filtering for implicit feedback datasets. In _IEEE International Conference on Data Mining_. 263–272.
  * Jegou et al. (2010) Herve Jegou, Matthijs Douze, and Cordelia Schmid. 2010\.  Product quantization for nearest neighbor search.  _IEEE Transactions on Pattern Analysis and Machine Intelligence_ 33, 1 (2010), 117–128.
  * Jeunen and Goethals (2021) Olivier Jeunen and Bart Goethals. 2021.  Top-K contextual bandits with equity of exposure. In _ACM Conference on Recommender Systems_. 310–320.
  * Korda et al. (2016) Nathan Korda, Balazs Szorenyi, and Shuai Li. 2016\.  Distributed clustering of linear bandits in peer to peer networks. In _International Conference on Machine Learning_. PMLR, 1301–1309.
  * Koren et al. (2009) Yehuda Koren, Robert Bell, and Chris Volinsky. 2009\.  Matrix factorization techniques for recommender systems.  _Computer_ 42, 8 (2009), 30–37.
  * Koren et al. (2022) Yehuda Koren, Rendle Steffen, and Robert M. Bell. 2022\.  Advances in collaborative filtering.  In _Recommender Systems Handbook_. Springer, 91–142.
  * Li (2011) Shengqiao Li. 2011\.  Concise formulas for the area and volume of a hyperspherical cap.  _Asian Journal of Mathematics & Statistics_ 4, 1 (2011), 66–70.
  * Li et al. (2016) Shuai Li, Alexandros Karatzoglou, and Claudio Gentile. 2016\.  Collaborative filtering bandits. In _International ACM SIGIR Conference on Research and Development in Information Retrieval_. 539–548.
  * Liang et al. (2018) Dawen Liang, Rahul G. Krishnan, Matthew D. Hoffman, and Tony Jebara. 2018.  Variational autoencoders for collaborative filtering. In _The World Wide Web Conference_. 689–698.
  * Mahadik et al. (2020) Kanak Mahadik, Qingyun Wu, Shuai Li, and Amit Sabne. 2020\.  Fast distributed bandits for online recommendation systems. In _ACM International Conference on Supercomputing_. 1–13.
  * Malkov and Yashunin (2018) Yu A. Malkov and Dmitry A. Yashunin. 2018.  Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs.  _IEEE Transactions on Pattern Analysis and Machine Intelligence_ 42, 4 (2018), 824–836.
  * Massa and Avesani (2007) Paolo Massa and Paolo Avesani. 2007.  Trust-aware recommender systems. In _ACM Conference on Recommender Systems_. 17–24.
  * McMullen (1970) Peter McMullen. 1970\.  The maximum numbers of faces of a convex polytope.  _Mathematika_ 17, 2 (1970), 179–184.
  * Mehta et al. (2021) Harsh Mehta, Steffen Rendle, Walid Krichene, and Li Zhang. 2021\.  ALX: Large scale matrix factorization on TPUs.  _arXiv preprint arXiv:2112.02194_ (2021).
  * Memarrast et al. (2021) Omid Memarrast, Ashkan Rezaei, Rizal Fathony, and Brian Ziebart. 2021.  Fairness for robust learning to rank.  _arXiv preprint arXiv:2112.06288_ (2021).
  * Meng et al. (2016) Xiangrui Meng, Joseph K. Bradley, Burak Yavuz, Evan R. Sparks, Shivaram Venkataraman, Davies Liu, Jeremy Freeman, D.B. Tsai, Manish Amde, Sean Owen, Doris Xin, Reynold Xin, Michael J. Franklin, Reza Zadeh, Matei Zaharia, and Ameet Talwalkar. 2016\.  MLlib: Machine learning in Apache Spark.  _The Journal of Machine Learning Research_ 17, 1 (2016), 1235–1241.
  * Minkowski (1896) Hermann Minkowski. 1896\.  _Geometrie der zahlen_.  Teubner, Leipzig.
  * Motzkin (1957) Theodore S. Motzkin. 1957\.  Comonotone curves and polyhedra.  _Bull. Amer. Math. Soc._ 63 (1957), 35.
  * Ning and Karypis (2011) Xia Ning and George Karypis. 2011.  SLIM: Sparse linear methods for top-n recommender systems. In _IEEE International Conference on Data Mining_. IEEE, 497–506.
  * Patil et al. (2021) Vishakha Patil, Ganesh Ghalme, Vineet Nair, and Y. Narahari. 2021\.  Achieving fairness in the stochastic multi-armed bandit problem.  _The Journal of Machine Learning Research_ 22 (2021), 174:1–174:31.
  * Patro et al. (2020) Gourab K Patro, Arpita Biswas, Niloy Ganguly, Krishna P Gummadi, and Abhijnan Chakraborty. 2020\.  FairRec: Two-sided fairness for personalized recommendations in two-sided platforms. In _The World Wide Web Conference_. 1194–1204.
  * Pilászy et al. (2010) István Pilászy, Dávid Zibriczky, and Domonkos Tikk. 2010.  Fast als-based matrix factorization for explicit and implicit feedback datasets. In _ACM Conference on Recommender Systems_. 71–78.
  * Rendle (2012) Steffen Rendle. 2012\.  Factorization machines with libFM.  _ACM Transactions on Intelligent Systems and Technology_ 3, 3 (2012), 1–22.
  * Rendle et al. (2020) Steffen Rendle, Walid Krichene, Li Zhang, and John Anderson. 2020.  Neural collaborative filtering vs. matrix factorization revisited. In _ACM Conference on Recommender Systems_. 240–248.
  * Rendle et al. (2021) Steffen Rendle, Walid Krichene, Li Zhang, and Yehuda Koren. 2021\.  iALS++: Speeding up matrix factorization with subspace optimization.  _arXiv preprint arXiv:2110.14044_ (2021).
  * Rendle et al. (2022) Steffen Rendle, Walid Krichene, Li Zhang, and Yehuda Koren. 2022\.  Revisiting the performance of ials on item recommendation benchmarks. In _ACM Conference on Recommender Systems_. 427–435.
  * Sachdeva et al. (2019) Noveen Sachdeva, Giuseppe Manco, Ettore Ritacco, and Vikram Pudi. 2019.  Sequential variational autoencoders for collaborative filtering. In _ACM International Conference on Web Search and Data Mining_. 600–608.
  * Shenbin et al. (2020) Ilya Shenbin, Anton Alekseev, Elena Tutubalina, Valentin Malykh, and Sergey I. Nikolenko. 2020\.  RecVAE: a new variational autoencoder for top-n recommendations with implicit feedback. In _ACM International Conference on Web Search and Data Mining_. 528–536.
  * Shrivastava and Li (2014) Anshumali Shrivastava and Ping Li. 2014.  Asymmetric LSH (ALSH) for sublinear time maximum inner product search (MIPS). In _Advances in Neural Information Processing Systems_. 2321–2329.
  * Singh and Joachims (2018) Ashudeep Singh and Thorsten Joachims. 2018.  Fairness of exposure in rankings. In _ACM SIGKDD International Conference on Knowledge Discovery & Data Mining_. 2219–2228.
  * Steck et al. (2021) Harald Steck, Linas Baltrunas, Ehtsham Elahi, Dawen Liang, Yves Raimond, and Justin Basilico. 2021\.  Deep learning for recommender systems: A Netflix case study.  _AI Magazine_ 42, 3 (2021), 7–18.
  * Steck et al. (2020) Harald Steck, Maria Dimakopoulou, Nickolai Riabov, and Tony Jebara. 2020.  ADMM SLIM: Sparse recommendations for many users. In _ACM International Conference on Web Search and Data Mining_. 555–563.
  * Steck and Liang (2021) Harald Steck and Dawen Liang. 2021.  Negative Interactions for Improved Collaborative Filtering: Don’t go Deeper, go Higher. In _ACM Conference on Recommender Systems_. 34–43.
  * Swaminathan and Joachims (2015) Adith Swaminathan and Thorsten Joachims. 2015.  Batch learning from logged bandit feedback through counterfactual risk minimization.  _The Journal of Machine Learning Research_ 16, 1 (2015), 1731–1755.
  * Temme (1996) Nico M. Temme. 1996\.  _Special functions: An introduction to the classical functions of mathematical physics_.  John Wiley & Sons.
  * Togashi and Abe (2022) Riku Togashi and Kenshi Abe. 2022.  Fair matrix factorisation for large-scale recommender systems.  _arXiv preprint arXiv:2209.04394_ (2022).
  * Wang et al. (2021) Lequn Wang, Yiwei Bai, Wen Sun, and Thorsten Joachims. 2021\.  Fairness of exposure in stochastic bandits. In _International Conference on Machine Learning_. 10686–10696.
  * Warlop et al. (2019) Romain Warlop, Jérémie Mary, and Mike Gartrell. 2019.  Tensorized determinantal point processes for recommendation. In _ACM SIGKDD International Conference on Knowledge Discovery & Data Mining_. 1605–1615.
  * Weyl (1935) Hermann Weyl. 1935\.  Elementare theorie der konvexen polyeder.  _Commentarii Mathematici Helvetici_ 7 (1935), 290–306.
  * Wilhelm et al. (2018) Mark Wilhelm, Ajith Ramanathan, Alexander Bonomo, Sagar Jain, Ed H. Chi, and Jennifer Gillenwater. 2018.  Practical diversified recommendations on youtube with determinantal point processes. In _ACM International Conference on Information & Knowledge Management_. 2165–2173.
  * Winder (1966) Robert O. Winder. 1966\.  Partitions of $N$-space by hyperplanes.  _SIAM J. Appl. Math._ 14, 4 (1966), 811–818.
  * Xie et al. (2021) Zhe Xie, Chengxuan Liu, Yichi Zhang, Hongtao Lu, Dong Wang, and Yue Ding. 2021\.  Adversarial and contrastive variational autoencoder for sequential recommendation. In _The World Wide Web Conference_. 449–459.
  * Yang et al. (2020) Ji Yang, Xinyang Yi, Derek Zhiyuan Cheng, Lichan Hong, Yang Li, Simon Xiaoming Wang, Taibai Xu, and Ed H. Chi. 2020\.  Mixed negative sampling for learning two-tower neural networks in recommendations. In _The World Wide Web Conference_. 441–447.
  * Yao et al. (2016) Jin-ge Yao, Feifan Fan, Wayne Xin Zhao, Xiaojun Wan, Edward Y. Chang, and Jianguo Xiao. 2016\.  Tweet timeline generation with determinantal point processes. In _AAAI Conference on Artificial Intelligence_. 3080–3086.
  * Yin et al. (2012) Hongzhi Yin, Bin Cui, Jing Li, Junjie Yao, and Chen Chen. 2012.  Challenging the long tail recommendation.  _Proceedings of the VLDB Endowment_ 5, 9 (2012), 896–907.
  * Yu et al. (2014) Zhi-Qin Yu, Xing-Jian Shi, Ling Yan, and Wu-Jun Li. 2014\.  Distributed stochastic ADMM for matrix factorization. In _ACM International Conference on Information & Knowledge Management_. 1259–1268.
  * Zhou et al. (2008) Yunhong Zhou, Dennis Wilkinson, Robert Schreiber, and Rong Pan. 2008.  Large-scale parallel collaborative filtering for the netflix prize. In _International Conference on Algorithmic Applications in Management_. 337–348.


[aff1]Stony Brook University [aff2]University of California, Los Angeles
[aff3] Lawrence Berkeley National Laboratory<EMAIL_ADDRESS>
# Analytical Solution to Electron Beam Envelope Evolution in a Plasma
Wakefield

Jiayang Yancor1  Audrey Farrell  Lígia Diana Amorim  Navid Vafaei-Najafabadi

###### Abstract

Beam-induced ionization injection (B-III) is currently being explored as a
method for injecting an electron beam with a controlled density profile into a
plasma wakefield accelerator (PWFA). This process is initiated by the fields
of an unmatched drive beam where the slice envelope reaches its minimum value,
the “pinch”. To control the injected beam’s qualities, it is crucial to study
the beam-slice envelope oscillations, especially size and the location of the
pinch. In this proceeding, an ansatz based on the harmonic motion is proposed
to find the analytical solution to beam-slice envelope evolution in the
nonlinear regime. The size of the pinch is then found through the application
of energy conservation in the transverse direction. The resulting analytical
expressions are shown to be in good agreement with numerical solutions.

##  1 INTRODUCTION

Beam-driven plasma wakefield accelerators (PWFA) use electron drivers to
create plasma cavities where the acceleration gradient can reach tens of GeV/m
Blumenfeld  _et al._ (2007). In the so-called nonlinear regime Lu  _et al._
(2006), the plasma electrons are repelled from the axis by the drive electron
beam due to the Coulomb force, while heavier plasma ions are left behind the
driver. The stationary ions provide focusing forces that attract plasma
electrons back to the axis, forming a bubble-like structure. A trailing
electron beam located at the back of the bubble gains energy from the
generated electromagnetic field, the wakefield. The wakefield provides a
transverse focusing force in which the electrons execute an oscillatory
motion, called the betatron oscillation, around the axis.

One method that can be used to form and inject the trailing beam inside the
ion cavity is called Beam-Induced Ionization Injection (B-III) Amorim  _et
al._ (2019), where the plasma is comprised of a low-ionization-threshold (LIT)
gas (high concentration) plus a high-ionization-threshold (HIT) impurity
component (low concentration) and the driver is unmatched with the plasma.
During the wake excitation, as the initial drive beam space charge field does
not go above the high ionization threshold, only the LIT gas is ionized to
form the wake structure. Then because of the betatron oscillation, the
envelope of each beam slice oscillates in time, and so does the beam field. As
the transverse size of the beam slice reduces to its minimum (pinch), the beam
field increases and exceeds the high ionization threshold. As a result, the
HIT impurity can be ionized and becomes the source for the injected trailing
beam.

To control the ionization and injection process, which is initiated around the
pinch, it is required to know the evolution function of beam slice envelope
along the propagation direction as well as the size of the pinch. In this
proceeding, an ansatz is proposed to find the analytical solution to beam-
slice envelope oscillation in the nonlinear regime. This ansatz is based on
the application of energy conservation in the transverse direction. The
solution is first developed for the case of an electron beam with constant
energy and is then generalized to the case of an accelerating/decelerating
beam. The analytical results are shown to be in good agreement with numerical
solutions.

It is important to note that while this envelope oscillation calculation is
intended here for applications in the case of a PWFA, the results are general
and can apply to the case of a trailing electron beam in a laser driven
wakefield accelerator (LWFA) as well.

##  2 EVOLUTION OF BEAM-SLICE ENVELOPE

Evolution of a beam-slice envelope $\sigma_{r}(z)$ undergoing betatron
oscillation is expressed as a function of propagation distance $z$ by Clayton
_et al._ (2002)

$\frac{d^{2}\sigma_{r}(z)}{dz^{2}}+k_{\beta}^{2}\sigma_{r}(z)-\frac{\epsilon_{N}^{2}}{\gamma^{2}\sigma_{r}^{3}(z)}=0,$
(1)

where $k_{\beta}=\frac{\omega_{p}}{c}\sqrt{\frac{1}{2\gamma(z)}}$ is the
betatron frequency, $\omega_{p}=\sqrt{\frac{e^{2}n_{0}}{m_{e}\epsilon_{0}}}$
is plasma frequency, $\gamma$ is the Lorentz gamma factor, $n_{0}$ is plasma
density, $e$, $m_{e}$ are electron charge and mass respectively, and
$\epsilon_{N}$ is the normalized beam emittance. In the equation,
$F_{+}=k_{\beta}^{2}\sigma_{r}(z)$ is the focusing force of the wakefield, and
$F_{-}=-\frac{\epsilon_{N}^{2}}{\gamma^{2}\sigma_{r}^{3}(z)}$ works as an
effective defocusing force. It is well known that the solution to Eq. (1) is a
betatron oscillation with the wavenumber $k_{\beta}$ and a minimum size that
is called the “pinch”. As the exact solution of Eq. (1) is too complicated to
be solved, an ansatz is proposed to describe the betatron motion as a harmonic
oscillation with a minimum size (pinch) of $\Delta\sigma_{r}$.

$\sigma_{r}(z)=|(\sigma_{r_{0}}-\Delta\sigma_{r})\cos(k_{\beta}z)|+\Delta\sigma_{r}.$
(2)

Here, $\sigma_{r_{0}}$ is the initial transverse beam size, which is known.
The consequence of this ansatz is that $F_{-}$ can be written in terms of
$\Delta\sigma_{r}$ in the same frequency as $F_{+}$ is written in terms of
$\sigma_{r}$.

The next step is to find the value of the pinch size, $\Delta\sigma_{r}$,
which is determined by balancing the energy that would be associated with each
force term in an oscillation period.
Consider a half cycle,

$W_{+}=\int^{\sigma_{r_{0}}}_{\Delta\sigma_{r}}F_{+}(\sigma_{r})d\sigma_{r}={\omega_{p}^{2}\over
4{c^{2}\gamma}}\left(\sigma_{r_{0}}^{2}-\Delta\sigma_{r}^{2}\right),$ (3)

$W_{-}=\int^{\sigma_{r_{0}}}_{\Delta\sigma_{r}}F_{-}(\sigma_{r})d\sigma_{r}=\frac{\epsilon_{N}^{2}}{2\gamma^{2}}\left({1\over\sigma_{r_{0}}^{2}}-{1\over\Delta\sigma_{r}^{2}}\right).$
(4)

The energy is conserved in the half cycle, so $\Delta\sigma_{r}$ can be found
from $W_{+}+W_{-}=0$:

$\Delta\sigma_{r}^{2}={1\over
2}\left[\sigma_{r_{0}}^{2}+\frac{2\epsilon_{N}^{2}c^{2}}{\omega_{p}^{2}\gamma\sigma_{r_{0}}}\pm\sqrt{\left(\sigma_{r_{0}}^{2}+\frac{2\epsilon_{N}^{2}c^{2}}{\omega_{p}^{2}\gamma\sigma_{r_{0}}}\right)^{2}-4\frac{2\epsilon_{N}^{2}c^{2}}{\omega_{p}^{2}\gamma}}\right]=\frac{2\epsilon_{N}^{2}c^{2}}{\omega_{p}^{2}\gamma\sigma_{r_{0}}^{2}},$
(5)
$\Delta\sigma_{r}=\sqrt{{2\over\gamma}}\frac{\epsilon_{N}c}{\omega_{p}\sigma_{r_{0}}}.$
(6)

Figure 1: Forces in Eq. (1), where $\gamma=19570.5$ (10 GeV),
$k_{p}\sigma_{r_{0}}=0.5$, and $k_{p}\epsilon_{N}=1$.

A conceptually simple understanding of $\Delta\sigma_{r}$ can emerge by
studying the behavior of the total force $F_{+}+F_{-}$ in the limiting cases
of $\sigma_{r}$. From their mathematical expressions, we expect the total
force $F_{+}+F_{-}$ to be dominated by $F_{+}$ at a large $\sigma_{r}$, where
$-\frac{1}{\gamma^{2}\sigma_{r}^{3}(z)}\rightarrow 0$. On the other hand,
$F_{-}$ is expected to dominate when $\sigma_{r}$ is small and
$\sigma_{r}\ll\left(\frac{1}{\gamma}\right)^{1/4}$. The plot of the total
force as well as $F_{+}$ and $F_{-}$ as functions of transverse position are
shown in Fig. 1 using normalized units. It is clearly seen here that the total
force (in green) follows $F_{+}$ (in blue) when $\sigma_{r}$ is large (i.e.,
$\sigma_{r}\geq 0.15$ in the figure); on the contrary, it follows $F_{-}$ (in
orange) when $\sigma_{r}$ is small (i.e., $\sigma_{r}\leq 0.05$). The
equilibrium position $\sigma_{r_{eq}}$, defined as the position where the
forces balance, $F_{+}=F_{-}$, is given by the plasma matched spot size

$\sigma_{r_{eq}}=\left({\epsilon_{N}\over\gamma k_{\beta}}\right)^{1\over 2}.$
(7)

Because different forces dominate the interaction on either sides of
$\sigma_{r_{eq}}$, a simplified physical model for the betatron oscillation
may be prescribed as follows: only $F_{+}$ acts on the electrons when
$\sigma_{r_{0}}>\sigma_{r}>\sigma_{r_{eq}}$ and only $F_{-}$ acts on the
electrons for $\Delta\sigma_{r}<\sigma_{r}<\sigma_{r_{eq}}$, with
$\sigma_{r_{eq}}$ considered as the transition point. This model allows for
the work done by $F_{+}$ to be found independently of the size of the pinch,
$\Delta\sigma_{r}$,

$W_{+}^{\prime}=\int_{\sigma_{r_{eq}}}^{\sigma_{r_{0}}}F_{+}(\sigma_{r})d\sigma_{r}={\omega_{p}^{2}\over{c^{2}\gamma}}\left({\sigma_{r_{0}}^{2}\over
2}-\sqrt{\epsilon_{N}\over{2\gamma}}\right).$ (8)

$\Delta\sigma_{r}$ then can be simply interpreted as the distance through
which $F_{-}$ needs to be exerted to cancel the energy gained by $F_{+}$.
Applying the same conservation of energy criteria as discussed above,
$W_{+}^{\prime}+W_{-}^{\prime}=0$, with $W_{+}^{\prime}$ defined in Eq. (8)
and $W_{-}^{\prime}$ given by

$W_{-}^{\prime}=\int^{\sigma_{r_{eq}}}_{\Delta\sigma_{r}}F_{-}(\sigma_{r})d\sigma_{r}=-\frac{\epsilon_{N}^{2}}{4\gamma^{2}}\left({\sqrt{2\gamma\over\epsilon_{N}}}-{2\over\Delta\sigma_{r}^{2}}\right),$
(9)

leads to the same expression for $\Delta\sigma_{r}$ as Eq. (6), which was
obtained using the exact expressions.

Figure 2: Comparison between numerical solution and analytical ansatz, where
$k_{p}\sigma_{r_{0}}=0.5$, $k_{p}\epsilon_{N}=1$, $\gamma=19570.5$ (10 GeV),
$\Delta\sigma_{r}=0.0202183$ from Eq. (6), numerical pinch size is 0.0202185.
The relative difference is 0.01%. The absolute difference between both
solutions is in the order of $10^{-7}$.

Mathematically, $\Delta\sigma_{r}$ represents the transverse offset between
the minimum value of $\sigma_{r}(z)$ and z axis, which is the size of the
pinch.

The analytical ansatz in Eq. (2) is compared with the numerical solution of
Eq. (1) shown in Fig. 2 for a sample set of parameters described in the figure
caption. Based on Eq. (6), $\Delta\sigma_{r}=0.0202183$, numerical pinch size
is 0.0202185. The relative difference is $0.01\%\ll 1\%$. The absolute
difference between the numerical and analytical solutions was checked for
multiple cases where $10<\gamma<10000$, and the average difference was found
to be on the order of $10^{-7}$. This indicates that the expression in Eq. (6)
is also valid for a low energy beam.

##  3 THE IMPACT OF ENERGY VARIATION

Taking acceleration into account, the betatron envelope equation is modified
to Rosenzweig (2003); Ferrario (2016),

$\frac{d^{2}\sigma_{r}(z)}{dz^{2}}+\frac{\gamma(z)^{\prime}}{\gamma(z)}\sigma_{r}^{\prime}(z)+k_{\beta}^{2}\sigma_{r}(z)-\frac{\epsilon_{N}^{2}}{\gamma(z)^{2}\sigma_{r}^{3}(z)}=0.$
(10)

Here, typically $\gamma(z)=\gamma_{0}+E_{z}z$ in the normalized unit, and
$E_{z}$ is the longitudinal electric field, which is usually a constant (in
$z$ for each beam slice), because the beam velocity and the phase velocity of
the wake are both nearly $c$. The impact of energy gain/loss is modelled using
the approach of adiabatic damping. Based on the simplified physical model
developed in the previous section, for $\sigma_{r}>\sigma_{r_{eq}}$, only the
impact of $F_{+}$ can be considered. The solution to Eq. (10) without the
$F_{-}$ term consists of damped harmonic oscillations, where the oscillation
amplitude is modified by a factor of
$\left(\frac{\gamma_{0}}{\gamma(z)}\right)^{1/4}$, i.e.
$\sigma_{r_{0}}\rightarrow\sigma_{r_{0}}\left(\frac{\gamma_{0}}{\gamma(z)}\right)^{1/4}$
Thomas (2010). Similar modifications for the amplitude and the phase of the
ansatz [Eq. (2)] result in the following expression, where the effect of
$F_{-}$ in Eq. (10) is once again taken into account using the parameter
$\Delta\sigma_{r}$:

$\sigma_{r}(z)=\left|\left[\sigma_{r_{0}}\left(\frac{\gamma_{0}}{\gamma(z)}\right)^{1/4}-\Delta\sigma_{r}(z)\right]\cos\left(\int
k_{\beta}(z)dz\right)\right|+\Delta\sigma_{r}(z).$ (11)

Here $\Delta\sigma_{r}(z)$ becomes a function of $z$. The modification of
$\Delta\sigma_{r}$ is likewise carried out by
$\sigma_{r_{0}}\rightarrow\sigma_{r_{0}}\left(\frac{\gamma_{0}}{\gamma(z)}\right)^{1/4}$,
making $\Delta\sigma_{r}(z)$ vary from one cycle to the next as $\gamma(z)$
changes,

$\Delta\sigma_{r}(z)=\sqrt{{2\over\gamma(z)}}\frac{\epsilon_{N}c}{\omega_{p}\sigma_{r_{0}}\left(\frac{\gamma_{0}}{\gamma(z)}\right)^{1/4}}=\left({4\over\gamma(z)\gamma_{0}}\right)^{1/4}\frac{\epsilon_{N}c}{\omega_{p}\sigma_{r_{0}}}.$
(12)

The modified analytical solution given by Eq. (11) is compared with the
numerical solution for Eq. (10) in Fig. 3. The initial energy of the drive
beam is 10 GeV and the deceleration field is -5 in the normalized units,
resulting in $\gamma(z)=\gamma_{0}-5z$. This deceleration field is chosen
artificially so that the trend is more clear. The analytical solution closely
tracks the numerical solution, and strong agreement is observed between the
two in the description of the amplitude, frequency and the pinch size.

Figure 3: Comparison between numerical solution for Eq. (11) (blue) and
analytical ansatz (orange) with acceleration, where $\gamma_{0}=19570.5$ (10
GeV), $\gamma(z)=\gamma_{0}-5z$, $k_{p}\sigma_{r_{0}}=0.5$, and
$k_{p}\epsilon_{N}=1$. The analytical ansatz is calculated based on Eq. (12).

##  4 CONCLUSION

In conclusion, an analytical solution for the betatron envelope oscillation
was developed based on an ansatz that the solution consists of a bound
harmonic oscillation. The minimum transverse size of the envelope, called the
pinch, was calculated using an energy conservation argument between the two
force terms in the envelope oscillation. The variation of particle energy was
taken into account using the adiabatic damping of the betatron envelope model.
These analytical solutions show excellent agreement with the numerical
solutions to the envelope equations. The general solution
$\sigma_{r}(z)=\left|\left[\sigma_{r_{0}}\left(\frac{\gamma(z)}{\gamma_{0}}\right)^{1/4}-\Delta\sigma_{r}(z)\right]\cos\left(\int
k_{\beta}(z)dz\right)\right|+\Delta\sigma_{r}(z)$, where
$\Delta\sigma_{r}(z)=\sqrt{{2\over\gamma(z)}}\frac{\epsilon_{N}c}{\omega_{p}\sigma_{r_{0}}(\frac{\gamma_{0}}{\gamma(z)})^{1/4}}$,
gives us a valuable tool for accurately predicting the size and the location
of the pinch (along $z$), which in turn allows for the calculation of the
position and the magnitude of the maximum radial electric field. This
information is invaluable for the B-III method as it will enable the precise
positioning of the impurity elements. Alternatively, in methods that attempt
to avoid additional ionization of the impurity, it will give an insight into
the position where the presence of the impurity should be avoided. The size of
the pinch will determine the size of the ionization region, which can be used
in the future to calculate the quality of the generated electron beam in
B-III.

##  5 ACKNOWLEDGMENTS

We acknowledge the support by U.S. Department of Energy, Office of High Energy
Physics (HEP) program under Award No. DE-SC-0014043 and resources of NERSC
facility, operated under Contract No. DE-AC02-5CH11231.

## References

  * Blumenfeld  _et al._ (2007) I. Blumenfeld, C. E. Clayton, F. Decker, M. Hogan, C. Huang, R. Ischebeck, R. Iverson, C. Joshi, T. Katsouleas, N. Kirby, W. Lu, K. A. Marsh, W. B. Mori, P. Muggli, E. Oz, R. H. Siemann, D. Walz, and M. Zhou, Nature 445, p. 741 (2007).
  * Lu  _et al._ (2006) W. Lu, C. Huang, M. Zhou, W. B. Mori, and T. Katsouleas, Phys. Rev. Letters 96, p. 165002 (2006).
  * Amorim  _et al._ (2019) L. D. Amorim, N. Vafaei-Najafabadi, C. Emma, C. I. Clarke, S. Z. Green, D. Storey, G. White, B. O’Shea, M. J. Hogan, V. Yakimenko, M. Litos, G. Raj, O. Kononenko, P. S. M. Claveria, S. Corde, S. Gessner, X. Xu, K. Marsh, C. E. Clayton, C. Joshi, W. B. Mori, and E. Adli, Phys. Rev. Accel. Beams 22, p. 111303 (2019).
  * Clayton  _et al._ (2002) C. E. Clayton, B. E. Blue, E. S. Dodd, C. Joshi, K. A. Marsh, W. B. Mori, S. Wang, P. Catravas, S. Chattopadhyay, E. Esarey, W. P. Leemans, R. Assmann, F. J. Decker, M. J. Hogan, R. Iverson, P. Raimondi, R. H. Siemann, D. Walz, T. Katsouleas, S. Lee, and P. Muggli, Phys. Rev. Lett. 88, p. 154801 (2002).
  * Rosenzweig (2003) J. B. Rosenzweig, “Collective descriptions of beam distributions,” in  _Fundamentals of beam physics_ (Oxford University Press, New York, 2003) , pp. 125–126.
  * Ferrario (2016) M. Ferrario, “Injection, Extraction and Matching,” in  _CAS - CERN Accelerator School: Plasma Wake Acceleration_ (CERN, Geneva, 2016) , pp. 159–179, arXiv:1705.10564 [physics.acc-ph] .
  * Thomas (2010) A. G. R. Thomas, Phys. of Plasmas 17, p. 056708 (2010).