A Similarity Metric Based on the Rearrangement Inequality

基于排序不等式的相似度指标 苏剑林 · 2026-07-16 · Mathematics inequality semantic similarity

Yesterday I saw @Ji_Ha_Kim sharing an interesting paper, Beyond Cosine Similarity, which proposes building a new, looser similarity metric based on the rearrangement inequality. After reading it I found it quite interesting, so here's a quick write-up.

Cosine Similarity

For two vectors $\boldsymbol{x},\boldsymbol{y}\in\mathbb{R}^d$, a commonly used normalized similarity metric is cosine similarity:

\begin{equation}\cos(\boldsymbol{x},\boldsymbol{y}) = \frac{\boldsymbol{x}\cdot \boldsymbol{y}}{\Vert\boldsymbol{x}\Vert\, \Vert\boldsymbol{y}\Vert} \in [-1, 1]\end{equation}

Setting aside its geometric meaning, from a purely algebraic point of view cosine similarity is a normalized inner product built on top of the Cauchy–Schwarz inequality

\begin{equation}-\Vert\boldsymbol{x}\Vert\, \Vert\boldsymbol{y}\Vert \leq \boldsymbol{x}\cdot \boldsymbol{y}\leq \Vert\boldsymbol{x}\Vert\, \Vert\boldsymbol{y}\Vert\end{equation}more

When $\cos(\boldsymbol{x},\boldsymbol{y})=\pm 1$, this means there exists $k > 0$ such that $\boldsymbol{y} = \pm k\boldsymbol{x}$, which shows that cosine similarity is insensitive to magnitude — it measures the degree of similarity in direction between two vectors, or in other words their degree of linear correlation. In particular, from the AM–GM inequality we have $\Vert\boldsymbol{x}\Vert\, \Vert\boldsymbol{y}\Vert \leq \frac{1}{2}(\Vert\boldsymbol{x}\Vert^2 + \Vert\boldsymbol{y}\Vert^2)$, and substituting this into the Cauchy–Schwarz inequality to loosen it further gives

\begin{equation}-\frac{1}{2}(\Vert\boldsymbol{x}\Vert^2 + \Vert\boldsymbol{y}\Vert^2) \leq \boldsymbol{x}\cdot \boldsymbol{y} \leq \frac{1}{2}(\Vert\boldsymbol{x}\Vert^2 + \Vert\boldsymbol{y}\Vert^2)\end{equation}

The first equality holds under the condition $\boldsymbol{x}=-\boldsymbol{y}$, and the second equality holds under the condition $\boldsymbol{x}=\boldsymbol{y}$. From this we can define a new normalized inner product

\begin{equation}\newcommand{dcos}{\mathop{\text{dcos}}}\dcos(\boldsymbol{x},\boldsymbol{y}) = \frac{\boldsymbol{x}\cdot \boldsymbol{y}}{\frac{1}{2}(\Vert\boldsymbol{x}\Vert^2 + \Vert\boldsymbol{y}\Vert^2)}\end{equation}

in which case $\dcos(\boldsymbol{x},\boldsymbol{y}) = \pm 1 \Leftrightarrow \boldsymbol{x}=\pm\boldsymbol{y}$, i.e., $\dcos$ is a metric of the degree to which two vectors are fully identical.

The Rearrangement Inequality

For the inner product $\boldsymbol{x}\cdot \boldsymbol{y}$, the rearrangement inequality also holds:

\begin{equation}\boldsymbol{x}^{\downarrow}\cdot \boldsymbol{y}^{\uparrow}=\boldsymbol{x}^{\uparrow}\cdot \boldsymbol{y}^{\downarrow}\leq \boldsymbol{x}\cdot \boldsymbol{y} \leq \boldsymbol{x}^{\uparrow}\cdot \boldsymbol{y}^{\uparrow} = \boldsymbol{x}^{\downarrow}\cdot \boldsymbol{y}^{\downarrow}\end{equation}

Here $\boldsymbol{x}^{\downarrow},\boldsymbol{x}^{\uparrow}$ denotes the new vector obtained by sorting the components of $\boldsymbol{x}$ in descending/ascending order (similarly for $\boldsymbol{y}$); put simply, "reverse-order inner product ≤ shuffled-order inner product ≤ same-order inner product." The first equality holds when $\boldsymbol{x},\boldsymbol{y}$ are in complete reverse order, i.e., $(x_i - x_j)(y_i - y_j)\leq 0$ holds for all $i,j$; the second equality holds when $\boldsymbol{x},\boldsymbol{y}$ are in complete matching order, i.e., $(x_i - x_j)(y_i - y_j)\geq 0$.

