# The Bifurcation Coalescence Problem for Feedforward Coalescence Networks

Manuela Aguiar  Manuela Aguiar, Faculdade de Economia, Centro de Matemática,
Universidade do Porto, Rua Dr Roberto Frias, 4200-464 Porto, Portugal.
<EMAIL_ADDRESS>and  Pedro Soares  Pedro Soares, Instituto Superior de
Economia e Gestão, Universidade de Lisboa, Rua do Quelhas,
n${}^{\underline{o}}$ 6, 1200-781 Lisboa, Portugal<EMAIL_ADDRESS>
###### Abstract.

Consider two networks and combine them through the coalescence operation to
get a larger network. Is it possible to study the steady-state bifurcations of
the coalescence network by studying the steady-state bifurcations of the
component networks? We conclude that this is not possible for general
coalescence networks. We show, however, that in the case of feedforward
coalescence networks this is possible and we cover the simplest cases. In
particular, we prove how the growth rate of the bifurcation branches in the
feedforward coalescence network depends on the connections from one network to
the other.

###### Contents

  1. 1 Motivation
  2. 2 Definitions and preliminary results

##  1\. Motivation

In general, real-world networks are large, which makes the study of their
dynamical properties a difficult task. An interesting methodology would be to
be able to divide a network into smaller subnetworks, study their dynamical
properties separately and then draw conclusions about the dynamics of the
large network. This, in analogy, for example, with what is done in the
analysis of electronic circuits.

Network motifs are small networks that appear recurrently as components of
large networks and that can be considered as their building-block components.
Since it is easier to analyze motif dynamics, it is useful to be able to
relate the dynamical properties of a large network with those of its motif
components.

In this work, among the binary operations that can be used to combine small
networks in order to get larger ones, we choose to consider the coalescence
operation. Roughtly speaking, a network $N$ is the coalescence of two networks
$N_{1}$ and $N_{2}$, which we denote by $N_{1}\circ N_{2}$, if $N$ can be
obtained by identifying (merging) one cell of $N_{1}$ with one cell of
$N_{2}$, where the coalescence cell inherits the input and output edges of
those two merging cells. We consider networks where the cells are all of the
same type, there is only one type of edge and the edges can have associated
weights.

We are interested in analyzing what conclusions can be drawn for steady-state
bifurcations of the coalescence networks by studying the corresponding steady-
state bifurcations in the component networks. Given a codimension-one steady-
state bifurcation problem in a coalescence network $N=N_{1}\circ N_{2}$ we ask
whether the bifurcation condition for $N$ is necessarily a bifurcation
condition for at least one of the networks $N_{1}$ or $N_{2}$. If the answer
is positive, the next question we ask is to what extent it is possible to
predict the bifurcation branches for $N$ having knowledge of the bifurcation
branches for $N_{1}$ and/or $N_{2}$. We call this the bifurcation coalescence
problem.

We conclude that for most coalescence networks the bifurcation coalescence
problem has a negative answer. The first question fails, the bifurcation
conditions in an $N_{1}\circ N_{2}$-admissible system does not need to follow
from a bifurcation condition in $N_{1}$ or $N_{2}$-admissible systems. Even
when a coalescent network shares a bifurcation condition with the component
networks, we observe that, except for some specific cases, the bifurcation
branches in the coalescence network cannot, in general, be obtained from the
bifurcation branches in the component networks. However, the bifurcation
coalescence problem has some positive answers if the coalescence network has a
feedforward structure, that is, is a Feedforward Coalescence Network (FFCN) –
a network $N_{1}\circ N_{2}$ such that the coalescence cell in $N_{2}$ has no
inputs from the other cells in $N_{2}$ and, thus, $N_{1}\circ N_{2}$ has a
feedforward structure where the first layer contains the cells in $N_{1}$ and
the second layer the cells in $N_{2}$ excluding the coalescence cell.

Restricting the bifurcation coalescence problem to FFCNs and considering
diffusive admissible systems, we first show that the bifurcation conditions
for a FFCN $N=N_{1}\circ N_{2}$ are the union of the bifurcation conditions
for the networks $N_{1}$ and $N_{2}$. We then study three different cases:
(1) If the bifurcation occurs exactly in one of the component networks $N_{1}$
or $N_{2}$, then each bifurcation branch in the coalescence network is given
by an unique extension of a bifurcation branch in the component network where
the bifurcation occurs, Proposition LABEL:Prop:bif_cond_one.
(2) When the bifurcation occurs in both component networks, we consider an
explicit condition on the couplings between the merging cell and the other
cells in $N_{2}$ for nilpotent bifurcations. This coupling condition can be
formulated as the couplings from the merging cell to the other cells in
$N_{2}$ being a linear combination of the couplings between the other cells in
$N_{2}$. When the bifurcation condition is met simultaneously in both
networks, and it is simple in $N_{2}$, if the above coupling condition does
not hold, then each bifurcation branch in $N_{1}$ gives rises to two
bifurcation branches in the coalescence network (Proposition
LABEL:prop:extbifbra). Moreover, these bifurcation branches have a growth rate
equal to $\sqrt{|\lambda|}$. This coincides with previous study on the
bifurcations in feedforward networks where the amplified growth-rate
bifurcation branches are studied, Soares [S18].
(3) Finally, if the above coupling condition does hold, then each bifurcation
branch in $N_{1}$ still extends to two bifurcation branches in the coalescence
network (Proposition LABEL:prop:extbif2). However, in this case, the
bifurcation branches do not show the amplified growth-rate. Thus the amplified
growth-rate can be explained by the relation between the couplings between the
merging cell with the other cells in $N_{2}$ and the couplings between the
other cells in $N_{2}$.

The results mentioned above include non-degenerated conditions, as usual in
bifurcation theory. These non-degenerated conditions explicitly depend on the
network structure and the bifurcation branch that we are extending. Fixing a
network, the non-degenerated condition is satisfied for generic admissible
system of that network or they fail for any admissible system of that network.
For each of our results, we present examples of networks where the non-
degenerated conditions generically hold and the previous results can be
applied. Moreover, we present examples of networks such that the non-
degenerated conditions do not hold and we illustrate how the methods
introduced here can be applied in those cases.

We revisit a network analyzed in [ADGL09], where the authors used a different
approach considering quotient networks instead of subnetworks. More
concretely, given a coupled cell network there are subspaces, defined by
equalities of cell coordinates, that are left invariant by all the coupled
systems that are admissible by that network and that are designated by the
synchrony subspaces of the network. The restriction of an admissible system to
a synchrony subspace is a coupled system that is admissible by a smaller
network, a quotient network. In [ADGL09], the question is, given a
codimension-one steady-state bifurcation problem in a network, if it is
possible to get all the bifurcation branches for that network by studying the
corresponding bifurcation problem in the restriction to its quotient networks
where the bifurcation condition is valid. The conclusion is that the answer is
negative, in general. One example, presented in [ADGL09], where the answer is
negative is the network represented in Figure LABEL:Fig:coal_3-cell_net6. This
network is a particular example of a Feedfoward Coalescence Network (FFCN).
Despite this network does not satisfy the non-degenerated condition, we
illustrate how the methods introduced here can be used to study the
bifurcation branches of that network.

The paper is organized as follows: Section 2 contains the definitions and
results on coupled cell networks and coupled admissible systems that are
needed here. In particular, it is presented the relation between the
linearization of the admissible systems at the origin and the (weighted)
adjacency matrix and Laplacian matrix of the network. In Section 3 we consider
FFCNs, first we prove that the eigenvalues of the Laplacian matrix $L_{N}$,
with $N=N_{1}\circ N_{2}$ a FFCN, are given by the union of the eigenvalues of
the Laplacian matrices $L_{N_{1}}$ and $L_{N_{2}}$ of the component networks
$N_{1}$ and $N_{2}$. Then, we study the bifurcation coalescence problem for
FFCNs by considering admissible systems that are diffusive. In Section 4, we
end with some final remarks.

##  2\. Definitions and preliminary results

We consider the coupled cell networks formalism of Golubitsky, Stewart and
collaborators [SGP03, GST05, GS06] and its extension to weighted networks in
Aguiar and Dias [AD18]. Here, we focus these formalisms to the case where the
networks have only one cell type and one edge type, uniform networks. A
(weighted) coupled cell network can be represented by a (weighted) directed
graph, where the cells are placed at vertices (nodes) and the couplings are
depicted by directed arrows (edges).

######  Definition 2.1.

A (uniform coupled cell) network $N$ consists of a finite nonempty set $C$ of
nodes or cells and a finite nonempty subset $E=\\{(i,j):\ i,j\in C\\}\subseteq
C\times C$ of edges or arrows, where each pair $(i,j)$ represents an edge from
cell $i$ to cell $j$. And we write $N=(C,E)$. In a weighted (uniform coupled
cell) network, each edge $(i,j)$ has associated a weight
$w_{ij}\in\mbox{$\mathbf{R}$}$. ∎

A network is said connected if the associated graph is connected – there is an
undirected path between any two vertices (cells). From now on, when we refer
to a network we mean a connected network.

The topology of an $n$-cell weighted network $N$ can be given by an $n\times
n$ (weighted) adjacency matrix, $W_{N}=[w_{ij}]_{1\leq i,j\leq n}$, where
$w_{ij}$ is the weight of the edge from cell $j$ to cell $i$ or zero if there
is no such edge. Thus, we can simplify notation and use simply
$N=(C,E,W_{N})$.

The input valency of a cell $i\in C$, denoted by $v(i)$, is the sum of the
weights of the edges directed to the cell $i$, that is, $v(i)=\sum_{j\in
C}w_{ij}$. A network is said to be regular when all the network cells have the
same input valency, that is, $v(i)=v(j)$, for all $i,j\in C$. This equivalent
to the weighted matrix $W_{N}$ having constant row sum, say
$v_{W}=\sum_{k=1}^{n}w_{ik}$, for $i=1,\ldots,n$. In that case, we also say
that $W_{N}$ is regular of valency $v_{W}$.

Let $D_{N}$ be the $n\times n$ diagonal matrix with the principal diagonal
entries $d_{ii}$ given by the input valencies $v(i)$. The (weighted) Laplacian
matrix of $N$ is the matrix $L_{N}=D_{N}-W_{N}$. That is,
$L_{N}=[l_{ij}]_{n\times n}$, with:

