pulsatrix 1.1.0
Loading...
Searching...
No Matches
landmarks.hpp File Reference

Farthest-point landmarks: a subset of a large point cloud that covers it, with a certified bound on what persistent homology loses by using the subset. More...

#include <cstdint>
#include <vector>
#include "pulsatrix/tda/diagram_distance.hpp"
#include "pulsatrix/tda/persistence_diagram.hpp"
#include "pulsatrix/tda/point_cloud.hpp"
#include "pulsatrix/tensor.hpp"
Include dependency graph for landmarks.hpp:

Go to the source code of this file.

Classes

struct  pulsatrix::LandmarkOptions
 FarthestPointLandmarks()'s settings. Selection stops at whichever limit comes first. More...
 
struct  pulsatrix::Landmarks
 FarthestPointLandmarks()'s result. More...
 

Namespaces

namespace  pulsatrix
 

Functions

Landmarks pulsatrix::FarthestPointLandmarks (const Tensor &points, const LandmarkOptions &options)
 Picks farthest-point landmarks among the rows of points.
 
Landmarks pulsatrix::FarthestPointLandmarks (const PointCloud &cloud, DeviceBackend *backend, const LandmarkOptions &options)
 Landmarks of a cloud's points, computed on the given backend.
 
Tensor pulsatrix::LandmarkPoints (const Tensor &points, const Landmarks &landmarks)
 The landmark rows of points, as a (k, ...) tensor on points' backend.
 
PersistenceDiagram pulsatrix::WithSubsamplingBound (PersistenceDiagram diagram, const Landmarks &landmarks)
 A diagram of the landmarks re-certified against the whole cloud: its error_bound becomes its own plus the subsampling term, a bound on its bottleneck distance from the diagram of all the points (with exact distances).
 

Detailed Description

Farthest-point landmarks: a subset of a large point cloud that covers it, with a certified bound on what persistent homology loses by using the subset.

Persistent homology above H0 can't run on 100,000 activations. Farthest-point (maxmin) sampling picks landmarks greedily, each the point farthest from those already picked, so they spread over the whole cloud. Every point is then within the covering radius e of a landmark; the landmarks are within Hausdorff, hence Gromov-Hausdorff, distance e of the cloud; and Rips stability gives d_B(Dgm(landmarks), Dgm(cloud)) <= 2 e (the research notes' TDA-7 bound). The greedy choice also gives a covering radius within a factor of 2 of the best possible for the same number of landmarks (Gonzalez 1985).

Distances to each new landmark come from one GEMM against all points on the backend, so the full n x n matrix is never formed: memory is O(n + k d) beyond the points.