0
$\begingroup$

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)?

$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

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.

$\endgroup$
8
  • $\begingroup$ I don't follow the last step Av := c because of b:=σc. How do we know that Av and b are linearly dependent? $\endgroup$ Commented Apr 1, 2018 at 8:12
  • $\begingroup$ $b$ or $c$ in this problem is not crucial. what is important is set representation. $\endgroup$ Commented Apr 1, 2018 at 21:51
  • $\begingroup$ 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). $\endgroup$ Commented Apr 2, 2018 at 12:52
  • $\begingroup$ 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. $\endgroup$ Commented Apr 2, 2018 at 12:56
  • $\begingroup$ How do you know that $Av$ can be written as $\frac{b}{\sigma}$ if we don't know $b$ is in range of $A$? $\endgroup$ Commented Apr 2, 2018 at 14:22

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.