6
$\begingroup$

Given $A\in\mathbb{C}^{n\times n}$, find all $x\in\mathbb{C^n}$ such that $||Ax||_2=1$ and $||x||_2=1$.

Lets do SVD: $A=U\Sigma V^*$, where $\Sigma=\mathrm{diag}\{\sigma_1,\ldots,\sigma_n\}$.

We do change of a coordinates $x=Vy,$ then we need to find $y\in\mathbb{C^n}$ such that $||\Sigma y||_2=1$ and $||y||_2=1$.

$\endgroup$
7
  • 1
    $\begingroup$ Note that $\|\Sigma y \|^2 = 1$ is the same as $\sigma_1^2 y_1^2 + \cdots + \sigma_n^2 y_n^2 = 1$. This is the equation of an ellipsoid in $n$ dimensions. $\endgroup$
    – user169852
    May 18, 2021 at 7:58
  • 1
    $\begingroup$ so I need to find points where this ellipsoid touches a sphere given by $||y||_2=1$? $\endgroup$
    – Lee
    May 18, 2021 at 8:00
  • $\begingroup$ You could also use regular optimization methods and use $ {\left\| x \right\|}_{2}^{2} \leq 1 $ to have a convex function. Then find the $ \lambda $ for equality. $\endgroup$
    – Royi
    May 23, 2021 at 4:07
  • $\begingroup$ @Royi since I am searching for all $x$ that satisfy certain constraints, I am not sure how this problem can be formulated as optimization problem. $\endgroup$
    – Lee
    May 23, 2021 at 4:50
  • $\begingroup$ What do you mean by all $x$? It’s easy to describe (intersection of an ellipsis and a sphere). It has nontrivial solutions whenever the singular values have min at most one and max at least one. A rational parametrization (impossible?) is very difficult, but it’s not too hard to project into the axis of the lowest singular value which will give you an ellipsoid that you can inverse project onto 2 pieces on the sphere. $\endgroup$
    – Eric
    May 26, 2021 at 3:18

1 Answer 1

1
$\begingroup$

Consider the system

$\left\{ \begin{matrix} \sigma_1^2|y_1|^2+\sigma_2^2|y_2|^2+\ldots+\sigma_n^2|y_n|^2=1 \\ |y_1|^2+|y_2|^2+\ldots+|y_n|^2=1 \end{matrix}\right.$

Let $\sigma_i=\max\{\sigma_1,\ldots,\sigma_n\}$ and $\sigma_j=\min\{\sigma_1,\ldots,\sigma_n\}$.

We are assuming that $\sigma_i^2>1>\sigma_j^2\geq0$.

We can rewrite this system as

$\left\{ \begin{matrix} \sigma_i^2|y_i|^2+\sigma_j^2|y_j|^2=1-\sum_{l\neq i,j}\sigma_l^2|y_l|^2\\ |y_i|^2+|y_j|^2=1-\sum_{l\neq i,j}|y_l|^2 \end{matrix}\right.$

By Cramer's rule, we obtain

$|y_j|^2=\det\begin{pmatrix}\sigma_i^2 & 1-\sum_{l\neq i,j}\sigma_l^2 |y_l|^2\\ 1 & 1-\sum_{l\neq i,j}|y_l|^2\end{pmatrix}/\det\begin{pmatrix}\sigma_i^2 & \sigma_j^2\\ 1 & 1\end{pmatrix}$ and $|y_i|^2=\det\begin{pmatrix}1-\sum_{l\neq i,j}\sigma_l|y_l|^2 & \sigma_j^2\\ 1-\sum_{l\neq i,j}|y_l|^2 & 1\end{pmatrix}/\det\begin{pmatrix}\sigma_i^2 & \sigma_j^2\\ 1 & 1\end{pmatrix}$.

Notice that

  1. $\det\begin{pmatrix}\sigma_i^2 & \sigma_j^2\\ 1 & 1\end{pmatrix}=\sigma_i^2-\sigma_j^2>0$
  2. $\det\begin{pmatrix}\sigma_i^2 & 1-\sum_{l\neq i,j}\sigma_l^2|y_l|^2\\ 1 & 1-\sum_{l\neq i,j}x_l^2\end{pmatrix}=\sigma_i^2-1+\sum_{l\neq i,j}(\sigma_l^2-\sigma_i^2)|y_l|^2$.

Since $\sigma_l^2-\sigma_i^2\leq 0$ e $0<\sigma_i^2-1$, we can find a solution when $\sum_{l\neq i,j}(\sigma_i^2-\sigma_l^2)x_l^2\leq \sigma_i^2-1.$

  1. $\det\begin{pmatrix}1-\sum_{l\neq i,j}\sigma_l^2|y_l|^2 & \sigma_j^2\\ 1-\sum_{l\neq i,j}|y_l|^2 & 1\end{pmatrix}=1-\sigma_j^2+\sum_{l\neq i,j}(\sigma_j^2-\sigma_l^2)|y_l|^2$.

Since $\sigma_j^2-\sigma_l^2\leq 0$ e $0<1-\sigma_j^2$, we can find a solution when $\sum_{l\neq i,j}(\sigma_l^2-\sigma_j^2)|y_l|^2\leq 1-\sigma_j^2.$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .