# Similarity metrics for more than two vectors?

I am aware of Cosine Similarity which measure the angle between "two" vectors. Prototype for cosine similarity would look something like this:

float cosine_similarity(vector<float> a, vector<float> b);


Are there any similarity measures that measure the similarity between "n" vectors? Prototype of this function would look something like this:

float cosine_similarity(vector<vector<float>> vectors);


PS: I am NOT looking for clustering/classification sort of a thing.

I will appreciate if someone can point out in some direction.

Thanks!

• Would you like a single number to represent the similarity among all the samples in a group? What should this value signify in your case? The purity of the group? Or perhaps an average of all pairwise cosine similarities? Commented Oct 7, 2016 at 22:36
• If you start to look at all pairwise cosine similarities, then this falls under a standard class of "linear dependence" metrics. This suggests a natural possibility could be linear dimension reduction techniques. Commented Oct 8, 2016 at 2:54
• @GeoMatt22 could you please elaborate? Commented Oct 8, 2016 at 7:37
• @user115202 yeah I'd like for it to be a single number but definitely more sophisticated than an average of cosine similarities. Commented Oct 8, 2016 at 7:38
• @user3667569 there are many variants, and the best choice will vary depending on your data and goals. However, the basic idea is do an SVD on a data matrix of your vectors. A simple example would be to use the ratio of the first singular value and the matrix norm, which is similar to an $R^2$, giving the "fraction of variance explained", a number between 0 and 1. (PageRank is similar.) Commented Oct 8, 2016 at 8:30

The cosine similarity between two column vectors $$x_1$$ and $$x_2$$ is simply the dot product between their unit vectors $$\mathrm{CosSim}[x_1,x_2]=\frac{x_1}{\|x_1\|}\bullet\frac{x_2}{\|x_2\|}$$ and varies from -1 to +1, similar to a correlation coefficient $$R$$ (to which it is closely related).

There are many ways to generalize this idea to a set of $$n$$ vectors, but as requested in the comments, here I will expand on one possibility, related to the idea of (linear) dimensionality reduction.

First, in the $$n=2$$ case, we can think of $$R^2\in[0,1]$$ as the "fraction of the variance explained" by a linear regression. For the squared cosine similarity, a similar interpretation is possible, except the associated regression has no "intercept term" (i.e. the vectors are scaled, but not centered).

In the $$n$$ dimensional case, we can concatenate the vectors into a matrix $$X=\begin{bmatrix}x_1 \, \ldots \, x_n\end{bmatrix}$$ analogous to the cosine similarity case, we can consider dot products based on the scaled matrix $$Y=\begin{bmatrix}y_1 \, \ldots \, y_n\end{bmatrix}$$ assembled from the corresponding unit vectors $$y_i=\frac{x_i}{\|x_i\|}$$ In general we could then conduct varying analyses on the "correlation matrix" $$Y^TY$$, including dimension reduction via PCA.

The general idea here is to create a low-rank approximation to the matrix $$Y$$ by truncating its singular value decomposition (SVD). Mathematically, we have $$Y=USV^T=\sum_{k=1}^n\sigma_ku_kv_k^T$$ where the singular values $$\sigma_1,\ldots,\sigma_n$$ are non-negative and arranged in decreasing order. (For simplicity I am assuming that for $$x_i\in\mathbb{R}^m$$ the number of vectors is at least $$n\geq m$$. Otherwise the sum will have $$m$$ terms.) If we truncate the sum at $$K, then we get a "rank $$K$$ approximation" $$\hat{Y}_K$$ to the matrix $$Y=\hat{Y}_n$$. The truncated SVD is optimal in the sense that it minimizes the Frobenius norm of the reconstruction error $$\|\hat{Y}_K-Y\|_F^2$$.

The squared Frobenius norm is just the sum of the squares of all the entries of a matrix. In particular, for the scaled matrix $$Y$$ we will always have $$\|Y\|_F^2=n$$ For any matrix, the Frobenius norm is also equal to the sum of the squares of the singular values. In particular, for the $$K$$-rank approximation $$\hat{Y}_K$$ we have $$\|\hat{Y}_K\|_F^2=\sum_{k=1}^K\sigma_k^2$$ So we can define an "order $$K$$ coefficient of determination" as $$R_K^2\equiv\frac{\|\hat{Y}_K\|_F^2}{\|Y\|_F^2}\in[0,1]$$

A simple option would be to just use the first singular value, i.e. $$R_1^2\equiv\frac{\sigma_1^2}{n}$$ The maximum similarity would be for $$n$$ parallel vectors (i.e. scalar multiples of a single vector), giving $$R_1^2=1$$. The minimum similarity would be for $$n$$ orthogonal vectors, giving $$R_1^2=\frac{1}{n}$$.

A few final notes:

• The first singular value $$\sigma_1$$ can be computed via an iterative method, so no detailed SVD need be computed. (Similar to PageRank; e.g. svds(Y,1) in Matlab.)
• To get a similarity that can range over the entire [0,1] interval, you could simply normalize, i.e. $$\hat{R}_1^2\equiv\frac{\sigma_1^2-1}{n-1}$$
• So in Matlab the similarity function could be defined via CosSimN = @(Y) (svds(Y,1)^2-1)/(size(Y,2)-1), if we assume that $$Y$$ is already available as input.
• For $$n=2$$ the above will reduce to the absolute value of the standard cosine similarity.
• thank you for your elaborate answer. Does the equation CosSimN = @(Y) (svds(Y,1)^2-1)/(size(Y,2)-1) also hold for n > 2 and possibly negative data? If not, is there a way to support negative data? Commented Dec 10, 2020 at 13:12
• @D.Phi sorry for the confusion. My proposed $n$-vector similarity measure $\hat{R}_1^2$ can be applied to any collection of vectors. (The only limitation is that no vector is entirely zeros, which also applies to cosine similarity.) For the special case of $n=2$, the result will just be the absolute value of the cosine similarity. So $n > 2$ and negative data are no problem. Commented Dec 10, 2020 at 17:44
• Thanks, I appreciate your answer. I implemented your code and found an error. You divide by the column count of Y instead of n (which is row count * column count). Here is the code which works for me: CosSimN = @(Y) (svds(Y,1)^2-1) / (prod(size(Y)) - 1) Commented Dec 14, 2020 at 19:11
• I've noticed that your proposed formula does not work well on vectors with many zeros. E.g. if Y = [[1,0,0],[1,0,0],[1,0,0]], then CosSimN(Y) = 0.25, even though it should be 1. Is there a benefit to this approach in comparison to the average of pairwise cosine similarities? Commented Dec 14, 2020 at 19:53
• @D.Phi as for the size: As noted in my answer, the sum of squares of singular values by definition equals the sum of squares of the matrix entries (squared Frobenius norm). If you input a $Y$ with normalized (unit-vector) columns, then the sum of squares of $Y$'s entries will be the number of columns. This is the max you can get for the square of $Y$'s first singular value. (If you do not normalize the columns first, this would not hold.) As for "What is the benefit of this approach?", as I mentioned in my initial comment to OP, this is simply one plausible approach to generalizing CosSim. Commented Dec 14, 2020 at 20:19