Return to Question

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$, and there are linear-time exact algorithms for projecting (for example, Condat's algorithm 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.).

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

Let $E$ be a sparse $l$-by-$n$ matrix 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 $l = 1$, then $Q$ is precisely the unit simplex in $\mathbb R^n$, and there are linear-time exact algorithms for projecting (for example, Condat's algorithm 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.).

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$, and there are linear-time exact algorithms for projecting (for example, Condat's algorithm 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.).

Let $E$ be a sparse $l$-by-$n$ matrix 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'd I'm looking for the "book solution". There are strong motivations for demanding this.

Special cases: If we take $l = 1$, then $Q$ is precisely the unit simplex in $\mathbb R^n$, and there are linear-time exact algorithms for projecting (for example, Condat's algorithm 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.).

Let $E$ be a sparse $l$-by-$n$ matrix 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 $l = 1$, then $Q$ is precisely the unit simplex in $\mathbb R^n$, and there are linear-time exact algorithms for projecting (for example, Condat's algorithm 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.).