efficient "dot" product of two sparse vectors with uncertainty

Question

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.)

Answer 1

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)$.

EDIT: You might want to use a different formula for the contribution of a pair of points, depending on exactly how you want your dot product to behave, but the basic idea that you can independently calculate the contribution from any pair of points and can restrict to pairs of points within some range of each other should be general.