Topological Optimization with Big Steps
Discrete & Computational Geometry - Trang 1-35 - 2024
Tóm tắt
Using persistent homology to guide optimization has emerged as a novel application of topological data analysis. Existing methods treat persistence calculation as a black box and backpropagate gradients only onto the simplices involved in particular pairs. We show how the cycles and chains used in the persistence calculation can be used to prescribe gradients to larger subsets of the domain. In particular, we show that in a special case, which serves as a building block for general losses, the problem can be solved exactly in linear time. This relies on another contribution of this paper, which eliminates the need to examine a factorial number of permutations of simplices with the same value. We present empirical experiments that show the practical benefits of our algorithm: the number of steps required for the optimization is reduced by an order of magnitude.
Tài liệu tham khảo
Anguelov, D., Srinivasan, P., Koller, D., Thrun, S., Rodgers, J., Davis, J.: Scape: shape completion and animation of people. In: ACM SIGGRAPH 2005 Papers, pp. 408–416 (2005)
Attali, D., Glisse, M., Hornus, S., Lazarus, F., Morozov, D.: Persistence-sensitive simplication of functions on surfaces in linear time. In: TopoInVis’ 09 (2009)
Bauer, U.: Ripser: efficient computation of Vietoris-Rips persistence barcodes. J. Appl. Comput. Topol. (2021). https://doi.org/10.1007/s41468-021-00071-5
Bauer, U., Lange, C., Wardetzky, M.: Optimal topological simplification of discrete functions on surfaces. Discrete Comput. Geom. 47(2), 347–377 (2012)
Bauer, U., Kerber, M., Reininghaus, J., Wagner, H.: Phat-persistent homology algorithms toolbox. J. Symbol. Comput. 78, 76–90 (2017)
Bendich, P., Edelsbrunner, H., Morozov, D., Patel, A.: Homology and robustness of level and interlevel sets. Homol. Homotopy Appl. 15(1), 51–72 (2013)
Brüel-Gabrielsson, R., Nelson, B.J., Dwaraknath, A., Skraba, P., Guibas, L.J., Carlsson, G.: A topology layer for machine learning. In: Proceedings of the International Conference on Artificial Intelligence and Statistics (AISTATS), pp. 1553–1563 (2020)
Carriere, M., Chazal, F., Glisse, M., Ike, Y., Kannan, H., Umeda, Y.: Optimizing persistent homology based functions. In: Meila, M., Zhang, T. (eds.) Proceedings of the 38th International Conference on Machine Learning. Proceedings of Machine Learning Research, vol. 139, pp. 1294–1303. PMLR (2021). proceedings.mlr.press/v139/carriere21a.html
Chen, C., Kerber, M.: Persistent homology computation with a twist. In: Proceedings 27th European Workshop on Computational Geometry, Vol. 11, pp. 197–200 (2011). eurocg11.inf.ethz.ch/abstracts/22.pdf
Chen, C., Ni, X., Bai, Q., Wang, Y.: A topological regularizer for classifiers via persistent homology. In: Proceedings of the International Conference on Artificial Intelligence and Statistics (AISTATS), pp. 2573–2582 (2019)
Cohen-Steiner, D., Edelsbrunner, H., Morozov, D.: Vines and vineyards by updating persistence in linear time. In: Proceedings of the Annual Symposium on Computational Geometry, pp. 119–126 (2006)
Davis, D., Drusvyatskiy, D., Kakade, S., Lee, J.D.: Stochastic subgradient method converges on tame functions. Found. Comput. Math. 20(1), 119–154 (2020). https://doi.org/10.1007/s10208-018-09409-5
de Silva, V., Morozov, D., Vejdemo-Johansson, M.: Dualities in persistent (co)homology. Inverse Probl. 27(12), 124003 (2011). https://doi.org/10.1088/0266-5611/27/12/124003
Edelsbrunner, H., Morozov, D., Pascucci, V.: Persistence-sensitive simplification functions on 2-manifolds. In: Proceedings of the Annual Symposium on Computational Geometry, pp. 127–134. ACM (2006)
Edelsbrunner, H., Morozov, D.: Persistent homology. In: Handbook of Discrete and Computational Geometry, pp. 637–661. Chapman and Hall/CRC, Boca Raton (2017)
Edelsbrunner, H., Harer, J.: Computational Topology: An Introduction. American Mathematical Society, Providence (2010)
Edelsbrunner, H., Letscher, D., Zomorodian, A.: Topological persistence and simplification. Discrete Comput. Geom. 28(4), 511–533 (2002). https://doi.org/10.1007/s00454-002-2885-2
Edelsbrunner, H., Morozov, D., Patel, A.: Quantifying transversality by measuring the robustness of intersections. Found. Comput. Math. 11(3), 345–361 (2011). https://doi.org/10.1007/s10208-011-9090-8
Gameiro, M., Hiraoka, Y., Obayashi, I.: Continuation of point clouds via persistence diagrams. Nonlinear phenomena. Physica D 334, 118–132 (2016). https://doi.org/10.1016/j.physd.2015.11.011
Guo, F., Li, H., Daughton, W., Liu, Y.-H.: Formation of hard power laws in the energetic particle spectra resulting from relativistic magnetic reconnection. Phys. Rev. Lett. 113, 155005 (2014). https://doi.org/10.1103/PhysRevLett.113.155005
Klacansky, P.: Open Scientific Visualization Datasets. klacansky.com/open-scivis-datasets/
Leygonie, J., Carrière, M., Lacombe, T., Oudot, S.: A gradient sampling algorithm for stratified maps with applications to topological data analysis. arXiv:2109.00530 (2021)
Luo, Y., Nelson, B.J.: Accelerating iterated persistent homology computations with warm starts. arXiv:2108.05022 (2021)
Morozov, D.: Homological illusions of persistence and stability. PhD thesis, Duke University (2008)
Nigmetov, A., Krishnapriyan, A.S., Sanderson, N., Morozov, D.: Topological regularization via Persistence-Sensitive optimization. arXiv:2011.05290 (2020)
Poulenard, A., Skraba, P., Ovsjanikov, M.: Topological function optimization for continuous shape matching. Comput. Graph. Forum 37(5), 13–25 (2018). https://doi.org/10.1111/cgf.13487
Rosenberg, D., Pouquet, A., Marino, R., Mininni, P.D.: Evidence for Bolgiano-Obukhov scaling in rotating stratified turbulence using high-resolution direct numerical simulations. Phys. Fluids 27(5), 055105 (2015). https://doi.org/10.1063/1.4921076
Solomon, Y., Wagner, A., Bendich, P.: A fast and robust method for global topological functional optimization. In: International Conference on Artificial Intelligence and Statistics, pp. 109–117 (2021). PMLR
Tierny, J., Pascucci, V.: Generalized topological simplification of scalar fields on surfaces. IEEE Trans. Vis. Comput. Graphics 18(12), 2005–2013 (2012). https://doi.org/10.1109/TVCG.2012.228
Trailie, C.: PyHKS. GitHub. github.com/ctralie/pyhks (2018)