Merken

# Projections, Learning, and Sparsity for Efficient Data Processing

#### Automatisierte Medienanalyse

## Diese automatischen Videoanalysen setzt das TIB|AV-Portal ein:

**Szenenerkennung**—

**Shot Boundary Detection**segmentiert das Video anhand von Bildmerkmalen. Ein daraus erzeugtes visuelles Inhaltsverzeichnis gibt einen schnellen Überblick über den Inhalt des Videos und bietet einen zielgenauen Zugriff.

**Texterkennung**–

**Intelligent Character Recognition**erfasst, indexiert und macht geschriebene Sprache (zum Beispiel Text auf Folien) durchsuchbar.

**Spracherkennung**–

**Speech to Text**notiert die gesprochene Sprache im Video in Form eines Transkripts, das durchsuchbar ist.

**Bilderkennung**–

**Visual Concept Detection**indexiert das Bewegtbild mit fachspezifischen und fächerübergreifenden visuellen Konzepten (zum Beispiel Landschaft, Fassadendetail, technische Zeichnung, Computeranimation oder Vorlesung).

**Verschlagwortung**–

**Named Entity Recognition**beschreibt die einzelnen Videosegmente mit semantisch verknüpften Sachbegriffen. Synonyme oder Unterbegriffe von eingegebenen Suchbegriffen können dadurch automatisch mitgesucht werden, was die Treffermenge erweitert.

Erkannte Entitäten

Sprachtranskript

00:02

we the OK so well actually thanks to the organizers for this nation edition and thanks to the European Research Research Council funding the research that's what I'm trying to summarize them in the stalker so I decided to be lazy and uses the title just and they're running of of the project so this is a project and that the where they will be talking about is the result of the collaboration with a number of both the students and their and colleagues and issue center of 2 of those who are doing the main the main work and that they will talk about terms so the on the basic idea that they would like to try to promote here is that they also more fruitful connections between the signal processing emission earning between them all the activity that has been around dementia reduction compressive sensing that could be level raised and maybe with that have not been completely explored in a national for the idea there is that can we develop and Jennifer compressor machine learning reporters and that the ideas from the emission reductions so far has I'm thinking it was a question that there will be more questions than answers but I will provide some case studies on that mainly compressor festering approaches but there were some run for in ideas and Gaussian mixture model estimation there will see that's OK a few things that can be elaboration of results of about Our dimension reduction and information preservation so enough information that the cured guarantees the Ahmed but you will see how we can get so my dear ones like the 1 the Commission on the new that we have to be done and so we have some desk which consists in which more or less at some stage consisting mainly for example homages the parliament for testified about that the centuries of when you Nunavut for conservation but the lives of data and some parameters to to estimated 1 of the main issues being in as whole How will the generalisable will be done about the results of that you get from the Sloan Barnett arose when you get new data with this think distributor the main distribution so here I take your favorite example from March and on and on support and supervise the techniques of PCA crystalline dictionary longing also provides technique for you considering classification I did assaulted 1 classical way of saying it so that I would like to emphasize this is to my user geometric viewpoint and on this type of problems that we consider the date as a cloud of points in high dimensions and so here well the plight of contestants for Germany the task is to influence the structure of the many cases you can use represent as a point of clouds or as a collection of columns from a large matrix and maybe it is important because in many talks with the roles of the matrix of Hiram using columns although ways all I know nobody that I know that I can help this discovered and these will be columns and it would be convenient actually so much more convenient with governments that increased local media but it goes on and like 1 the following day that yeah that's that's the remark was a manipulate actually the that cited it you when you start them mean that led the governed but indirect again so that I was a high-dimensional got 2 sizes too that the high-dimensional that emission of it's gone so the dimension of the future so if you if you data if its colonies and the major signal it can be already millions of patients but more reasonably fit the sift descriptor it's already a few hundred mentions the other dimensions more the volume of the collection of the training collection and so I somehow doubt as to the question they want addressed is how much can we hope to compress this whole collection before we even started performing some so there are different ways of comprising 1 layer and the game well it's opportunities Demitra picture as we have this think about it's columns of the matrix as a high-dimensional vectors lives in the high dimensional vector space but we can use some of our projections of sketching so well Will dimensional projection to market to admission Northern that just yet collections of lower initial vector it's obligations maybe this is not about and this is actually about something that is so that has been used already envisioning the of flora and fauna have been the work of capital market and but in most of the cases this requires some some knowledge model on cover the geometry of your point of flouts attentive points uh that's it has and will dimensional structure

05:49

