23

Consider a convex body $K$ centered at origin and symmetric (i.e. if $x\in K$ then $-x\in K$). I desire to find a different convex body $L$ such that $K\subseteq L$ and the following measure is minimized:

$f(L)=\mathbb{E}(\sqrt{x^T \cdot x})$, where $x$ is a point chosen uniformly at random from L.

I am ok with constant factor approximation to the measure.

Some notes - The first intuitive guess that $K$ itself is the answer is wrong. For example consider $K$ to be a thin cylinder in very high dimension. Then we can get $L$ such that $f(L)<f(K)$ by letting $L$ have more volume close to origin.

Hsien-Chih Chang 張顯之
  • 7,638
  • 4
  • 44
  • 83
Ashwinkumar B V
  • 1,584
  • 12
  • 20
  • For the nothing its worth, the problem looks hard. Even in 3d is not obvious how to solve it. – Sariel Har-Peled Jan 08 '12 at 22:42
  • Is it obvious how to do it in 2d optimally? Of course in 2d a constant factor approximation is uninteresting. – Ashwinkumar B V Jan 09 '12 at 09:33
  • It is not obvious to me. Constant factor approximation is obvious in any dimension by approximating the shape by an ellipsoid www.math.sc.edu/~howard/Notes/john.pdf. The constant would depend on the dimension. – Sariel Har-Peled Jan 09 '12 at 15:27
  • I am more interested in constant factor approximation where the constant does not depend on the dimension. – Ashwinkumar B V Jan 09 '12 at 17:23
  • 1
    Naturally. But let me take it back - even the ellipsoid case is not obvious. If you want to attack this problem, that would be the first version to investigate. Intuitively, you have to decide which dimensions to ignore, and which dimensions to expand. It seems the natural solution is the convex-hull of the union of the ellipsoid with another ellipsoid, where the axises of the new ellipsoid are either equal to some parameter r, or are equal to the other ellipsoid. – Sariel Har-Peled Jan 09 '12 at 18:37

3 Answers3

1

If we restrict $K$ and $L$ to be both ellipsoids, then your problem can be solved to any accuracy with an SDP. I know this is not what you asked originally, but it seems we have no solution even for this restricted case, and maybe it can help in general.

So let's say $E$ is the input ellipsoid and we are looking to find an optimal enclosing ellipsoid $J$. There exists a linear map $F$ s.t. $E = FB_2$ and a map $G$ s.t. $J = GB_2$, where $B_2$ is the unit ball. Then $\mathbb{E}_{x \sim J}[\|x\|_2^2] = \frac{1}{n}\mathsf{Tr}(G^TG)$. Also $E \subseteq J \Leftrightarrow J^\circ \subseteq E^\circ$, where $E^\circ$ is the polar body of $E$. Conveniently, $E^\circ = \{x: x^TF^TFx \leq 1\}$ and $J^\circ = \{x: x^TG^TGx \leq 1\}$. It follows that $J^\circ \subseteq E^\circ$ (and therefore $E \subseteq J$) if and only if $G^TG - F^TF$ is a positive semidefinite matrix.

So the SDP is defined by: given a symmetric PSD matrix $M$, find a symmetric PSD matrix $N$ s.t. $N - M$ is PSD and $\mathsf{Tr}(N)$ is minimized. $N$ can be found by solving the SDP and then an SVD will give the axes and axes lengths of $J$.

Sasho Nikolov
  • 18,189
  • 2
  • 67
  • 115
0

The following solution is based on the this assumpotion/conjecture [to be proved]:

