More algorithms on PSDP

[FanwangM]

The original "algorithm 3" has been peer reviewed (I think; it is published in a conference proceedings and that is never a sure thing).
http://www.scielo.org.co/pdf/rcm/v55n1/0034-7426-rcm-55-01-109.pdf

However, I really like Fanwang's suggestion. The Oviedo paper (algorithm 3) performs similarly to what they call PARATAN and what the above reference calls PARTAN. The above reference seems to have good performance, and has four closely related algorithms which could be implemented simulataneously, switching between the algorithms as specified by the user by a keyword. This is explained at the top of Section 5.

Specifically, the

• projected gradient method
• fast gradient method
• parallel tangents method
• semi-analytic fast gradient method

This gives a nice alternative to the first two algorithms, which focus on a more analytic approach (more like the other methods we have considered). This is a numerical approach, and perhaps might be faster (hard to know until we test).

Originally posted by @PaulWAyers in #189 (comment)

[FanwangM]

For those who are interested, people can work with the following algorithms listed in Gillis, N., & Sharma, P. (2018). A semi-analytical approach for the positive semidefinite procrustes problem. Linear Algebra and its Applications, 540, 112-137.

• projected gradient method
• fast gradient method
• parallel tangents method
• semi-analytic fast gradient method

This paper is mentioned in #98.

[banrovegrie]

More info about MATLAB implementation of the spectral gradient method is present in #189.

[banrovegrie]

Since, OptPSDP (from Oviedo's paper) seems to be performing better on average, I guess we will include that to our PSDP module as the third algorithm for now?

@FanwangM @PaulWAyers

[abhishekmittal15]

Hi, I am Abhishek Mittal. @banrovegrie introduced me to this repository and I found the work really interesting. I would like to contribute by starting off with this issue.

[PaulWAyers]

@abhishekmittal15 thanks for your help. I'll add you to the organization.

[PaulWAyers]

@banrovegrie it is OK to use the Oviedo algorithm, but the performance does not seem much better than the PARATAN. In any event, I think the algorithm is quite similar to the algorithms from this issue, so there should be a single implementation that has all of these optimization-based strategies I think. I will assign you to this issue also.

[banrovegrie]

Yep, we are almost done with implementing OptPSDP (so we can benchmark it). I will push the code in a few minutes. I think tests might fail and we can debug them iteratively.

[FanwangM]

Welcome on board! @abhishekmittal15

I will be working with both you and @banrovegrie. Feel free to tag me if there is anything you need. Thanks.

[banrovegrie]

@PaulWAyers @FanwangM What should be the next algorithm for us to plan on implementing?

[PaulWAyers]

I'm not sure what @FanwangM thinks, but I think that if you want to implement more algorithms in Procrustes, I wouldn't focus on PDSP but instead something else. One possibility would be to extend the permutation Procrustes algorithms available: it's becoming clear that that is one of the most useful (and tricky) cases.

[FanwangM]

I agree. Let's shift our focus to permutation Procrustes which are more interesting and practically useful. But I don't have any paper or algorithm in mind yet. I have tried to do some literature research on two-sided permutation Procrustes problem last weekend and didn't find any interesting y et.

[PaulWAyers]

I think I have an interesting algorithm. Let me look through my notes.

[PaulWAyers]

@FanwangM when the last pull requests on this issue are merged, please close it.

[FanwangM]

Sure. I will do it.

[FanwangM]

@abhishekmittal15 is contributing a new implementation for PSDP. Do you think we should shift our focus to permutation-related Procrustes problem? If so, do you have something in your mind? Thanks. @PaulWAyers

I will close this issue once #198 is merged.

[PaulWAyers]

I do think we should shift our focus to permutation methods. Let me write some notes.

The other main outstanding issue is a bit of a larger refactoring so that we can treat multiple/mixed Procrustes problems more efficiently. But that probably should wait for other key methods to be implemented.

The issue here is #76 but I'd do issue #49 (and maybe #32) first though.

[PaulWAyers]

I would look at #80 and #65 as key permutation-Procrustes-related issues.

[FanwangM]

We have merged #198 and we are not adding more PSDP algorithms for now.