# Proving that $p = \inf\{\|Ax-b\|: x\in\mathbb{R}^n\}$ is attained

I'm trying to solve the following problem in my textbook:

Let $A$ be an $m \times n$ matrix of unspecified rank, $b\in\mathbb{R}^n$ and let $p =\inf\{\|Ax-b\|: x\in\mathbb{R}^n\}$ (the norm is abitrary on $\mathbb{R}^n$).

Show that this infimum is attained (meaning, proving the existence of an $x$ for which $\|Ax-b\| = p$).

I'm having a lot of trouble figuring out how to exactly prove this. In the problems chapter, I have been introduced to "Least-squares problems", which is the first thing I thought of.

The problem is that the least-square method uses a specific norm (problem uses an abitrary) and also assumes that the rank is $n$, and thereby $n\le m$ (problem has unspecified rank).

Another thought was to introduce $b'$, with property $\|b'-b\|=p$, and then prove that a solution to $Ax=b'$ exists — but as far as I know, that would again depend on the actual rank of $A$, and I'm not too sure that this is the correct way to proceed.

Would appreciate any hints on how one might tackle on such a proof?

The trick for proving a result like this is to reduce it to the case in which $A$ has full column-rank.

Suppose that $A$ has full column-rank. Then there exists a $c > 0$ such that $\|Ax\| > c\|x\|$

Of course, the infimum is smaller than $\|A0 - b\| = \|b\|$. Note that for $\|x\| > 2\|b\|/c$, we have $$\|Ax - b\| \geq |\|Ax\| - \|b\|| \geq |c\|x\| - \|b\|| \geq \\ |c\|x\| - \|b\|| \geq |2\|b\| - \|b\|| = \|b\|$$ So, we have $$\inf\{\|Ax - b\| : x \in \Bbb R^n\} = \inf\{\|Ax - b\| : x \in \Bbb R^n, \|x\| \leq 2\|b\|/c\}$$ However, $S = \{x \in \Bbb R^n : \|x\| \leq 2 \|b\|/c\}$ is closed and bounded, and is therefore compact. The function $f(x) = \|Ax - b\|$ is continuous. Thus, the $\inf\{f(x) : x \in S\}$ is attained within $S$, which gives us the desired result.

Suppose that $A$ doesn't have full column rank. Then, there exists a matrix $B$ such that $AB$ has the same column space as $A$, and $AB$ has full column rank (in particular: the columns of $B$ may be taken from the identity matrix).

From the above, we know that $\|ABx - b\|$ attains its minimum at some $x^*$. However, since $AB$ has the same column space as $A$, this infimum coincides with that of $\|Ax - b\|$, and $\|ABx^* - b\| = \|A(Bx^*) - b\|$. So again, the infimum is attained.

• Very helpful. Just a question though: How do we know that there exists a c>0, such that ||Ax||>c||x||? – NAstuden Oct 24 '16 at 22:14
• Take $c=\inf\{ \|Ax\| : \|x\|=1\}$. We're minimizing a continuous function over a compact domain, so the minimum is attained. $A$ has a trivial null space, so the minimum can't be $0$. – Omnomnomnom Oct 24 '16 at 22:21
• Just revisited this and I'm not sure how we in the second part can confirm the existence of the matrix B? – NAstuden Oct 25 '16 at 0:09
• @NAstuden I changed my answer up a bit there: if $B$ is made out of columns of the identity matrix, then $AB$ is simply some arrangement of the columns of $A$. It suffices, then, to select columns from the identity matrix so that the columns of $AB$ are a basis for the column space of $A$. – Omnomnomnom Oct 25 '16 at 0:12
• Wouldn't this link outrule the existence of such a matrix B: math.stackexchange.com/questions/192164/… ? – Viktor Jeppesen Oct 27 '16 at 13:00