1
$\begingroup$

I know there are many ways to compute similarity of two different non-zero vectors but is it possible to get a list of nearest vectors whose values are continous given a single continous vector.

Lets take these two vectors

a = [1, 1, 1, 1, 0, 0, 0, 0, 0]
b = [0, 0, 1, 1, 1, 1, 0, 0, 0]

I know that cosine similarity of these two vectors is 0.5. Is it possible to find about 20 vectors with a cosine similarity of 0.9 nearest to a vector alone.

$\endgroup$
2
  • $\begingroup$ are you talking about binary vectors only? $\endgroup$
    – gunes
    Nov 26, 2019 at 10:57
  • $\begingroup$ no but vecotrs with continous values $\endgroup$
    – Eka
    Nov 26, 2019 at 13:03

1 Answer 1

1
$\begingroup$

In continuous setting, it's not possible to find the closest $n$ vectors. Consider the simpler case where you want to find the closest only, and assume we have only one dimension, e.g. real numbers. For example, you can't find the closest number to $3$ (other than itself). Let's say the number you propose as the closest is something like $3+\epsilon$; then $3+\epsilon/2$ will be a closer number.

In binary setting, you can find such vectors, at least by brute force.

However, you can find a vector with desired cosine similarity, i.e. $\cos \theta$, by employing the following method (let your initial vector be $x$):

  • First find a perpendicular unit vector to $x$, call it $y$.
  • Find $\tan\theta$ from $\cos\theta$
  • Calculate $z=x+y||x||\tan\theta $, which has the desired cosine similarity.
$\endgroup$
6
  • $\begingroup$ Can we at least estimate values at "discrete" locations say a vector at cos similarity 0.1 should be entirely different from 0.9. using that logic is it possible to get vectors near 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9 $\endgroup$
    – Eka
    Nov 26, 2019 at 13:38
  • 1
    $\begingroup$ If $a,b$ has cosine distance $0.1$, so as $a,kb$, where $k>0$ is a scalar, which means there are infinite number of possibilities at equal distance. $\endgroup$
    – gunes
    Nov 26, 2019 at 13:43
  • $\begingroup$ I understood that its infinite but what am I asking is whether its theortically possible to sample from those locations. $\endgroup$
    – Eka
    Nov 26, 2019 at 13:47
  • $\begingroup$ Yes, you can. I've added a method. $\endgroup$
    – gunes
    Nov 26, 2019 at 14:49
  • 1
    $\begingroup$ There are various ways, we just need a vector satisfying $x^Ty=0$. Put random numbers to the $n-1$ of the positions, and solve for the last, e.g. if $x=[3,5,2]$, then let $y=[1,1,a]$. $x^Ty=3+5+2a=0\rightarrow a=-4$. If the corresponding index in $x$ is $0$, then choose a non-zero index. $\endgroup$
    – gunes
    Nov 27, 2019 at 6:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.