随机秩揭方法的理论分析（一）

本文是对 Joel A. Tropp 教授所写的 Randomized Numerical Linear Algebra: Foundations & Algorithms 中第 11 章 the randomized rangefinder 的阅读笔记.  这一章给出了随机秩揭方法的理论分析，其中的部分结论十分有趣且富有启发性，故作此笔记. 

首先给出秩揭问题的定义. 设  是输入矩阵，是子空间维数. 找出一个列正交阵 ，使得  恰好对应于  的前  个左奇异向量. 对于我们求出的 ，用  来度量结果的准确度，这里所用的范数为谱范数（也就是 2-范数）.  由 Eckhart-Young 定理，不难得到该最小值应为 . 

解决这个问题的一种方法是用测试矩阵  右乘 ，得到 ，对  做 QR 分解得到  的正交基 ，将  作为我们要求的正交阵. 接下来我们将探究该方法在理论上的可靠性. 

首先引入一些记号. 设 表示测试矩阵，即 . 设  表示到  张成的子空间上的正交投影，即 . 用  表示对称（半）正定阵  关于  的 Schur 补，即

表示广义逆. 定义 . 

据上述定义，有如下关系成立

.

证明  注意到 . 将  记为 ，则

.

由定义可知结论成立.

接着，我们给出一个引理. 首先仍要定义一些记号. 设  是有限维欧式空间， 是  的一个子空间且 . 则半正定阵  可表示为

,

其中  和  分别是  和  上的线性算子， 和  分别是从  到  和从  到  的线性算子. 定义 

.

用  表示两向量的标准内积，用  表示由  定义的准内积 (因为 不一定正定，因此只能要求是准内积). 则有

引理1  对任意半正定阵 和子空间 ，

.

下面给出一个重要推论. 

推论1 设 ，这里 表示  半正定. 则对任一测试矩阵 ，有

证明   记  及 . 则  和  半正定. 构造 

及 ,

易验证  和  都是半正定的，且 .  取  为算子  (或 ) 对应的子空间，则对任意的   及  ，有

.

由引理1 可知对任意 ，都有

.

据  的定义可知结论成立.