4 ms·

> A consequence is that, if you’re trying to cluster data points by looking at points within a fixed distance r of one point, you’ll have to make r exponentiall

• goblinking 11y ago
  but it looks sorta mathy, I better upvote even if the guy has no clue whatsoever!
• jfoutz 11y ago
  His point is the volume of the unit sphere is tiny. The "volume" of the unit 20-cube is 1. The volume of a 20-sphere is just 0.0258. 100-cube, volume is 1. 100-sphere, 2.36e-40 If your algorithm works well for "nearby" meaning 1, i can just keep adding dimensions till you find nothing. If "nearby" on the other hand is related to the number of dimensions, you're going to have to grow the "nearby" value exponentially.
  • shasta 11y ago
    You've made the same error as the OP. The volume of a unit n-dimensional sphere decreases exponentially in n. But that doesn't mean you need to increase r exponentially to compensate - in the volume formula, the r also has an exponent of n. The distance between opposite corners of a unit cube in n-dimensional space is root(n). That's hardly exponential.
    • jfoutz 11y ago
      Huh. I always thought n! grew faster than c^n which would be even worse than exponential. Maybe enough cancels out to make it simpler than it appears. edit Actually, for even dimensions it's pretty clear. n = dimension/2 pi^n / n! factorial wins. The problem is worse than exponentiation.
      • arielb1 11y ago
        But if you have r=sqrt(n) that works out fine.
      • ph0rque 11y ago
        At some point, I wondered if n! is proportional to n^n. Turns out, it is: n! ~= (2 * pi * n)^1/2 * (n/e)^n (https://en.wikipedia.org/wiki/Stirling%27s_approximation https://en.wikipedia.org/wiki/Stirling%27s_approximation)
        • madcaptenor 11y ago
          Not exactly "proportional", because you have that pesky e in the denominator. But that's the right idea. Basically, to get n! you're multiplying together n things that are sort of n-ish, so you'd expect n! ~ n^n. (When the numbers get really big, like in statistical mechanics, I've seen the approximation log n! ~ n log n.) The next step is to figure that you're multiplying together n things that are on average n/2, so n! ~ (n/2)^n. But then it really turns out that you should have been using a geometric average (since you're multiplying), not an arithmetic one, so n! must be smaller yet. (I don't know a way to get (n/e)^n without doing an integral, though.)
          • ph0rque 11y ago
            Right, proportional in the sense that for both n! and n^n, the fastest-growing component is ~n^n. (I was curious in the context of which grew faster for larger values of n in the big O notation).
• deleted 11y ago
  [deleted]
• j2kun 11y ago
  You're right. Amended.