another issue that so will probably believed that the bank is needed when the really you have loss collections if you have a loss collection reducing the emission of its future victory will have some impact but where can do so there is a new era stronger challenges in the year of last collections to compress and the collection site itself so we can think of to of these collection that is lost .period clout and that's there are a dozen attended way of of trying to reduce the size of a collection which again is related to the talk of the governorship this morning and there somehow the idea of sketching or also assembling and so call sets so that I know very little but I think I'm related to sampling methods were you you find that you there are clever ways of further sampling in your letter collections but that would be relevant to your clear task so this maybe we use whatever skulls there's also of fictional sketching based approaches I'm thinking of the early works of Faber ,comma at with histogram so scared that there can be an adhesive Rentiesville dimension that can be deal with it and it was a fine Admiral beans you can consider them as victories and you can actually sketched them however when you're really high dimension again the fall to even build histogram or you don't even know how to discretized today how you would use critized the call for other approaches but those periods and that sort of thing would be investigating and that we have been investigating is that of sketching with the idea that you start from a collection and you got it actually is collection as are represented here the empirical probability distribution of fuel data and what you will we would like to sketching operator that will start from the collection and build a finite dimensional vectors the sketch the sketch I also will usually be nominee nearing the victors themselves but should be designed so has to some help preserve the information content of your relative to the task but you want to perform so the I'm uh what so that the sketch will be nonlinear that in the future but the idea that we can build a 2 billion during the probability distribution of the debate actually quite the seniority will be what's that makes them with favors a number of fathers was involves problems and Spofford construction so before we go further mistaken an example so here are not yet describing what the nature of the sketch but this is an example of compressive clustering 6 here I just roll a cloud of points so that was drawn from an artificial nature offers for options I guess you see that there forecasters so them to separated but none too mixed to either the and the blue centers are the actual centuries after each of the governance and here we design and not more than that of an approach to step 1st there was sketch we computer 60 dimensional lecture and from this vector only so we completely forgets the rest of the collection from these lectures for that wasn't that inspired by sponsored construction with teammates the such of deductions and here you can see a fairly good match between the estimated centuries and the original so here we go again in the 6th and you can refer to the suspect was special enough exactly so this is an aggregated description of the whole let me maybe contrasts with where they understood from Galveston came down in an annual told the matrix of West sketch was the nearby by multiplying by giving the prediction and hear what the scheduling to build it is not only a projection of the debtor victory it's not an interim protection of the individual that it does not all the rules of the matrices but it's going to be a leader in the probability distribution of the day but may way I should be during a few of the future so what are the potential impacts of the specter of Medford swelled in terms of memory and the local natural resources but if you have an increasing collection sons of a typical methods for clustering means or or in Gaussian mixture models of expectation maximization are alone will have a cost indicated by the end of the picture that brawls with the collection and here with this type of approach as you knew you have to sketch the collection so there's something in there and the collection size that was CDs can be distributed for the civilian OK the scenery the collection site but it's not that constant and there is a fixed costs associated to reconstructed we're learning from your so the collection site is not is relatively small but really wasn't but when you get a large collection size essentially you have a fixed costs for the fun and in terms of sold both in terms of memory and the well-being of the memories even when Akira you have a fixed size sketch so somehow you for getting the collection and you can do it and what you can computers get on and rules so

11:46

yeah but from their respective would you want that the size of this gets through increases in it is possible that so full the moment with elected to make to make things simpler let's think about how you have a given desk you by you have fixed the size of of the script actually it's a life-threatening disease for example was doubling schemes to have a lot to do progressively increase the size of the sky but it is not clear in which scenario which is where it is desirable depending on the trade-off between accuracy and complexity that you may want to reach so let's keep it simple and thinking of it as a fixed size and 1 of the question will be OK what is the order of size of cancer that is is reasonable a game have more questions than answers were I'm free of so just to make it to the media and try to make it clearer what's the by that the sketch itself the idea is to make a body along with this that this genetic picture I had before in signal-processing we're used to thinking about what the object that manipulate are victors in a finite dimensional space sampled signals and images and so we do low-dimensional projections Syrian nationality some holding of on statistics the natural object to manipulate is the distribution of debate and you would like to compute something nearing the distribution of your data that's mattered to find the finite dimensions form which you will gather some relevant information how can you do that well if you have really had the to your distribution you could simply shows that a number of functions in you compute the expectations of functions and you see that the expectation of its function is nearing the underlying the distribution and use can also estimated With finitely many assembled by simply leverage because average do choose all the estimated more busses estimators some of these functions required so this is both these nonlinear individual victims because the 8 stealth functions that future that you will choose here can be no millionaire probably should be nonlinear but this is nearing the distribution and some holders so when we realized recently that this use of this can be interpreted as a fine initial version of the new map embedding so so you take a distribution a new map it's to a Hilbert space here finite dimensions to space where you can measure distances and look at work with many questions at this stage so With these idea for low-key using getting trickier thing in this type of pitching cheated trigger formation only it we can also try to mimic the questions that there have been addressed in the this thing around the notion Well the focus was on eve of problems up here that would be up once you've chosen a sketch a recovering at a distribution from the sketch is the result of method the generalized method of money but probably so that you don't necessarily want to do density estimation so the metric with which you interested in returning work with the reconstruction of fuel density and actually whatever might be related to the desk and beyond that said you have to consider so will still so that's well it's a generalized method of moments but we want to do some dimension reduction so in fact we are and we have the possibility to choose their own diskettes In the process seems to be compressive sensing to work August would be included fear Computer Sciences would be sketching you you argue the line than to preserve information and probably to have some also competition alone track with favorably favorable competition aspects where would like to do the same thing in compressive learning would be about the lining sketches with similar problems and I think the main question :colon consistently make you very recently superstition the group developed at absolutely the empirical rescues of some sort of sketch except that in fact usually it's an infinite dimensional sketch because you have to use of the whole funny of about possible values of parameters so you only have to do with our policy the hypothesis testing more and you you have to compare the risk of a finite number of that parameters sure surely you get a sketch that's natural sketch In fact the things moderately the young and the question is somehow can you design of Freddie Mitchell's sketch the gathering of information that you can recall structure and empirical or at least find the meaning neither him so before so so they were the general picture and trying to explore here with you and now I would like to give some highlights on some compressive learning examples of mostly heuristic so that within the PDC the flow of Albany bullying and neglected area who is still on the pigeon corroboration with that but it did

17:24

