# efficient "dot" product of two sparse vectors with uncertainty

I'm interested in extensions or analogs of the vector dot product that apply to sparse vectors in the case of uncertainty in the abscissa.

The vectors I deal with are often of large (100,000 or 1,000,000 or more) dimension. The "dimensions" are just distinct non-overlapping bins of the real-number line. Thus, a non-sparse data vector $\mathbf y$ would consist of $n$ elements $y_i$. The $y_i$ are ordered, where (for example) $y_i$ represents binned signal intensity for $0<x\le 1$, ..., and $y_{1000000}$ represents binned signal intensity for $999999<x\le1000000$.

The data are sparse:very few of the $y_i$ for any given $\mathbf y$ are non-zero. However the value of $i$ for which a given non-zero value occurs is not known exactly, only an approximate value of $i$ is known. Thus perhaps a better description of each data vector $\mathbf y$ is a small number (10 to 100) of $(x_j, y_j)$ pairs, where $x_j$ is not known exactly, is assumed to be normally distributed with mean $x_j$ and standard deviation $\delta$. $\delta$ can be assumed to be independent of $j$, i.e. every $x_j$ has the same uncertainty.

My goal is to efficiently compute a dot product, or something like it, for two different sparse vectors of this type. So $\mathbf y$ is represented by $m$ points of the form $(x_j, y_j)$, and $\mathbf z$ is represented by $m^\prime$ points of the form $(x_k, z_k)$. The uncertainty of every $x_k$ and $x_j$ is $\delta$.

One (inefficient!) way to proceed is (i) convert these sparse vectors to dense vectors, then (2) convolve the dense vectors with a gaussian kernel having standard deviation $\delta$, and then (3) calculate the traditional dot product on the convolved dense vectors.

I've been googling "sparse dot product" and "sparse dot product with uncertainty" and similar things without much luck. Is there a better way to accomplish this calculation, especially one that can maintain the sparsity? Can anyone give me pointers towards better terminology or relevant literature?

(I hope this question is on-topic here at CV.se; I think it fits here better than the other SE sites I follow.)

• May I ask the computing environment you are using. Feb 8, 2016 at 18:19
• I use both R 3.2.3 and python 2.7 regularly. Back when I wrote this question, Python 2.7. Feb 8, 2016 at 18:20

You don't need to convert to dense vectors to do the convolution. Each pair of points $((x_j,y_j),(x_k',y_k'))$ (first point from $\mathbf y$, second from $\mathbf z$) contributes $y_jy_k'\exp\left[-(x_j-x_k')^2/(4\delta^2)\right]/(2\delta\sqrt{\pi})$ to the dot product, so you can just analytically sum this over all $j$ and $k$. If $\mathcal{O}(m^2)$ is too computationally intense for you, you can restrict to $(j,k)$ pairs such that $x_j$ and $x_k'$ are within (say) $10\delta$ of each other to bring it down to $\mathcal{O}(m)$.