0:00:13 | um i will play a will explain and the second what a Q as complex as |
---|---|

0:00:17 | uh this is the work of uh |

0:00:19 | my former student a a sundry high low grade it in two thousand ten then he would have laughed to |

0:00:24 | present uh this work but if we can a father last week |

0:00:28 | and uh i let that count as an Q |

0:00:31 | um so it's code advice the by michael a the yeah not much of it sure go from carnegie mellon |

0:00:36 | university and i was was at carnegie mellon and died recently moved to |

0:00:40 | you cage thirty |

0:00:43 | um so the word is a concern with you C G signals |

0:00:48 | so electrocardiogram signals |

0:00:50 | and uh you as an example of a measure D C G signal from some data base |

0:00:55 | oh you see it's a periodic repetition |

0:00:57 | of um |

0:00:59 | of |

0:00:59 | sort of elements that we to each other but with slight variation |

0:01:03 | and so if you take out one period |

0:01:05 | then and text books it's typically described like this so this is it is an idiot idealistic representation of that |

0:01:12 | period |

0:01:13 | and the cardiologist they divide this into into pieces |

0:01:17 | um with you see here is a T are interval and S T interval and in the middle of the |

0:01:22 | one that contains the peak that's stick Q R S and of a Q or as complex |

0:01:27 | for yeah i repeated it and um |

0:01:30 | the middle part that's the your S |

0:01:32 | complex of purist's interval and that's what we are concern |

0:01:36 | and uh |

0:01:37 | here's sort of a an extract version of it because you it's kind of a |

0:01:41 | which so this is roughly how it looks like |

0:01:44 | uh and it turns out to as |

0:01:45 | you know cardiologist tell us this as the uh most important part of this uh of the signal |

0:01:52 | and it's used to the for a variety of purposes and in in diagnosed |

0:01:57 | so |

0:01:58 | so cardiologist look at this part to determine whether to and you problems with a hard read them or two |

0:02:04 | detect certain D Cs |

0:02:07 | a typical duration of that part it's hundred milliseconds or a tenth of a second |

0:02:12 | and um you know you may imagine many C G signals are recorded and their stored in a database and |

0:02:18 | if you have millions of patients so |

0:02:21 | uh a and and and many many seconds stand this amounts to you to amount of data so that's why |

0:02:25 | people have started to study the problem of compressing these Q R S comp |

0:02:29 | because you one store it |

0:02:31 | but you want to reduce the amount of data |

0:02:33 | that it takes |

0:02:34 | so of course when you start compressing it you introduce an arrow and you don't want T error to be |

0:02:38 | so large that the diagnostics doesn't work in |

0:02:41 | so all goal is |

0:02:42 | is an essence since to |

0:02:44 | what we what we have in doing is present a method to |

0:02:47 | to compress |

0:02:48 | the |

0:02:48 | Q are as complex |

0:02:50 | while maintaining sufficient quality |

0:02:53 | that's and prior work on this problem because it's so it's relevant and that there was some early work by |

0:02:59 | certain more and others |

0:03:01 | from at one |

0:03:02 | and take compressed to Q are as complex by extracting certain feature |

0:03:07 | that they did reduce the dimensionality |

0:03:09 | uh a late later this work was subsumed by by this is uh a line of work |

0:03:14 | which uh which used or her meat functions to to describe these Q S comp |

0:03:20 | in essence taking that |

0:03:21 | part of the uh |

0:03:23 | taking the cure as complex and expanding it as a linear combination of a mute function |

0:03:27 | and the reason why i meet function came into play was not some |

0:03:30 | the mathematical theory that says a limited functions adjust the functions you want to use here |

0:03:35 | it was just because of the |

0:03:37 | similarity in shape it's just the timit function somehow have system looks similar |

0:03:42 | then together as a cue or as complex and that's why people started doing |

0:03:47 | our approach also is continuous this line of work and um meaning we take that you are as complex and |

0:03:53 | we |

0:03:54 | we expanded into a basis of discrete met function |

0:03:58 | and that this is a somewhat different than the prior work and and i weeks i will explain how |

