Is there a perfect fit solution for linear regression with high dimensional data ?

Let's say we have a label dataset $\mathbb{X}$ with $N$ data points with linear independent feature vectors $\textbf{x}^{(i)} \in \mathbb{R}^d$ and labels $y^{(i)} \in \mathbb{R}$ and $N\leq d$

We fit linear regression $h^{(w)}(\textbf{x}) = w^T\textbf{x}$ into the model by minimize the loss $$ \mathcal{E}(h^{(w)}(.)|\mathbb{X}) = \frac{1}{N}\sum^N_{i=1}(y^{(i)}-w^T\textbf{x}^{(i)})^2$$

Is there any perfect fit solution $w_0$ such that $\mathcal{E}(h^{(w_0)}(.)|\mathbb{X}) = 0$ ?

  • $\begingroup$ In any Euclidean space, $N$ points determine a subspace of dimension at most $N$. Equivalently, by setting the right hand side to zero you're trying to solve $N$ simultaneous linear equations in $d$ variables; for $N\le d$, that's always possible (except for very special values of $y$). $\endgroup$ – whuber Nov 30 '17 at 21:05
  • $\begingroup$ That's right ! Could we show it mathematically (more rigid form) ? $\endgroup$ – Tuan Viet Nguyen Nov 30 '17 at 21:14
  • $\begingroup$ By the way I just read this article en.wikipedia.org/wiki/Underdetermined_system, it said there could be either infinite solution or no solution at all ? Is it true ? $\endgroup$ – Tuan Viet Nguyen Nov 30 '17 at 21:15
  • 1
    $\begingroup$ Geometrically, zeroing out any term in the sum describes an affine codimension-1 subspace; zeroing out them all intersects all $N$ subspaces. Provided there isn't any inconsistency, the intersection will have dimension at least $d-N$. These are rigorous mathematical ideas. Since you sound unfamiliar with them, consult a textbook of linear algebra for details. $\endgroup$ – whuber Nov 30 '17 at 21:21
  • $\begingroup$ @TuanVietNguyen: As an example, the following set of equations are inconsistent. $x+y+z=6$ and $2x+2y+2z=9$ Here, we have two equations and three variables. $\endgroup$ – kasa Dec 1 '17 at 0:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.