Answers.Body: <p>First, there's a mistake or typo in the quoted statement. The requirement should be <span class="math-container">$n \geq m-1,$</span> not <span class="math-container">$n \geq m.$</span> For instance, you can fit two points <span class="math-container">$(m=2)$</span> with a line <span class="math-container">$(n=1).$</span></p>
  <p>Second, it's most straightforward to see this with simple linear algebra, not the fundamental theorem of algebra. I'll explain below.</p>
  <p>In general, if you have a <span class="math-container">$n$</span>th-degree polynomial <span class="math-container">$p(x) = a_0 + a_1 x + \ldots + a_n x^n,$</span> and you're fitting it to the set of <span class="math-container">$m$</span> data points <span class="math-container">$\{ (x_1,y_1), \ldots, (x_m,y_m) \},$</span> then you're trying to solve the following system of linear equations:</p>
  <p><span class="math-container">\begin{align*}
  y_1 &amp;= p(x_1) = a_0 + a_1 x_1 + \ldots + a_n x_1^n \\
  &amp;\vdots \\
  y_m &amp;= p(x_m) = a_0 + a_1 x_m + \ldots + a_n x_m^n \\
  \end{align*}</span></p>
  <p>Let's write this using vectors:</p>
  <p><span class="math-container">\begin{align*}
  \begin{bmatrix} y_1 \\ \vdots \\ y_m \end{bmatrix}
  =
  \begin{bmatrix} a_0 \\ \vdots \\ a_0 \end{bmatrix}
  + \begin{bmatrix} a_1x_1 \\ \vdots \\ a_1x_m \end{bmatrix}
  + \cdots
  + \begin{bmatrix} a_nx_1^n \\ \vdots \\ a_nx_m^n \end{bmatrix}
  \end{align*}</span></p>
  <p>And simplify a bit:</p>
  <p><span class="math-container">\begin{align*}
  \begin{bmatrix} y_1 \\ \vdots \\ y_m \end{bmatrix}
  =
  a_0 \begin{bmatrix} 1 \\ \vdots \\ 1 \end{bmatrix}
  + a_1 \begin{bmatrix} x_1 \\ \vdots \\ x_m \end{bmatrix}
  + \cdots
  + a_n \begin{bmatrix} x_1^n \\ \vdots \\ x_m^n \end{bmatrix}
  \end{align*}</span></p>
  <p>In other words, a solution exists if the <span class="math-container">$y$</span>-vector is in the span of the <span class="math-container">$x$</span>-vectors:</p>
  <p><span class="math-container">\begin{align*}
  \begin{bmatrix} y_1 \\ \vdots \\ y_m \end{bmatrix}
  \in \textrm{span} \left \{
  \begin{bmatrix} 1 \\ \vdots \\ 1 \end{bmatrix},
  \begin{bmatrix} x_1 \\ \vdots \\ x_m \end{bmatrix},
  \cdots,
  \begin{bmatrix} x_1^n \\ \vdots \\ x_m^n \end{bmatrix}
  \right \}
  \end{align*}</span></p>
  <p>Since the <span class="math-container">$y$</span>-values are arbitrary, this is equivalent to saying that the <span class="math-container">$x$</span>-vectors span all possible <span class="math-container">$y$</span>-vectors in <span class="math-container">$\mathbb{R}^m{:}$</span></p>
  <p><span class="math-container">\begin{align*}
  \textrm{span} \left \{
  \begin{bmatrix} 1 \\ \vdots \\ 1 \end{bmatrix},
  \begin{bmatrix} x_1 \\ \vdots \\ x_m \end{bmatrix},
  \cdots,
  \begin{bmatrix} x_1^n \\ \vdots \\ x_m^n \end{bmatrix}
  \right \} = \mathbb{R}^m
  \end{align*}</span></p>
  <p>You can span <span class="math-container">$\mathbb{R}^m$</span> with and only with a set of <span class="math-container">$m$</span> independent vectors in <span class="math-container">$\mathbb{R}^m.$</span> So, let's count off <span class="math-container">$m$</span> vectors:</p>
  <ul>
  <li>The <span class="math-container">$1$</span>st vector is <span class="math-container">$\begin{bmatrix} 1 \\ \vdots \\ 1 \end{bmatrix}$</span> which you can think of as <span class="math-container">$\begin{bmatrix} x_1^0 \\ \vdots \\ x_m^0 \end{bmatrix},$</span></li>
  <li>the components of the <span class="math-container">$2$</span>nd vector <span class="math-container">$\begin{bmatrix} x_1 \\ \vdots \\ x_m \end{bmatrix},$</span> i.e. <span class="math-container">$\begin{bmatrix} x_1^1 \\ \vdots \\ x_m^1 \end{bmatrix},$</span> have exponents <span class="math-container">$1,$</span></li>
  <li>the components of the <span class="math-container">$3$</span>rd vector (not shown above, but it would be <span class="math-container">$\begin{bmatrix} x_1^2 \\ \vdots \\ x_m^2 \end{bmatrix}$</span>) have exponents <span class="math-container">$2,$</span></li>
  <li>...</li>
  <li>the components of the <span class="math-container">$m$</span>th vector have exponents <span class="math-container">$m-1.$</span></li>
  </ul>
  <p>So, we need <span class="math-container">$n$</span> to be at least <span class="math-container">$m-1.$</span></p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-10-06T03:05:34.807Z
