Show that a set is compact

Question

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.

Answer 1

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$.

Answer 2

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.