Recovering original matrix from its kernel matrix

Question

For a given linear kernel matrix, $K [n \times n]$, we would like to recover the original matrix $X$.

In general it is not possible to recover the data matrix from a kernel matrix, as the projection of data matrix into possibly infinite-dimensional space loses the original embedding. However, we impose the condition on the original matrix $X$ to be some perturbation of a known matrix $M [n \times p]$ measured in terms of the Frobenius norm.

For the simple case, where the kernel function is linear, the problem can be expressed as the following optimization problem: \begin{equation*} \begin{aligned} & \underset{X}{\text{min}} & & \|X - M \|_F^2 \\ &\text{subject to}& & XX^{\top} = K\\ \end{aligned} \end{equation*}

where, $K$ and $M$ are known.

1. How would you solve the above problem? Is there an analytical solution to this?

2. For a general (known or unknown) kernel function which satisfies Mercer's condition, is it possible to retrieve the original matrix?

Answer 1

We have the following optimization problem in fat matrix $\mathrm X \in \mathbb R^{n \times p}$

$$\begin{array}{ll} \text{minimize} & \| \mathrm X - \mathrm M \|_{\text{F}}^2\\ \text{subject to} & \mathrm X \mathrm X^\top = \mathrm K\end{array}$$

where fat matrix $\mathrm M \in \mathbb R^{n \times p}$ and symmetric positive semidefinite matrix $\mathrm K \in \mathbb R^{n \times n}$ are given. Since the objective function is

$$\begin{array}{rl} \| \mathrm X - \mathrm M \|_{\text{F}}^2 &= \mbox{tr} \left( (\mathrm X - \mathrm M) (\mathrm X - \mathrm M)^\top \right)\\ &= \mbox{tr} \left( \mathrm X \mathrm X^\top - \mathrm X \mathrm M^\top - \mathrm M \mathrm X^\top + \mathrm M \mathrm M^\top \right)\\ &= \mbox{tr} \left( \mathrm K \right) - \langle \mathrm M , \mathrm X \rangle - \langle \mathrm X , \mathrm M \rangle + \| \mathrm M \|_{\text{F}}^2\\ &= \mbox{tr} \left( \mathrm K \right) - 2 \langle \mathrm M , \mathrm X \rangle + \| \mathrm M \|_{\text{F}}^2\end{array}$$

the original optimization problem can be rewritten as follows

$$\begin{array}{ll} \text{maximize} & \langle \mathrm M , \mathrm X \rangle\\ \text{subject to} & \mathrm X \mathrm X^\top = \mathrm K\end{array}$$

Let the Lagrangian be

$$\mathcal L (\mathrm X, \Lambda) := \langle \mathrm M , \mathrm X \rangle - \frac 12 \langle \Lambda , \mathrm X \mathrm X^\top - \mathrm K \rangle$$

Taking the partial derivatives and finding where they vanish, we obtain two matrix equations

$$\begin{array}{rl} \left(\dfrac{\Lambda + \Lambda^\top}{2}\right) \mathrm X &= \mathrm M\\ \mathrm X \mathrm X^\top &= \mathrm K \end{array}$$

Let us introduce (symmetric) matrix variable $\mathrm S := \dfrac{\Lambda + \Lambda^\top}{2}$. We write

$$\begin{array}{rl} \mathrm S \mathrm X &= \mathrm M\\ \mathrm X \mathrm X^\top &= \mathrm K \end{array}$$

and, thus,

$$\mathrm M \mathrm M^\top = \mathrm S \,\mathrm X \mathrm X^\top \mathrm S = \mathrm S \mathrm K \mathrm S = \mathrm S \mathrm K^{\frac 12} \mathrm K^{\frac 12} \mathrm S$$

Hence, we obtain the matrix equation

$$\mathrm S \mathrm K^{\frac 12} = \left( \,\mathrm M \mathrm M^\top \right)^{\frac 12}$$

Assuming that $\rm K$ is positive definite,

$$\mathrm S = \left( \,\mathrm M \mathrm M^\top \right)^{\frac 12} \mathrm K^{-\frac 12}$$

Assuming that $\rm M$ has full row rank (so that $\rm \mathrm M \mathrm M^\top$ is invertible),

$$\mathrm S^{-1} = \mathrm K^{\frac 12} \left( \,\mathrm M \mathrm M^\top \right)^{-\frac 12}$$

and, thus, the optimal solution is

$$\boxed{\bar{\mathrm X} := \mathrm S^{-1} \mathrm M = \color{blue}{\mathrm K^{\frac 12} \left( \,\mathrm M \mathrm M^\top \right)^{-\frac 12} \mathrm M}}$$

Verifying that the constraint is satisfied,

$$\bar{\mathrm X} \bar{\mathrm X}^\top = \mathrm K^{\frac 12} \left( \,\mathrm M \mathrm M^\top \right)^{-\frac 12} \mathrm M \mathrm M^\top \left( \,\mathrm M \mathrm M^\top \right)^{-\frac 12} \mathrm K^{\frac 12} = \mathrm K$$

Lastly, the minimum is

$$\mbox{tr} \left( \mathrm K \right) - 2 \langle \mathrm M , \bar{\mathrm X} \rangle + \| \mathrm M \|_{\text{F}}^2 = \| \mathrm K^{\frac 12} - \left( \,\mathrm M \mathrm M^\top \right)^{\frac 12} \|_{\text{F}}^2$$