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.

  • $\begingroup$ Very helpful. Just a question though: How do we know that there exists a c>0, such that ||Ax||>c||x||? $\endgroup$ – NAstuden Oct 24 '16 at 22:14
  • 1
    $\begingroup$ 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$. $\endgroup$ – Ben Grossmann Oct 24 '16 at 22:21
  • $\begingroup$ Just revisited this and I'm not sure how we in the second part can confirm the existence of the matrix B? $\endgroup$ – NAstuden Oct 25 '16 at 0:09
  • 1
    $\begingroup$ @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$. $\endgroup$ – Ben Grossmann Oct 25 '16 at 0:12
  • $\begingroup$ Wouldn't this link outrule the existence of such a matrix B: math.stackexchange.com/questions/192164/… ? $\endgroup$ – Viktor Jeppesen Oct 27 '16 at 13:00

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.