so well with seeing that the ideas would take a point I'd consider it as an empirical probability distribution of debates and many lines getting the beginning of the the escapes this form you have to choose functions H. L and he did challenges to chew them so that they their information relevant for the problem so but let us go back producer compressive clustering example of racial so the seller put here would be came in also we Scania Stewart donates a clusters of you manipulate modulator dude drove on where you saw sales etc he went with you and the way we designed a sketch was by kid doing some analogy with it was a human processing work we know that if something is especially localized simply needed before you is is a good way to make sure that we don't miss the Indians to think of a single that is perfect especially localized if you do only a few random samples you will probably miss the information was present unless you have many samples but if you sample with 40 and in 48 Everything is known it when went to work now so we use this analogy here but having few Christos means that I'm would approach to the idea for tradition of clusters of your accent you have caters to victory the Ark Katie and this here it would wait sample such a distribution would be to sampling freedom for something different domain simply means something the characteristic function Of the distribution and here we assembling the empirical characteristic function for the sketches there you can only serve deserted him said releases its meaning that aims to His Tennessee and a salon so there is a steady state doing lately assessing transformed features to the transforming says this is just this is this is related to their actually you can think of this is we're still working on the relations as so probably a good way to design sketches is to the line but but can mean that so that's a pretty infinite dimensional and sample I hope that the interplay between the 2 1 that the dimension that you can say that used sample is not completely clear for the 1st so you're precisely what here was starting from the signal-processing intuition that you sampling 240 domain assembled in their work artistic functions so essentially what you have to choose Sultan frequencies only gas and in fact when you look at it and you think about running for the future of this is very related to the generic around them for you future interpreted this is a pool of that but this is the empirical average of among them for the future that's a description of the distribution of so this is a sketch and so well behind all also of lot of questions holy chooses for the truth the sampling frequency is the irony of this is all the data that will not give in this in this presentation at distillate of the mn we we have heuristics so that's that that needs to be related I think to what is going on in that ambling through the proper channels so if you're interested in more detail so there a recent paper at the I gasped and that's presenting this week actually but we cannot OK so you know that in this case so we use this this type of sketching so with 60 of Salford City complex where or valued members of 60 60 inches sample the characteristic function and the results of its how do we obtain the result we need wasn't that starts from the sketch and performs the estimation of the sentence for that we need to exploit certainly is a model and when we have taken an arbitrary distribution and skits it so there's no way we can reconstruct it without a model in the modern here is there is a Gaussian mixture model which equaled alliances so all alliances identity for the only parameters of the weights of the trust of the GOP-controlled Christians and that the the central so if you assume that you'll distribution is a communism mixture of Gaussian set by seniority of the sketching operator the sketchy itself a mixture office gives the the good news is that when you take a Gaussian defended the goddess to function is that has an analytic expressions so you can everything can be used in be written explicitly and Uganda designer than that but that will perform the decoding the reconstruction inspired by that mimics offered matching Boston and the exploits the sudden the agree in the sense leveraging the explicit expressions of the great with respect to the ponchos and took off on this land for construction so this is something I was actually we are liberates complement propaganda machine posted replete with replacements rather than when p uh which brings significantly better results because of some the better ability to escape from the community and that's what might and waiting your the interpretation we have new analysis of the convergence of although all branches for the sirens for the moment did we just upset that it performs really well well have venturesome summaries so this is what compressive questions no can extend its a tool more types of problems well there's something I've already use a mixture of Goshen gaseous with a quota I was identity could alliances is not difficult to accept extended to 4 compressive definition models so what we've done we we've not completely relaxed at the that the arbitrary a government-run model just was diagonal covariance matrices and that's already a richer sets and with it you can you can adapt the evidence either the reuse the ABA than we had before but just use gradients suspected is not constrained options or that will be used to in the next experiments have some things which OK which use more the competition more efficient algorithm that not designed for Gustavsson scenarios mall knows where you have overlapping notions you don't really want to recover the centers of all that but that do you want the gushes to fit well so this is a new using high articles getting to slow to try the rights of yeah and yeah any question so let's see an example of well it's the proof of concept of how this can be used in Alaska's scenario the assessing the scenario considering speaker recognition so and how and why familiar with the German edition so who is not familiar with the German tradition this so In the West

25:03

German tradition is something where I at the well suppose you calling your bank and you say I'm the I'm a native Mellon idea that I would like you to transfer and all my money to work together to move the following account number probably menu cleaning and identity and the German vacationers about checking that this is the the day that it is the 1 you climb is that about the same thing about among them unified and it is who you are it's just sticking with your the often nuclear this this is to be digitally donor with trained models of each of the pursuant claimed identities but he already have very little data to train for a given model so what the way are you trying to using step 1st and the bill so-called world model with as much data as Uganda are representative of a very wide diversity of speeches and then you will adapt these models to 2 would be representative of each speaker so there's a step where you take care last collection and this and that and here we use the the 2005 news database of 450 gigabytes of of the all of the false Ginsburg maybe this is more compelled to debate the bikes that some limited manipulating this is a book thousands of hours of speech and you will not a definition model for 2 approaches will use in expectation maximization all the proposed program the value of the euro on this model and there is certain the so-called adaptation procedure for each new claimed identity and all way in the Andes calls and asked to did to transfer some money and all here is the speech that is pronounced it is compelled both to the world model and to the claimed identity enter college I'd like you would tests of a new likely would test is conducted to decide whether we said the transaction on so what we did was to compare this to the compressing approach the classical piano approach in this city so if you look at the end of the day sets the database that that is used to on this universal banking model this is a database of 1st the number of speech I know what all the individual victories that we can't hear well we the speech is getting too a small by friends and it's a friend you compute and ecstasy coefficients emission 12 so you don't need to know what Dynasty secret missions agreement of 1502 so if you think the hole that base of the 300 million the fastest quotations In fact or if you look carefully there are many more of these good vision that corresponds to the inactive and that speech and silence between the 2 words and so that users got some good reason they're not really are handful fall foreign following and it's it's a stumble to technique to 1st decide as addiction but you never have to sign the fiction is to have 60 million victors in your training collection In fact when you use the state of the altered the amount to suppress books the maximum size that kid can manage a free hand thousands of assembled 15 so we learned so we 1st conducted an experiment with this number of training samples if there was a cooperative approach all with expected with expectation recommendations and you can see the picture so this is essentially a false positive answers from the false negative cover well that's a little the better and it's got all the violence curve corresponds to Yemen rest response to all year at the end of the proposed approach was values sketch the agency that's OK if you increase the skates as you get better but doesn't really quite rich the quality of him no remember that game was limited by the collection site we couldn't from that with more data all methods can yes here was assessed using also those elements for you he said analysts and industry the sampling frequency occured so the W so I said that this a figure that there's a there's a heuristic that developed developing them in the papers but essentially I saw its their isotropic the distributed and so really deserve distribution which is uh which has low density around the origin because of all this tradition essentially declared that the cactus detention is always 1 of the origin and is even the you have testicles putting new moments that you could measure intercity there there's not much information and so that to assemble mall where gradient with respect to the parameters of your model is expected to be high so with this sampling our strategy we can all run them .period the proposed approach with the 60 meaning that it was a sketch computed in 16 years and fear what we get is that will offer sufficiently get sizes we know that we will do what it could idiom got sold that the results are getting better so In details here if you if you will use a small sketch but also it 500's samples represent the 16 million collection from this and this is more of a representation of the we were not quite at the performance of the Yemen but not that far from want to match situated performers of the M which include taken twice the number of 4 of the size of dispatcher answered with a slightly larger larger and size of collection so compared to the size of the region a slightly larger sketch Saskin compared to the time of the initial connection you get something better than so this is really a proof of concept and claiming this is compared to state of the art the Emmys no no longer the state of the art in the instigator education but this is to give you an idea that's just they simply unwilling to is spotted you get something that says that is not certain whether somehow explodes the fact that you have a loss training collection and that's what buy really capturing underground averages over a larger collection probably you get from all the diversity of the collection and you can mix could rather than better than if you were simply sampling 300 thousand samples From the Collection and so well regarded this is where you could also should I increases sketch Sizewell you see that's a problem if you have a few samples you can take a small collection that if you're more samples you would like to read benefits from the most by starting to increase the look at how much

