# The relationship between singular value decomposition and hyper-ellipsoid

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.

• I don't follow the last step Av := c because of b:=σc. How do we know that Av and b are linearly dependent?
– Ted
Commented Apr 1, 2018 at 8:12
• $b$ or $c$ in this problem is not crucial. what is important is set representation. Commented Apr 1, 2018 at 21:51
• Could you please provide proper justifications? Are you saying b or c is negligible? I still don't follow how you drew that conclusion (finding suitable $\alpha$ such that inequality becomes equality).
– Ted
Commented Apr 2, 2018 at 12:52
• In essence you could write $Av=b/\sigma$ if you wish and $x=y/\sigma$ then you get the equivalent set $\{y\in\mathbb{R}^n:||Ay-b||^2=\sigma^2\}$. This set again represents the hyperellipsoid. Commented Apr 2, 2018 at 12:56
• How do you know that $Av$ can be written as $\frac{b}{\sigma}$ if we don't know $b$ is in range of $A$?
– Ted
Commented Apr 2, 2018 at 14:22