本文是對?Joel A. Tropp 教授所寫的?Randomized Numerical Linear Algebra: Foundations & Algorithms 中第 11 章 the?randomized?rangefinder 的閱讀筆記.? 這一章給出了隨機秩揭方法的理論分析，其中的部分結(jié)論十分有趣且富有啟發(fā)性，故作此筆記.?

首先給出秩揭問題的定義. 設(shè)??是輸入矩陣，是子空間維數(shù). 找出一個列正交陣 ，使得 ?恰好對應(yīng)于??的前? 個左奇異向量. 對于我們求出的?，用??來度量結(jié)果的準(zhǔn)確度，這里所用的范數(shù)為譜范數(shù)（也就是 2-范數(shù)）.? 由 Eckhart-Young 定理，不難得到該最小值應(yīng)為 .?

解決這個問題的一種方法是用測試矩陣??右乘 ，得到 ，對? 做 QR 分解得到? 的正交基?，將? 作為我們要求的正交陣. 接下來我們將探究該方法在理論上的可靠性.?

首先引入一些記號. 設(shè) 表示測試矩陣，即 . 設(shè)??表示到 ?張成的子空間上的正交投影，即?. 用? 表示對稱（半）正定陣? 關(guān)于??的 Schur 補，即

表示廣義逆. 定義?.?

據(jù)上述定義，有如下關(guān)系成立

.

證明??注意到?. 將? 記為?，則

.

由定義可知結(jié)論成立.

接著，我們給出一個引理. 首先仍要定義一些記號.?設(shè)??是有限維歐式空間，?是??的一個子空間且?. 則半正定陣? 可表示為

,

其中??和? 分別是? 和??上的線性算子， 和? 分別是從? 到? 和從? 到? 的線性算子. 定義?

.

用? 表示兩向量的標(biāo)準(zhǔn)內(nèi)積，用? 表示由? 定義的準(zhǔn)內(nèi)積 (因為 不一定正定，因此只能要求是準(zhǔn)內(nèi)積). 則有

引理1? 對任意半正定陣 和子空間 ，

.

下面給出一個重要推論.?

推論1?設(shè)?，這里 表示??半正定. 則對任一測試矩陣 ，有

證明? ?記 ?及 .?則? 和? 半正定. 構(gòu)造?

及?,

易驗證? 和? 都是半正定的，且?. ?取? 為算子??(或 ) 對應(yīng)的子空間，則對任意的???及? ，有

.

由引理1 可知對任意?，都有

.

據(jù)? 的定義可知結(jié)論成立.?