More Like this

1. Apex Representatives

   https://doi.org/10.4230/lipics.socg.2025.40  

   Dey, Tamal K; Hou, Tao; Morozov, Dmitriy (January 2025, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Aichholzer, Oswin; Wang, Haitao (Ed.)

   Given a zigzag filtration, we want to find its barcode representatives, i.e., a compatible choice of bases for the homology groups that diagonalize the linear maps in the zigzag. To achieve this, we convert the input zigzag to a levelset zigzag of a real-valued function. This function generates a Mayer-Vietoris pyramid of spaces, which generates an infinite strip of homology groups. We call the origins of indecomposable (diamond) summands of this strip their apexes and give an algorithm to find representative cycles in these apexes from ordinary persistence computation. The resulting representatives map back to the levelset zigzag and thus yield barcode representatives for the input zigzag. Our algorithm for lifting a p-dimensional cycle from ordinary persistence to an apex representative takes O(p ⋅ m log m) time. From this we can recover zigzag representatives in time O(log m + C), where C is the size of the output. 

   more » « less
2. A Survey on the High Performance Computation of Persistent Homology

   https://doi.org/10.1109/TKDE.2022.3147070  

   Malott, Nicholas; Chen, Shangye; Wilsey, Philip (January 2022, IEEE Transactions on Knowledge and Data Engineering)

   Persistent Homology is a computational method of data mining in the field of Topological Data Analysis. Large-scale data analysis with persistent homology is computationally expensive and memory intensive. The performance of persistent homology has been rigorously studied to optimize data encoding and intermediate data structures for high-performance computation. This paper provides an application-centric survey of the High-Performance Computation of Persistent Homology. Computational topology concepts are reviewed and detailed for a broad data science and engineering audience. 

   more » « less
3. Kernel multigrid on manifolds

   https://doi.org/10.1016/j.jco.2024.101900  

   Hangelbroek, Thomas; Rieger, Christian (February 2025, Journal of Complexity)

   Kernel methods for solving partial differential equations work coordinate-free on the surface and yield high approximation rates for smooth solutions. Localized Lagrange bases have proven to alleviate the computational complexity of usual kernel methods for data fitting problems, but the efficient numerical solution of the ill-conditioned linear systems of equations arising from kernel- based Galerkin solutions to PDEs is a challenging problem which has not been addressed in the literature so far. In this article we apply the framework of the geometric multigrid method with a τ ≥ 2-cycle to scattered, quasi-uniform point clouds on the surface. We show that the resulting solver can be accelerated by using the Lagrange function decay and obtain satisfying convergence rates by a rigorous analysis. In particular, we show that the computational cost of the linear solver scales log-linear in the degrees of freedom. 

   more » « less
4. A Mixed-Integer Fractional Optimization Approach to Best Subset Selection

   https://doi.org/10.1287/ijoc.2020.1031  

   Gómez, Andrés; Prokopyev, Oleg A. (March 2021, INFORMS Journal on Computing)

   null (Ed.)

   We consider the best subset selection problem in linear regression—that is, finding a parsimonious subset of the regression variables that provides the best fit to the data according to some predefined criterion. We are primarily concerned with alternatives to cross-validation methods that do not require data partitioning and involve a range of information criteria extensively studied in the statistical literature. We show that the problem of interest can be modeled using fractional mixed-integer optimization, which can be tackled by leveraging recent advances in modern optimization solvers. The proposed algorithms involve solving a sequence of mixed-integer quadratic optimization problems (or their convexifications) and can be implemented with off-the-shelf solvers. We report encouraging results in our computational experiments, with respect to both the optimization and statistical performance. Summary of Contribution: This paper considers feature selection problems with information criteria. We show that by adopting a fractional optimization perspective (a well-known field in nonlinear optimization and operations research), it is possible to leverage recent advances in mixed-integer quadratic optimization technology to tackle traditional statistical problems long considered intractable. We present extensive computational experiments, with both synthetic and real data, illustrating that the new fractional optimization approach is orders of magnitude faster than existing approaches in the literature. 

   more » « less
5. Harmonic Persistent Homology

   https://doi.org/10.1137/22M1518761  

   Basu, Saugata; Cox, Nathanael (March 2024, SIAM Journal on Applied Algebra and Geometry)

   We introduce harmonic persistent homology spaces for filtrations of finite simplicial complexes. As a result we can associate concrete subspaces of cycles to each bar of the barcode of the filtration. We prove stability of the harmonic persistent homology subspaces, as well as the subspaces associated to the bars of the barcodes, under small perturbations of functions defining them. We relate the notion of ``essential simplices'' introduced in an earlier work to identify simplices which play a significant role in the birth of a bar, with that of harmonic persistent homology. We prove that the harmonic representatives of simple bars maximizes the ``relative essential content'' amongst all representatives of the bar, where the relative essential content is the weight a particular cycle puts on the set of essential simplices. \footnote{An extended abstract of the paper appeared in the Proceedings of the IEEE Symposium on the Foundations of Computer Science, 2021.} 

   more » « less