32:45

time do I have book and so on now there are a few things I would like to to talk about after furor this illustration of the general ideas of sketching out the first one is the key states rights on the Internet deluded about how this can be implemented and the competition competition efficiency and so on and then will begin to rule some of the possible theoretical connections with some of what is known in involve problems and the persistence seoul regarding competition which efficiency well this is the expression of discontent the sketches as we proposed to compute them with essentially averaging run free futures so in terms of architecture started from your life large collection of training samples and then there's your matrix of

33:43

overall for the role of the you hear all year the frequencies where you sample nor the book artistic function so you know 1st and largest you have to make more frequency than the initial dimension of the vector in the office and knowledge of vectors applying the newly married you which is the complex exponential and then the average To compute the sketch so this is probably reminiscent of a case when the era of the of the network and by the leader the media are more connections with with neural networks are there but they're still to be investigated on ice in there somewhere cure recent work by the hope of Duke's on on some information preservation grant is for your networks but I think they could they consume all the information preservationists in the sense of being able to reconstruct the initial data and yeah what they do did the they message would be rather that the information that's important is the distribution Of the date that you want to preserve at least in this annihilation which is considered and now OK this is below the architecture when you think about it in terms of privacy and this is related to the and I think that was about the mentioned well once you've computer diskettes you when you just and the sketch not the rest of the data so to some extent there is this good to ahead with some privacy issues of course if the sketch has sufficient information to both .period and whether you will not be private with respect to the status but if we can do to investigate further the information preservation grant you is lower than the levels we may expect that to happen lower below that ensure that there is not enough information to perform certain tasks With submissions cancer so besides of course this is you can computes to sketch itself online so streets compatible with streaming and compatible with distributed computing so in mind summary here

36:00

with the services so sketches in this particular compressive Virginia members scenario you started from last collection the new computers gets you achieve high dimension reduction and then you will move durable loan with Sultanov residents to worlds that army more-efficient and competition efficiency to win extractor information provided that provided that everything has been designed that you have guarantees of information privileged salt In the gave I'm special and they're going do and that of scenarios where are you seemed to have information preservation and we'll see what could be a roll of the 2 walls proving In the information preservation so this is this is related to work we did a couple of years ago with company will you might need is done up in again there but it does so with the idea that there are all techniques classically used to analyze them Laurent miseries completion of the spots recovery general and involve problems in general that actually have our some really all generality and that maybe they're worth and packaging insufficiently a universal way so the big earlier in the inning those problems you consider that you have a hydrogen eventually observers of the initial version so without further information there's no way you can move to reconstruct that if you know that your baby that comes from is well approximated baseball's victory then there are .period equivalence with reconstruction branches so and

37:51

the Sultan the could now when no conditions for gay spouse covering you able to build an algorithm that we would go to the good they're here this is the dominant introducing the bill in the nice they provide you and Duquesne on development of endowment so the decoders of the ideally from your measurements you want to be able to build the decoder the Hassan reconstruction grants you here the reconstruction that was metric that I will leave quite physical so that he could have been done even if you have some knowledge renewal data the reconstruction of your X will be controlled essentially by the side of the noise of the show they don't satisfy your model so is exactly please boss here In so this has been investigated so I think we know there are cases where there is a good news but that's the nice work of going in there "quotation mark further west investigate the fundamentals of information theory the great question is OK when I there can expect such a decoder trade so we know the number of the good and when innovation graveyard residents and so on ah I work and I expect that the number of you are more or less familiar with the wet with this ends in terms of burnt are 1 of my possible focuses on so-called uniform granted worse-case their related to the window restricted item at the proper so no questions cool I said it was not familiar with the restricted asymmetry properties OK enough people that they would spend some time explaining and so these algorithms they are all designed to recover despite pollinators so you have kids public housing project dental dimension and what you would like to be sure that there is no way you can confuse to gage public to save you have 1 gets during another and that you putting them and get to essentially the same our representation than your last there's no way you can hope to reconstruct their case public the arrested asymmetry property is essentially something that just say that if you take her to gage public tour that are sufficiently distance in original space there will remain well distance in India and in your observations and says his new that the deal the disco considering the difference between 2 baseball victories victory that has took a 1 0 components is is the expression of the restricted isometric property preserves the Bloomberg attended the normal of I have reacted to gage public so this is what he is going for us in the case of spots recovery but actually there's a number of other models that have been considered in the literature of soul related work has been done with the some whistles ball there's always bigger than a spot in the dictionary and a number of other mention of those at your favorite 1 so and in all cases we would be in particular interested in this and models were the emission energy comes from the fact that you have a mixture of fear a few reductions with few body turns some and you would be like to consider something that doesn't really leaving the the line of finite dimensional vector space but the space of college in history full measure of final and finite signed measures so I don't question is still the same

