search

theochem / procrustes

Python library for finding the optimal transformation(s) that makes two matrices as close as possible to each other.
https://procrustes.qcdevs.org/
GNU General Public License v3.0
109 stars 20 forks source link

positive semi-definite Procrustes problem #98

Open FanwangM opened 3 years ago

FanwangM commented 3 years ago

This positive semi-definite Procrustes problem is trying to

More details can be found at Woodgate, K. G. (1993, December). A new algorithm for the positive semi-definite Procrustes problem. In Proceedings of 32nd IEEE Conference on Decision and Control (pp. 3596-3601). IEEE..

This will be on the to-do list of our package, but not for this stage.

PaulWAyers commented 3 years ago

This would be really cool to have. It's also nice because it explains (finally!) why the symmetric Procrustes problem is useful!!!

FanwangM commented 3 years ago

some more papers related to positive semi-definite Procrustes problem

  1. Kiskiras, J., & Halikias, G. D. (2007). A note on the complex semi‐definite matrix Procrustes problem. Numerical Linear Algebra with Applications, 14(6), 485-502.
  2. Gillis, N., & Sharma, P. (2018). A semi-analytical approach for the positive semidefinite Procrustes problem. Linear Algebra and its Applications, 540, 112-137.
  3. Jingjing, P., Qingwen, W., Zhenyun, P., & Zhencheng, C. (2019). Solution of symmetric positive semidefinite Procrustes problem. The Electronic Journal of Linear Algebra, 35, 543-554.
  4. Andersson, L. E., & Elfving, T. (1997). A constrained Procrustes problem. SIAM Journal on Matrix Analysis and Applications, 18(1), 124-139.
  5. Oviedo, H. F. (2019). A Spectral Gradient Projection Method for the Positive Semi-definite Procrustes Problem. arXiv preprint arXiv:1908.06497. with matlab codes in https://www.mathworks.com/matlabcentral/fileexchange/64597-spectral-projected-gradient-method-for-the-positive-semi-definite-procrustes-problem

This list is built for future implementation.

FanwangM commented 2 years ago

I would propose these algorithms be prioritized.

  1. Woodgate, K. G. (1993, December). A new algorithm for the positive semi-definite Procrustes problem. In Proceedings of 32nd IEEE Conference on Decision and Control (pp. 3596-3601). IEEE.
  2. Jingjing, P., Qingwen, W., Zhenyun, P., & Zhencheng, C. (2019). Solution of symmetric positive semidefinite Procrustes problem. The Electronic Journal of Linear Algebra, 35, 543-554.
  3. Oviedo, H. F. (2019). A Spectral Gradient Projection Method for the Positive Semi-definite Procrustes Problem. arXiv preprint arXiv:1908.06497.

The proposed algorithms either come with numerical tests example or source code in Matlab. This makes the testing of the code easy.

PaulWAyers commented 2 years ago

Probably just implementing one algorithm here may suffice, at least at first. A related problem with an explicit solution is to find the closest semidefinite matrix to a given matrix (one matrix = I) or the closest semidefinite matrix with a given trace to a given matrix. There are analytic solutions here, and they can be used as testing. If it were possible, it would be nice to be able to solve the positive semi-definite Procrustes problem with a trace constraint, since often positive semidefinite matrices with specified (usually unit) trace show in up quantum-mechanical examples (as (reduced) density matrices).

FanwangM commented 2 years ago

Thank you for the suggestions. I have changed the GSoC documentation accordingly.

For the closest semidefinite matrix problem, do you mean something like https://nhigham.com/2021/01/26/what-is-the-nearest-positive-semidefinite-matrix/?

Also, an analog problem is the nearest correlation matrix problem, https://nhigham.com/2013/02/13/the-nearest-correlation-matrix/. I am not sure how this can be used for chemistry, but this is interesting, at least from a math perspective. And it's application examples are listed at the end of the post.

PaulWAyers commented 2 years ago

Yep, these references are good leads. The nearest correlation matrix is obviously interesting for machine learning.

The trace-constraint is yet another linear constraint (so similar to the correlation matrix) but has an explicit solution, see the appendix of https://doi.org/10.1063/1.4994618.

In general, adding any set of linear constraint(s) on the solution is helpful (i.e., Tr[Q_k*P] = q_k) where P is positive semidefinite, Q_k is a linear operator (Hermitian in all the cases I can think of), and q_k is a float.