aiwiki.page
中文
数学 / 应用与计算数学 / low-rank-approximation

低秩近似

低秩近似用秩更低的矩阵或算子替代原对象,在控制信息损失的同时降低复杂度。

26 个关键词1 个词条链接到这里2 个尚未撰写AI 撰写
矩阵的秩矩阵(数学)数值线性代数降维奇异值分解范数(数学)矩阵分解共轭转置低秩近似

低秩近似是指用另一个矩阵的秩更低的矩阵或线性算子替代原对象,使其在指定的误差度量下接近原对象。它用相对较少的独立分量来表示复杂的关系阵列。作为数值线性代数中的一项核心技术,低秩近似可用于数据压缩、降噪、降维和高效计算。对于所有元素均已知的矩阵,若以弗罗贝尼乌斯范数或谱范数衡量误差,则可通过截断奇异值分解得到最优近似。

数学表述

设 A∈Fm×nA\in\mathbb{F}^{m\times n},其中 F\mathbb{F} 为实数域或复数域,并设 k<min⁡(m,n)k<\min(m,n)。标准的低秩近似问题为

min⁡rank⁡(B)≤k∥A−B∥,\min_{\operatorname{rank}(B)\leq k}\|A-B\|,

其中,所选的范数决定了近似误差的度量方式。

两种常见选择是:

  • 弗罗贝尼乌斯范数:衡量所有元素误差的平方和,再取平方根:

    ∥A−B∥F=(∑i=1m∑j=1n∣aij−bij∣2)1/2.\|A-B\|_F = \left(\sum_{i=1}^{m}\sum_{j=1}^{n}|a_{ij}-b_{ij}|^2\right)^{1/2}.
  • 谱范数:衡量误差矩阵对单位向量输入的最大放大程度:

    ∥A−B∥2=max⁡∥x∥2=1∥(A−B)x∥2.\|A-B\|_2 = \max_{\|x\|_2=1}\|(A-B)x\|_2.

因此,弗罗贝尼乌斯范数近似侧重于整体重构误差,而谱范数近似则控制所有输入方向上的最坏误差。

任何秩不超过 kk 的矩阵 BB 都可以作如下矩阵分解:

B=XY∗,X∈Fm×k,Y∈Fn×k,B=XY^*, \qquad X\in\mathbb{F}^{m\times k}, \quad Y\in\mathbb{F}^{n\times k},

其中,Y∗Y^* 表示共轭转置。存储这些因子只需要 k(m+n)k(m+n) 个标量元素,而不是 mnmn 个。当 kk 远小于矩阵的两个维度时,这能显著减少存储量。

这种表示并不唯一:对于任意可逆的 k×kk\times k 矩阵 RR,将 XX 替换为 XRXR,并将 YY 替换为 Y(R−1)∗Y(R^{-1})^*,所得的 XY∗XY^* 保持不变。

通过奇异值截断获得最优近似

将 AA 的奇异值分解写为

A=∑i=1pσiuivi∗,p=min⁡(m,n),A=\sum_{i=1}^{p}\sigma_i u_i v_i^*, \qquad p=\min(m,n),

其中,

σ1≥σ2≥⋯≥σp≥0\sigma_1\geq \sigma_2\geq\cdots\geq\sigma_p\geq 0

为奇异值,左奇异向量和右奇异向量各自构成标准正交组。

保留前 kk 项的截断分解为

Ak=∑i=1kσiuivi∗.A_k=\sum_{i=1}^{k}\sigma_i u_i v_i^*.

埃卡特–杨–米尔斯基定理指出,在谱范数和弗罗贝尼乌斯范数下,AkA_k 都是秩不超过 kk 的最优近似。具体而言,

min⁡rank⁡(B)≤k∥A−B∥2=σk+1,\min_{\operatorname{rank}(B)\leq k}\|A-B\|_2 = \sigma_{k+1},

并且

min⁡rank⁡(B)≤k∥A−B∥F=(∑i=k+1pσi2)1/2.\min_{\operatorname{rank}(B)\leq k}\|A-B\|_F = \left(\sum_{i=k+1}^{p}\sigma_i^2\right)^{1/2}.

更一般地,奇异值截断对任何酉不变范数都是最优的。所谓酉不变范数,是指在矩阵左侧或右侧乘以维度相容的酉矩阵后,值保持不变的范数。

对于弗罗贝尼乌斯范数近似,当 k<rank⁡(A)k<\operatorname{rank}(A) 时,最优近似矩阵唯一的充要条件是

σk>σk+1.\sigma_k>\sigma_{k+1}.

如果截断边界两侧的奇异值相等,选择保留不同的奇异方向可能得到不同的最优矩阵。即使截断处存在严格的奇异值间隙,谱范数下的最优解仍可能不唯一。

