矩阵奇异值的随机抽样方法
科技资讯2008N O . 13
SC I ENC E &TEC HN OLO GY I NFO RM ATI O N 学术论坛
矩阵奇异值的随机抽样方法
廖文彬孙逊
(仰恩大学数学系概率教研室福建泉州362014)
摘要:矩阵的奇异值由于其本身具备的一些良好性质, 在许多领域得到了广泛的应用。但有很多时候, 传统的矩阵奇异值求解方法很难得到良好的结果。本文考虑采用一种抽样估计方法估计大矩阵的奇异值。关键词:矩阵奇异值随机抽样
中图分类号:O151. 21文献标识码:A 文章编号:1672-3791(2008) 04(c) -0249-02
矩阵奇异值本身具备许多良好的特性, 在
学术界, 矩阵的奇异值理论已经被应用于许多
不同领域。矩阵的奇异值分解理论在实际应用以上矩阵的第一个奇异值可用于降低计
领域的关键往往是矩阵奇异值的求解问题, 对算机对存储器的要求; 第三个特征常用于图象
于阶数较小矩阵的奇异值分解问题, 传统的奇的旋转、镜像、平移等; 第五个特征可用于
异值分解方法一般都能获得良好的结果。但是信号除噪; 此外可通过控制矩阵的奇异值大小
对于规模庞大的矩阵, 传统的分解方法在计算来控制两个矩阵空间的距离。
误差、计算精度、分解效率等方面都很难达到
要求。我们考虑使用一种基于随机抽样理论的2基于随机抽样的奇异值求解
奇异值估计方法计算大矩阵的奇异值, 以求获现在矩阵奇异值的那些优良特性都已经
取更高的分解效率, 更好的计算精度。摆在我们面前, 可以预期的应用也可以估计,
那么在实践中我们应该怎样去利用矩阵奇异
1矩阵奇异值的特征及应用值的这些优良特性能呢? 这里的关键当然是先
(1) 矩阵奇异值的第一个特征是可以降维。要求出矩阵的那些具有代表性的奇异值(通常
(2) 奇异值分解的第二个特征是奇异值对这些具有代表性的奇异值指的就是矩阵的那
矩阵的扰动不敏感。些大的奇异值) 。对于维数较低的矩阵而言, 传
(3) 矩阵奇异值的第三个特征是比例不变统的矩阵奇异值分解方法通常能得到比较良
性, 即a A 的奇异值是A 奇异值的a 倍。好的结果, 但是试想一下, 如果摆在我们面前
(4) 奇异值的第四个特征是旋转不变性。的矩阵是一个一万阶的矩阵结果会怎样？答
即若P 是正交阵PA 的奇异值与A 的奇异值相案是显然的, 传统的矩阵奇异值分解方法在高
同。维矩阵的奇异值分解问题上, 很难得到让人满
(5) 奇异值的第五个特征是容易得到矩阵意的值。
A 的秩为的一个最佳逼近矩阵。我们考虑是不是能把待分解的矩阵做降
(6) 奇异值分解的第六个特征:若A 、B 都维处理？设A 是一个M ×N 的大矩阵, 由于
有相同的奇异向量,
则矩阵A 的尺寸足够大, 我们很难计算他的奇异值。我们考虑用下面的方法去估计这个大
矩阵的奇异值
我们考虑从矩阵A 中随机抽取P (P
行构造一尺寸较小的矩阵A (1) , 使用传统的标
准方法计算A (1) 的奇异值, 重复这个步骤50
次(也可以是满足能够允许统计分析的任意
次) , 也就是说, 通过从矩阵A 随机取样(随机
选取不同的行) 的方法, 构造矩阵序列A (i ) ,
i =1,2, . . . , 50, 计算其最大的奇异值, 第二大的奇异值, 第三大的奇异值……依次
下去, 直到计算出所有需要的奇异值。接着
我们开始估计矩阵A 的第k 个奇异值, 这
图
1时, 我们要做的就是绘制的曲线图。首
表
1
236科技资讯S C I E N CE &T ECH NOLOGY I NFORM A TI O N 先, 计算的平均值(P 表示随机取样时选择的行数) ; 接着改变P 的取值; 然后将上面的步骤重复进行下去; 最后绘制出P 跟之间的曲线关系。最终我们将得到一条平滑的曲线, 此时, 利用这条曲线我们可以通过外推法估计出当P ＝M 时矩阵A 的奇异值s i 。通常这里的外推法可以通过拟合方式实现, 也可以借助工具软件(如神经网络等) 方式实现。图(1) 描述了抽样估计算法的执行过程3实例验证简单起见, 我们选择一个规模较小的矩阵来验证上面的抽样估计方法, 设矩阵如图1。下面给出了采用抽样方法与传统方法所得矩阵D 奇异值的对照表(如表1所示) 。比较矩阵D 的真是奇异值跟估计奇异值可看出, 估计奇异值较矩阵D 的真实奇异值有一定的误差, 但这通常并不影响实际的应用效果, 所以我们认为通过抽样估计方法计算出的矩阵奇异值基本上能达到实际应用(如数字图象压缩) 的效果, 且能较好的解决大矩阵奇异值的难计算问题。参考文献[1]张贤达. 矩阵分析与应用[M ].清华大学出版社, 2004年9月. [2]赵犁丰, 姚玉玲. SV D 方法在信号重构中的应用[M ]. 青岛海洋大学学报, 1999. [3]王文胜等. 图像特征抽取的奇异值分解方法[J].计算机工程, 2006年4月. [4]V an L oan C F. G ener al i zi ng t he si ngu-l ar val ue dec om posi t i on[M ].SI A M J Num be r Anal , 1976. [5]+++ZhangX D(张贤达) , Z hang Y S. Si ngul ar val ue decom posi t i on-bases M A or der det e r m i na t i on of na n-G aussi an ARM A m odel s. I EEE Tr a ns Si gna l Pr ocess i ng[M ]. 1993. [6]M . K O BA Y ASHI 等, E st i m at i on Of Si n-gul ar V al ue s of V er y L ar ge M at r i ces Usi ng R andom Sam pl i ng[M ].Com put er a nd M a t he m at i cs w i t h A ppl i c at i ons, 2001. [7]魏洪增. 矩阵理论与方法[M ].电子工业出版社, 2006年1月. [8]裴鹿成. 计算机随机模拟[M ].湖南科学技术出版社, 1989年12月. [9]郭文彬. 奇异值分解中非奇异矩阵的性质结构[M ].聊城大学学报, 2005年3月. [10]王文胜. 一种基于奇异值分解的特征抽取方法[J ]. 电子与信息学报, 2005年2月.