Answers.Text: I think I understand your argument, it's very related to one of the results in Linear Algebra that I've learnt before about the (in)homogeneous system of equations (not Fundamental Theorem of Algebra). Also I think that $\mathbf{w}$ should have been a matrix of shape $mxn$, i.e $\mathbf{w} \in \mathbf{R}^{mxn}$, instead of a vector of length $n$?
Answers.UserDisplayName: Tran Khanh
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-10-06T04:08:25.223Z
Answers.Text: The author's $\mathbf{w} \in \mathbb{R}^n$ is correct because $\mathbf{w}^T \mathbf{x}$ needs to be in the range of $h,$ which is $\mathbb{R}.$ If $\mathbf{w} \in \mathbb{R}^{m \times n}$ then there would be a dimension mismatch in the multiplication $\mathbf{w}^T \mathbf{x}$ (note that $\mathbf{x} \in \mathbb{R}^n$). And if $\mathbf{w} \in \mathbb{R}^{n \times m}$ then we would have $\mathbf{w}^T \mathbf{x} \in \mathbb{R}^m,$ not $\mathbb{R}.$
Answers.UserDisplayName: Justin Skycak
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-10-05T16:18:13.757Z
Answers.LastActivityDate: 2023-10-05T16:18:13.757Z
Answers.UserDisplayName: Justin Skycak
Answers.Body: <p>Justing gave an amazing answer, however I would like to give a more &quot;empirical&quot; way of looking at it</p>
  <p>Say you have a 2D plane, you randomly set 2 point, then it's easy to see that you can intersect perfectly the 2 points with a line</p>
  <p>Say you have a 3D plane, you randomly set 3 point, then it's easy to see that you can intersect perfectly the 3 points with a plane</p>
  <p>Then you can just go and extend this to any dimension (losing the visual representation)</p>
  <p>(Note: not always you can have this &quot;generalization in N dimensions&quot;, but in this case it works, and it's correct)</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-10-06T03:12:24.470Z
Answers.Text: As I pointed out in the comment, I think his answer implies that $\mathbf{w}$ should be in $\mathbf{R}^{mxn}$ instead of $\mathbf{R}^{n}$ as in the hypothesis formulation, is it correct?
Answers.UserDisplayName: Tran Khanh
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-10-06T11:50:10.910Z
Answers.Text: @TranKhanh, no, a line $y=mx+b$ is constituted by 2 factors $m$ and $q$, a plane by 3 of them and so on, so it is in $R^n$
Answers.UserDisplayName: Alberto
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-10-05T20:01:27.793Z
Answers.LastActivityDate: 2023-10-05T20:01:27.793Z
Answers.UserDisplayName: Alberto
Body: <p>On p.36 in <em>&quot;Machine Learning: The Basics&quot;, Alexander Jung, Spinger</em>, the author wrote:</p>
  <blockquote>
  <p>The fundamental theorem of algebra tells us that any set of <em>m</em> data points with different features can be perfectly fit by a polynomial of degree <em>n</em> as long as <em>n ≥ m</em>.</p>
  </blockquote>
  <p>Where <em>n</em> is the length of the weight vector <strong>w</strong> in <span class="math-container">$\mathbf{R}^{n}$</span>. To be specific, the hypothesis space is:</p>
  <p><span class="math-container">$\mathcal{H}^{(n)}_{poly} = \{h:R^{n} \rightarrow R:h(\mathbf{x})=\mathbf{w}^{T}\mathbf{x} \ with \ some\ vector\ \mathbf{w}∈\mathbf{R}^{n}\}.$</span></p>
  <p>But I can't relate the fundament theorem of algebra to the existence of the hypothesis (or the weight vector). Can someone help to explain?</p>
  
Tags: <machine-learning><hypothesis-class>
Title: Why any set of m data points with different features can be perfectly fit by a polynomial of degree n as long as n ≥ m
UserDisplayName: Tran Khanh
ThreadText: # Why any set of m data points with different features can be perfectly fit by a polynomial of degree n as long as n ≥ m
  
  (Asked by: username_0 on 2023-10-05)
  
  On p.36 in *"Machine Learning: The Basics", Alexander Jung, Spinger*, the author wrote:
  
  > The fundamental theorem of algebra tells us that any set of *m* data points with different features can be perfectly fit by a polynomial of degree *n* as long as *n ≥ m*.
  
  Where *n* is the length of the weight vector **w** in $\mathbf{R}^{n}$. To be specific, the hypothesis space is:
  
  $\mathcal{H}^{(n)}\_{poly} = \{h:R^{n} \rightarrow R:h(\mathbf{x})=\mathbf{w}^{T}\mathbf{x} \ with \ some\ vector\ \mathbf{w}∈\mathbf{R}^{n}\}.$
  
  But I can't relate the fundament theorem of algebra to the existence of the hypothesis (or the weight vector). Can someone help to explain?
  
  **Tags:** machine-learning, hypothesis-class
  
  ---
  
  ## 2 answers
  
  ### Answer by username_1 on 2023-10-05. Score: 1 | Accepted answer
  
  First, there's a mistake or typo in the quoted statement. The requirement should be $n \geq m-1,$ not $n \geq m.$ For instance, you can fit two points $(m=2)$ with a line $(n=1).$
  
  Second, it's most straightforward to see this with simple linear algebra, not the fundamental theorem of algebra. I'll explain below.
  
  In general, if you have a $n$th-degree polynomial $p(x) = a\_0 + a\_1 x + \ldots + a\_n x^n,$ and you're fitting it to the set of $m$ data points $\{ (x\_1,y\_1), \ldots, (x\_m,y\_m) \},$ then you're trying to solve the following system of linear equations:
  
  \begin{align\*}
  y\_1 &= p(x\_1) = a\_0 + a\_1 x\_1 + \ldots + a\_n x\_1^n \\
  &\vdots \\
  y\_m &= p(x\_m) = a\_0 + a\_1 x\_m + \ldots + a\_n x\_m^n \\
  \end{align\*}
  
  Let's write this using vectors:
  
  \begin{align\*}
  \begin{bmatrix} y\_1 \\ \vdots \\ y\_m \end{bmatrix}
  =
  \begin{bmatrix} a\_0 \\ \vdots \\ a\_0 \end{bmatrix}
  + \begin{bmatrix} a\_1x\_1 \\ \vdots \\ a\_1x\_m \end{bmatrix}
  + \cdots
  + \begin{bmatrix} a\_nx\_1^n \\ \vdots \\ a\_nx\_m^n \end{bmatrix}
  \end{align\*}
  
  And simplify a bit:
  
  \begin{align\*}
  \begin{bmatrix} y\_1 \\ \vdots \\ y\_m \end{bmatrix}
  =
  a\_0 \begin{bmatrix} 1 \\ \vdots \\ 1 \end{bmatrix}
  + a\_1 \begin{bmatrix} x\_1 \\ \vdots \\ x\_m \end{bmatrix}
  + \cdots
  + a\_n \begin{bmatrix} x\_1^n \\ \vdots \\ x\_m^n \end{bmatrix}
  \end{align\*}
  
  In other words, a solution exists if the $y$-vector is in the span of the $x$-vectors:
  
  \begin{align\*}
  \begin{bmatrix} y\_1 \\ \vdots \\ y\_m \end{bmatrix}
  \in \textrm{span} \left \{
  \begin{bmatrix} 1 \\ \vdots \\ 1 \end{bmatrix},
  \begin{bmatrix} x\_1 \\ \vdots \\ x\_m \end{bmatrix},
  \cdots,
  \begin{bmatrix} x\_1^n \\ \vdots \\ x\_m^n \end{bmatrix}
  \right \}
  \end{align\*}
  
  Since the $y$-values are arbitrary, this is equivalent to saying that the $x$-vectors span all possible $y$-vectors in $\mathbb{R}^m{:}$
  
  \begin{align\*}
  \textrm{span} \left \{
  \begin{bmatrix} 1 \\ \vdots \\ 1 \end{bmatrix},
  \begin{bmatrix} x\_1 \\ \vdots \\ x\_m \end{bmatrix},
  \cdots,
  \begin{bmatrix} x\_1^n \\ \vdots \\ x\_m^n \end{bmatrix}
  \right \} = \mathbb{R}^m
  \end{align\*}
  
  You can span $\mathbb{R}^m$ with and only with a set of $m$ independent vectors in $\mathbb{R}^m.$ So, let's count off $m$ vectors:
  
  * The $1$st vector is $\begin{bmatrix} 1 \\ \vdots \\ 1 \end{bmatrix}$ which you can think of as $\begin{bmatrix} x\_1^0 \\ \vdots \\ x\_m^0 \end{bmatrix},$
  * the components of the $2$nd vector $\begin{bmatrix} x\_1 \\ \vdots \\ x\_m \end{bmatrix},$ i.e. $\begin{bmatrix} x\_1^1 \\ \vdots \\ x\_m^1 \end{bmatrix},$ have exponents $1,$
  * the components of the $3$rd vector (not shown above, but it would be $\begin{bmatrix} x\_1^2 \\ \vdots \\ x\_m^2 \end{bmatrix}$) have exponents $2,$
  * ...
  * the components of the $m$th vector have exponents $m-1.$
  
  So, we need $n$ to be at least $m-1.$
  
  > **Comments:**
  > **username_0**: I think I understand your argument, it's very related to one of the results in Linear Algebra that I've learnt before about the (in)homogeneous system of equations (not Fundamental Theorem of Algebra). Also I think that $\mathbf{w}$ should have been a matrix of shape $mxn$, i.e $\mathbf{w} \in \mathbf{R}^{mxn}$, instead of a vector of length $n$?  
  > **username_1**: The author's $\mathbf{w} \in \mathbb{R}^n$ is correct because $\mathbf{w}^T \mathbf{x}$ needs to be in the range of $h,$ which is $\mathbb{R}.$ If $\mathbf{w} \in \mathbb{R}^{m \times n}$ then there would be a dimension mismatch in the multiplication $\mathbf{w}^T \mathbf{x}$ (note that $\mathbf{x} \in \mathbb{R}^n$). And if $\mathbf{w} \in \mathbb{R}^{n \times m}$ then we would have $\mathbf{w}^T \mathbf{x} \in \mathbb{R}^m,$ not $\mathbb{R}.$  
  
  ---
  
  ### Answer by username_2 on 2023-10-05. Score: 0
  
  Justing gave an amazing answer, however I would like to give a more "empirical" way of looking at it
  
  Say you have a 2D plane, you randomly set 2 point, then it's easy to see that you can intersect perfectly the 2 points with a line
  
  Say you have a 3D plane, you randomly set 3 point, then it's easy to see that you can intersect perfectly the 3 points with a plane
  
  Then you can just go and extend this to any dimension (losing the visual representation)
  
  (Note: not always you can have this "generalization in N dimensions", but in this case it works, and it's correct)
  
  > **Comments:**
  > **username_0**: As I pointed out in the comment, I think his answer implies that $\mathbf{w}$ should be in $\mathbf{R}^{mxn}$ instead of $\mathbf{R}^{n}$ as in the hypothesis formulation, is it correct?  
  > **username_2**: @TranKhanh, no, a line $y=mx+b$ is constituted by 2 factors $m$ and $q$, a plane by 3 of them and so on, so it is in $R^n$  
  
  ---
  
  