Clearly, reordering does not change the norm, i.e., $\Vert\boldsymbol{x}^{\downarrow}\Vert=\Vert\boldsymbol{x}^{\uparrow}\Vert=\Vert\boldsymbol{x}\Vert$, so combining this further with the Cauchy–Schwarz inequality gives

\begin{equation}-\Vert\boldsymbol{x}\Vert\, \Vert\boldsymbol{y}\Vert \leq \boldsymbol{x}^{\uparrow}\cdot \boldsymbol{y}^{\downarrow}\leq \boldsymbol{x}\cdot \boldsymbol{y} \leq \boldsymbol{x}^{\uparrow}\cdot \boldsymbol{y}^{\uparrow} \leq \Vert\boldsymbol{x}\Vert\, \Vert\boldsymbol{y}\Vert\end{equation}

This shows that, for $\boldsymbol{x}\cdot \boldsymbol{y}$, the rearrangement inequality is tighter than the Cauchy–Schwarz inequality. The standard proof of the rearrangement inequality uses a local-adjustment argument, starting from the identity

\begin{equation}(x_i - x_j)(y_i - y_j) = (x_i y_i + x_j y_j) - (x_i y_j + x_j y_i)\end{equation}

The first term on the right-hand side is the inner product of $(x_i, x_j)$ and $(y_i, y_j)$, and the second term is the inner product after swapping $x_i,x_j$ or $y_i,y_j$. If $x_i > x_j$ and $y_i > y_j$ (same order), then the left-hand side is greater than 0, meaning that swapping from matching order into reverse order decreases the inner product. It follows that the maximum is attained when everything is in fully matching order, and by the same reasoning the minimum is attained when everything is in fully reversed order.

Rearrangement Similarity

Given that $l(\boldsymbol{x},\boldsymbol{y})\leq \boldsymbol{x}\cdot \boldsymbol{y} \leq u(\boldsymbol{x},\boldsymbol{y})$ holds and both equalities are attainable on either side, we can, in general, construct a similarity metric

\begin{equation}2\cdot\frac{\boldsymbol{x}\cdot \boldsymbol{y} - l(\boldsymbol{x},\boldsymbol{y})}{u(\boldsymbol{x},\boldsymbol{y}) - l(\boldsymbol{x},\boldsymbol{y})} - 1 = \frac{2\cdot\boldsymbol{x}\cdot \boldsymbol{y} - l(\boldsymbol{x},\boldsymbol{y}) - u(\boldsymbol{x},\boldsymbol{y})}{u(\boldsymbol{x},\boldsymbol{y}) - l(\boldsymbol{x},\boldsymbol{y})} \in [-1, 1]\end{equation}

Substituting into the rearrangement inequality gives

\begin{equation}\newcommand{rcos}{\mathop{\text{rcos}}}\rcos(\boldsymbol{x},\boldsymbol{y}) = \frac{2\cdot\boldsymbol{x}\cdot \boldsymbol{y} - \boldsymbol{x}^{\uparrow}\cdot\boldsymbol{y}^{\downarrow} - \boldsymbol{x}^{\uparrow}\cdot\boldsymbol{y}^{\uparrow}}{\boldsymbol{x}^{\uparrow}\cdot\boldsymbol{y}^{\uparrow} - \boldsymbol{x}^{\uparrow}\cdot\boldsymbol{y}^{\downarrow}}\end{equation}

so $\rcos(\boldsymbol{x},\boldsymbol{y})=1$ means that $\boldsymbol{x},\boldsymbol{y}$ are in complete matching order, and $\rcos(\boldsymbol{x},\boldsymbol{y})=-1$ means that $\boldsymbol{x},\boldsymbol{y}$ are in complete reverse order. If cosine similarity describes the degree of linear correlation, then $\rcos$ describes, to some extent, a form of nonlinear correlation. $\rcos$ is invariant under translation and positive scaling, i.e.,

\begin{equation}\rcos(a \boldsymbol{x} + b\boldsymbol{1},c\boldsymbol{y} + d\boldsymbol{1})=\rcos(\boldsymbol{x},\boldsymbol{y})\end{equation}