$l_{ij}=\left\\{\begin{array}[]{l}-w_{ij}\mbox{ if }i\not=j;\\\
v(i)-w_{ii}\mbox{ if }i=j\,.\end{array}\right.$

Following [AR12], we define coalescence on coupled cell networks:


Metric learning aims at finding a suitable distance metric over the input space, to improve the performance of distance-based learning algorithms. In high-dimensional settings, metric learning can also play the role of dimensionality reduction, by imposing a low-rank restriction to the learnt metric. In this paper, instead of training a low-rank metric on high-dimensional data, we consider a randomly compressed version of the data, and train a full-rank metric there. We give theoretical guarantees on the error of distance-based metric learning, with respect to the random compression, which do not depend on the ambient dimension. Our bounds do not make any explicit assumptions, aside from i.i.d. data from a bounded support, and automatically tighten when benign geometrical structures are present. Experimental results on both synthetic and real data sets support our theoretical findings in high-dimensional settings.

§ INTRODUCTION

In clustering and classification, there have been numerous distance-based algorithms proposed. While the Euclidean metric is the “standard” notion of distance between numerical vectors, it does not always result in accurate learning. This can be e.g. due to the presence of many dependent features, or features with large ranges that dominate the distances [23]. Metric learning aims at lessening this caveat by linearly transforming the feature space in a way that properly weights all important features, and discards redundant ones. In its most common form, metric learning focuses on learning a Mahalanobis metric [29, 27, 6].

Metric learning algorithms can be divided into two types based on their purpose [23]. Distance-based metric learning aims at increasing the distances between instances of different classes (inter-class distances) and decreasing the distances inside the same class (intra-class distances). On the other hand, classifier-based metric learning focuses on directly improving the performance of a particular classification algorithm, and is thus dependent on the algorithm in question. Examples of both types of algorithms abound in the literature, see e.g. [21] and references therein.

Despite the success of metric learning, a bottleneck that arises fairly often in practice is high-dimensionality of the data. When many features are present, the required sample size for efficient learning increases exponentially, and so does the computational complexity. In addition, high-dimensionality is known to quickly degrade the performance of machine learning algorithms, owing to some counter-intuitive geometrical phenomena that arise in high dimensions. This means that, even if a suitable distance metric is found, the subsequent algorithm might still perform poorly. All these phenomena are collectively known as the curse of dimensionality [22].

It has been observed, however, that many real-world data sets do not fill their ambient spaces evenly in all directions, but instead their vectors cluster along a low-dimensional subspace, or have many redundant features [19]. We refer to these data sets, in a general sense, as having a low intrinsic dimension (low-ID). Due to their lower information content, it is intuitively expected that learning from a such a data set should be easier, both statistically and computationally. One of the most popular ways to take advantage of a low-ID, is to compress the original data set into a low-dimensional space and then proceed with learning in this smaller space [1]. Random projections is a widely used compression method. In this context, all instances are subjected to a universal mapping, via a random matrix, and the expectation is that important distances are preserved to a high-degree.

A common motivation behind random projection is that, it offers a trade-off between computational complexity and accuracy. Indeed, when operating on a compressed version of the original data, the computational complexity is reduced, but there is some degradation in the accuracy, as some information gets lost with compression. Despite this, under some conditions, random projections are known to preserve structural traits. Their good properties often allow us to control the loss of accuracy, while still enjoying a reduced complexity, should these traits be present – see e.g. [20, 12]. Another advantage, is that no pre-processing step is necessary beforehand, making random projections simple to implement [1]. In the case of metric learning, an additional motivation is to reduce the number of parameters to be estimated.

We show that random projections can improve the performance of metric learning, and can give us insights into its working as well. We consider distance-based metric learning on data compressed with a Gaussian random matrix, and derive theoretical guarantees on quantities of interest. As a summary of our main contributions, we derive the following:

* a uniform high-probability upper bound on the generalisation error of compressive metric learning; and

* a high-probability upper bound on the excess empirical error of the learnt metric, compared to the empirical error of a metric learnt in the original space.

These two theoretical guarantees, given in <Ref> respectively, capture the trade-off of compressive learning: when the projection dimension decreases, the first quantify becomes lower, and the second becomes higher.

Most importantly, unlike metric learning in the original high-dimensional space, we find that neither of the two quantities depends on the ambient dimension, but instead it turns out that they depend on some notion of ID, known as the stable dimension, defined in <Ref>. The stable dimension is a robust version of the classical algebraic dimension, that “averages” the spread of a set across different directions. This shows that the aforementioned trade-off can be reduced, should the stable dimension be low. We corroborate these theoretical findings with numerical experiments on synthetic data in order to show the extent to which the stable dimension plays a role in the effectiveness of metric learning in practice.

As an important ingredient of our analysis, we revisit a well-known result that uniformly bounds the maximum and minimum norm of vectors in the compressed unit sphere under a Gaussian random projection. We extend this result into a dimension-free version, for arbitrary domains, in <Ref>, which may be of independent interest.

§.§ Related work

Metric learning was introduced in [29] and it has attracted a significant amount of research since. Shortly after its introduction, two of the most popular metric learning algorithms were proposed: Large Margin Nearest Neighbour (LMNN) [27] and Information Theoretic Metric Learning (ITML) [6]. Generalisations and extensions to metric learning algorithms have also been well-studied. We refer the reader to the surveys in [15, 26] for a more detailed review on metric learning algorithms. There have also been attempts to learn non-linear metrics (e.g. [14, 5]), as well as to use metric learning as a pre-processing step to training neural networks, known as deep metric learning (see [13] for a survey). Metric learning has also been applied to other fields, e.g. collaborative filtering [10] and facial recognition [9].

Much recent literature has been devoted to mitigate the undesirable effects of the curse of dimensionality on metric learning. A typical approach is to train a low-dimensional metric in the ambient space,
this was demonstrated to improve the classification performance – see e.g. [28] and the references therein.

A notable thread of research, which our work builds upon, appears in a NeurIPS paper [23]. The authors consider both distance-based and classifier-based metric learning in high-dimensions, and show that, if a Frobenius norm-constraint is imposed onto the hypothesis class of Mahalanobis metrics then a smaller sample size is required for a low generalisation error. Based on this observation, they define the metric learning complexity of a data set as the minimum Frobenius norm constraint on the hypothesis class, that is required for efficient generalisation. Because the optimal constraint is not known in advance, they propose choosing the Frobenius norm-constraint at random, and show that this approach can lead to a reduced sample dependence on the ambient dimension.

Despite the large amount of publications about high-dimensional metric learning, most methods assume that the full data set is available. While of theoretical interest, in real-world settings, this is often not the case. Instead, it is common to only have access to a compressed version of the original data set. This can be either due to space constraints, or because a lower-dimensional data set is easier to work with, from a computational point of view. Learning from, or reconstructing compressed observations, has been well-studied in the literature, in a field known as compressed sensing [7]. In fact, the geometric structures that make compressed sensing easier, have also been examined in the analysis of learning tasks to some extent, e.g. [20]. Novel data acquisition sensors from compressed sensing enable collecting data in a randomly compressed form, alleviating the need to select and discard significant fractions of it during pre-processing.

In this work we only assume to have access to an already compressed version of the original data and never need the original. Yet, the guarantees we provide will be relative to the original high-dimensional parameters. To the best of our knowledge, distance-based metric learning has eluded a systematic study under compression so far. This paper aims to lessen this gap between theory and practice, and quantify the extra loss we suffer from the random compression, as well as identify the conditions that reduce that loss. Our work focuses on mitigating the curse of dimensionality by unveiling the benign structural traits that make metric learning more efficient, even when not having access to the original data.

§ MAIN RESULTS: METRIC LEARNING UNDER GAUSSIAN RANDOM PROJECTION

We denote scalars and vectors with lowercase letters, and matrices with capital letters. The Euclidean norm of a vector is denoted $\|\cdot\|$, whereas the Frobenius norm of a matrix is denoted $\|\cdot\|_F$. The trace of a matrix is denoted $\tr(\cdot)$. We let $\sigma_{\min}(\cdot)$ and $\sigma_{\max}(\cdot)$ be respectively the smallest and largest singular values of a matrix. $I_n$ denotes the $n\times n$ identity matrix, and $0_n$ denotes the $n$-dimensional zero vector. The notation $\mathcal N(\mu,\Sigma)$ denotes the Gaussian distribution with mean vector $\mu$ and covariance matrix $\Sigma$. We denote by $\E$ the expectation of a random variable (or random vector). For a set $T$, we write $T-T:=\{x-x':x,x'\in T\}$. We denote by $\mathcal S^{n-1}$ the $n$-dimensional unit sphere, that is $\mathcal S^{n-1}:=\{x\in\mathbb R^n:\|x\|=1\}$.

We now formally introduce the problem of distance-based metric learning, as well as the compression scheme. Let $\mathcal X\times\mathcal Y$ be the instance space, where $\mathcal X\subset\mathbb R^d$ is the feature space and $\mathcal Y=\{-1,1\}$ is the set of labels. We consider the usual setting where all instances are assumed to have been sampled i.i.d. from a fixed but unknown distribution $\mathcal D$ over $\mathcal X\times\mathcal Y$. For our derivations, the diameter of $\mathcal X$ is assumed finite, that is $\diam(\mathcal X)<\infty$.[Recall that for a set $T\subset\mathbb R^d$, its diameter is defined as $\diam(T):=\sup_{x,x'\in T}\|x-x'\|$.]

The goal of distance-based metric learning is to learn a matrix $M\in\mathbb R^{d\times d}$, such that the Mahalanobis distance between two instances $x,x'$, i.e. $\|Mx-Mx'\|$, is larger if $x,x'$ have different labels and smaller if $x,x'$ share the same label. For the purpose of dimensionality reduction, given a fixed $k$, where $k\leq d$, we let $R\in\mathbb R^{k\times d}$, with elements i.i.d. from $\mathcal N(0,1/k)$, be our projection matrix. We assume that each datum instance is already projected by the same $R$ (as in compressed sensing). We will be referring to $d$ and $k$ as the ambient dimension and the projection dimension respectively.

We next define the hypothesis classes of Mahalanobis metrics. Let

\begin{equation}
\mathcal M:=\{M\in\mathbb R^{d\times d}:\sigma_{\max}(M)=1\}
\label{eq:metric class}\end{equation}

be the hypothesis class in the ambient space, and

\begin{equation}
\mathcal M_k:=\{M\in\mathbb R^{k\times k}:\sigma_{\max}(M)=1\}
\label{eq:compressed metric class}\end{equation}

be the hypothesis class in the compressed space $R\mathcal X$,[With a slight abuse of notation, if $T$ is a set and $A$ is a conformable matrix, we write $AT:=\{Ax:x\in T\}$.] where the constraints on $\sigma_{\max}$ are to avoid arbitrary scaling. Let

\begin{equation}
(\mathcal X\times\mathcal Y)^2\supset T:=\{((x_{2i-1},y_{2i-1}),(x_{2i},y_{2i}))\}_{i=1}^n
\label{eq:training set}\end{equation}

be a training set of $n$ pairs of instances, that contains no pairs of duplicate elements. Also, let $\ell_{l,u}:\mathbb R\times\{0,1\}\to[0,1]$ be a distance-based loss function defined as

\begin{equation}
\ell_{l,u}(x,y):=\begin{cases}
\min\{1,\rho(x-u)_+\}\text{ if }y=1\\
\min\{1,\rho(l-x)_+\}\text{ if }y=0.
\end{cases}
\label{eq:loss function}\end{equation}

where $(\cdot)_+:=\max\{\cdot,0\}$, and $\rho,l,u$ are positive numbers with $l<u$.

Note that $\ell_{l,u}$ is $\rho$-Lipschitz in its first argument, a property we exploit later in the derivations. This loss function penalizes small inter-class distances and large intra-class distances, and is a common choice for distance-based metric learning [23].

We next define the true error of a hypothesis $M\in\mathcal M_k$, given the matrix $R$, as

\begin{equation}
L^R_{\mathcal D}(M):=\E_{((x,y),(x',y'))\sim\mathcal D^2}\ell_{l,u}(\|MRx-MRx'\|,\I{y=y'}),
\label{eq:true error compressed}\end{equation}

and its empirical error, given the training set $T$ from (<ref>), as

\begin{equation}
\hat L^R_T(M):=\frac1n\sum_{i=1}^n\ell_{l,u}(\|MRx_{2i-1}-MRx_{2i}\|,\I{y_{2i-1}=y_{2i}}),
\label{eq:empirical error compressed}\end{equation}

where $\I{\cdot}$ denotes the indicator function, that equals $1$ if its argument is true, and $0$ otherwise.

For a hypothesis in $M_0\in\mathcal M$, the true error and empirical error are defined analogously, by omitting $R$ and considering the original vectors, that is, the true error is defined as

\begin{equation}
L_{\mathcal D}(M_0):=\E_{((x,y),(x',y'))\sim\mathcal D^2}\ell_{l,u}(\|M_0x-M_0x'\|,\I{y=y'}),
\label{eq:true error}\end{equation}

and the empirical error is defined as

