Optimal computation
21 views
Formal Metadata
Title 
Optimal computation

Title of Series  
Number of Parts 
33

Author 

License 
CC Attribution 3.0 Germany:
You are free to use, adapt and copy, distribute and transmit the work or content in adapted or unchanged form for any legal purpose as long as the work is attributed to the author in the manner specified by the author or licensor. 
Identifiers 

Publisher 

Release Date 
2006

Language 
English

Content Metadata
Subject Area  
Abstract 
A large portion of computation is concerned with approximating a function u. Typically, there are many ways to proceed with such an approximation leading to a variety of algorithms. We address the question of how we should evaluate such algorithms and compare them. In particular, when can we say that a particular algorithm is optimal or near optimal? We shall base our analysis on the approximation error that is achieved with a given (computational or information) budget n. We shall see that the formulation of optimal algorithms depends to a large extent on the context of the problem. For example, numerically approximating the solution to a PDE is different from approximating a signal or image (for the purposes of compression).

Keywords 
optimal computation
encoding and compression
learning theory
entropy and widths

Related Material
00:00
Functional (mathematics)
Numerical digit
Arithmetic mean
Elementary arithmetic
Linear regression
Variety (linguistics)
Range (statistics)
Analytic set
Approximation
Theory
01:14
Family
02:06
Functional (mathematics)
State of matter
Direction (geometry)
Real number
Range (statistics)
Set (mathematics)
Theory
Goodness of fit
Mathematics
Manysorted logic
Different (Kate Ryan album)
Mathematical optimization
Area
Block (periodic table)
Concentric
Content (media)
Sampling (statistics)
Computability
Funktionalanalysis
Fourier transform
Approximation
Probability theory
Numerical analysis
Linearization
Resultant
06:24
Point (geometry)
Building
Length
Connectivity (graph theory)
List of unsolved problems in mathematics
Set (mathematics)
Mereology
Grothendieck topology
Dimensional analysis
Product (business)
Group representation
Plane (geometry)
Manysorted logic
Matrix (mathematics)
Gastropod shell
Skalarproduktraum
Position operator
Mathematical optimization
Physical system
Sigmaalgebra
Military base
Block (periodic table)
Moment (mathematics)
Sampling (statistics)
Algebraic structure
Special unitary group
Basis <Mathematik>
Price index
Approximation
Planar graph
Category of being
Voting
Vector space
Numerical analysis
Right angle
Game theory
Object (grammar)
Hyperplane
Spacetime
16:37
Discrete group
Randomization
Presentation of a group
Range (statistics)
Water vapor
Perspective (visual)
Dimensional analysis
Expected value
Estimator
Different (Kate Ryan album)
Orthogonality
Bernoulli number
Descriptive statistics
Physical system
Social class
Structural load
Sampling (statistics)
Maxima and minima
Category of being
Arithmetic mean
Order (biology)
Fehlerschranke
Moving average
Figurate number
Spacetime
Directed graph
Point (geometry)
Einheitskugel
Connectivity (graph theory)
Least squares
Product (business)
Element (mathematics)
Goodness of fit
Hyperbolischer Raum
Finite set
Term (mathematics)
Energy level
Modulform
Selectivity (electronic)
Distribution (mathematics)
Physical law
Content (media)
Basis <Mathematik>
Mortality rate
Linear algebra
Cartesian coordinate system
Equivalence relation
Universe (mathematics)
Game theory
Distortion (mathematics)
State of matter
Multiplication sign
Set (mathematics)
Parameter (computer programming)
Mereology
Proper map
Grothendieck topology
Mathematics
Casting (performing arts)
Manysorted logic
Analogy
Matrix (mathematics)
Series (mathematics)
Isometrie <Mathematik>
Position operator
Stability theory
Area
Process (computing)
Sigmaalgebra
Concentric
Generating set of a group
Moment (mathematics)
Computability
Determinism
Price index
Measurement
Sparse matrix
Vector space
Uniformer Raum
Normal (geometry)
Right angle
Resultant
Geometry
Classical physics
Probability distribution
Finitismus
Existence
Functional (mathematics)
Inverse function
Interpolation
Divisor
Link (knot theory)
Random matrix
Inequality (mathematics)
Theory
Power (physics)
Operator (mathematics)
GaloisFeld
Linear programming
Mathematical optimization
Condition number
Random variable
Stochastic process
Addition
Military base
Eigenvalues and eigenvectors
Forcing (mathematics)
Mathematical analysis
Approximation
Voting
Numerical analysis
Gleichverteilung
Nearring
Maß <Mathematik>
00:01
it gives me great pleasure it's an honor to be the pulled over the last decades decades is being moved by nearing introducing a variety of methods are functional approximation an approximation theory in all of its implication that grants contributions cover a broad range of issues and problems deep analytical issues related To make to biology for functional approximation you'll hear sought observer outcome and import import of this kind of work in top later but that we just say that functional approximation of the key to the digital age Simpson's machine learning and functional regression its rosy means straightforward elementary questions that
01:16
everybody asks but nobody knows how trained a hopefully you will learn something in the next few minutes another aside that just learned a few minutes ago that we are actually met medically related
01:28
is my nephew back to better connect you read graduated under body and each my medical brother we're than we were forced to of small Maddox and how but fool can't thank you cool role for roughly I think we're all
02:12
aware that most scientific problem be solved exactly so we have to resort to some sort of approximation or numerical can amputation so we create a algorithms to try to resolve these
02:30
problems and my Clark is concerned with is there a way to tell whether an algorithm it is absolutely or nearer this would be not only a
02:50
wonderful result mathematically would lead us In a right direction of how democracy computation Seoul you that West scorers were gonna have to describe exactly what we mean by optimal but I wanna put another caveat until you may think of an algorithm that solves very good fuel in theory but you have to remember that whatever we implement such an overlooked we do it on a computer and were subject to machine and even areas and entering the data was not just a question of designing an out of them but the world should be numerically stable you will see that ingredient coming up my talk so there many settings that I could describe this that With my colleagues especially with bare opponent both turned down and we studied this problem of optimal algorithms many different settings but after some thought about what I should do during the stock decided to speak about me in the setting this quicker work also make up stand here maybe I decided the concentrate on an area which is called compressed sensing this is a relatively new area In mathematics is getting a lot of interest these days and the motivation for this the problem of sensing realworld signal so the usual paradigm for signals that their banner limited functions and the way sample them through with goal channel sampling theorem overnight with sampling unfortunate state of affairs is they many of real world signal there were interested in art broadband and this means that their Fourier Transform as large support and that yes type of assembly cannot be implemented in practice sold compressed sensing is looking for a way around this to find another way of innovative way of sampling that defeats the road block of fairness sampling and sample signals more aptly information content in the signal rather than at we determined by bandwidth with soaked my reason for choosing this subject is 3 reasons why the very audience friendly as you'll see it would be easy for you to Graf the main ideas that are here because it's basically going to be an exercise In a finite dimensional geometry linear algebra the reason is that the subject itself interface a lot of areas of mathematics most notably probability theory theoretical computer science functional analysis but the real reason is that by discussing this subject I'll be able to introduce the kind of optimality that are important in numerical computation and all the nuances you will Google CEO introduced 3 types of optimality when we discussed this problem and it's sort of the a full range that
06:25
I know of that occurs in America problems OK let's begin well really is in compressed censoring were addressed in an analog signals but the subject is fully developed only for discrete signals so I'm going to stick to the PRI's signals until the very end when I make a few comments so our problem is the following we have a vector actually are and in here capital and large so for example if we're dealing with images and would be the number of pixels would be of decisive 1 million or even more but and the problem is at work the game we're going a place work allow that have small and questions about this signal signal and these should be nonadaptive by which I mean I don't want to have that 100 question depended on the answers to the previous nite United you must set the questions in advance I'm even more restrictive because the what I mean by question of going be very specific the question to me is that it's gonna be the inner product that this vector acts with some other vector so you can choose the Vector B and that we'll give you that by taking theater productivity with that you get the answer to your question so to question the very specific in this case when information now we can always represent this however the system by and by and matrix 5 the roles of the Matrix would be these vectors V there were taking theater product with respect to capital and the length of the of the vector X so technically capital and very large and small and very small so we have short in fact matrices 5 in this world of Brazilian diet this is applied were were interested short fat thing say object my question is can we say what are the best matrices to to you such a system or it's not best near best good matrices now you're God is going to mean what means that once we extracted this information why would fire that so access appeared before us we ask these questions we get the vector why and how Aqsa disappeared from our site and all we uses why and what we're interested in His how well we recover acts from this information while I welcome we approximated this of roughly speaking what we mean by good now there's gotta be 2 aspects this problem 1 doesn't y contain enough information about acts and the 2nd is how do we extract this information from why that part of called the decoding and both are serious issues OK so let's think about what the problem really is here so we have a lot matrix 5 that snapping a large dimensional space are entered into a small dimensional space so naturally a lot of vectors are mapped of the same image and protect to look at all the vector of map and they the most space this is a large where venture capital in my little capital and begin little and small This is a large dimensional space so we have a lot of the Laughing going on if you took than any of vector y and asked what vectors are mapped into why they can be described as just off hyper where you take any 1 of the vector met the wife and then at all space who would give your hyper played in this entire hyper players has the same information y so what these type planes which are denoted here and we also lists of a given type of player why all the point that this type of planar map into the same information vector while price of this tremendous collapsing here going on now decoder what is it going to do it's going to take awhile and has been a map of back into the big space are after that we get our approximation X bar To our original at now this point you should be very pessimistic there were going do something here because of the collapse so with this vector X mark would have served as an approximation for all the actors in this big hyper playing that with map of the why because but those are Our are distinguished in any way by this encoding decoding
11:31
role treated the same way well indeed if we if we had to work and complete generality we wouldn't be able to say much about however our Our understanding of the world the real signaled that they have some structure and we want you lie the structure or take advantage of the structure and going forward paradigm for the way we think of realworld signals that there's Parsons said that there is a set of building blocks in if you represent the signal with respect to this set a building block it either have very small representation or can be approximated well by future arms now building blocks in my case when a restricted the case for the building blocks are a basis for our you could think of this and other settings as well In some problem we may know the basis in which the vectors another problem we might not know the basis of this is an important consideration I'm might actually procedure for the moment assuming that with the bases is known to us and then later I'll say something about what we do when the basis is not known all get Harris going to be my 1st way of measuring optimality so I'm interested in value that we tackle a problem like let's try it and make a precise mathematical problem To see what we mean by best were near best album of the year is my 1st motion of optimality I want to duel I might assume that might signal this bar and I'm going for for now I can assume that the bases in which part of the canonical bases this is not I'm not pushing anything out the ride because you can always make a bases transformed forget to this Shell what I mean by a sparse vector it has few nonzero component but let's a given a vector acts the support as the number of I indices for which the bacteria nonzero and I formed this collapse Sigma which all backers who support of less than or equal to care so this is nonlinearity that bottle innerspace it's a union of hide foreplay you can take for example thank God any index at outside K and look at the set of vectors supported on TV new union union so you can visualize the have a lot hyper planes in the Union of these is the censored McKay I would assume I signals and Sigma Annan asked them and that information how they knew best design In encoding decoding scheme so is a problem capital when as fixed little kids fixed and I ask What's the smallest man such alike and build a matrix 5 Kennedy voters that will capture every 1 of those guys exactly and under the value right offhand what theaters the answer is and people to care for this is sort of morally justified if you think about it why because of that there's a stigma case is determined by 2 game pieces of information you need to know the K positions where is nonzero and you need to know the the value of X at a position Best UK pieces of information sold 1 would think you can do this with 2 case samples but of course my definition of questions with very specific I have to take enterprise was not absolutely clear that I can do that but as we will see we can Seoul to describe what matrices my goal now is to describe what are the good matrices for this problem what matrices will work so I wanna think of my matrix of belt from column of the Matrix has How do you want to read capital anomaly introduced a property of the matrix that if the Matrix has property that will allow solution to this problem to describe this property what I look at it some thought matrices of 5 and the matrices I did I take any columns and a set of indices column the and I look at the sun matrix gotten from 5 I just keeping both columns of throwing away everything else I'll be annulled this by fight he said I will use this matrix frequently and associated that matrix Aziz granted matrix fight he transport fight he which is a matrix of inner products this matrix is a square matrix look at
16:38
symmetrical nonnegative definite and I'm years of 0 so support you have and then you wanna check whether a matrix
16:50
of this size will capture every 2 days every case sparse vector exactly I maybe this will be the case if and only if 1 of these 4 conditions hold and they're all equipped so the 1st condition is that the intersection of Sigma KOO these 3 conditions since this the requirement that we reproduce all signals exactly so the 1st condition is that segment intersect and also faces 0 no notice I'm trying to recover fire signals but here the conditions to now why do we have that is very intuitive we need to avoid the case where to signal the link here both map the the same wine because we couldn't find which 1 wealth to signal their map the same why I can't take their differences about a bitmapped Azinger role less something and and all space but their difference will typically be a signal Of like to get that target of this condition and equivalent conditions are the following in these a simple linear algebra another way status to say that these matrices fired he that I form no matter what selection of columns I picked as long as I picked to pick found that this matrix should have a right to play for now the winners that his Ramadan and matrix should be convertible so if I can't find a matrix 5 with this properties that I know it will recover to face case sparse signals exactly so that questions that I have struck such major and I rights and not maybe I'm getting so find such while what do we need to do we need to create factors Our claiming I can do this friend equals to carry right so I need to be able to create a lot of vector because Capital One as arbitrary could be arbitrarily large I need to create a lot of actors in are case and I need that when every right to take to pay them there more or less independent there have to be linearly independent well here is a quick and easy solution to this take the vendor undetermined take this thing . x 1 through excess and for the matrix where in each column you have the success of power would be given extra that we know that if we picked a solid matrix consisting of 2 came calendar this would get a square matrix which corresponds to followed interpolation this matrix admirable so the matrix satisfy the properties I wanted so it solve the problem but I haven't discussed element do decoding that you can think of many ways to do decoding I'm going just 4 naively voters an ideal Dakota would be I'm looking now I'd like my decoder to be defined for every why not just for the wise images of a farce vectors because the practice I will have that information so 1 might be voter to be defined for every so something you could do that why you look over there said Sigma and tried a finder's fees that best fits that is why minus 5 these balls possible this is a leastsquares problem of tried a final these leastsquares to wine from the image of Sigma under map 5 you can't be couple this problem namely a look at these the spaces that we introduced before that where TO the set of column series of 5 Cheney and we solve the least problem on said and forced we know we can actually right now what the solution is more general and were we have why Grammy matrix universal that defied BY so this already shows you where we need somehow that the matrix is invertible need known singularity and that we just search over all these he invited the gives us the smallest residual indicates that are Vector was image of up sparse back there there will be achieved for which they rock and a beer unique will pick up that by the decoding process OK sounds great and we saw their 1st problem gold and have a glass of phony your happy that we done something positive well I'm sorry to tell you that there's bad news here None of us will be alive when the decoding is finished that is so this decoding that I told you this naive decoding is horrible if we had a problem entered like a million like an image processing and little and the like of thousands In amended at the state capital and things take little another time Jack but a more serious problem it turns out is to coating is not stable now you can actually fixed the 1st problem you could find another matrix for example you could take off for a discrete Fourier matrix 1st and rolls of the discrete Fourier matrix and that by some clever Our decoding you can do this whole problem and this number of operations which is a reasonable number of operations for us so this is the real problem is that the decoding takes forever but the fact that the decoding is unstable is a real problem and let me just explain this to to you that were released back here in some sense because support lab that I am a generous Mansour like value where they vector acts what supported a ball that supporters and we now you only have defined don't have the final indices port you have to find the vector acts how would you do this what you have to apply this is the inverse operator and this of course we know in the example that I that I created that this is very poorly be here and in fact defies the wanting there have all week 2 case samples I'm stock I cannot do this in a stable way OK so what seemed like an easy mathematical solution a lesson to us what mathematically OK okayed may not be numerically reasonable well this brings us to actually wear from processing began and jurors not telling us in chronological order from press center began about 3 or 4 years ago and the work of Immanuel Kant there's nary now sometimes Justin Romberg & & parallel development by Dave and what they do is they show how create matrices that not only will recover 2 cases are factors but do it stable To do their when I have to pay a little bit when asked increase the number of flesh and we'll see how that plays out so they make and I'm going to talk about became towel development which I think is very elegant and very much of a point they make 2 important attribution 1st I gotta tell us what are the good matrices where they're gonna tell us a sufficient condition that may be good but secondly they're gonna handle the problem of decoding they're going show us how we can do that would out of the so that the property 3rd and introduced for the matrices of the following remember these matrices fight he and grammar matrices there a required we we say the Matrix satisfies the restricted isometry property of water case of whenever we pick came found the the eigenvalues of this matrix are 1 minus Delta 1 plus dealt here Delta between 0 and 1 of the important thing is the eigenvalues are staying away from V role entered they're staying Ballmer so this madam in matrix now not only convertible but it's nicely condition the last and no ingredients you could restate this property has followed you could just say that what you need is at whatever you apply vied to any vector Sigma the resulting vector have warm roughly the same as a normal backs that's where the word restricted I sanitary and if we could take Delta look and that's equal to 0 In this formulation that it would mean that we have an isometry but we give up a little bit and we have to to give up a a little bit now what about the decoding may suggest for decoding that once used at 1 minimization in this way so support we have our vector to decode what I'm going to do is look at all acts which may have been the wiser how pick the 1 which as a minimum out 1 or the other very simple geometrical description if I'd think of wire determines the site most of the ball a little Alwan I take the ball very small about the origin and load up like a balloon until it had this hyperbole when it's aside plan that would be the solution generically usually happens that it a unique voice now here is the main result of of by the way the important part about 1 the position as it can be solved by linear programming so we have a modest investment in the decoder for example we always know we can decode with capital and few operation near the main result of candles pal they say if you have a matrix 5 that satisfies is restricted isometry property now for 3 before I had to pay probably could replace 3 by 2 Caliente every once studied the not but what you have the property then you'll still your you can find a matrix with this if you have a matrix with this property then you use 1 decoding you capture every ex exactly that and every sparked by will be captured exactly but moreover the decoding is stable when our problem is OK with revenue matrix problem can we find matrices 5 less satisfied this restricted isometry proper and how we do that we thought would we build good matrices while I claim that given and then we can't go struck such matrices so will satisfy restricted I cemetery property of ordered case for every a lesson and divided by now all of a sudden you see a lot of fear and which pattern appeared before this is the price we pay for stability You can actually show that you can't discard the organist that it must be there if you want this restricted a cemetery property you're stuck with the so we give up a little before we could take a equal to an over to right now we can't quite kick take a large but only sacrificed by the Margaret now not that question I wanna discuss next in the next few minutes and how can we construct such a fine whether we wanna do while we're back to our problem of creating a matrix with that column matrix and our vectors an hour and a lot of them but now we want not only to just be there whatever we take to K of them working of them that their linearly independent we want to be very far from being dependent we wanted to be almost orthogonal sunset and I'm mentioned to you now 3 ways you can do that all these distractions or probabilistic the 1st away and we could look at the unit sphere and are manager choose our talent we simply pick and random according to the uniform distribution in the penalty random we take our how this would work another way as we could create a stop Catholic matrix what we could do is take 1 ear favorite distributions listed a golf and distribution would mean 0 and various won over at an art for the 1st entry just make a draw drawl the distribution of whatever number you get figured in as 1st the 1st entry and the maker and that independently repeaters every time you want an entry and thereby fill out your made you could do the same thing With a Bernoulli distribution with plus or minus 1 0 1 1 any 1 of these construction will work it will give you a matrix 5 with high probability that will work that is you do this realization that you control prove that with overwhelming probability the resulting matrix will satisfy the RIP property for this range that I never tires of protagonist of the best range possibly so we have a way to construct matrices I want to make 1 point very clear here where probability coming here because sometimes people get confused and that's what we use probability to construct this matrix 5 to prove the existence of 5 always knows we do this construction almost every matrix we get is gonna have the property we want once we have a matrix an army and the algorithm constructed there's nothing probabilistic and Alberta we applied why we play at 1 minimization and so on so probability is only used to construct if fragile because this RIP property is sold important this of interest that have placed methods the verified RIT and typically 1 would think that well this is an eigenvalue problem no approach through eigenvalues what I wanna point out here that actually there is elementary track to verify the RIP property in the settings that I just right for example in the calcium Berber newly case suppose I generators the stochastic matrix by taking draws of some random variables are below the matrix in this way the then the 1st thing to observers you could just about right now would file VAXes expanded and take the Norman you'll see that the expectation of the specter of norm of text where funded tried ball out what distributions about what probability distributions would work and creating these matrices that satisfy the RIP property so this is always put a hold rating distribution but we need more what we need to have more is that when we look at a given tax and we look at Wyoming go back then gets with high probability closed do it this means so we need a concentration of matter inequality namely that for Eddie given acts we have this estimate on the probability that these 2 things differ by Delta times form of acts this concentration of measured quality will be satisfied golf Bernoulli maybe distribution you ladies matter to show that the property is satisfied that I claim that whatever you have this then the resulting matrix that you created from the random process will satisfy the RIP property for the range of that you want this is and maybe it's not sold important that that this is true but what I want emphasizes approved because there are other ways as I met through Eigen value analysis to prove this result but there's actually exist this as a very simple analytic proved that I wanted us quickly draw upon so what I this what I do is say I need the on Sigma case I need to verify this restricted isometry property which meant that the norm of fire applied taxes like the normal all excellent Sigma case that's what I need so what I do it 1st I cover the unit's fear Sigma case some tolerance the Sidell over that I know that With this covering the a point for each that I told this this is this list of the concentration of measuring quality told me with high probability this is true with a high probability I don't apply to Union bound and get that uniformly true for all Q force you gotta be careful of poised to throw in there but do this and then finally you need to extended to every vectors said Mikhail not justices appointed discover and to do that is quite trivial for example the upper estimate you get made normal 5 by saying while approximated backed by a fuel from my neck and I have this trivial estimates for normal 5 and the 2nd 1 is under control because of this and the first one well any matrix on a finite dimensional space filed that there's some mild but course I won't get the best result this way with them but then I can bootstrap that's because once I get about 4 am I can repeat the process if you do that you'll arrive at this year OK uh I talk in the beginning about the bases is known me what can we do it the bases of people the subject talked frequently about the concept of universe salary while they random things they work for any basis but I caution you to be a little bit careful on this point let's make this precise make this precise if I'd start with any collection of bases and the number of based in this collection is controlled by need to the sea Kansas remember the number rose in America this same argument I gave probability argument can be used to show that you can prove the existence of 1 matrix side that will satisfy our IP with respect every 1 of these bases simultaneously for the hope there the rage of K that you would like the biggest range the problem show this is a sensitive Estate universe you could say that if you draw a random matrix with high and if you had been bases known in advance to this collect bases with high probability that will uniformly handle and Caldwell sparse singled with respect any 1 of these babies the problem is that we would need to know the bases to decode this is good for encoding but not good for decoding for some people talk about well in code 20 years later coal in all put in time capsule well normal too many applications would people 1 of wait 20 years but OK that was my 1st example of lock up the melody was the simplest now I wanna go to more general so we know that the real world signaled are typical the the sense that I mentioned they're gonna be there I gotta have supported only a finite number of the terms were small number of terms there typically don't have a lot of entries in them but in general most of these entries are going to be small In our idea remember as we began was that we said that we view signals has but being approximated well by by our signal that is they have only a few components that are essential to capture them and we only need to find those components so to make this a meaningful discussion I wanna talk about Pollock a signal that can be approximated by fire signal so I introduced a measure of error so you can choose whatever where you want to measure Arab Normac maybe for the fog of fake Texas the leastsquares helped to end MND given the vector acts we look at how well I can be approximated by factors which have support case so that there is nice if there's no law 100 vector like hundreds of 400 that approximated well we think realworld signals are not sold mathematically weekend so were interested in classes of signals which in which we know that they can be approximated well and typical way to get such classes are the following you could take the Uni Ball but help yet so for example if you wanna measured parallel to and then I suggest you to take a few equals to hear that any vector and LP and will be approximated by he turned the sacristy no look at this moment as he gets small town near small better than large won't means that they vector acts on the components of it dialog very fast if you order them inside and you'll have this PKK the 1 of the few minus 1 over piece of this in a very very fast is very small for example of fuel Tool and you take a veteran unit ball about 1 then it can be approximated by terms sacristy won over scored a case this is easy to united don't stop from the well I mean backed the melody in the 2nd set up melody now will mean I have a class of Signal capital case and I have some more which I'm gonna measure distortion or error and I say that sensing system is not Saturday if if it performs like this Min Max over this main Max says of a letter look at how well we could possibly performed the best performance we can make by systems of size and that is the matrix has has a dimension little by capital we take such a matrix and a decoder and we apply this will given actually achieve a certain error and how we look at this be error of overall X in the classic case of this is the usual Min Max way of doing things we look at the worst terror that we look at these systems the fire doubt that give the best worst terror so we take TMobile overall and I would say it a a system is near optimal if I have this kind of an inequality with some absolute nor if I had seen Audi will what I'd have optimality there would be nothing better but usually you have to give up a little sore so this is interesting Thunder stay on for a given class of signal does this he and behave what's the target was the best we could possibly do that the usefulness of beer and tells us the best we could do and the story is that this behavior he and war classical set case in R and his aware that not only known but was not a long time ago in the 1970 the early eighties and the context of finite dimensional geometry or geometry but experts the main players were passion and blue skin I just mentioned 1 result for example 5 I look at the unit ball 1 hand and asked what the best encoding decoding I could do with that and help to what I measure their 2 and then here is the estimate notice the estimate from a barber below are the same order the only thing differs are the 1st of 3 0 1 the estimate is basically 1 over supported 1 over scored and would be what we could do if we chose the investor of the vector and we pay a little price here log of capital over little Lanagan remember we had that before and this price we know it is necessary paved the way of a lower estimate now a I'd like to say why it was that's not a solution to the compressor sensing problem back in the seventies the thing that these players did not look at lawyers practical and decoding or how to implement this encoder affected never touched the product the problem of decoding and a contribution of candles and talent all that they show that if you have a matrix with restricted a cemetery property and S L 1 minimization then it will be at near optimal performance single this type of performance not not for every human peak but for certain chuan P for example if you want a measure parallel to tool for every P less but 1 of the optimal so they give a practical scheme and once you have this game now you're happy because you know that you're doing the best we possibly can let me say just a couple words about this because there is no would controversy but I talk to people of functional Alice's what these guys press that thing just doing our work all over again and so on but this is not a fair statement because as I mentioned to you they did not discuss the practicalities of the decoding so their results are useful and interesting but didn't discuss practical decoding What is the most useful but the result is the law by turns up because it tells us we can't do any better but it doesn't give us real practical schemes to do including fighting both camps have made a great contribution now I wanna go to my 3rd and last way of measuring up the melody and that to me if if you mistakes to call this the Cadillac of war about ways of measuring optimality Germany would be Agustin MercedesBenz space but a with what I I want to have the melody in a very strong said here the center aisle say that this encoding decoding scheme is it is the optimal of order case if the following hold every vector right I don't need it in any class or anything like that again it back when I encoded decoded performed like a term approximation well this would be terrific if you could do this for large values of day for example if you have this and you can return to your 1st problem and if you take a vector which is viruses will be there also encode didn't exactly it will also include all the results optimality for classes so this to me is like I don't think you could get this is like a dream but if you could get this would be the best possible way and a problem is that supposed to fix the size of the problem the size of that the system to reduce the number of road you're going to use the new matrix and the question is how big take case and achieve this not the melody and with Elvera Conan both going and we solve the problem all wanna a measure the error In any help you face feud between 1 and 2 and I'm just gonna mentioned a couple of so there 2 things to say want good new the good news is that you have instance optimality 1 and you have it 4 K of the raid that year the most you could expect a namely came less and log moral or were you can build this system and use Alwan minimization of the decoder so you can actually build a stable system and Abbas's but the melody and this result although we prove it in are our paper you can't it essentially files from the work of candles and so that was a good now the bad the bad news is that if you asked for instance optimality and help to you want a measure in the where to the bad news is that you kid even ministers after melody of order ask you pick number of measurements is roughly the same as the like the back there what we don't want that were tried have little and small we don't want a little and big for this says that it is just not the melody and help Tula doesn't seem to be a viable cancer but what happens in for altitude between 1 and 2 and you start mediator from 1 of the other near 1 you have almost the same as them at once and he moved to 2 Q equal to measuring their NLQ nor the situation deteriorates until when you get L to it completely falls apart while there's there's some recovery although I said His does after melody and helped who was not possible there is a little bit of recovery and I think this is an interesting fact that you can recover so I wanted to leave the game a little bit sold the game I've played so so far has been you create once and for all a matrix 5 you create once and for all a decoder and I use as system over over Over here now want a change a game when I won allows was a different game that I get him I want things that I have a lot of bunch of the encoding scheme for example I have the Catholic matrices than I can grab any 1 of them that I won and I start with a vector acts and I roll the dice and grab 1 of these aspic matrices can I use it for my encoding and I coated and somewhat an ally has OK I know that America and be able to do for every act with certainty that instance optimality but maybe I can do it with high probability ministers out to be the case and to describe this I need to tell you what types of matrices what what do you need about half the cast matrices to make this the source all that I have a collection of random matrices I want this collection have 2 properties of forces as I wanted to have the restricted isometry property of order case with high probability what we know that we know how to create such major cities that would make the drawl that they these did resulting matrix will have restricted us oratory property with high probability so I want this in a 2nd thing I want is I want it to be remember the respect I son 3 property applied vectors and Sigma case here I wanna have filed the property with high probability namely that for every vector acts in our hands a with high probability that a random draw this matrix when I look at 5 may applied tax is Norma's control but that's times norm now we know in general given given and acts in general we can't your letter given the Matrix viable mega what a stuck footing in different axes for some Exs this is gonna be big nor gonna be bad but we also know that the probability there's gonna be big smile remember those concentration measure quality they they said the probability of this was small so it turns out you can have matrices satisfy the property the gals the Burnley they'll satisfy these 2 property and I here is the fear of the fear of support you have off collection matrices and they satisfy those 2 property then went high probability you're gonna have vistas optimality namely figure acts draw your matrix of random fighter encoding and decoding then with high probability you're going to have assessed so should would be happy with results of high probability I thanks so I think it's made if you know that you could do something with probability 10 to the minus the probably more certain than anything else ever do in your life so I think results in high probability yards OK and arrange again as the same range as we could best we could expect an unfortunate part of this is as it they presently stands the way we prove the theory that we use the leastsquares minimization saying that we can really do minutes off the comet oral search over all the space but I believe that up would probably to won the position we just have to look at them with the content of the talks but I wanna make Nelson comments about where are we whatever we tried where are we sold talk about 3 subjects years amplify a little bit further give you an idea of what where we sit all this talk about Apple matrices remember I my whole thing was that what's optimality and to build up wake the optimal matrices with belt whenever we ask for optimality in terms of performance are vector instability in addition the only way we know to do this is through probabilistic met so interesting to ask could we do this through determine but structure now I wanna be a little careful on because this need some thought what do you mean by determined because let's think about our our Bernoulli matrices we know we can create matrices with 1 0 0 that Apple we prove that by probability that what we need is that this restricted isometry proper given a matrix I can check to an isometry property not realistically check it would take forever to check it but From countered from world if they determine as they did not have enough people working jacket soul I could die right not all the roll 1 matrices are only a finite number on check there for restricted a cemetery property until I get 1 and I've got matrix their work so I ever determinist a construction but this isn't fair to me this is a determinist a construction so I have to be careful about what I mean by determinist a construction and maybe what we need to do would make the precise state what we mean by determinist maybe it means that you have an outgrowth of that column only time will assemble a matrix that has the property but we at present we have will determine a stick construction that give the type of former said we want that gives us a highperformance that is that we have to take very few sample remember we had we could get by part of the sparsity was then the number of samples and with just a little bit bigger than what you can do and this is very poor man ruled for mysteries do this if you could prove that but through using matrices from cotinga finite field you could prove that so you could construct matrices really construct the path that would give sparsity perform at for K less than forward at hand while that's far from here so were far along with way from having a good performance look is 2nd topic I wanna say a few words about computational issue I have tried I made the following there were 3 ingredients a Kmart when we started discussing optimality 1 with 1 optimality in terms of the varsity level we wanted to be able handle signals as possible case a secular they came up with the number of computations you needed it want to implement hero and the 3rd 1 was stability and these things play against 1 another when you try 1st aspires to level up then you have problems with computations and have problems with bill has not been sorted out yet exactly what the story is what are the best result solitude if you fixed buyers city a level our you force they have spent so much time decoding the best we know right now is Alwan minimization decoding the linear programming could be water and cubed hit we do that this is not understood 3rd things that are being done fortunately I don't have time to mention it in their article Computer Science Gilbert Krishna Strauss and many other people in this is a problem that really fits well of theoretical computer science of churches and people from that area the audience saying well we do this all the time and the sort of true and they have results but they don't come Close to answering this 3 out of the questions how these they introduced other aspects of computation into picture finally were really interested in building practical scheme right and they were not just doing this for for the fun of it all those lights interesting mathematics we would like an analog signals original problem was would have a cell phone conversations or or our radar chirps out there and we want a bid a fine grab that's the whole purpose of compressors and so we really want analog on we wanted him handle analog signals so how we go from this treaty analog This is not completely clear the waters are very muddy here and is not sure there were gonna really be able to do this in a way that we would like moreover I want to say that even if you mathematically full conceive of the system that would work an analog you have to keep in mind that we wanna build the sort put and are worried when you when you start putting things into a circuit it'll all the sudden is not just like even America amputation you have more serious problems to to deal with our souls but To get the big day there were hoping for and signal processing is not there yet but I do wanna mentioned that there are already impressive applications of the compressor and protect their Immanuel Kant part and tomography and I'd like to recommend that you go to manuals talk of taking place here which takes place last Friday OK 1 last thought year at all interested compressed these ideas there is a website at right a electrical Computing Engineering and I had fairly uptodate all the papers dealing with the press and think surely more than a hundred of them now and it's an interesting areas if you want to you can easily get into it from that perspective thank you very much