Answers.Body: <p>First, let's try to build some intuition for what we mean when we say that we want to &quot;densely cover&quot; a <span class="math-container">$d$</span>-dimensional space <span class="math-container">$\mathbb{R}^d$</span> of real numbers. For simplicity, let's assume that all values in all dimensions are restricted to lie in <span class="math-container">$[0, 1]$</span>. Even with just a single dimension <span class="math-container">$d=1$</span>, there are actually already infinitely many different possible values even in such a restricted <span class="math-container">$[0, 1]$</span> range.</p>
  <p>But generally we don't actually care about literally covering every single possible value. Generally, we expect that points in this <span class="math-container">$d$</span>-dimensional space that are &quot;close&quot; to each other also &quot;behave&quot; similarly, that there's some level of &quot;continuity&quot;. Hence, to get &quot;sufficient&quot; or &quot;good&quot; or &quot;dense&quot; coverage of the space, you can somewhat informally assume that every data point you have occupies some space around it. This is the intuition behind Lutz Lehmann's comment under your question: you can think of every point as being a <span class="math-container">$d$</span>-dimensional cube occupying some volume of your <span class="math-container">$d$</span>-dimensional space.</p>
  <p>Now, if you have a <span class="math-container">$d$</span>-dimensional space of size <span class="math-container">$[0, 1]$</span> along every dimension, and you have little cubes that occupy a part of that space (for instance, cubes of size <span class="math-container">$0.1$</span> in every dimension), you will indeed find that the number of cubes you need to fill up your space scales exponentially in <span class="math-container">$d$</span>. The basic idea is: if some number of cubes <span class="math-container">$K$</span> is sufficient to fill up the <span class="math-container">$d$</span>-dimensional space, and if you then increase the dimensionality to <span class="math-container">$d+1$</span>, you'll need <span class="math-container">$dK$</span> cubes to fill the new space. When you add a new dimension, the complete previous space becomes essentially just one &quot;slice&quot; of the new space.</p>
  <p>For dimensions <span class="math-container">$d = 1, 2, 3$</span>, this is fairly easy to visualise. If you have <span class="math-container">$d=1$</span>, your space is really just a line, or a line segment if you constrain the values to lie in <span class="math-container">$[0, 1]$</span>. If you have a <span class="math-container">$[0, 1]$</span> line segment, and you have little cubes of length <span class="math-container">$0.1$</span>, you'll need just ten of them to fill up the line.</p>
  <p>Now imagine that you add the second dimension. Suddenly your line becomes an entire plane, or a <span class="math-container">$10\times10$</span> square grid. The <span class="math-container">$10$</span> cubes are now only sufficient to fill up a single row, and you'll have to repeat this <span class="math-container">$10$</span> times over to fill up the entire <span class="math-container">$2$</span>D space; you need <span class="math-container">$10^2 = 100$</span> cubes.</p>
  <p>Now imagine that you add the third dimension. What used to be a plane gets &quot;pulled out&quot; into an entire three-dimensional cube -- a large cube, which will require many little cubes to fill! The plane that we had previously is again just a flat slice in this larger <span class="math-container">$3$</span>D space, and the entire strategy for filling up a plane will have to be repeated <span class="math-container">$10$</span> times over to fill up <span class="math-container">$10$</span> such slices of the <span class="math-container">$3$</span>D space; this now requires <span class="math-container">$10^3 = 1000$</span> cubes.</p>
  <p>Past <span class="math-container">$3$</span> dimensions, the story continues in exactly the same way, but is a bit harder for us humans to visualise.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-03-19T20:06:52.237Z
