# Perfect fit linear regression solution for high dimensional data

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$ ?

• 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$). – whuber Nov 30 '17 at 21:05
• That's right ! Could we show it mathematically (more rigid form) ? – Tuan Viet Nguyen Nov 30 '17 at 21:14
• 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 ? – Tuan Viet Nguyen Nov 30 '17 at 21:15
• 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. – whuber Nov 30 '17 at 21:21
• @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. – kasa Dec 1 '17 at 0:28