WWW.DIS.XLIBX.INFO
FREE ELECTRONIC LIBRARY - Thesis, dissertations, books
 
<< HOME
CONTACTS



«Bei Wang School of Computing Scientific Computing and Imaging Institute (SCI) University of Utah May 18, 2016 Joint work with Liz Munch (University ...»

Category Representations and Convergence

Reeb Space and Mapper

Bei Wang

School of Computing

Scientific Computing and Imaging Institute (SCI)

University of Utah

May 18, 2016

Joint work with Liz Munch (University at Albany - SUNY)

Motivation

Multivariate data and atmospheric science

Multivariate: data points with vector values

Domain applications: weather ensembles from atmospheric science

with large societal impacts, windstorms, smoke transport from

wildfires, winter season precipitation, and hurricane forecasting Explore multivariate topological data analysis tools Multivariate analysis and vis: Jacobi sets, Reeb spaces and mapper Study relations among level sets and critical pts of multiple functions [Bhatia, Wang, Norgard, Pascucci, Bremer (CGTA) 2015] [Munch, Wang (FWCG) 2015] [Munch, Wang (SoCG) 2016] Reeb space Generalization of Reeb graph Compresses the contours of a multivariate mapping and obtains a summary representation of their relationships Fundamental to the study of multivariate scientific data Multivariate analysis within in an end-to-end view Multivariate analysis within in an end-to-end view High-Level Question Original Reeb graph construction Original Reeb graph construction Mapper Image: Nicolau Levine Carlsson 2011 Mapper Image: Nicolau, Levine, Carlsson, PNAS 2011 Joint Contour Net Image: Duke, Carr, 2013 Intuition Mapper is an approximation of the Reeb space.

Intuition Mapper is an approximation of the Reeb space.

Question How do we formalize this?

Intuition Mapper is an approximation of the Reeb space.

Question How do we formalize this?

Goal Develop some theoretical understanding of the relationship between the Reeb space and its discrete approximations to support its use in practical data analysis.

Intuition Mapper is an approximation of the Reeb space.

Question How do we formalize this?

Goal Develop some theoretical understanding of the relationship between the Reeb space and its discrete approximations to support its use in practical data analysis.

Result Prove the convergence between the Reeb space and mapper in terms of an interleaving distance between their categorical representations (Partially) address some open questions [Carri´re, Oudot, 2016]: is it possible to describe the mapper as a e particular constructible cosheaf? Yes, d = 1; hopefully d 1.

[Dey, M´moli, and Wang]: does the mapper construction converges e to the Reeb space in the limit? Yes, in the categorical representations; hopefully geometrically on the space level.

Sheaves make baby cry.

During a talk given by: Amit Patel Baby: Stanley Michael Phillips Quote contributed to (possibly): Dmitriy Morozov SIAM Conference on Applied Algebraic Geometry, August 2, 2013 Category Theory Basics Category and opposite category Data of a category: the objects and the arrows A “generalization” of set theory: set and relationships between elements of a set Arrows: morphisms between the objects Arrows can be composed associatively; identity arrow for each object Intuitively, a big (probably infinite) directed multi-graph with extra underlying structures: objects – nodes, each possible arrow between the nodes – directed edge Examples of categories Top: the category of topological spaces with continuous functions between them Set: the category of sets with set maps Open(Rd ): the category of open sets in Rd with inclusion maps Vect: the category of vector spaces with linear maps R: the category of real numbers with inequalities connecting them Cell(K): the category induced by any simplicial complex K, where the objects are the simplices of K, and there is a arrow σ → τ if σ is a face of τ Poset category A category P in which any pair of elements x, y ∈ P has at most one arrow x → y.

Open(Rd ): exactly one arrow I → J between open sets if I ⊆ J R: exactly one arrow a → b between real numbers if a ≤ b Intuitively, a poset category can be thought of as a directed graph which is not a multigraph Opposite category The opposite category C op of a given category C is formed by interchanging the source and target of each arrow Functor A functor is a map between categories that maps objects to objects and arrows to arrows Functor F : C → D maps an object x in C to an object F (x) in D, and maps an arrow f : x → y of C to an arrow F [f ] : F (x) → F (y) of D in a way that respects the identity and composition laws Intuitively, a functor is a map between graphs which sends nodes (objects) to nodes and edges (arrows) to edges in a way that is compatible with the structure of the graphs Examples of functors Hp : Top → Vect, sends a topological space X to its p-th singular homology group Hp (X), and sends any continuous map f : X → Y to the linear map between homology groups, Hp [f ] := f∗ : Hp (X) → Hp (Y) π0 : Top → Set, sends a topological space X to a set π0 (X) where each element represents a path connected component of X, and sends a map f : X → Y to a set map π0 [f ] := f∗ : π0 (X) → π0 (Y) Natural Transformation A natural transformation ϕ : F ⇒ G between functors F, G : C → D is a family of arrows ϕ in D such that (a) for each object x of C, we have ϕx : F (x) → G(x), an arrow of D; and (b) for any arrow f : x → y in C, G[f ] ◦ ϕx = ϕy ◦ F [f ] Any collection of functors F : C → D can be turned into a category, with the functors themselves as objects and the natural transformations as arrows, notated as DC Our case: D = Set Colimit The cocone (N, ψ) of a functor F : C → D is an object N of D along with a family of ψ of arrows ψx : F (x) → N for every object x of C, such that for every arrow f : x → y in C, we have ψy ◦ F [f ] = ϕx A cocone (N, ψ) factors through another cocone (L, ϕ) if there exists an arrow u : L → N such that u ◦ ϕx = ψx for every x in C The colimit of F : C → D, denoted as colim F, is a cocone (L, ϕ) of F such that for any other cocone (N, ψ) of F, there exists a unique arrow u : L → N such that (N, ψ) factors through (L, ϕ).





Topological Notions Reeb space

–  –  –

The Point The Reeb space of a (nice enough) Image: [de Silva, Munch, Patel, 2015] (X, f ) is a stratified space.

[Edelsbrunner, Harer, Patel 2008] A Reeb space comes with a space and a function Data Data (X, f ) A compact topological space X with a function f : X → Rd

–  –  –

Mapper M (U, f ) Given f : X → Rd Fix a good cover U = {Uα } of Rd f ∗ (U): the cover of X obtained by considering the path connected components of {f −1 (Uα )} Mapper is the nerve of this cover M (U, f ) := Nrv(f ∗ (U)) [Singh, M´moli, Carlsson 2007] e A Road Map Connecting categorical representations Measures the amount the above diagram deviates from being commutative.

Results Overview Convergence result Theorem Given a multivariate function f : X → Rd defined on a compact topological space, the data is represented as an object (X, f ) in Rd -Top. Let U = {Uα }α∈A be a good cover of f (X) ⊆ Rd, K be the nerve of the cover and res(U) be the resolution of the cover, res(U) = sup{diam(Uα ) | Uα ∈ U}. Then

–  –  –

Convergence between continuous Reeb Space and discrete Mapper Distance between their categorical reps. requires only the knowledge of the cover Interleaving distance is an extended pseudometric.

Geometric convergence (d = 1) Corollary Given a constructible R-space (X, f ) with f : X → R, let U = {Uα }α∈A be a good cover of f (X) ⊆ R, and let K be the nerve of the cover. Then

–  –  –

In particular, a sequence of mappers for increasingly refined covers converges to the Reeb graph.

Interleaving distance is an extended metric when d = 1 [de Silva, Munch, Patel, 2015].

d = 1: convergence geometrically (i.e. on the space level).

Categorical Notions Data Data is stored in the category Rd -Top Object: Rd -space, a pair consisting of a topological space X with a continuous map f : X → Rd, (X, f ) Arrow: ν : (X, f ) → (Y, g), a function-preserving map, i.e., a continuous map on the underlying spaces ν : X → Y such that g ◦ ν(x) = f (x) for all x ∈ X Examples: PL functions on simplicial complexes or Morse functions on manifolds are objects in Rd -Top Function preserving maps

–  –  –

Interleaving Distance Perturb each Reeb graph/Reeb space by ε (Smoothing) Determine if there is an almost isomorphism (ε-interleaving) Interleaving between categorical Reeb spaces Definition (Interleaving distance between Categorical Reeb spaces) An ε-interleaving between functors F, G : Open(Rd ) → Set is a pair of natural transformations, ϕ : F ⇒ Sε (G) and ψ : G ⇒ Sε (F) such that the diagrams below commute.

Interleaving between categorical Reeb spaces Definition Given two functors F, G : Open(Rd ) → Set, the interleaving distance is defined to be dI (F, G) = inf{ε ∈ R≥0 | F, G are ε-interleaved} Interleaving between categorical Reeb spaces Definition Given two functors F, G : Open(Rd ) → Set, the interleaving distance is defined to be

–  –  –

Idea The interleaving is a metric on Reeb spaces which takes into account both the space and the function Categorical Mapper: data over nerve of cover

–  –  –

Mapper doesn’t have an obvious Rd function.

Mapper and Reeb are not represented in the same category.

Compare Reeb space and mapper

–  –  –

PK (F )(I) = colimσ∈KI F (σ) for every I in Open(Rd ) Colimit: “gluing”, push discrete entities to continuous entities Lemma Let F : Open(Rd ) → Set be a functor which maps an open set I, to a set π0 f −1 ( σ∈KI Uσ ) with morphisms induced by π0 on the inclusions. Then, the functor PK CK (X, f ) is equivalent to F.

Convergence result revisited Theorem Given a multivariate function f : X → Rd defined on a compact topological space, the data is represented as an object (X, f ) in Rd -Top. Let U = {Uα }α∈A be a good cover of f (X) ⊆ Rd, K be the nerve of the cover and res(U) be the resolution of the cover, res(U) = sup{diam(Uα ) | Uα ∈ U}. Then

–  –  –

If we have a sequence of covers Ui such that res(Ui ) → 0, then the categorical representations of the mapper converge to the Reeb space in the interleaving distance Connecting categorical rep. with geometric rep. (d = 1) Define a mapping that recovers the geometric rep. of mapper from its categorical rep.

Convergence between mapper and Reeb graph geometrically (on the space level).

Highlight Constructing the (geometric) Reeb graph from well behaved data is the same as creating its categorical representation, and then turning it back into a geometric object.

Well behaved data Requiring the data to be constructible R-spaces [de Silva, Munch, Patel, 2015], [Patel, Curry, 2016] R-Topc : full subcategory of R-Top, objects are constructible R-spaces Reeb: full subcategory of R-Topc, category of (geometric) Reeb graphs The construction of a (geometric) Reeb graph from well behaved data (a constructible R-space) is captured by the functor R : R-Topc → Reeb.

Well behaved data Further restrict our objects of interest in SetOpen(R) to be well behaved A cosheaf is a functor F : Open(R) → Set such that for any open cover U of a set U, the unique map colimUα ∈U F (Uα ) → F (U ) is an isomorphism.

A cosheaf is constructible if there is a finite set S ⊂ R such that if A, B ∈ Open(R) with A ⊆ B and S ∩ A = S ∩ B, then F (A) → F (B) is an isomorphism. In addition, we require that if A ∩ S = ∅ then F (A) = ∅.

The category of constructible cosheaves with natural transformations is denoted Cshc.

Equivalence of categories [de Silva, Munch, Patel, 2015] Reeb ≡ Cshc C has an “inverse” functor D : Cshc → Reeb which can turn a constructible cosheaf back into a geometric object Commutativity of the upper right triangle: R = DC Our geometric result

–  –  –

Corollary Given a constructible R-space (X, f ) with f : X → R, let U = {Uα }α∈A be a good cover of f (X) ⊆ R, and let K be the nerve of the cover. Then

–  –  –

Glue a collection of disjoint edges along equivalent vertices defined by the cover Summary [Carri´re, Oudot, 2016]: is it possible to describe the mapper as a e particular constructible cosheaf? Yes, d = 1 with our geometric results: we described the mapper as a constructible cosheaf when it is passed to the continuous version.

Suspect that our geometric results may hold in the case d 1.

Require proper notion of constructibility for Rd -spaces and cosheaves:

want an equivalence of categories, and a proof that the interleaving distance is an extended metric, not just a pseudometric; and therefore the mapper converges to the Reeb space on the space level.

Algorithm strategy for building the associated geometric mapper may be generalized by considering k-dimensional cover elements and their intersections.

First steps towards providing a theoretical justification for the use of discrete objects (mapper and JCN) as approximations to the Reeb space with guarantees.

On-going/future directions Categorical interpretations of Jacobi sets and their distances Categorical interpretations of multiscale mapper Geometric graphs Take home message Category theory provides a simple, beautiful language that could potentially give us cleaner interpretation of some commonly used TDA constructs Simple language for convergence proofs that connect discrete with continuous entities (hard to prove otherwise) New interpretations for studying topological structures, and for multivariate data analysis Thank you!

Liz Munch Vin de Silva, Justin Curry, Amit Patel, Robert Ghrist...

All the TDA researchers who make category theory less scary arXiv:1512.04108, SoCG 2016 NSF-IIS-1513616





Similar works:

«SYG 2000 – Introductory Sociology Evidence of Learning Critical Thinking Thread: Critical Thinking 1 Post: Critical Thinking 1 Author: Anonymous Posted Date: June 21, 2011 11:38 AM Status: Published How well do we think? You might have questioned why I required each of you to purchase a copy of The miniature guide to critical thinking: Concepts and tools by Paul and Elder along with the required textbook for this class. I am personally convinced that the single most important thing we should...»

«Use of Salt and Sodium Metabisulfite Dips Prior to Sun-Drying Tomatoes Guadalupe Latapi and Diane M. Barrett Department of Food Science and Technology University of California, Davis 1 Shields Avenue Davis, CA 95616-8589 Keywords: sulfur dioxide, sodium metabisulfite, salt, tomatoes, sun-drying Abstract Two pre-drying treatments, i.e. 1) salt and 2) sodium metabisulfite dips were evaluated on sun-dried tomatoes by assessing moisture content, color, rehydration ratio, mold and yeast count,...»

