Interleaved Filtrations: Theory and Applications in Point cloud Data Analysis

28/08/2013
OAI : oai:www.see.asso.fr:2552:4856
DOI :

Résumé

Interleaved Filtrations: Theory and Applications in Point cloud Data Analysis

Métriques

967
201
4.63 Mo
 application/pdf
bitcache://6479498bd9777a04abc637692f3cc7ed4da1d9d7

Licence

Creative Commons Aucune (Tous droits réservés)

Sponsors

Sponsors scientifique

logo_smf_cmjn.gif

Sponsors financier

logo_gdr-mia.png
logo_inria.png
image010.png
logothales.jpg

Sponsors logistique

logo-minesparistech.jpg
logo-universite-paris-sud.jpg
logo_supelec.png
Séminaire Léon Brillouin Logo
logo_cnrs_2.jpg
logo_ircam.png
logo_imb.png
<resource  xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
                xmlns="http://datacite.org/schema/kernel-4"
                xsi:schemaLocation="http://datacite.org/schema/kernel-4 http://schema.datacite.org/meta/kernel-4/metadata.xsd">
        <identifier identifierType="DOI">10.23723/2552/4856</identifier><creators><creator><creatorName>Frédéric Chazal</creatorName></creator><creator><creatorName>Steve Oudot</creatorName></creator></creators><titles>
            <title>Interleaved Filtrations: Theory and Applications in Point cloud Data Analysis</title></titles>
        <publisher>SEE</publisher>
        <publicationYear>2013</publicationYear>
        <resourceType resourceTypeGeneral="Text">Text</resourceType><dates>
	    <date dateType="Created">Mon 16 Sep 2013</date>
	    <date dateType="Updated">Mon 25 Jul 2016</date>
            <date dateType="Submitted">Fri 17 Aug 2018</date>
	</dates>
        <alternateIdentifiers>
	    <alternateIdentifier alternateIdentifierType="bitstream">6479498bd9777a04abc637692f3cc7ed4da1d9d7</alternateIdentifier>
	</alternateIdentifiers>
        <formats>
	    <format>application/pdf</format>
	</formats>
	<version>9620</version>
        <descriptions>
            <description descriptionType="Abstract"></description>
        </descriptions>
    </resource>
.