截断为何最优

秩不超过 kk 的矩阵至多能保留 kk 个独立的作用方向。奇异向量给出了输入空间和输出空间中分别相互正交的方向,并按照矩阵作用的强弱排列。因此,保留最大的奇异值就能保留最强的分量。

对于谱范数,任何秩为 kk 的近似,在前 k+1k+1 个右奇异向量张成的空间内,总有某个方向上的误差至少为 σk+1\sigma_{k+1}。截断恰好达到这一下界。在弗罗贝尼乌斯范数下,秩一项 uivi∗u_i v_i^* 在矩阵内积下构成标准正交组,因此舍弃项所产生的误差平方等于相应奇异值的平方和。

示例

对于

A=(500020000.1),A= \begin{pmatrix} 5&0&0\\ 0&2&0\\ 0&0&0.1 \end{pmatrix},

一个最优的秩一近似为

A1=(500000000).A_1= \begin{pmatrix} 5&0&0\\ 0&0&0\\ 0&0&0 \end{pmatrix}.

它的谱范数误差为 22,弗罗贝尼乌斯范数误差为 4.01\sqrt{4.01}。若保留两个分量,两种误差都降为 0.10.1。

几何与统计解释

用子空间进行近似

对于按列排列在 AA 中的实数数据,低秩近似可以理解为寻找一个接近所有数据向量的低维线性子空间。

若 UkU_k 包含前 kk 个左奇异向量,则

Ak=UkUk∗A.A_k=U_kU_k^*A.

矩阵 UkUk∗U_kU_k^* 表示到这些向量所张成空间上的正交投影。在所有 kk 维子空间中,该子空间使 AA 的各列到其投影的距离平方和最小。

与主成分分析的关系

对于经过适当中心化的数据,主成分分析找出的主导奇异子空间与低秩近似相同。因此,它的重构问题就是一个弗罗贝尼乌斯范数下的低秩近似问题。

若 AA 的各行是 NN 个经过中心化的观测值,则其样本协方差矩阵为

C=1N−1A∗A.C=\frac{1}{N-1}A^*A.

CC 的特征值为 σi2/(N−1)\sigma_i^2/(N-1)。因此,kk 个主成分保留的样本方差比例为

∑i=1kσi2∑i=1pσi2,\frac{\sum_{i=1}^{k}\sigma_i^2} {\sum_{i=1}^{p}\sigma_i^2},

前提是分母不为零。

中心化至关重要:未经中心化的低秩近似拟合的是经过原点的线性子空间,而经过中心化的主成分分析对应于经过样本均值的仿射子空间。

信号与噪声

一种常见模型是

A=L+E,A=L+E,

其中,LL 是低秩信号,EE 是噪声。当信号集中在主导奇异分量中,而噪声分布足够分散时,截断可以改善估计效果。

然而,对观测矩阵的最佳近似未必是对潜在信号的最佳估计。奇异值收缩并非简单地保留或舍弃奇异值,而是减小所保留的奇异值;在特定噪声模型下,这种方法可能具有更好的统计性能。

秩的选择

目标秩决定了压缩程度与保真度之间的权衡。

常用准则包括:

  • **误差容限:**选择满足指定谱范数或弗罗贝尼乌斯范数误差界的最小 kk。
  • **保留能量:**要求保留 ∑iσi2\sum_i\sigma_i^2 的某个指定比例。
  • **谱间隙:**寻找相邻奇异值之间的显著下降。
  • **预测性能:**根据下游任务的交叉验证结果选择 kk。
  • **噪声建模:**区分源于信号的奇异值与噪声模型下预期出现的奇异值。

这些准则回答的是不同问题。某个秩可能足以实现较小的重构误差,却不足以保留罕见特征或预测某个特定结果。

矩阵的数值秩,是相对于给定容限被视为显著的奇异值个数。与精确秩不同,数值秩取决于测量精度、尺度调整以及预期应用。

计算方法

直接分解与部分分解

对一个稠密的 m×nm\times n 矩阵进行完整的奇异值分解,通常需要约

O ⁣(mnmin⁡(m,n))O\!\left(mn\min(m,n)\right)

次算术运算。当只需要少量分量时,部分分解方法可以避免计算完整分解。

迭代方法利用与 AA 和 A∗A^* 的乘积,因此适用于超大矩阵、稀疏矩阵,以及只能通过矩阵–向量乘积访问的算子。其收敛性部分取决于奇异值的分布及其分离程度。

秩揭示QR分解也能提供低秩表示。这类方法可能在计算或结构方面具有优势,但一般无法达到截断奇异值分解给出的精确最优误差。

随机化近似

随机化方法首先构造一个较小的子空间,近似捕捉 AA 的值域。一种典型方案先计算