0:04:04 | the first some background whatever you'd function is to understand to meet function we first have to look at the |

0:04:09 | close "'cause" in the army polynomial |

0:04:12 | i mean polynomials is a is a sequence of polynomials there's one for every degree |

0:04:17 | so the first ones are |

0:04:19 | one and Z uh so here you see for degree zero it's one and then four minus one it's two |

0:04:24 | at zero |

0:04:25 | and then you have a two term occur |

0:04:27 | and that because if defines in um |

0:04:29 | H L S degree at it's easy to see that |

0:04:33 | um and uh |

0:04:34 | because it's a two term occurrence that's a theory that says this put enormous all of can no with respect |

0:04:39 | to some weight function |

0:04:41 | if you take out this weight functions so you divided of |

0:04:44 | you get functions that are |

0:04:46 | truly orthogonal |

0:04:48 | without any weight function and these other of meat function |

0:04:50 | and don't you see that |

0:04:52 | the meat functions it's are in essence the polynomial |

0:04:55 | but no you have to store in front of it and you see there's to E to the minus least |

0:04:59 | square |

0:05:00 | and that just usually make sure that these functions tk very quickly as you go to infinity |

0:05:05 | and so are just a few examples of the first three or meet functions |

0:05:09 | and uh and you see that uh |

0:05:11 | that they have a support that this the entire realign but they D K very quickly because of the each |

0:05:16 | of the minus T square |

0:05:18 | and he you see a little bit you know that |

0:05:20 | good argue some similarity to Q R S K |

0:05:23 | that's why people start |

0:05:25 | and so just the orthogonality condition there exactly orthogonal on the real line |

0:05:30 | but because they D K so quickly you can an essence assigned to them |

0:05:34 | an interval of support and say the orthogonal and that interval approximate just because they are very close to zero |

0:05:40 | outside |

0:05:41 | new see there's also does magic factor uh my trigger parameters mar |

0:05:45 | and that's just stretch as |

0:05:47 | allows you to stretch these functions and that maintains the of net |

0:05:53 | so |

0:05:54 | so the previous work used is for me functions to to express these Q as complex as because of hour |

0:06:00 | that before it was because of visual similarity and the other worked as follows |

0:06:04 | you have a cure or as complex |

0:06:06 | so that one has a certain supports so first you stretch their meet functions to have the same support |

0:06:13 | then you pick the first i don't know however many you one fifteen seventeen a meet functions and you project |

0:06:19 | you Q as complex on to them by just computing the scalar product because they also but now |

0:06:24 | so compute D seattle L coefficients and the more of those you have the better you represent present you see |

0:06:29 | that's the idea |

0:06:31 | and then you keep the first so many |

0:06:33 | fifty |

0:06:34 | that's a use stop somewhere because you don't want to a and seen it many |

0:06:38 | and that's what used store |

0:06:39 | and then if you want to reconstruct you take these fifteen coefficients out of your data base and he the |

0:06:44 | reconstruction for |

0:06:46 | and you get an approximation of the original |

0:06:48 | so that was the approach take |

0:06:50 | now there a problem if you want to implement this yeah this stage you have to compute these integrals and |

0:06:55 | in the computer you cannot do that right you have to is tie some so they went on and discrete |

0:06:59 | times that |

0:07:00 | and if you discrete ties an integral |

0:07:02 | you use a credit sure rule |

0:07:04 | and the at it picked the standard one out of a book |

0:07:07 | and that this as the credits so the whole than an essence what you do is |

0:07:10 | you um |

0:07:12 | you sample at you a function at certain point |

0:07:15 | then you multiply by the length of interval |

0:07:17 | or to see that the usually |

0:07:19 | you have the interval of support |

0:07:22 | and i normalized for minus one to one |

0:07:24 | you divided in this case into a touch of seven just randomly |

0:07:29 | in to seven inch of and now you have to pick one |

0:07:31 | sampling |

0:07:32 | location in each of these intervals and what they did naturally actually the chose an actually actually spaced sampling because |

0:07:38 | it just a natural thing to |

0:07:41 | and then an that since this is the computation you perform you have your samples |

0:07:44 | at exactly space point |

