Show that a set is compact Let $y\in\mathbb{R}^{n}$ be a vector, $A\in\mathbb{R}^{n\times m}$ be a matrix with  $rank(A)=r<m$ (assume the first $r$ columns are linearly independent) and $M>0$. I want to show that the set $\{x\in\mathbb{R}^{m}: \lVert y-Ax \lVert^2  \leq M ,  x_i=0 \hspace{0.2cm}\text{for}\hspace{0.2cm} i>r \}$ is compact.
I can see intuitively that the set must bounded but I can't show it rigorously. I also have no clue how to show that it is closed. Any help is appreciated.
 A: Suppose that the first $r$ columns of $A$ are linearly independent.  Let $\tilde A$ denote the matrix whose columns are the first $r$ columns of $A$ are linearly independent.  We note that for any $x$ such that $x_{r+1} = \cdots = x_{m} = 0$, we have
$$
A(x_1,\dots,x_m)^T = \tilde A (x_1,\dots,x_r).
$$
Thus, we can identify the set $\{x\in\mathbb{R}^{m}: \lVert y-Ax \lVert^2  \leq M ,  x_i=0 \hspace{0.2cm}\text{for}\hspace{0.2cm} i>r \}$ with the set $\{x\in\mathbb{R}^{r}: \lVert y-\tilde Ax \lVert^2  \leq M \}$.  
In short: it suffices to consider the case where $A$ has full column rank.  So, for the remainder of the question, suppose that $A$ has $r$ columns and full column-rank.  We would like to show that $\{x\in\mathbb{R}^{r}: \lVert y- Ax \lVert^2  \leq M \}$ is compact.
Boundedness: note that $\|y - Ax\| \leq \|y\| + \|Ax\|$.  It follows that
$$
\{x\in\mathbb{R}^{r}: \lVert y- Ax \lVert^2  \leq M \} \subset 
\{x\in\mathbb{R}^{r}: \lVert Ax \lVert^2  \leq (\sqrt{M} + \|y\|)^2 \}.
$$
So, taking $C = \sqrt{M} + \|y\|$, it suffices to show that $\{x\in\mathbb{R}^{r}: \lVert Ax \lVert  \leq C\}$ is bounded.  
Now, note that there exists a $c > 0$ such that for all $x \in \Bbb R^r$, we have $\|Ax\| \geq c \|x\|$.  It suffices to take
$$
c = \min_{\|x\| = 1} \|Ax\|.
$$
This minimum must exist because $\{x: \|x\| = 1\}$ is compact and the map $x \mapsto \|Ax\|$ is continuous.  This minimum cannot be zero since $A$ has a trivial kernel.  So, $\|x\| \neq 0$  implies that $\|Ax\| \neq 0$. It follows that 
$$
\{x \in \Bbb R^r: \|Ax\| \leq C\} \subseteq
\{x \in \Bbb R^r: c\|x\| \leq C\} = 
\{x \in \Bbb R^r: \|x\| \leq \frac{C}{c}\}.
$$
So, the set is indeed bounded.
Closure: it suffices to note that the function $\|Ax - y\|$ is continuous.  Thus, if $(x_n)$ is a sequence such that $\|Ax_n - y\|^2 \leq M$ and $x_n \to x$, then it must hold that $\|Ax - y\|^2 = \lim_{n \to \infty} \|Ax_n - y\|^2 \leq C$.
A: It is sufficient to prove that given matrix $A_{m \times r}$ with independent columns and $M \geq 0$, the set $U=\left\{ x : \|Ax - b\| \leq M \right\}$ is compact.  Since $x \mapsto Ax - b$ is continuous, $U$ is closed.
If $U$ is empty then we are done as the empty is compact. Otherwise choose any $ x \in U$, we have $$Ax = b + c$$ for some $c$ with $\|c\| \leq M$.
So,
$$A^{\top}Ax = A^T(b+c),$$ or 
$$x = (A^{\top}A)^{-1} A^T(b+c).$$
Note $A^{\top}A$ is invertible as $A$ has independent columns.
Taking norms of both sides we have
$$\|x\| \leq  \|(A^{\top}A)^{-1} A^T b\| + \|(A^{\top}A)^{-1} A^T c\|,$$
that is,
$$ \|x\| \leq  \|(A^{\top}A)^{-1} A^T b\|  + \|(A^{\top}A)^{-1} A^T\|  M.$$
Here for a matrix $L$, $ \|L\|= \sup_{ \|y\| =1} \| Ly\|$ is the usual operator norm of a matrix.
Since $x$ in $U$ was arbitrary, this shows $U$ is bounded.
So $U$ is closed and bounded, hence compact.
