Schubert varieties and distances between subspaces of different dimensions

Ke Ye; Lek-Heng Lim

Source-linked AI summary

Schubert varieties and distances between subspaces of different dimensions

Ke Ye, Lek-Heng Lim

arXiv:1407.0900v3Jul 3, 2014math.NAmath.AG

TL;DR

The paper addresses how to extend Grassmann distance from equidimensional to different-dimensional subspaces. It defines the extension as a point-to-Schubert-variety distance within the Grassmannian and establishes computability, invariance, and compatibility with standard distances. The construction also supports metrics for subspaces of all dimensions and a volumetric probability analogue.

Problem
Distances for different-dimensional subspaces are needed in broad applications, but existing proposals are ad hoc and do not specialize to the Grassmann distance.
Method
The paper defines the distance from a subspace to the nearest equidimensional subspace contained in or containing the other, interpreting this as distance to a Schubert variety.
Results
The resulting distance is SVD-computable, reduces to Grassmann distance for equal dimensions, is independent of coordinates and ambient dimension, and can pair with other common subspace distances.
Takeaways & Limitations
The framework provides an intrinsic algebraic-geometric treatment of subspaces of unequal dimensions and extends to metrics on the space of subspaces of all dimensions.
Takeaways & Limitations
The principal point-to-set distance is not a metric because distinct nested subspaces can have distance zero.

Abstract

from arXiv · show

We resolve a basic problem on subspace distances that often arises in applications: How can the usual Grassmann distance between equidimensional subspaces be extended to subspaces of different dimensions? We show that a natural solution is given by the distance of a point to a Schubert variety within the Grassmannian. This distance reduces to the Grassmann distance when the subspaces are equidimensional and does not depend on any embedding into a larger ambient space. Furthermore, it has a concrete expression involving principal angles, and is efficiently computable in numerically stable ways. Our results are largely independent of the Grassmann distance --- if desired, it may be substituted by any other common distances between subspaces. Our approach depends on a concrete algebraic geometric view of the Grassmannian that parallels the differential geometric perspective that is well-established in applied and computational mathematics.

1. Introduction

Subspace-valued data is common, but applications often involve subspaces of different dimensions, for which existing distances are ad hoc and do not recover the Grassmann distance. The paper proposes a Schubert-variety distance with intrinsic, computational, and geometric advantages.

Motivation: Modern biological, image, and text datasets can be represented as matrices with massive sample sizes, high dimensionality, or both.Such data are often more usefully analyzed through the subspaces defined by their rows, columns, or principal components.
Motivation: Subspace-valued data arise across applications including computer vision, bioinformatics, machine learning, communications, classification, and computational mathematics.The paper also lists applications involving different-dimensional subspaces, such as information retrieval, facial recognition, and network analysis.
Existing framework: The Grassmann distance gives an intrinsic, coordinate-independent distance for equidimensional subspaces and is computable from principal angles using SVD.Other common Grassmannian distances include Asimov, Binet–Cauchy, chordal, Fubini–Study, Martin, Procrustes, projection, and spectral distances.
Problem: Different-dimensional subspaces are common in applications, but containment gap and symmetric directional distance are ad hoc and do not reduce to the Grassmann distance.For example, principal subspaces selected by a noise threshold can have different dimensions.
Main contribution: The proposed distance is the distance from a point to a Schubert variety within the Grassmannian.It is computable via SVD, coordinate-independent, ambient-dimension-independent, and compatible with other common Grassmannian distances.
Main contribution: The point-to-set distance is not a metric because distinct subspaces can have distance zero when one contains the other.The paper separately develops a metric for subspaces of all dimensions using a related furthest-subspace construction.

2. Grassmannian of linear subspaces

The Grassmannian represents fixed-dimensional subspaces as equivalence classes of orthonormal frames and carries a Riemannian geometry. Principal angles, obtained from the SVD of basis inner products, provide the computational link to Grassmann distance.

Definitions: The Grassmannian Gr(k, n) consists of k-dimensional subspaces of R^n, while the Stiefel manifold consists of orthonormal k-frames.A subspace corresponds to all orthonormal frames related by right multiplication with an orthogonal matrix.
Geometry: The orthogonal group acts transitively on Gr(k, n), allowing any k-plane to be rotated onto any other k-plane.The Grassmannian and Stiefel manifold have dimensions k(n−k) and nk−k(k+1)/2, respectively.
Geometry: The Grassmannian inherits a Riemannian metric whose geodesic distance is the Grassmann distance for equidimensional subspaces.This construction is intrinsic to the manifold rather than tied to a particular coordinate representation.
Principal angles: Principal vectors are obtained by recursively maximizing paired inner products between orthogonal unit vectors in the two subspaces.The resulting principal angles satisfy 0 ≤ θ_1 ≤ ··· ≤ θ_r ≤ π/2, where r=min(k,l).
Principal angles: The principal angles are computed from the singular values of A^TB using θ_i = cos^-1 σ_i.Orthonormal bases and QR/SVD procedures provide a practical computational route.
Distance computation: When k=l, the principal angles determine the Grassmann distance and an explicit minimizing geodesic between the subspaces.The SVD also supplies the principal vectors used to describe intersections and geodesic coordinates.
Related distances: The framework is presented alongside several alternative distances on Gr(k, n), summarized in Table 2.These include distances expressed through principal angles and orthonormal bases.

