6
$\begingroup$

Let $X\in\mathbb{R}^{3\times 3}$ be an orthogonal matrix. Then $\mathrm{vec}X\in\mathbb{R}^9$ is a 9 by 1 vector formed by stacking the columns of the matrix $X$ on top of one another. Given a matrix $A\in\mathbb{R}^{9\times 9}$, find the optimal orthogonal matrix $X$ minimizing the following objective function. $$J=\left(\mathrm{vec}X\right)^T A \mathrm{vec}X$$ I think Kronecker product may be useful for solving this problem. Does a closed-form solution exist? If not, is it possible to solve it iteratively? Thanks.

EDIT

a) Here $A$ doesn't have any special property. But it is also acceptable if solutions can be obtained by adding some properties on $A$.

b) In the original problem, $X$ is constrained as a rotation matrix. But I think that would be even harder, so I put $X$ as an orthogonal matrix herein. Of course, optimal rotation matrices are better.

  • 0
    Does $A$ has any property, e.g. being positive definite?2011-10-09
  • 0
    @Hauke Strasdat: Thanks, I've edited the question about this point.2011-10-09
  • 0
    Note sure whether there is a closed form solution. But you could solve it iteratively (e.g. using the Newton method or Gradient Descent) and the Lie algebra so3. Is X a proper rotation $\det(X)=1$ or can it also be a reflection?2011-10-09
  • 0
    @Hauke Strasdat: Yes, but the general Newton or Gradient methods suffer from several drawbacks: (1) convergence is not guaranteed. (2) Orthogonality is not satisfied. (3) initial values are required and may converge to local but not global minima. I think better solutions should be possible due to the specific format of the objective function.2011-10-09
  • 2
    You can preserve orthogonality, if you do the update in the tangent space (Lie algerba). Thus, you calculate the gradient: $\nabla J =\frac{\partial }{\partial \epsilon} \text{vec} (\exp(\epsilon)X)^\top A \text{vec} (\exp(\epsilon)X)|_{\epsilon=0}$ with $\exp(\cdot)$ being the Rodriguez formula. Now you can iteratively update $X$ using gradient descent: $X' = \exp(-\alpha\nabla J) X$.2011-10-09
  • 3
    On the issue of rotations vs. reflections, note since X is of odd dimension and can be replaced wlog in the objective function by -X if necessary, there is no problem restricting attention to det(X)=1.2011-10-09
  • 0
    @Hardmath: I see now that if $X$ is the minimum then $-X$ is a minimum too. Is this what you were saying?2011-10-09
  • 0
    @Hauke Strasdat: Right, and that if X is 3x3 orthogonal, exactly one of X and -X is properly a rotation (as Shiyu original wants).2011-10-10
  • 0
    @Hauke Strasdat: the $\epsilon$ in the Rodriguez formula is a skew-symmetric matrix, right? Is it possible to find a good step size $\alpha$ and prove the convergence? BTW, can you also give some reference on this method? I think it is interesting.2011-10-10
  • 0
    @hardmath: I didn't notice that. thanks.2011-10-10
  • 0
    @hardmath, you and Shiyu are both correct about my solution. For some reason, I though it could be moved like a matrix.2011-10-10
  • 0
    @Shiyu: I am happy to provide some more details in a bit. Just wondering how your problem is motivated. Is there any particular application you try to solve?2011-10-10
  • 0
    Following the footsteps of @HaukeStrasdat , the space of 3x3 rotation matrices [can be parameterized](http://en.wikipedia.org/wiki/Rotation_matrix#Conversion_from_and_to_axis-angle) in terms of an axis (unit vector) and an angle of rotation about that axis, a fact [proven by Euler](http://en.wikipedia.org/wiki/Euler_rotation_theorem). In principle for given $A$ we can maximize with respect to the angle of rotation symbolically, leaving just a 2D optimization problem over the 2-sphere for the axis of rotation. While daunting in full generality, the case $A$ diagonal seems tractable.2011-10-10
  • 0
    @Hauke Strasdat: Frankly, this problem comes from a 3D computer vision problem. More precisely, it is a pose estimation problem. I read the paper "2000 - TPAMI - Fast and globally convergent pose estimation from video images", and find an interesting objective function there. I reformulated that objective function to this one, and try to see if I can find the closed-form solution. I notice you are also a student in computer vision. So I believe you may familiar with pose estimation, which is a very old problem.2011-10-10
  • 0
    @hardmath: Interesting! I believe gradient descent with orthogonality constraints may have been investigated by other people.2011-10-10
  • 0
    You might try asking this on http://scicomp.stackexchange.com/2012-01-12

1 Answers 1

3

This is a bit late, but I believe this might help.

Use the Cayley parametrization of orthogonal matrices. Example usage in optimization: http://www.caam.rice.edu/~wy1/paperfiles/Rice_CAAM_TR10-26_OptManifold.PDF

You might want to start by just understanding the Wiki article on the Cayley transform and why a parametrization helps (you can do the optimisation without constraints, which should be easier)

  • 1
    Please explain how this "might help". A link-only Answer risks becoming obsolete as links break, and it is advantageous to the Reader to have a clear expectation of what they would find if the link were followed.2014-07-23