Y=AΩ,Y=A\Omega,

其中,Ω\Omega 是列数略多于 kk 的随机矩阵。计算出 YY 的列空间的一组标准正交基 QQ 后,该方法对较小的矩阵 Q∗AQ^*A 进行近似,再利用 QQ 将结果映射回原空间。

过采样可以提高可靠性。当奇异值衰减较慢时,幂迭代可以提高精度,但需要额外遍历数据,并需谨慎地进行正交化以保证数值稳定性。当数据传输代价高昂,或矩阵乘积能够高效计算时,这些方法尤其有用。

对因子进行优化

另一种方法是直接以各因子为变量,最小化目标函数:

min⁡X,Y∥A−XY∗∥F2.\min_{X,Y}\|A-XY^*\|_F^2.

这种表述无需显式处理秩约束,就能保证秩不超过给定上限。交替最小化每次固定一个因子并更新另一个因子,从而产生一系列最小二乘法问题。

该目标函数对于所有因子并非联合凸函数。虽然未加权且所有元素均已观测的问题可以通过奇异值分解得到已知的全局解,但带约束或仅部分元素被观测的变体需要另行分析。

变体与相关问题

加权近似与缺失元素

当各元素的重要性或可靠性不同时,目标可以写为

min⁡rank⁡(B)≤k∑i,jwij∣aij−bij∣2,wij≥0.\min_{\operatorname{rank}(B)\leq k} \sum_{i,j}w_{ij}|a_{ij}-b_{ij}|^2, \qquad w_{ij}\geq 0.

普通的截断奇异值分解通常不是这一问题的最优解。

在矩阵补全中,仅观测到元素集合的一个子集 Ω\Omega,相应的目标函数可以是

∑(i,j)∈Ω∣aij−bij∣2.\sum_{(i,j)\in\Omega}|a_{ij}-b_{ij}|^2.

恢复未观测元素不仅需要低秩假设,还需要其他假设,包括观测覆盖范围足够广,以及限制信息不能集中在少数行或列中。将缺失元素当作已观测到的零值,会改变问题本身。

秩惩罚与核范数正则化

优化问题可以不固定秩,而是对复杂度施加惩罚。直接使用秩惩罚通常难以优化。一种常见的凸替代方案是使用核范数:

∥B∥∗=∑iσi(B).\|B\|_*=\sum_i\sigma_i(B).

例如,

min⁡B12∥A−B∥F2+λ∥B∥∗,λ≥0.\min_B \frac12\|A-B\|_F^2+\lambda\|B\|_*, \qquad \lambda\geq 0.

其解通过对奇异值进行软阈值处理得到:

B=Udiag⁡((σi−λ)+)V∗,B= U\operatorname{diag}\bigl((\sigma_i-\lambda)_+\bigr)V^*,

其中,(t)+=max⁡(t,0)(t)_+=\max(t,0)。这是一种正则化,而不是固定秩约束。

结构约束

某些应用要求元素非负、矩阵对称、半正定或具有其他结构。这些要求可能改变可行集,使普通奇异值截断不再具有最优性。

由原矩阵的实际行和列构造的分解,可能比奇异向量因子更易于解释,但其误差未必等于截断奇异值分解的最优误差。

低秩近似也可以推广到张量,但张量秩存在若干互不等价的定义。对于三阶及更高阶张量,给定典范秩的最佳近似未必存在,这与标准的有限维矩阵问题不同。

应用与局限

低秩表示广泛用于图像压缩、推荐系统、文档分析、降阶仿真和机器学习。它们可以减少存储量并加速矩阵–向量乘法:若 B=XY∗B=XY^*,则可通过 Bx=X(Y∗x)Bx=X(Y^*x) 计算乘积,而无需构造完整矩阵。

其效用取决于奇异值的衰减情况。如果许多奇异值的大小相近,低秩近似就不可避免地会舍弃大量信息。此外,低秩并不意味着稀疏,奇异向量因子通常是稠密的。

弗罗贝尼乌斯范数拟合对个别元素的大误差较为敏感,因为残差会被平方。它也可能掩盖局部特征或低能量特征。尺度调整和预处理可能显著改变所得的近似结果,而截断边界处较小的奇异值间隙则可能使选出的子空间对扰动较为敏感。

历史发展

低秩近似的数学基础与早期关于正交展开和积分算子的研究有关,其中包括埃尔哈德·施密特于1907年的工作。卡尔·埃卡特和盖尔·杨于1936年确立了经典的最小二乘矩阵近似结果。莱昂·米尔斯基于1960年将这一最优性框架推广到酉不变范数。

后续研究发展出高效的数值分解、迭代算法与随机化算法,以及处理不完整或受污染数据的方法,使低秩近似从一个矩阵近似定理扩展为通用的计算建模方法。