Let $X$ be an $n$-by-$p$ matrix and consider the closed convex polyhedron

$$\mathcal P_X := \{y \in \mathbb R^n | \|X^Ty\|_\infty \le 1\}.$$ Notice that $\mathcal P_X$ is symmetric about the origin.

**Problem 1:** Given a point $a \in \mathbb R^n$ with $a \not \in \mathcal P_X$, how to compute the euclidean projection of $a$ on $\mathcal P_X$, i.e to solve the convex optimization problem

$$\text{minimize }\frac{1}{2}\|y - a\|^2\text{ subject to }y \in \mathcal P_X.$$

Let $\mathrm{proj}_{\mathcal P_X}(a)$ denote the unique solution. There is probably a zoo of iterative algorithms (from signal-processing literature, e.g) for approximately solving such problems, but I'd prefer a solution with an analytical taste. Utilimately, I'd like to

**Problem 2:** Find for any index $j \in \{1,2,\ldots,p\}$, a *good* upper-bound for the quantity $$|X^T_j\mathrm{proj}_{\mathcal P_X}(a)|.$$
For example, the bound $|X^T_j\mathrm{proj}_{\mathcal P_X}(a)| \le 1$ is immediate, but useless... Ideally, given $j$, I'd like to predict if $|X^T_j\mathrm{proj}_{\mathcal P_X}(a)| < 1$.

**Some basic observations:** A general strategy is to locate $\mathrm{proj}_{\mathcal P_X}(a)$ within a *simple* and *small* set $K$, and then bound $$|X^T_j\mathrm{proj}_{\mathcal P_X}(a)| \le \sup_{y \in K}|X^T_jy|.$$

"Simple" means the above supremum is easy to compute, and "small" means this supremum approximates $|X^T_j\mathrm{proj}_{\mathcal P_X}(a)|$ well (i.e the smaller the supremum, the better). For example, if one could find a small sphere $K := \{y | \|y - c\|_2 \le r\}$ containing $\mathrm{proj}_{\mathcal P_X}(a)$, then it would follow that $$|X^T_j\mathrm{proj}_{\mathcal P_X}(a)| \le r\|X^T_j\|_2 + |X^T_jc|.$$

It's not easy to find such spheres giving tight bounds. However, using the variational characterization of projection onto closed convex sets, it's easy to show that as $y$ runs through $\mathcal P_X$, all the spheres with center $\frac{1}{2}(y + a)$ and radius $\frac{1}{2}\|y-a\|_2$ contain $\mathrm{proj}_{\mathcal P_X}(a)$, and in fact, this is the only point common to all these spheres and $\mathcal P_X$. Note that these spheres give an arbitrarily bad approximation if the point $a$ is far from $\mathcal P_X$, as this point must ly on the surface of each such sphere...

**Yet another random observation:** Suppose $X$ has non-zero rows, and let $D_X := \mathrm{diag}(\|X_1\|_\infty,\ldots,\|X_n\|_\infty)$, and $\mathbb B_1$ be the unit ball w.r.t the $\ell_1$-norm. Then

$$Z_{D_X} := D_X^{-1}\mathbb B_1 \subseteq \mathcal P_X.$$

Note that like $\mathcal P_X$, $D_X^{-1}\mathbb B_1$ is also symmetric about the origin. Also, note that it is straight-forward to project onto $Z_{D_X}$, as this problem is essentially equivalent to projecting onto a simplex, for which there are linear-time exact algorithms, etc.

A strategy could then be, starting with the template $Z_{D_X}$, find an invertible diagonal matrix $D$ such that $Z_D := D^{-1}\mathbb B_1 \subseteq \mathcal P_X$ and $\mathrm{proj}_{\mathcal P_X}$ is sufficiently close to the boundary of $Z_D$. Then use this closest boundary point as an approximation for $\mathrm{proj}_{\mathcal P_X}$.

**Some geometric experiments**

Refer to the figure above. The following are less important problems which are interesint in their own right.

**Question:** What are necessary and sufficient conditions on $D$ which ensure that $Z_D \subseteq \mathcal P_X$ ? What can be said about the triangle $APQ$ ?

For example, it is immediate that

$$\max\left(\frac{1}{2}AP, PQ\right) \le QA \le AP + PQ,$$

since $QA \ge PQ$, by the variational characterization whispered above, and $AP \le PQ + QA$, by the triangle inequality. As a particular consequence, the point $Q$ can be made an arbitrarily bad approximation for the projection point $P$ by taking the projected point $A$ sufficiently far from the polytope $\mathcal P_X$.

**Question:** Which minimal conditions on the matrix $X$ ensure that the distance between the boundaries of $\mathcal P_X$ and $Z_{D_X}$ is small? Note that this would give us control over $PQ$.

onlyspecial property, i.e. all symmetric polyhedra are of this form. $\endgroup$ – Dirk Jan 3 '16 at 18:19in general. But as is always the case, inherent structure (in the form of symmetry, etc.) can drastically help the solution to an otherwise very hard problem. Also, I think being symmetric about the origin is quite some structure. For example, think of the Minkowski convex body theorem :). $\endgroup$ – dohmatob Jan 3 '16 at 18:32