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.

enter image description here

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

  • $\begingroup$ As far as I remember, projecting onto polyhedra is in general a hard problem (probably as hard as a generic second order cone program?). That your polyhedron is symmetric about the origin is in fact its only special property, i.e. all symmetric polyhedra are of this form. $\endgroup$ – Dirk Jan 3 '16 at 18:19
  • $\begingroup$ @Dirk: Yes indeed projecting onto polyhedra is not an easy business in 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
  • $\begingroup$ @dohmatob Let $x = y - a$ then problem 1 becomes $\arg\min ||x||^2$ subject to $X^Tx \le \mathbf{1} - X^T a$. The RHS in the inequality is a known vector, say $b$. Now this standard form can be found in textbooks, for example math.stackexchange.com/a/293010/52858 is a nice answer that shows active set methods and interior point methods for solving this problem. The active set methods seem similar to your approach. I am no expert but I guess that methods that try to estimate the inequalities that are satisfied exactly at the solution would need the info that you ask for in problem 2 $\endgroup$ – Pushpendre Jan 4 '16 at 7:58
  • 1
    $\begingroup$ As already explained in my question above, I'm aware of iterative schemes for solving this problem (and there are really a dozen of them, beyond interior point methods...). But I'm intentionally not considering these. I'm interested in something analytic: I need bounds, inequalities, etc. $\endgroup$ – dohmatob Jan 4 '16 at 10:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.