3. The Infinite Grassmannian

The paper extends Grassmannian geometry across ambient dimensions by constructing an infinite Grassmannian whose finite-dimensional inclusions preserve distances. This makes distances and minimizing geodesics independent of the chosen ambient dimension.

3. The Infinite Grassmannian: The infinite Grassmannian Gr(k,∞) is defined as the direct limit of the family Gr(k,n) under natural inclusions.Finite-dimensional subspaces are identified with their images in larger ambient spaces.
3. The Infinite Grassmannian: A distance on Gr(k,∞) is defined using any sufficiently large finite Grassmannian containing both subspaces.Isometry guarantees that the resulting value is well-defined and independent of the chosen dimension.
3. The Infinite Grassmannian: The Grassmann distance between two k-planes is therefore independent of the ambient dimension and its minimizing geodesic extends to Gr(k,∞).The same ambient-dimension independence is established for the other distances in Table 2.
3. The Infinite Grassmannian: Isometric inclusions embed Gr(k,n) into Gr(k,m) without changing distances based on principal angles.The result applies to the Grassmann distance and the other listed common Grassmannian distances.

4. Distances between subspaces of different dimensions

The paper defines distance between unequal-dimensional subspaces as a distance to Schubert varieties in Grassmannians. The two natural containment-based formulations coincide, yielding an intrinsic, ambient-independent, principal-angle-computable distance.

4. Distances between subspaces of different dimensions: The Schubert varieties are closed, uniquely determined by the subspaces, and can be viewed as sub-Grassmannians.This ensures the nearest-point minima used in the definition are attained.
4. Distances between subspaces of different dimensions: The proposed distance is intrinsic because it is measured within a Grassmannian rather than after embedding Grassmannians into an arbitrary ambient manifold.It remains unchanged when the subspaces are regarded in larger ambient spaces.
4. Distances between subspaces of different dimensions: When k=l, the distance reduces to the usual Grassmann distance and is independent of the ambient dimension n.The theorem states invariance for all n≥l+1.
4. Distances between subspaces of different dimensions: The distance has an explicit expression in terms of the principal angles between A and B and can be computed using the singular value decomposition.The construction is supported by principal vectors and explicitly realizes closest points on both Schubert varieties.
4. Distances between subspaces of different dimensions: For k≤l, the distance from A to the nearest k-plane contained in B equals the distance from B to the nearest l-plane containing A.These candidate sets are the Schubert varieties Ω−(B) and Ω+(A), respectively.
4. Distances between subspaces of different dimensions: The equality and construction extend beyond the Grassmann distance to the other common distances listed in Table 2.The proof uses principal angles and an isometric orthogonal-complement correspondence.

5. Grassmannian of subspaces of all dimensions

The paper extends subspace distances to all dimensions by defining a premetric on the doubly infinite Grassmannian, while showing that the resulting topology is non-Hausdorff and non-metrizable. It also distinguishes this construction from a metric on all-dimensional subspaces.

Premetric limitations: The distance δ is a point-to-set distance, so distinct nested subspaces can have zero separation and δ is not a metric.Specifically, δ(A, B) = 0 iff A ⊆B or B ⊆A, and it can also fail the triangle inequality.
All-dimensional Grassmannian: All-dimensional subspaces are parameterized by the doubly infinite Grassmannian Gr(∞, ∞), formed as a direct limit of Grassmannians with inclusion maps.The construction uses generalized embeddings for subspaces whose dimensions and ambient dimensions both vary.
Topology: The distance δ induces a topology on Gr(∞, ∞) consistent with the usual topology on each fixed-dimensional component, but not the disjoint union topology.Its restriction to Gr(k, ∞) agrees with the topology induced by the Grassmann distance.
Topology: The induced topology is non-Hausdorff and therefore non-metrizable because nested subspaces cannot be separated by open sets.This contrasts with its metric behavior on every fixed-dimensional Grassmannian.
Metrics and categorical boundary: The paper constructs metrics on Gr(∞, ∞) that restrict to the usual fixed-dimensional Grassmann distances without requiring a coproduct in the category of metric spaces with contractions.A broader categorical setting admits coproducts, but the resulting disjoint-union metric is unrelated to δ.

6. Metrics for subspaces of all dimensions

The paper converts distances for unequal-dimensional subspaces into metrics on Gr(∞, ∞) by completing principal-angle lists with right angles and combining distance with dimension difference. These constructions are metrics and retain the corresponding equal-dimensional distances.