Answers.Text: Thank you for the answer. It's much more detailed. So when we say "densely cover the space", it doesn't mean that our points are dense in this space but that they have some space around them and with which we can cover the whole space.
Answers.UserDisplayName: Daviiid
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-03-19T20:23:31.520Z
Answers.Text: @Daviiid Well, points are still points. Mathematically, they don't occupy any space around them. But "densely covered" isn't a very precise definition, it's a bit informal. The basic intuition is that it should "feel like" you "sufficiently" cover most areas of the space, that you don't have any huge subsections of the space that are completely empty without any points in them at all.
Answers.UserDisplayName: Dennis Soemers
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-03-19T19:23:16.587Z
Answers.LastActivityDate: 2021-03-19T19:23:16.587Z
Answers.UserDisplayName: Dennis Soemers
Body: <p>In <a href="https://www.youtube.com/watch?v=OoUX-nOEjG0#t=42m9s" rel="nofollow noreferrer">this lecture</a> (minute 42), the professor says that the number of training examples we need to densely cover the space of training vectors grows exponentially with the dimension of the space. So we need <span class="math-container">$4^2=16$</span> training data points if we're working on <span class="math-container">$2D$</span> space. I'd like to ask why this is true and how is it proved/achieved? The professor was talking before about K-Nearest Neighbors and he was using <span class="math-container">$L^{1}$</span> and <span class="math-container">$L^{2}$</span> metrics. I don't think these metrics induce a topology that makes a discrete set of points dense in the ambient space.</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-03-19T17:58:44.230Z
Comments.Text: $N^d=e^{d\ln(N)}$ is exponential in the dimension $d$. Fill a unit cube in dimension $d$ with small cubes of side length/diameter $1/N$.
Comments.UserDisplayName: Lutz Lehmann
Tags: <classification><k-nearest-neighbors><curse-of-dimensionality>
Title: Why the number of training points to densely cover the space grows exponentially with the dimension?
UserDisplayName: Daviiid
ThreadText: # Why the number of training points to densely cover the space grows exponentially with the dimension?
  
  (Asked by: username_0 on 2021-03-18)
  
  In [this lecture](https://www.youtube.com/watch?v=OoUX-nOEjG0#t=42m9s) (minute 42), the professor says that the number of training examples we need to densely cover the space of training vectors grows exponentially with the dimension of the space. So we need $4^2=16$ training data points if we're working on $2D$ space. I'd like to ask why this is true and how is it proved/achieved? The professor was talking before about K-Nearest Neighbors and he was using $L^{1}$ and $L^{2}$ metrics. I don't think these metrics induce a topology that makes a discrete set of points dense in the ambient space.
  
  **Tags:** classification, k-nearest-neighbors, curse-of-dimensionality
  > **Comments:**
  > **username_1**: $N^d=e^{d\ln(N)}$ is exponential in the dimension $d$. Fill a unit cube in dimension $d$ with small cubes of side length/diameter $1/N$.  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_2 on 2021-03-19. Score: 2 | Accepted answer
  
  First, let's try to build some intuition for what we mean when we say that we want to "densely cover" a $d$-dimensional space $\mathbb{R}^d$ of real numbers. For simplicity, let's assume that all values in all dimensions are restricted to lie in $[0, 1]$. Even with just a single dimension $d=1$, there are actually already infinitely many different possible values even in such a restricted $[0, 1]$ range.
  
  But generally we don't actually care about literally covering every single possible value. Generally, we expect that points in this $d$-dimensional space that are "close" to each other also "behave" similarly, that there's some level of "continuity". Hence, to get "sufficient" or "good" or "dense" coverage of the space, you can somewhat informally assume that every data point you have occupies some space around it. This is the intuition behind Lutz Lehmann's comment under your question: you can think of every point as being a $d$-dimensional cube occupying some volume of your $d$-dimensional space.
  
  Now, if you have a $d$-dimensional space of size $[0, 1]$ along every dimension, and you have little cubes that occupy a part of that space (for instance, cubes of size $0.1$ in every dimension), you will indeed find that the number of cubes you need to fill up your space scales exponentially in $d$. The basic idea is: if some number of cubes $K$ is sufficient to fill up the $d$-dimensional space, and if you then increase the dimensionality to $d+1$, you'll need $dK$ cubes to fill the new space. When you add a new dimension, the complete previous space becomes essentially just one "slice" of the new space.
  
  For dimensions $d = 1, 2, 3$, this is fairly easy to visualise. If you have $d=1$, your space is really just a line, or a line segment if you constrain the values to lie in $[0, 1]$. If you have a $[0, 1]$ line segment, and you have little cubes of length $0.1$, you'll need just ten of them to fill up the line.
  
  Now imagine that you add the second dimension. Suddenly your line becomes an entire plane, or a $10\times10$ square grid. The $10$ cubes are now only sufficient to fill up a single row, and you'll have to repeat this $10$ times over to fill up the entire $2$D space; you need $10^2 = 100$ cubes.
  
  Now imagine that you add the third dimension. What used to be a plane gets "pulled out" into an entire three-dimensional cube -- a large cube, which will require many little cubes to fill! The plane that we had previously is again just a flat slice in this larger $3$D space, and the entire strategy for filling up a plane will have to be repeated $10$ times over to fill up $10$ such slices of the $3$D space; this now requires $10^3 = 1000$ cubes.
  
  Past $3$ dimensions, the story continues in exactly the same way, but is a bit harder for us humans to visualise.
  
  > **Comments:**
  > **username_0**: Thank you for the answer. It's much more detailed. So when we say "densely cover the space", it doesn't mean that our points are dense in this space but that they have some space around them and with which we can cover the whole space.  
  > **username_2**: @Daviiid Well, points are still points. Mathematically, they don't occupy any space around them. But "densely covered" isn't a very precise definition, it's a bit informal. The basic intuition is that it should "feel like" you "sufficiently" cover most areas of the space, that you don't have any huge subsections of the space that are completely empty without any points in them at all.  
  
  ---
  
  