In addition to the Fields medallists mentioned in the previous post, the IMU also awarded the Nevanlinna prize to Subhash Khot, the Gauss prize to Stan Osher (my colleague here at UCLA!), and the Chern medal to Phillip Griffiths. Like I did in 2010, I’ll try to briefly discuss one result of each of the prize winners, though the fields of mathematics here are even further from my expertise than those discussed in the previous post (and all the caveats from that post apply here also).

Subhash Khot is best known for his Unique Games Conjecture, a problem in complexity theory that is perhaps second in importance only to the problem for the purposes of demarcating the mysterious line between “easy” and “hard” problems (if one follows standard practice and uses “polynomial time” as the definition of “easy”). The problem can be viewed as an assertion that it is difficult to find exact solutions to certain standard theoretical computer science problems (such as -SAT); thanks to the NP-completeness phenomenon, it turns out that the precise problem posed here is not of critical importance, and -SAT may be substituted with one of the many other problems known to be NP-complete. The unique games conjecture is similarly an assertion about the difficulty of finding even *approximate* solutions to certain standard problems, in particular “unique games” problems in which one needs to colour the vertices of a graph in such a way that the colour of one vertex of an edge is determined uniquely (via a specified matching) by the colour of the other vertex. This is an easy problem to solve if one insists on exact solutions (in which 100% of the edges have a colouring compatible with the specified matching), but becomes extremely difficult if one permits approximate solutions, with no exact solution available. In analogy with the NP-completeness phenomenon, the threshold for approximate satisfiability of many other problems (such as the MAX-CUT problem) is closely connected with the truth of the unique games conjecture; remarkably, the truth of the unique games conjecture would imply asymptotically sharp thresholds for many of these problems. This has implications for many theoretical computer science constructions which rely on hardness of approximation, such as probabilistically checkable proofs. For a more detailed survey of the unique games conjecture and its implications, see this Bulletin article of Trevisan.

My colleague Stan Osher has worked in many areas of applied mathematics, ranging from image processing to modeling fluids for major animation studies such as Pixar or Dreamworks, but today I would like to talk about one of his contributions that is close to an area of my own expertise, namely compressed sensing. One of the basic reconstruction problem in compressed sensing is the basis pursuit problem of finding the vector in an affine space (where and are given, and is typically somewhat smaller than ) which minimises the -norm of the vector . This is a convex optimisation problem, and thus solvable in principle (it is a polynomial time problem, and thus “easy” in the above theoretical computer science sense). However, once and get moderately large (e.g. of the order of ), standard linear optimisation routines begin to become computationally expensive; also, it is difficult for off-the-shelf methods to exploit any additional structure (e.g. sparsity) in the measurement matrix . Much of the problem comes from the fact that the functional is only barely convex. One way to speed up the optimisation problem is to relax it by replacing the constraint with a convex penalty term , thus one is now trying to minimise the unconstrained functional

This functional is more convex, and is over a computationally simpler domain than the affine space , so is easier (though still not entirely trivial) to optimise over. However, the minimiser to this problem need not match the minimiser to the original problem, particularly if the (sub-)gradient of the original functional is large at , and if is not set to be small. (And setting *too* small will cause other difficulties with numerically solving the optimisation problem, due to the need to divide by very small denominators.) However, if one modifies the objective function by an additional linear term

then some simple convexity considerations reveal that the minimiser to this new problem *will* match the minimiser to the original problem, provided that is (or more precisely, lies in) the (sub-)gradient of at – even if is not small. But, one does not know in advance what the correct value of should be, because one does not know what the minimiser is.

With Yin, Goldfarb and Darbon, Osher introduced a Bregman iteration method in which one solves for and simultaneously; given an initial guess for both and , one first updates to the minimiser of the convex functional

and then updates to the natural value of the subgradient at , namely

(note upon taking the first variation of (1) that is indeed in the subgradient). This procedure converges remarkably quickly (both in theory and in practice) to the true minimiser even for non-small values of , and also has some ability to be parallelised, and has led to actual performance improvements of an order of magnitude or more in certain compressed sensing problems (such as reconstructing an MRI image).

