User mark reid - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-21T11:42:37Z http://mathoverflow.net/feeds/user/1915 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/15509/solutions-to-a-monge-ampere-equation-on-the-simplex Solutions to a Monge-Ampère equation on the simplex Mark Reid 2010-02-16T23:35:27Z 2011-05-30T15:43:52Z <p>Let $\Delta_k$ be the k-simplex and $\mu$ a non-negative measure over $\Delta_k$. I want to know if there exists a function $u : \Delta_k \to \mathbb{R}$ such that $u$ is convex, $u(e_i) = 0$ for all vertices $e_i$ of $\Delta_k$, and $M[u] = \mu$ where $M[u] = \det\left(\frac{\partial^2 u}{\partial x_j \partial x_k}\right)$ is the Monge-Ampère operator. Furthermore, I'd like to know if the solution is unique. Any techniques for how one might solve a specific instance of this problem would be a bonus.</p> <p>My background is not in PDEs but the closest I've found to an answer seem to be in [1] and [2] where the boundary conditions are more restrictive and the domain is required to be strictly convex for uniqueness.</p> <p>[1] "On the fundamental solution for the real Monge-Ampère operator", Blocki and Thorbiörnson, Math. Scand. 83, 1998</p> <p>[2] "The Dirichlet problem for the multidimensional Monge-Ampère equation", Rauch and Taylor, Rocky Mountain Journal of Mathematics, 7(2), 1977.</p> <p>Any other pointers to solving this type of problem would be greatly appreciated.</p> http://mathoverflow.net/questions/17790/are-bregman-divergences-quasi-convex Are Bregman divergences quasi-convex? Mark Reid 2010-03-11T00:59:13Z 2010-03-17T12:45:28Z <p>Given a convex set <em>S</em> &sub; &#8477;<sup>d</sup> and an appropriately differentiable convex function <em>f</em>: <em>S</em> &rarr; &#8477;, a Bregman divergence <em>B</em><sub><em>f</em></sub>(<em>x</em>, <em>y</em>) = <em>f</em> (<em>x</em>) - <em>f</em> (<em>y</em>) -&lang;<em>x</em>- <em>y</em> , &nabla;<em>f</em> (<em>y</em>)&rang; for <em>x</em>, <em>y</em> &isin; <em>S</em>.</p> <p>For any <em>x</em>, consider the function <em>b</em>(y) = <em>B</em><sub>f</sub>(<em>x</em>, <em>y</em>). It is known that this is not always convex (choose <em>f</em> (<em>x</em>) = x<sup>3</sup> for <em>S</em> &sub; &#8477;) and I can show that for <em>S</em> &sub; &#8477; it is always quasi-convex (i.e., <em>b</em>(&lambda;<em>y</em>+(1-&lambda;)<em>y</em>') ≤ max{ <em>b</em>(y), <em>b</em>(y') } for &lambda;&isin;[0,1], <em>y</em>, <em>y</em>' &isin; <em>S</em>) but cannot prove or find a counter-example in the general case.</p> <p>I've done a quick hunt around the literature on Bregman divergences but cannot find an answer either way.</p> http://mathoverflow.net/questions/6061/explicitly-describing-extreme-points-of-infinite-dimensional-convex-sets Explicitly describing extreme points of infinite dimensional convex sets Mark Reid 2009-11-19T04:00:50Z 2009-11-19T05:02:43Z <p>I am currently trying to apply some results from Choquet theory - i.e., the generalisation of results by Minkowski and Krein-Milman for representing points in a compact, convex set C by probability measures over its extreme points, ext C = { x &isin; C : C - { x } is convex }.</p> <p>My main problem is with explicitly describing the set of extreme points for a particular convex set, namely the set C of concave functions over the k-simplex that vanish at the vertices of the simplex and have sup-norm at most 1. I've convinced myself that this set of functions in compact and convex and so the Choquet's theorem applies. However, apart from the case of the 1-simplex I am struggling to say anything about what the extreme functions might be.</p> <p>In the case of the 1-simplex, the functions in ext C are "tents" with height 1, that is, functions f that are zero on the boundaries and rise linearly to a single point x where f(x)=1. I suspect that in the case of the 2-simplex the extreme functions are also piece-wise linear concave functions with height 1. I have considered a number of candidates (the functions formed by the taking the minimum of 3 affine functions, each zero on a different vertex) but am having trouble showing that the candidates are actually extreme.</p> <p>Does anyone know of any techniques for identifying extreme points of convex sets? </p> <p>Pointers to applications of Choquet's theorem that explicitly construct ext C and the probability measure for a given point in C would also be much appreciated. My reading in this area has only got me as far as Phelps' monograph "Lectures on Choquet Theory" and a survey article by Nina Roy titled "Extreme Points of Convex Sets in Infinite Dimensional Spaces".</p> http://mathoverflow.net/questions/17790/are-bregman-divergences-quasi-convex/18484#18484 Comment by Mark Reid Mark Reid 2010-03-17T23:09:26Z 2010-03-17T23:09:26Z Thanks for the proof—it's very well written—however, as I stated in my question, I already have a proof (indeed, it is quite similar to your own) of quasi-convexity for the case when S ⊂ ℝ. My real problem is showing it for multi-dimensional functions. http://mathoverflow.net/questions/17790/are-bregman-divergences-quasi-convex/17842#17842 Comment by Mark Reid Mark Reid 2010-03-11T22:49:51Z 2010-03-11T22:49:51Z I had briefly tried coming at the problem via the dual but didn't get very far. Maybe I'll revisit that approach. Thanks for the suggestion. http://mathoverflow.net/questions/15509/solutions-to-a-monge-ampere-equation-on-the-simplex/16206#16206 Comment by Mark Reid Mark Reid 2010-02-24T05:17:02Z 2010-02-24T05:17:02Z By a similar degrees of freedom argument I see that specifying exactly where |u(x)|=1 won't help either. My geometric intuition about the problem has completely failed me now. I originally thought that specifying the function's values at the vertices, its &quot;curvature&quot; (roughly speaking) at each point, as well as its height would have determined it. However, your construction shows that there are, in fact, a whole family that satisfy those constraints when M[u] is constant. I suspect M throws away too much information about the function and my intuition is confusing it with the Hessian. http://mathoverflow.net/questions/15509/solutions-to-a-monge-ampere-equation-on-the-simplex/16206#16206 Comment by Mark Reid Mark Reid 2010-02-24T03:17:24Z 2010-02-24T03:17:24Z Thanks for the demonstration of non-uniqueness. I had already realised that M was invariant under affine transformations which is why I had required u to vanish at the vertices. Another natural constraint in my problem is that $\sup_{x\in{\Delta_k}} |u(x)|=1$. Would that give uniqueness? I suspect, at least, that the construction you give would only satisfy this extra constraint for a single value of $a$. I'll definitely have a look at the book you suggested too. http://mathoverflow.net/questions/15509/solutions-to-a-monge-ampere-equation-on-the-simplex Comment by Mark Reid Mark Reid 2010-02-17T04:21:57Z 2010-02-17T04:21:57Z I also found Jerrard's &quot;Some Remarks on Monge-Amp&#232;re functions&quot; (2008) useful but not conclusive for my question. http://mathoverflow.net/questions/15509/solutions-to-a-monge-ampere-equation-on-the-simplex/15536#15536 Comment by Mark Reid Mark Reid 2010-02-17T04:15:35Z 2010-02-17T04:15:35Z Thanks for the pointers. I work in statistical machine learning and have recently been investigating properties of loss functions for probability estimation and their associated entropies. Many properties of losses in the binary case (i.e., k=1) can be explained by the curvature of their entropy function. The question above is an attempt to generalise some results beyond the standard binary prediction problem. http://mathoverflow.net/questions/6061/explicitly-describing-extreme-points-of-infinite-dimensional-convex-sets Comment by Mark Reid Mark Reid 2009-12-15T02:46:38Z 2009-12-15T02:46:38Z I've since found a paper that more or less answers my question. In case anyone else is interested it is &quot;Extremal Convex Functions&quot;, Bronshtein, E.M., Sibirskii Matematicheskii Zhurnal, Vol. 19, No 1., 1978 <a href="http://www.springerlink.com/content/k89m467j865uw7x2/" rel="nofollow">springerlink.com/content/k89m467j865uw7x2</a> http://mathoverflow.net/questions/6061/explicitly-describing-extreme-points-of-infinite-dimensional-convex-sets/6062#6062 Comment by Mark Reid Mark Reid 2009-11-19T05:07:18Z 2009-11-19T05:07:18Z I'd also considered these as candidates. Does your argument show that they constitute all of ext C? http://mathoverflow.net/questions/6061/explicitly-describing-extreme-points-of-infinite-dimensional-convex-sets/6063#6063 Comment by Mark Reid Mark Reid 2009-11-19T05:04:51Z 2009-11-19T05:04:51Z Regarding compactness, I think you may have a point. Those function would converge to a point that is non-zero over a vertex and thus not in C. I may have to rethink my construction. http://mathoverflow.net/questions/6061/explicitly-describing-extreme-points-of-infinite-dimensional-convex-sets/6063#6063 Comment by Mark Reid Mark Reid 2009-11-19T05:02:24Z 2009-11-19T05:02:24Z If I understand your candidates in the case of the 1-simplex, these would be functions over [0,1] that are trapeziums with a flat top over [a,b]? I don't think these are extreme though - an appropriately weighted sum of &quot;tents&quot; plus some proportion of the 0 function (also extreme) would show these are a convex combination of other points in C.