Interleaved Filtrations: Theory and Applications in Point cloud Data Analysis Paris - August, 30 2013 GSI 2013 Fr´ed´eric Chazal and Steve Oudot Introduction • Data often come as (sampling of) metric spaces with possibly complex topolog- ical/geometric structure. • Topological Data Analysis (TDA): infer relevant topological and geometric features of these spaces. • Goals: → Better understanding of the phenomena from which data have been observed. → Taking advantage of the structure of data for more efficient analysis (dimen- sionality reduction, parametrization,...). → clustering, comparison, classification, visualization, learning,... Introduction • Data often come as (sampling of) metric spaces with possibly complex topolog- ical/geometric structure. • Topological Data Analysis (TDA): infer relevant topological and geometric features of these spaces. • Challenges: → no direct access to topological/geometric information from data: need of intermediate constructions (e.g. simplicial complexes); → distinguish topological “signal” from noise: robustness, stability results; → topological information may be multiscale; Curve or torus? Topological signatures for data ∞ 0 0 1-dimensional homology generators 0-dimensional homology generators Metric data set Filtrations / Filtered simplicial complex Signature: persistence diagram Build a geometric fil- tered simplicial com- plex on top of the data Compute persistent homology of the complex. Approach: • Build a filtration / filtered simplicial complex on top of (X, dX ) (dX being a metric/similarity on X). Topological signatures for data ∞ 0 0 1-dimensional homology generators 0-dimensional homology generators Metric data set Filtrations / Filtered simplicial complex Signature: persistence diagram Build a geometric fil- tered simplicial com- plex on top of the data Compute persistent homology of the complex. Approach: • Build a filtration / filtered simplicial complex on top of (X, dX ) (dX being a metric/similarity on X). • Compute the persistent homology of the filtration → persistence diagram: mul- tiscale topological signature. Topological signatures for data ∞ 0 0 1-dimensional homology generators 0-dimensional homology generators Metric data set Filtrations / Filtered simplicial complex Signature: persistence diagram Build a geometric fil- tered simplicial com- plex on top of the data Compute persistent homology of the complex. Approach: • Build a filtration / filtered simplicial complex on top of (X, dX ) (dX being a metric/similarity on X). • Compute the persistent homology of the filtration → persistence diagram: mul- tiscale topological signature. • Compare the signatures of “close” data sets → robustness and stability results. Filtered complexes and filtrations A filtered simplicial complex S built on top of a set X is a family (Sa | a ∈ R) of subcomplexes of some fixed simplicial complex S with vertex set X s. t. Sa ⊆ Sb for any a ≤ b. A filtration F of a space X is a nested family (Fa | a ∈ R) of subspaces of X such that Fa ⊆ Fb for any a ≤ b. Example: If f : X → R is a function, then the sublevelsets of f, Fa = f−1 ((−∞, a]) define the sublevel set filtration associated to f. Filtered complexes and filtrations Examples: Let (X, dX ) be a metric space. • The Vietoris-Rips and ˇCech complexes Rips(X) and ˇCech(X) are the filtered complexes defined by: for a ∈ R, [x0, x1, · · · , xk] ∈ Rips(X, a) ⇔ dX (xi, xj) ≤ a, for all i, j [x0, x1, . . . , xk] ∈ ˇCech(X, a) ⇔ k i=0 B(xi, a) = ∅, where B(x, a) = {x ∈ X : dX (x, x ) ≤ a}. Rips ˇCech Persistent homology of filtered complexes • An efficient way to encode the evolution of the topology (homology) of a filtered complex. • Multiscale topological information. • Barcodes/persistence diagrams can be effi- ciently computed. • Stability properties Persistent homology of filtered complexes • An efficient way to encode the evolution of the topology (homology) of a filtered complex. • Multiscale topological information. • Barcodes/persistence diagrams can be effi- ciently computed. • Stability properties Persistent homology of filtered complexes • An efficient way to encode the evolution of the topology (homology) of a filtered complex. • Multiscale topological information. • Barcodes/persistence diagrams can be effi- ciently computed. • Stability properties Persistent homology of filtered complexes • An efficient way to encode the evolution of the topology (homology) of a filtered complex. • Multiscale topological information. • Barcodes/persistence diagrams can be effi- ciently computed. • Stability properties Persistent homology of filtered complexes • An efficient way to encode the evolution of the topology (homology) of a filtered complex. • Multiscale topological information. • Barcodes/persistence diagrams can be effi- ciently computed. • Stability properties Persistent homology of filtered complexes • An efficient way to encode the evolution of the topology (homology) of a filtered complex. • Multiscale topological information. • Barcodes/persistence diagrams can be effi- ciently computed. • Stability properties Persistent homology of filtered complexes • An efficient way to encode the evolution of the topology (homology) of a filtered complex. • Multiscale topological information. • Barcodes/persistence diagrams can be effi- ciently computed. • Stability properties birth death ∞ 0 Multiplicity: 2 Persistence diagram Add the diagonal Persistence bar code The bottleneck distance between two diagrams D1 and D2 is dB(D1, D2) = inf γ∈Γ sup p∈D1 p − γ(p) ∞ where Γ is the set of all the bijections between D1 and D2 and p − q ∞ = max(|xp − xq|, |yp − yq|). Distance between persistence diagrams birth death ∞ 0 Multiplicity: 2 Add the diagonal D1 D2 → Persistence diagrams provide easy to compare topological signatures. Tame persistent modules Definition: A persistence module V is an indexed family of vector spaces (Va | a ∈ R) and a doubly-indexed family of linear maps (vb a : Va → Vb | a ≤ b) which satisfy the composition law vc b ◦ vb a = vc a whenever a ≤ b ≤ c, and where va a is the identity map on Va. Examples: • Let S be a filtered simplicial complex, i.e. a family (Sa | a ∈ R) of sub- complexes of some fixed simplicial complex S, s. t. Sa ⊆ Sb for any a ≤ b. If Va = H(Sa) and vb a : H(Sa) → H(Sb) is the linear map induced by the inclusion Sa → Sb then (H(Sa) | a ∈ R) is a persistence module. • Given a metric space (X, dX ) , H(Rips(X)) is a persistence module. • Given a metric space (X, dX ) , H(ˇCech(X)) is a persistence module. • If f : X → R is a function, then (H(f−1 ((−∞, a])) | a ∈ R) is a persistence module. Tame persistent modules Definition: A persistence module V is an indexed family of vector spaces (Va | a ∈ R) and a doubly-indexed family of linear maps (vb a : Va → Vb | a ≤ b) which satisfy the composition law vc b ◦ vb a = vc a whenever a ≤ b ≤ c, and where va a is the identity map on Va. Definition: A persistence module V is q-tame if for any a < b, vb a has a finite rank. Theorem [CCGGO’09-CdSGO’12]: q-tame persistence modules have well-defined persistence diagrams. Tame persistent modules Definition: A persistence module V is an indexed family of vector spaces (Va | a ∈ R) and a doubly-indexed family of linear maps (vb a : Va → Vb | a ≤ b) which satisfy the composition law vc b ◦ vb a = vc a whenever a ≤ b ≤ c, and where va a is the identity map on Va. Definition: A persistence module V is q-tame if for any a < b, vb a has a finite rank. Theorem [CCGGO’09-CdSGO’12]: q-tame persistence modules have well-defined persistence diagrams. Recall that a metric space (X, dX ) is precompact if for any > 0 there exists a finite subset F ⊂ X such that dH (X, F ) < (i.e. ∀x ∈ X, ∃p ∈ F s.t. dX (x, p) < ). Examples: - Let X be a precompact metric space. Then H(Rips(X)) and H(ˇCech(X)) are q-tame [CdSO’12]. - If f : X → R si continuous and X is homeomorphic to a finite simplicial complex, then (H(f−1 ((−∞, a])) | a ∈ R) is q-tame. Tame persistent modules Definition: A persistence module V is an indexed family of vector spaces (Va | a ∈ R) and a doubly-indexed family of linear maps (vb a : Va → Vb | a ≤ b) which satisfy the composition law vc b ◦ vb a = vc a whenever a ≤ b ≤ c, and where va a is the identity map on Va. A homomorphism of degree between two persis- tence modules U and V is a collection Φ of linear maps (φa : Ua → Va+ | a ∈ R) such that vb+ a+ ◦ φa = φb ◦ ub a for all a ≤ b. Ua Ub V a+ V b+ An ε-interleaving between U and V is specified by two homomorphisms of degree Φ : U → V and Ψ : V → U s.t. Φ ◦ Ψ and Ψ ◦ Φ are the “shifts” of degree 2 between U and V. Ua V a+ Ua+2 V a+3 · · · · · · φa ψa+ ua+2 a va+3 a+ · · · · · · Tame persistent modules Definition: A persistence module V is an indexed family of vector spaces (Va | a ∈ R) and a doubly-indexed family of linear maps (vb a : Va → Vb | a ≤ b) which satisfy the composition law vc b ◦ vb a = vc a whenever a ≤ b ≤ c, and where va a is the identity map on Va. Stability Theorem [CCGGO’09-CdSGO’12]: If U and V are q-tame and -interleaved for some ≥ 0 then dB(dgm(U), dgm(V)) ≤ Tame persistent modules Definition: A persistence module V is an indexed family of vector spaces (Va | a ∈ R) and a doubly-indexed family of linear maps (vb a : Va → Vb | a ≤ b) which satisfy the composition law vc b ◦ vb a = vc a whenever a ≤ b ≤ c, and where va a is the identity map on Va. Stability Theorem [CCGGO’09-CdSGO’12]: If U and V are q-tame and -interleaved for some ≥ 0 then dB(dgm(U), dgm(V)) ≤ Strategy: build q-tame homology persistence modules from input data/space that turn out to be -interleaved when the considered data/spaces are O( )-close. The example of the Rips and ˇCech filtration The Gromov-Hausdorff distance. Let (X, dX ) and (Y, dY ) be compact metric spaces. A subset C ⊆ X × Y is an -correspondence if - ∀x ∈ X, ∃y ∈ Y s.t. (x, y) ∈ C, - ∀y ∈ Y , ∃x ∈ X s.t. (x, y) ∈ C, - ∀(x, y), (x , y ) ∈ C, |dX (x, x ) − dY (y, y )| ≤ ε. dGH (X, Y ) = 1 2 inf{ε ≥ 0 : there exists an ε-correspondence between Xand Y } Y X C x x y y The example of the Rips and ˇCech filtration The Gromov-Hausdorff distance. Let (X, dX ) and (Y, dY ) be compact metric spaces. A subset C ⊆ X × Y is an -correspondence if - ∀x ∈ X, ∃y ∈ Y s.t. (x, y) ∈ C, - ∀y ∈ Y , ∃x ∈ X s.t. (x, y) ∈ C, - ∀(x, y), (x , y ) ∈ C, |dX (x, x ) − dY (y, y )| ≤ ε. dGH (X, Y ) = 1 2 inf{ε ≥ 0 : there exists an ε-correspondence between Xand Y } Y X C x x y y Proposition: Let (X, dX ), (Y, dY ) be metric spaces. For any > 2dGH(X, Y ) the persistence modules H(Rips(X)) and H(Rips(Y )) are -interleaved (same result for H(ˇCech(.))). Theorem [CdSO 2012]: Let X, Y be precompact metric spaces. Then db(dgm(H(ˇCech(X))), dgm(H(ˇCech(Y )))) ≤ 2dGH(X, Y ), db(dgm(H(Rips(X))), dgm(H(Rips(Y )))) ≤ 2dGH(X, Y ). The example of the Rips and ˇCech filtration Application: topological signatures for shapes - Use persistence diagrams of Rips filtrations built on top of sampled shapes as a discriminative tool to compare them (persistence is much easier to compute than GH-distance). - Minimax rates of convergences of persistence diagrams for randomly sampled (mea- sured) metric spaces. camel cat elephant face head horse ∞ 0 0 1 ∞ 0 0 1 ∞ 0 0 1 ∞ 0 0 1 Use the metric on the space of per- sistence diagrams.[C., Cohen-Steiner, Guibas, M´emoli, Oudot ’09] The example of scalar field analysis Let X be a Riemannian manifold and f : X → R be c-Lipschitz. Let L ⊂ X be a finite ε-sample: ∀x ∈ X, ∃p ∈ L s.t. d(x, p) < ε. Challenge: Approximate the persistence diagram of f from L and f|L. The example of scalar field analysis Let X be a Riemannian manifold and f : X → R be c-Lipschitz. Let L ⊂ X be a finite ε-sample: ∀x ∈ X, ∃p ∈ L s.t. d(x, p) < ε. For α ∈ R, Lα = {p ∈ L : f(p) ≤ α} X Lα Lβ α < β Persistence module: Vδ = (im (H(Rips(Lα, δ)) → H(Rips(Lα, 2δ))) , α ∈ R) Challenge: Approximate the persistence diagram of f from L and f|L. The example of scalar field analysis Let X be a Riemannian manifold and f : X → R be c-Lipschitz. Let L ⊂ X be a finite ε-sample: ∀x ∈ X, ∃p ∈ L s.t. d(x, p) < ε. For α ∈ R, Lα = {p ∈ L : f(p) ≤ α} X Lα Lβ α < β Persistence module: Vδ = (im (H(Rips(Lα, δ)) → H(Rips(Lα, 2δ))) , α ∈ R) Theorem [CGOS 11]: Let ρ(X) be the convexity radius of X. If 4ε < ρ(X), then for any δ ∈ [2ε, ρ(X)/2], Vδ is q-tame and dB(dgm(f), Vδ) < 2cδ where dgm(f) is the persistence diagram of the sublevel set filtration of f. Challenge: Approximate the persistence diagram of f from L and f|L. The example of scalar field analysis Applications: • Persistence-based Clustering (use persistence to find persistence modes of a density estimate). • Segmentation of non-rigid shapes (use persistence of heat kernel signature to segment shapes). [C.-Guibas,O.-Skraba,2011] [C.-Ovsjanikov-Skraba 2010] Complexity issues Commonly used filtrations (ˇCech, Rips,...) become huge at large scale and/or in high dimensions : 2n , n d 2 ,... Interleaving strategy helps: - Sparse Rips filtration [Sheehy 2012]: a O(n)-size approximation of the Rips filtra- tions that turns out to be interleaved to the Rips filtration. - Zig-zag Rips modules [O.-Sheehy 2013]: a zig-zag module (arrows can go forward and backward) whose persistence approximate the Rips persistence. Take-home message