\begin{equation}
\hat L_T(M_0):=\frac1n\sum_{i=1}^n\ell_{l,u}(\|M_0x_{2i-1}-M_0x_{2i}\|,\I{y_{2i-1}=y_{2i}}).
\label{eq:empirical error}\end{equation}

We would first like to upper bound the generalisation error $(L^R_{\mathcal D}(M)-\hat L^R_T(M))$, uniformly, for all $M\in\mathcal M_k$, with high-probability, with respect to the random draws of $R$. To this end, let us introduce some complementary definitions and results, that appear in the derivations.

Let $T\subset\mathbb R^d$ be a set, and $g\sim\mathcal N(0_d,I_d)$. The Gaussian width of $T$, is defined as

\begin{equation}
\omega(T):=\E\sup_{x\in T}g^\top x,
\end{equation}

and the squared version of the Gaussian width of $T$, is defined as

\begin{equation}
\psi(T):=\sqrt{\E\sup_{x\in T}(g^\top x)^2}.\qedhere
\end{equation}

<Ref> allows us to introduce a more robust version of the algebraic dimension, as follows.

The stable dimension of a set $T\subset\mathbb R^d$, with $0<\diam(T)<\infty$, is defined as

\begin{equation}
\end{equation}

Intuitively, we can see the stable dimension as a more “detailed” version of the algebraic dimension, that takes into account the relative spread of a set, across different directions. It is straightforward to show that for any set $T\subset\mathbb R^d$, $s(T)\leq d$ (see again <cit.>). However, the stable dimension can be much lower than the algebraic dimension, even if the latter is allowed to be infinite. As we shall see, the stable dimension and the diameter of the data support, both appear in the upper bounds we derive for the generalisation error, and for the excess empirical error. We will also be using the following lemma about the relation of $\omega(\cdot)$ and $\psi(\cdot)$.

For any set $T\subset\mathbb R^d$, we have

\begin{equation}
\omega(T-T)\leq\psi(T-T).\qedhere
\end{equation}

The backbone of our two main results is an extension of the well-known Gordon's theorem <cit.>, from the unit sphere to arbitrary sets. While we are aware of more general results that assume sub-gaussian random matrices (e.g. <cit.>), we offer a simpler proof for the Gaussian case, that is free of any unspecified constants, and can thus be of interest in its own right. This is provided in the following lemma.[The proofs of all our new results, are deferred to the Appendix.]

Let $R\in\mathbb R^{k\times d}$ be a matrix, with elements i.i.d. from $\mathcal N(0,1)$, and let $T\subset\mathbb R^d$ be a set, such that $\sup_{x\in T}\|x\|=b$. Also, let $a(k):=\E\|z_k\|$, where $z_k\sim\mathcal N(0_k,I_k)$. Then, for any $\epsilon>0$, with probability at least $1-\exp(-\epsilon^2/2b^2)$, we have

\begin{equation}
\sup_{x\in T}\|Rx\|\leq ba(k)+\omega(T)+\epsilon
\end{equation}

and also, with probability at least $1-\exp(-\epsilon^2/2b^2)$, we have

\begin{equation}
\inf_{x\in T}\|Rx\|\geq ba(k)-\omega(T)-\epsilon
\end{equation}

where $\omega(\cdot)$ is the Gaussian width from <Ref>. Recall that $\frac k{\sqrt{k+1}}\leq a(k)\leq\sqrt k$.

Applying <Ref>, we can derive the following uniform, high-probability upper bound for the generalisation error of the compressed hypothesis class.

Let $R\in\mathbb R^{k\times d}$, with elements i.i.d. from $\mathcal N(0,1/k)$, $T\subset(\mathcal X\times\mathcal Y)^2$ be the training set defined in (<ref>), $\mathcal M_k$ be the hypothesis class defined in (<ref>), $L^R_{\mathcal D}$ be the compressed true error defined in (<ref>), and $\hat L^R_T$ be the compressed empirical error defined in (<ref>). Then, for any $0<\epsilon<1$, and for all $M\in\mathcal M_k$, with probability at least $1-\epsilon$, we have

\begin{equation}
L^R_{\mathcal D}(M)-\hat L^R_T(M)\leq2\rho\sqrt{\frac kn}\diam(\mathcal X)^2\left(1+\sqrt{\frac{s(\mathcal X)}k}+\sqrt{\frac{2\ln\frac2\epsilon}k}\right)^2+\sqrt{\frac{\ln\frac2\epsilon}{2n}}
\end{equation}

where $s(\cdot)$ is the stable dimension from <Ref>.

We can see that the ambient dimension does not appear in the generalisation bound, and is instead replaced by the stable dimension of the data support. This implies that if the data support has a low stable dimension, the empirical error calculated in the compressed space will serve as a closer approximation to the true error in the compressed space. Also, the bound is asymptotically increasing in $k$, and is, specifically, of order $O(\sqrt k)$. This is expected, as higher values of $k$, can result in more “complex” hypothesis classes.

In [23], a uniform upper bound for the generalisation error of $\mathcal M$ from (<ref>) is derived; for any $0<\epsilon<1$, and for all $M_0\in\mathcal M$, with probability at least $1-\epsilon$, we have

\begin{equation}
L_{\mathcal D}(M_0)-\hat L_T(M_0)\leq2\rho\sqrt{\frac dn}\diam(\mathcal X)^2+\sqrt{\frac{\ln\frac1\epsilon}{2n}},
\label{eq:verma generalisation bound}\end{equation}

where $L_{\mathcal D}$ and $\hat L_T$ are respectively the true error defined in (<ref>), and the empirical error defined in (<ref>). In addition, if a Frobenius norm constraint is imposed in (<ref>), then $d$ can be replaced by the upper bound on the Frobenius norm constraint. Although our uniform bound for $\mathcal M_k$ in <Ref> is similar to the one for $\mathcal M$, its purpose is different. In [23], the ambient data set is examined on whether it is possible to learn a metric with a low-Frobenius norm. In our case, we are instead interested to quantify the trade-off induced by the random projection between the generalisation error, and the excess empirical error (see <Ref> below for the latter). Therefore, the observation of [23], that a Frobenius norm-constraint can replace the ambient dimension, becomes irrelevant, as we impose no norm-constraints. The advantage we gain is not having to know beforehand about bounded Frobenius norm, instead we only need to set the projection dimension $k$. Besides this, of course, the main gain lies in the time and space savings of learning a $k\times k$ instead of a $d\times d$ matrix.

However, a generalisation bound is not the complete story in compression schemes, as there is usually a trade-off between the empirical error and the complexity term. Intuitively, we can expect that, as the projection dimension $k$ decreases, we obtain a lower complexity of the compressed hypothesis class, but a higher empirical error (due to the potential distortion that results from the compression). We already upper bounded the former in <Ref>, so we next upper bound the latter, uniformly, with high-probability, as follows:

Let $R\in\mathbb R^{k\times d}$, with elements i.i.d. from $\mathcal N(0,1/k)$, $T\subset(\mathcal X\times\mathcal Y)^2$ be the training set defined in (<ref>), $\mathcal M$ and $\mathcal M_k$ be the hypothesis classes defined in (<ref>) and (<ref>) respectively, and $\hat L_T$ and $\hat L^R_T$ be respectively the empirical error defined in (<ref>), and the compressed empirical error defined in (<ref>). Then, for any $0<\epsilon<1$, and for all $M\in\mathcal M_k$ and $M_0\in\mathcal M$, with probability at least $1-\epsilon$, we have

\begin{equation}
\hat L^R_T(M)-\hat L_T(M_0)\leq\rho\diam(\mathcal X)^2\left(1+\sqrt{\frac{s(\mathcal X)}k}+\sqrt{\frac{2\ln\frac2\epsilon}k}\right)^2
\end{equation}

Examining the bound in <Ref>, we can see that is does not depend on the ambient dimension, but on the stable dimension and diameter of the data support, just like the bound in <Ref>. This means that if the empirical error in the ambient space is small, the empirical error in the compressed space scales with the stable dimension, instead of the ambient dimension. It is also decreasing in $k$ as expected. Also, we can see that regardless of $k$, there is always the term $\rho\diam(\mathcal X)^2$, which can be seen as the “flat cost” of the compression. Finally, the sample size, $n$, does not appear at all, as it is assumed the same for training both $M$ and $M_0$, and simplifies out in the derivation.

To summarise, a Gaussian random projection incurs a lower generalisation error on metric learning, but induces an excess empirical error, compared to metric learning in the ambient space. Both quantities depend on the diameter and the stable dimension of the data support, instead of the ambient dimension, and automatically tighten, when these quantities are low. We next illustrate the effects that the stable dimension has on metric learning, in practice.

§ EXPERIMENTS

In this section we conduct numerical experiments to validate our theoretical guarantees in practice on both synthetic and benchmark data sets, in compressed settings. Synthetic data allow easy control of the diameter and stable dimension of their support, hence it allows us to test the explanatory abilities of our theoretical results.
Benchmark data sets will serve to test the usefulness and effectiveness of metric learning under compression.

§.§ Verifying theoretical findings on synthetic data sets

To design our experiments, let us recall that we derived theoretical guarantees for two quantities:

* the generalisation error of metric learning under Gaussian random projection; and

* the excess empirical error incurred relative to that of metric learning in the ambient space.

First, we fix the ambient dimension, as well as the diameter and stable dimension of the data support. We then perform a Gaussian random projection and train a metric using LMNN in the compressed space. Finally, we use $1$-NN on the compressed set and report the out-of-sample empirical error. We repeat this process 10 independent times, for different choices of the projection dimension.

We take the data support to be an ellipsoid of the form $\mathcal X=A\mathcal S^{d-1}$, where $A\in\mathbb R^{d\times d}$ with $\sigma_{\max}(A)=1$ is a diagonal, positive-definite matrix (without loss of generality, since the algorithm is rotation-invariant). We vary the stable dimension $s(\mathcal X)$ by considering different rates of decay of the diagonal elements of $A$. We generate a sample set of $2000$ instances, $\{x_i\}_{i=1}^{2000}$, sampled uniformly randomly over $\mathcal X$, and employ a train/test ratio of $80\%/20\%$.

By construction, the stable dimension of $\mathcal X$ has the closed form expression $s(\mathcal X)=(\|A\|_F/\sigma_{\max}(A))^2$ <cit.>. In addition, since $\sigma_{\max}(A)=1$, this ensures that $\diam(\mathcal X)=1$. Hence, according to our theoretical results, we expect that increasing $d$ should not blow up the average empirical error, as long as both $s(\mathcal X)$ and $\diam(\mathcal X)$ stay bounded from above, independently of $d$.

We want to compare the empirical out-of-sample error in the compressed space, with the error in the ambient space. Due to this, we consider settings where the empirical error in the ambient space is small, and thus it is enough to examine only the empirical error in the compressed space. For the purpose of maintaining a small (but not zero) empirical error in the ambient space, we considered linearly separable data sets, where 1-NN can achieve almost perfect classification. Specifically, the original labels were set to $y_i:=\sign(w^\top x_i)$ for all $i\in[2000]$, where $w$ was sampled from $\mathcal N(0_d,I_d)$, and then fixed for each value of $d$.