Metric construction: For k ≤ l, the metric construction sets θ_k+1 through θ_l to π/2 and applies the chosen l-dimensional Grassmannian distance.This is equivalent, in sufficiently large ambient dimension, to completing the smaller subspace with l − k orthonormal vectors perpendicular to the larger subspace.
Metric properties: For equal-dimensional subspaces, these all-dimensional metrics restrict to the corresponding metrics on Gr(k, ∞).Thus the construction preserves the established fixed-dimensional distances rather than replacing them.
Metric construction: The resulting expressions combine the unequal-dimensional distance δ∗ with the dimension difference |dim A − dim B| through a root mean square or indicator function.The construction applies to several common subspace distances, including Grassmann, chordal, and Procrustes distances.
Metric properties: The expressions in Table 3 and equation (19) are metrics on Gr(∞, ∞).The proof reduces the nontrivial triangle inequality cases to the triangle inequality in a suitably embedded equal-dimensional Grassmannian.
Geometric interpretation: The Grassmann metric equals the distance to the furthest compatible subspace, with Proposition 16 expressing equivalent maximizations over subspaces containing or contained in the inputs.The equality is stated for k ≤ l ≤ n/2 in the cited proposition.
Categorical boundary: These metrics do not serve as coproducts in the category of metric spaces with continuous contractions, despite satisfying the metric axioms.The paper identifies this as a categorical compatibility limitation rather than a failure of metricity.

7. Comparison with existing works

The paper places its construction alongside the containment gap and symmetric directional distance, showing that both existing proposals arise as special cases of the proposed distance or metric.

Unifying comparison: Both existing proposals are special cases of the paper’s unequal-dimensional distance and its all-dimensional metric.This connects established application-oriented distances to the proposed Grassmannian framework.
Containment gap: The containment gap is equivalent to the projection distance δπ in Theorem 12.The paper further realizes it symmetrically through nearest subspaces in the corresponding Grassmannians.
Containment gap: The containment gap also admits the alternative realization obtained from the nearest l-dimensional subspace containing A.This relation follows from Theorem 12 and was not previously observed for the containment gap.
Symmetric directional distance: The symmetric directional distance is equivalent to the chordal metric dκ introduced for subspaces of different dimensions.It is described as popular in machine-learning applications.

8. Geometry of Ω+(A) and Ω−(B)

The sets Ω+(A) and Ω−(B) are Schubert varieties and can be treated as Grassmannian-like geometric objects. They also admit dual descriptions and a common projection-matrix representation.

Ω+(A) and Ω−(B) are Schubert varieties in Gr(l, n) and Gr(k, n), respectively.
Orthogonal complementation identifies Ω+(A) with Ω−(A⊥) and Ω−(B) with Ω+(B⊥), showing that both constructions are essentially the same type of object.
The maps A ↦ Ω+(A) and B ↦ Ω−(B) are injective, allowing subspaces of different dimensions to be represented as distinct subsets of one Grassmannian.
Each Ω+(A) is algebraically and smoothly isomorphic to Gr(l − k, n − k), while each Ω−(B) is isomorphic to Gr(k, l).The first identification uses X ↦ X/A; the second regards k-dimensional subspaces in Ω−(B) as subspaces of B.
Any two points in Ω−(B) or Ω+(A) can be joined by a length-minimizing geodesic in the corresponding ambient Grassmannian.These geodesics need not be unique, so the varieties are not geodesically convex.
Under the orthogonal-projection representation, Gr(k, n), Gr(l, n), Ω+(A), and Ω−(B) are all subvarieties of R^n×n.Ω+(A) consists of rank-l projections whose images contain A, while Ω−(B) consists of rank-k projections whose images lie in B.

9. Probability density on the Grassmannian

The natural Riemannian volume density on the Grassmannian induces uniform probability measures, under which the two containment probabilities are equal. Their relative volumes share a value determined only by the dimensions k, l, and n.

The probability that a random l-dimensional subspace contains A equals the probability that a random k-dimensional subspace is contained in B.
The Grassmannian’s Riemannian metric induces a volume density and a natural uniform probability density.
The relative volumes of Ω+(A) in Gr(l, n) and Ω−(B) in Gr(k, n) are equal and depend only on k, l, and n.
Because relative volume uses the ambient-space volume, its dependence on n differs from the corresponding dimension-independent statement for the main distance result.

10. Conclusions

The paper addresses the gap in distances and metrics for subspaces of unequal dimensions while developing geometric models across all subspace dimensions. It complements the differential-geometric view of Grassmannians with an algebraic-geometric perspective.

The paper fills a major gap by defining distances and metrics for subspaces of unequal dimensions.
It develops simple geometric models for subspaces of all dimensions.
It enriches the established differential-geometric perspective on Grassmannians with algebraic-geometric perspectives.