Phillip Griffiths has made many contributions to complex, algebraic and differential geometry, and I am not qualified to describe most of these; my primary exposure to his work is through his text on algebraic geometry with Harris, but as excellent though that text is, it is not really representative of his research. But I thought I would mention one cute result of his related to the famous Nash embedding theorem. Suppose that one has a smooth -dimensional Riemannian manifold that one wants to embed locally into a Euclidean space . The Nash embedding theorem guarantees that one can do this if is large enough depending on , but what is the minimal value of one can get away with? Many years ago, my colleague Robert Greene showed that sufficed (a simplified proof was subsequently given by Gunther). However, this is not believed to be sharp; if one replaces “smooth” with “real analytic” then a standard Cauchy-Kovalevski argument shows that is possible, and no better. So this suggests that is the threshold for the smooth problem also, but this remains open in general. The cases is trivial, and the case is not too difficult (if the curvature is non-zero) as the codimension is one in this case, and the problem reduces to that of solving a Monge-Ampere equation. With Bryant and Yang, Griffiths settled the case, under a non-degeneracy condition on the Einstein tensor. This is quite a serious paper – over 100 pages combining differential geometry, PDE methods (e.g. Nash-Moser iteration), and even some harmonic analysis (e.g. they rely at one key juncture on an extension theorem of my advisor, Elias Stein). The main difficulty is that that the relevant PDE degenerates along a certain characteristic submanifold of the cotangent bundle, which then requires an extremely delicate analysis to handle.

## 16 comments

Comments feed for this article

13 August, 2014 at 3:37 pm

Anurag Bishnoi“in such a way that the colour of one vertex of an edge is determined uniquely (via a specified matching) by the colour of the other edge.” – Is that a typo? Did you mean to write vertex instead of edge in the end?

[Corrected, thanks - T.]13 August, 2014 at 6:17 pm

AnonymousDear Terry,I’m not a mathematician,but every thing and every man in my hand and my mind.these people win these winners that i knew 4 years ago,may be these award is easier than in future.Order of the world has change.List of winners of the last 50 years .I recognize that only one and only one is on the top in now and futher(I don’t reveal here).Someone is more stupid than if he/she thinks my sayings is stupid.Please don’t cancel my comment.

13 August, 2014 at 6:20 pm

arch1“This functional is more convex…” – do you mean “This function…”?

[Notation changed to refer to functional consistently, rather than function, for the quantity to be extremised. -T.]14 August, 2014 at 7:09 am

arch1Thanks for the pointer Terry. I didn’t realize that a functional needn’t be a function of a function.

13 August, 2014 at 8:33 pm

deaneyangTerry, I am quite flattered that you chose of all the theorems that Griffiths has proved the one I collaborated with him on. I thought I would take advantage of this and write a shamelessly long comment about the theorem.

First, even the case is not fully settled. There, the problem can be reduced to a scalar Monge-Ampere-type equation that is elliptic if the Gauss curvature is positive, hyperbolic if it is negative, and degenerate if it is zero. So if at a point, the local existence of an isometric embedding follows by standard theorems about nonlinear elliptic and hyperbolic PDE’s. If, however, at a point but not in a neighborhood of a point, things get a lot more difficult. C. S. Lin proved local existence theorems if and at a point, as well as the case in a neighborhood of a point. I’m blanking out on whether other cases have been handled since then, but the general question still remains open.

