nhaliday + math.mg   46

inequalities - Is the Jaccard distance a distance? - MathOverflow
Steinhaus Transform
the referenced survey: http://kenclarkson.org/nn_survey/p.pdf

It's known that this transformation produces a metric from a metric. Now if you take as the base metric D the symmetric difference between two sets, what you end up with is the Jaccard distance (which actually is known by many other names as well).
q-n-a  overflow  nibble  math  acm  sublinear  metrics  metric-space  proofs  math.CO  tcstariat  arrows  reduction  measure  math.MG  similarity  multi  papers  survey  computational-geometry  cs  algorithms  pdf  positivity  msr  tidbits  intersection  curvature  convexity-curvature  intersection-connectedness  signum
february 2017 by nhaliday
Consider the following statements:
1. The shape with the largest volume enclosed by a given surface area is the n-dimensional sphere.
2. A marginal or sum of log-concave distributions is log-concave.
3. Any Lipschitz function of a standard n-dimensional Gaussian distribution concentrates around its mean.
What do these all have in common? Despite being fairly non-trivial and deep results, they all can be proved in less than half of a page using the Prékopa–Leindler inequality.

ie, Brunn-Minkowski
acmtariat  clever-rats  ratty  math  acm  geometry  measure  math.MG  estimate  distribution  concentration-of-measure  smoothness  regularity  org:bleg  nibble  brunn-minkowski  curvature  convexity-curvature
february 2017 by nhaliday
The Brunn-Minkowski Inequality | The n-Category Café
For instance, this happens in the plane when A is a horizontal line segment and B is a vertical line segment. There’s obviously no hope of getting an equation for Vol(A+B) in terms of Vol(A) and Vol(B). But this example suggests that we might be able to get an inequality, stating that Vol(A+B) is at least as big as some function of Vol(A) and Vol(B).

The Brunn-Minkowski inequality does this, but it’s really about linearized volume, Vol^{1/n}, rather than volume itself. If length is measured in metres then so is Vol^{1/n}.

...

Nice post, Tom. To readers whose background isn’t in certain areas of geometry and analysis, it’s not obvious that the Brunn–Minkowski inequality is more than a curiosity, the proof of the isoperimetric inequality notwithstanding. So let me add that Brunn–Minkowski is an absolutely vital tool in many parts of geometry, analysis, and probability theory, with extremely diverse applications. Gardner’s survey is a great place to start, but by no means exhaustive.

I’ll also add a couple remarks about regularity issues. You point out that Brunn–Minkowski holds “in the vast generality of measurable sets”, but it may not be initially obvious that this needs to be interpreted as “when A, B, and A+B are all Lebesgue measurable”, since A+B need not be measurable when A and B are (although you can modify the definition of A+B to work for arbitrary measurable A and B; this is discussed by Gardner).
mathtariat  math  estimate  exposition  geometry  math.MG  measure  links  regularity  survey  papers  org:bleg  nibble  homogeneity  brunn-minkowski  curvature  convexity-curvature
february 2017 by nhaliday
mg.metric geometry - Pushing convex bodies together - MathOverflow
- volume of intersection of colliding, constant-velocity convex bodies is unimodal
- pf by Brunn-Minkowski inequality
q-n-a  overflow  math  oly  tidbits  geometry  math.MG  monotonicity  measure  spatial  dynamical  nibble  brunn-minkowski  intersection  curvature  convexity-curvature  intersection-connectedness
january 2017 by nhaliday
Ehrhart polynomial - Wikipedia
In mathematics, an integral polytope has an associated Ehrhart polynomial that encodes the relationship between the volume of a polytope and the number of integer points the polytope contains. The theory of Ehrhart polynomials can be seen as a higher-dimensional generalization of Pick's theorem in the Euclidean plane.
math  math.MG  trivia  polynomials  discrete  wiki  reference  atoms  geometry  spatial  nibble  curvature  convexity-curvature
january 2017 by nhaliday
Dvoretzky's theorem - Wikipedia
In mathematics, Dvoretzky's theorem is an important structural theorem about normed vector spaces proved by Aryeh Dvoretzky in the early 1960s, answering a question of Alexander Grothendieck. In essence, it says that every sufficiently high-dimensional normed vector space will have low-dimensional subspaces that are approximately Euclidean. Equivalently, every high-dimensional bounded symmetric convex set has low-dimensional sections that are approximately ellipsoids.

http://mathoverflow.net/questions/143527/intuitive-explanation-of-dvoretzkys-theorem
http://mathoverflow.net/questions/46278/unexpected-applications-of-dvoretzkys-theorem
math  math.FA  inner-product  levers  characterization  geometry  math.MG  concentration-of-measure  multi  q-n-a  overflow  intuition  examples  proofs  dimensionality  gowers  mathtariat  tcstariat  quantum  quantum-info  norms  nibble  high-dimension  wiki  reference  curvature  convexity-curvature  tcs
january 2017 by nhaliday
Carathéodory's theorem (convex hull) - Wikipedia
- any convex combination in R^d can be pared down to at most d+1 points
- eg, in R^2 you can always fit a point in convex hull in a triangle
tcs  acm  math.MG  geometry  levers  wiki  reference  optimization  linear-programming  math  linear-algebra  nibble  spatial  curvature  convexity-curvature
january 2017 by nhaliday
(Gil Kalai) The weak epsilon-net problem | What's new
This is a problem in discrete and convex geometry. It seeks to quantify the intuitively obvious fact that large convex bodies are so “fat” that they cannot avoid “detection” by a small number of observation points.
gowers  mathtariat  tcstariat  tcs  math  concept  rounding  linear-programming  research  open-problems  geometry  math.CO  magnitude  probabilistic-method  math.MG  discrete  nibble  org:bleg  questions  curvature  pigeonhole-markov  convexity-curvature
january 2017 by nhaliday
Talagrand’s concentration inequality | What's new
Proposition 1 follows easily from the following statement, that asserts that if a convex set {A \subset {\bf R}^n} occupies a non-trivial fraction of the cube {\{-1,+1\}^n}, then the neighbourhood {A_t := \{ x \in {\bf R}^n: \hbox{dist}(x,A) \leq t \}} will occupy almost all of the cube for {t \gg 1}:
exposition  math.CA  math  gowers  concentration-of-measure  mathtariat  random-matrices  levers  estimate  probability  math.MG  geometry  boolean-analysis  nibble  org:bleg  high-dimension  p:whenever  dimensionality  curvature  convexity-curvature
may 2016 by nhaliday