0:07:46 | and then you have this |

0:07:48 | mar you multi but this transform matrix and you C these other meat |

0:07:52 | polynomials evaluated at actually distant point |

0:07:54 | and if you want to reconstruct a and you get the code fish |

0:07:57 | and if you want to reconstruct a |

0:07:59 | you uh you have to use the inverse trend |

0:08:04 | that's fine but there were a a a a few problems with the approach the first is this transform is |

0:08:09 | not orthogonal |

0:08:11 | um and typically be like to have orthogonal transforms for for a variety of three |

0:08:16 | signal processing |

0:08:17 | and then for this kind of transform there that that is not really a very efficient al |

0:08:22 | in other words it's a kind of really comes and |

0:08:25 | you have to do it by definition and that can be very expense |

0:08:29 | so so we built on this approach but |

0:08:32 | but uh changed something namely we change the uh the sampling points because |

0:08:37 | this theory of orthogonal polynomial |

0:08:40 | suggests jess explains that if you sample the actress space are not the natural sampling |

0:08:46 | but in fact |

0:08:47 | uh the sampling points are the remote |

0:08:50 | the proper sampling points should be the roots of of of the and i meet me norm and so i |

0:08:55 | in our case seven |

0:08:57 | uh a here again for price of seven you divide them to seven sub intervals you do not want to |

0:09:02 | sample at these is space points but you want to pick the seventh for me polynomial |

0:09:06 | pick its zeros |

0:09:08 | and these are sort of mathematically than natural sampling |

0:09:12 | and that's why be that interested to see whether these are the actual sampling points so the big you can |

0:09:16 | also get better result |

0:09:18 | and so you see this is here you see it not to space |

0:09:22 | and now you have a slightly different version of transform and reconstruction of the transform yeah the sampling points to |

0:09:28 | are not decrease space |

0:09:30 | and all the transform looks like this and these are the in essence the zeros of the of the and |

0:09:34 | t-norm polynomial |

0:09:35 | and the theory of uh are me in most tells us now that this transform some orthogonal so it you |

0:09:40 | want to reconstruct you can do would with the |

0:09:42 | with the trends |

0:09:44 | what's orthogonal |

0:09:45 | and um |

0:09:47 | um |

0:09:47 | and and just the second part is that actually it's non that for these transforms you have fast out |

0:09:55 | so to test |

0:09:56 | uh |

0:09:57 | to to test this approach to the uh uh uh for the icassp paper to time presenting here we took |

0:10:02 | uh we took a |

0:10:04 | right now a relatively small experiment taking twenty nine Q or as complex of from three different uh uh is |

0:10:10 | C G signal |

0:10:12 | an be compared to a be computed the compression ability |

0:10:15 | and we compared to the previous |

0:10:17 | or meet |

0:10:18 | approach |

0:10:18 | and then we through and also the dft and D T just a |

0:10:23 | yeah because these are the more natural candy that's when you can |

0:10:25 | so in essence dct based compression just like an image process |

0:10:28 | a do a dct transform to keep only the first five or six |

0:10:32 | but visions |

0:10:33 | and that that we tried that also |

0:10:36 | and and here the results |

0:10:38 | um and on the x-axis you C |

0:10:41 | how many coefficients we cap |

0:10:43 | and because once your as complex has twenty seven samples and this particular example of a few people all the |

0:10:49 | if you do a transform and then you keep all the twenty seven coefficient |

0:10:52 | you get perfect reconstruction euro error |

0:10:55 | on the Y is the arrow |

0:10:57 | and the fewer coefficients you keep the large as the error match |

0:11:01 | a now you get these are rate of fronts uh sort of these curve |

0:11:04 | and then depending on the area you can choose how many coefficients you key |

0:11:08 | and every line of the different algorithm and and our new one is the red one |

0:11:12 | not the question is what arrow can you tolerate |

0:11:14 | and i and after the icassp paper we started talking to a cardiologist and we had to a cardiologist go |

0:11:20 | a reconstructed signals |

0:11:21 | and then since the result was that ten percent is good |

0:11:25 | and more is not good |

0:11:26 | so in since you wanna cut here |