Conjecture: The expectation of a convex function on $\textrm{conv}(K\bigcup K')$ is smaller than the larger between the expectation on $K$ and the expectation on $K'$.

[We will need the above only for $K,K'$ convex, but is might be true in general]

Take now any set $K$ and apply a rotation $R$ to it centered on the origin, obtaining $R(K)$. You are going to have $f(K)=f(R(K))$, because the rotation leaves the length of the elements of $K$ invariant. If I am right about the conjecture, $f(\textrm{conv}(K\bigcup R(K)))\leq f(K)$. Since for any optimal $L$ you could consider $L'=\bigcup_R R(L)=\textrm{conv}(\bigcup_R R(L))$, where $\bigcup_R$ indicates the union over all rotations, and have $f(L)\geq f(L') \geq f(L)$, it would seem that the optimal $L$ can be chosen to be the smallest sphere containing $K$.

Marco
  • 101
  • It would be sufficient to prove that $\mathbb{E}{\textrm{conv}(A)}\leq \mathbb{E}{A}$ for the expectation of a convex function. That $\mathbb{E}_{K\bigcup K'}\leq \max{\mathbb{E}_K,\mathbb{E}_K'}$ seems easy. – Marco Feb 08 '12 at 06:08
  • 4
    I am not entirely sure I get your answer. But it is definitely not true that L can be chosen to be the smallest sphere containing K. Consider a long thin cylinder in $d$ dimensions of length $t$. Then any sphere $S$ containing $K$ should have $f(S)\geq t$. But if you construct $L=conv(K\cup U)$ where U is a sphere or radius roughly $c_1 t/d$ you get $f(L)$ roughly $c_2 t/d$. (where $c_1,c_2$ are constants) – Ashwinkumar B V Feb 10 '12 at 19:44
0

(As mentioned in the comments, the following approach does not work. The obtained object is not convex. It characterizes a "star-shaped" object with minimum expected distance though.)

I think the optimal object would be a union of $K$ and some ball centered at the origin. Here are my thoughts. By your definition of $f(L)$, $$ f(L) \sim \int_{{\mathbb S}^{d-1}} \int_{0}^{r_L} x\frac{\mathrm{d}(x^d/x_L^d)}{\mathrm dx}\frac{r_L}{\mathrm{vol}(L)} \mathrm dx\mathrm dS \sim \int_{{\mathbb S}^{d-1}} \frac{r_L^2}{\mathrm{vol}(L)}dS \sim \frac{\int_{{\mathbb S}^{d-1}} r_L^2 dS}{\int_{{\mathbb S}^{d-1}} r_L dS} \stackrel{\mathrm{def}}{=} g(L), $$ where $r_L$ is the distance from the origin to the surface of $L$ along a particular direction. I used $\sim$ instead of =, because I dropped some constants. Now we want to minimize $g(L)$ under the constraints that $r_L \ge r_K$ along any direction. Notice that if $r_K$ along some direction is smaller than $g(K)/2$, then we can make it slightly larger, say increase it by $\epsilon \le g(K)/2 -r_K$, to make $g(K)$ smaller. That is because we increase the enumerator by $(r_L+\epsilon)^2 -r_L^2 = \epsilon(2r_L + \epsilon)$, less than a factor $g(K)$ of the increase in the denominator. Therefore, we can think of gradually "deforming" $K$ (by repeatedly growing the object slightly, and updating $g(\cdot)$) to make its $g(\cdot)$ value smaller. Let $K^*$ be the convex object in the end. Then, any point on $\partial K^*\setminus \partial K$ is at distance $g(K^*)/2$ from the origin, i.e., $K^*$ is the union of $K$ and a ball with radius $g(K^*)/2$.

Indeed, consider another convex object $K'$ such that $g(K') = g(K)$. Then $K^*\subseteq K'$, since otherwise we can grow the part of $K'$ inside $K^*$ to make $g(K')$ smaller. On the other hand, $K'\subseteq K^*$, because otherwise, by the same idea, we can shrink the part of $K'\setminus K$ outside $K^*$ to make $g(K')$ smaller. So there is a unique optimal solution.

user7852
  • 1
  • 1
  • 1
    Maybe I'm missing something, but why is the object generated in this way convex? – mjqxxxx Jan 06 '12 at 18:26
  • @mjqxxxx You are right. How did I miss that... – user7852 Jan 07 '12 at 07:48
  • How about the following idea: it is well known that a convex object can be approximated by some ellipsoid, i.e., there is an ellipsoid $E_K$ such that $E_K\subseteq K\subseteq \sqrt{d}E_K$. Then $f(\sqrt{d} E_K)$ approximates $f(K)$ with approx ratio $d$. For any $L$ containing $K$, $\sqrt{d}E_K \subseteq d E_L$. So if we can find the optimal ellipsoid $E$ containing $\sqrt{d} E_K$, then $f(E) \le d^2 f(L)$. I don't know how to compute $E$. But I would guess its axes align with the axes of $\sqrt{d} E_K$, and all eigenvalues of $\sqrt{d} E_K$ below some threshold are raised to that threshold. – user7852 Jan 07 '12 at 08:15
  • I agree that if L is not restricted to a convex body it is union of K and a ball. – Ashwinkumar B V Jan 08 '12 at 05:49
  • The idea of using ellipsoid won't give you a constant factor. It can give at best a $\sqrt{d}$ approximation. My conjecture is that convex hull of $L$ with a ball of appropriate radius is a constant factor approximation. I am not sure how to prove or disprove the conjecture. – Ashwinkumar B V Jan 08 '12 at 14:21