41:36

occasion given some model some little dimensional model and for the moment it's not specified what we mean by a low-dimensional model in some space and you have some measurement of Florida a thing of the sketching operator when can we expect but to that there exists some reconstruction are over so where that that there is a decoder with sentences sense of community ground this time this is a question that is not new but said there has been a that is related to all questions from the faulty intelligence on embeddings where people have been this questions such as I have described as secure and 2 and can I might to find a dimension that and the what's the dimension akin to at the moment but I will not say that the developer disposal here will see that's actually the existence of such a gain related to a generalized notion of restricted asymmetric property so sent us stating when you're restricted asymmetric property for it's a type of model of when that state 1 4 any model sets and series so consider signal which is some subset the fury ambient space when you say that's your measurement operator Emma satisfies a restricted asymmetry property on this model largely under the consent of his model that makes the difference they chose between 2 vectors of the model if you will the so this inequality of all of us thought he I wrote it in an isometric way that you can write it was usually with one-liners that there was presented in a straightforward manner and where it's possible to show that in fact the if there exists but the quota with this reconstruction granted then necessary the matrix and that you're considering satisfies the other restricted asymmetric property this is just an analysis of the worst-case conditions In the 2nd reserve was responding to

43:47

more of the most interesting to me is that in fact if the restricted isometric property then there is indeed a decoder with reconstruction guarantees "quotation mark I come back to the good said you're just beginning on the day my next faulty science Walter justly so give Justin existence results so this is where y states information theory results rather than mean it's not dealing with the completion trader there are many nice questions surrounding that try to evoke some of them are so I think it's a good it implies that so if the new matrix or your measurement operator because of the lateness saying 5 dimensions of history matrix satisfies the rate then there is a that's provides exact recovery and was that needed to noise so whenever you take eggs which is a new model said similar you measure it you had some noise at the decoder provides an narrow proportional to the nicer than the size of so this is just an extension and the provisions follows from October rewriting of that of being the work of Glen Abbott we've just extended version that it can be extended to not arbitrary models as something of a bonus is that's and that's probably the main difference with the Aaliyah bidding results so far the real from the leader of lamenting that there is also sense that to mining so even if you're initial signal does not exactly belong to the new models that but if he is close enough With the metric that's also related to your model sets then the army and new measure its distance from the need to be closing measure distance and then there's the unedited film In your inner inequalities so this is this is the most stable tonight and robust now of course postures asking yes that was good so

45:53

somewhere down with some somewhere down this year with the million homes now whether that try to provide some and since that 1st maybe I

46:05

need to adjust unit with the decoder ring the proof of that in the previous 4 so you know that you have a meeting with the rest of the there is a good whether go but it's written here for you given your observations while you find the X that minimizes the other way that some of the the blows stands the model said they're happy to for the manipulated this about security of the stance is not the conditions you are the sort itself and it's here that this is missing money get strike in certain cases it's essentially the 1 on so it could look OK exhibit your computing the distinctive public research and that's not that nice to too many saw of the good news is that the figure is also in my mind you'll need to know that the noise levels the decoded is decoder will work and provides the grant is whatever denies that received only 2 June to to begin with but my grief not very convenient something slightly more

47:18

conveniences that was proposed by the government to my Blumenthal so who the proposed to my date is the attractive offers shutting out with them .period reconstruction and the predicted and there are there is just that a geriatrician to lavatories that so I hear something connected to the talk of the on the pommel yesterday when the related talks and there was a question by Duma with the on yet but would give the proximity so easily computable into this would put up here so the idea that idea of the predicted on whether Italy there is simply no that's it's initiative and the predicted rate of the you but you do at this that some gradients tool of decrees the use of that he did down that's when it to develop and then you project to the closest point on new models so that's perfectly fine when you have kids but you might affect this case Polydoras Oregon mattresses and the victor sets for which you know how to do it do it efficiently but you know it's easy to exhibit its number of the cases where it's a very gently held up to compute this products working on all soldiers opened the number of questions on maybe got rising up with all the models sets for which showed that the you you have actually something computer props that is computable because support for the Union will have dimension reduction and compatibility which which would be nice and in this case because the proof of convergence of soul with a well-chosen step size related to the rear the constants in the restricted asymmetric property of 2 matrix corresponding to law 1 of the best more than 1 Fountain one-fifth you can't prove that this the subways in this convergence and that recovers of the doors and no you can prove that the future rights provide a stable recovery so if you're single was with the new models set to recover it exactly the you cover students and show much new models that you may not be confident that you will circle within the ball that's not too far from the from the that the noise level and the millenium again OK maybe not so convenient and so since there were a number of talks on conflicts of the musicians maybe you went through all of you would rather be expecting is something of this type and that they could do that based on the minimization of some functions so we knew a number of them so that they could or would be I try to find Mongols solutions within the prescribed period well that G the 1 that minimizes some regularize the FOX clause you should lecturers as and when not to try to well for a number of such a model pairs of Mandel said and regularize many of those have proved that but if you read that rules restrict is isometric properties below Sultan constants then use recovered duties and instance human good somebody good although reserves of Guyana's I'm going to be shop and so the whenever we do can be improved 4 and 1 . 1 million musicians clothing and then less story of a work showing that the the 0 . 4 3 1 0 4 4 2 2 4 2 3 5 wares and we're working on that but still every time you get a new the new models and try your arises there's a new were granted to the obtain well that's what we investigated which shall Tommy is In the was the existence of an underlying principle and so we got 1 and so please please don't read this small forms it's more falls just through 2 minutes so that you don't so in fact that if you'd like if you have a model said that simply homogeneous set to protocol and committed by vapors at scanner you remain in your mother set text that include the case of unions of the patients that Oscars was table include the number 2 petition anything can you read your eyes are you can actually find them a restricted asymmetry property constants is deep in the new models that the new regularized and will do so in this again that any measurement military that has a rape with a bit of a smaller than this particular constants will now become compatible with regularization was ever on your model and to the degree that questioning the Gooding will and will work we will have so this promise or what we would have like to do would be taken model sets find out automatically with the right to regularise their the only thing I saw at 1st we thought that the meals with that would do it said that the big wanted knows is nice but if you look carefully at what it does is it here is my model sets but in fact but these mothers sets it has special poisoning and you know I like all the items and they had in fact special property that I don't really discuss on the of Sultan also energy properties between them at the homes of ants from the side beaten at the meeting that we were going to get to it it was the moment you have a business case here there an example of if you take as did that you might have to be deceptive to spores victors so probably the natural law In a way of designing at those would be I think every you need every normalized 2 spots lecture and then the acknowledges the so-called case support normal in there was cake was true and it's really doesn't Bruno recovery of pointed out the corners of the world and 1 board because every day because at an enormous flat so it's 2 bits of it and I think the question of Starting from the model and construction dear regular rises to an interesting and open 1 of the few if any have all along in the final of last year the not that's down that way you can do them in that starting from the normal get better but so I'm interested in the reverse way starting from a model in which all the victims you would you want to reconstruct how do you build your ignorance and 1 possible way that we like investigators to try to design it to us to maximize his constant human users the use of some sets the politicization of the news media boasted of the feasible to go on the air in any school they send the people may say that many that would include 2 that involves the measles nested may be impossible for them to have a complex 1 and say I didn't even say that it says is complex but still F signal identified his 1st but like all aggregated many at some point and it took too much to be able to optimize the but sometimes condemned the epidemic so but if you look at it as quelled loss plus f it collects on the following cases Delaware Basin sadistic on that sometimes it's the overall problem that you poses problems grew convictions of the penitent focus on do I just have to give you an example of what can be obtained with idea that the results and probably at minus 1 1 and I know you get sort of Uganda and ruled out the mechanics of the Of the propriety of the Roman recovery Justinian users but gets shot through the results from World examples for example I don't know if anybody interested in recovering delegation addresses from the initial projections but so you can do it provided you have read to further and that can be achieved with the American designed .period dimension reduction that the operator that is that despite the this this rate with the number of measurements that some the uh that's controlled by rival Ranil having minor the covering members of the set of 4 road competition witnesses so that can be done