0:11:28 | and then you see that for ten percent year |

0:11:31 | the red one is a bit better than the previous one so if you if you quantify that |

0:11:35 | it's again about fifteen twenty percent and the compression ratio that achieve as a factor of five |

0:11:41 | so used store you transform and because to store only like five coefficients |

0:11:45 | before you had twenty seven of sec |

0:11:49 | and uh just a visual confirmation that ten percent |

0:11:51 | is reasonable and twenty percent not |

0:11:54 | so the black |

0:11:55 | line is a a is the a your as complex |

0:11:58 | as a obtained uh as in the database |

0:12:01 | and the the red one is the reconstructed one ten percent error uh and a twenty one of the blue |

0:12:06 | one is with twenty percent |

0:12:07 | you see the blue one is already quite |

0:12:09 | different |

0:12:10 | but really the gold standard is not |

0:12:12 | a a picture like this but what are we real |

0:12:14 | a practitioner say |

0:12:17 | so uh |

0:12:18 | after the get but we continued with the larger experiment where one a brief you show the results because twenty |

0:12:23 | nine or as complex as a |

0:12:25 | relatively small sample so |

0:12:27 | we went into the timit database and B now hundred sixty eight leads so hundred sixty at C E chick |

0:12:33 | uh is C G signals |

0:12:35 | and we two coats five fifteen a hundred of these company |

0:12:38 | and then we also compared to the to the wavelet transform because that's also a natural candidate for |

0:12:44 | for compression |

0:12:46 | um and you the results |

0:12:48 | and you see that uh |

0:12:50 | we have here different arrows |

0:12:52 | because we are a established that more than ten percent is not really acceptable you only need really to look |

0:12:57 | at ten percent error |

0:12:59 | and uh you see here the new algorithm which is a a a minor |

0:13:04 | only a minor modification of the of the one from from this icassp paper since the same one |

0:13:09 | this is the previous one dft based dct based and dwt bay |

0:13:14 | and uh you see always two numbers |

0:13:17 | so the first number is the compression racial by what's factor could you compress the data |

0:13:22 | and you see that all and of large scale experiment we get about a factor of five |

0:13:28 | oh that stuff the |

0:13:30 | a the full to reduction of the amount of data |

0:13:33 | and the the previous algorithm actually on that's larger or uh dataset of worse than on that smaller ones of |

0:13:39 | the smaller one was apparently nice for this previous gore |

0:13:42 | for now here the compression ratio is only three point five |

0:13:46 | so that sort of an improvement of uh |

0:13:48 | fifty percent |

0:13:50 | um and it turns out actually that the dft D T and D W |

0:13:54 | dwt T |

0:13:55 | a a compression to also reasonable candy that |

0:13:58 | uh actually some perform better than their meat based one |

0:14:01 | but the or like in the range around for |

0:14:03 | oh here |

0:14:05 | so |

0:14:07 | yes we |

0:14:07 | we better and you what you've seen the parent as this |

0:14:10 | is how many coefficients you need to keep |

0:14:12 | oh |

0:14:13 | you have a a high compression ratio you only need to keep few |

0:14:16 | coefficients efficient if you have a low one you need to keep more |

0:14:22 | or the method seems to to work |

0:14:27 | okay so my conclusion um i i i the method |

0:14:31 | for the compression of cure S complex as |

0:14:33 | using discrete ties to meet function |

0:14:36 | and it's really a could argue only a small sort of incremental step from the prior work which already used |

0:14:42 | continuous or meat function then using the quadrature rule |

0:14:45 | um but what's really interesting here arguably is that |

0:14:49 | that non could distance sampling performs better than a distance a |

0:14:53 | that's kind of nice because |

0:14:55 | the mathematics of these or meet functions suggests these as natural sampling points |

0:15:00 | i i this functions just have those points as an actual sampling |

0:15:03 | that's actually the reason why we studied the problem because we started actually |

0:15:08 | um |

0:15:08 | see approach to signal processing based on orthogonal polynomials and then we were looking for application and this is one |

0:15:14 | of the applications we found |

0:15:16 | but interesting thing is really that non equidistant sampling you can make say |

