Show that a Norm Obtains a Minimum Consider a real normed vector space, and a collection of linearly independent vectors $x_i \in X$ for $i=1,2,3,4..., n$. For a fixed $y \in X$ show that:

$\inf_{\alpha_i \in \mathbb{R}, i=1,2,3...,n} ||{y-\sum_{i=1}^{n}\alpha_ix_i}||$ assumes a minimum.

So this is an engineering math course and were going over function fitting. First off, I know that infimum and minimum are not the same thing, but the way the problem is posed seems to imply that there is an absolute minimum and it is equal the infimum of the set. I think it may that I'm not understanding his notation.

Conceptually, as I see it, if $X$ were the space of continuous functions, and we wanted to fit a polynomial to that continuous function, we certainly would want to minimize the norm difference between our function, $y$, and the fit polynomial $\sum_{i=1}^{n}\alpha_ix_i$. In this case the $x_i$ could be a basis of $n$th order polynomials. Hence, if we find a minimum norm value and the vector $\sum_{i=1}^{n}\alpha_ix_i$ that generates it, then we've found a "best" fit approximation for $y$.

My first thought to go about showing a minimum exists was to say that we could simply go through every possible $\sum_{i=1}^{n}\alpha_ix_i$, evaluate the norm with $y$, and then find one particular selection of $x_i$ and $\alpha_i$ that generates the minimum. However, since the $\alpha_i$ can be any numbers, I can't "check" every possible fit function. So this won't work.

Another small note I made is that $0$ is always a bound I can make below by properties of norms, but I'm unsure of how to refine the minimum value from that point.
Here is a one answer:

If a matrix $X$ has linearly independent columns, then there is some $k&gt;0$ such that $\|Xz \| \ge  k \|z\|$ for all $z$.

Let $f(\alpha) = \|X \alpha -y\|$, where $X$ is the matrix composed of the vectors $x_k$. Note that $f(\alpha) \ge 0$ and let $m = \inf_\alpha f(\alpha)$.
We have $f(\alpha) \ge \|X \alpha \| - \|y\| \ge k \|\alpha \| - \|y\|$.

In particular, if $\| \alpha \| &gt; {1 \over k} (m+1+\|y\|)$ we have
$f(\alpha) &gt; m+1$, and so the set $\{ \alpha | f(\alpha) \le m+1 \}$ is non empty and compact and hence $f$ has a minimiser $\alpha_0$
such that $f(\alpha_0) = m$.

Here is a more satisfactory answer, but it relies on the result
that says that a differentiable convex function $f$ is minimised at a point $\alpha^*$ iff ${\partial f( \alpha^*) \over \partial \alpha} = 0$.

Ley $\phi(\alpha) = {1 \over 2} \|X\alpha -y \|^2$ (the ${1 \over 2}$
is a conventional convenience, the square makes $\phi$ differentiable everywhere). It should be clear that minimising $\phi$ is the
same as minimising $f$.

We can write $\phi(\alpha) = {1 \over 2}\langle \alpha , X^T X \alpha \rangle - \langle X^T y, \alpha \rangle + {1 \over 2} \|y\|^2$ and 
note that since $X^T X$ is positive semi definite (in fact definite,
in this case) that $\phi$ is convex. Furthermore,
${\partial \phi(\alpha) \over \partial \alpha} = \alpha^T X^T X -y^T X = (X^T(X\alpha-y))^T$.

Hence $\alpha^*$ minimises $\phi$ (and hence $f$) iff
$X^T(X\alpha^*-y) = 0$ (these are the normal equations).

In particular, there is always a solution to the normal equations
(for any matrix $X$, not just one with linearly independent columns), and if $X^T X$ is invertible (iff the columns are
linearly independent) then there is a unique minimiser given by
$\alpha^* = (X^TX)^{-1} X^T y$.

If the columns of $X$ are not linearly independent, a solution still exists but is not unique.
Let $\delta=\inf \left\{\left\lVert{y-\sum_{i=1}^{n}\alpha_ix_i}\right\rVert\,;\, (\forall i=1,\dots,n)\,\alpha_i\in\mathbb{R}\right\}$ and $S=\text{span}(x_1,\dots,x_n)$.
Notice that $\lVert x-y\rVert=d(x,y)$.
Then $\delta=\inf_{v\in S} d(y,v)=d(y,S).$


Proposition: Let $(M,d)$ be a metric space with the property that closed and bounded sets are compact (for instance, any finite dimensional, normed vector space). Let $K\subset M$ be compact and $C\subset M$ closed.
Then there are $x\in C$ and $y\in K$ with $d(C,K)=d(x,y)$.

Proof: Let $(x_n,y_n)\subset C\times K$ be a minimizing sequence for $d(C,K)$, say with $$d(x_n,y_n)&lt;d(C,K)+\frac1n.\tag{*}$$
The existence of such a sequence is guaranteed by the infimum property -- it shows up in the definition of $d(C,K)=\inf_{x\in C,\,y\in K}d(x,y)$.
Because $K$ is compact, there is a subsequence $(x_{n_k},y_{n_k})$ such that $\lim_{k\to\infty}y_{n_k}=y\in K$.
In particular, this implies that $\big(d(y_{n_k},y)\big)_{k\in\mathbb{N}}$ is bounded, say by $M\geq 0$.
Then:
$$d(x_{n_k},y)&lt;d(x_{n_k},y_{n_k})+d(y_{n_k},y)&lt;d(C,K)+(M+1)$$
With $R=d(C,K)+(M+1)$, it follows that $\big(x_{n_k}\big)_{k\in\mathbb{N}}$ lies in $\stackrel{\sim}{K}=\overline{B(R, y)}\cap C$.
As the intersection of two closed sets, $\stackrel{\sim}{K}$ is closed.
Moreover, since $\overline{B(R, y)}$ is bounded, $\stackrel{\sim}{K}$ is also bounded.
It follows that $\stackrel{\sim}{K}$ is compact.
Thus, there must be a subsequence $\left(x_{n_{k_j}},y_{n_{k_j}}\right)$ with $\lim_{j\to\infty} x_{n_{k_j}}=x\in\, \stackrel{\sim}{K}\subset C$.
Since $d:M\times M \longrightarrow \mathbb{R}$ is continuous, we have that
$$\lim_{j\to\infty} d\left(x_{n_{k_j}},y_{n_{k_j}}\right)=d(x,y)$$
Moreover, by the defining property $(*)$ of $(x_n,y_n)$, we must have $d(x,y)\leq d(C,K)$.
Since $x\in C$ and $y\in K$, and $d(C,K)$ is the infimum over $x\in C$ and $y\in K$, it must be that $d(x,y)=d(C,K)$, which concludes our proof. $\square$.

To see that the proposition applies here, it suffices to consider $M=\text{span}(y,x_1,\dots,x_n)$, $d$ the metric induced by the norm of $X$, $K=\{y\}$ and $C=S$.