Skip to main content
Loading Explore guides…
Topology · Acedra
Home
Explore
Mathematics
Topology
Sign in to save
Chat
If YouTube asks you to sign in, open the video on YouTube.
Watch on YouTube
Reload player
Transcript
107 segments
Copy
Hide video
0:03
have people back for the second time it that have been submitted is the grandson of the male building and over the last few years of become involved in the faculty providing scholarships and also providing the funding for the bench McMeel colloquium so we have two lectures a year on average in that means there is and
0:46
various scientists and engineers know it's traditional in lectures of this kind to invite people on at the end but following a long but was very insistent along with this we invited people who brought new ideas and people although so children only of the year older than my other daughter with people who would make you think without something new and that's the reason why we invited right Mattox one form another I won't go into the details because they're not very important just
2:11
to give you an idea how he's different from other mathematicians and I think every mathematician being teachers calculus but here's an interesting statistic is next calculus course which is to be given before already has an enrollment 110 thousand morton's and the expectation is it will go up by a factor of 10 or more there's an unusual lecturer he also has joint appointment in University of Pennsylvania and the reason is that what makes Robert unique is is that he is one
3:11
of two or three people that's not unique I want two or three people the head of who to take well he's probably the most abstract area of mathematics algebraic topology and to bring it into the real world and use it application
3:39
but well thank you very much for coming to this lecture thank you Robert for that wonderful introduction and thanks in particular to Vincent Mayer for helping fund this series I would like to I would like to tell you a little bit about some of the things that I have done and I'm interested in doing let me start off with a more general instruction that I hope is is suitable for this audience so if we if we take a look at pardon me well we set this up perfect all right thank you
5:14
all right if we you know if we think about why things work in the world so well the way they work one of the answers that you might say is is Moore's law things keep getting better because we're able to fit more and more semiconductors onto a chip this means that the computers are faster this means that we can solve more problems more quickly and you might say that the progress of the engineering sciences has has been maybe a large part due to Moore's law but there's something beyond
5:49
that it is true that Moore's Law is amazing and amazingly useful and if you look back at you know where things were when digital computers first came out this is the the ENIAC machine that is still in the first floor of Moore Hall in the University of Pennsylvania right where my office is so if you look at how far we've come since then it's quite a long way but it's not just in semiconductors and in computers where we have progressed and where we have a Moore's law there's a Moore's law for
6:23
the mind as well and the tools that we create in order to solve problems also exponentially increase if we look at the tools that have been useful in the engineering sciences coming from from mathematics if we look at analysis if we look in linear algebra these were once very newfangled tools very unfamiliar tools but applied mathematics did not stop with calculus with linear algebra there is an exponential increase in mathematics seen all yes some of which have crossed over very quickly into
7:00
applied mathematics others others which have yet to be applied now as Robert said in the introduction one of the things that I'm interested in doing is taking a particular branch of pure mathematics namely algebraic topology and dragging it sometimes kicking and screaming across the fence into applications in the engineering sciences let me let me take a couple of minutes and talk about what I mean by topology and then what I mean by its applications so first of all well what is topology
7:33
this isn't the the the usual training that engineers receive other than network topology which is a little bit different well the word itself tells you a little bit about what it means you might say that topology is the mathematics of holes or of finding global features qualitative features inside of objects and and the word itself has a fairly interesting topology in the form of quite a few holes now I have to when I speak to english-speaking audiences I have to be a little bit
8:09
careful because some people who are not familiar with the word topology confuse it with another very similar word in English that being typography that is not what topology is about it has nothing to do with maps at least not this kind of map now the word topology comes from the word tapas which means place so you might say that topology is the study of place here again there's potential for confusion because I said place not plates the study of plates small plates
8:44
full of delicious food that is that is not topology that's a that's tapas that's a Spanish word tapas is something different that's a that's a Greek word and it means place or location where things are at so topology coming from tapas is the study of abstract space is very very qualitative as opposed to quantitative is very very much interested in global phenomena now how is how is this mathematical subject finding uses in the engineering and applied sciences there are there are
9:20
almost too many to survey quickly in a talk but let me mention a couple that are relevance to engineering systems so one of the one of the most interesting applications that several people in this room may find interesting is to to robotics when you have a collection of several robots such as the the Nano quad rotors that we've been playing around with in the grasp lab at the University of Pennsylvania coordinating the motion making sure that they don't collide into each other that
9:55
planning can be thought of as a topological or a geometric problem on an abstract space whose dimension might be quite high depending on how many agents you have in motion likewise if you're looking at working legged robotics for example the the Rex robots that is built off of roughly speaking this structure of cockroach you have to coordinate the motion of the six legs each leg has one degree of freedom that winds up giving you a six dimensional configuration space some states of which are are
10:33
illegal you can't have all the legs off the ground at the same time and expect to still be standing so coordinating motion for this robot winds up being equivalent to coordinating pads inside of an interesting topological space there's a there's been a lot of work recently that's been done in applications of topology of finding global features in in data and in data coming in particular from point clouds namely a scattering of points in some geometric space we have a
11:08
lot of practice as human beings and looking at a collection of points in space and then trying to piece them together to get the the big picture associated with it and that various times in the past we've been very creative in the methods that we've used to understand the global features a collection of points well the topology provides somewhat more formal principle tools for understanding that and one of the people very active in this realm has been Gunnar Carlsen from Steam
11:41
bird who's applied a lot of very deep algebraic topological tools to find global features in statistical data in point cloud data I've done a little bit of work in coverage problems in sensor networks you're all familiar with what happens when you go to a particular place and you lose coverage for your cellphone you're you're in a gap where the towers don't cover how could you get a an ad hoc network of nodes having no idea about its coordinates let's say in
12:15
a GPS denied environment how could you get the network to decide whether or not there are holes in coverage and if so where those holes are located that's a very very interesting global problem to which algebraic topology has been applied that's a little bit of it's a little bit hard to see why that's an interesting problem because you're seeing a picture of all the coordinates but of course the the ad hoc network doesn't know what this picture looks like a mathematically equivalent problem
12:45
that your brain is not so good at doing maybe would be a time-dependent version let's say that you have a collection of sensors that are moving around and they can't cover the entire domain there's always some gaps but you'd like to know is it possible for an invader for a bad guy to escape detection while the sensors are moving around mathematically that's exactly the same problem you're looking for a hole but not in a two dimensional plane where you can easily
13:18
see what's going on but in a three dimensional setting where your brain is is not so good at working that out maybe so well those are some roughly sketched examples what you know what's actually going on what do you actually do when you apply topology to something well hmm this this is going to have to be done very quickly and briefly fortunately you have a lot of mathematicians here who'll be able to fill you in on some of the details roughly speaking two of the
13:57
tools that have been most useful are homology which you might think of as linear algebra and a little more applied to categorizing holes in a space but there's also a dual to this an algebraic mirror image that's called Co homology that sometimes gives you just a little bit extra power in order to solve a problem the canonical example of a problem that can be solved by these means without actually having to do any hard work would be the following problem let's say that you are you're located
14:34
somewhere in the plane and you are surrounded by a fence by a simple closed curve that makes something like a maze and you want to know or you want to know how to get out but that's a little bit too hard let's let's start with a feasibility question you want to know is it possible to get out or are you trapped now I haven't shown you the entire maze and in particular I haven't shown you where the exit is located how are you going to be able to figure out whether or not you can escape well you
15:09
know I'm afraid to say that earlier in my life you know I would have said well you're gonna have to tell me the equation of this curve and then I'm gonna have to analyze the equation and plot it out you don't need that a homological solution would be the following just shoot a beam out to infinity and look at the intersections of that beam with the curve and then count them with they with a particular index with a with a parity plus minus plus minus because when you're way out
15:43
here you're outside the curve when you cross then you're inside then you're outside then you're in than your outside etc and whether or not these values add up to zero or does something nonzero tells you whether or not you're trapped inside or can escape now what's nice about this why why would engineers care about something like this look at what kind of data you need in order to solve this problem you don't need to know what's happening to the fence outside here you only need to know
16:19
what's happening at a finite number of points and you need to count appropriately and then you can solve the feasibility problem it doesn't tell you how to get out but it tells you whether or not you can get out ok so that's a that's a simple example of a homological way of thinking and of course there are a lot more details behind this but I'm not going to tell you about but you know if you're interested you've got a lot of local experts here who would be glad to fill
16:50
you in on some of the some of the background associated with this but let me move on to some more explicit examples of applications of algebraic topology in engineering systems mostly focused on signals signal processing things of that sort some of these examples are going to be sketched out somewhat loosely but as we go on we're going to fill in more and more details until the end where we're going to get very explicit so the first set of examples that I'd like to talk about
17:26
concerns a theorem that was just published recently in the I Triple E journal on signal processing this is with one of my postdocs Michael Robinson this is called a signals embedding theorem let me tell you the setup for it which is somewhat abstract and then we'll bring it down to a more concrete level let's say that you've got some domain D that's no say in a in the plane and a Euclidean space doesn't really matter and I have a collection of transmitters
17:59
that are emitting a signal maybe a pulse something like that and I have a receiver that can intercept those signals that can hear those pulses and it might record something like the the time at which the pulse struck or the the signal strength maybe the direction of arrival maybe if things are in motion it uses Doppler but you have some sort of signals space associated with this system now I'm going to mathematize this transmission reception problem in the following way I'm going to assume that
18:39
my domain D contains a receiver somewhere and that the signals that are received are contained in some sort of signal space normally this is going to be the the reals if you think of a time of arrival then each transmitter is going to give me some time at which I hear the ping now the problem is I may or may not hear it depending on whether or not I'm within the within the range associated to that transmitter so I might have a a fail state associated with this and even more I might have
19:17
some some modulation that occurs for example I might not have pure time of arrival I might have time difference of arrival or I don't have a global clock I just know how much time is elapsed since the last signal I heard in which case I can I could set up that modulation as some projection map down to a received signal space and in the end I'll wind up getting a signal profile mapping to this received signal space and the problem I want to address is this given some
19:55
signals some pings that I've heard how much can I infer about where I am located in the domain well that's a geometry problem but there's a topology problem a feasibility problem behind this how unique is that collection of signals is it possible for me to be at several different places in the domain adhere the same pings here are the same signals there's a very general theorem that addresses this question that says if you have a signal profile mapping whose
20:34
transmissions are generic you know up to small perturbations you you you jiggle things then the non injective set that is the collections of points where I hear exactly the same signals I can control the dimension of that set in terms of the dimension of the domain D and what is called the depth of the signal profile map which you should think of as how many transmitters can I hear at any given point that's a that's a somewhat abstract sounding result let's make it a little more concrete
21:11
let's say I'm in the plane and I'm using time of arrival so I can I can look at the clock and see whenever I hear a ping whenever I hear a gunshot go off anything like that then if I can hear five real-valued signals I know that I have unique localization well what's special about five and why isn't it three we're all used to thinking about triangulation right if I can if I can hear three signals and I record the time of arrival then I can triangulate I can figure out the distance to each
21:48
transmitter and I know exactly where I am ah but this is making no assumptions about the geometry this is not assuming that you have a nice propagation model with a waves propagate out as circles it can be on linear not just a little bit a lot a lot you know nothing about the propagation geometry well you can't do anything in that case can you yes you you can you can know that if you're hearing five signals then what you hear cannot be heard anywhere else in the domain
22:30
generically a small perturbation would take it away so that means if you have a collection of agents running around a domain and and two agents here the the same pulses then they must have they must have visited the same place now again how does that come from the serum well your domain is planar so it's two-dimensional if the number of signals you hear is five then the dimension of the non injective set is twice to minus five negative one what set has dimension
23:02
negative one the empty set and that's it that means that means that you have unique localization in this context and if you were to just just you know tease this out a little bit further and look at what you would need to localize in three-dimensional space well you'd need seven signals if what you're getting is time of arrival you'd need eight if it were time differencing if you use direction of arrival then you wouldn't have to hear as many transmitters you would only need
23:35
four a direction in 3d has has more stuff associated to it various things like that now we we played around with trying to run some experiments off of this to see how it would work solving a qualitative as opposed to quantitative questions and this leads to something that well you know it's not it's not quite fair to call it topological sonar we're certainly not doing sonar since we didn't use any equipment more sophisticated than a cell phone to do it but my postdoc Michael Robinson soldered
24:12
up some sound cards that emitted some chirps at particular frequencies and then we we put a few of them around a table and took a microphone hooked to a laptop and just swept it around it it's terrible data the sounds echoing all over the place so our experimental setup was you know it cost us all about $10 but we took the data and then we took the data again with the stack of books in the middle now there's no way you're gonna be able to do high-quality sonar in image stack
24:46
of books from from this kind of data but but you can tell whether or not there is a stack of books there you can't solve the quantitative problem but you can't solve the qualitative problem if you wind up looking at this data sitting naturally in its four dimensional space you can try and project the data and see whether there's a hole or not it's not so easy to see it's rather ambiguous but if you apply some some algebraic topological constructs if you compute
25:16
the homology associated of the data then you see a very clear difference in these two settings and you can you can see the hole inside your domain Michael Robinson has just recently posted a preprint on the archive where he asks a question in topological signal processing can you with nothing more than your cell phone tell which way a ceiling fan is turning in a room there's no way you're going to be able to image a ceiling fan but by having the cell phone emit chirps and
25:54
have it bounce off the ceiling fan well that's not enough you can't do anything with that it's not enough signals but if you're in a room that has walls and you use not just the reflections from the ceiling fan but the multi bounce reflections off the wall then that's enough to be able to see the difference between a fan that's rotating clockwise and a fan that's rotating counterclockwise and you know using nothing more than a cellphone he was able to do that that's really something
26:27
topological it's really a degree a winding number and index for an example that you could do really easily in this building with undergrads consider the following problem some graduate students I was teaching a summer school to last summer in Utah we decided to try these ideas out just using laptops an apple is really a nice machine because it has a feature on it called airport you type an airport and it will tell you all the wireless routers that are nearby and all
27:04
the networks that are available with the signal strength associated to it so we had people walk around the building with the laptops just dumping that signal strength data into a file it was a big building there were lots of networks the data having one axis per network that you could hear per router for SSID the data wound up being about 120 dimensional space that it sat inside but of course it's just a an embedding of the the map of the building inside that
27:39
wireless signal space and doing a little bit of topology on the data set you know we very easily found the large atrium in the middle in which you know there's a there's a hole you can image the building without GPS using nothing more than just wireless signal okay so those are those are some examples of one type of application of topology to problems involving signals there's a very very different type that I would like to spend the the majority of the talk touching upon
28:22
and this is a particular type of integral calculus that we've had some success with in applying to sensor network problems and I believe I believe this is going to be very useful in developing something like a topological theory of signal processing something that is very qualitative but with a little bit of quantitative in it as well so if you don't mind let me take a let me take a few moments and tell you the basics of this calculus it's been around for about 30 40 years but very few
29:01
people have heard of it fewer have used it it's a calculus that's based not on the big measure but on Oyler characteristic on an algebraic topological quantity now Euler characteristic is very very intuitive it's really just a generalization of counting which of course is the primal topological invariant if I were to have a discrete set of points and I would say how many things are there every one would compute the Euler characteristic you just count the number of objects now if I were to
29:35
say connect two of those objects together glue them together and I could do that formally with a with an edge then the number of pieces that I have goes down by one for every edge then I add the Euler characteristic keeps track of that that works really well until you wind up building a cycle in your network and then the number of pieces hasn't changed but if you just follow the algebra of what you were doing before having a plus one for nodes and a negative one for edges your Euler
30:13
characteristic formally would would have to go down by one in fact it does so what's the difference between this and this nothing in terms of the number of pieces but the number of pieces is really just the simplest type of hole that you can count there's another hole here but the Euler characteristic is counting as well and if I were to fill that in with a 2-dimensional simple piece or simplex then the Euler characteristic would be bumped back up to 3 because
30:45
I've got three pieces with no holes this is motivation for what the combinatorial definition of Euler characteristic is if you have a space that's built from a finite number of pieces of different dimension then you count the number of pieces and grade it in an alternating manner according to dimension and the the very classical theorem is that this provides you with the topological invariant of your space that means that no matter how you break your space up
31:19
into cells long as it's a finite number you'll get the same Euler characteristic it doesn't matter how you deform your space as long as you don't add any additional holes break it up into pieces you'll get the same Euler characteristic now what is nice about this is that besides being so intuitive and so easily computed it can build the basis for a calculus it provides a measure against which certain functions can be integrated this subject has a fairly long history I learned about it from
31:54
algebraic topology but it has some antecedents in integral geometry as well even though it's been around for a long time it's had surprisingly few uses outside of algebraic geometry one of the most significant uses is in work in Gaussian random fields by Professor Adler and others and I got interested in the subject because I was motivated by a certain problem in data aggregation over networks and you know the thing about doing applied mathematics is when you have a problem
32:36
you have to solve it it doesn't matter what tools you get forced to use you've just got to solve it and that is why I learned this theory let me take a couple of minutes and explain the definition the integral and then what it's used for so if we want to build up a measure theory a calculus well you need to do what you always do you have to talk about measures that's the other characteristic you talk about measurable sets you need to talk about measurable functions well the measurable sets are
33:06
things that we're gonna call definable one can get very fancy here but for purposes of this talk just think semi algebraic sets sets it can be defined by a finite number of polynomial inequalities and on those measurable sets we're going to look at functions that are called constructible these are not going to be real valued functions they're gonna be integer valued functions and they're gonna be integer valued functions whose level sets are going to be nice and definable so think
33:42
of a piecewise constant function on a reasonable space now the results that we need in order to make this calculus work are that all these sets can be triangulated broken up into cells they therefore have a well-defined Euler characteristic and all of the functions that are constructible are likewise triangular Bowl I can represent each as a finite linear combination of characteristic functions over nice SATs okay with that set of definitions in hand it's very very easy to define this
34:21
calculus here's a very explicit definition the integral of a constructible function H with respect to Euler characteristic is what well H as we said before is a linear combination of characteristic functions functions that are won on some nice simplex let's say and 0 everywhere else well what happens when you see an integral on a sum what do you always do yeah you can always interchange him right well maybe not always but in in this talk you can because everything is
34:54
finite when you're looking at order characteristic so anytime you see something like this switch it around let's do that now whatever you know whatever integration is it got to be linear we can we can switch we could pull out the constant the only thing I need to know is what's the integral of a characteristic function with respect to a measure where there's only one sensible definition for that it's a measure the set what's the measure it's the Euler characteristic so the
35:23
definition of the integral with respect to other characteristic it's just the the finite linear combination of Euler characteristics of level sets pieces now why is this why is this well defined it seems like it depends on this decomposition but it doesn't and it doesn't because you have an inclusion exclusion principle for Euler characteristic why because or the characteristic is based on counting and counting is the fundamental measure in the world on which lengths area and
35:55
volume are based okay so with that definition in place let's talk about a let's talk about a the problem that motivated me to learn this calculus let's say that I have a network of sensors and these sensors are very very simple in the sense that they can count the number of targets that are nearby but they cannot do the sophisticated signal processing to do target identification they can't disambiguate the the sensing is anonymous in this sense now there are many reasons why you might want that
36:41
it's expensive to do target identification for privacy reasons you might want things to be anonymous or you just might not have time so for example the this sensor right here sees two targets but it doesn't know who they are this sensor here sees two targets but it can't identify them these two sensors can communicate but they can't disambiguate they don't know if they're seeing the same two targets or not probably are since they're reasonably close but they don't know so the problem
37:18
is one of aggregation how do I get out all the redundancy in this input and have the network collaboratively decide how many targets are there you might want to know where they're located etc etc but first off how many targets are being sensed over the network well maybe you've solved this problem before if if you enjoy doing research in sensor networks that's really what you were doing when you were yes because this is giving you the exact same data right you
38:00
click on a sensor in the network and it tells you how many targets are nearby doesn't tell you where they are it doesn't identify them for you you have to figure out how to count and in this case locate the targets based on based on this anonymous data now if you think about it from the targets point of view each target has some neighborhood of sensors that it activates you might call it a a footprint but it turns on and that's the perspective that's gonna
38:35
allow us to apply Euler's and get a very very simple answer to this problem even in a setting where we don't have a nice regular lattice like this so here's a very simple theorem that we can set up this is with you Lee Baryshnikov from a couple of years back I'm going to do what one always does in calculus that is make the unrealistic assumption that nothing is discrete and everything is on a continuum so I'm going to assume that I have some finite number of targets
39:05
inhabiting domain let's call it W and I'm going to assume that my sensors completely fill some topological space typically a continuum topological space let's call that space X it might be the same space as W it might be that the sensors are embedded in the carpet underneath you it might be that the sensors are in orbit overhead who knows but each point in X is a sensor that looks at some region in W counts how many targets it sees and returns the Associated number that number is just as
39:46
on the last slide the the depth of overlap of the target footprints what you are given is this counting function the sensor field that tells you for each sensor X how many targets it sees from that here is how you compute the total number of targets if we assume not unlike in minesweeper that each footprint has the same shape not geometrically topologically if we assume that each sensor has a support a footprint whose Euler characteristic is a constant and then the number of targets is just the
40:31
integral of this counting field normalized by n by the mass of each target the proof is crystal clear what is the integral of this sensor field well the sensor field is just a sum of characteristic functions over the footprints that's what this is illustrating and of course what happens when you see an integral on the sum you switch them and so the only thing I have to worry about is the integral of target footprints which we're assuming has a uniform Euler characteristic divided by
41:08
N and you get the number of targets and what's remarkable is that you do not need to know this decomposition in order to solve the problem you just need to be able to compute the integral oh except I made a mistake and what's my mistake my mistake is I better be careful that n is not equal to zero because of N equals zero this formula goes bad but of course who would care about sets of measure zero well this is not the usual calculus there are sets of measure zero that don't look
41:50
small for example here is a collection of annuli of rings that are embedded in the plane and they overlap where they overlap the sensors would read a value of two here they would read a value of one here they would read a value of zero it is clear how many such rings there are correct there are two or six or ten or twelve or eight or if you like for it is not unique how to decompose this into a collection of embedded annuli why is it not unique because an annulus has all the characteristics zero
42:37
it's a set of measure zero in this calculus and calculus does not play well with sets of measure zero so this theorem is it's really remarkable that it works because it does not work when you're dealing with sets of measure zero so the first lesson in this calculus is B where you where here's a here's an example where things do work nicely let's take a collection of target footprints that are all simple contractable sets if you look at them you can you can count how many there are
43:12
with your brain brain works well if I remove the colors it's a little more difficult but from a general formula that tells you you can sum up the Euler characteristics of the upper excursion sets we can compute this really easily I look at the set of all sensors that are turned on compute its Euler characteristic that's a negative one I look at the set of all sensors that read a value of two or more there are three patches and then one annulus that has Euler characteristic three I keep moving
43:47
on up looking at sensors that read higher and higher values computing the Euler characteristics when I'm done if I add all those together I get the correct answer the value of the integral the number of targets which is seven and I didn't need to know how this was broken up into pieces in order to be able to compute that here are a couple of other circumstances under which you know a result like this might be useful let's say that you have a sensors that count wave fronts you
44:22
have some sort of event that happens a wave goes out and you have a sensor that every time it hears a wave increments a an internal counter how many waves are there this is a non-trivial problem you know I come from Philadelphia where there's gunshots that go off now and then and you interview people afterwards and no one can tell you how many gunshots were fired you get all kinds of crazy answers if you have a collection of sensors that are poised none of them can hear all of the waves can you
45:00
disambiguate figure out how many the girl there were without you know without any sort of a central coordination well the resulting target impact sets are all contractible so if you just integrate this height function over the network with respect to Euler characteristic you want it getting the right answer what's nice about this is that nobody has a clock nobody kept track of when they heard the wave they only kept track of how many waves passed overhead that's interesting because as
45:36
you know it's not easy to synchronize clocks over a network it's great if you could solve the problem without it in similar vein if you have a collection vehicles that are driving around with sensors embedded in the asphalt and every time a car rumbles overhead click I heard another vehicle go by then even if you have cars that globally loop back on themselves integrating the underlying counting function is still gonna give you the total number of vehicles that
46:07
you have this is an application of the fubini's theorem in this texts okay you know all of these things sound great but how do you actually compute this stuff again the theorems are proved in this unreasonable situation where you have a continuum of sensors a sensor at every point in in the domain that's we just can't build that kind of stuff yet well you know in solving this problem in terms of an integral and in given the integrand that sampled at some discrete
46:45
set well we already have a lot of practice at doing numerical integration you know people in applied math are pretty good at that one let's just import what we know from numerical integration theory over to this context win okay let's see how well your brain does at numerical integration here's this compute the Euler integral you could do that not a problem now I'm gonna discretize the input but I'm gonna do so very nice it's gonna be very dense it's gonna be on a nice
47:16
regular lattice let's see let's see how how good your brain is at doing the integration here ooh that is not so easy and this is totally unreasonable you're not gonna get sensor networks like this you're gonna get sensor networks that are like this where the sampling is sparse where maybe you don't know the exact coordinates of these points but you have a proximity measure you know when nodes are close or not this seems pretty hopeless I'm afraid instead of telling you
47:48
theorems that we've proved whoops go back let me show you those theorems in action by showing you a little bit of software that we've written in order to to do numerical integration there's some good news and bad news good news is it kind of works keine bad news is it only works in the plane there are fundamental reasons why this technology will not work in three-dimensional space but let's say I have a random ad-hoc sensor network I drop a target and some footprint turns on now
48:24
you can see that there's under sampling that's occurred here there's a hole inside of there that seems like it could cause problems let me drop another target ah there we go and on the overlap those sensors read to they they were impacted by two targets now if I integrate this with respect to other characteristic it's gonna give me the right answer even though there was some under sampling going on that's the that's the good news that's the good news and because it's a
48:54
topological results and not geometric I can have some target impact sets they're really quite big and nonlinear looking and you know I can keep going and maybe you know maybe I'll get the right answer when I do this maybe after I've put down enough things the sampling well it still works maybe the sampling will be such that I I really don't have enough data points in order to be able to get the correct answer so let's see what happens I might be off by Epsilon
49:27
no darn it I'm not off by Epsilon soon I will be off by epsilon let's say please be off by Epsilon well you know I didn't set this up in advance darn new software for working too well now I'm off by two epsilon I'm very happy not like two Epsilon the correct answer is 18 but it computed 16 and this reveals the big problem Epsilon's are not small in this integration theory everything is integer valued so when you're off by epsilon you're off by a lot and the news gets
50:08
even worse because if I add noise let's say we just percent of the nodes go bad but not too bad just read a plus or minus one visually not much has changed if I integrate now with respect to Euler characteristic I'm off by much more than epsilon much much more than epsilon what I would like to do is to do what we you know we do in numerical analysis smooth the data out but that's difficult in an integer valued setting so what we would like to do in moving towards numerical
50:46
integration is to move beyond an integer valued Theory let me outline how that goes so we're gonna do that we need we need to look at reasonable real valued integrands these are gonna be integrand Suz those graphs are definable we're nice so you know nothing to fractally something reasonable and I'm gonna do the the most simple-minded thing I can think of which is a Riemann sum type definition I'm gonna I'm gonna take my continuous my real valued function and
51:21
I'm going to approximate it by a step function from below and then I'm gonna blow it up so that it's integer valued in a great with respect to Euler characteristic blow it down and then take a limit as my steps get smaller and smaller the good news is that limit exists that's a good news now of course there's no reason why I should have chosen steps from below as opposed to steps from above but of course he's converged to the same function so this limit also exists but
51:58
the bad news is these two limits are not the same and so we wind up getting two in equivalent integrals for real valued functions that is the first hint that I've done something wrong the second hint that I've done something wrong is that neither of these are linear operators because the floor function and the ceiling function are not linear these are nonlinear integral operators you don't have a fubini's theorem all kinds of things go bad this is surely the gods telling me I'm doing it wrong
52:36
but but with a little bit of persistence I think I think we have an argument that this is not wrong there's a very deep mathematical theorem that I will not delve completely but a crawler II of which is that you can express these integrals in terms of critical points for your function so you know in the context of something called Moore's theory you can express these in terms of the the Moore's indices of critical points in slightly more down-to-earth language if you were to integrate a nice
53:11
smooth function over a surface what would these integrals with respect to other characteristic be it's simply the sum of the maximal values minus the sum of the saddle values plus the sum of the local minima values so these these integrals really collapse the measure down to a finite number of critical points and that's where everything is happening and if you were to move down to a one-dimensional manifold then you would see that these this is really just total variation so this integration
53:50
theory is a generalization of total variation it's a higher dimensions that takes into account some of these some of these fancy ideas Moore's theory that really winds up being helpful in doing things like numerical computation because now in the real valued theory I could do something like convolution with a Gaussian and smooth that out if I do so I went up getting you know something that's nice and smooth remember that had all that noise in it and we were off by
54:22
much more than epsilon if I integrate it now with respect to this smoothed out order characteristic measure well you know I'm closer to what I started off with but it's off by quite a bit it's off by it quite a bit lower it's never going to be quite a bit higher how do I know that I know that because the way that you do the integral here is by taking an alternating sum of the critical points the Maxima the minim of the saddles after smoothing out with a bump function oh I've taken a whole
55:01
bunch of maxima and pulled them down or as I haven't done much to change the saddles and the minima are not going to keep up with the maxima so I know that I'm gonna get something below the true value okay now talking in terms of convolving with a with a Gaussian to smooth data leads to what I see as some very interesting potential applications of this integral TLS to something like signal processing or image processing and I think the key to making these applications is to start
55:41
looking at integral transforms there are a number of very interesting integral transforms that one can define in this novel integration theory that have some unusual effects now maybe maybe you're familiar with Redang transforms and how they work there's a there's an oil airy inversion of a radon transform that write down the formulae they're kind of complicated like normal integral transforms but a cartoon is it's kind of helpful this this integral transform
56:15
takes a kernel s that is a subset of a cross product of two spaces and and what does it read on transform do it takes a function over this space lifts it integrates out in this direction to get a function over this space properly interpreted the kernel of the radon transform is the sensing relation where sensors detect targets living here and this word on transform is really what's converting target data to sensor data so if you can invert the radon transform you can go from having sensors
56:55
counting targets to not just figuring out how many targets are but under inversion of the integral transform locating where the targets are that's that's an important problem in radar imaging for example and in reconstruction there are other interesting integral transforms out there in the the the algebraic topology and algebraic geometry literature there's something called a micro local Fourier transform which sounds like engineering right well I don't recommend
57:30
going to read the literature on the micro local Fourier transform it's a little hard to see the connections to engineering but they're really hiding there there's a strong connection to curvature properties sitting inside of this very very topological machinery well that's a bit obtuse let me let me bring it down to earth by mentioning an integral transform that's a something that Michael Robinson and I worked to invent over the past year that's not a micro local Fourier transform it's more
58:04
like the the regular Fourier transform but without the complex numbers so how do I think about a Fourier transform let's say I'm in a planar domain I have to choose a frequency vector right and then when I do the the integral well you've got that dot product between the spatial vector and the frequency vector which means that you know it's equivalent to saying you integrate over all the all the ISO spectral hyperplanes everything orthogonal to the frequency vector now here's the idea behind the
58:39
this integral transform you mix up the Euler and the lebesgue measures and so mix up topology and geometry in so doing so I'm going to integrate along these hyper planes with respect to Euler characteristic and then integrate along this direction with respect to lebesgue and let's see what happens let's see what happens let's take as our our integrand a characteristic function over some shape some blob now what happens when I intersect it with this hyper plane I get an interval what's the Euler
59:14
characteristic of an interval one so in the frequency direction I get a function that's 0 and then it's 1 and then it's 0 and if I integrate that with respect to lebesgue measure what do I get I get the length of that interval was this correspond to well it's it's the projected width of this object with respect to this frequency direction so you can infer information about the geometry of your object from this Euler Fourier transform and there are there are other modifications that you can do
59:54
as well if you took a polar version of this Fourier transform you get something it's kind of like a Bessel transform we call it an Euler Bessel transform if you base it at a point X no more frequency vector just base it at a point X and then integrate along these concentric spheres with respect to Euler istic what are you going to get well I'm going to get a 1 and a 1 and a 1 and 1 and I'm gonna get some sort of radial projected width but that integral transform is
1:00:23
going to give you different results depending on where you put the base point X if I were to put the base point X in the middle of the box then something very different would happen because on all of these ISO spectral sets I would get the Euler characteristic of a circle what's the other characteristic of a circle zero so it wouldn't contribute and I would have a minimum of my Bessel transform here at the center of the target ooh that sounds like a useful thing and and in fact it
1:00:58
is we've done a little bit of playing around with these sorts of things at doing shape detection but we found that computing the transforms was difficult what helped us a lot was a theorem that told us how to compute the Bessel transform in terms of these real valued Euler characteristic measures in in the plane you wind up getting a very simple formula that tells you something about the vessel transform over the interior of the domain with respect to the integral over the boundary of the domain
1:01:36
and if this reminds you somewhat of Stokes theorem that's that's really that's really reminiscent of what it is so this helps us dramatically in terms of computing the Bessel transforms on things like polygonal shapes at the boundaries and what we've used this for is in not only target localization finding the center of an object but in shape discrimination let's say that you have a collection of targets that overlap just from counting data taking the Bessel transform in an l2 sense
1:02:17
allows you to identify which of the targets was round even when you have significant amounts of overlap between these targets significant interference between the shapes you can pick out which one has the shape you want and by tuning the integral transform in the same way that you tune transforms in radar signal processing we can wind up doing things like Oh find me the square target or find me a square target up to rotation by doing apodization well you know
1:02:51
that's a that's kind of a lot there at the end and I really didn't talk about the places where this could go there's a lot of open questions in the subject with very few people working on it can you do wavelets in this integral theory we have one or two examples of a wavelet transform seems to give interesting results on images I don't know what's the oil aryan version of an fft wouldn't that be interesting especially if it has one-tenth the impact that the
1:03:27
regular fft has had and the big question is how do you do numerics how do you do numerical analysis we have software that just works in the plane and works under limited circumstances and we don't have a lot of good theorems about when we get the right answer and all this is really just a small portion of what's happening in a much broader movement of applying algebraic topology in the engineering sciences in the biological sciences and the statistical sciences and and even this is a small
1:04:02
part of what's happening in contemporary applied mathematics and with that come back with that I will I will say thank you to some of the people in my group who have helped with some of these results and I will say thank you to you for listening
1:04:39
okay so Roman will be arrested today
1:04:53
I don't know this is uh this is the this is the American Morris this is Marsden Morris I don't think that's the same Morris I think it's a different Morris yeah
1:05:19
all right thank you
Here to help you learn
Sign in to keep a private conversation with your course tutor.
Ask me anything about the material…
Sign in to chat