Timeline for Concentration of sum of pairwise squared Euclidean distances of random vectors
Current License: CC BY-SA 3.0
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 17, 2014 at 20:51 | answer | added | Marsu_ | timeline score: 5 | |
| Apr 1, 2014 at 8:52 | comment | added | guest | Suppose your points were instead on the surface the ball, say by projecting them outwards. This is much the same question for large d. However now the distances are pairwise uncorrelated, so var(f) is O(1/n^2). Have you computed correlations between distances and hence the variance in your case? | |
| Apr 1, 2014 at 0:35 | answer | added | niche | timeline score: 2 | |
| Mar 18, 2013 at 17:04 | comment | added | PRam | @cardinal Thanks for the pointer to U-statistic. The function is basically a V-statistic (in this case, it is same as the U-statistic barring a normalization factor). The results for the concentration of U-statistics (and V-statistics) generally show that $\epsilon \sim O(1/\sqrt{n})$ but can be improved to $O(1/n)$ at best with Berstein style results. It appears that I might not be able to do better than $\epsilon \sim O(1/n)$. | |
| Mar 14, 2013 at 14:56 | comment | added | Mark Meckes | Are your $X_i$ uniformly distributed in the ball? If so, you may be able to do better using logarithmic Sobolev inequalities (but I haven't thought through the normalizations to be sure). | |
| Mar 14, 2013 at 7:18 | answer | added | Victor Kleptsyn | timeline score: 1 | |
| Mar 14, 2013 at 0:56 | comment | added | cardinal | Notice that this is a (multivariate) $U$-statistic. I would start by searching with those terms. Have you already looked at the case $d = 1$? | |
| Mar 13, 2013 at 18:44 | comment | added | Anthony Quas | I think you should expect to get something like $O(1/n)$. I think the random variables behave essentially as if they were independent, so that you're summing $n^2$ random variables of variance $\Theta(1)$ (assuming $d$ and $D$ are fixed), and dividing by $n^2$. The variance should be $\Theta(1/n^2)$, so the standard deviation should be something like $1/n$. | |
| Mar 13, 2013 at 16:55 | history | asked | PRam | CC BY-SA 3.0 |