子空间的距离

在机器学习研究中，我们有时会遇到以“一个集合的向量”而非“一个向量”为基本元素的问题，为此需要定义这些向量集合之间的距离。特别地，如果允许我们直接考虑每个向量集合张成的线性子空间，那么问题就变成了如何度量两个线性子空间之间的距离。

Grassmann Manifold

用数学语言描述，设 $a_1,\dots ,a_k\in {\mathbb{R}}^n$ 和 $b_1,\dots ,b_k\in {\mathbb{R}}^n$ 是两个线性无关向量组 ($1\le k\le n$)，分别张成 $k$ 维子空间： $$\mathcal{A}=\text{Span}\{a_1,\dots ,a_k\}\subset {\mathbb{R}}^n,\mathcal{B}=\text{Span}\{b_1,\dots ,b_k\}\subset {\mathbb{R}}^n$$ 我们希望寻求一个度量 $d(\mathcal{A},\mathcal{B})$ 来衡量子空间 $\mathcal{A}$ 和 $\mathcal{B}$​​​ 之间的距离。

从泛函分析的角度来讲，“距离”应该定义在一个集合上。因此，定义 Grassmann manifold 为 ${\mathbb{R}}^n$ 上所有 $k$ 维线性子空间构成的集合： $$\text{Gr}(k,n)=\{k\text{-dim linear subspaces of }{\mathbb{R}}^n\}$$ 那么 $\mathcal{A},\mathcal{B}\in \text{Gr}(k,n)$. 也就是说，从 Grassmann manifold 的角度，子空间 $\mathcal{A},\mathcal{B}$ 可以视为 $\text{Gr}(k,n)$ 上的两个点，$d(\mathcal{A},\mathcal{B})$ 是这两个点之间的距离。

Grassmann Discriminant Analysis: a Unifying View on Subspace-Based Learning. 符号与本文略有不同

Principle Angles

为了寻求 $d(\mathcal{A},\mathcal{B})$，我们从最简单的情形入手。当 $n=2,k=1$ 时，$\mathcal{A},\mathcal{B}$ 是二维平面上的过原点的直线，那么一个自然的想法是用直线间的夹角作为距离度量： $$d(\mathcal{A},\mathcal{B})=\theta ,\text{where }\cos \theta =a^{T}b(\Vert a\Vert =\Vert b\Vert =1)$$ 受到二维情形的启发，当 $n>2$​ 时，我们先在 $\mathcal{A},\mathcal{B}$ 中分别找一个方向，使得夹角尽可能小（点积尽可能大）： $$\begin{array}{rl}max& a^{T}b\\ \text{s.t.}& a\in \mathcal{A},b\in \mathcal{B}\\ & \Vert a\Vert =\Vert b\Vert =1\end{array}$$ 设最优解为 $a_1^{\ast },b_1^{\ast }$. 接下来再分别找一个方向，使得夹角尽可能小，但要求与前一个方向正交： $$\begin{array}{rl}max& a^{T}b\\ \text{s.t.}& a\in \mathcal{A},b\in \mathcal{B}\\ & \Vert a\Vert =1,a^T{a}_1^{\ast }=0\\ & \Vert b\Vert =1,b^T{b}_1^{\ast }=0\end{array}$$ 以此类推，我们不断地找与已知方向正交的、夹角最小的方向： $$\begin{array}{rl}max& a^{T}b\\ \text{s.t.}& a\in \mathcal{A},b\in \mathcal{B}\\ & \Vert a\Vert =1,a^T{a}_1^{\ast }=\cdots =a^T{a}_{j-1}^{\ast }=0\\ & \Vert b\Vert =1,b^T{b}_1^{\ast }=\cdots =b^T{b}_{j-1}^{\ast }=0\end{array}$$ 这样定义了 $k$ 个优化问题。设它们的最优解分别为 $a_1^{\ast },b_1^{\ast },\dots ,a_k^{\ast },b_k^{\ast }$，则每一对解之间的夹角余弦值为： $$\cos {\theta }_j={a_j^{\ast }}^T{b}_j^{\ast },j=1,\dots ,k$$ 称这些夹角 $\{{\theta }_1,\dots ,{\theta }_k\}$ 为 principle angles.

