Let $E$ be a large sparse $l$-by-$n$ matrix ($l$ and $n$ can be in the billions...) with coefficients in $\{-1, 0, 1\}$: the first row of $E$ is the vector $(1,0,0,\ldots,0) \in \mathbb R^n$, and every other row contains exactly one entry equal $1$ (the other entries are thus equal to $0$ or $-1$). Also, let $e := (1,0,0,\ldots,0) \in \mathbb R^l$.

Now consider the convex compact polytope

$$Q := \{z \ge 0 | Ez = e\}.$$

**Question:** Given a point $x \in \mathbb R^n$, how to compute **exactly** (**non-iteratively, etc.**), a point of $Q$ which is closest to $x$. That is how to solve the problem

$$\text{minimize }\frac{1}{2}\|z-x\|^2\text{ subject to }z \in Q$$
exactly. There is a whole zoo of iterative algorithms for solving such problems in signal-processing, but I'm looking for the "book solution". There are strong motivations for demanding this.

**Special cases:** If we take $E = \begin{bmatrix}1 & 0 & \ldots & 0\\1 & -1 & \ldots -1 & -1\end{bmatrix}$ and $e := [1\hspace{.5em}0]^T$, then $Q$ can be identified with the unit simplex in $\mathbb R^{n-1}$, and there are linear-time exact algorithms for projecting (for example, [Condat's algorithm][1] based on median-of-medians).

**Applications:** The set $Q$ defined above can be identified with the strategy profile of a player in the *sequence-form representation* of a sequential game with incomplete information and perfect recall (like Poker, etc.).


  [1]: http://www.gipsa-lab.grenoble-inp.fr/~laurent.condat/publis/Condat_simplexproj.pdf