Computational Science Stack Exchange is a question and answer site for scientists using computers to solve scientific problems. It only takes a minute to sign up.
Sign up to join this community
Suppose I have a set of $N$ points of shape $N \times D$, where $D$ is the dimensionality. I want to compute the average Euclidean distance between all points, as well as additional moments such as the variance, median, and percentile boundaries.
Is there a way to calculate or estimate these quantities without finding the full $N \times N$ distance matrix? I am hoping for a solution that requires less than $\mathcal{O}(N^2)$ memory.
You can do this in $\mathcal{O}(N)$ time (and memory) using a fast multipole algorithm that can handle nondecaying kernel functions such as the distance function $d(\mathbf{x},\mathbf{y})=|\mathbf{x}-\mathbf{y}|$.
The average distance is given by $\frac{1}{N^2}\sum_{i=1}^{N}\sum_{j=1}^{N} d(\mathbf{x}_i,\mathbf{x_j})$. The inner sum can be evaluated at each $\mathbf{x}_i,i=1,\ldots,N$ in a total of $\mathcal{O}(N)$ time, and the outer sum over $i$ can also be computed in $\mathcal{O}(N)$ time.
I'd recommend the use of the black-box FMM code here: https://github.com/ruoxi-wang/BBFMM3D.
When calculating averages, you can iterate through all point connections and carry a counter, and the sum of the distances. You can overwrite any individual distance with the new ones. That way your memory footprint is minimal.
