flat similarity

[gusl]

I previously inquired about a natural measure of "hyperplane similarity". But what I meant was "flat similarity": hyperplanes are flats with codimension 1, which makes this easy (we can simply take the dot product of the unit normals)

So again:
(1) What is a natural measure of flat similarity? Let's call our flats V and W. WOLOG, let's assume that V and W go through the origin.

rdore proposed that projecting to the orthogonal complement of V ∩ W won't change the answer. However, in general this won't give you vectors. Can we instead pick an arbitrary plane that is orthogonal to both flats (i.e. a 2D subspace of the above), thus ensuring that the projections are vectors?

So here's another basic question:

(2) Given two flats that go through the origin (with dimension m and n), what is the (a) maximum, and the (b) minimum/typical dimension of their intersection?

Thanks to Don Sheehy, I learned that the space of k-flats forms a manifold known as the Grassmannian, in which we can talk about geodesics. Geodesics give at least a partial order, which may be a first step towards a metric.

I'm feeling generally shocked at my ignorance of geometry. Here are some concepts to study:

http://en.wikipedia.org/wiki/Plücker_coordinates
http://en.wikipedia.org/wiki/Vector_bundle
http://en.wikipedia.org/wiki/Gauss_map
http://en.wikipedia.org/wiki/Gaussian_curvature
http://en.wikipedia.org/wiki/Real_projective_plane

Comments

[pbrane.livejournal.com]

I have never heard these describe as "flats" before (and in fact for some reason I hate that term). In mathematics, I've always heard them simply described as k-planes (if they are k-dimensional).

(1) What is a natural measure of flat similarity? Let's call our flats V and W. WOLOG, let's assume that V and W go through the origin.


How is this general? Is the location of the plane not important for what you are considering (you only care about shape/orientation)? If this is the case (you're trying to generalize cosine similarity between vectors [which are equivalent to oriented lines *through the origin*]), then ok.

I'm not sure how much sense it makes to consider similarity of k-planes of differing dimension, but if it does, I'm not sure what you can do with Grassmannians and them - G_k,m is the manifold of k-planes in R^m, but G_k,m and G_k',m are different manifolds for k != k', so you can't meaningfully talk about geodesics from a k-plane to a k'-plane without making some new space in which they both live.

(2) Given two flats that go through the origin (with dimension m and n), what is the (a) maximum, and the (b) minimum/typical dimension of their intersection?

Clearly the answer to (a) is min(m,n). For (b), if the dimension of the ambient space in which the m-plane and n-plane is "d", then if d is greater than m+n, then "almost all" (all but a set of measure zero) m-planes and n-planes intersect trivially: zero-dimensionally - just the origin.

[gustavolacerda.livejournal.com]

oh you're right, I'm only interested in similarity between flats of the same dimension.


<< For (b), if the dimension of the ambient space in which the m-plane and n-plane is "d", then if d is greater than m+n, then "almost all" (all but a set of measure zero) m-planes and n-planes intersect trivially: zero-dimensionally - just the origin. >>

hmmm... I thought that "almost all" pairs of planes intersected on a line, regardless of d.
How do you know this?

[pbrane.livejournal.com]

hmmm... I thought that "almost all" pairs of planes intersected on a line, regardless of d.

Let U and V be a pair of 2-planes in d-dimensions, and lets choose coordinates such that U = { (x, y, 0, 0, ..., 0) | x, y real }. So now V = { a v + b v' | a, b real, v, v' in R^d such that v.v' = 0 }. The intersection of U and V is therefore the set of points in V such that the final (d-2) coordinates are zero, or the set of simultaneous solutions to a v_3 + b v'_3 = a v_4 + b v'_4 = ... = a v_d + b v_d = 0. This is (d-2) homogeneous linear equations in 2 unknowns (a, b), and in general has no solutions other than the trivial one: the origin.

More generally, U = { (x_1, x_2, ..., x_k, 0, 0, ..., 0) | x_i real }, and V = { sum a_i v_i | a_i real, v_i in R^d s.t. v_i.v_j = delta_ij }, then the intersection of U and V is the set of solutions to sum(a_i v_ij) = 0 for all j = k+1, ... , d. This is (d-k) equations in k unknowns, and will have no nontrivial solutions for k less than d/2.

This is maybe easier to see if you think about the opposite problem: what is the dimensionality of the space spanned by the k + k' vectors u_1, ... u_k, v_1, ..., v_k'? The dimension of the intersection will then be k+k'-dim(span(u_i,v_i)). But in general, if you have m orthogonal vectors, and you start taking more d-vectors, unless you already have the entire d-space, typically the next vector does not lie in the space you've already built: unless k+k' is greater than d, the space spanned by k+k' vectors is k+k'-dimensional!

[gustavolacerda.livejournal.com]

<< So now V = { a v + b v' | a, b real, v, v' in R^d such that v.v' = 0 } >>

Doesn't this make V = R^d ? I think there's a typo here.


<< unless k+k' is greater than d, the space spanned by k+k' vectors is k+k'-dimensional! >>

do you mean "is d-dimensional"?

[pbrane.livejournal.com]

Doesn't this make V = R^d ? I think there's a typo here.

v, v' are a pair of *fixed* vectors such that v.v' = 0. Sorry if that wasn't clear - V = span(v, v')

do you mean "is d-dimensional"?

No, if k + k' is *less than* d, then typically the k+k' vectors span a k+k'-dimensional subspace of R^d (in particular the space of this span is not strictly less than k+k'). If k+k' is greater than or equal to d, then the span of k+k' randomly chosen vectors spans all of R^d.

[pbrane.livejournal.com]

To clarify why k+k' vectors in a d-greater-than-(k+k')-dimensional space span a k+k'-dimensional space (and not less), proceed inductively: you have n-vectors spanning a n-dimensional space (n less than d-1), and you now take another randomly chosen d-vector. Pick coordinates on your space such that the span of the n-vectors are the just those x = (x_1, ..., x_n, 0, 0, ..., 0) (nonzero only for the first n dimensions out of d). Then a generic d-vector in these coordinates is y = (y_1, ..., y_d). The subset of these y's which has y_(n+1) = y_(n+2) = ... = y_d = 0 is measure zero in the set of all d-vectors (since it lies in a n-dimensional subspace of d-dimensions).

