0:00:13um i will play a will explain and the second what a Q as complex as
0:00:17uh this is the work of uh
0:00:19my former student a a sundry high low grade it in two thousand ten then he would have laughed to
0:00:24present uh this work but if we can a father last week
0:00:28and uh i let that count as an Q
0:00:31um so it's code advice the by michael a the yeah not much of it sure go from carnegie mellon
0:00:36university and i was was at carnegie mellon and died recently moved to
0:00:40you cage thirty
0:00:43um so the word is a concern with you C G signals
0:00:48so electrocardiogram signals
0:00:50and uh you as an example of a measure D C G signal from some data base
0:00:55oh you see it's a periodic repetition
0:00:57of um
0:00:59of
0:00:59sort of elements that we to each other but with slight variation
0:01:03and so if you take out one period
0:01:05then and text books it's typically described like this so this is it is an idiot idealistic representation of that
0:01:12period
0:01:13and the cardiologist they divide this into into pieces
0:01:17um with you see here is a T are interval and S T interval and in the middle of the
0:01:22one that contains the peak that's stick Q R S and of a Q or as complex
0:01:27for yeah i repeated it and um
0:01:30the middle part that's the your S
0:01:32complex of purist's interval and that's what we are concern
0:01:36and uh
0:01:37here's sort of a an extract version of it because you it's kind of a
0:01:41which so this is roughly how it looks like
0:01:44uh and it turns out to as
0:01:45you know cardiologist tell us this as the uh most important part of this uh of the signal
0:01:52and it's used to the for a variety of purposes and in in diagnosed
0:01:57so
0:01:58so cardiologist look at this part to determine whether to and you problems with a hard read them or two
0:02:04detect certain D Cs
0:02:07a typical duration of that part it's hundred milliseconds or a tenth of a second
0:02:12and um you know you may imagine many C G signals are recorded and their stored in a database and
0:02:18if you have millions of patients so
0:02:21uh a and and and many many seconds stand this amounts to you to amount of data so that's why
0:02:25people have started to study the problem of compressing these Q R S comp
0:02:29because you one store it
0:02:31but you want to reduce the amount of data
0:02:33that it takes
0:02:34so of course when you start compressing it you introduce an arrow and you don't want T error to be
0:02:38so large that the diagnostics doesn't work in
0:02:41so all goal is
0:02:42is an essence since to
0:02:44what we what we have in doing is present a method to
0:02:47to compress
0:02:48the
0:02:48Q are as complex
0:02:50while maintaining sufficient quality
0:02:53that's and prior work on this problem because it's so it's relevant and that there was some early work by
0:02:59certain more and others
0:03:01from at one
0:03:02and take compressed to Q are as complex by extracting certain feature
0:03:07that they did reduce the dimensionality
0:03:09uh a late later this work was subsumed by by this is uh a line of work
0:03:14which uh which used or her meat functions to to describe these Q S comp
0:03:20in essence taking that
0:03:21part of the uh
0:03:23taking the cure as complex and expanding it as a linear combination of a mute function
0:03:27and the reason why i meet function came into play was not some
0:03:30the mathematical theory that says a limited functions adjust the functions you want to use here
0:03:35it was just because of the
0:03:37similarity in shape it's just the timit function somehow have system looks similar
0:03:42then together as a cue or as complex and that's why people started doing
0:03:47our approach also is continuous this line of work and um meaning we take that you are as complex and
0:03:53we
0:03:54we expanded into a basis of discrete met function
0:03:58and that this is a somewhat different than the prior work and and i weeks i will explain how
0:04:04the first some background whatever you'd function is to understand to meet function we first have to look at the
0:04:09close "'cause" in the army polynomial
0:04:12i mean polynomials is a is a sequence of polynomials there's one for every degree
0:04:17so the first ones are
0:04:19one and Z uh so here you see for degree zero it's one and then four minus one it's two
0:04:24at zero
0:04:25and then you have a two term occur
0:04:27and that because if defines in um
0:04:29H L S degree at it's easy to see that
0:04:33um and uh
0:04:34because it's a two term occurrence that's a theory that says this put enormous all of can no with respect
0:04:39to some weight function
0:04:41if you take out this weight functions so you divided of
0:04:44you get functions that are
0:04:46truly orthogonal
0:04:48without any weight function and these other of meat function
0:04:50and don't you see that
0:04:52the meat functions it's are in essence the polynomial
0:04:55but no you have to store in front of it and you see there's to E to the minus least
0:04:59square
0:05:00and that just usually make sure that these functions tk very quickly as you go to infinity
0:05:05and so are just a few examples of the first three or meet functions
0:05:09and uh and you see that uh
0:05:11that they have a support that this the entire realign but they D K very quickly because of the each
0:05:16of the minus T square
0:05:18and he you see a little bit you know that
0:05:20good argue some similarity to Q R S K
0:05:23that's why people start
0:05:25and so just the orthogonality condition there exactly orthogonal on the real line
0:05:30but because they D K so quickly you can an essence assigned to them
0:05:34an interval of support and say the orthogonal and that interval approximate just because they are very close to zero
0:05:40outside
0:05:41new see there's also does magic factor uh my trigger parameters mar
0:05:45and that's just stretch as
0:05:47allows you to stretch these functions and that maintains the of net
0:05:53so
0:05:54so the previous work used is for me functions to to express these Q as complex as because of hour
0:06:00that before it was because of visual similarity and the other worked as follows
0:06:04you have a cure or as complex
0:06:06so that one has a certain supports so first you stretch their meet functions to have the same support
0:06:13then you pick the first i don't know however many you one fifteen seventeen a meet functions and you project
0:06:19you Q as complex on to them by just computing the scalar product because they also but now
0:06:24so compute D seattle L coefficients and the more of those you have the better you represent present you see
0:06:29that's the idea
0:06:31and then you keep the first so many
0:06:33fifty
0:06:34that's a use stop somewhere because you don't want to a and seen it many
0:06:38and that's what used store
0:06:39and then if you want to reconstruct you take these fifteen coefficients out of your data base and he the
0:06:44reconstruction for
0:06:46and you get an approximation of the original
0:06:48so that was the approach take
0:06:50now there a problem if you want to implement this yeah this stage you have to compute these integrals and
0:06:55in the computer you cannot do that right you have to is tie some so they went on and discrete
0:06:59times that
0:07:00and if you discrete ties an integral
0:07:02you use a credit sure rule
0:07:04and the at it picked the standard one out of a book
0:07:07and that this as the credits so the whole than an essence what you do is
0:07:10you um
0:07:12you sample at you a function at certain point
0:07:15then you multiply by the length of interval
0:07:17or to see that the usually
0:07:19you have the interval of support
0:07:22and i normalized for minus one to one
0:07:24you divided in this case into a touch of seven just randomly
0:07:29in to seven inch of and now you have to pick one
0:07:31sampling
0:07:32location in each of these intervals and what they did naturally actually the chose an actually actually spaced sampling because
0:07:38it just a natural thing to
0:07:41and then an that since this is the computation you perform you have your samples
0:07:44at exactly space point
0:07:46and then you have this
0:07:48mar you multi but this transform matrix and you C these other meat
0:07:52polynomials evaluated at actually distant point
0:07:54and if you want to reconstruct a and you get the code fish
0:07:57and if you want to reconstruct a
0:07:59you uh you have to use the inverse trend
0:08:04that's fine but there were a a a a few problems with the approach the first is this transform is
0:08:09not orthogonal
0:08:11um and typically be like to have orthogonal transforms for for a variety of three
0:08:16signal processing
0:08:17and then for this kind of transform there that that is not really a very efficient al
0:08:22in other words it's a kind of really comes and
0:08:25you have to do it by definition and that can be very expense
0:08:29so so we built on this approach but
0:08:32but uh changed something namely we change the uh the sampling points because
0:08:37this theory of orthogonal polynomial
0:08:40suggests jess explains that if you sample the actress space are not the natural sampling
0:08:46but in fact
0:08:47uh the sampling points are the remote
0:08:50the proper sampling points should be the roots of of of the and i meet me norm and so i
0:08:55in our case seven
0:08:57uh a here again for price of seven you divide them to seven sub intervals you do not want to
0:09:02sample at these is space points but you want to pick the seventh for me polynomial
0:09:06pick its zeros
0:09:08and these are sort of mathematically than natural sampling
0:09:12and that's why be that interested to see whether these are the actual sampling points so the big you can
0:09:16also get better result
0:09:18and so you see this is here you see it not to space
0:09:22and now you have a slightly different version of transform and reconstruction of the transform yeah the sampling points to
0:09:28are not decrease space
0:09:30and all the transform looks like this and these are the in essence the zeros of the of the and
0:09:34t-norm polynomial
0:09:35and the theory of uh are me in most tells us now that this transform some orthogonal so it you
0:09:40want to reconstruct you can do would with the
0:09:42with the trends
0:09:44what's orthogonal
0:09:45and um
0:09:47um
0:09:47and and just the second part is that actually it's non that for these transforms you have fast out
0:09:55so to test
0:09:56uh
0:09:57to to test this approach to the uh uh uh for the icassp paper to time presenting here we took
0:10:02uh we took a
0:10:04right now a relatively small experiment taking twenty nine Q or as complex of from three different uh uh is
0:10:10C G signal
0:10:12an be compared to a be computed the compression ability
0:10:15and we compared to the previous
0:10:17or meet
0:10:18approach
0:10:18and then we through and also the dft and D T just a
0:10:23yeah because these are the more natural candy that's when you can
0:10:25so in essence dct based compression just like an image process
0:10:28a do a dct transform to keep only the first five or six
0:10:32but visions
0:10:33and that that we tried that also
0:10:36and and here the results
0:10:38um and on the x-axis you C
0:10:41how many coefficients we cap
0:10:43and because once your as complex has twenty seven samples and this particular example of a few people all the
0:10:49if you do a transform and then you keep all the twenty seven coefficient
0:10:52you get perfect reconstruction euro error
0:10:55on the Y is the arrow
0:10:57and the fewer coefficients you keep the large as the error match
0:11:01a now you get these are rate of fronts uh sort of these curve
0:11:04and then depending on the area you can choose how many coefficients you key
0:11:08and every line of the different algorithm and and our new one is the red one
0:11:12not the question is what arrow can you tolerate
0:11:14and i and after the icassp paper we started talking to a cardiologist and we had to a cardiologist go
0:11:20a reconstructed signals
0:11:21and then since the result was that ten percent is good
0:11:25and more is not good
0:11:26so in since you wanna cut here
0:11:28and then you see that for ten percent year
0:11:31the red one is a bit better than the previous one so if you if you quantify that
0:11:35it's again about fifteen twenty percent and the compression ratio that achieve as a factor of five
0:11:41so used store you transform and because to store only like five coefficients
0:11:45before you had twenty seven of sec
0:11:49and uh just a visual confirmation that ten percent
0:11:51is reasonable and twenty percent not
0:11:54so the black
0:11:55line is a a is the a your as complex
0:11:58as a obtained uh as in the database
0:12:01and the the red one is the reconstructed one ten percent error uh and a twenty one of the blue
0:12:06one is with twenty percent
0:12:07you see the blue one is already quite
0:12:09different
0:12:10but really the gold standard is not
0:12:12a a picture like this but what are we real
0:12:14a practitioner say
0:12:17so uh
0:12:18after the get but we continued with the larger experiment where one a brief you show the results because twenty
0:12:23nine or as complex as a
0:12:25relatively small sample so
0:12:27we went into the timit database and B now hundred sixty eight leads so hundred sixty at C E chick
0:12:33uh is C G signals
0:12:35and we two coats five fifteen a hundred of these company
0:12:38and then we also compared to the to the wavelet transform because that's also a natural candidate for
0:12:44for compression
0:12:46um and you the results
0:12:48and you see that uh
0:12:50we have here different arrows
0:12:52because we are a established that more than ten percent is not really acceptable you only need really to look
0:12:57at ten percent error
0:12:59and uh you see here the new algorithm which is a a a minor
0:13:04only a minor modification of the of the one from from this icassp paper since the same one
0:13:09this is the previous one dft based dct based and dwt bay
0:13:14and uh you see always two numbers
0:13:17so the first number is the compression racial by what's factor could you compress the data
0:13:22and you see that all and of large scale experiment we get about a factor of five
0:13:28oh that stuff the
0:13:30a the full to reduction of the amount of data
0:13:33and the the previous algorithm actually on that's larger or uh dataset of worse than on that smaller ones of
0:13:39the smaller one was apparently nice for this previous gore
0:13:42for now here the compression ratio is only three point five
0:13:46so that sort of an improvement of uh
0:13:48fifty percent
0:13:50um and it turns out actually that the dft D T and D W
0:13:54dwt T
0:13:55a a compression to also reasonable candy that
0:13:58uh actually some perform better than their meat based one
0:14:01but the or like in the range around for
0:14:03oh here
0:14:05so
0:14:07yes we
0:14:07we better and you what you've seen the parent as this
0:14:10is how many coefficients you need to keep
0:14:12oh
0:14:13you have a a high compression ratio you only need to keep few
0:14:16coefficients efficient if you have a low one you need to keep more
0:14:22or the method seems to to work
0:14:27okay so my conclusion um i i i the method
0:14:31for the compression of cure S complex as
0:14:33using discrete ties to meet function
0:14:36and it's really a could argue only a small sort of incremental step from the prior work which already used
0:14:42continuous or meat function then using the quadrature rule
0:14:45um but what's really interesting here arguably is that
0:14:49that non could distance sampling performs better than a distance a
0:14:53that's kind of nice because
0:14:55the mathematics of these or meet functions suggests these as natural sampling points
0:15:00i i this functions just have those points as an actual sampling
0:15:03that's actually the reason why we studied the problem because we started actually
0:15:08um
0:15:08see approach to signal processing based on orthogonal polynomials and then we were looking for application and this is one
0:15:14of the applications we found
0:15:16but interesting thing is really that non equidistant sampling you can make say
0:15:21or if you another what's if you deploy it this into real but application maybe be would immediately sampled those
0:15:26C C G signals at those points
0:15:28rather than actually distantly as it's of course done right now and
0:15:32a so we need to actually to interpolate
0:15:35to find the value
0:15:36at these uh
0:15:37these other
0:15:39and uh and compared to the previous methods that's and also to compare to reasonable uh candy that's based on
0:15:44wavelets some cosine transform
0:15:47we achieve a a compression improve compression rates of like twenty to forty percent on no
0:15:51about
0:15:54a some obvious future works one can do and some of these things we already uh where we have been
0:15:58doing in the last three like
0:16:00you know better adjusting those to stretch factor because they you can still do some of fine tuning
0:16:06um
0:16:07there's the question of efficient implementations and be also that some results on having
0:16:11a fast
0:16:12a faster out with for this from me try
0:16:16then of course the question is
0:16:17can you use a similar approach to to other to the other segments of these C G or not to
0:16:22Q as complex but but the other
0:16:26and that concludes my talk thank you very much
0:16:39which work
0:16:45yeah
0:16:46how we choose to segment is that um in sense if you look at the support of the Q or
0:16:51as complex so this my depends on the support of related to the support
0:16:55and so what i say did he looked at the uh interval of support of the cure as signal
0:17:00and that narrows down the choices of sigma very much to like a small interval
0:17:04and then in there you just does a little bit of trial and error
0:17:08and uh because typically only need to do that once for a neat
0:17:12and then you can keep the same signal for your entire lead of Q as complex it's which means you
0:17:17you can actually invest computation time to really fine tune it uh you will not and of i
0:17:23oh so no not a terribly sophisticated approach but the let's say works in correct
0:17:30oh
0:17:30exactly yeah oh what in um
0:17:33uh we do but i mean you get those in from the hard be functions or
0:17:38um always always the non-uniform sampling i mean what are do something instants the sampling points if you want um
0:17:44if you um
0:17:46that's a stick you are as complex has twenty seven samples
0:17:51and uh that so in the beginning you would assume then you take the first twenty seven how me polynomials
0:17:56uh meaning from to be put in a meat functions from number zero to number twenty six
0:18:02and the sampling points are
0:18:04the zeros of the twenty seven
0:18:06one
0:18:08okay and that seems like a we at random choice but if you study mathematical books on orthogonal polynomials
0:18:14then they explain to use that if you choose to this is a general thing more for form of is
0:18:18that if you choose if you use this approach to choosing the sampling points
0:18:22the trends some will become orthogonal
0:18:25okay that doesn't necessarily say that it would
0:18:27perform better for compression but it turned out that actually it it
0:18:31but that that's the
0:18:38oh
0:18:39hmmm
0:18:47yeah
0:18:49the
0:18:50yeah
0:18:56we have no no no
0:18:58oh no insight here
0:19:00it's really i think that is something that you can only find out a group
0:19:04course
0:19:05but Q as complex clearly has a particular shape
0:19:08and the question as the basis function that correspond to this
0:19:11but the different forms
0:19:14which can approximate shape better
0:19:17and and uh
0:19:20yeah no no in so there's not nice biological a model
0:19:23of the heart let's say that would explain to you
0:19:27why what function of the natural one so we have absolutely no inside it's some period
0:19:31in fact it was a surprise to us that
0:19:33and many cases to just using the dct was better than the previous method on a meat functions and that
0:19:38maybe the authors didn't
0:19:40try
0:19:44no problem
0:19:45interesting so