Toposes for Wireless Networks: An idea whose time has come
This is a modal window.
Das Video konnte nicht geladen werden, da entweder ein Server- oder Netzwerkfehler auftrat oder das Format nicht unterstützt wird.
Formale Metadaten
| Titel |
| |
| Serientitel | ||
| Anzahl der Teile | 6 | |
| Autor | ||
| Mitwirkende | ||
| Lizenz | CC-Namensnennung 3.0 Unported: Sie dürfen das Werk bzw. den Inhalt zu jedem legalen Zweck nutzen, verändern und in unveränderter oder veränderter Form vervielfältigen, verbreiten und öffentlich zugänglich machen, sofern Sie den Namen des Autors/Rechteinhabers in der von ihm festgelegten Weise nennen. | |
| Identifikatoren | 10.5446/46721 (DOI) | |
| Herausgeber | ||
| Erscheinungsjahr | ||
| Sprache |
Inhaltliche Metadaten
| Fachgebiet | ||
| Genre | ||
| Abstract |
|
00:00
TopostheorieHomologieGruppenkeimBeobachtungsstudieOrdnungsreduktionVektorraumMinkowski-MetrikMannigfaltigkeitLokales MinimumWellenpaketPrimzahlzwillingeMaß <Mathematik>Inklusion <Mathematik>PolareÜbergangswahrscheinlichkeitMatrizenrechnungVakuumpolarisationSymmetrische MatrixStichprobenfehlerExponentPotenz <Mathematik>TopologieGraphNichtlineares GleichungssystemApproximationGleichheitszeichenKomplex <Algebra>DreieckSimplizialer KomplexÄquivalenzklasseGarbentheorieElement <Gruppentheorie>BimodulFunktion <Mathematik>SimplexverfahrenGesetz <Physik>Pi <Zahl>Allegorie <Mathematik>Orientierung <Mathematik>MorphismusQuotientUntergruppeLineare AbbildungRandwertGruppenoperationFolge <Mathematik>KettenkomplexStichprobennahmeNichtunterscheidbarkeitTheoremScherbeanspruchungUnendlichkeitPermutationFormale PotenzreihePunktrechnungAbelsche GruppeNichtlinearer OperatorBetti-ZahlZahlentheorieStreuungsdiagrammPunktModulformHausdorff-DimensionMengentheoretische TopologieEbeneAbstandMathematikTopologischer RaumVakuumpolarisationLineare AlgebraMatrizenrechnungÜbergangswahrscheinlichkeitSimplizialer KomplexMultiplikationsoperatorGalois-FeldVektorraumOptimierungsproblemSymmetrische MatrixHomologiegruppeModulformExponentEndlichkeitFaktorgruppeGraphentheorieKozyklusPotenz <Mathematik>Lineare AbbildungStichprobenfehlerGraphBetti-ZahlNichtlineares GleichungssystemSimplexverfahrenDatenanalyseGruppenoperationMinkowski-MetrikMengentheoretische TopologieGraphfärbungDickeDreiecksfreier GraphTermPropagatorVerschiebungsoperatorKategorie <Mathematik>Ordnung <Mathematik>AuswahlaxiomPunktRechter WinkelBerechenbare FunktionZeitbereichFlächeninhaltKartesische KoordinatenMultiplikationRandwertBasis <Mathematik>SummierbarkeitModelltheorieRelativitätstheorieStellenringPhasenumwandlungWiderspruchsfreiheitFunktion <Mathematik>TransmissionskoeffizientPhysikalische TheorieFolge <Mathematik>ZweiKoeffizientZusammenhängender GraphQuantisierung <Physik>RechteckRauschenKlassische PhysikFunktionalGarbentheorieArithmetischer AusdruckKette <Mathematik>EinsRuhmasseRadikal <Mathematik>RichtungOrientierung <Mathematik>SterbezifferTVD-VerfahrenMengenlehreEinflussgrößeReduktionsverfahrenAlgebraische StrukturRangstatistikKlasse <Mathematik>RadiusOrtsoperatorDreieckIndexberechnungGrenzwertberechnungParametersystemUntergruppeWellenlehreAlgebraisches ModellMorphismusElement <Gruppentheorie>MultigraphEndlich erzeugte GruppeFaltung <Mathematik>MereologieKnotenmengeUltraviolett-PhotoelektronenspektroskopieTheoremStichprobenumfangMathematikMomentenproblemNichtunterscheidbarkeitDifferenteFormation <Mathematik>GruppendarstellungFamilie <Mathematik>HomologieNebenbedingungResultanteStreuungsdiagrammProzess <Physik>PunktrechnungUnendlichkeitAnalysisTopologieGlobale OptimierungInklusion <Mathematik>Spezielle unitäre GruppeAdditionLeistung <Physik>DifferenzkernDimensionsanalyseZentrische StreckungMannigfaltigkeitQuotientAbelsche GruppeLikelihood-Quotienten-TestTopostheorieKohomologieAggregatzustandNichtlinearer OperatorSigma-AlgebraLokales MinimumMassestromLinearisierungTorusGrothendieck-TopologieComputeranimation
Transkript: Englisch(automatisch erzeugt)
00:18
Yeah, exactly. There is, in fact, I hesitated regarding the question mark
00:27
because at the beginning I was not sure at all. I mean, there are many aspects of topos, probably, that could be right now very interesting for what we are
00:40
doing, but then there are some other aspects. For now, I have no idea of what they could bring to our activity, to our way, and essentially in wireless networks. So, in fact, this talk is essentially a way of trying to
01:05
identify the topics covered by these wireless networks, the topics in which topos can bring some value. And, in fact, at the beginning I had very few
01:30
of them, and then by thinking, by looking at the literature, many other ones came to my mind, and I think that it's just the beginning, and probably in the near
01:45
future we will be able to identify even some other topics very interesting, and that could bring some solutions to some of our problems. Okay, so let's start with
02:03
the problematics that we have in wireless networks and that could be impacted by topos. Okay, so first, what is wireless network? What is the wireless communication in general? In fact, it is something that uses a
02:25
lot of tools that are very diverse, for example, information theory, so Shannon theory essentially, signal processing, because in these wireless communication
02:42
networks, in fact, we have to transmit bits, and the problem is that to transmit bits, these bits have to be converted into signals, and then, of course, at the receiver these signals have to be processed in a way that we can, for
03:01
example, minimize the error probability or some other measure. We have also optimization. For example, I mean, there are many points where optimization can be useful, and I can give you an example. Suppose that you have, in
03:21
wireless networks, in fact, the wireless network is a cellular network, and the problem is that each cell interferes with the neighboring cells, right? And the problem, of course, is that if everybody starts to talk loudly,
03:42
the problem is that you will impact the signal-to-noise ratio of the neighbor that will start to speak even louder, et cetera, et cetera, and so, of course, it will diverge, and that's why there are some procedure which I'll call the power control in order to avoid these problems, and we have
04:08
to find the optimal solution of power control, so it's an optimization problem that can be decentralized or decentralized. We have also a problem related to data fusion. For example, if we have sensors, we want to use them in order to
04:24
localize terminals or in order to do something else, and then we have graphs. So graphs can be used to study the cellular network. It can be used also for channel coding. I will give you some examples afterwards. And finally,
04:44
maybe I forgot some of them, sorry for that, and finally, at least in my list, there is channel modeling, which is very important because this is the basis of the wireless network, and in order, for example, to be able to transmit or
05:05
to receive efficiently the signals that have been transmitted. In fact, we need to know the behavior of the channel, and we need to model the channel in some sense. Okay, so you see, there are quite a lot of technical areas
05:27
impacted by wireless. So now, okay, if I just copy the definition of the Grothendieck topos, what can be the relation between this and this? This is
05:42
not obvious at all, and this was the problem that I was faced with that problem, so which of these items can be impacted by this? In fact, it's not
06:01
easy at all to answer directly, but just using the definition, we can first try to find some relations between some of these topics, maybe all of them, you will see. The first one, for example, Daniel has shown in his talk the
06:21
relation that we can find between information theory and the topos. For the other ones, there can be some relations, and in fact, I will start by finding some relations between these points and sheaves. Okay, and moreover,
06:41
there is another constraint we have. The problem is that we need to implement algorithms, we need to perform computations, alright, and so we need to use computational and algorithmic mathematics, and that means that, for
07:03
example, the sites or the topological spaces that we will have, that we can use, will be quite restricted. They cannot be, I mean, we need to find the
07:20
ones onto which we can compute some interesting quantities, like cohomology, etc. And also, we need to find, let's say, some, we need to find also sheaves that give rise to computations that make sense for us. For example, what we
07:46
can do the best is linear algebra, in terms of computation, and that's why we will mainly focus on these restrictions. Okay, so first of all, I needed to analyze
08:05
why we need, we could need the sheaves, or more deeply, topos. In fact, this property of sheaves is the one which we need the more. That means
08:21
the how to reconstruct, I mean, from local to global, we have local data, how to reconstruct the global picture. And in fact, that's why the computations that we will mainly be faced to, will be the computation of cohomology
08:40
groups, etc. And also, sometimes, to derive some criteria for setting to zero some cohomology groups in order to remove the obstructions. For example, our local data can be local probabilities, they can be LLRs, so
09:04
this is log-likelihood ratio, so it is related to probabilities. For example, for coding, for channel coding, there can be local interferences if we consider the cellular network, and we want to go from the local interference picture
09:22
to something more global. And so, in this case, we need from there to derive the right sheaves, and so for the last stage, I have to confess that I haven't too much idea for now. Okay, let's start with one of these applications,
09:45
which is in fact the channel, it is the basis, the channel is the basis for us. Okay, so first topic is, I would call it learning the channel, I can tell you why.
10:00
Suppose that we have, for example, this is a cellular network with here cell with its base station, so you see the antennas, and a mobile terminal that communicated with this base station. I consider in this example the uplink, and
10:21
so we have, let's say that in general, if we use a simple model, we can say that what we receive on all antennas, so this is why there is this word MIMO, which means multiple input, multiple output, so multiple antennas are the
10:43
transmitted, multiple antennas are the receiver. So, in fact, it is this model, which is the simplest and the most commonly used. So, what we receive at all the antennas is modeled as a vector, Y, and it is some matrix H times what is
11:01
transmitted by the terminal, which is also a vector, and plus some noise, Z. This noise component, in fact, can incorporate also interferences coming from the neighboring cells. So, as you can see, here the channel is characterized by this matrix, H, all right? The problem is that we have
11:24
to recover the signals that have been transmitted here, so which are embedded in the vector X, and, of course, if we don't know X, we don't know X, and if we don't know H, then we are in trouble. So, what, no, no, no,
11:42
it can, it's a rectangular matrix in general, yeah. So, the idea is that, of course, we have to know in some sense the H matrix. So, what we do in this kind of network is that we transmit what we call
12:01
pilot sequences, which is, in fact, a sequence of known symbols, and onto which we will project the coefficients of this channel matrix so that we can estimate these coefficients, all right? And at the end, so, our new problem is that we have just to detect what has been
12:24
transmitted in X when we know, in some sense, or when we have estimated the channel coefficients which are embedded in this matrix, H. Okay. So, this is what happens in the multi-user case. So, you see, you have exactly the same kind of expression, but then we have the sum
12:45
of the two components coming from the two terminals. So, now for 5G, 5G, in fact, is using what is called Massive MIMO, which means that the base station, we have a lot of antennas, many, many antennas, it can be 64, 128, okay? And what is called CSI,
13:07
so it is a channel state information, so it is the knowledge of the channel or the knowledge of the H matrices lives, in this case, in a high-dimensional vector space because of Massive MIMO. So, the problem is that in order
13:24
to estimate all these coefficients, we need to send a lot of pilots, all right? And at the end, the problem is that if we send pilots, then we have less space for sending data. And that's why one possibility
13:41
could be this because, in fact, the CSI lives in a very high-dimensional vector space. In fact, what is sure is that for a given cell, let's say that the set of all possible CSI doesn't fill the whole space,
14:02
but rather lives in the manifold, which will be of dimension, which can be, if we have many, many antennas, it can be much less than the whole space, the whole original space, all right? And so, the idea should be here to go from this high-dimensional vector that
14:22
requires a lot of pilots, and so, which will, let's say, prevent the transmission of high-rate datas. Instead of using the whole space,
14:42
just try to use this manifold of lower dimension, all right? In this case, it will reduce signaling and also reduce the feedback. So, the feedback can be necessary, for example, if you want to transmit then, for example, in downlink from the base station to the terminals, the base station has
15:03
to know the channel which goes from the base station to the terminals and which is accessible only at the terminals, for example, I mean, in some cases, let's say, let it be not too general. And in this case,
15:23
learning this manifold, knowing what could be this manifold, could be very valuable for us, okay? Then, another problem, I mean, another application related to the channel is fingerprinting. So,
15:40
there are some people in our lab who have implemented some fingerprinting approach in order to have the localization of the terminals by using machine learning. The idea is to use the CSI, so the channel knowledge at the base station, in order to determine the localization of the terminal, okay?
16:04
So, what is the idea? The idea is that, in fact, by using supervised machine learning, we train a neural network, it can be extreme learning, deep learning, I mean, there are many possibilities, in order to learn,
16:24
given, let's say, a function, phi, which defines a manifold here as well, and this function, in fact, is a function of the CSI and of the position of the terminal, okay?
16:40
So, we train a neural network in order to learn this function, or at least partly, and then, once this stage is finished, we can find the localization as a function of the CSI, all right? The problem is that, in this case, as well as in the other case, what happens is
17:03
that the manifold we have to learn, in general, is learned with noise, it can be noisy observation, we can have small variations of the channel, because the problem is that the channel
17:21
behavior depends also on the obstacles that you can find on the path of the waves, and these obstacles may be fixed or moving like cars or human beings, I mean, yeah? So, this is another, let's say, example where we need to learn some manifold which can be
17:52
impaired by noise, by some clattering, by, you know, some small changes of the channel, all right? So, and for these two cases,
18:06
in fact, we can propose to use persistent topology to solve at least partly these problems, okay? Another problem, so, what is quite amazing is that this morning I have discussed
18:27
with Daniel about this belief propagation on graphs, and I didn't know that there were some solutions, I mean, based on the computation of cohomologies, and yeah, so that's good news for
18:43
us. Okay, especially we have this problem of making belief propagation work on graphs, essentially in channel coding, okay? So, for example, in 5G, so in the fifth generation
19:00
that we are developing right now of wireless networks, wireless cellular networks, in fact, the channel codes that have been adopted for 5G, I mean, for what has been done right now, but maybe there will not be so much changes in the next releases,
19:23
there are what are called LDPC codes in order to encode data bits, and polar codes in order to encode control bits, control channels. So, data is the information that is sent, and the control is the bits that are useful in order to make the network work, okay? So, and
19:46
these two families of codes are quite different. LDPC codes, in fact, are decodable by using a belief propagation of a graph, which is called a Tanner graph, and polar codes are decodable using another kind of algorithm, which is called serial cancellation, and apparently,
20:05
it's not related to belief propagation, not yet, let's say. So, what we know about the decoding of LDPC codes is that the Tanner graph of LDPC codes on which we have to run belief propagation is loopy, we have cycles, and so, in this case, we know that belief propagation
20:24
doesn't work, I mean, we cannot make it work well, or it's something that is very painful, very complex, and so, okay? Oh, sorry, yeah, yeah, yeah, sure, sorry for that. So, you have a graph,
20:42
yes, and the idea is that you have some probabilities on vertices of this graph, right? And the idea is that, for example, you have some constraints,
21:02
some vertices can correspond to some constraints, okay? That, in fact, will change the probability, you start with unconstrained probabilities, and then you take into account these constraints, right? By, and you have, the idea is to do what is called also
21:23
message passing on the graph, on the edges of the graph, so that you take into account locally all these constraints, right? And at the end, the idea is to have a global understanding that means, at the end, let's say, the optimal thing that you have to do is to,
21:48
let's say, to take into account, let's say, all these constraints, right? And if you have a tree, then it's quite easy to do it, right? But if you have cycles, then
22:05
we get some issues, and it's very hard to have the optimal solution in this case, right? But for LDPC codes, in fact, the method we use to decode them is to use belief propagation
22:27
as if it were a tree, because what we know is that when the length of the LDPC codes goes to infinity, then the tanner graph tends to be a tree. But, of course, we are not using infinite
22:40
length codes, and the idea is that we use belief propagation as if it were a tree, so it's so optimal, but we design the code in such a way that the gap to optimality is kept small. Okay, so in this case, let's say that we don't really need
23:10
to run belief propagations on a loopy graph. But there is another case, which is polar codes. So, very quickly, polar codes is based on what is called the kernel. So, suppose that you have
23:27
so the simplest kernel, which is the original one, is called the Arikan's kernel. So Arikan is the inventor of polar codes, and in fact it works in this way. u1 and u2 are two bits, all right?
23:43
And then x2 equals u2, x1 equals u1 plus u2, okay? Then x1 and x2 are sent into the given channel that can introduce errors, erasures, or can add Gaussian noise, for example.
24:05
And so, in fact, x1 and x2 will see exactly the same channel, right? And the output of the channel will be y1 and y2. But then, the idea is that in this case, what u1 and u2, which are the information bits, what these bits will see, I mean, which channels will they see?
24:26
Because, of course, x1 and x2 will see the same channel, but u1 and u2 will not see the same channels. And so, here is how it works. So, okay, this is matrix form, and let's do a capacity analysis of what happens here. Okay, suppose that i of x and y is the mutual information
24:48
between x and y, so it can be an index because it's exactly the same channel we have here. So, if we consider this vector channel, now we have the mutual information is the sum because
25:03
it's these two channels are independent, and so this is i of x1, x2, and the vector y, which is y1 and y2, okay? Then, I replace, in fact, what I want to know is what happens if you,
25:22
instead of having x1, x2, you have u1, u2. So, in fact, because u1 is x1 plus, sorry, because in this case, you can recover u1 by doing the addition of x1 and x2. And then, once you have recovered u1, you can say that u2 is just, can be recovered
25:44
by the observation y and the knowledge of u1, then you get this kind of equality, right? And what, in fact, what happens is that this first term is smaller than the symmetric mutual
26:04
information, right, which is the capacity in this case if we consider symmetric channels, and this will be larger, okay? And now, polar codes are formed by considering the end time, sorry, the Kronecker power of this kernel, of the Arachn kernel, okay?
26:26
And in this case, what happens is that for a given ratio of the bits that we have, the first term will tend to zero, and for the rest, it will tend to one. And the ratio
26:43
of bits for which the mutual information here tends to one will exactly be the capacity of the channel if n goes to infinity, all right? So, and this phenomenon is called the channel polarization, and this is why these codes are called polar codes, all right?
27:06
But then the problem is that this Arachn kernel is polarizing but too slowly, so too slowly with respect to the length of the polar code. So the idea is that we want to find some better polarizing kernels. Of course, their size will be bigger than
27:26
two, which is the case for the Arachn kernel. It will be of size L for given L. The problem is that if we have a general kernel, so a general kernel will be, let's say, a square matrix of size L and which is invertible in the finite field of size two, okay?
27:45
And, okay, let's forget it. So this, and what we know is that channels with better scaling exponent exist if the length is more than eight, and there is another exponent which
28:04
is the error exponent, and these two exponents in fact characterize the way the channel polarizes with respect to the length of the code. And for example, there are kernels, okay, for example, this channel of length 16 is known to be the best channel in length 16 in terms of
28:25
error exponent, okay? So now what we have to do is that if we want to find the equations of decoding of a big kernel, then in fact for each bit that is decoded,
28:44
it corresponds a tanner graph, and this tanner graph may have cycles. This is, for example, for length eight, and for decoding the third bit, this is the corresponding graph. As you can see, they are cycles, and this is a very simple one. If you have, for example, the kernel
29:04
that I showed you, the EBCH kernel of length 16, for decoding, for example, bits in the middle, then the tanner graph will be terrible. It's something that is very, very hard to decode,
29:25
okay? And how to decode it is by running belief propagation on this kind of graph, on the tanner graph, okay? And we cannot do the same as for LDPC codes, we cannot change the code,
29:40
because this is not the code, this is the kernel that is fixed, and so we have to find a way. And what I was thinking even before talking with Daniel was that belief propagation is exactly this, local to global, so there should be some cohomology and so, and I was happy
30:02
to learn that it's true, so I will be happy to read what you have done on this topic. All right. Now, okay, now we have identified a couple of problems. I have also identified some publication which applies shifts on the domains, on the areas
30:25
that I have listed at the beginning of my talk, right? And I can show you a couple of examples. First one, sorry, before starting, we have in fact, as I told you, to use
30:46
topological spaces on which we can compute things like cohomology groups, and in this case, one good choice is to use simplicial complexes as topological space.
31:02
So for those who don't know what it is, so what is a case simplex? Let's say, so this is the concrete point of view of simplicial complex, and so this is, for example, zero simplex is vertex, one simplex is an edge, a triangle for two simplex,
31:22
the triadron for three simplex, et cetera. And a simplicial complex is a finite set of simplices that satisfy these two properties. Now, in order to apply this,
31:48
for example, to be able to compute cohomology on these simplicial complexes in a way that will be efficient for our applications, in fact, this is a very restricted way of defining
32:02
presheaf on this complex, but it is the one which will be useful for us. So in fact, we define our presheaf on the category of vector spaces, or it can be modules, and so we define, of course, a restriction, which we call this way,
32:29
f of a rho b and a b are two faces, and of course, we have consistency of the composition.
32:41
And we have also to define a morphism between presheafs or sheafs, and so this is a, it assigns for each face a linear map, which satisfy this equality. And then we define a quantity, which is, so b a, and this quantity equals zero if a is not
33:07
a face of b, otherwise, it equals plus or minus one, depending on the orientation. And these quantity will be useful to compute with what follows, and essentially the co-boundaries,
33:22
et cetera. So this is our co-boundary, which is defined this way. And so this is the formal sum over all k-simplex, and you see this appears, so this is the restriction map, and sigma of a, sorry, okay, let me go on.
33:50
So this, we have the classical, we have the classical relations between the kernel of decay and the, so the cycles and the co-boundaries,
34:09
and because of that, of course, we have bk, which is a subgroup of zk, and in this case,
34:24
the cohomology group, the k-th cohomology group will be defined in this way as the Gaussian group. Okay, and in this case, we get a sequence of linear maps from, and of course,
34:42
this, in fact, the idea is that only the elements of, in fact, the idea of this cohomology group is that only the elements of zk that are not already consistent are worth mentioning. Okay, and now let's apply it to sampling theory. So this example comes from this
35:08
reference from Michael Robinson, and he proposes a sheaf interpretation of the sampling theorem. So, in fact, he starts with a sheaf of vector spaces on an abstract simplicial complex,
35:22
okay, and then he uses sheaf morphism between two sheafs, so f, which is a sheaf on this simplicial complex, and s is, in fact, what is called the sampling sheaf, and which correspond to the operation of sampling, and it is associated to a sampling morphism from f to s,
35:48
and then he defines an ambiguity sheaf, a, in which simply the stalk, in fact, a of small a, where small a is a face, is just a kernel of this map. All right, and this is the sheaf
36:08
theoretic sampling theorem that he derives. It is that the global sections of f, so of s, are identical with the global section of s, which means that we can reconstruct,
36:21
in fact, we can reconstruct the, we can reconstruct the, this just from this, if and only if, in fact, the case homology group, cohomology group related to the
36:43
sheaf is zero for k equals zero and k equals one. So, and from there, it can recover the classical Shannon-Hartley sampling theorem of band-limited functions, for example, or some other results coming from graph theory or
37:05
from a quantum graph, if I remember well. Okay, so, in fact, we can have, in signal processing, we can, by using sheafs, we can generalize the results that we had at the origin.
37:26
Second example, network coding, and it has been developed in this paper from Grist and Irauca, and, in fact, so very quickly, they have, they have been the sheaf cohomologies,
37:40
in which case H0 is equivalent to the information flows that we have in the network, and many practical problems may be solved by using these cohomologies, such as the max flow bounds, network robustness, and some other ones, right? And the final example, persistent homology, which I think will be very valuable in our case, if we want to learn the
38:07
channel, to denoise what we measure, so to denoise it, to remove the small variations in order to keep only what is persistent, and so it's still simplices, complex.
38:23
Okay, so in this case, now, we define an elementary k-chain in this way, and, of course, we have two different orientations, which are here represented by the sign plus or minus, and this is a k-chain,
38:43
so in the case of persistent homology, what is used is essentially a coefficient in z, but it can be an abelian group, and, yeah, and then, so we define the boundary operator in this way, so now, of course, we are in the reverse direction compared to cohomology,
39:06
so we go from k to k-1, and the same way as for cohomology, so we have the k-th homology group now, which is the quotient group of the kernel, so the cycles by the boundaries,
39:22
and we have also Betti numbers, which are useful in persistent homology, which are defined as being the rank of these homology groups. Okay, so now, coming from there, what is persistent homology? So, suppose we have a cloud of points
39:41
in a space, all right, and in our case, it will be the measurements that we will do, and from there, we need to find structures, we need to remove noise, we need to remove the small variations, the clutters, etc., and we need to find some structure inside this cloud of points, okay? So, how to do it? So, what would be theoretically
40:03
the most acceptable would be to build a church complex in this way, so you draw some balls around, of given radius around the points, and then you form a simplex S, if there is at least
40:22
one common point in each ball of S, all right? The problem is that computationally, it's very hard, I mean, it's something for which it will be hard to compute the homology groups. So, instead of this, what we do in practice is rather to consider the Rips complexes,
40:41
and in this case, we will form a simplex if there is at least one common point in the balls, which are considered now pairwise, okay? So, for example, this one is a two simplex for the Rips topology, but not for the church one, okay? So, and then we considered
41:02
a nested sequence of topological spaces, x0, x1, etc., and this is done just by considering, in our case, varying radiuses, radii from the smallest one to the biggest one,
41:20
and in this case, we need for, sorry, we obtain for each of them homology groups, okay? And then, in fact, what happens is that we want to identify when a homology class is born and when it dies, all right? And so, in this case, for example,
41:48
this one is born here and dies here, okay? And the birth and death of the homology classes will be very important because with this, we can construct barcodes and, sorry, barcodes,
42:07
and in this case, long bars will have a long life and will mean that long bars will be the persistent features, all right? So, for example, if we use the Rips complex,
42:21
so this is our cloud of points, you see they are more or less in a torus, I mean on the torus or donut, and when, so this is the complexes we obtain when the radius increases, okay? And for the same thing, these are the barcodes, so these are the, so on the x-axis,
42:49
you have, it's parametrized by epsilon, so this is the homology groups H0, H1 and H2. As you can see, this one is persistent, this one is persistent, yeah? And so, sorry?
43:08
How long does it have to be? This, I don't know exactly, excellent question, but it depends probably on the application that, yeah, because it depends mainly on the application, yeah. Okay, and I found
43:29
something related to the topos of persistence and that means that, in fact, it's a kind of generalization of the topos of sets in which instead of having just sets, we have sets indexed
43:45
by time, yeah? So, these are given by these barcodes that I have shown to you and it corresponds to time-index sets and on these time-index sets, in fact, we can construct a
44:02
persistence-heighting algebra of intervals ordered by inclusions and the sheaves of this algebra P encode barcodes, all right? And, sorry, this is a very simple example. For example here,
44:20
so at time zero, so these zero correspond to the time and this one to the dimension of the terminology. So here, for example, in this case, as you can see, h0 of zero is essentially, I mean, xy quotient by zero, so it is asomorphic to z plus z and h1 of zero is
44:44
just zero because you have only two vertices, so two points. Then at time one, we have this and we can compute h0 of one which is this and, in fact, asomorphic to z and h1 of one can be computed and we can see that it is asomorphic to z as well, etc. We can compute
45:05
the homology group of all these guys and so by doing gluing, in fact, we can glue, we may glue point-wise homology groups together consistently and in order to extract global information,
45:23
so it's, of course, it's a toy example, and the global information is this one. For t, in the interval zero one, we have h0 equals to this, changing to h0 equals to z when t goes from one to five and for the first homology group, we have for t equals one to two,
45:44
we have h1 equals z, changing to h1 equals zero when t is, in fact, the union of these two intervals and so this is a very simple example of one topos which is related to persistent
46:04
homology and which may be useful for us. And that concludes my talk. Thank you very much. So there are some questions.
46:20
I mean, for this last example, does this suggest new algorithms? Not yet. In fact, there are algorithms for computing, of course. Maybe they have to be simplified because in general it's very heavy, but the idea now, for example, there are some ideas now
46:44
of combining persistent homology and, in fact, the topological analysis of data with the neural networks. And for now, I have just seen one paper which is not very, I mean, it's not
47:06
very easy to understand what they are doing, so, and that's it. But this will be next step because apparently using topological data analysis plus machine learning seems to be very efficient.
47:26
Other questions? Do this method give an hint on what you told before that this small dimensional?
47:41
Yeah. Yes, the idea is to try to characterize these manifolds, in fact, thanks to the homology group. Usually it's not really exactly the homology group you come from. Yeah, yeah, yeah, yeah.
48:01
So this is not really cyclic? Yes, yes, yes, yes. You mean one comment? I mean, it was very interesting the fact that, I mean, some people revisit the sampling theorem of Shannon based on topos. My question is that did you see some results on compressed sensing in topos, which could be also linked to the fact
48:25
that maybe you want to, from a couple of samples, try to find a global representation of your information? No, I haven't seen it right now, but I haven't searched really to that direction, so.
48:41
Okay, if there are no other questions, we'll take a 15 minutes break and then we'll have a short discussion, like half an hour. So come back at 4, and we'll move from 4 to 4.30, and we'll speak to you after 5. Thanks.