56:12

and seems 100 which also I peppery I'm convinced that was just to illustrate the idea that the best you can really use this technique to somehow the designer regular from model soulful Sultan model could you the 1 Norma that is the name physical papers all knowing this bastard the different blocks the way you were nominated dissuaded 1 on you have reaped Perkinston that I higher so beloved that recovery grants so high you tend

56:43

to conclude as the main

56:47

message right to convey here is that they are interesting part is to be done between the signal processing machinery running and there with the idea that compressors sensing good maybe give rise to the compressive learning techniques with the ability to reduce it to substantially reduce the size of the coalition while preserving the information necessary to perform the task that you that you want and administratively we spotted hero sketches that only nearing the date of chimera inter-party distribution that so well know just so that's been it's fulsome advertisement for some of the results that I couldn't fit in the previous but most of all the fault of compressive festering in the presidium member that these are all the references of the people really can be found no regarding information preservation and this is what I show with this restricted asymmetric properties the 1st lady Of the story option for falsify worst-case analysis now seeing that's a it's the information is there in your initial projection but there's a and in dissidents the stories here I know there's the question of how much the emission reduction can you and and you perform well actually presumably in well this is there are many works that currently trying to generalize and by such and the also the limo to the General Motors sets and in particular the work of Gypsy and that's the word that establishes that and links between the Goshen we says the measure of dimension and how much you can reduce you can and hope to work with the dimension you can hope to protect to but it seems that it is not clear yet the end of the story and that's this dimension in metropolis or there are questions about what is the right manager of dimension for models that and Botica when you Potter grew at a given moment just how should you measure it it has sold some of the questions that around this our our related some of the notion of compressors that he's going to win what you want to reconstruct the risk functional by but the force of the discretion we now know that you can actually characterized the interesting dimension of stitching that is needed for 2 to achieve it's about so many questions remain open so thank you for your patience and attention the only question will you use the types of things to do that and understand that didn't use it to his it father was evidence that people are able to convince voters that is madam completion program said that it was not member of the most likely that Ottawa was filed for the rest of the completion of a absolutely the assault the military and the RIP reticulated Mishra property is necessary and sufficient to where to have the uniform world reconstruction wearing his I bet it's but the Armenian entities that do not require worst-case analysis and that's as it is somehow related to a contrast OK we there is there a key people did and better during the military so if you do launch matrix reconstruction they all are waves of sampling ignoring mattresses which satisfied the restricted asymmetric property but this is not the point twice sampling corresponding to matrix completions so if you if you want to do matrix completion when you have some matrix of few points in this the measurement operator will never satisfy the restricted asymmetric properties could you can find very simple following mattresses that will just to 1 at the moment of locations thought that the restricted Mitra properties is feasible but measurement that measure of essentially the whole world all coefficients at once the Commission claiming that the other than other practical matters the completion of millions behind your back to the 1st major medical report the nation it applies to matrix reconstruction problems with certain types of food observations but not his observation that our related to the next fix problems in Warsaw where you know you have a number of entries and observant for his part this also shows that during the campaign of on the part of where the hell is there's 1 that I'm not sure would be interested in it because if your models that is the linear a substance that has accomplished a number that essentially cut but that's their view of the reservation is that it was still demanded to be useful in southern scenarios where actually you just revisits the if you don't have the same as that of the same number of that's important to about from that I think it is due to the difficult and got people so no soaring and governments of focus something that was the specified problems related to the computing power testing whether the rest of the asymmetry property and restricted asymmetrical something exudes a sudden departure the which is the opposite of highly probative "quotation mark also used the I was also modified its analysis will also grow here says so you to commemorate rested in the new properties OK and there I am in no notice later this year contact but that Pfizer and there are no it's a related to the distant corners of the of the Baltic Europe could cost the construction so here I was talking about the change and want to do reconstruction the information in your measurements on the the restricted eigenvalues property I think is more related to the depart the choice of a particular and now you're looking at the behavior of some of the restricted asymmetry property Fund vector that are and then decreases the risk of functions this is not this I think typically to the tomb uniform results on and only from grantees is when you have a given point you can see you how you can decrease the cost function the English duration it can be critical function and analyzed the restricted items the it what was the 1st to all we have friends over the years it was painful "quotation mark was OK and so 1st in the things that I didn't really think that thing to evoke they also not in general arguments from the air when you try to deny Johnson the minutes from the start the name of and there's the notion of the but there are models of the mention of Phil sets that's naturally appear and so if you on the side of Saskatchewan sufficiently sees this measure of dimension but you should satisfy the restricted image property it's not secure when you have kids files victors of the gala event of the appeals and naturally so of course who was a constant and that's the thing is to be cured before definition models that we played with while you can essentially count the number of parameters and so if you have a K Gaussian certain dimensions of the especially when you have the weights minus-1 weights and the anarchy case centuries to give answers that will be there and that they can't use sense you harm and what's the size of we have empirically observed that we get face physicians with the fully aware that with this size of sketches only here in the this is the kind of power this what is where the meaning section of this residents of the that's that's the that's a different problem I have often thought of paid too much attention to which is OK with the model among voters to choose your model for properly and to the point of view with rather OK I've been given the model fortunately model and this is the idea saying they will fit 64 governance will harmony with the fate of the sketches I should I should use the 1 your evoking those divisions much

