Projector onto solution space of $X'AX = 0$?

147 Views Asked by At

Let $A\in\mathbb{R}^{N\times N}$ be a given constant symmetric $N\times N$ square matrix. Consider the equation:

$$X' A X = 0$$

in $X$, which is a rectangular matrix, $N\times M$.

If $A$ is positive definite, then of course the only solution is the zero matrix, $X = 0$. So I'll assume that's not the case: $A$ has both some negative and some positive eigenvalues.

Now consider another rectangular matrix $Y\in\mathbb{R}^{N\times M}$. My goal is to project $Y$ onto the solution space of the above equation. In other words, given $A, Y$, I must $X$ closest to $Y$, which satisfies the above equation:

$$\underset{X}{\mathrm{argmin}} \| X - Y \|^2 \qquad \text{subject to} \qquad X'AX=0$$

Here by the distance $\| X - Y \|^2$ I mean $\sum_{ij} (X_{ij}-Y_{ij})^2$.

Note that, differentiating the Lagrangian of this, leads to a Sylvester equation (hence the tag) which doesn't look very helpful.

1

There are 1 best solutions below

11
On

Before looking at projection properties (we will do it in the last paragraph), it is essential to have an idea of what matrices $X$ such that $X^TAX=0$ "look like".

In the case $N=M$ the set of such matrices $X$ is rather easy to characterize.

Let us illustrate it in the case $N=M=3$ for a general non-definite positive matrix, where:

$$X^TAX=\begin{pmatrix}a&b&c\\d&e&f\\g&h&i \end{pmatrix}\begin{pmatrix}1& 0&0\\0&1&0\\0&0&-1 \end{pmatrix}\begin{pmatrix}a&d&g\\b&e&h\\ c&f&i\end{pmatrix}=0\tag{1}$$

This is equivalent to the set of 6 equations:

$$\begin{cases} a^2+b^2-c^2&=&0&(Eq. 1)\\ d^2+e^2-f^2&=&0&(Eq. 2)\\ g^2+h^2-i^2&=&0&(Eq. 3)\\ ad+be-cf&=&0&(Eq. 4)\\ ag+bh-ci&=&0&(Eq. 5)\\ bc+ef-hi&=&0&(Eq. 6) \end{cases}\tag{2}$$

Let

$$u:=\begin{pmatrix}a\\b\\c \end{pmatrix}, \ \ v:= \begin{pmatrix}d\\e\\f \end{pmatrix}, \ \ w:= \begin{pmatrix}g\\h\\i \end{pmatrix}$$

Let $(C)$ be the cone with equation $x^2+y^2-z^2=0$.

The 3 first relationships in (2) express the fact that points $u,v,w \in (C)$.

Let us take the case of the tangent plane $(T_u)$ to $(C)$ in $u$.

Its equation is $xa+yb-zc=0$.

(Eq. 4) and (Eq. 5) above express the fact that $v \in (T_u)$ and $w \in (T_u)$. This is possible if and only $u,v,w$ are proportional vectors (i.e;, belong to a same generatrix line of the cone).

As a consequence, the set of matrices $X$ such that $X^TAX=0$ is the set of rank-one matrices described by the formula:

$$X=\begin{pmatrix}a&pa&qa\\b&pb&qb\\ c&pc&qc\end{pmatrix}=\begin{pmatrix}a\\b\\c\end{pmatrix}(1 \ \ p \ \ q)\tag{3}$$

In this case, we can characterize the projection of a $3 \times 3$ matrix $Y$. Let us recall that a general result dealing with SVD (Singular Value Decomposition) says that projection of $Y$ onto the family of rank one matrices is obtained by taking $\sigma_1 U_1V_1^T$ where $\sigma_1, U_1, V_1$ are the main singular value, and associated unit left singular vector and right singular resp. in the SVD of $Y$.

Edit: The cases where $M>N$ look to be amenable at the previous case. Let us consider, once agin for the sake of simplicity, the case $N=3$ and $M=N+1=4$. One can write $X=[X_1,X_2]$ where $X_1$ is a $3 \times 3$ matrix and $X_2$ a "column" vector of $\mathbb R^3$.

$$X^TAX=0 \iff \begin{pmatrix}X_1^T\\X_2^T\end{pmatrix}A\begin{pmatrix}X_1&X_2\end{pmatrix}=0 \iff \begin{pmatrix}X_1^TAX_1&X_1^TAX_2\\X_2^TAX_1&X_2^TAX_2\end{pmatrix}=\begin{pmatrix}0&0\\0&0\end{pmatrix}\tag{4}$$

Otherwise said:

$$\begin{cases}X_1^TAX_1&=&0\\X_1^TAX_2&=&0\\X_2^TAX_2&=&0\end{cases}\tag{5}$$ Among the $3$ constraints given by (5), the first one has already been met before. The third one, once again with the cone interpretation means that $X_2$ belongs to the cone, and the second one that $X_2$ belongs to all the tangent planes to the columns of matrix $X_1$. As a consequence, $X_2$ belongs to the column space of matrix $X_1$. Therefore, using (3):

$$X=\begin{pmatrix}a\\b\\c\\d\end{pmatrix}(1 \ \ p \ \ q)\tag{6}$$