Matus Telgarsky
Reputation
639
Top tag
Next privilege 1,000 Rep.
 Mar 14 awarded Enlightened Mar 14 awarded Nice Answer Oct 23 awarded Yearling Jun 25 awarded Yearling Aug 11 revised How to compute KL-divergence when PMF contains 0s? added 362 characters in body Aug 11 answered How to compute KL-divergence when PMF contains 0s? Jul 13 comment Conic hulls and cones BTW I believe there is a typo in your description: primal certificates mean no extreme point, and dual certificates mean some extreme point amongst the remaining input points. Jul 13 comment Conic hulls and cones Welcome to MO! That is a very nice algorithm! Just a note--I can't figure out how to directly convert this to conic hulls, so it seems necessary to use a conic-to-convex reduction as remarked by Jean-Marc Schlenker in the comments above. (To be specific about the problem: it is possible that a non-extremal point has the largest projection onto the dual certificate, simply because it is "farthest down" that polyhedral face. I tried a couple quick fixes, but all failed. Anyway, the projection solution by Jean-Marc is fast and sufficient.) Jul 12 revised Conic hulls and cones math parse error Jul 12 answered Conic hulls and cones May 9 awarded Nice Answer Apr 6 revised Existence of nonnegative solutions to an underdetermined system of linear equations sampling for pos & neg Apr 6 answered Existence of nonnegative solutions to an underdetermined system of linear equations Dec 17 awarded Yearling Aug 22 comment Kernel width in Kernel density estimation About using neighbors--although this seems like a reasonable idea, there is very little work in this direction. Luc Devroye has a few papers on this topic http://cg.scs.carleton.ca/~luc/devs.html , and you'll see that just looking at the closest is inadequate. In general, cross-validation is the standard technique. If you are interested in L1 density estimates, there is an excellent book by Devroye and Lugosi titled "Combinatorial Methods in Density Estimation". Aug 19 revised Why were matrix determinants once such a big deal? added 227 characters in body Aug 19 answered Why were matrix determinants once such a big deal? Jul 23 answered Is quadratic programming still NP-hard if you have bounds and a feasible point? Mar 18 comment Are Bregman divergences quasi-convex? (and set $x= (0,0)$.) in the bad example, since $f$ is linear along $x-y$ and $x-z$, then $b_x(y) = b_x(z) = 0$. On the other hand, since it is quadratic along $x-w$, the Bregman divergence is nonzero; in fact, it is $1/2$. I have an argument that $f$ is convex, but it is vague. I have to run, but tomorrow hopefully I can come back with something better. Mar 18 comment Are Bregman divergences quasi-convex? thanks for clarifying. If you can verify the following example (in cylindrical coordinates) is convex, then the general case does not work. Set $\lambda(\theta) = \frac {4}{\pi}\left | \theta - \frac \pi 4\right|$, $S= [0,1] \times [0,\pi/2]$, and $f : S\to \mathbb{R}$ to $f(r,\theta) = \lambda(\theta)r + (1-\lambda(\theta))r^2$. Since $\lambda(\cdot)$ goes between 0 (at $\theta \in \{0,\pi/2\}$) and 1 (at $\theta = \pi/4$), $f$ interpolates (rotationally) between linear and quadratic. The bad choice is $y = (1,0)$, $z =(1,\pi/2)$, and $w = (y+z)/2 = (\sqrt{2}/2,\pi/4)$.