00:00

Resultante

Matrizenrechnung

Punkt

Wellenpaket

Hausdorff-Dimension

t-Test

Zahlenbereich

Term

Eins

Überlagerung <Mathematik>

Algebraische Struktur

Spieltheorie

Punkt

Spezifisches Volumen

Schätzwert

Einfach zusammenhängender Raum

Beobachtungsstudie

Diskrete Wahrscheinlichkeitsverteilung

Parametersystem

Stichprobe

Vektorraum

Ordnungsreduktion

Endlicher Graph

Zusammengesetzte Verteilung

Projektive Ebene

Energieerhaltung

Streuungsdiagramm

Geometrie

05:48

Resultante

Matrizenrechnung

Einfügungsdämpfung

Adhäsion

Punkt

Prozess <Physik>

Momentenproblem

Extrempunkt

Natürliche Zahl

Gruppenkeim

Extrempunkt

Komplex <Algebra>

Massestrom

Raum-Zeit

Deskriptive Statistik

Hausdorff-Dimension

Exakter Test

Endliche Menge

Punkt

Einflussgröße

Gerade

Nichtlinearer Operator

Lineares Funktional

Parametersystem

Statistik

Topologische Einbettung

Grothendieck-Topologie

Ähnlichkeitsgeometrie

Frequenz

Dichte <Physik>

Arithmetisches Mittel

Zusammengesetzte Verteilung

Diskrete Wahrscheinlichkeitsverteilung

Lemma <Logik>

Histogramm

Sortierte Logik

Projektive Ebene

Normalspannung

Hausdorff-Dimension

Zahlenbereich

Term

Erwartungswert

Spieltheorie

Stichprobenumfang

Abstand

Inhalt <Mathematik>

Gammafunktion

Schätzwert

Diskrete Wahrscheinlichkeitsverteilung

Matrizenring

Matching <Graphentheorie>

Graph

Dimensionsanalyse

Schlussregel

Vektorraum

Fokalpunkt

Ordnungsreduktion

Objekt <Kategorie>

Flächeninhalt

Klumpenstichprobe

Streuungsdiagramm

17:23

Resultante

Einfügungsdämpfung

Kovarianzfunktion

Diagonale <Geometrie>

Punkt

Prozess <Physik>

Momentenproblem

Extrempunkt

Element <Mathematik>

Erweiterung

Extrempunkt

Komplex <Algebra>

Determinante

Computeranimation

Gradient

Deskriptive Statistik

Gruppendarstellung

Arithmetischer Ausdruck

Hausdorff-Dimension

Exakter Test

Standardabweichung

Nichtunterscheidbarkeit

Punkt

Fließgleichgewicht

Figurierte Zahl

Analogieschluss

Gerade

Sterbeziffer

Nichtlinearer Operator

Lineares Funktional

Parametersystem

Multifunktion

Grothendieck-Topologie

Güte der Anpassung

Stichprobe

Klassische Physik

Heuristik

Binomialkoeffizient

Frequenz

Endlicher Graph

Dichte <Physik>

Arithmetisches Mittel

Zusammengesetzte Verteilung

Diskrete Wahrscheinlichkeitsverteilung

Diskrete-Elemente-Methode

Rechter Winkel

Koeffizient

Beweistheorie

Anpassung <Mathematik>

Strategisches Spiel

Hierarchie <Mathematik>

Normalspannung

Diagonale <Geometrie>

Aggregatzustand

Subtraktion

Gewicht <Mathematik>

Wellenpaket

Hausdorff-Dimension

Zahlenbereich

Bilinearform

Kombinatorische Gruppentheorie

Heegaard-Zerlegung

Überlagerung <Mathematik>

Erwartungswert

Spieltheorie

Mittelwert

Endogene Variable

Stichprobenumfang

Freie Gruppe

Modelltheorie

Optimierung

Grundraum

Gammafunktion

Analysis

Einfach zusammenhängender Raum

Schätzwert

Diskrete Wahrscheinlichkeitsverteilung

Matrizenring

Kurve

Stichprobennahme

Zeitbereich

Relativitätstheorie

Modul

Vorhersagbarkeit

Unendlichkeit

Dämpfung

Klumpenstichprobe

Numerisches Modell

32:42

Einfach zusammenhängender Raum

Arithmetischer Ausdruck

Wellenpaket

Funktion <Mathematik>

Rechter Winkel

Stichprobenumfang

Vorlesung/Konferenz

Term

Aggregatzustand

33:42

Einfach zusammenhängender Raum