0:15:21 | or if you another what's if you deploy it this into real but application maybe be would immediately sampled those |

0:15:26 | C C G signals at those points |

0:15:28 | rather than actually distantly as it's of course done right now and |

0:15:32 | a so we need to actually to interpolate |

0:15:35 | to find the value |

0:15:36 | at these uh |

0:15:37 | these other |

0:15:39 | and uh and compared to the previous methods that's and also to compare to reasonable uh candy that's based on |

0:15:44 | wavelets some cosine transform |

0:15:47 | we achieve a a compression improve compression rates of like twenty to forty percent on no |

0:15:51 | about |

0:15:54 | a some obvious future works one can do and some of these things we already uh where we have been |

0:15:58 | doing in the last three like |

0:16:00 | you know better adjusting those to stretch factor because they you can still do some of fine tuning |

0:16:06 | um |

0:16:07 | there's the question of efficient implementations and be also that some results on having |

0:16:11 | a fast |

0:16:12 | a faster out with for this from me try |

0:16:16 | then of course the question is |

0:16:17 | can you use a similar approach to to other to the other segments of these C G or not to |

0:16:22 | Q as complex but but the other |

0:16:26 | and that concludes my talk thank you very much |

0:16:39 | which work |

0:16:45 | yeah |

0:16:46 | how we choose to segment is that um in sense if you look at the support of the Q or |

0:16:51 | as complex so this my depends on the support of related to the support |

0:16:55 | and so what i say did he looked at the uh interval of support of the cure as signal |

0:17:00 | and that narrows down the choices of sigma very much to like a small interval |

0:17:04 | and then in there you just does a little bit of trial and error |

0:17:08 | and uh because typically only need to do that once for a neat |

0:17:12 | and then you can keep the same signal for your entire lead of Q as complex it's which means you |

0:17:17 | you can actually invest computation time to really fine tune it uh you will not and of i |

0:17:23 | oh so no not a terribly sophisticated approach but the let's say works in correct |

0:17:30 | oh |

0:17:30 | exactly yeah oh what in um |

0:17:33 | uh we do but i mean you get those in from the hard be functions or |

0:17:38 | um always always the non-uniform sampling i mean what are do something instants the sampling points if you want um |

0:17:44 | if you um |

0:17:46 | that's a stick you are as complex has twenty seven samples |

0:17:51 | and uh that so in the beginning you would assume then you take the first twenty seven how me polynomials |

0:17:56 | uh meaning from to be put in a meat functions from number zero to number twenty six |

0:18:02 | and the sampling points are |

0:18:04 | the zeros of the twenty seven |

0:18:06 | one |

0:18:08 | okay and that seems like a we at random choice but if you study mathematical books on orthogonal polynomials |

0:18:14 | then they explain to use that if you choose to this is a general thing more for form of is |

0:18:18 | that if you choose if you use this approach to choosing the sampling points |

0:18:22 | the trends some will become orthogonal |

0:18:25 | okay that doesn't necessarily say that it would |

0:18:27 | perform better for compression but it turned out that actually it it |

0:18:31 | but that that's the |

0:18:38 | oh |

0:18:39 | hmmm |

0:18:47 | yeah |

0:18:49 | the |

0:18:50 | yeah |

0:18:56 | we have no no no |

0:18:58 | oh no insight here |

0:19:00 | it's really i think that is something that you can only find out a group |

0:19:04 | course |

0:19:05 | but Q as complex clearly has a particular shape |

0:19:08 | and the question as the basis function that correspond to this |

0:19:11 | but the different forms |

0:19:14 | which can approximate shape better |

0:19:17 | and and uh |

0:19:20 | yeah no no in so there's not nice biological a model |

0:19:23 | of the heart let's say that would explain to you |

0:19:27 | why what function of the natural one so we have absolutely no inside it's some period |

0:19:31 | in fact it was a surprise to us that |

0:19:33 | and many cases to just using the dct was better than the previous method on a meat functions and that |

0:19:38 | maybe the authors didn't |

0:19:40 | try |

0:19:44 | no problem |

0:19:45 | interesting so |