Renegar's Condition Number and Compressed Sensing Performance
10 views
Formal Metadata
Title 
Renegar's Condition Number and Compressed Sensing Performance

Title of Series  
Part Number 
3

Number of Parts 
10

Author 

License 
CC Attribution 3.0 Unported:
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. 
DOI  
Publisher 
Institut des Hautes Études Scientifiques (IHÉS)

Release Date 
2016

Language 
English

Content Metadata
Subject Area  
Abstract 
Renegar's condition number is a datadriven computational complexity measure for convex programs, generalizing classical condition numbers in linear systems. We provide evidence that for a broad class of compressed sensing problems, the worst case value of this algorithmic complexity measure taken over all signals matches the restricted eigenvalue of the observation matrix, which controls compressed sensing performance. This means that, in these problems, a single parameter directly controls computational complexity and recovery performance. Joint work with Vincent Roulet and Nicolas Boumal.

00:00
Point (geometry)
Complex (psychology)
Statistics
Observational study
Presentation of a group
Transformation (genetics)
Direction (geometry)
Multiplication sign
Complete metric space
Solid geometry
Number
Explosion
Mathematics
Goodness of fit
Thermodynamisches System
Manysorted logic
Natural number
Subtraction
Descriptive statistics
Condition number
Series (mathematics)
Pairwise comparison
Focus (optics)
Convex function
Coalition
Optimization problem
Exponentiation
Content (media)
Bound state
Algebraic structure
Independence (probability theory)
Limit (category theory)
Measurement
Arithmetic mean
Hausdorff dimension
Normal (geometry)
Mathematical optimization
Resultant
08:46
Complex (psychology)
Group action
Direction (geometry)
Multiplication sign
Parameter (computer programming)
Variable (mathematics)
Independence (probability theory)
Mathematics
Invariant (mathematics)
Meeting/Interview
Charge carrier
Hausdorff dimension
Descriptive statistics
Physical system
Logarithm
Block (periodic table)
Generating set of a group
Gradient
Parameter (computer programming)
Functional (mathematics)
Maxima and minima
Flow separation
Concordance (publishing)
Sparse matrix
Arithmetic mean
Hausdorff dimension
Right angle
Physical system
Point (geometry)
Ocean current
Classical physics
Divisor
Transformation (genetics)
Set (mathematics)
Modulform
Mathematical analysis
Mass
Affine space
Number
Tabu search
Frequency
Thermodynamisches System
Iteration
Subtraction
Absolute value
Linear map
Condition number
Pairwise comparison
Addition
Focus (optics)
Sine
Newton's method
Model theory
Exponentiation
Algebraic structure
Independence (probability theory)
Set (mathematics)
Local Group
Estimator
Mathematics
Computer animation
Function (mathematics)
Iteration
Object (grammar)
Limit of a function
16:35
Axiom of choice
Complex (psychology)
Greatest element
Curvature
Euler angles
Logarithm
Multiplication sign
Decision theory
Water vapor
Mereology
Order of magnitude
Glatte Funktion
Explosion
Maxima and minima
Order (biology)
Mathematics
Invariant (mathematics)
Matrix (mathematics)
Manysorted logic
Square number
Position operator
Descriptive statistics
Physical system
Logical constant
Coalition
Process (computing)
Optimization problem
Gradient
Moment (mathematics)
Staff (military)
Bilinear form
Functional (mathematics)
Maxima and minima
Flow separation
Category of being
Vector space
Graph coloring
Normal (geometry)
Right angle
Bernoulli number
Point (geometry)
Classical physics
Divisor
Set (mathematics)
Distance
Discrete element method
Event horizon
Affine space
Number
Mach's principle
Kritischer Exponent
Latent heat
Goodness of fit
Thermodynamisches System
Iteration
Term (mathematics)
Average
Boundary value problem
Normal (geometry)
Field (mathematics)
Subtraction
Game theory
Condition number
Addition
Image resolution
Chemical equation
Newton's method
Projective plane
Entropy
Computer animation
Convex set
Function (mathematics)
Combinatory logic
Iteration
Game theory
Coefficient
Mathematical optimization
Matrix (mathematics)
Spectrum (functional analysis)
27:37
Logical constant
Axiom of choice
Complex (psychology)
Group action
Multiplication sign
1 (number)
Weight
Mereology
Mathematics
Sign (mathematics)
Manysorted logic
Insertion loss
Meeting/Interview
Normed vector space
Covering space
Logical constant
Product (category theory)
Optimization problem
Closed set
Gradient
Interior (topology)
Physicalism
Functional (mathematics)
Measurement
Metric tensor
Maxima and minima
Arithmetic mean
Normal (geometry)
Point (geometry)
Product (category theory)
Minkowski space
Transformation (genetics)
Distance
Affine space
Scheduling (computing)
Frequency
Thermodynamisches System
Causality
Simplex algorithm
Normal (geometry)
Symmetric matrix
Addition
Lemma (mathematics)
Mortality rate
Gauge theory
Point reflection
Enumerated type
Convex set
Function (mathematics)
Coefficient
Distortion (mathematics)
34:16
Logical constant
Complex (psychology)
Group action
Euler angles
Gradient
Logarithm
Multiplication sign
Direction (geometry)
Sign (mathematics)
Mathematics
Invariant (mathematics)
Manysorted logic
Meeting/Interview
Square number
Daylight saving time
Uniform space
Logical constant
Spacetime
Gradient
Propositional formula
Parameter (computer programming)
Functional (mathematics)
Measurement
Maxima and minima
Hausdorff dimension
Simplex algorithm
Normal (geometry)
Landau theory
Point (geometry)
Geometry
Divisor
Set (mathematics)
Student's ttest
Regular graph
Discrete element method
Affine space
Number
Latent heat
Regular graph
Thermodynamisches System
Iteration
Simplex algorithm
Normal (geometry)
Analytic continuation
Subtraction
Condition number
Standard deviation
Focus (optics)
Model theory
Bound state
Independence (probability theory)
Set (mathematics)
Estimator
Computer animation
Function (mathematics)
Universe (mathematics)
Iteration
Object (grammar)
43:02
Axiom of choice
Logical constant
Focus (optics)
Logical constant
Product (category theory)
Logarithm
Multiplication sign
Infinity
Affine space
Variable (mathematics)
Power (physics)
Maxima and minima
Invariant (mathematics)
Computer animation
Boundary value problem
Normal (geometry)
Uniform space
44:22
Complex (psychology)
Complex analysis
Logarithm
Multiplication sign
Affine space
Number
Glatte Funktion
Iteration
Meeting/Interview
Square number
Boundary value problem
Logical constant
Spacetime
Physical law
Bound state
Infinity
Functional (mathematics)
Power (physics)
Entire function
Approximation
Estimator
Maxima and minima
Computer animation
Function (mathematics)
Iteration
Absolute value
Mathematical optimization
Mathematical optimization
47:06
Classical physics
Complex (psychology)
Multiplication sign
Sheaf (mathematics)
Distance
Number
Frequency
Sign (mathematics)
Matrix (mathematics)
Thermodynamisches System
Iteration
Term (mathematics)
Charge carrier
Feasibility study
Descriptive statistics
Linear map
Physical system
Condition number
Addition
Link (knot theory)
Spacetime
Optimization problem
Point (geometry)
Interior (topology)
Bound state
Mathematical analysis
Independence (probability theory)
Algebraic structure
Parameter (computer programming)
Measurement
Connected space
Computer animation
Equation
Normal (geometry)
Right angle
Iteration
Object (grammar)
Mathematical optimization
Spectrum (functional analysis)
52:06
Classical physics
Complex (psychology)
Statistics
Group action
Image resolution
Mathematical singularity
Mereology
Variable (mathematics)
Maxima and minima
Iteration
Term (mathematics)
Descriptive statistics
Condition number
Social class
Pairwise comparison
Eigenvalues and eigenvectors
Optimization problem
Price index
Metric tensor
Concordance (publishing)
Arithmetic mean
Numeral (linguistics)
Computer animation
Numerical analysis
Phase transition
Mathematical singularity
Theorem
Dependent and independent variables
Pressure
Mathematical optimization
Gradient descent
55:17
Axiom of choice
Logical constant
Point (geometry)
Complex (psychology)
Statistics
Divisor
Set (mathematics)
Multiplication sign
Insertion loss
Mereology
Perspective (visual)
Event horizon
Open set
Mathematics
Centralizer and normalizer
Invariant (mathematics)
Crosscorrelation
Matrix (mathematics)
Thermodynamisches System
Meeting/Interview
Natural number
Statistics
Normal (geometry)
Product (category theory)
Prisoner's dilemma
Projective plane
Bound state
Nominal number
Set (mathematics)
Functional (mathematics)
Measurement
Open set
Estimator
Metric tensor
Computer animation
Normal (geometry)
Right angle
Resultant
Spectrum (functional analysis)
Matching (graph theory)
Directed graph
1:03:04
Computer animation
00:02
so what time of year the the move thank you and I'm not very good for the for the station and and for the opportunity to talk during the years sisters that I conclude that a WiFi whatever and so on however I should start by saying that this is joint work with a number of people including systematic was manned vessel it was in the home and is going to be listed in the 2nd African finance well you wait a year and a half and the crew of now Princeton and multimedia news not given so the the title change but the content than in the same time it and and the content is a lot simpler than what the title of this sort of because so the idea generally is that when you get a complex abounded with it looks like this "quotation mark free speech the various of independence on the pollen dimensions and the sudden dependence on the target precision that generate code ,comma complexity musician problem in this case your lucky because the exponent is not too high at Saitama this is what a lot of the looks like again if you're lucky it looks a bit like this the midmorning and where now you have a religious constant and at least you have some dependence on the problem structure OK but clearly wanting important is missing from this complex and this is the data right the complexity bound you get on the complex of musician policy of trying to solve only a very very loosely depends on the problem data and if you want to study competition tradeoffs or competition complexity versus this fiscal performance tradeoffs In general the fact that you're Bond on the complexity of the problem you're studying socalled and so the dependent on the structure of the other the ties of the issue OK noted this is of course an above answers to begin with so the it's hard to make comparisons between the complexity of values optimization problems using only local bonds it's even worse because this upper bounds is very loose and in particular are only loosely dependent on the public data and so did the general idea behind the 2 quick results I'm gonna presented a case to gets closer to datadriven complexity look at it and hopefully get closer to something that would be died even complexity bounds on optimization problem OK if you want to start to make comparisons between the complexity of ideas of musicians problems if you need something more than ample grounds you need time announced on the complexity and if you want to compare problems based on their structure indeed bounds that depend on the column structure and on the data in a meaningful way look at and so will the material I'm going to present today's NFL in that direction and of course it's support topic and this didn't do too the president's umbrella presents to the largest very specialized residents in this action but that stood united in 1 bit that complexity abounds that hopefully uptight and allow you to quantify in a much finer way what happens on the competition side when considering and comparing the statistical optimization of solid optimization problems coming from statistics for example so again if you're studying the complexity of gasses that fiscal performance tradeoffs well it helps if you have a fine description of the complexity aspect OK on at this point we don't so you could talk a lot about the this this this tradeoff but at least on the complex decide on measures of complete problem complexity and we get a late to the problems touches on we epoxy became pretty far from the and they suffer from a certain number of key deficiencies among these deficiencies is a fine invited OK so it it makes sense that if you're going to describe the complexity of the problem the bond you use to describe this complexity should not be affected by elementary transformations of your problem OK and in particular on the shoemaker symbol of fine change of coordinates the complexity of your problems should not change just our normalization should not have any impact on the complex human musician public yes when selling itself OK so I guess you implementing this on machines have sold machines are finite precision so obviously there are limits to what I'm saying but on the other hand it's it's not OK as Richmond a report having had a hand over it's a matter of all of us nice if a fuel problem can be fixed by a simple fine change of coordinates perhaps your message should be smart enough to recognize it that's so it's setting the Bobbitt high against maybe but at least as far as I'm concerned may be ongoing should be robust enough to recognize that you know the problem now facing simple condition and do I going concern should be all vestiges conditioning the coalition in the face of the condition number is not defined environment for mean conditioning starts and so but that's the precise point so it's a conditioning issue you can fix it by just changing coordinates but what I mean by by I find invited is you make enough fine change of coordinates you don't expect to your Parliament changing nature OK in particular you haven't done anything to yield data so if you're looking at statistics John and manufacturing data are uh it's simple a simple preprocessing step you could do with said got so this is something that should be within reach it but I I agree that it's is partially subjected this new embody the reason for this to be true but if it if it can be a tool it's a good really believes it will take a look at Is that OK the free to question my motivation is even more the focus so fighting violence is a good thing and we want more good things in optimization that's sort of the essence of the limit and so that's the 1st point so I'm gonna start by talking about the finding Bayern's can we get it and if yes what does it say and submit separate but equally important importance of 100 gas condition number and compressed sensing so this would be again and again in the sector different direction but in the sense carried out we see that in certain cases like complacency and problems the same quantity of drives both our competition complexity and statistical performance so In this particular case were lucky because we have a single metric for both competition complexity and sponsor recovery titles OK so in decades the problem is solved in general course it's still OK so often what I consider a very simple generic optimization public you minimize a convex function as overseen by the compact complex OK and you can assume here that it's complex and smoothen I'm going to make all this precisely at her and that she was combatants against symbol will be made precisely look at the rest of the general public more interested and is doing and Sekulow which we optimize is not tubing and we have a complete series fall this problem
08:47
OK so we have Newton's method and that Newton's method that instigation there's a simple thing it takes a step in the direction given by the gradient but it normalizes the step up by Twohatchet OK and if you assume that the function is Centcom Collins and that the said she was a sitcom called own you have very explicit estimate on the complexity of minimizing a complex of concordant functions using Newton's method if you haven't seen it before cervical Golden of the sitcom called assumption fees and beat the bizarre to say the least but if you think about it for a 2nd you see basically just 2 things at the same time if you the made it in 1 direction it's essentially a lower bound on the 2nd diversity of the function and so it's a way of writing strong complexity while maintaining our a finding violence in the conditions and if you read it in the other the action then it becomes an upper bound on the absolute value of the severity of the functions and that's a way of saying that the 2nd direction will not change too much when you move from 1 point to another and that of the musician in general just about minimizing clotted functions in end and what that's exactly what Newton's method that is OK and so instead of twitching why this is the right set of assumptions they were using air quality model to minimize or function and you want this cluttered model to women pulled even outside your current point and that's why you buy you need to buy the severity I think so this bizarre but in the end it is simply a way of combining both an upper bound on the solidarity and the abound on the 2nd directly and to do so in a way that makes the condition environment which respect and I find a change of coordinates into .period X OK and this is why you have this exponent 1 . 5 here OK so everything it's it's bizarre but everything has a name and once you make that assumption you right you use focus on solving a a problem of course you need to buy itself to be said concordant but basically then you can buy on the number of iterations required to get a solution with precision excellence by some coefficient times did the difference between the value of the Biondi initial point and it's about to press love of logs of 1 red mutations OK and for all of these numbers values of epsilon this is basically free and this summer's here depends only on parameters that you said for the Lions surge In the Newton step OK so you decide what the value of these parameters on and other face typically something . 2 and be ties . 5 so this this is a fixed quantity OK so surmised the
12:05
complexity of Newton's method is basically freed so the number of iterations you need to wage essentially any precision is bounded by something like 375 times each of you is 0 minus minus each song classics again that's clean enough for me I don't know about you but did then OK but it's some I'm taking bellied up to a factor solidstate 300 and is back a bit of a it's a constant and what's striking is that is not in sight is about sewing particulates independent from the dimension and which is pretty spectacular and again this is objectivity and it's also a fine invited of course because it only depends on the values of the functions OK where the only thing missing from this bond is the cost of solving the Newton system the ticketing system but that's just July so this is something you can measure very precisely from building up and structural problem it's just just conditioning press problems touches sparsity block structure at the top but you can get a very fine estimated the complexity of solving the cake at the system using simple knowledgeable procedures because of this and this is some conditions for this year the efficiency of Salinas's said his does that if you look at things in a slightly more precise when I will at the end of the talk but but overlord it is the number of iterations vise between 15 and 20 well and so did the the cost of a generation clearly but you at least you you can read it directly from the data so you can write the cost of serving the Newton step as a function of the problem structure dimension it's a block structure things and that and the data conditioning so you have a completely explicit data even description of the complexity of your problem OK and this is what you're looking for it's a fine environment and it fits into the structure of the data work and in particulate you want to compare to problems you just come down the complex system OK coming from the knowledge of our size so at least you have an upper bound that's useful for making comparisons between the complexity of vise problem UK which is something you don't have fulfill solar masses that's my next goal is yes the question of how the days of age and like you the licenses saying it was using Group .period arrived there should be 12 years clearly yeah scared somewhat but it should make a difference and no I don't remember exactly but that I know it's a nonissue I can't tell you what looking soul this is the picture for Newton's method and especially the topics completely closed OK so we know exactly how many how to balance the number of iterations the myth of ghost who and we know exactly how to measure the cost of these situation so you have a problem and you can describe very precisely How much is gonna cost to solve it numerically using Newton's method meaning when you have 2 problems you know which 1 is going to be more expensive than the other OK so that's the beautiful world of school smallscale problems yet so that in addition to that of mentioned it several times but Newton's method is a fine invited meaning he should do and I find change of God in history of public there dates of Newton's method applied to the transformed problem we simply media are fine transformations of the dates of Newton's method on the origin of a problem formulation meaning that in particular the number of iterations hasn't changed and end the complexity bound isn't changing and so you have enough I'm inviting complexity Belmont on enough finding vines procedures and so again this is very
16:36
important to the future so the problem is that at at a certain point and your problem becomes too big and you can't even sort of a single instance of the kick it system let alone on several occasions of Newton's method of cooking and and so on Beyond the substance came 2nd all the information is out of reach you cannot form the Hessian also indicated his system and 2nd although information it is what makes Newton's method of finding buyers OK so what people do is just stop 2nd order of of the information and used gradients instead 1st although information and but the problem is now can we get similarly clean complexity bombs fall frost on the methods that are tight enough to say something twin meaningfully about the complexity of the optimization problems and satisfy some of these environs property OK and the answer is yes in certain cases so just to come back to America and that is a big favorite among some members of the audience and if you can't find water for example which is also known as the condition gradient method on the field off method at each iteration is sort not finding a musician problem is vector is given by the gradient and can you get an extreme point of the feasible said to take complex combinations of these extreme points and magic EU converged and somewhat the more magically you can show that the complexity of of the form of a fire going is bounded by 4 times C est divided by the targeted to the target position at West CFCs abound on the curvature of your function OK and sewage the good news about CFL this complexity estimated status symbol in itself but the additional piece of good news about this boundaries that CFCs environment which respect find change of coordinates In your public OK so that's excellent news the only issue with this is that in many cases the defendants in the target President excellent it's about bottom OK in particular when it has a Lipschitz continues gradient then the long bond can be as low as 1 over square motivated cancel your mom is nice but it's really far from being talked and it's kind of useless if at some point 1 for example to compel the complexity of the report guests this life isn't actually flavor into the fray stretch of scale function by some of the largest 3rd appropriate did its distance here if you put it in here and you get a fine violence of efficiency In was the overviews alleges they say that a little but as this is is the financial yeah it want the walls of the coalition losing scientists along with just that of the general called so is it that is you make a certain number so you have a certain number of facts about your problems smoothness of the function like the light said that that are so you you have a black box and then you have a few Liu open delivered the black box and you know a few things about your problem and suddenly so if you only have covered cheered and things of different but if you know for example that has allegiance gradient then you can do better In terms of excellence what you you need to know more about Q 2 women is that if this was universally optimal and I fine environment wouldn't have a problem this is a list of the will of the gods this involves a yes but what I mean is that in certain instances you have more than that and in that case then you have to use another ongoing if you want to be as close as possible to the bombs and these other methods will not have enough uninvited that's what I mean so it of course this might give too many in certain scenarios but when you leave the scene I used a new and troubling because suddenly you lose your your method you all the best option for solving a problem doesn't have a clean complex development that's what I other questions OK so at least we know it's possible for 1st although method To have enough finding by so it's not the fact that we're losing 2nd all information that makes it impossible to produce invited OK it's really about the Guyton design and the way we bound the complexity of the matter where so you're sort of classical method that features lower complexity bounds faults Moussa to musician for example is the staff method of 1983 OK the origin paper was inundated in setting but in the general case I G I going requires you to do 2 things OK so it's fully specified that to a certain number of choices OK so in particular when you write down Nextel's method for specific optimization problem the general right not the 1 in 1983 you have to choose a going and that none is important because when you say that the and has allegiance continues to story that the agreement is achieved continues with constant and which respect and on your choice of only affect and and you change and then you change your context about you choose army that has an impact on complexity and once you've chosen the nonuse of need to choose pox function for the attitude and you want talks function to be ,comma Convex which respect to your choice of not again and again this hunk of St which within the context about so how you choose the path we have an impact on the problem complexity OK and then once you've done that Diego I'm basically computer gradient this tool Hollis projection steps averages dollars out to end italics again and it would produce an excellent solution In at most as Square of 8 NDX town divided by a tenancy and now the dependency in at Sudanese up too much because it's more in 1 overs quota that's however the constant and and Sigma used in the description of that balance on that environment which respect when I find change of government and so on it would seem that consummation of the public you skater apologize and 78 of the complexity can vary message so when you say to here when people say to here what they really mean is ultimately which respect website in the general case if you don't really look carefully at how you choose your moment how you choose your parts there's no reason for the nite here to the optimum and and not only that this Snyder can have a very significant impact on the complexity of the problem OK and we also this marital makes the complexity balance value which define changes color of coordinates in diligent public OK so this is something you would like to fix so in part to get what you want is abound on the complicity of additional funding that is not only about 2 million excellence but also in everything else OK you want to complex demand that its ultimate onto to a constant factor just like what we got from Newton's method and the problem is that you cannot write such a ban on using the quantities and Sigma and for that matter next all these quantities are the depend on evaluating finetuning of God annual OK so we have to find something else to write this complex demands and make it a fine environment and we also have to check if there's something else is optimal OK in the sense that it matches the best possible down on this
25:17
Snyder cares sold just to give you an example of what destroys of Norman talks function means I suppose you look at the it's an example taken from a paper by the users skin announced :colon and appeal where you have this simple matrix game public so it's enough find missing skin problems and you have some small thing to do its job and that is metal to much here but if you pick an setting and in this case the square the kid in parks you can bound the number of iterations by 4 times the spectrum norm of the Matrix a divided by and 1 if on the other hand you think it would be more carefully in PGA 1 arm and public parks and then you bound becomes "quotation mark of Logan Logan Max coefficient so the maximum the Mac's the magnitude of the coefficients of the Matrix OK forget I'm using the same excitement and getting the same dependence on the number of iterations and however reminding writer is changing very significant and for example when matrix down the difference between these 2 terms as "quotation mark event so the method may be optimally next year but if you don't get attention to your choice of Norman choice of parks you can still be effective from the best complexity nonplussed again and that's a big deal OK so a question of the environment there is also a question of 292 you want the best possible implementation of the optimum effort to make it fast if the land is the number of iterations it's not so after annotations you instead that decision the last of the 1st no enemies did number of uh 0 we will wait no OK so it's a or whatever makes it quite so I'd heard this should be the precision and this number of iterations of the opposite but not both at the same time .period OK but you see what I mean OK sorry so this should be under its Illinois and whatever you prefer and have a little more
27:39
and so OK so I hope I convinced you that that choosing the nominee and choosing the parks had an impact and was an important step and if you want things to behave properly this should be done in a principled way and I am here in some sense looking for a finding of I'm bound that sort of timid bonds of gonna be for a fine invite going so the optimal enumerated are in the Hindi complexity of the problem is going to be I find environment because you can always do not find transformation of your mom and of the normalize your or your coefficients OK but that doesn't mean that and if you get enough finding fineboned it's going to be a but looking for offline and violence is probably a good way choosing a nominee and choosing epoxy just have to check afterward that which emitting is indeed an ultimate effect and this will turn out to be the case here so think about it for a minute if you want your choice of Norman your choice of parks to be environment it cannot come from outside of the public OK if suddenly you decide that your mom has to be a Clinton there's no way if it doesn't depend on your problem there is no way to invite as your problem OK so you have to exploit your mom and your parks From the problem it said and this would to stop doing that in certain passages in Iowa's 1 is when is a century symmetric a convex set with nonIndian Jr In that case curies do you need more of an and the natural normal to peak Out of Your optimization problem is the 1 corresponding to choose OK the Minkowski gage of Cuba look that enveloped along the news and what makes this a particularly good choices is that when you pick this June known has the underlying on defining you underwrite the corresponding Lipschitz constant constant for the gradient we'd be environment which respect when a finetuned of college so you do enough I'm change of coordinates to your problem and if you pick the new Pudong corresponding to the transforms the feasible said but it would have the same features ,comma do do great and we have the same interests constant which respected transformed on then which respected the origin again so choosing the long corresponding to the fees but said it makes your Lipschitz constant and a strong complexity constant of the parks environment which has spread to enough and change of college so that seems to be a good option now the last thing that needs to be done is to choose the talk and
30:36
vultures in the past I need to stop at 2 quick definition yes it is used his youthful years since the advent now you have to do a little bit more and I don't have the words if you take the simplex then it makes sense to simmer tries it and then then it becomes a 1 more than he was year exploded and I wish I had the general answer in that case but I don't at this point so we can cover Central symmetric and everything that looks or can be but done into a centrist metrics and filled with the unity schedules coitus yeah so it turns out I'm going handle as discussed in a few signs a case where we optimize simplex and where we should they do 1 more everything works out fine in the Himalayan Tahiti this litigation in recent years the designation of being reduced 74 was on political opposition to the EU voluntary from the only political opened for I have no idea I mean that I don't so so far only centrist metric is is easy but indigent yes that was the vision of Ministry that squaring off the and all it was really looking like this and why do you do you can have synthetic and we're just get in 1 arm it's likely that illegal physical said Costa Close to you a wife was the issue was the cause of function in the middle of the the solicitation by buried may be yes it's just that still needed nonIndian and so the problem is how the weight of all Bodman of the yeah would .period maybe but I only have a plan for timidity at least In the forgetting of finding alliances for easy but the the rate prices to get both of finding vines and timidity and so far we only have a timidity in the central symmetric cases because we only have a war bonds in this century symmetric so that so I think it's probably do Woodward to cover .period are finding vine procedures to construct a long 1 yourself origin that is not centrally symmetric nobody poverty but unfortunately it's not clear that you're going to get the optimal long corresponding to that of said and I don't even know at this point what to look for so maybe by Monday the audience's give you additional flexibility but I'm not sure how to use the flexibility that that OK so we at least we have interest metrication it's pretty obvious what's a limitless abuses and now that we have this normally Minardi's movements that docile we have to come up with a pox and for talk centered of the definition of the parts they need a few more definitions so the 1st systematic massive distance between 2 norms spaces and this is just defined as the smallest product in usage that 1 Overby times the 1st nominee is smaller than the 2nd which is it serves more than 8 times that of so this product in the measures the distortion between these 2 norms an annual revenues it in the office of the parks and a
34:18
2nd definition is a bit more obscure 1 less classical and it's called Oregon IT constant and so it's taken from a paper by made of on a large deviations of Victor valued Martin gains from the doesn't really have anything to do with the legitimization context but it's a way of measuring the regularity of the backspace I have and so the 2nd IT constant back it's the smallest constant bent added does 2 things so fast we want to pass function PSquare divided by a tool to have any chance continues gradient which respected the nonpeak focus so we look for smooth on way to construct talks we want that's moving along to the final parks that is Lipschitz continues which respect that hazardous sorry Lynch's continues gradient which respect Woods said OK and we also want this not appear to be not too far away From the OIG known as long as we funded of their back OK so this not here may not be moved but we approximated by this movement and because the nonPC moves that allows us to disclose to tool the diver parks by just squaring it and don't weakened 2 things at the same time it will control of 1 house I 2 years from the Georgia norms and to house moves the puck so there's a tradeoff between the 2 there's a square here and here that there is a giant Bauman on the parliament on you but for some happy some act accident this is exactly the kind of we need novel so what you can show
36:08
using this definition is that the complexity of Nextel's method applied to this problem here can be bounded by square out of 4 times a few times DQ where did you the Lipschitz constant of the gradient of F which respected the Norman induced by you and did you is doing IT constant of the Benike space already at the end of the door would arm of the optional again the good news is that these 2 domes here are a few indeed you are are fine as Soriano environment which respect when find change of coordinates In your problem who can produce we saw the 1st problems so now the narrator in this complexity estimate we still have the optimal independence in its Amsterdam and at least now we have the find environments Of the narrator which respect when function of Gordon yes this is basically a good guy and I think we should have a lot of people yeah but you need to know this year you want to make it as constructive as possible but they didn't have the heart of the heart the the more I find so you take the move over all are fine change of coordinates of times DMX stock yet but that how you solve the problem on the whole history of the year nobody attitude you wait out and show you in a minute and you can do it for certain specific instances in the general case you can't but for certain specific instances it's it's easy so what when keyboard for example and and so the student movement coming back to the simplex example when optimizing was simplex it makes sense to signifies that sent him to and 1 more and when you do that classically people take India 1 arm as the underlying and and hope he has the park's function because Intel Putin's up to this point complex which respect 1 and the bond you get is the and 1 which is constant of your function times no again divided by its became if you don't at the same thing but using what is suggested by the previous construction you don't selected 1 almost in darling known you take as something that is DIC pocket of the 2 Logan OK don't ask me why I read the paper have but basically this suggests another way of constructing a non based on the geometry of your problem and you measure D Lynch's continuity of function which respect to that the norm as well and the complexity bound you get can be written and 1 times again divided that sometimes 16 yes the university places would you consider Rhode Island effective effective ways of thinking and conditions that would be issued later in life you shouldn't miss the I don't think that should make a difference in the lives half hour of All has thanks to the use of the money militants has no impact on the objectivity the on questions this city that you just put his life that was for running over removed with this on the stocks and so we did do not induced by you and epoxy which is induced by this definition of going to light a constant Durex Kilic suggestion giving squared divided by 2 OK so if you can compute the do you know and you can compute tailbacks then you have a specification of Nextel's method which is a fine OK In you uh this is smaller than the overall that's the question and remove this Christmas so it didn't clearly are finding answers is not sufficient to meet many denied 2 Indiana which Walters is a constant where Osorio complexity down which is similar to an absolute constant and you know we don't have entered this lesson in the issue he program a little around said he success that yes I'm going to come I'm gonna hide their little bit Brian and haven't really Dagestan this 1 yet so I'm not sure exactly what it means but the role models are pretty tight on this thing to so I have doubts that Sevilla lost his financial assets he will of be able to quality for their 1st patients I that also they also give up and asked if the number of iterations becomes bigger than and then the absurd method is a bit odd so then so this only applies in the highdimensional where you're doing fewer iterations and the dimensions Kelly but this is typically delays in column look at but I'm going to talk about other scenarios where did this out of bounds on the subject so when you have met all of this depends on getting it needed more information on that looks so I'll come back to that in again matzo this fall saying anything about that many this this bomb actually allows us to say something about the easy and heart problem if we if we invade the and try to understand what it means for the genetic appointed you so on easy problems so easy problems where problems means fewer problems lie in Tunisia OK well and you will be lowered the nominees larger in directions where the gradient is arch OK and that means less than the subliminal sets of F of X and you online and what that means dramatically that when there there's a vivid sidelined days enough time change of coordinates that is going to make your problem his factor so and optimizing the psychological was furious action the simplest pollen you can think of that sort of makes sense the and 2nd if you think about empty spaces and the union boss BP have lower IT constants OK and the big IT constant of G and 1 borders and that's the worst case but remember that you are the guy to use as defined under the Bruins space and so what that means is that the public were written over a union bosses beat you fall to between 1 and 2 are easier nonpublic Britain elections for example just because of the way it is works only people have but the question
43:05
is how good are these bonds located nice enough there are finding violence but it doesn't mean that the convicted on tight and in particular on the West but some choice of product NDX town divided by seamer Reynoso nicely nearfinal right OK but we don't expect that bound to be really good because of the industries are finding and this suit is also a fine in my opinion you gotta take Inc so and the question is can we showed tonight at TI at least can we should too many teams in particular cases
43:38
and it turns out that we can anybody go we can do so for white people OK so now organized focus on a very specific as problems were curies DES and keyboard OK and ending decades the boundaries and times deeply divided by its quoted Putin's deeply divided by its and the constant so can be computed explicitly look at something for the corresponding known as there simply cannot OK so when peace between 20 Infiniti G P simply enter the power P minus 2 working and when want peace between 1 and 2 you can bound by pretty tightly by this quantity OK West season at constant
44:23
and that means that we can compare this of abound with blue abounds we have fall optimizing smooth complex functions alike keyboards at the end of volcano 1 through the lower bond we have is this 1 here is divided by Logan divided by its young I'm sorry I I debated London and I'll complexity boundaries for all times and absent ,comma sometimes Ella Logan divided by yes the fees that he is in his whole life sentences to go all this is sufficiently that's essentially what you're doing when you defiantly so the origin of enormous Jack from the sect and many of these and peace there to produces both approximation of the 6 centuries so that's that's how it's constructive it's not constructive in the sense that you know manufacturers but it's the end of the regular IT constant is computed using this was approximation OK so don't have that here the the boundaries of similar to a police about the fact and orange peel between 2 infinity the law bomb is given by this and the upper bound of the land is given by this and this is again up to Moscow to apply the law when case publishing to and by optimality I mean up to maintain both Epsilon and OK which is a much stronger statement and symbol optimality which respect 20 Is there get the number of iterations so there is no doubt annoying things that happen when you went so you have to show melody for the entire square of values of its London and hooker and here in certain genes it turns out that voice is up when Newman you'll not counting the number of iterations that public that is proportional to end I regret but to date so we can discuss about this so fine I don't have time to go through mentioned
46:33
is here so in particular but I knew the dozens that that that did you that if you have a bit more information on the smoothness of your space and on ideology of your functions and then and in that case you can get much more precise estimates of the complex and in that case we are not yet able to produce a finding vine bounds and that that's the work similarly as the bonds ended in the fall that will work was OK but this is probably too much information faltered again so that's
47:07
it we have I find environment bounds on the complexity of Nestle's method that give you a kiss the principal aware specifying the method of choosing a norm in choosing a epoxy and these bonds are finding by then in addition to that in certain problem instances for example when your optimizing is bonds also turned out to be to and by up to my we now ultimately in terms of their independence which respected the precision of the end of tumor which respected dependence on the problem Parliament on the damage right and so that that's important OK so very briefly in the few minutes I have left I have a few signs about the numbers you well we are lucky and where the a description of the problem complexity matches exactly the quantity we use to describe its statistical performance and even tho there is no immediate connection with the topic and just discussed India and the objective is exactly the same described the complexity of an optimization problem that is in a way that is better than even and allows you to compare the complexity of optimization problems in a meaningful way so here I have to specialize things again and focus on the I'm going to clean our systems that followed a time you valve committee our systems 1 where you try to find vector on inside and the intersection of the local and such space and another where you try to find a victim why such debt minus it once was wide belongs to the core repair and it turns out we can say save very fine things that we have a very fine way of characterizing the complexity of solving such an alternative our system for care
49:04
and this this dump complexity description is written in terms of the distance between again and so what is the distance between feasibility it's essentially the minimum cultivation you need to include used to the Matrix To make your problem feasible also met victory the name that emission you need to make real your problem it takes 8 to make the problem his bike and forget about the duties here with distance to feasibility .period feasibility means is that the problems that our clearly feasible all problems that are clearly there will be much easier to solve the problems that are near the region where visibility starts to wind down knowing the stuff to because without this physical presence is still on the 1st section of the adding can choose but clearly appearance the spectrum not yet but yeah you may want to pick another 1 that's it said that that is effective against so soap a deal and what what ,comma gas condition number does is is measure this distance to feasibility on feasibility in a scaling OK so it takes this distance between feasibility and normalizing by the spectrum right so when an overloaded distance to finish his duties very smaller then "quotation mark allegedly speaking this condition number is going to be really hot OK and the idea of this condition numbers to fall faulty musician problems artist in this case and done at the clinic in our systems where the traditional condition number does fall our system OK so you compute the condition number of in our system gonna tell you at the same time how hard this system is going to be it's it's going to be to solve this problem numerically and how stable the solution will the condition number defined by huntergatherers gathers exactly the same thing for musician put it there you 1st how hard it's going to be to solve this optimization problem and 2nd how stable solution with this is a very very good if you can compute it of course it's a very good description of the data cut the description of the complexity of indigenization policy OK and so there's a lot of work on bond bounding the complexity of classical optimization techniques using this condition number and a more refined analysis of bio method shows for example that this condition number shows up in the abound on the number of iterations of intent upon methods and that the complexity of serving the ticketing system of equations actually lies with this condition number as well and so this started out to be a good way of measuring the complexity of an optimization problem using it precise structure and the input data and when you focus
52:08
on compressed sensing problems and sponsor coterie problems this should be the 1 on here I forgot to pretty important index you can define In in very precise terms the performance of this response recovery problem using clinically stated minimum in values of of the matrix OK and these are just the very much like the portion defining the classical singular values except U.S. think director to belong to a sudden code which is the descent Call of Duty 1 arm and this generalized eigenvalues allow you to bomb the performance of the farcical Korea going again and would serve pretty striking
52:54
here is that we're looking enough that these 2 quantities much meaning that when a gust condition number is actually quarter 2 d goal value controlling statistical like Avery performance in comparison in public so the quantity that compose numerical performance on the optimizations side In this case is also the quantity that compose a sponsor recovery combined performance on the statistical OK and we can generalize this so much of what our class of recovery problems and and more details on the paper OK and making his way so this is an example where we can go as far as possible in the consigning complexity descriptions of all complexity bound with statistical performance metrics again so what you see here is the classical phase transitions boss recovery so this is the poverty of recovery using values again and this is the 1st composition in the condition of look at it said nonsignatory it should be symmetric key free had tries on definition of the condition number with what happens on this side of the face opposition is not that interesting so the really interesting part is the fact that this condition number decreases as you move away from the official transition pressured here OK and that needs to face transitions are pretty wincing from OK and indeed which observers that the complexity of the corresponding numerical methods has the same face conversations when you move away come around in the sponsor ,comma attention meaning that it's much harder automatically to solve sponsor recovery problems when you on the year the transition pressure and when you much farther away from it and this is something that was observed on gay keys starting with the papers by the new in 2008 for example but here it's not completely explicit by this concordance between them conditioning 1 of the optimization problem on 1 side and the called it tonight and values on the other because this is my
55:18
cue to conclude before I get to the computer and so on and so just to sum up and somewhat emaciated prisoners but the idea here is to but produce complexity estimates that are near enough to the data to say something about the complexity of 1 of the musician problem versus another and so in particular we get the formulation of the ultimate I'm going by Mustafa whose complexity bounds are a fine invite our environment which is fit enough change of coordinates and don't know to be up to the Stronach and the completely datadriven complexity measure false farcical Republicans which matches exactly the the quantities used to measure the the statistical performance of dispersion procedures because there's a long list of open problems if you're interested that 1 is to shore up to 90 of the product HUD to during the general case and as you mentioned produced from on when she was not centrally cemetery can then that's obviously not we don't know how to do that is also a key question which is CFI's along nominated to GQ is that the 1 time would like to know because it would solve a lot of all problems but we don't know and I missed out also that bet is that it's not about you you can bet against him and and so the again the bestknown choice announced metrics insecure mentioned that already and also more important in some sense a systematic talked procedure false moving here OK and that would preserve a finding environments and so that would allow us to produce pox functions in cases where she was not an to board we don't know how to do that yet and that means they're going and implementable in the general case and so that's set to open in this thank you that is what the formal was more sources said for the sake of all the rest of the yes because then for the spectrum you know would be curious and that is died on that don't remember Paul they're hard to say the the United States we could be optimistic and suggested to put it on there and I guess that's the answer but I'm not on Central but so basically the the important part is that the the reason why we're able to check up to melodies here is that we knew exactly when DQ foreign peoples on the vegetables for and the same thing is true for the spectrum nominal matrix known so we know exactly where the DQ constant is for the metrics Turkey's we have an excuse there has still says they've learned losses for the year various in no not yet you could do so know what I guess you could you get a complexity constants but for the way you have to check out because of that I guess it work because then you no I gag is supposed to in that use it also here but I haven't checked the lowlands that's the point so as don't who exactly if this is but it should be used the other it's 1 of the interesting to note that you do do everything depends on the ratio signal violence and surmising fine environment and is a finding by and riches should be offended by it but I haven't checked is that all bonds and indeed if we have this and the a match that yes he left evaluation of the the results the plan would be put to use in Europe slightly receded In the last few holes he was the son of the owner of the schools so on the motivation cited least I think 1 which 1 polymers to feed the question so what you're really interested in this the ultimate so you not only give too many merits the optimum dependence on its USA won the optimum dependence on the dimensions and OK you can only do that get that if you pick the best choice of Norman the choice of Park OK if you get choice of Norman the choice of pucks along there you you lose you can lose a pretty significant factor on your behalf as you square event the example I just mentioned at all in the office just isn't all the rocks moscow's if there is such a you know that I'm not using the good the that's cool but in this case did it on out to be an inflight people's I agree with you that you don't have a genetic statement on the talks but in a sense when you computer bond former stealth method method you start from the assumption that you projection sets would be solvable what whatever 440 even secure so if you need to know if you make that assumption in Ernesto whatever happens so it here this is the center serious because this is the 1 which and in the years since the perspectives of problem which is high enough correlation he hired the problems which have no correlation that reflected in a suicide Bagheri assumed that there there is a gap in the United States but at least the problem we decided to focus on right now it's true I have abounded that is ultimately in both and an OK right now we do not have that by far so in many cases in some cases we know exactly how to beat the parks and supporting the efficiency and 1 European gentle Tolkien everything's fine but for a generic problem you're faced with a fuse but said no 1 tells you which poachers who you should big and you could really use a factor was "quotation mark event for example by not picking the right products so what we wanted originally was a principal procedure to choose the nonintrusive parks and he took about that when you do that by nature what you get is a finding by the ways you can simply that cities should get something that looks like being few over all are fine changes of coordinates of and indeed over signal look OK in other ways you can always take enough find skating the this union so whatever you do wish you want to get to know you need to be a finding by the end it's easier to look fast fine invites that's that's the reason why it took so much about the fine In the end only goal is to find of course the ultimate bound fall Nextel's method in the principal away so in a way that tells you exactly how to select the norms and how to save the parks I agree with you that this doesn't solve the problem of computing the corresponding parks in solving the projections but uh I guess said that we have to wait until we solve this problem fast I guess nor have so so I agree with you but but I II and my message is that getting the optimal bombing itself is not always solved issue at this point the once again each time
1:03:00
they