[pbrane.livejournal.com]

oh you're right, I'm only interested in similarity between flats of the same dimension.

In this case your answer is simple: the Grassmannian's have a metric (defined in the usual way for a connected Riemanninan manifold: the distance between two points is the length of the shortest geodesic connecting them), and this means your k-planes can inherit this metric directly as their similarity measure, and in fact this reduces to cosine similarity for 1-planes (lines), if you use the natural angular coordinates for the Grassmannian inherited from their definition as a homogeneous space O(n) / (O(k) x O(n-k)).

[gustavolacerda.livejournal.com]

how would you write down the geodesic for two k-planes? how would you compute its length (the distance between them)?

[pbrane.livejournal.com]

Ahh, computation. I knew it would come to that. :P You've gone from a question of linear algebra, to one of differential geometry on Lie groups! I'll get back to you in a bit on that and see if I've got a rigorous answer on that.

[pbrane.livejournal.com]

for the last part of (b), regardless of whether m+n is greater or less than d, then the generic dimension of the intersection of an m-plane and an n-plane in d-dimensions is min(0, m+n-d), which follows via the same logic which gets you that the intersection is trivial when d is greater than m+n.

[gustavolacerda.livejournal.com]

<< min(0, m+n-d) >>

This number is never positive!

[pbrane.livejournal.com]

sorry, max(0, m+n-d). :P

[bhudson.livejournal.com]

I've definitely heard (and used) the term flat, meaning an affine subspace. The term hyperplane often gets people really focussed on the codimension 1 case, to the point of annoyance when you tell them you're talking arbitrary codimension -- I've never understood why.

[pbrane.livejournal.com]

This is why I've often used merely "plane" or "k-plane" if k isn't clear from context, so as to avoid confusion with "hyper-" meaning n-1, instead of just "generalized"-".

Flat is an adjective! Turning verbs into nouns is bad enough, now adjectives need to be nouns too? :P

[bhudson.livejournal.com]

You probably *live* in a flat. And eat oranges.

[pbrane.livejournal.com]

Maybe in England I'd live in a flat (if I weren't living a house, like I am now), but yes, I suppose I eat oranges.

[staskikotx.livejournal.com]

Why not to take

r(V, W) = inf_{v in V, w in W} arccos( (v; w)/(|v||w|))

[gustavolacerda.livejournal.com]

in other words, v and w are unit vectors, and you minimize the angle between them?

[gustavolacerda.livejournal.com]

The problem is: this angle is always 0.

Here's my idea:

max_{v in V} min_{w in W} angle(v,w)
where angle(v,w) = arccos(dot(v,w)/(|v||w|))


I suspect this will be equivalent to what I proposed in the post:

<< rdore proposed that projecting to the orthogonal complement of V ∩ W won't change the answer. However, in general this won't give you vectors. Can we instead pick an arbitrary plane that is orthogonal to both flats (i.e. a 2D subspace of the above), thus ensuring that the projections are vectors? >>