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$.
