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.