Constructs (weak) witness complex for a given table of nearest landmarks with respect to witnesses. More...
Detailed Description
Author
Siargey Kachanovich
Witness complex representation
Definitions
Witness complex is a simplicial complex defined on two sets of points in \(\mathbb{R}^D\):
\(W\) set of witnesses and
\(L\) set of landmarks.
Even though often the set of landmarks \(L\) is a subset of the set of witnesses \( W\), it is not a requirement for the current implementation.
Landmarks are the vertices of the simplicial complex and witnesses help to decide on which simplices are inserted via a predicate "is witnessed".
De Silva and Carlsson in their paper [de2004topological] differentiate weak witnessing and strong witnessing:
weak: \( \sigma \subset L \) is witnessed by \( w \in W\) if \( \forall l \in \sigma,\ \forall l' \in \mathbf{L \setminus \sigma},\ d(w,l) \leq d(w,l') \)
strong: \( \sigma \subset L \) is witnessed by \( w \in W\) if \( \forall l \in \sigma,\ \forall l' \in \mathbf{L},\ d(w,l) \leq d(w,l') \)
where \( d(.,.) \) is a distance function.
Both definitions can be relaxed by a real value \(\alpha\):
weak: \( \sigma \subset L \) is \(\alpha\)-witnessed by \( w \in W\) if \( \forall l \in \sigma,\ \forall l' \in \mathbf{L \setminus \sigma},\ d(w,l)^2 \leq d(w,l')^2 + \alpha^2 \)
strong: \( \sigma \subset L \) is \(\alpha\)-witnessed by \( w \in W\) if \( \forall l \in \sigma,\ \forall l' \in \mathbf{L},\ d(w,l)^2 \leq d(w,l')^2 + \alpha^2 \)
which leads to definitions of weak relaxed witness complex (or just relaxed witness complex for short) and strong relaxed witness complex respectively.
Strongly witnessed simplex
In particular case of 0-relaxation, weak complex corresponds to witness complex introduced in [de2004topological], whereas 0-relaxed strong witness complex consists of just vertices and is not very interesting. Hence for small relaxation weak version is preferable. However, to capture the homotopy type (for example using Gudhi::persistent_cohomology::Persistent_cohomology) it is often necessary to work with higher filtration values. In this case strong relaxed witness complex is faster to compute and offers similar results.
Implementation
The two complexes described above are implemented in the corresponding classes
Example3: Computing relaxed witness complex persistence from a distance matrix
In this example we compute the relaxed witness complex persistence from a given matrix of closest landmarks to each witness. Each landmark is given as the couple (index, distance).
/* This file is part of the Gudhi Library. The Gudhi library
* (Geometric Understanding in Higher Dimensions) is a generic C++
* library for computational topology.
*
* Author(s): Siargey Kachanovich
*
* Copyright (C) 2016 INRIA (France)
*
* This program is free software: you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation, either version 3 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program. If not, see <http://www.gnu.org/licenses/>.
*/
#define BOOST_PARAMETER_MAX_ARITY 12
#include <gudhi/Simplex_tree.h>
#include <gudhi/Witness_complex.h>
#include <gudhi/Persistent_cohomology.h>
#include <iostream>
#include <fstream>
#include <utility>
#include <string>
#include <vector>
int main(int argc, char * const argv[]) {
using Nearest_landmark_range = std::vector<std::pair<std::size_t, double>>;
using Nearest_landmark_table = std::vector<Nearest_landmark_range>;