PSDP: Woodgate Algorithm

[banrovegrie]

The basic algorithm has been implemented. Reformatting the code and testing are left. Putting in this PR so that we can discuss this tomorrow.

[banrovegrie]

@FanwangM let's run tests only after I have reformatted the code.

[banrovegrie]

I tested the algorithm for square matrices and it appears to work. 3 doubts remain which I have posted in the discussion forum.

[banrovegrie]

@FanwangM could you help me out on where tox is failing?

[FanwangM]

It's coding style issue, https://github.com/theochem/procrustes/runs/7303673817?check_suite_focus=true. You will have to google them and fix. @banrovegrie

[FanwangM]

Can you help finalize this algorithm as we discussed including the formatting style? Please feel free to tag me if you have questions. Thank you. @banrovegrie

[banrovegrie]

@FanwangM The algorithm has exact precision as expected. After implementing scaling and choosing $E_0 = I_n$, I obtained the exact results mentioned in the paper's examples.

Our algorithm also converges equally as fast.

[banrovegrie]

Hey, so I ran into an issue while using ProcrustesResult to return the error and required transformation. In case of ProcrustesResult, we aim to return $S, T$. They are defined as follows.

$$ |\mathbf{S}\mathbf{A}\mathbf{T} - \mathbf{B}|_{F}^2 = \text{Tr}\left[ \left(\mathbf{S}\mathbf{A}\mathbf{T} - \mathbf{B}\right)^\dagger \left(\mathbf{S}\mathbf{A}\mathbf{T} - \mathbf{B}\right)\right] $$

However, in our program, we are dealing with transformation only on the left-hand side. Namely, $\min_{\mathbf{P}} |F - \mathbf{P}G|^2$.

How should I proceed for this?

[banrovegrie]

Also, abiding by the terminology present in other modules, $A$ is considered as the matrix on which the transformation will be applied and $B$ is the target matrix.

Thus, our result in woodgate is effectively finding a left hand transformation $P$ such that $|PA - B|^2 = |B - PA|^2$ is minimum. Note that to draw parallel with the paper, $A$ is $G$ and $B$ is the matrix $F$.

[banrovegrie]

Other than these two persisting questions, everything else is complete. @FanwangM

[FanwangM]

Hey, so I ran into an issue while using ProcrustesResult to return the error and required transformation. In case of ProcrustesResult, we aim to return S,T. They are defined as follows.

|SAT−B|F2=Tr[(SAT−B)†(SAT−B)]

However, in our program, we are dealing with transformation only on the left-hand side. Namely, minP|F−PG|2.

How should I proceed for this?

The other matrix is defined as the identity matrix with the same shape.

[FanwangM]

The linter keeps complaining and needs to be fixed. Also, can you also add a test file for this module, either in this PR or another PR? Thank you. @banrovegrie

I will take a look at the codes again once these two are ready.

[banrovegrie]

Apparently, tox says the error is in softassign.py. That shouldn't be the case right?

************* Module procrustes.softassign
  procrustes/softassign.py:221:15: E1121: Too many positional arguments for method call (too-many-function-args)

[FanwangM]

Some general comments for this implementation.

• [x] Rename woodgate.py to psdp.py.
• [x] Rename function woodgate to psdp_woodgate as we have two more algorithms coming.
• [x] Only put psdp_woodgate as a public function that a user can access and put other functions as private functions.
• [x] Fix the matrix representation in the docstring as we use bold characters to denote matrix, such as $\mathbf{P}$.
• [ ] Try to avoid use @ operations and use np.dot if possible, https://numpy.org/doc/stable/reference/generated/numpy.linalg.multi_dot.html. This can help make things clean and consistent.
• [ ] We will need to make the argument names consistent and you can take a look at other examples in Procrustes package for reference.
• [ ] We will need a testing file.

Thank you for the nice work. @banrovegrie

[banrovegrie]

• [x] Renamed function woodgate to psdp_woodgate.

• [x] psdp_woodgate is now the only public function.

• [x] Bold characters represent matrices in docstring now.

• Testing file I will add in a different PR so that there we can talk about the efficiency of the implementation as well.

• Since, we will use the same testing for multiple algorithms, I think this makes more sense.

• In the case of small equations, I tried to use np.dot rather than @ but some of the formulae are quite elaborate and converting them too to np.dot might make the readability hard.

[banrovegrie]

I tested with tox locally. All the tests seem to pass. @FanwangM

[FanwangM]

Thanks for the new codes.

Since, we will use the same testing for multiple algorithms, I think this makes more sense. It makes sense to me and we can add more tests in the coming PR. For example, there are at least two numerical examples in the second paper.

In the case of small equations, I tried to use np.dot rather than @ but some of the formulae are quite elaborate and converting them too to np.dot might make the readability hard. Maybe I didn't make things clear before and sorry for the confusion. We should try np.linalg.multi_dot which will benefit the running performance, https://numpy.org/doc/stable/reference/generated/numpy.linalg.multi_dot.html#numpy.linalg.multi_dot. @banrovegrie

[banrovegrie]

Oh okay you wanted me to implement np.linalg.multi_dot makes sense. Will do it right away.

[banrovegrie]

I am just left to implement multi_dot. Once that is done, could you merge it so that I can start pushing the test using another PR and simultaneously start working on the new algorithm?

[banrovegrie]

In https://github.com/theochem/procrustes/pull/170/commits/2baf69adc757f7f8163c473c360655d3d12b0555, I have reimplemented @ with np.dot or np.linalg.mult_dot as required.

[banrovegrie]

@FanwangM could you run tests whenever you are free?

[FanwangM]

It looks good to me now and I am going to merge it. Thanks for the nice contribution! @banrovegrie