Intersecting Simplices with Normballs

28 Views Asked by At

Let $e$ be the vector of all ones 's consider the standard simplex $$\Delta_m:=\{x\in\mathbb{R}^m_+: \langle x, e\rangle=1\}.$$ Then the truncated simplex $\Delta_m^d$ is given as $$\Delta_m^d:=\{x\in\Delta_m \colon \|x\|_0\leq d\}$$ where $\|x\|_0$ is the number of nonzero entries of $x$, that is, $\Delta_m^d$ is the union of lower dimensional faces of $\Delta_m$.

Now consider the optimization problem $\min_{x\in\Delta_m^d} \|e-x\|_p^p$ which has optimal solution $(m-d)+d(1-\tfrac{1}{d})^p$. This yields the inequality $$g_{(p,m,d)}(x)=\|e-x\|_p^p-[(m-d)+d(1-\tfrac{1}{d})^p]\geq 0$$ which is true for all points $x\in\Delta_m^d$ but cuts off points $x\in\Delta_m$. Define $$C_p(m,d)=\{x\in\Delta_m\colon g_{(p,m,d)}(x)<0\}$$ to be the cutoff area.

I would like to show that the $C_p(m,d)$ yield a ascending chain in $p$ which converges against $\Delta_m\setminus \Delta_m^d$, such that $$\Delta_m^d=\lim_{p} \{x\in \Delta_m \colon g_{(p,m,d)}(x)\geq 0\}.$$ I think I can actually show that each point $x\in \Delta_m\setminus \Delta_m^d$ is contained in some $C_p(m,d)$, but not that the sets are an ascending chain. I tried for 2 days now but so far I had no luck. Since the $C_p(m,d)$ are convex, it would suffice to show that their boundary is contained in the closure of the next set. Any suggestions?