Suppose we have a collection of linear subspaces $\mathbb{C}$ lying in $\mathbb{R}^d$, such that each $c \in \mathbb{C}$ is of dimension at most $k \leq d$ for a given fixed $k$ and $|\mathbb{C}| = n$. Now we want to find the subspace of dimension at most $k$ closest to each $c \in \mathbb{C}$ under the sin-theta distance. (Note we do not restrict this optimal subspace to be chosen from $\mathbb{C}$).

How can compute this and how much time would this take? This seems simple enough that it might be standard and well-known, perhaps under the right geometric transformation? Even an exponential time algorithm would be very useful - I am more interested in computability rather than optimal efficiency.

To be more precise, define the sin-theta distance for two linear subspaces $L$ and $M$ as follows: $\sin \theta(L,M) = \max_{x \in L, ||x|| = 1} \min_{y \in M, ||y|| = 1} || x - y||_2$. (This is symmetric if and only if $L$ and $M$ are of equal dimensionality.)

Now if we let $S$ be the space of all subspaces of $\mathbb{R}^d$ of rank at most $k$ our problem reduces to finding $\text{argmin}_{s \in S} \sin \theta (\mathbb{C}, s)$.

Note: Having though about this where all the subspaces are of dimension exactly $k$, the problem simply maps to having a collection $\bar{\mathbb{C}}$ of $n$ points on the surface of the sphere $\mathbb{S}^{d-1}$ and finding the point closest to them. It becomes more tricky where the subspaces in $\mathbb{C}$ are of varying dimensions, as you introduce more degrees of freedom.

  • 1
    $\begingroup$ Look up Alexander Barg work on Grassmannian Codes. $\endgroup$
    – Mr.
    Sep 27 '13 at 16:06
  • $\begingroup$ What is the rank of a linear subspace? $\endgroup$
    – Yury
    Sep 27 '13 at 17:08
  • 1
    $\begingroup$ Ah, sorry. My notation was poor. I mean, the dimensionality of the subspace - i.e, a line could be of rank 1, a plane would of rank 2 and so on. I'll modify it. $\endgroup$
    – Amir
    Sep 27 '13 at 20:12
  • 1
    $\begingroup$ you can guess the optimal dimension for the answer (enumerate all choices). Secondly, for a fixed ball of fixed dimension, the distance function to any given objects is some kind of second degree polynomial defined on the ball, and so you're trying to walk over the lower envelope of the arrangement of polynomials. Finally, you'd need to reason about critical points that form as this ball moves. It's a horrendous calculation, but there's likely nothing in here that isn't "computable" (since that's all you care about :)) $\endgroup$ Sep 28 '13 at 6:34

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.