[title=$d=100$,xlabel=Projection dimension ($k$),ylabel=Out-of-sample error rate of $1$-NN,legend entries=$1$,$i/d$,$(i/d)^2$,$1/i$,$(1/i)^2$,ymin=.01,ymax=.53]
[red,mark=triangle,y filter/.append expression=set!=1 ? nan:,y filter/.append expression=d!=100 ? nan:]table[x=k,y=bmean]synthetic.txt;
[blue,mark=triangle,y filter/.append expression=set!=2 ? nan:,y filter/.append expression=d!=100 ? nan:]table[x=k,y=bmean]synthetic.txt;
[green,mark=triangle,y filter/.append expression=set!=3 ? nan:,y filter/.append expression=d!=100 ? nan:]table[x=k,y=bmean]synthetic.txt;
[magenta,mark=triangle,y filter/.append expression=set!=4 ? nan:,y filter/.append expression=d!=100 ? nan:]table[x=k,y=bmean]synthetic.txt;
[orange,mark=triangle,y filter/.append expression=set!=5 ? nan:,y filter/.append expression=d!=100 ? nan:]table[x=k,y=bmean]synthetic.txt;
[red,dashed,mark=triangle,y filter/.append expression=set!=1 ? nan:,y filter/.append expression=d!=100 ? nan:]table[x=k,y=cmean]synthetic.txt;
[blue,dashed,mark=triangle,y filter/.append expression=set!=2 ? nan:,y filter/.append expression=d!=100 ? nan:]table[x=k,y=cmean]synthetic.txt;
[green,dashed,mark=triangle,y filter/.append expression=set!=3 ? nan:,y filter/.append expression=d!=100 ? nan:]table[x=k,y=cmean]synthetic.txt;
[magenta,dashed,mark=triangle,y filter/.append expression=set!=4 ? nan:,y filter/.append expression=d!=100 ? nan:]table[x=k,y=cmean]synthetic.txt;
[orange,dashed,mark=triangle,y filter/.append expression=set!=5 ? nan:,y filter/.append expression=d!=100 ? nan:]table[x=k,y=cmean]synthetic.txt;

[title=$d=500$,xlabel=Projection dimension ($k$),ytick pos=upper,legend entries=$1$,$i/d$,$(i/d)^2$,$1/i$,$(1/i)^2$,ymin=.01,ymax=.53]
[red,mark=triangle,y filter/.append expression=set!=1 ? nan:,y filter/.append expression=d!=500 ? nan:]table[x=k,y=bmean]synthetic.txt;
[blue,mark=triangle,y filter/.append expression=set!=2 ? nan:,y filter/.append expression=d!=500 ? nan:]table[x=k,y=bmean]synthetic.txt;
[green,mark=triangle,y filter/.append expression=set!=3 ? nan:,y filter/.append expression=d!=500 ? nan:]table[x=k,y=bmean]synthetic.txt;
[magenta,mark=triangle,y filter/.append expression=set!=4 ? nan:,y filter/.append expression=d!=500 ? nan:]table[x=k,y=bmean]synthetic.txt;
[orange,mark=triangle,y filter/.append expression=set!=5 ? nan:,y filter/.append expression=d!=500 ? nan:]table[x=k,y=bmean]synthetic.txt;
[red,dashed,mark=triangle,y filter/.append expression=set!=1 ? nan:,y filter/.append expression=d!=500 ? nan:]table[x=k,y=cmean]synthetic.txt;
[blue,dashed,mark=triangle,y filter/.append expression=set!=2 ? nan:,y filter/.append expression=d!=500 ? nan:]table[x=k,y=cmean]synthetic.txt;
[green,dashed,mark=triangle,y filter/.append expression=set!=3 ? nan:,y filter/.append expression=d!=500 ? nan:]table[x=k,y=cmean]synthetic.txt;
[magenta,dashed,mark=triangle,y filter/.append expression=set!=4 ? nan:,y filter/.append expression=d!=500 ? nan:]table[x=k,y=cmean]synthetic.txt;
[orange,dashed,mark=triangle,y filter/.append expression=set!=5 ? nan:,y filter/.append expression=d!=500 ? nan:]table[x=k,y=cmean]synthetic.txt;

[title=$d=1000$,xlabel=Projection dimension ($k$),ylabel=Out-of-sample error rate of $1$-NN,legend entries=$1$,$i/d$,$(i/d)^2$,$1/i$,$(1/i)^2$,ymin=.01,ymax=.53]
[red,mark=triangle,y filter/.append expression=set!=1 ? nan:,y filter/.append expression=d!=1000 ? nan:]table[x=k,y=bmean]synthetic.txt;
[blue,mark=triangle,y filter/.append expression=set!=2 ? nan:,y filter/.append expression=d!=1000 ? nan:]table[x=k,y=bmean]synthetic.txt;
[green,mark=triangle,y filter/.append expression=set!=3 ? nan:,y filter/.append expression=d!=1000 ? nan:]table[x=k,y=bmean]synthetic.txt;
[magenta,mark=triangle,y filter/.append expression=set!=4 ? nan:,y filter/.append expression=d!=1000 ? nan:]table[x=k,y=bmean]synthetic.txt;
[orange,mark=triangle,y filter/.append expression=set!=5 ? nan:,y filter/.append expression=d!=1000 ? nan:]table[x=k,y=bmean]synthetic.txt;
[red,dashed,mark=triangle,y filter/.append expression=set!=1 ? nan:,y filter/.append expression=d!=1000 ? nan:]table[x=k,y=cmean]synthetic.txt;
[blue,dashed,mark=triangle,y filter/.append expression=set!=2 ? nan:,y filter/.append expression=d!=1000 ? nan:]table[x=k,y=cmean]synthetic.txt;
[green,dashed,mark=triangle,y filter/.append expression=set!=3 ? nan:,y filter/.append expression=d!=1000 ? nan:]table[x=k,y=cmean]synthetic.txt;
[magenta,dashed,mark=triangle,y filter/.append expression=set!=4 ? nan:,y filter/.append expression=d!=1000 ? nan:]table[x=k,y=cmean]synthetic.txt;
[orange,dashed,mark=triangle,y filter/.append expression=set!=5 ? nan:,y filter/.append expression=d!=1000 ? nan:]table[x=k,y=cmean]synthetic.txt;

[title=$d=2000$,xlabel=Projection dimension ($k$),ytick pos=upper,legend entries=$1$,$i/d$,$(i/d)^2$,$1/i$,$(1/i)^2$,ymin=.01,ymax=.53]
[red,mark=triangle,y filter/.append expression=set!=1 ? nan:,y filter/.append expression=d!=2000 ? nan:]table[x=k,y=bmean]synthetic.txt;
[blue,mark=triangle,y filter/.append expression=set!=2 ? nan:,y filter/.append expression=d!=2000 ? nan:]table[x=k,y=bmean]synthetic.txt;
[green,mark=triangle,y filter/.append expression=set!=3 ? nan:,y filter/.append expression=d!=2000 ? nan:]table[x=k,y=bmean]synthetic.txt;
[magenta,mark=triangle,y filter/.append expression=set!=4 ? nan:,y filter/.append expression=d!=2000 ? nan:]table[x=k,y=bmean]synthetic.txt;
[orange,mark=triangle,y filter/.append expression=set!=5 ? nan:,y filter/.append expression=d!=2000 ? nan:]table[x=k,y=bmean]synthetic.txt;
[red,dashed,mark=triangle,y filter/.append expression=set!=1 ? nan:,y filter/.append expression=d!=2000 ? nan:]table[x=k,y=cmean]synthetic.txt;
[blue,dashed,mark=triangle,y filter/.append expression=set!=2 ? nan:,y filter/.append expression=d!=2000 ? nan:]table[x=k,y=cmean]synthetic.txt;
[green,dashed,mark=triangle,y filter/.append expression=set!=3 ? nan:,y filter/.append expression=d!=2000 ? nan:]table[x=k,y=cmean]synthetic.txt;
[magenta,dashed,mark=triangle,y filter/.append expression=set!=4 ? nan:,y filter/.append expression=d!=2000 ? nan:]table[x=k,y=cmean]synthetic.txt;
[orange,dashed,mark=triangle,y filter/.append expression=set!=5 ? nan:,y filter/.append expression=d!=2000 ? nan:]table[x=k,y=cmean]synthetic.txt;

Out-of-sample error of $1$-NN on synthetic data sets, with metric learning (solid lines), and without metric learning (dashed lines), averaged over $10$ Gaussian random projections, for several choices of $s({\mathcal X})$. The input data support was ${\mathcal X}=A{\mathcal S}^{d-1}$, where $A\in\mathbb{R}^{d\times d}$ is a diagonal matrix with $\sigma_{\max}(A)=1$, and the legend shows its $j$-th diagonal element ($j\in [d]$) – this determines the stable dimension $s(\mathcal X)$. The sample set consists of $2000$ instances, $\{x_i\}_{i=1}^{2000}$, and a train/test ratio of $80\%/20\%$ was used. In each setting, the original labels were determined as $y_i:=\sign(w^\top x_i)$, for all $i\in[2000]$, where $w$ was sampled from $\mathcal N(0_d,I_d)$.

<Ref> shows the empirical results obtained. As expected from the theory, we see that the error is affected by the stable dimension and unaffected by the ambient dimension. To confirm, we repeated these experiments with different values of $d$, and for different decay rates on the eigenvalues of $A$, as shown in the sub-plots of <Ref>. Each time we observe the same behaviour.

In addition, comparing the solid and dashed lines of <Ref>, we see that compressive learning of the metric appears to be useful even for small values of $k$, provided the stable dimension of the data support is small. While it is expected that random compression makes the covariance of the data distribution more “spherical”, and can potentially distort any separation that existed, if the support is highly anisotropic (i.e. has a low stable dimension), then the separability can still be preserved to a high degree. Thus, a learnt metric can outperform the classic Euclidean metric. Indeed, we can see that the dashed lines approach the respective solid lines, as $k$ decreases.

An exception to the above is when the stable dimension is too small, and the empirical error without metric learning is already low, so learning a metric does not significantly improve it. However, judging from the sub-plots, this seems to depend mostly on the ratio $s(\mathcal X)/d$, rather than on $s(\mathcal X)$ only.

§.§ Experiments with benchmark UCI data sets

In real data, the values of the stable dimension and diameter of the support are unknown, but one may expect some structure that metric learning can exploit. To evaluate the effectiveness of metric learning under compression in more realistic settings, we follow the same experimental protocol as in synthetic data sets (80%/20% split), and compute the empirical error, for varying degrees of compression. We also measure the time it takes for the algorithm to run, in each case.

We used three benchmark UCI data sets with moderate ambient dimension from [8]: Ionosphere (33 features, 351 instances), Wine (13 features, 178 instances), and Sonar (60 features, 208 instances). We appended each data set with standard Gaussian random noise, for a total of 250 features for all sets. This simulates the case where many uninformative features are present, and tests whether compression is able to preserve information from the important features.

[title=Empirical performance,xlabel=Projection dimension ($k$),ylabel=Out-of-sample error rate of $1$-NN,legend entries=Ionosphere,Wine,Sonar,ymin=.01,ymax=.49]
[red,mark=triangle,y filter/.expression=set!=1 ? nan:,error bars,y dir=both,y explicit]table[x=k,y=bmean,y error=bsd]real.txt;
[blue,mark=triangle,y filter/.expression=set!=2 ? nan:,error bars,y dir=both,y explicit]table[x=k,y=bmean,y error=bsd]real.txt;
[green,mark=triangle,y filter/.expression=set!=3 ? nan:,error bars,y dir=both,y explicit]table[x=k,y=bmean,y error=bsd]real.txt;

[title=Time complexity,xlabel=Projection dimension ($k$),ylabel=Runtime in seconds,yticklabel pos=upper,legend entries=Ionosphere,Wine,Sonar,legend pos=north west]
[red,mark=triangle,y filter/.expression=set!=1 ? nan:,error bars,y dir=both,y explicit]table[x=k,y=amean,y error=asd]real.txt;
[blue,mark=triangle,y filter/.expression=set!=2 ? nan:,error bars,y dir=both,y explicit]table[x=k,y=amean,y error=asd]real.txt;
[green,mark=triangle,y filter/.expression=set!=3 ? nan:,error bars,y dir=both,y explicit]table[x=k,y=amean,y error=asd]real.txt;

