# Iterating projections to random halfspaces

Consider the following process:

• Start with a set $$S = \mathbb R^n$$. Repeat $$L$$ times: choose a random orthonormal basis $$u_1, \ldots, u_n$$, and consider the cone $$C = \{ \sum \alpha_i u_i : \alpha_i \in \mathbb R_{\ge 0} \}$$. Project $$S$$ to this cone.

What is the minimum dot product between two unit vectors in $$S$$, after $$L$$ iterations? Can it be bounded away from zero, say with high probability in $$n$$?

See the illustration of the process for $$n = 2$$. The red area outlines the set $$S$$. After projecting to the cones defined by the blue, green, and orange bases, the set $$S$$ becomes contained in a line.

The regime of interest is ideally $$L = O(1)$$, but $$L = o(n)$$ could also work.

• What does it mean to project to a cone? Jan 20, 2021 at 17:11
• There is a projection map $P_K(x)$ to any closed convex set $K$ in Hilbert space. $P_K(x)$ is the unique closest point to $x$ in $K$. Jan 20, 2021 at 17:33
• In line with my comment below, what do you do when $S$ is mapped onto the origin? (This happens when $S$ is wholly contained in $-C$.) Dec 21, 2021 at 16:39
• @GoodBoy Sorry for the ambiguity. In that case, define the minimum as $+\infty$. I may rephrase the question to the simpler "Can we rule out the existence of two orthogonal vectors in S after L iterations, with high probability?", to avoid similar formal difficulties. Dec 21, 2021 at 18:43
• The problem is that even if you have two rays at a small angle in $\mathbb R^3$ at some moment, there is always a chance that they become $(a,-b,-1)$ and $(-c,d,-1)$ with small $c,d>0$ after the rotation to the new orthonormal basis, so after the projection they will give two orthogonal vectors again, i.e., there is no deterministic monotonicity in the process. Well, this just makes it more interesting... Dec 24, 2021 at 21:25

The unit $$(n-1)$$-sphere in $$\mathbb{R}^n$$ is covered by finitely many disks (sectors) each portending an acute cone from the origin. Each projection to a half-space of an acute cone becomes the union of (possibly) a subset of the intersecting hyperplane with (possibly) a sub-cone of the cone, also acute. Eventually, with probability $$1$$, each cone (or sub-cone) will lie entirely outside a half-space and therefore will be projected into a hyperplane. Since there are only finitely many cones, all of $$\mathbb{R}^n$$ will eventually project into a finite union of subsets the hyperplanes defining the half-spaces. This has measure $$0$$.
For the harder question, I did some experimenting. First notice that a ray (semi-line from the origin) is always projected to a ray. Then I ran some simulation in $$\mathbb{R}^3$$, and noticed that starting from 2 rays, no matter what the angle between them is, eventually I always end up with an angle between them of less than pi/180, almost always within less than 100 iterations, and typically within less than 30. It would be tedious but not hard to run such simulations for other dimensions and to collect some data. Though I wonder if floating point precision could quickly become an issue.
In $$\mathbb{R}^2$$ it's pretty obvious that we'll eventually hit, with probability 1, a pair of projections such that first brings two starting rays to within an acute angle of each other, and the second projects both of those rays into a single one. So eventually all of $$\mathbb{R}^2$$ has to end up in a single ray, as the OP was speculating.
• It is not always the case that a ray is projected to a ray (in the harder question): for example, the projection of the ray $\mathbb R \cdot (-1,-1)$ onto the positive quadrant $\{(x,y) \mid x,y\ge 0\}$ is just the origin. Dec 21, 2021 at 16:35