As for the BGY paper, the first half of the paper is a tour de force of complex and real algebraic geometry (I can say this because I was only a bystander watching it happen. By the way, this was right after Robert got his Ph.D. He would visit Harvard, and we would watch awestruck as he showed us all the things he could do using exterior differential systems.) studying what the symbol of the linearized PDE looked like. What this led to was the observation that if the Einstein tensor satisfied a certain open condition, then the PDE was effectively symmetric or strictly hyperbolic, even though the problem involves in no way a natural time co-ordinate. Instead, there is a cone of tangent directions at a point in the manifold such that if you declare one of them as time, then the PDE can be written as a hyperbolic system with respect to that time co-ordinate. At this point the local existence of smooth solutions to the linear equation is quite straightforward using energy estimates. The only question is how to prove estimates (now called “smooth tame estimates”) needed for applying Nash-Moser to obtain local existence and regularity for the original nonlinear system. This is in fact also quite straightforward and easy. We didn’t know this at the time, because back then (early 80′s) nobody at Harvard knew anything about PDE’s (well, except for Cliff Taubes). Griffiths called Nirenberg, who referred him to Sergiu Klainerman. I went down to Courant, and it took Sergiu about 5 minutes to explain to me how to prove what he called an “elementary calculus lemma” which indeed was elementary (anyone in nonlinear PDE’s knows this stuff in their sleep) and gave the necessary estimates. We then talked about music the rest of the time.

This and Stein’s extension lemma (which I found in one of his books) were the last pieces we needed. So I would like to express mild disagreement to your statement that this involved “delicate estimates”. Especially by modern standards (for example, recent work by you and others on the Navier-Stokes equation), the PDE part of the BGY paper was rather straightforward. Don’t get me wrong. I’m very proud of this work and believe it was groundbreaking back then. But the PDE part is arguably the easiest part of the paper. If it looks harder than it really is, it’s because I wrote that part.

And then there’s what came after that paper. We had also shown that for the generic 3-d and 4-d metrics, the PDE was what Hormander called “real principal type”. Hormander used microlocal analysis and Fourier integral operators to prove local existence and regularity theorems for linear PDE’s of real principal type. To obtain a local isometric embedding in these cases, it again sufficed to prove the smooth tame estimates for the solution to the linear system. However, proving such estimates held for the microlocal analysis and Fourier integral operators is rather painful. Nakamura and Maeda did publish a paper grinding through all of this, but it’s not an easy read. Separately, while I was a postdoc at Courant, Jonathan Goodman and I found a proof that involved perturbing a fixed linear PDO using a “microglobal” Fourier integral operator. We submitted it to CPAM, but it was rejected. We wanted to revise it before submitting it to another journal but never got around to it. The preprint is available on my web page.

Others have extended these results since then, including Qing Han, J. X. Hong, Marcus Khuri, and T. Poole. However, as far as I know, nobody has the slightest clue to how one might be able to prove this in all dimensions with or without curvature assumptions. The linearized PDO has no structure (that other important PDE’s have) that can be used to obtain estimates. In fact, the algebraic geometric analysis of the symbol showed that in some sense the linearized PDO is a generic -by- first order differential operator. Nothing is known about how to deal with such an operator.

[Description of the n=2 case corrected, thanks - T.]14 August, 2014 at 3:35 pm

Pedro Lauridsen RibeiroHi Deane, thanks a lot for sharing a bit of the history behind your paper with Bryant and Griffiths. I think it is worthwhile to mention (as it is a matter of my interest) that it is one of the few works one is faced with the problem of solving an *inhomogeneous* nonlinear hyperbolic PDE system (i.e. with sources). Having an external source in the right hand side of a nonlinear PDE brings hurt to pain, as the Navier-Stokes equations show so dramatically in the parabolic case (after all, there is no turbulence if there is no pressure gradient). Also, it seems hopeless to prove global existence in such a case, even for small Cauchy data (unless, perhaps, the source has compact space-time support). On the other hand, since such a problem is clearly an “implicit function problem”, using Nash-Moser becomes a natural idea, even because it’s possible to “tamefy” the energy estimates for the linearized equation (which was first done by Klainerman in his PhD thesis, right?). I also find amusing (albeit not wrong, mind you) that Klainerman called the Moser and Schauder estimates used for this task simply “an elementary calculus lemma”. He kind of called them that in his PhD thesis paper at CPAM as well…

