7
$\begingroup$

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.

Improve this question
$\endgroup$
5
  • $\begingroup$ What does it mean to project to a cone? $\endgroup$
    – Anthony Quas
    Commented Jan 20, 2021 at 17:11
  • 2
    $\begingroup$ 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$. $\endgroup$
    – Yuval Peres
    Commented Jan 20, 2021 at 17:33
  • $\begingroup$ 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$.) $\endgroup$
    – Good Boy
    Commented Dec 21, 2021 at 16:39
  • $\begingroup$ @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. $\endgroup$
    – Daniel Paleka
    Commented Dec 21, 2021 at 18:43
  • 2
    $\begingroup$ 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... $\endgroup$
    – fedja
    Commented Dec 24, 2021 at 21:25

1 Answer 1

Reset to default
1
$\begingroup$

This addresses only the easy part.

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thank you for reproducing some experiments! Proving two fixed input vectors in R^n become correlated during this process should not be the hard part, both in this toy problem and in the larger scope of research. But I don't know whether that helps at all -- how to control the Lipschitz constant in the epsilon net approach? $\endgroup$
    – Daniel Paleka
    Commented Jan 21, 2021 at 17:50
  • $\begingroup$ 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. $\endgroup$
    – Good Boy
    Commented Dec 21, 2021 at 16:35

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .