Skip to main content

Questions tagged [procrustes-problem]

The Orthogonal Procrustes Problem is a matrix approximation problem in linear algebra. In its classical form, one is given two matrices, $A$ and $B$, and is asked to find an orthogonal matrix $R$ that most closely maps $A$ to $B$.

Filter by
Sorted by
Tagged with
1 vote
1 answer
36 views

I want to solve the orthogonal procrustses problem, but I am confused by the deformed form.

I'm studying about orthogonal Procrustses problem. Now, I wonder if there is a way to solve the orthogonal procrustses problem when the orthogonal matrix $Q$ is located in two or more terms. Also, the ...
Kisoo kim's user avatar
4 votes
0 answers
128 views

Procrustes with inequality constraint

I am interested in a variant of the orthogonal Procrustes problem $$ \begin{array}{ll} \underset{X} {\text{minimize} } & \| X A - B \|_{\text F} \\ \text{subject to} & X^TX = I \\ & (X^T ...
xdaimon's user avatar
  • 87
1 vote
1 answer
35 views

Orthogonal procrustes with kernel constraint

Given a matrix $M \in \mathbb{R}^{n \times m}$ with $n > m$ and an arbitrary vector $v \in \mathbb{R}^n$, I am looking for an analytical solution for the orthogonal matrix $R \in \mathbb{R}^{n \...
tommym's user avatar
  • 371
0 votes
0 answers
26 views

Finding optimal orthogonal matrix that transforms onto a subspace

I have two matrices with orthonormal columns, $A$ $(k\times n)$ and $B$ $(k\times m)$, with $k \ge m \ge n$. I would like to find the optimal orthogonal $(n\times n)$ matrix, $T$, that transforms $A$ ...
Jellby's user avatar
  • 247
2 votes
1 answer
73 views

Why projection onto the Stiefel manifold fails to solve the orthogonal Procrustes problem

The orthogonal Procrustes problem finds an orthogonal matrix $\Omega$ minimizing the Procrustes objective: $$ \min_\Omega ||\Omega A - B||_F, \quad \Omega^\top \Omega = I $$ It is well known that the ...
calmcc's user avatar
  • 251
0 votes
0 answers
83 views

Procrustes Problem With Scaling

Given matrices $A,B \in \mathbb{R}^{m,n}$, the orthogonal Procrustes problem asks to find an orthogonal matrix $Q \in \mathbb{R}^{n \times n}$ such that $$\|AQ - B\|_F^2$$ is minimized. There is a ...
Frederic Chopin's user avatar
0 votes
2 answers
89 views

Procrustes algorithm with non-square datasets causing issues with power

Context I'm trying to use Procrustes algorithm as defined in this answer. When trying to run this I get an error saying the matrix isn't square so it cant calculate the power of the matrix: ...
Joe Jankowiak's user avatar
2 votes
1 answer
118 views

Solution to a Procrustes-like Problem

I recently came across the following problem that resembles a Procrustes problem and I wonder if an analytic solution for this problem might exist: $$\underset{(R,\alpha)}{\operatorname{argmin}} ||RAe^...
Mantabit's user avatar
  • 203
0 votes
0 answers
131 views

Solving a variant of an orthogonal Procrustes problem

While reading the following paper on an optimization problem, there was a variant of an orthogonal Procrustes problem, where the solution is an element of the Stiefel manifold. The authors provided a ...
schlodinger's user avatar
1 vote
0 answers
47 views

Find $Q$ in $R_2 = Q^TR_1Q$ where all matrices $R_1, R_2, Q$ are 3x3 rotations

Can we obtain $Q$ in $$R_2 = Q^TR_1Q$$ where $R_1, R_2, Q$ are all 3x3 rotation matrices, $R_1 \ne R2$, and $\operatorname{trace}(R_1)=\operatorname{trace}(R_2)$? I have a problem where $R_1$ and $R_2$...
Kay's user avatar
  • 571
1 vote
2 answers
945 views

Projection onto the Stiefel manifold and the orthogonal Procrustes problem

Let $m$ and $n$ be positive integers such that $m \ge n$, the case with $m >n$ being particularly interesting to us. The Stiefel manifold is \begin{equation} \mathbb{S}^{m, n} = \{X \in \mathbb{R}^{...
Nuno's user avatar
  • 658
0 votes
0 answers
74 views

Trace-maximizing orthogonal rotation

Let $A\in R^{m\times m}$. Consider the following problem: $$ \begin{align} \max \,& \langle A, X\rangle\\ \text{s.t.}\,&X'X=I_m\\ &X\in R^{m\times m} \end{align} $$ where $\langle X, Y\...
gappy's user avatar
  • 739
1 vote
1 answer
588 views

How is Procrustes Distance Defined?

How is Procrustes Distance defined between two given datasets? Assume that the datasets each of them having "k" points in "n" dimensions. I couldn't find a proper source anywhere ...
truth_seeker's user avatar
1 vote
1 answer
60 views

Determining a family of Solutions to an underconstrained Modified Wahba's Problem, $J = \sum_{i=1}^{N} \frac{1}{2} \|a_i - RQR^Tb_i \|^2$

I have a minimisation problem of the form: $$ J(R) = \underset{R}{\mathrm{argmin}} \sum_{i=1}^{N} \frac{1}{2}\|a_i - RQR^T b_i \|^2 $$ Where $Q\in SO\{3\}$ and $a_i, b_i \in \mathbb{R}^3$ are known, ...
Damien's user avatar
  • 1,566
1 vote
3 answers
364 views

Is there a natural way to "project" an arbitrary matrix to an orthogonal matrix?

I am dealing with an optimization problem where I need to find an optimal rotation matrix. Let me first formulate the problem. Input: An initial rotation matrix $M\in SO(3)\subset\mathbb{R}^{3\times ...
trisct's user avatar
  • 5,241
2 votes
1 answer
177 views

Optimizing Trace$(Q^TZ)$ subject to $Q^TQ=I$

Let $Z \in \mathbb{R}^{m \times n}$ be a tall matrix ($m > n$). Solve the following optimization problem in $Q \in \mathbb{R}^{m \times n}$ $$\begin{array}{ll} \text{maximize} & \mbox{Tr} \left(...
kkcocoqq's user avatar
  • 306
2 votes
1 answer
360 views

Convexity of the orthogonal Procrustes problem

Given two orthogonal matrices ${\bf{M}} \in {{\Bbb{R}}^{m \times n}}$ and ${\bf{N}} \in {{\Bbb{R}}^{m \times n}}$, there is an orthogonal transformation matrix ${\bf{T}} \in {{\Bbb{R}}^{n \times n}}$ ...
ar_k's user avatar
  • 51
2 votes
1 answer
731 views

Orthogonal (unitary) Procrustes problem (complex matrices)

The orthogonal Procrustes problem can be stated as finding the orthogonal matrix $\Omega$ that maps $A$ most closely to $B$ $$\arg\min_{\Omega}\|A\Omega - B\|_F \quad\mathrm{subject\ to}\quad \Omega^...
zilver's user avatar
  • 61
0 votes
2 answers
93 views

Matrix derivative in images matching problem

Problem Suppose zero-centered matrices $\mathbf{X}$ and $\mathbf{Y}$ of shape $\mathbb{R}^{n\times 2}$. Each row of $\mathbf{X}$ and $\mathbf{Y}$ represents a point on 2-D plane. Therefore, they each ...
Mr.Robot's user avatar
  • 646
8 votes
1 answer
2k views

Find a permutation of the rows of a matrix that minimizes the sum of squared errors

I'm struggling with the following problem: Let $A, B \in \mathbb R^{n \times d}$. Denote by $\mathcal{P}$ the set of all possible permutations of the rows of $A$. Find a permutation $\pi \in \...
Eva's user avatar
  • 101
0 votes
1 answer
142 views

Procrustes Problem with Maximization (Instead of Minimization)

The classical (orthogonal) Procrustes problem is to solve the optimization problem $$ \begin{array}{rl} \min&\|\Omega{A}-B\|_F\\ \text{s.t.}&\Omega^\mathrm{T}\Omega=I \end{array} $$ The ...
David M.'s user avatar
  • 2,633
1 vote
2 answers
169 views

Distance of matrix to $\mbox{SO}(n)$ w.r.t. Frobenius norm

Given $A \in \mathbb R^{n\times n}$, I was told that $$\mbox{dist}(A, \mbox{SO}(n)) = \inf_{Q \in \mbox{SO}(n)} |A-Q| \overset ? = \inf_{Q \in \mbox{SO}(n)} | Q^\top A - \text{Id} |$$ where we use ...
Pink Panther's user avatar
2 votes
1 answer
469 views

Nearest (in the Frobenius sense) semi-orthogonal matrix

I found a question about finding a nearest semi-orthogonal matrix, but I need to find the nearest semi-orthogonal matrix subject to a slightly different constraint. Given $m \times n$ matrix $M$, $$ \...
Buu Pham's user avatar
-1 votes
1 answer
83 views

Optimal Rotation between two sets of points [closed]

Let $p_i,q_j\in\mathbb{R}^3$ be sequences of points with $i,j\in\{1,2,3\}$. How can I solve the optimization problem $$D:=\arg\min_{R,t}\left(\max_{i=1,2,3}\Vert p_i-(Rq_i+t) \Vert\right),$$ where $...
Aleph0's user avatar
  • 101
1 vote
0 answers
473 views

Least squares minimization subject to generalized orthogonality constraint?

I'd like to solve the following minimization problem: $$ \min_{\Phi^T D \Phi = I_k} \frac{1}{2}\|\Phi - Y\|_F^2, $$ where $\Phi \in \mathbb{R}^{n \times k}$, $D \in \mathbb{R}^{n \times n}$ is a (...
Alec Jacobson's user avatar
1 vote
1 answer
673 views

Deriving the Optimal Solution of the Orthogonal Procrustes Problem

I am trying to work through the Orthogonal Procrustes Problem but I do not understand a particular step. I would appreciate any help in understanding the steps the author goes from the first line to ...
Evan Gertis's user avatar
14 votes
3 answers
2k views

Solve least-squares minimization from overdetermined system with orthonormal constraint

I would like to find the rectangular matrix $X \in \mathbb{R}^{n \times k}$ that solves the following minimization problem: $$ \mathop{\text{minimize }}_{X \in \mathbb{R}^{n \times k}} \left\| A X - ...
Alec Jacobson's user avatar
25 votes
1 answer
6k views

Showing that matrix $Q=UV^T$ is the nearest orthogonal matrix to $A$.

Let $A$ be an $m \times n$ matrix with a singular value decomposition $A=U\Sigma V^T$. Show that the matrix $Q=UV^T$ is the nearest orthogonal matrix to $A$, i.e., $$\min_{Q^TQ=I_{n \times n}} \|A-Q\...
BadAtMath's user avatar
  • 429
2 votes
1 answer
1k views

Find an orthogonal matrix to minimize the norm

Let $A\in \mathbb{R}^{n\times n}$. Find $\overline O$, orthogonal matrix, to minimize $\|A-O\|_F$. That is; $$\min_{O\in O(n)} \|A-O\|_F$$ Where $O(n)$ are the set of orthogonal matrices of $\mathbb{R}...
blueplusgreen's user avatar
0 votes
0 answers
321 views

How to apply Procrustes transformation to a single point

I guess this is probably a too simple question for most of you but my algebra skills are very limited (ashamed). I have run two PCA analyses and conducted a Procrustes analyses to fit one matrix (...
Federico's user avatar
3 votes
1 answer
358 views

Orthogonal Procrustes Problem using the operator norm

If $A, B \in \mathbb{R}^{n \times r}$ are two matrices, the solution to the so-called Orthogonal Procrustes Problem $$\min_{O^TO=I_r} \|AO-B\|$$ is given by the polar factor of $A^TB$ whenever the ...
squattyroo's user avatar
2 votes
0 answers
742 views

Orthogonal Procrustes Problem

The classical Orthogonal Procrustes Problem is $$\begin{array}{ll} \text{minimize} & \|A\Omega-B\|_{F}\\ \text{subject to} & \Omega'\Omega=I\end{array}$$ where $A$ and $B$ are known matrices....
Mael's user avatar
  • 751
5 votes
0 answers
223 views

Orthogonal Procrustes Variant

(author note: this question was also asked on mathoverflow). The orthogonal Procrustes problem seeks a matrix $M$ that minimizes $||AM-B||_F$ subject to $M^TM=I$, where $M$ is $d\times d$ and both $A$...
Matt's user avatar
  • 51
1 vote
1 answer
543 views

Orthogonal procrustes problem using quaternions

Hello I'm trying solve orthogonal procrustes problem in 3d with a help of quaternions. Original problem is: For matrix $A$ find orthogonal matrix $Q$ that $$||A-Q||_F =\min_{\Omega \in SO(3)} ||A-\...
tom's user avatar
  • 4,616
1 vote
0 answers
831 views

Variant of orthogonal Procrustes problem

I want to find an anti-symmetric matrix $T$ which minimizes $\|A-e^TBe^{-T}\|^2 + \mu\|T\|^2$, where $A$ and $B$ are symmetric positive definite matrices and the norm is the Frobenius matrix norm. The ...
uekstrom's user avatar
  • 133