# Welcome to Procrustes's Documentation!

Procrustes is a free, open-source, and cross-platform Python library for (generalized) Procrustes problems with the goal of finding the optimal transformation(s) that makes two matrices as close as possible to each other. Please use the following citation in any publication using Procrustes library:

"Procrustes: A Python Library to Find Transformations that Maximize the Similarity Between Matrices", F. Meng, M. Richer, A. Tehrani, J. La, T. D. Kim, P. W. Ayers, F. Heidar-Zadeh, Computer Physics Communications, 276(108334), 2022..

The Procrustes source code is hosted on GitHub and is released under the GNU General Public License v3.0. We welcome any contributions to the Procrustes library in accordance with our Code of Conduct; please see our Contributing Guidelines. Please report any issues you encounter while using Procrustes library on GitHub Issues. For further information and inquiries please contact us at qcdevs@gmail.com.

# Description of Procrustes Methods

Procrustes problems arise when one wishes to find one or two transformations, $$\mathbf{T} \in \mathbb{R}^{n \times n}$$ and $$\mathbf{S} \in \mathbb{R}^{m \times m}$$, that make matrix $$\mathbf{A} \in \mathbb{R}^{m \times n}$$ (input matrix) resemble matrix $$\mathbf{B} \in \mathbb{R}^{m \times n}$$ (target or reference matrix) as closely as possible:

$\underbrace{\min}_{\mathbf{S}, \mathbf{T}} \|\mathbf{S}\mathbf{A}\mathbf{T} - \mathbf{B}\|_{F}^2$

where, the $$\| \cdot \|_{F}$$ denotes the Frobenius norm defined as,

$\| \mathbf{A} \|_{F} = \sqrt{\sum^m_{i=1} \sum^n_{j=1} |a_{ij}|^2} = \sqrt{ \text{Tr} (\mathbf{A}^{\dagger} \mathbf{A})}$

Here $$a_{ij}$$ and $$\text{Tr}(\mathbf{A})$$ denote the $$ij$$-th element and trace of matrix $$\mathbf{A}$$, respectively. When $$\mathbf{S}$$ is an identity matrix, this is called a one-sided Procrustes problem, and when it is equal to $$\mathbf{T}$$, this becomes two-sided Procrustes problem with one transformation, otherwise, it is called two-sided Procrustes problem. Different Procrustes problems use different choices for the transformation matrices $$\mathbf{S}$$ and $$\mathbf{T}$$ which are commonly taken to be orthogonal/unitary matrices, rotation matrices, symmetric matrices, or permutation matrices. The table below summarizes various Procrustes methods supported:

 Procrustes Type $$\mathbf{S}$$ $$\mathbf{T}$$ Constraints $$\mathbf{I}$$ $$\mathbf{T}$$ None $$\mathbf{I}$$ $$\mathbf{Q}$$ $${\mathbf{Q}^{-1} = {\mathbf{Q}}^\dagger}$$ $$\mathbf{I}$$ $$\mathbf{R}$$ $$\begin{cases} \mathbf{R}^{-1} = {\mathbf{R}}^\dagger \\ \left | \mathbf{R} \right | = 1 \\ \end{cases}$$ $$\mathbf{I}$$ $$\mathbf{X}$$ $$\mathbf{X} = \mathbf{X}^\dagger$$ $$\mathbf{I}$$ $$\mathbf{P}$$ $$\begin{cases} [\mathbf{P}]_{ij} \in \{0, 1\} \\ \sum_{i=1}^n [\mathbf{P}]_{ij} = \sum_{j=1}^n [\mathbf{P}]_{ij} = 1 \\ \end{cases}$$ $$\mathbf{Q}_1^\dagger$$ $$\mathbf{Q}_2$$ $$\begin{cases} \mathbf{Q}_1^{-1} = \mathbf{Q}_1^\dagger \\ \mathbf{Q}_2^{-1} = \mathbf{Q}_2^\dagger \\ \end{cases}$$ $$\mathbf{Q}^{\dagger}$$ $$\mathbf{Q}$$ $$\mathbf{Q}^{-1} = \mathbf{Q}^\dagger$$ $$\mathbf{P}_1^{\dagger}$$ $$\mathbf{P}_2$$ $$\begin{cases} [\mathbf{P}_1]_{ij} \in \{0, 1\} \\ [\mathbf{P}_2]_{ij} \in \{0, 1\} \\ \sum_{i=1}^n [\mathbf{P}_1]_{ij} = \sum_{j=1}^n [\mathbf{P}_1]_{ij} = 1 \\ \sum_{i=1}^n [\mathbf{P}_2]_{ij} = \sum_{j=1}^n [\mathbf{P}_2]_{ij} = 1 \\ \end{cases}$$ $$\mathbf{P}^{\dagger}$$ $$\mathbf{P}$$ $$\begin{cases} [\mathbf{P}]_{ij} \in \{0, 1\} \\ \sum_{i=1}^n [\mathbf{P}]_{ij} = \sum_{j=1}^n [\mathbf{P}]_{ij} = 1 \\ \end{cases}$$

In addition to these Procrustes methods, summarized in the table above, the generalized Procrustes analysis (GPA)  and softassign algorithm  are also implemented in our package. The GPA algorithm seeks the optimal transformation matrices $$\mathbf{T}$$ to superpose the given objects (usually more than 2) with minimum distance,

$\begin{equation} \min \sum_{i<j}^{j} {\left\| \mathbf{A}_i \mathbf{T}_i - \mathbf{A}_j \mathbf{T}_j \right\|_F}^2 \end{equation}$

where $$\mathbf{A}_i$$ and $$\mathbf{A}_j$$ are the configurations and $$\mathbf{T}_i$$ and $$\mathbf{T}_j$$ denotes the transformation matrices for $$\mathbf{A}_i$$ and $$\mathbf{A}_j$$ respectively. When only two objects are given, the problem shrinks to generic Procrustes.

The softassign algorithm was first proposed to deal with quadratic assignment problem  inspired by statistical physics algorithms and has subsequently been developed theoretically  and extended to many other applications . Because the two-sided permutation Procrustes problem is a special case of the quadratic assignment problem, it can be used here. The objective function is to minimize $$E_{qap} (\mathbf{M}, \mu, \nu)$$, , which is defined as follows,

\begin{split}\begin{aligned} E_{q a p}(\mathbf{M}, \mu, \nu) = &-\frac{1}{2} \sum_{a i b j} \mathbf{C}_{a i ; b j} \mathbf{M}_{a i} \mathbf{M}_{b j} \\ & + \sum_{a} \mu_{a}\left(\sum_{i} \mathbf{M}_{a i} - 1 \right) + \sum_{i} \nu_{i} \left( \sum_{a} \mathbf{M}_{a i} - 1 \right) \\ & - \frac{\gamma}{2} \sum_{a i} \mathbf{M}_{a i}^{2} + \frac{1}{\beta} \sum_{a i} \mathbf{M}_{a i} \log \mathbf{M}_{a i} \end{aligned}\end{split}

Procrustes problems arise when aligning molecules and other objects, when evaluating optimal basis transformations, when determining optimal mappings between sets, and in many other contexts. This package includes the options to translate, scale, and zero-pad matrices, so that matrices with different centers/scaling/sizes can be considered.

User Documentation

API Documentation