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.