Suppose that $A \in \mathbb{R^{m x n}}$ and has full column rank, and its singular values are ordered as $\sigma_1 \ge \sigma_2 \ge... \sigma_n \gt 0$. Define the set {$x : ||Ax - b||_2 \le \sigma$} for a positive constant $\sigma$. When $\sigma$ is large enough, show that the set is an n-dimensional hyper-ellipsoid.
My question is, I know that the singular values of $A = U\sum V^T$ are the lengths of semiaxes of hyper-ellipsoid defined by $E = ${$Ax: ||x||_2 = 1$}. But for the above question, what do I exactly need to show that the set is hyper-ellipsoid for big enough constant $\sigma$ (what makes it hyper-ellipsoid)?
You set is equivalent to $\{y\in\mathbb{R}^n:||Ay-c||\leqslant 1\}$ where $x:=\sigma y$ and $b:=\sigma c$. In general an hyperellipsoid centered at some vector $v\in\mathbb{R}^n$ can be represented by $$\{x\in\mathbb{R}^n:(x-v)^TM(x-v)=1\}$$ where $M$ is some positive definite matrix. The eigenvectors of $M$ define the principal axes of the ellipsoid and the eigenvalues of $M$ are the reciprocals of the squares of the semi-axes. Note that $A^TA$ is positive definite since $$x^TA^TAx=\langle A^TAx,x\rangle=\langle Ax,Ax\rangle=||Ax||^2\geqslant 0$$ and $\ker(A)=\{0\}$ since it has full column rank i.e. $A$ is injective. Setting $M:=A^TA$ we obtain $$\{x\in\mathbb{R}^n:(x-v)^TA^TA(x-v)=1\}$$ is an hyperellipsoid where the eigenvectors of $A^TA$ (equivalently singular values of $A$) define the principal axes of the ellipsoid and the eigenvalues of $A^TA$ are the reciprocals of the squares of the semi-axes. Using $$(x-v)^TA^TA(x-v)=\langle A^TA(x-v),x-v\rangle=\langle A(x-v),A(x-v)\rangle=||A(x-v)||^2$$ the above set is the same as $$\{x\in\mathbb{R}^n:||Ax-Av||^2=1\}$$ Let $Av:=c$ then we have $$\{x\in\mathbb{R}^n:||Ax-c||^2=1\}$$ hence the original set $\{y\in\mathbb{R}^n:||Ay-c||^2\leqslant1\}$ represents an hyperellipsoid for some suitable $\sigma$ so that the inequality becomes equality.