search

scikit-tda / DREiMac

Dimensionality Reduction with Eilenberg-MacLane Coordinates
Apache License 2.0
39 stars 13 forks source link

Fixing cocycle lifts with arbitrary integer coefficients #17

Closed vincent-grande closed 2 months ago

vincent-grande commented 2 months ago

Hi, I have just looked at the portion of DREiMac's code responsible for fixing lifts from prime coefficients to integer coefficients, as discussed in [1]. DREiMac does this using a linear program and scipy.optimize.milp. However, no bounds are passed to the milp-solver, which defaults to all variables assumed to be non-negative.

I might be wrong here, but I don't see any reason to enforce the non-negativity. In particular, I can imagine there to be extraordinarily rare cases where a fix depends on negative values to be available.

I have implemented a similar fix to faulty lifted Z/3Z coefficients for homology generators (I.e. cycles) on alpha-complexes in my own project [2], and there the integer linear program required negativity of some of the variables to be feasible (On the TREFOIL knot from DREiMac's documentation).

I have added empty bounds to the uses of milp in complexprojectivecoords.py and toroidalcoords.py. Sorry if I misunderstood something here! (I have tested the proposed changes using the unit tests and the fix_cocycle notebook and both worked.)

[1] de Silva, V., Morozov, D. & Vejdemo-Johansson, M. Persistent Cohomology and Circular Coordinates. Discrete Comput Geom 45, 737–759 (2011). [2] https://github.com/vincent-grande/topf

LuisScoccola commented 2 months ago

@vincent-grande good catch; indeed there is no reason the solution should be positive. Thanks a lot for realizing this, and fixing it!

As nitpicks: could you please revert the other two changes to toroidalcoords (this and this), and say "empty bounds" here (for consistency).

vincent-grande commented 2 months ago

@LuisScoccola Thanks for the quick reply and sure! The other changes seemed to have been autoformatting, but I have reverted them.

ctralie commented 2 months ago

Thank you so much @vincent-grande! @LuisScoccola, I'll let you handle the pull request. Also Luis, I wonder if this improves any examples that didn't work as well before. Do you have anything you thought should have worked better that this might improve?

LuisScoccola commented 2 months ago

@vincent-grande thanks again!

@ctralie it may be the case that fixing cocycles works faster now, since there are more solutions available. Also, it used to be the case that the algorithm would find no solution (or take a long time) when lifting cocycles with Z/2Z coefficients; I haven't had the chance to check this, but I feel like this might have been the issue.