but this is not true in general for arbitrary component-wise strictly monotonic transformations (such as component-wise cubing), meaning that $\rcos$ retains and makes use of the actual magnitudes of the values, rather than relying purely on rank order.

Connections and Differences

It should be pointed out that, although this post was inspired by Beyond Cosine Similarity, the rearrangement similarity constructed here differs slightly from the one in the original paper. The original paper's construction is ($\newcommand{recos}{\mathop{\text{recos}}}\recos$ is also the original paper's notation)

\begin{equation}\recos(\boldsymbol{x},\boldsymbol{y}) = \frac{\boldsymbol{x}\cdot\boldsymbol{y}}{|\boldsymbol{x}^{\uparrow}\cdot\boldsymbol{y}^{\updownarrow}|},\qquad \boldsymbol{y}^{\updownarrow} = \begin{cases}\boldsymbol{y}^{\uparrow}, & \boldsymbol{x}\cdot\boldsymbol{y} > 0\\ \boldsymbol{y}^{\downarrow}, & \boldsymbol{x}\cdot\boldsymbol{y} < 0\end{cases}\end{equation}

That is, it selects the same-order or reverse-order bound according to the sign of the inner product. While this definition also confines the result to $[-1,1]$, the sign of the inner product in this case can no longer be used to distinguish same order from reverse order, which in my personal opinion makes it less well-motivated than the definition proposed here.

Here's an example: $\boldsymbol{x}=(1,2,3), \boldsymbol{y}=(6,5,4)$ — these two vectors are in complete reverse order, and intuitively a rearrangement similarity metric ought to give at least a negative value in this case. But clearly $\recos(\boldsymbol{x},\boldsymbol{y})$ gives a positive result, whereas $\rcos(\boldsymbol{x},\boldsymbol{y})$ does give a negative result. The definition proposed here directly normalizes using the two-sided bounds of the rearrangement inequality, letting $\pm 1$ anchor complete matching order and complete reverse order respectively, which I think is more semantically sensible.

Of course, which of $\rcos$ or $\recos$ is more reasonable in actual applications depends on the specific scenario; the claim of "more reasonable" made here is only with respect to what the term "rearrangement similarity" ought to mean.

Rank Correlation Coefficient

If we treat $\boldsymbol{x},\boldsymbol{y}$ as a collection of two-dimensional data points $(x_1,y_1),(x_2,y_2),\cdots$, then cosine similarity is related to their linear correlation coefficient (Pearson correlation coefficient)]:

\begin{equation}\mathop{\text{pearson}}(\boldsymbol{x}, \boldsymbol{y}) = \cos(\boldsymbol{x}-\bar{\boldsymbol{x}}, \boldsymbol{y}-\bar{\boldsymbol{y}})\end{equation}

where $\bar{\boldsymbol{x}},\bar{\boldsymbol{y}}$ is the mean of the components of $\boldsymbol{x}, \boldsymbol{y}$. Building on the linear correlation coefficient, we get the rank correlation coefficient (Spearman's rank correlation coefficient)]:

\begin{equation}\mathop{\text{spearman}}(\boldsymbol{x}, \boldsymbol{y}) = \mathop{\text{pearson}}(\boldsymbol{r}_x, \boldsymbol{r}_y)\end{equation}

Here $\boldsymbol{r}_x,\boldsymbol{r}_y$ are respectively the rank vectors of $\boldsymbol{x}, \boldsymbol{y}$, meaning that if $x_i$ is the $k$-th smallest component of $\boldsymbol{x}$, then $(\boldsymbol{r}_x)_i=k$. By definition, the rank correlation coefficient completely ignores the actual magnitudes of the data and cares only about their ordering — we made use of this metric earlier when evaluating semantic similarity]. Interestingly, the rank correlation coefficient can also be viewed as a special case of $\rcos$:

\begin{equation}\mathop{\text{spearman}}(\boldsymbol{x}, \boldsymbol{y}) = \rcos(\boldsymbol{r}_x, \boldsymbol{r}_y)\end{equation}

I'll leave the verification of this identity to the reader and won't go into it here. From this, $\rcos(\boldsymbol{x}, \boldsymbol{y})$ can be seen as a generalized rearrangement similarity that retains the original numerical information.

In a Nutshell

This post has introduced the idea of building similarity metrics from the perspective of "similarity = normalized inner product," based on two-sided inequalities involving inner products, with particular focus on the rearrangement similarity metric constructed from the rearrangement inequality.