Diskrete Wahrscheinlichkeitsverteilung

Lineares Funktional

Erweiterung

Vervollständigung <Mathematik>

Hausdorff-Dimension

Laurent-Reihe

Annulator

Vektorraum

Äquivalenzklasse

Frequenz

Term

Ordnungsreduktion

Computeranimation

Übergang

Hausdorff-Dimension

Eulersche Formel

Stichprobenumfang

Modelltheorie

Gleitendes Mittel

Normalspannung

37:48

Momentenproblem

Extrempunkt

Raum-Zeit

Computeranimation

Erneuerungstheorie

Arithmetischer Ausdruck

Gruppendarstellung

Numerisches Modell

Existenzsatz

Eigentliche Abbildung

Asymmetrie

Punkt

Chi-Quadrat-Verteilung

Einflussgröße

Gerade

Nichtlinearer Operator

Topologische Einbettung

Gruppe <Mathematik>

Kategorie <Mathematik>

Reihe

Zusammengesetzte Verteilung

Teilmenge

Diskrete-Elemente-Methode

Menge

Konditionszahl

Tensor

Projektive Ebene

Aggregatzustand

Lineare Abbildung

Theorem

Subtraktion

Hausdorff-Dimension

Matrizenrechnung

Zahlenbereich

Geräusch

Nichtlinearer Operator

Kappa-Koeffizient

Ungleichung

Iteration

Massestrom

Zusammenhängender Graph

Abstand

Modelltheorie

Ideal <Mathematik>

Analysis

Fundamentalsatz der Algebra

Finitismus

Vektorraum

Methode der kleinsten Quadrate

Ordnungsreduktion

Menge

Energiedichte

Modelltheorie

Rangstatistik

Numerisches Modell

43:46

Resultante

Matrizenrechnung

Subtraktion

Theorem

Sterbeziffer

Hausdorff-Dimension

Geräusch

Kappa-Koeffizient

Ungleichung

Numerisches Modell

Existenzsatz

Eigentliche Abbildung

Abstand

Modelltheorie

Einflussgröße

Gammafunktion

Nichtlinearer Operator

Erweiterung

Vervollständigung <Mathematik>

Oval

Kategorie <Mathematik>

Güte der Anpassung

Menge

Aggregatzustand

Numerisches Modell

46:03

Resultante

Matrizenrechnung

Einfügungsdämpfung

Punkt

Momentenproblem

t-Test

Gradient

Extrempunkt

Gesetz <Physik>

Computeranimation

Gradient

Numerisches Modell

Einheit <Mathematik>

Regulärer Graph

Existenzsatz

Asymmetrie

Figurierte Zahl

Einflussgröße

Inklusion <Mathematik>

Lineares Funktional

Nichtlinearer Operator

Extremwert

Tabelle

Kategorie <Mathematik>

Güte der Anpassung

Stichprobe

Globale Optimierung

Übergang

Rauschen

Biprodukt

Frequenz

Konstante

Matrizenring

Menge

Verbandstheorie

Sortierte Logik

Rechter Winkel

Beweistheorie

Konditionszahl

Projektive Ebene

Mechanismus-Design-Theorie

Theorem

Sterbeziffer

Hausdorff-Dimension

Zahlenbereich

Bilinearform

Permutation

Unterring

Massestrom

Konstante

Modelltheorie

Abstand

Ideal <Mathematik>

Basisvektor

Erweiterung

Kreisfläche

Schlussregel

Isochore

Fokalpunkt

Ordnungsreduktion

Energiedichte

Normalvektor

Eigentliche Abbildung

Dampf

Rangstatistik

Numerisches Modell

56:11

Resultante

Matrizenrechnung

Abstimmung <Frequenz>

Punkt

Momentenproblem

Extrempunkt

Analysis

Computeranimation

Numerisches Modell

Hausdorff-Dimension

Exakter Test

Regulärer Graph

Uniforme Struktur

Asymmetrie

Ausgleichsrechnung

Kontrast <Statistik>

Einflussgröße

Auswahlaxiom

Lineares Funktional

Parametersystem

Nichtlinearer Operator

Vervollständigung <Mathematik>

Verschlingung

Kategorie <Mathematik>

p-Block

Ereignishorizont

Koalitionstheorie

Arithmetisches Mittel

Forcing

Rechter Winkel

Koeffizient

Garbentheorie

Projektive Ebene

Explosion <Stochastik>

Normalspannung

Eigenwertproblem

Partitionsfunktion

Gewicht <Mathematik>

Hausdorff-Dimension

Wellenlehre

Physikalismus

Besprechung/Interview

Zahlenbereich

Division

Kostenfunktion

Modelltheorie

Optimierung

Analysis

Leistung <Physik>

Diskrete Wahrscheinlichkeitsverteilung

Indexberechnung

Vektorraum

Fokalpunkt

Menge

Mereologie

Modelltheorie

Numerisches Modell

### Metadaten

#### Formale Metadaten

Titel | Projections, Learning, and Sparsity for Efficient Data Processing |

Serientitel | Computational and statistical trade-offs in learning |

Teil | 09 |

Anzahl der Teile | 10 |

Autor | Gribonval, Remi |

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. |

DOI | 10.5446/20252 |

Herausgeber | Institut des Hautes Études Scientifiques (IHÉS) |

Erscheinungsjahr | 2016 |

Sprache | Englisch |

#### Inhaltliche Metadaten

Fachgebiet | Mathematik |

Abstract | The talk will discuss recent generalizations of sparse recovery guarantees and compressive sensing to the context of machine learning. Assuming some "low-dimensional model" on the probability distribution of the data, we will see that in certain scenarios it is indeed (empirically) possible to compress a large data-collection into a reduced representation, of size driven by the complexity of the learning task, while preserving the essential information necessary to process it. Two case studies will be given: compressive clustering, and compressive Gaussian Mixture Model estimation, with an illustration on large-scale model-based speaker verification. Time allowing, some recent results on compressive spectral clustering will also be discussed. |