2
$\begingroup$

I am trying to find the invertible matrix $M$ satisfying: $$v_t'= MA_tM^{-1}v_t$$

For a dataset of observed transformations $(v_t',A_t,v_t)_t$. Note, there is a different linear transformation $A_t$ for each sample tuple.

Basically I have two isomorphic vector spaces $U$ and $V$, where transformations on $U$ are known but the space itself is not observed. I am trying to describe transformations on $V$ from observing the transformations $A_t$ on the space $U$ and their effects on $V$ through observed vectors $(v_t', v_t)_t$.

For now I am trying to solve it through Least squares: $$M = \underset{X}{argmin} \sum_t||v_t' - XA_tX^{-1}v_t||^2_2$$

But I was wondering if this is a known problem or if a closed solution exists.

I would also be interested in any factorizations of $M$ that could make it simpler, maybe orthogonal.

$\endgroup$
2
  • $\begingroup$ @Reinderien Thank you for the pointer but I actually meant the sample index $t$, as for every $t$ there is a linear transformation $A_t$. $\endgroup$ Commented Jan 28 at 21:12
  • $\begingroup$ Ah; good to know - it would help for you to add that to the question. $\endgroup$
    – Reinderien
    Commented Jan 28 at 21:31

1 Answer 1

2
$\begingroup$

I am not sure a unique solution exists (consider the one-dimensional case for example), nor a closed-form one.

An approach to (approximately) solving your problem is to first reformulate it as: $$\min_{\mathbf{X} \in \mathbb{R}^d} \sum_{t} \|\mathbf{X} \mathbf{v}_t' - \mathbf{A}_t \mathbf{X} \mathbf{v}_t\|_2^2,$$ assuming that $\mathbf{v}_t,\mathbf{v}_t' \in \mathbb{R}^d$ and $\mathbf{A}_t \in \mathbb{R}^{d \times d}$ for all $t$. Thus, inverting the solution to the above solves OP's problem. The benefit is that it is easier to differentiate the objective now wrt. $\mathbf{X}$ (see The Matrix Cookbook for details): $$2\sum_t \mathbf{X} \mathbf{v}_t' \mathbf{v}_t'^\top + \mathbf{A}_t^\top \mathbf{A}_t \mathbf{X}\mathbf{v}_t \mathbf{v}_t^\top -(\mathbf{A}_t^\top\mathbf{X} \mathbf{v}_t' \mathbf{v}_t^\top+\mathbf{A}_t\mathbf{X} \mathbf{v}_t \mathbf{v}_t'^\top).$$ Then using gradient descent with the derivative above should solve the problem. Also, looking at the expression above, it seems to me that finding a matrix with zero derivative is as hard as the original matrix problem, so I doubt that a closed-form can be obtained this way.

EDIT: the proposed reformulation only yields an admissible solution to the original problem if we additionally constrain the solution to be invertible, as pointed out in the comments. In this case, the gradient descent method probably won't work in practice. But I guess that the solution above should be good enough, by somehow excluding/penalizing the zero solution, or if it's fine to have pseudo-inverses in the original equation.

$\endgroup$
3
  • 2
    $\begingroup$ You need some additional constraint, otherwise $X = 0$ is a trivial solution. I think you'd want to make sure it's invertible as well. Under linear equality constraints, there is a closed-form solution by setting the gradient to be orthogonal to the equalities (see Wikipedia). $\endgroup$
    – Ggouvine
    Commented Feb 21 at 13:06
  • $\begingroup$ This was also what I thought the solution would be for the past week, but the 0 solution troubles me. Could you tell more about the regularization technique to constrain the optimization to the group of invertible matrices? $\endgroup$ Commented Feb 26 at 9:16
  • $\begingroup$ A unique solution does not exist in general and is not expected, basically you get solutions up to multiplication by matrices which commute with the $A_t$'s. $\endgroup$ Commented Feb 26 at 9:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.