Out-of-sample error (left) and runtime (right) of the combined procedure of metric learning and subsequent $1$-NN classification, using benchmark UCI data sets. All data sets were augmented to 250 dimensions by adding standard Gaussian random noise. A train/test ratio of $80\%/20\%$ was used. The curves represent averages over $10$ independent Gaussian random projections, for several choices of $k$. The error bars show one standard deviation.

<Ref> shows the empirical results. We see a clear trade-off between complexity and performance. As $k$ increases, the performance improves (left sub-plot), but the time complexity grows considerably (right sub-plot). While the time complexity is strictly increasing with $k$ (disregarding fluctuations that occur due to randomness), the empirical performance
presents some fluctuations. Nevertheless, for all data sets there seems to be a value of $k$ where the time complexity is much lower, while the empirical performance is no worse than $k=d$. Apart from the low end of $k$ values, the choice of $k$ depends on the user's preference to balance complexity and performance in these noisy data sets.

§ CONCLUSIONS

We considered distance-based metric learning when working with a randomly compressed version of the data. We derived high-probability theoretical guarantees for its generalisation error, as well as for its excess empirical error. We showed theoretically that both quantities are unaffected by the ambient dimension, and instead depend on the diameter and the stable dimension of the data support. We supported these findings with experiments on both synthetic and benchmark data sets in conjunction with Nearest Neighbour classification, and studying its empirical performance under metric learning.

§.§ Limitations and future work

In this work we only considered properties of the support of the data. Future work may focus on studying the effect of the data distribution on the effectiveness of metric learning under projection. This is particularly useful in settings where the second-moment (covariance) matrix of the distribution is far from isotropic, and the data support is only bounded with high-probability, e.g. sub-gaussian, or even heavy-tailed data. Related work has been done for quadratic classifiers in [16], which showed that the effective rank (a measure of isotropy) of the covariance matrix affects the generalisation error. The second-moment matrix is usually unknown, so it would be insightful to see how metric learning can automatically adapt to some particular structure in that matrix.

Another possible extension is to implement a setting where each compressed instance is perturbed by random noise. Metric learning under noisy regimes has already been examined, e.g. [18], but only for the ambient space. Considering the effect of noise on metric learning under compression may also be of interest in many real-world settings, since noisy observations are common sights in practice.

[1]
Dimitris Achlioptas.
Database-friendly random projections: Johnson-lindenstrauss with
binary coins.
Journal of computer and System Sciences, 66(4):671–687, 2003.

[2]
Afonso S Bandeira.
Ten lectures and forty-two open problems in the mathematics of data
science, 2015.

[3]
Peter L Bartlett and Shahar Mendelson.
Rademacher and gaussian complexities: Risk bounds and structural
Journal of Machine Learning Research, 3(Nov):463–482, 2002.

[4]
George Casella and Roger L Berger.
Statistical inference.
Cengage Learning, 2 edition, 2002.

[5]
Shuo Chen, Lei Luo, Jian Yang, Chen Gong, Jun Li, and Heng Huang.
Curvilinear distance metric learning.
Advances in Neural Information Processing Systems, 32, 2019.

[6]
Jason V Davis, Brian Kulis, Prateek Jain, Suvrit Sra, and Inderjit S Dhillon.
Information-theoretic metric learning.
In Proceedings of the 24th international conference on Machine
learning, pages 209–216, 2007.

[7]
David L Donoho.
Compressed sensing.
IEEE Transactions on information theory, 52(4):1289–1306,

[8]
Dheeru Dua and Casey Graff.
UCI machine learning repository, 2017.

[9]
Matthieu Guillaumin, Jakob Verbeek, and Cordelia Schmid.
Is that you? Metric learning approaches for face identification.
In 2009 IEEE 12th international conference on computer vision,
pages 498–505. IEEE, 2009.

[10]
Cheng-Kang Hsieh, Longqi Yang, Yin Cui, Tsung-Yi Lin, Serge Belongie, and
Deborah Estrin.
Collaborative metric learning.
In Proceedings of the 26th international conference on world
wide web, pages 193–201, 2017.

