5 ms·

Sheaf Theory: The Mathematics of Data Fusion (audio starts at 10:44) [video]

85 points by espeed 10y ago

espeed 10y ago
A sheaf is a combinatorial, high-dimensional data structure on a topological space. You can use it to stitch together images, spatio-temporal target tracking, inference, data fusion, IoT time-series, continuous functions -- all kinds of things. Crazy cool stuff! Applied sheaf theory is pretty new, and not yet widely known. This DARPA sheaf tutorial is a full two-day video series by Prof Michael Robinson (great teacher), and it's about the equivalent of a semester CS course compressed into two days. If you want to see an intro/big-picture overview video on what the sheaf data structure is, and how it's related to graph databases, topology, category theory, and data analysis, see: "Sheaves for engineering problems" https://www.youtube.com/watch?v=223-0x2KNOg https://www.youtube.com/watch?v=223-0x2KNOg And for a deep dive into a paper, see: "Sheaves are the canonical data structure for sensor integration" https://arxiv.org/abs/1603.01446 https://arxiv.org/abs/1603.01446 Python Cellular Sheaf Library: https://github.com/kb1dds/pysheaf https://github.com/kb1dds/pysheaf
- defen 10y ago
  That youtube link is great, thanks.
- faizshah 10y ago
  Have you found a book or a review/survey paper on this topic? I just started Computational Homology by Kaczynski et al. but I just looked in the index and didn't find anything on sheaves.
  - espeed 10y ago
    Prof Robinson's book is Topological Signal Processing [1], and there are a ton of papers linked from his home page [2]. For a general overview, check out the wikipedia page: https://en.wikipedia.org/wiki/Sheaf_(mathematics) https://en.wikipedia.org/wiki/Sheaf_(mathematics) [1] https://www.amazon.com/Topological-Signal-Processing-Mathematical-Engineering/dp/364236103X https://www.amazon.com/Topological-Signal-Processing-Mathema... [2] http://www.drmichaelrobinson.net/publications.html http://www.drmichaelrobinson.net/publications.html
  - sn9 10y ago
    Robert Ghrist offers his Elementary Applied Topology for free on his site. It's useful more as a supplement or survey than a primary text to learn. https://www.math.upenn.edu/~ghrist/notes.html https://www.math.upenn.edu/~ghrist/notes.html
  - diamonis 10y ago
    http://www.cis.upenn.edu/~jean/gbooks/sheaf-coho.html http://www.cis.upenn.edu/~jean/gbooks/sheaf-coho.html
- fmap 10y ago
  Sheaf models are one of the most useful tools in logic and I'll definitely read this paper once I have more time again. One thing that seems strange to me based on the overview video is the focus on sheafs on a topological space. In mathematics it's typically easier and more flexible to consider sheafs on categories equipped with a Grothendieck coverage. Is there a reason why topological spaces are sufficient to model sensor integration?
  - auggierose 10y ago
    Maybe because topological spaces are more familiar to many mathematicians than categories?
- hackernewsacct 10y ago
  What kind of math background do you need to understand Sheaf theory? Are these lectures truly accessible for someone with a non-background? I tried watching bits of the youtube video OP linked but never saw where he actually defined what a Sheaf was as oppose to building motivation of learning it for applications. I am excited for any truly accessibly beginner resources. Want to get your opinion if you links are for the true beginner?