Making available online your preprint with Prof. Goodman was fantastic (even because it’s very hard to go through the “Kumano-go calculus” Nakamura and Maeda use in their work), and I imagine it was some story to retrieve it – in 2009, I had an email exchange with you and Prof. Goodman when trying to find it. I even asked Prof. Bryant when he came to São Paulo in 2011, and he recalled he maybe had a copy in his office at Duke (he was at Berkeley at the time), but he wasn’t sure. One unfortunate disadvantage of the method in this paper, though, is that uniqueness of solutions is no longer guaranteed as in the hyperbolic case dealt with in your paper with Bryant and Griffiths (albeit this was probably not relevant for the applications you had in mind).

14 August, 2014 at 4:27 pm

deaneyangPedro, I found the email exchange we had. I see that I never replied to your last email. I’m sorry about that. In any case, I think you had gone beyond my limited knowledge about PDE’s anyway.

14 August, 2014 at 4:53 pm

Pedro Lauridsen RibeiroThat’s OK. In the end, the method used in your paper with Bryant and Griffiths ended up being more useful to me and my collaborators, since we needed uniqueness of the solution and the PDE’s we were interested on were always hyperbolic. However, since we were working in arbitrary Lorentzian manifolds (possibly with non-compact Cauchy hypersurfaces) instead of Euclidean space and needed a solution defined in arbitrarily large compact regions, I had at the same time to geometrize and localize the estimates. In the end, we had to carry a large part of the argument from scratch. In any case, now I can check your preprint…

13 August, 2014 at 10:29 pm

John Bentin(Typo) In line 9 of paragraph 3, should that be “of the vector $x$” (rather than $n$)?

[Corrected, thanks - T.]15 August, 2014 at 2:56 am

zr9558Reblogged this on ZHANG RONG.

15 August, 2014 at 3:43 am

Terrance Tao discusses the Fields Medal winners. | BUMPS[…] http://terrytao.wordpress.com/2014/08/13/khot-osher-griffiths/ […]

15 August, 2014 at 4:10 am

Peter WoolfittMinor typo – In line 4 of paragraph 2, it should be “if one follows standard practice” instead of “if one follow standard practice.”

[Corrected, thanks - T.]16 August, 2014 at 11:30 pm

Media Item from “Haaretz” Today: “For the first time ever…” | Combinatorics and more[…] work of all prize recipients. And from Quanta Magazine: (More) More on Osher, Griffiths, and Khot on terry Tao’s blog, on Khot on Scott Aaronson’s blog and on a description of the laudations on Gowers […]

17 August, 2014 at 8:19 am

ScotIn the sentence that begins “One of the basic reconstruction problem…” should A be $m x $n … x is in R^n and b is in R^m? Thanks for the interesting post!

[Corrected, thanks - T.]17 August, 2014 at 12:12 pm

deaneyangI also recommend another beautiful and under-appreciated paper “The Gauss equations and rigidity of isometric embeddings” published in the Duke Math Journal in 1983 by Berger, Bryant, and Griffiths. Eric Berger was another graduate student of Phillip two years ahead of me; he unfortunately left academia soon after he got a Ph.D. and was one of the early quants on Wall Street (as was another classmate Farshid Jamshidian).

In this paper algebraic geometry and representation theory are used to analyze deeply the relationship between the second fundamental form and its covariant derivatives with the Riemann curvature tensor and its covariant derivatives via the Gauss equations, Codazzi-Mainardi equations, and their covariant derivatives. The authors obtain not only new infinitesimal and local rigidity theorems but also identify situations where the isometric embedding has only a finite dimensional space of deformations.

18 August, 2014 at 10:04 am

Día importante para las Matemáticas: Maryam Mirzakhani (Irán) gana una Medalla Fields | Ciencia | La Ciencia de la Mula Francis[…] Hairer, Mirzakhani,” What’s New, 12 Aug 2014, y “Khot, Osher, Griffiths,” What’s New, 12 Aug 2014. Tim Gowers, “ICM2014 — Bhargava laudatio,” GWblog, 15 Aug 2014; “ICM2014 […]