[11]
Gabriel Romon (https://math.stackexchange.com/users/66096/gabriel-romon).
Relation between Gaussian width and its squared version.
Mathematics Stack Exchange.
url:https://math.stackexchange.com/q/3341819 (version: 2019-09-02).

[12]
Ata Kabán.
Non-asymptotic analysis of compressive Fisher discriminants in
terms of the effective dimension.
In Asian Conference on Machine Learning, pages 17–32. PMLR,

[13]
Mahmut Kaya and Hasan Şakir Bilge.
Deep metric learning: A survey.
Symmetry, 11(9):1066, 2019.

[14]
Dor Kedem, Stephen Tyree, Fei Sha, Gert Lanckriet, and Kilian Q Weinberger.
Non-linear metric learning.
Advances in neural information processing systems, 25, 2012.

[15]
Brian Kulis et al.
Metric learning: A survey.
Foundations and Trends in Machine Learning, 5(4):287–364,

[16]
Fabian Latorre, Leello Tadesse Dadi, Paul Rolland, and Volkan Cevher.
The effect of the intrinsic dimension on the generalization of
quadratic classifiers.
Advances in Neural Information Processing Systems,
34:21138–21149, 2021.

[17]
Michel Ledoux and Michel Talagrand.
Probability in Banach Spaces: Isoperimetry and processes,
volume 23.
Springer Science & Business Media, 1991.

[18]
Daryl Lim, Gert Lanckriet, and Brian McFee.
Robust structural metric learning.
In International conference on machine learning, pages
615–623. PMLR, 2013.

[19]
Phil Pope, Chen Zhu, Ahmed Abdelkader, Micah Goldblum, and Tom Goldstein.
The intrinsic dimension of images and its impact on learning.
In International Conference on Learning Representations, 2020.

[20]
Hugo Reboredo, Francesco Renna, Robert Calderbank, and Miguel RD Rodrigues.
Bounds on the number of measurements for reliable compressive
IEEE Transactions on Signal Processing, 64(22):5778–5793,

[21]
Juan Luis Suárez, Salvador García, and Francisco Herrera.
A tutorial on distance metric learning: Mathematical foundations,
algorithms, experimental analysis, prospects and challenges.
Neurocomputing, 425:300–322, 2021.

[22]
Michel Verleysen and Damien François.
The curse of dimensionality in data mining and time series
In International work-conference on artificial neural networks,
pages 758–770. Springer, 2005.

[23]
Nakul Verma and Kristin Branson.
Sample complexity of learning Mahalanobis distance metrics.
Advances in neural information processing systems, 28, 2015.

[24]
Roman Vershynin.
High-dimensional probability: An introduction with applications
in data science, volume 47.
Cambridge university press, 2018.

[25]
Martin J Wainwright.
High-dimensional statistics: A non-asymptotic viewpoint,
volume 48.
Cambridge University Press, 2019.

[26]
Fei Wang and Jimeng Sun.
Survey on distance metric learning and dimensionality reduction in
data mining.
Data mining and knowledge discovery, 29(2):534–564, 2015.

[27]
Kilian Q Weinberger and Lawrence K Saul.
Distance metric learning for large margin nearest neighbor
Journal of machine learning research, 10(2), 2009.

[28]
Pengtao Xie, Wei Wu, Yichen Zhu, and Eric Xing.
Orthogonality-promoting distance metric learning: Convex relaxation
and theoretical analysis.
In International Conference on Machine Learning, pages
5403–5412. PMLR, 2018.

[29]
Eric Xing, Michael Jordan, Stuart J Russell, and Andrew Ng.
Distance metric learning with application to clustering with
Advances in neural information processing systems, 15, 2002.

§ PROOFS

§.§ Proof of

To prove <Ref>, we first recall two well-known inequalities, regarding Gaussian processes (see <cit.> and the references therein for the definitions and derivations).

Let $(X_t)_{t\in T}$ and $(Y_t)_{t\in T}$ be two mean-zero Gaussian processes and assume that for all $t,s\in T$, we have
\begin{equation}\E(X_t-X_s)^2\leq\E(Y_t-Y_s)^2.\end{equation}
Then, we have
\begin{equation}\E\sup_{t\in T}X_t\leq\E\sup_{t\in T}Y_t.\qedhere\end{equation}

Let $(X_{u,t})_{(u,t)\in U\times T}$ and $(Y_{u,t})_{(u,t)\in U\times T}$ be two mean zero Gaussian processes. Assume that we have
\begin{equation}\E(X_{u,t}-X_{u,s})^2\leq\E(Y_{u,t}-Y_{u,s})^2\text{ for all }u,t,s\end{equation}
\begin{equation}\E(X_{u,t}-X_{v,s})^2\geq\E(Y_{u,t}-Y_{v,s})^2\text{ for all }u\neq v\text{ and all }t,s.\end{equation}
Then, for all $c\geq0$, we have
\begin{equation}\Pr\left\{\inf_{u\in U}\sup_{t\in T}X_{u,t}\geq c\right\}\leq\Pr\left\{\inf_{u\in U}\sup_{t\in T}Y_{u,t}\geq c\right\}\end{equation}
and consequently
\begin{equation}\E\inf_{u\in U}\sup_{t\in T}X_{u,t}\leq\E\inf_{u\in U}\sup_{t\in T}Y_{u,t}.\end{equation}

Equipped with <Ref>, we are now ready for the proof of <Ref>. We first define two mean-zero Gaussian processes as

\begin{equation}
X_{u,x}:=bg^\top u+h^\top x\qquad\text{ and }\qquad Y_{u,x}:=u^\top Rx
\end{equation}

where $(u,x)\in\mathcal S^{k-1}\times T$ and $g\sim\mathcal N(0_k,I_k)$ and $h\sim\mathcal N(0_d,I_d)$ are independent from each other.

For all $(u,x),(u',x')\in\mathcal S^{k-1}\times T$, we have

\begin{align}
\E\vert X_{u,x}-X_{u',x'}\vert^2&=\E(bg^\top u+h^\top x-bg^\top u'-h^\top x')^2\\
&=2b^2-2b^2u^\top u'+\|x\|^2+\|x'\|^2-2x^\top x'
\end{align}

\begin{align}
\E\vert Y_{u,x}-Y_{u',x'}\vert^2&=\E(u^\top Rx-u'^\top Rx')^2\\
&=\tr((ux^\top-u'x'^\top)^\top (ux^\top-u'x'^\top))\\
&=\tr(xu^\top ux^\top)+\tr(x'u'^\top u'x'^\top)-2\tr(x'u'^\top ux^\top)\\
&=\tr(x^\top x)+\tr(x'^\top x')-2\tr(u^\top u')\tr(x^\top x')\\
&=\|x\|^2+\|x'\|^2-2(u^\top u')(x^\top x').
\end{align}

Therefore, we find that

\begin{equation}
\E\vert X_{u,x}-X_{u',x'}\vert^2-\E\vert Y_{u,x}-Y_{u',x'}\vert^2=2(1-u^\top u')(b^2-x^\top x').
\end{equation}

This means that for all $(u,x),(u',x')\in\mathcal S^{k-1}\times T$ we have

\begin{equation}
\E\vert X_{u,x}-X_{u',x'}\vert^2-\E\vert Y_{u,x}-Y_{u',x'}\vert^2\geq0
\end{equation}

\begin{equation}
\E\vert X_{u,x}-X_{u,x'}\vert^2-\E\vert Y_{u,x}-Y_{u,x'}\vert^2=0
\end{equation}

Therefore, the conditions of <Ref> are satisfied, and thus

\begin{equation}
\E\sup_{u,x}X_{u,x}\geq\E\sup_{u,x}Y_{u,x}.
\end{equation}

Noting that

\begin{equation}
\E\sup_{u\in\mathcal S^{k-1}}\sup_{x\in T}X_{u,x}=b\E\sup_{u\in\mathcal S^{k-1}}g^\top u+\E\sup_{x\in T}h^\top x=ba(k)+\omega(T).
\end{equation}

\begin{equation}
\E\sup_{u\in\mathcal S^{k-1}}\sup_{x\in T}Y_{u,x}=\E\sup_{u\in\mathcal S^{k-1}}\sup_{x\in T}u^\top Rx=\E\sup_{x\in T}\|Rx\|
\end{equation}

we conclude that

\begin{equation}
\E\sup_{x\in T}\|Rx\|\leq ba(k)+\omega(T).
\end{equation}

Also, the conditions of <Ref> are satisfied, and thus

\begin{equation}
\E\inf_{x\in T}\sup_{u\in\mathcal S^{k-1}}X_{u,x}\leq\E\inf_{x\in T}\sup_{u\in\mathcal S^{k-1}}Y_{u,x}.
\end{equation}

Noting that

\begin{equation}
\E\inf_{x\in T}\sup_{u\in\mathcal S^{k-1}}X_{u,x}=b\E\sup_{u\in\mathcal S^{k-1}}g^\top u-\sup_{x\in T}(-h^\top x)=ba(k)-\omega(T).
\end{equation}

\begin{equation}
\E\inf_{x\in T}\sup_{u\in\mathcal S^{k-1}}Y_{u,x}=\E\inf_{x\in T}\sup_{u\in\mathcal S^{k-1}}u^\top Rx=\E\inf_{x\in T}\|Rx\|
\end{equation}

we conclude that

\begin{equation}
\E\inf_{x\in T}\|Rx\|\geq ba(k)-\omega(T)
\end{equation}

It remains to bound $\sup_{x\in T}\|Rx\|$ and $\inf_{x\in T}\|Rx\|$ with high-probability away from their expectations. To this end, we claim that the functions $f_1(R)=\sup_{x\in T}\|Rx\|$ and $f_2(R)=\inf_{x\in T}\|Rx\|$ are both $b$-Lipschitz with respect to the Euclidean norm. To see why, let $R_1,R_2\in\mathbb R^{k\times d}$ be fixed matrices (which can also be seen as vectors in $\mathbb R^{kd}$), and note that

\begin{align}
\vert f_1(R_1)-f_1(R_2)\vert&=\vert\sup_{x\in T}\|R_1x\|-\sup_{x\in T}\|R_2x\|\vert\\
&\leq\sup_{x\in T}\vert\|R_1x\|-\|R_2x\|\vert\\
&\leq\sup_{x\in T}\|(R_1-R_2)x\|\\
&\leq\sup_{x\in T}\|x\|\sigma_{\max}(R_1-R_2)\\
&\leq b\|R_1-R_2\|_F
\end{align}

and similarly that

\begin{align}
\vert f_2(R_1)-f_2(R_2)\vert&=\vert\inf_{x\in T}\|R_1x\|-\inf_{x\in T}\|R_2x\|\vert\\
&=\vert\sup_{x\in T}\|R_1x\|-\sup_{x\in T}\|R_2x\|\vert\\
&\leq b\|R_1-R_2\|_F.
\end{align}

Invoking both bounds of <cit.>, we complete the proof.

§.§ Proof of

Let $\mathcal P$ be a probability measure induced by the random variable $(X,Y)$, where $X:=(x,x')$ and $Y:=\I{y=y'}$, for $((x,y),(x',y'))\sim\mathcal D^2$. Also denote $\mathcal D_{\mathcal X}$ the marginal distribution induced by $\mathcal D$ on $\mathcal X$. Also let $\ell_{l,u}$ be the loss function defined in (<ref>). Given a matrix $R$, we define the function class in the compressed space as

\begin{equation}
\mathcal F_R=\{f_M:(x_1,x_2)\to\|M(Rx_1-Rx_2)\|^2:M\in\mathcal M_k\text{ and }x_1,x_2\in\mathcal X\}.
\end{equation}

Also, for all $i=\in[n]$, let $X_i:=(x_{2i-1},x_{2i})$ and $Y_i:=\I{y_{2i-1},y_{2i}}$ be “regrouped” versions of the elements of $T$, defined in (<ref>). We are interested in upper bounding

\begin{equation}
\sup_{f_M\in\mathcal F_R}\left(\E_{(X,Y)\sim\mathcal P}\ell_{l,u}(f_M(X),Y)-\frac1n\sum_{i=1}^n\ell_{l,u}(f_M(X_i),Y_i)\right)
\end{equation}

We then upper bound the Rademacher complexity[See <Ref> for the definition of the Rademacher complexity] of $\mathcal F_R$, with respect to $\mathcal P$. Let $\sigma_1,\ldots,\sigma_n$ be  i.i.d. uniform $\{\pm1\}$-valued random variables. Modifying the proof of <cit.>, we obtain with probability at least $1-\epsilon$

\begin{align}
\mathcal R_{n,\mathcal D}(\mathcal F_R)&:=\frac1n\E_{\substack{\sigma_i,X_i\\i\in[n]}}\sup_{f_M\in\mathcal F_R}\sum_{i=1}^n\sigma_if_M(x_{2i-1},x_{2i})\\
&=\frac1n\E_{\substack{\sigma_i,X_i\\i\in[n]}}\sup_{M\in\mathcal M_k}\sum_{i=1}^n\sigma_i(x_{2i-1}-x_{2i})^\top R^\top M^\top MR(x_{2i-1}-x_{2i})\\
&\leq\frac1{\sqrt n}\sup_{M\in\mathcal M_k}\|M^\top M\|_F(\E_{(x,x')\sim\mathcal D_{\mathcal X}\times\mathcal D_{\mathcal X}}\|R(x-x')\|^4)^{1/2}\\
&\leq\sqrt{\frac kn}(\E_{(x,x')\sim\mathcal D_{\mathcal X}\times\mathcal D_{\mathcal X}}\|R(x-x')\|^4)^{1/2}\\
&\leq\sqrt{\frac kn}\sup_{x,x'\in\mathcal X}\|R(x-x')\|^2\\
&\leq\sqrt{\frac kn}\left(\diam(\mathcal X)+\frac{\omega(\mathcal X-\mathcal X)}{\sqrt k}+\diam(\mathcal X)\sqrt{\frac{2\ln\frac1\epsilon}k}\right)^2\label{eq:use of lemma 1}\\
&\leq\sqrt{\frac kn}\left(\diam(\mathcal X)+\frac{\psi(\mathcal X-\mathcal X)}{\sqrt k}+\diam(\mathcal X)\sqrt{\frac{2\ln\frac1\epsilon}k}\right)^2\label{eq:use of lemma 2}\\
&=\sqrt{\frac kn}\diam(\mathcal X)^2\left(1+\sqrt{\frac{s(\mathcal X)}k}+\sqrt{\frac{2\ln\frac1\epsilon}k}\right)^2.
\label{eq:Rademacher bound}\end{align}

We used the upper bound of <Ref> to obtain (<ref>), and the inequality of <Ref> to obtain (<ref>). To complete the proof, we then invoke the well-known Rademacher bound, which we include for completeness in the following lemma, combined with the union bound <cit.>.

Let $\mathcal D$ be a distribution over $\mathcal X\times\{-1,1\}$ and let $\{(x_i,y_i)\}_{i=1}^n$ be a sample of size $n$ drawn i.i.d. from $\mathcal D$. Given a hypothesis class $\mathcal F$ and a loss function $\ell:\mathbb R\times\{-1,1\}\to\mathbb R$ such that $\vert\ell(y',y)\vert\leq1$, for all $y',y\in\mathbb R$ and $\ell$ is $\rho$-Lipschitz in its first argument, then, for any $0<\epsilon<1$, with probability at least $1-\epsilon$ for all $f\in\mathcal F$, we have
\begin{equation}\E_{(x,y)\sim\mathcal D}\ell(f(x),y)\leq\frac1n\sum_{i=1}^n\ell(f(x_i),y_i)+2\rho\mathcal R_{n,\mathcal D}(\mathcal F)+\sqrt{\frac{\ln\frac1\epsilon}{2n}}\end{equation}

where $\mathcal R_{n,\mathcal D}(\mathcal F)$ is the Rademacher complexity of the hypothesis class $\mathcal F$, given a sample of size $n$ i.i.d. from $\mathcal D$, and is defined as

\begin{equation}\mathcal R_{n,\mathcal D}(\mathcal F):=\frac1n\E_\sigma\sup_{f\in\mathcal F}\sum_{i=1}^n\sigma_if(x_i)\end{equation}

where $\sigma_1,\ldots,\sigma_n$ are i.i.d., uniform $\{\pm1\}$-valued random variables.

§.§ Proof of

To exploit the $\rho$-Lipschitz property of $\ell_{l,u}$, as well as to quantify the excess empirical error with respect to the random draws of $R$, assume we have trained (e.g. by ERM rule) hypotheses $M\in\mathcal M_k$ and $M_0\in\mathcal M$. We then have

\begin{equation}
\hat L^R_T(M)-\hat L_T(M_0)\leq\frac\rho n\sum_{i=1}^n\vert\|MR(x_{2i-1}-x_{2i})\|^2-\|M_0(x_{2i-1}-x_{2i})\|^2\vert.
\label{eq:empirical bound}\end{equation}

To upper bound the absolute value in (<ref>), we need to both lower and upper bound the quantity inside, with respect to $R$, and write the maximum of the two. There are two terms inside the maximum, which must be lower and upper bounded separately.

For the first term, recall that $\sigma_{\max}(M)=\sigma_{\max}(M_0)=1$ by their definition. We invoke <Ref> and both bounds of <Ref> to obtain our results. For the upper bound, with probability at least $1-\epsilon$, we have for all $i\in[n]$

\begin{align}
\|MR(x_{2i-1}-x_{2i})\|&\leq\|R(x_{2i-1}-x_{2i})\|\\
&\leq\sup_{x,x'\in\mathcal X}\|R(x-x')\|\\
&\leq\diam(\mathcal X)\left(1+\sqrt{\frac{s(\mathcal X)}k}+\sqrt{\frac{2\ln\frac1\epsilon}k}\right).
\end{align}

For the lower bound, with probability at least $1-\epsilon$, we have for all $i\in[n]$

\begin{align}
\|MR(x_{2i-1}-x_{2i})\|&\geq\sigma_{\min}(M)\|R(x_{2i-1}-x_{2i})\|\\
&\geq\sigma_{\min}(M)\inf_{x,x'\in\mathcal X}\|R(x-x')\|\\
&\geq\sigma_{\min}(M)\diam(\mathcal X)\left(\sqrt{\frac k{k+1}}-\sqrt{\frac{s(\mathcal X)}k}-\sqrt{\frac{2\ln\frac1\epsilon}k}\right)_+.
\end{align}

For the second term, since $\sigma_{\max}(M_0)=1$, we have for all $i\in[n]$

\begin{equation}
0\leq\|M_0(x_{2i-1}-x_{2i})\|^2\leq\diam(\mathcal X)^2.
\end{equation}

Plugging the lower and upper bounds into (<ref>), and using the union bound again, we obtain, with probability at least $1-\epsilon$

\begin{multline}
\hat L^R_T(M)-\hat L_T(M_0)\leq\rho\diam(\mathcal X)^2\max\Bigg\{\left(1+\sqrt{\frac{s(\mathcal X)}k}+\sqrt{\frac{2\ln\frac2\epsilon}k}\right)^2,\\1-\sigma_{\min}(M)^2\left(\sqrt{\frac k{k+1}}-\sqrt{\frac{s(\mathcal X)}k}-\sqrt{\frac{2\ln\frac2\epsilon}k}\right)_+^2\Bigg\}.
\end{multline}

Since the first term inside the maximum is always greater than $1$, and the second is always lower, this simplifies to our desired result.


# Instrumental Broadening of the SPOL spectropolarimeter at the University of
Arizona

Alfredo Amador-Portes11affiliation: Instituto Nacional de Astrofísica, Óptica
y Electrónica, Luis Enrique Erro #1, Tonantzintla, Puebla, México, C.P. 72840.
Vahram Chavushyan11affiliationmark:  Victor M. Patiño-
Alvarez11affiliationmark:  22affiliation: Max-Planck-Institut für
Radioastronomie, Auf dem Hügel 69, D-53121 Bonn, Germany. Alfredo Amador-
Portes and Vahram Chavushyan: Instituto Nacional de Astrofísica, Óptica y
Electrónica, Luis Enrique Erro #1, Tonantzintla, Puebla, México, C.P. 72840
(aamador, vahram@inaoep.mx). Victor M. Patiño-Alvarez: Instituto Nacional de
Astrofísica, Óptica y Electrónica, Luis Enrique Erro #1, Tonantzintla Puebla,
México, C.P. 72840 (victorp@inaoep.mx), and Max-Planck-Institut für
Radioastronomie, Auf dem Hügel 69, D-53121 Bonn, Germany.

###### Abstract

The Ground-based Observational Support of the Fermi Gamma-ray Space Telescope
is conducted by the University of Arizona using the 2.3m Bok and 1.54m Kuiper
telescopes operated by the Steward Observatory (SO). This program monitors
blazar sources with spectroscopic (among others) observations. Yet, the
instrumental broadenings for the different slit widths used in the spectra,
are unavailable (the widths range from $2\farcs 0$ to $12\farcs 7$.). Using
quasi-simultaneous spectroscopic observations of the blazar 3C 273 between the
SO, Observatorio Astrofísico Guillermo Haro (OAGH), and Observatorio
Astronómico Nacional San Pedro Mártir (OAN-SPM), we can provide an estimation
of the instrumental profile for two of the slit widths. Since the instrumental
broadening and the slit width are directly proportional, we were able to
estimate the instrumental broadening for all six slit widths used at the SO.
We found significant variations between the instrumental profiles, emphasizing
the need to correct the instrumental broadening for each aperture.

El soporte de observaciones terrestres del telescopio espacial Fermi de rayos
gamma, es realizado por la Universidad de Arizona usando los telescopios Bok
de 2.3m y Kuiper de 1.54m, operado por el Observatorio Steward (SO). Este
programa monitorea fuentes blazares con observaciones espectroscópicas (entre
otras). Sin embargo, la información del perfil instrumental para diferentes
anchos de rendija usados en los espectros ópticos no está disponible (los
anchos van desde $2\farcs 0$ a $12\farcs 7$). Por lo que utilizando
observaciones de espectros cuasi-simultáneos del blazar 3C 273 entre el SO, el
Observatorio Astrofísico Guillermo Haro (OAGH) y el Observatorio Astronómico
Nacional San Pedro Mártir (OAN-SPM), se pudo determinar el ensanchamiento
instrumental para 2 anchos de rendija. Ya que el ancho instrumental y el ancho
de rendija son directamente proporcionales, fue posible estimar el ancho
instrumental para los seis anchos de rendija usados en el SO. Encontramos
variaciones significativas entre los perfiles instrumentales, lo que enfatiza
la necesidad de corregir el ensanchamiento instrumental para cada apertura.

Galaxies: Active Instrumental Broadening Quasars: Individual: 3C 273 Steward
Observatory: SPOL

##  0.1 Introduction

Since the launch of the Fermi Gamma-Ray Space Telescope, there have been
counterpart supporting monitoring programs in the entire electromagnetic
spectrum, from radio waves to X-rays (e.g. SMA, Gurwell et al., 2007; OVRO,
Richards et al., 2011, SMARTS; Bonning et al., 2012, Swift; Stroh & Falcone,
2013). In particular, we focus on the Ground-based Observational Support of
the Fermi Gamma-ray Space Telescope carried out at the University of Arizona
using the 2.3m Bok (Kitt Peak) and 1.54m Kuiper (Mt. Bigelow) telescopes
operated by the Steward Observatory (SO) (Smith et al., 2009)1112009 Fermi
Symposium, eConf Proceedings C091122. This is one of the most important
monitoring programs because it is the most complete public database of optical
spectroscopy, photometry, and polarimetry, for blazars, with the most number
of sources and best cadence of
observation222http://james.as.arizona.edu/~psmith/Fermi/. In this program, the
spectroscopic observations are conducted with the SPOL spectropolarimeter
which uses up to 6 configurations (apertures) corresponding to six different
slit widths (1=20, 2=30, 3=41, 4=51, 5=76, and 6=127). Smith et al. (2009)
also provides a spectral resolution range of $15-25\text{ \AA}$, depending on
the slit width chosen for the observation.

Unfortunately, the instrumental broadening for each slit width is not publicly
available, this has prevented us from studying the variability of the FWHM of
the broad emission lines present in Flat-Spectrum Radio Quasars (FSRQ), unlike
the study of flux variability previously done in various works for the Mg II
$\lambda 2798$ (León-Tavares et al., 2013; Chavushyan et al., 2020; Amaya-
Almazán et al., 2021), H$\beta$ (Fernandes et al., 2020), and C IV $\lambda
1549$ (Amaya-Almazán et al., 2022) emission lines.

FSRQ are a sub-type of blazars (Urry & Padovani, 1995) characterized by their
high variability across the entire electromagnetic spectrum (e.g. Aharonian et
al., 2007; Amaya-Almazán et al., 2021), with variations on very different time
scales, even in the same wavelength range (e.g. Fan et al., 2018; Gupta,
2018). When there is a flux increase well above the average emission, in a
very short time, we call these phenomena a flare; among AGNs, these are mostly
found in blazars. There is observational evidence that the emission line
flares in some blazars can be driven by non-thermal emission from the jet
(e.g. León-Tavares et al., 2013; Chavushyan et al., 2020; Amaya-Almazán et
al., 2021, 2022), so it is interesting to study if the emission line profile
also changes during these flares. Such a study could involve a detailed
analysis of emission lines during both quiescent and flaring states, aiming to
characterize any changes in emission line profiles, including shifts in peak
wavelength, changes in line width (FWHM), and alterations in profile
asymmetry.

The importance of monitoring the FWHM is that the emission lines provide
information about the kinematics and dynamics of the gas in the Broad-Line
Region (BLR) surrounding the central supermassive black hole (SMBH).
Therefore, understanding the characteristics of the BLR contributes to the
knowledge of accretion processes, and gravitational potential. For example,
SMBH mass estimation techniques like reverberation mapping (Blandford & McKee,
1982; Peterson, 1993), and single-epoch spectra (Greene & Ho, 2005; Kong et
al., 2006; Vestergaard & Peterson, 2006; Shaw et al., 2012), directly use this
parameter.

It is clear that obtaining and understanding the instrumental line profile is
a fundamental step in studying emission line variability in AGNs and other
astronomical sources, as it enables the separation of the intrinsic
characteristics of the source from instrumental effects, leading to more
accurate scientific conclusions. The observed profile ($\text{FWHM}_{obs}$) is
a convolution of both, the intrinsic profile of the source
($\text{FWHM}_{corr}$) and the instrumental profile ($\text{FWHM}_{inst}$,
also known as the spectral resolution). This convolution is typically
represented mathematically as a quadratic sum, shown in Equation 1.

$\text{FWHM}_{obs}^{2}=\text{FWHM}_{corr}^{2}+\text{FWHM}_{inst}^{2}$ (1)

Nalewajko et al. (2019) studied line width behavior without performing
correction for instrumental broadening, which yielded an inconclusive result.
This fact led to the establishment of techniques to counteract the lack of
knowledge of instrumental broadening for SO spectroscopic data. Zhang et al.
(2019) used a single value for $\text{FWHM}_{inst}$ estimated from other
spectroscopic observations (not quasi-simultaneous) to apply it to
observations with different slit widths. Rakshit (2020) used the same value
and applied it to the SO spectra with different slit widths. The latter can
lead to underestimation or overestimation of intrinsic emission line width in
a set of spectra with different slit widths. Even using only spectra taken
with a single slit width as in Pandey et al. (2022), FWHM measurements of
emission lines will be overestimated without instrumental broadening
correction. However, studies of the relative line width behavior can still be
done in this case.

A proper approach to this problem would be to use calibration lamps or night
sky lines to measure the instrumental profile. Unfortunately, as these
original data were not available, we had to use instead a different method.
Use spectra from the same source from an observatory with known instrumental
widths, selecting only observations quasi-simultaneous to the SO data (within
24 hours of each other), and taking into account the possible intra-day
variability (IDV) that Blazars can show (Gupta, 2018). Assuming that the
corresponding intrinsic line profile is the same in the spectra from both
observatories, we can use the quasi-simultaneous data to estimate the SO
instrumental profile. This procedure must be performed for each slit width
because they have different instrumental broadening.

The spectrograph resolution depends on a series of factors that we assume
remain unchanged in the observations made in the SO, with the exception of the
slit width. Hence, the spectral resolution (instrumental broadening) should be
proportional to this slit
width333http://james.as.arizona.edu/~psmith/SPOL/gratings.html
($\text{FWHM}_{inst}\propto\text{SW}$, e.g. Schroeder, 1974). Also, the ratio
between the widths of the slits will reflect the expected difference in
instrumental broadening.

##  0.2 Observational Data

We search for quasi-simultaneous observations between the SO, the OAGH
operated by the Instituto Nacional de Astrofísica, Óptica y
Electrónica444https://astro.inaoep.mx/observatorios/oagh/ (INAOE) and the OAN-
SPM operated by the Universidad Nacional Autónoma de
México555https://www.astrossp.unam.mx/es/ (UNAM), in which for the last two we
have knowledge of the instrumental profile used in every observation. The
instrument used in the OAGH and OAN-SPM observations is the Boller & Chivens
spectrograph. The best candidate for this analysis was the FSRQ blazar 3C 273,
due to the high number of observations, high S/N ratio in the spectral range
between 4000-7000 Å, it does not present telluric absorption lines around the
emission lines of interest, and finally, its redshift (0.158) allows for the
presence of a narrow emission line ([O III] $\lambda 5007\>\text{\AA}$), which
in AGNs, is not expected to vary significantly over a long period of time
(e.g. Shapovalova et al., 2001).

We made a further filter in the spectra set for all observatories by removing
spectra with a low S/N ratio. We end up with 5 spectra taken with a slit width
of 5.1 arcsec (SO), in which we have quasi-simultaneous data in the OAGH or
OAN-SPM, while there are 19 spectra taken with a slit width of 7.6 arcsec
(SO), with quasi-simultaneous data.

##  0.3 Data Analysis

As mentioned before, for the OAGH and OAN-SPM spectra the instrumental
broadening is known, because, for each object spectra, we take a comparison
lamp of He-Ar (OAGH) and Cu-Ne-He-Ar (OAN-SPM) that is used for wavelength
calibration. Therefore the spectrum of the comparison lamp uses the same setup
and light path as the spectrum of the blazar, this justifies using the width
of the lines in the comparison lamp as the instrumental broadening for the
object spectra correction. Hence, for each lamp spectrum, the FWHM of the non-
blended lines was measured. We estimated a mean value, with its error as the
quadratic sum of the standard deviation of the measurements and the dispersion
of the spectrum (Å/pixel).

For all the spectra, we left them in the observed frame because the
instrumental broadening is geometrical, i.e. a fixed value in pixels. We then
fitted a local continuum and subtracted it from the spectra. The spectral
features were fitted with Gaussian functions in the range from
$5500-5900\text{ \AA}$ which correspond to the H$\beta$ region in the observed
frame, and consequently, the emission lines fitted were H$\beta$ (with narrow,
broad, and very-broad components), [O III]$\lambda\lambda 4959,5007\text{
\AA}$ (with one Gaussian each), and the Fe II emission. The same multi-
Gaussian model was used in each pair of spectrum, allowing to vary only the
FWHM and amplitude. An example can be seen in Figure 1 where the pair of
spectra are normalized to the maximum flux of the H$\beta$ emission.

Figure 1: Example of spectral decomposition for the H$\beta$ region in the 3C
273 data (observed frame) Left Panel: Spectra from the SO database. Right
Panel: Spectra from OAGH. The spectra were taken within 24 hours of each
other.

All measurements in this paper were made using the [O III] $\lambda 5007$ Å
emission line, in the observed frame; which at the redshift of 3C 273, the
line is at 5798 Å. This line is produced in the Narrow-Line Region (NLR), and
due to its large size, they are not expected to change over large periods of
time because the ionizing radiation will respond more slowly (Shapovalova et
al., 2001, and references therein). Previous studies of IDV on 3C 273 mainly
focus on high-energy and optical bands and have not been reported for narrow
lines. However, as mentioned earlier we do not expect such fast variations in
narrow emission lines. An example of the low expected variations in this line
is presented in Yuan et al. (2022), where they calculated [O III] $\lambda
5007$ Å emission line flux. The variation between each day was always less
than the uncertainties that could be obtained from the spectra. Additionally
for each pair of spectra, if the multi-Gaussian model was not fitted with
similar amplitudes (taking into account that the width changes), then the
spectra pair was discarded to avoid possible IDV.

From all the measurements obtained, we estimate the intrinsic profile and
their uncertainty with error propagation for each quasi-simultaneous
observation. Assuming that the intrinsic profiles for each date on the spectra
of both observatories are the same (since they are quasi-simultaneous), we
were able to estimate the instrumental broadening of the SO spectra, using the
intrinsic profile widths obtained from OAGH and OAN-SPM, and the observed
profile widths measured in the SO spectra. We estimated a weighted mean for
the instrumental broadening measurements of the two slit widths we have
available and calculated the standard error of the weighted mean.

##  0.4 Results

This analysis shows us that the instrumental profile for the SO spectra for
the slit widths of 5.1, and 7.6 arcsec are $16.55\pm 4.43$, and $23.23\pm
1.79\text{ \AA}$, respectively. Given that the instrumental broadening should
be proportional to the slit width, we can take any of the instrumental
broadening measurements we have and obtain expected values for the
instrumental profiles of the other slit widths. This means that for any two
slit widths (e.g. $a$ and $b$) these values must satisfy
$\text{FWHM}_{inst}(a)/\text{FWHM}_{inst}(b)=\text{SW}(a)/\text{SW}(b)$. For
example, for the slit width of 4.1 (that we do not measure) and 7.6 (that we
do measure), the instrumental broadening for the former is calculated as
$\text{FWHM}_{4.1}=\text{FWHM}_{7.6}\times 4.1/7.6$.

Figure 2: Left Panel: Expected sets of instrumental profiles with their
uncertainties, measured using a 5.1 arcsec (navy blue squares and dotted
line), and a 7.6 arcsec (orange dots and dashed line) slit width as a
reference point. Observational measurements of instrumental broadening are
also shown (red diamonds). Right Panel: Instrumental broadening estimations
for all 6 slit widths based upon the mean of the two expected values for each
slit width.

Since we have two measurements of the instrumental broadening, we obtained two
sets of expected instrumental profiles, with their uncertainties, for all the
slit widths. The difference between the values obtained for each slit width is
most likely due to the uncertainties. We then calculated the mean of these two
values for each slit width as well as its errors. These different values of
instrumental broadening for each slit width are presented in Table 1.

In Figure 2 left panel we present the instrumental broadening obtained through
this analysis for the spectra taken with slit widths of 5.1 and 7.6 (red
diamonds), and the expected values estimated with both measurements (blue
squares and orange circles respectively). The final instrumental broadening
values for all the slit widths (green circles) are presented in Figure 2 right
panel.

Table 1: Instrumental broadening for each slit width of the SPOL at the SO.

5  Instrumental Broadening (Å) Slit Width (arcsec) Expected Values Final
Values From 5.1 arcsec From 7.6 arcsec 2.0 $6.49\pm 1.74$ $6.11\pm 0.47$
$6.30\pm 1.80$ 3.0 $9.74\pm 2.61$ $9.17\pm 0.71$ $9.45\pm 2.70$ 4.1 $13.31\pm
3.57$ $12.53\pm 0.97$ $12.92\pm 3.69$ 5.1 $16.55\pm 4.44$ $15.59\pm 1.20$
$16.07\pm 4.59$ 7.6 $24.67\pm 6.61$ $23.23\pm 1.79$ $23.95\pm 6.85$ 12.7
$41.22\pm 11.04$ $38.82\pm 2.99$ $40.02\pm 11.44$

##  0.5 Conclusions

We have estimated the instrumental broadening for the six different slit
widths used in the spectroscopic observations carried out by the Steward
Observatory666http://james.as.arizona.edu/~psmith/Fermi/, and the results are
presented in Table 1. Notably, there is a significant difference in
instrumental broadening across the different slit widths (which is expected),
with the ratio between the maximum and minimum broadening being approximately
6.35 times. This highlights the importance of considering distinct
instrumental broadening values for each slit width. Using a fixed or mean
instrumental broadening for all slit widths will lead to an overestimation for
smaller slit widths and an underestimation for the larger ones. Even when
using mean and root mean square (rms) spectra with multiple slit widths, it is
not correct to use a single instrumental broadening value, because the
resulting spectra would still retain broadening information from all the slit
widths, and it is strongly dependent on the most used setup.

##  0.6 Acknowledgments

We thank the anonymous referee for the constructive comments that helped to
improve the manuscript. A.A.-P. acknowledges support from the CONAHCYT
(Consejo Nacional de Humanidades, Ciencia y Tecnología) program for Ph.D.
studies. This work was supported by CONAHCYT research grants 280789 and
320987. In addition, this work was supported by the Max Plank Institute for
Radioastronomy (MPIfR) - Mexico Max Planck Partner Group led by V.M.P.-A. Data
from the Steward Observatory spectropolarimetric monitoring project were used.
This program is supported by Fermi Guest Investigator grants NNX08AW56G,
NNX09AU10G, NNX12AO93G, and NNX15AU81G. This publication is based on data
collected at the Observatorio Astrofísico Guillermo Haro (OAGH), Cananea,
Sonora, Mexico, operated by the Instituto Nacional de Astrofísica, Óptica y
Electrónica (INAOE). Funding for the OAGH has been provided by CONAHCYT. This
paper is based upon observations carried out at the Observatorio Astronómico
Nacional on the Sierra San Pedro Mártir (OAN-SPM), Baja California, México.

## References

  * Aharonian et al. (2007) Aharonian, F., Akhperjanian, A. G., Bazer-Bachi, A. R., et al. 2007, ApJ, 664, L71. doi:10.1086/520635
  * Amaya-Almazán et al. (2021) Amaya-Almazán, R. A., Chavushyan, V., & Patiño-Álvarez, V. M. 2021, ApJ, 906, 5. doi:10.3847/1538-4357/abc689
  * Amaya-Almazán et al. (2022) Amaya-Almazán, R. A., Chavushyan, V., & Patiño-Álvarez, V. M. 2022, ApJ, 929, 14. doi:10.3847/1538-4357/ac5741
  * Blandford & McKee (1982) Blandford, R. D. & McKee, C. F. 1982, ApJ, 255, 419. doi:10.1086/159843
  * Bonning et al. (2012) Bonning, E., Urry, C. M., Bailyn, C., et al. 2012, ApJ, 756, 13. doi:10.1088/0004-637X/756/1/13
  * Chavushyan et al. (2020) Chavushyan, V., Patiño-Álvarez, V. M., Amaya-Almazán, R. A., and Carrasco, L., 2020, ApJ, 891, 68. doi:10.3847/1538-4357/ab6ef6
  * Fan et al. (2018) Fan, J. H., Tao, J., Liu, Y., et al. 2018, AJ, 155, 90. doi:10.3847/1538-3881/aaa547
  * Fernandes et al. (2020) Fernandes, S., Patiño-Álvarez, V. M., Chavushyan, V., et al. 2020, MNRAS, 497, 2066. doi:10.1093/mnras/staa2013
  * Greene & Ho (2005) Greene, J. E. & Ho, L. C. 2005, ApJ, 630, 122. doi:10.1086/431897
  * Gupta (2018) Gupta, A. 2018, Galaxies, 6, 1. doi:10.3390/galaxies6010001
  * Gurwell et al. (2007) Gurwell, M. A., Peck, A. B., Hostler, S. R., et al. 2007, From Z-Machines to ALMA: (Sub)Millimeter Spectroscopy of Galaxies, 375, 234
  * Kong et al. (2006) Kong, M.-Z., Wu, X.-B., Wang, R., et al. 2006, Chin. J. Astron. Astrophys, 6, 396. doi:10.1088/1009-9271/6/4/02
  * León-Tavares et al. (2013) León-Tavares, J., Chavushyan, V., Patiño-Álvarez, V., et al. 2013, ApJ, 763, L36. doi:10.1088/2041-8205/763/2/L36
  * Nalewajko et al. (2019) Nalewajko, K., Gupta, A. C., Liao, M., et al. 2019, A&A, 631, A4. doi:10.1051/0004-6361/201935904
  * Pandey et al. (2022) Pandey, S., Rakshit, S., Woo, J.-H., et al. 2022, MNRAS, 516, 2671. doi:10.1093/mnras/stac2418
  * Patiño Álvarez et al. (2016) Patiño Álvarez, V., Torrealba, J., Chavushyan, V., et al. 2016, Frontiers in Astronomy and Space Sciences, 3, 19. doi:10.3389/fspas.2016.00019
  * Peterson (1993) Peterson, B. M. 1993, PASP, 105, 247. doi:10.1086/133140
  * Rakshit (2020) Rakshit, S. 2020, A&A, 642, A59. doi:10.1051/0004-6361/202038324
  * Richards et al. (2011) Richards, J. L., Max-Moerbeck, W., Pavlidou, V., et al. 2011, arXiv:1111.0318. doi:10.48550/arXiv.1111.0318
  * Shapovalova et al. (2001) Shapovalova, A. I., Burenkov, A. N., Carrasco, L., et al. 2001, A&A, 376, 775. doi:10.1051/0004-6361:20011011
  * Shaw et al. (2012) Shaw, M. S., Romani, R. W., Cotter, G., et al. 2012, ApJ, 748, 49. doi:10.1088/0004-637X/748/1/49
  * Schroeder (1974) Schroeder, D. J. 1974, Astrophysics. Part A: Optical and infrared, 463
  * Smith et al. (2009) Smith, P. S., Montiel, E., Rightley, S., et al. 2009, Fermi Symposium, eConf Proceedings C091122, arXiv:0912.3621. doi:10.48550/arXiv.0912.3621
  * Stroh & Falcone (2013) Stroh, M. C. & Falcone, A. D. 2013, ApJS, 207, 28. doi:10.1088/0067-0049/207/2/28
  * Urry & Padovani (1995) Urry, C. M. & Padovani, P. 1995, PASP, 107, 803. doi:10.1086/133630
  * Vestergaard & Peterson (2006) Vestergaard, M. & Peterson, B. M. 2006, ApJ, 641, 689. doi:10.1086/500572
  * Yuan et al. (2022) Yuan, Y. H., Zheng, Y. G., Fan, J. H., et al. 2022, PASP, 134, 044102. doi:10.1088/1538-3873/ac5b88
  * Zhang et al. (2019) Zhang, Z.-X., Du, P., Smith, P. S., et al. 2019, ApJ, 876, 49. doi:10.3847/1538-4357/ab1099