mrkgnao 10y ago
So, I can probably try to provide the beginnings of an ELI5 from a math point of view, since the heading really caught my eye: a sheaf is a way of assigning some data to subsets of a space which satisfied some commonsense axioms. For instance, suppose you have a sheaf F that assigns to every open interval I on the real line the set[1] F(I) of real-valued functions defined on it. If I write F(a,b) for F((a,b)): * f(x) = x is in all the F(a,b), since it's defined everywhere on the real line * f(x) = 1/(x-3) isn't in F(2.9, 3.1) or even F(1,5), but it is in F(4,5) And so on. There's an axiom that says that if you have * f in F(I) * g in F(J) such that f = g everywhere on the intersection of I and J, then there is in fact some function h defined all over I ∪ J (i.e. h ∈ F(I ∪ J)) which you can restrict to I and J to get f and g respectively. So "compatible functions can be stitched together", where "compatible" means "agree on overlaps". Sheaves give you a language to coherently[0] talk about "partially-defined" functions such as 1/(x-3) above, to stitch them together, and go from the "local" to the "global" picture and back comfortably. This last point is actually a hallmark of mathematics in the last one or two centuries: for instance, consider some equation which you want to find integer solutions for. If you want to show it has no solutions, you can reduce both sides modulo some number and show that there are no solutions mod n, which means it is impossible to find any solutions to begin with. It is a much more deep fact (the Hasse principle) that if you can find solutions mod all n (and a real one), you can always solve the original equation! (I'm fudging a bit here: see [2] for details.) (Quick plug: I have a short post that talks about these things here[3], as well as another on the "p-adic" numbers that appear in the Hasse principle.) Sheaves are general enough ("data" can mean[4] almost anything!) that Paul Cohen used them to prove the independence of the axiom of choice[5] from the Zermelo-Fränkel axioms (which is hard set theory) even though they were created for geometry, broadly speaking: in particular, they were one of the tools with which Grothendieck and his collaborators powerfully recast algebraic geometry in the 20th century, giving birth to "scheme theory"[6], which is e.g. vital in modern number theory. (I should probably mention the standard example of Wiles' proof of the Taniyama-Shimura conjecture that settled FLT.) Cool stuff. [0]: excuse the pun [1]: ring, really [2]: https://en.m.wikipedia.org/wiki/Hasse_principle https://en.m.wikipedia.org/wiki/Hasse_principle [3]: https://mrkgnao.github.io/schemes-i/ https://mrkgnao.github.io/schemes-i/ [4]: Well, a sheaf can be defined as a certain kind of contravariant functor into a category, which one can think of as the "type" of our data. [5]: https://en.wikipedia.org/wiki/Forcing_(mathematics) https://en.wikipedia.org/wiki/Forcing_(mathematics) [6]: https://en.wikipedia.org/wiki/Scheme_(mathematics) https://en.wikipedia.org/wiki/Scheme_(mathematics)
maus42 10y ago
Fascinating stuff. I've now done maths for some years now and this is the first time I even hear about sheafs. Makes one wonder what else you may have missed just because it's not something profs at your programme are interested in. edit. Follow-up. I wonder if there's a list of curious and possibly useful math stuff you might easily miss because it's not as ubiquitous and 'canonical' as (e.g.) analysis, linear algebra or functional analysis?
- pizza 10y ago
  check out nLab
- RBerenguel 10y ago
  I had sheaf theory at an advanced algebraic geometry course, essentially you need them to define schemes. They are on the "you won't need this unless you go for a PhD" area, usually, although they are not that weird (I found schemes weirder than sheaves for some reason)

85 points by espeed 10y ago

A sheaf is a combinatorial, high-dimensional data structure on a topological space. You can use it to stitch together images, spatio-temporal target tracking, inference, data fusion, IoT time-series, continuous functions -- all kinds of things. Crazy cool stuff! Applied sheaf theory is pretty new, and not yet widely known. This DARPA sheaf tutorial is a full two-day video series by Prof Michael Robinson (great teacher), and it's about the equivalent of a semester CS course compressed into two days. If you want to see an intro/big-picture overview video on what the sheaf data structure is, and how it's related to graph databases, topology, category theory, and data analysis, see: "Sheaves for engineering problems" https://www.youtube.com/watch?v=223-0x2KNOg https://www.youtube.com/watch?v=223-0x2KNOg And for a deep dive into a paper, see: "Sheaves are the canonical data structure for sensor integration" https://arxiv.org/abs/1603.01446 https://arxiv.org/abs/1603.01446 Python Cellular Sheaf Library: https://github.com/kb1dds/pysheaf https://github.com/kb1dds/pysheaf

defen 10y ago
That youtube link is great, thanks.
faizshah 10y ago
Have you found a book or a review/survey paper on this topic? I just started Computational Homology by Kaczynski et al. but I just looked in the index and didn't find anything on sheaves.
- espeed 10y ago
  Prof Robinson's book is Topological Signal Processing [1], and there are a ton of papers linked from his home page [2]. For a general overview, check out the wikipedia page: https://en.wikipedia.org/wiki/Sheaf_(mathematics) https://en.wikipedia.org/wiki/Sheaf_(mathematics) [1] https://www.amazon.com/Topological-Signal-Processing-Mathematical-Engineering/dp/364236103X https://www.amazon.com/Topological-Signal-Processing-Mathema... [2] http://www.drmichaelrobinson.net/publications.html http://www.drmichaelrobinson.net/publications.html
- sn9 10y ago
  Robert Ghrist offers his Elementary Applied Topology for free on his site. It's useful more as a supplement or survey than a primary text to learn. https://www.math.upenn.edu/~ghrist/notes.html https://www.math.upenn.edu/~ghrist/notes.html
- diamonis 10y ago
  http://www.cis.upenn.edu/~jean/gbooks/sheaf-coho.html http://www.cis.upenn.edu/~jean/gbooks/sheaf-coho.html
fmap 10y ago
Sheaf models are one of the most useful tools in logic and I'll definitely read this paper once I have more time again. One thing that seems strange to me based on the overview video is the focus on sheafs on a topological space. In mathematics it's typically easier and more flexible to consider sheafs on categories equipped with a Grothendieck coverage. Is there a reason why topological spaces are sufficient to model sensor integration?
- auggierose 10y ago
  Maybe because topological spaces are more familiar to many mathematicians than categories?
hackernewsacct 10y ago
What kind of math background do you need to understand Sheaf theory? Are these lectures truly accessible for someone with a non-background? I tried watching bits of the youtube video OP linked but never saw where he actually defined what a Sheaf was as oppose to building motivation of learning it for applications. I am excited for any truly accessibly beginner resources. Want to get your opinion if you links are for the true beginner?

mrkgnao 10y ago

So, I can probably try to provide the beginnings of an ELI5 from a math point of view, since the heading really caught my eye: a sheaf is a way of assigning some data to subsets of a space which satisfied some commonsense axioms. For instance, suppose you have a sheaf F that assigns to every open interval I on the real line the set[1] F(I) of real-valued functions defined on it. If I write F(a,b) for F((a,b)): * f(x) = x is in all the F(a,b), since it's defined everywhere on the real line * f(x) = 1/(x-3) isn't in F(2.9, 3.1) or even F(1,5), but it is in F(4,5) And so on. There's an axiom that says that if you have * f in F(I) * g in F(J) such that f = g everywhere on the intersection of I and J, then there is in fact some function h defined all over I ∪ J (i.e. h ∈ F(I ∪ J)) which you can restrict to I and J to get f and g respectively. So "compatible functions can be stitched together", where "compatible" means "agree on overlaps". Sheaves give you a language to coherently[0] talk about "partially-defined" functions such as 1/(x-3) above, to stitch them together, and go from the "local" to the "global" picture and back comfortably. This last point is actually a hallmark of mathematics in the last one or two centuries: for instance, consider some equation which you want to find integer solutions for. If you want to show it has no solutions, you can reduce both sides modulo some number and show that there are no solutions mod n, which means it is impossible to find any solutions to begin with. It is a much more deep fact (the Hasse principle) that if you can find solutions mod all n (and a real one), you can always solve the original equation! (I'm fudging a bit here: see [2] for details.) (Quick plug: I have a short post that talks about these things here[3], as well as another on the "p-adic" numbers that appear in the Hasse principle.) Sheaves are general enough ("data" can mean[4] almost anything!) that Paul Cohen used them to prove the independence of the axiom of choice[5] from the Zermelo-Fränkel axioms (which is hard set theory) even though they were created for geometry, broadly speaking: in particular, they were one of the tools with which Grothendieck and his collaborators powerfully recast algebraic geometry in the 20th century, giving birth to "scheme theory"[6], which is e.g. vital in modern number theory. (I should probably mention the standard example of Wiles' proof of the Taniyama-Shimura conjecture that settled FLT.) Cool stuff. [0]: excuse the pun [1]: ring, really [2]: https://en.m.wikipedia.org/wiki/Hasse_principle https://en.m.wikipedia.org/wiki/Hasse_principle [3]: https://mrkgnao.github.io/schemes-i/ https://mrkgnao.github.io/schemes-i/ [4]: Well, a sheaf can be defined as a certain kind of contravariant functor into a category, which one can think of as the "type" of our data. [5]: https://en.wikipedia.org/wiki/Forcing_(mathematics) https://en.wikipedia.org/wiki/Forcing_(mathematics) [6]: https://en.wikipedia.org/wiki/Scheme_(mathematics) https://en.wikipedia.org/wiki/Scheme_(mathematics)

maus42 10y ago

Fascinating stuff. I've now done maths for some years now and this is the first time I even hear about sheafs. Makes one wonder what else you may have missed just because it's not something profs at your programme are interested in. edit. Follow-up. I wonder if there's a list of curious and possibly useful math stuff you might easily miss because it's not as ubiquitous and 'canonical' as (e.g.) analysis, linear algebra or functional analysis?

pizza 10y ago
check out nLab
RBerenguel 10y ago
I had sheaf theory at an advanced algebraic geometry course, essentially you need them to define schemes. They are on the "you won't need this unless you go for a PhD" area, usually, although they are not that weird (I found schemes weirder than sheaves for some reason)