由于这 $k$ 个优化问题是顺序求解的，所以一定有 ${\theta }_1\le \cdots \le {\theta }_k$；又因为 $0\le {a_j^{\ast }}^T{b}_j^{\ast }\le 1$，所以 $0\le {\theta }_j\le \pi /2$.

Grassmann Distance

在 principle angles 的基础上，定义 Grassmann distance 为： $$d(\mathcal{A},\mathcal{B})={\left(\sum _{i=1}^k{\theta }_i^2\right)}^{1/2}$$

也即向量 $$ 的 2-范数。有文献指出 Grassmann distance 等价于 Grassmann manifold 上的测地距离。

事实上，除了 Grassmann distance，基于 principle angles 还可以定义很多距离：

Lek-Heng Lim. distances between objects of different dimensions. 符号与本文略有不同

Computation: SVD

至此，虽然我们用 $$ 个优化问题定义出了 principle angles，进而定义出了 Grassmann distance，但显然不能真的靠依次解优化问题来计算。事实上，principle angles 可以通过奇异值分解计算，下面进行推导。

不妨设 $$ 和 $$ 都是单位正交向量，不然可以通过 Gram-Schmidt 正交化过程做到。设 $$，$$，则 $$ 均是 orthonormal 矩阵。于是第一个优化问题可以改写作： $$ 根据正交性，$$ 不改变 $$ 的长度，所以 $$，$$ 同理，因此问题等价于： $$ 定义拉格朗日函数： $$ 求导令为零： $$ 这意味着 $$ 是 $$ 的左右奇异向量，$$ 是对应奇异值。进一步地，为了最大化优化目标 $$，应取 $$ 为最大奇异值。依据同样的道理，第二个优化问题的最优解就是次大奇异值和对应奇异向量……第 $$ 个优化问题的最优解就是第 $$ 大的奇异值和对应奇异向量。

综上，principle angles 可以按如下方式计算：

1. 首先对 $$ 做 SVD： $$ 其中 $$ 且 $$.

2. 计算 principle angles： $$

简便起见，这两步也可以用一个式子表示： $$

有了 principle angles，Grassmann distance 就好计算了： $$ 特别地，对于上一节最后表格中的 Chordal distance，有： $$ 由于奇异值的平方和等于矩阵 F-范数的平方，所以： $$ 因此使用 Chordal distance 时我们甚至用不着做 SVD，直接算 $$ 的 F-范数（所有元素的平方和）就够了，非常方便。

Extension: Different Dimensions

截至目前，我们假设 $$ 和 $$ 具有相同的维度 $$，但如果 $$ 维度不同（不妨设 $$ 比 $$ 维度更小）该怎么办呢？一个想法是：将 $$ “膨胀”后再与 $$ 比较，或者将 $$ “缩减”后再与 $$ 比较。

具体而言，设 $$ 是 $$ 中的 $$ 维子空间而 $$ 是 $$ 维子空间，其中 $$，即： $$ 定义 Schubert varieties 为： $$ 例如，一条直线的 $$ 可以是包含这条直线的所有平面；反过来，一个平面的 $$ 可以是该平面包含的所有直线。

于是 $$ 与 $$ 之间的距离可以定义为： $$ 类似的，$$ 与 $$ 之间的距离可以定义为： $$ 文献 (Ye-Lim, 2016) 证明： $$ 其中： $$ 因此即便 $$ 维度不同，也可以用与上一节相同的方法计算二者的距离。

值得说明的是，此时 $$ 其实并不满足距离的性质。例如，当 $$ 时，有 $$，不满足非负性，进而不满足三角不等式，但满足对称性。

参考资料

1. Hamm, Jihun, and Daniel D. Lee. Grassmann discriminant analysis: a unifying view on subspace-based learning. In Proceedings of the 25th international conference on Machine learning, pp. 376-383. 2008. ↩︎
2. Ye, Ke, and Lek-Heng Lim. Schubert varieties and distances between subspaces of different dimensions. SIAM Journal on Matrix Analysis and Applications 37, no. 3 (2016): 1176-1197. ↩︎
3. Jackson Van Dyke. Distances between subspaces. link ↩︎
4. Lek-Heng Lim. distances between objects of different dimensions. link ↩︎