«1666 K Street, N.W. Washington, DC 20006 Telephone: (202) 207-9100 Facsimile: (202) 862-8433 www.pcaobus.org Inspection of Albert Wong & Co. (Headquartered in Hong Kong Special Administrative Region, People's Republic of China) Issued by the Public Company Accounting Oversight Board March 31, 2010 THIS IS A PUBLIC VERSION OF A PCAOB INSPECTION REPORT PORTIONS OF THE COMPLETE REPORT ARE OMITTED FROM THIS DOCUMENT IN ORDER TO COMPLY WITH SECTIONS 104(g)(2) AND 105(b)(5)(A) OF THE SARBANES-OXLEY...»

«Capabilities-Based Engineering Analysis (CBEA) © The MITRE Corporation. All rights reserved. Mike Webb The MITRE Corporation mwebb@mitre.org Abstract This paper describes capabilities-based engineering analysis (CBEA) as a new analytical approach to support enterprise systems engineering (ESE). CBEA provides a framework for capabilities-based planning, programming, and acquisition analysis in a systemic approach to the purposeful evolution of a complex enterprise. This paper outlines the basic...»

«June 6, 2012 VITA David G. John I. PERSONAL Citizenship: Canadian Home address: 361 Coleridge Place Waterloo, Ontario N2L 2V7 Present Employment: Professor of German Department of Germanic and Slavic Studies University of Waterloo Waterloo, Ontario N2L 3G1 Telephone: (519) 888-4567, Ext. 33684 Fax: (519) 746-5243 E-mail: djohn@ uwaterloo.ca Websites: http://germanicandslavic.uwaterloo.ca/ http://www.arts.uwaterloo.ca/~djohn/ II. EDUCATION 1970 1975 Ph.D. (German) University of Toronto...»

«MEDIA HIGHLIGHTS AND METRICS UPDATED JUNE 17, 2014 Report Release: April 30, 2014 METRICS As of June 17, the report has been downloaded 4,347 times, making it the second most downloaded National Academy of Sciences report in the last 60 days. The press release has been viewed 2,850 times since April 30, 2014.Visitors – 4/30/2014 to 6/17/2014: Page| 1 Visitors to the report came from several top sources: Total 2,850 Press Release 923 Google 380 Feedburner (RSS Feeds) 319 Nationalacademies.org...»

«NOAA CORPS DIRECTIVES CHAPTER 06 Chapter 06 Leave and Liberty CONTENT Leave Liberty Proceed Time Sick Leave Administrative Absence and Permissive Travel Telework.. Part 6 NOAA CORPS DIRECTIVES CHAPTER 06 PART 1 – LEAVE Section Policy Definitions Authority to Grant Leave Leave Schedules Leave in Conjunction with Temporary Duty Terminal Leave Absence Over Leave Leave Forfeited (Unearned) Lump-Sum Leave Payment Applications for Leave Computation of Leave Used Adoption Leave Paternity Leave Part...»

«Databorough Complexity Metrics and Difference Analysis for better Application Management Steve Kilner WHITE PAPER Table of Contents Executive Summary Concepts The Science Behind Software Maintenance Why Audit and Metric Capabilities are Critical for Managing Legacy Applications Overview Aspects of Quality in Software Maintenance Translating Quality Into Measurable Items How Measurable Items Become Actionable Uses of Historical and Time Series Information Version Comparison Testability Use Cases...»

«For Use by PPMM Staff Date Application Received Contacted_ Interview Date Forwarded to Date_ Placed Y N Date_ VOLUNTEER/INTERN APPLICATION Thank you for your interest in volunteering with PPMM. To facilitate placement, please complete all sections of this application and be sure to type or print clearly. After we receive your application we will contact you to discuss the next steps. Date Name (First) (Middle) (Last) Street Address City State Zip Code _ Phone with area code (day)...»

«How to Overcome your Difficulties By K. Sri Dhammananda Worry and fear Are you worried? Are you miserable? If so, you are invited to read this booklet. The theme of this booklet is dedicated to you and to those who worry themselves unduly – even unto death! Worries and miseries are twin evils that go hand in hand. They co-exist in this world. If you feel worried, you are miserable! If you are miserable, you are worried. We must face facts. Although we cannot run away from them, we must not...»

«20120111-3004 FERC PDF (Unofficial) 01/11/2012 138 FERC 61,018 UNITED STATES OF AMERICA FEDERAL ENERGY REGULATORY COMMISSION Before Commissioners: Jon Wellinghoff, Chairman; Philip D. Moeller, John R. Norris, and Cheryl A. LaFleur. In re Joseph Polidoro Docket No. IN09-6-001 ORDER APPROVING STIPULATION AND CONSENT AGREEMENT (Issued January 11, 2012) 1. The Commission approves the attached Stipulation and Consent Agreement (Agreement) between the Office of Enforcement (Enforcement) and Joseph...»

«Basel Committee on Banking Supervision Results of the comprehensive quantitative impact study December 2010 Copies of publications are available from: Bank for International Settlements Communications CH-4002 Basel, Switzerland E-mail: publications@bis.org Fax: +41 61 280 9100 and +41 61 280 8100 © Bank for International Settlements 2010. All rights reserved. Brief excerpts may be reproduced or translated provided the source is stated. ISBN print: 92-9131-861-2 ISBN web: 92-9197-861-2 Contents...»





 
<<  HOME   |    CONTACTS
2016 www.dis.xlibx.info - Thesis, dissertations, books

Materials of this site are available for review, all rights belong to their respective owners.
If you do not agree with the fact that your material is placed on this site, please, email us, we will within 1-2 business days delete him.