開發者必讀：計算機科學中的線性代數

選自arXiv

作者：Petros Drineas、Michael W. Mahoney

機器之心編譯

參與：李澤南、劉曉坤、蔣思源

矩陣計算在計算機科學中佔有舉足輕重的地位，是每個開發者都需要掌握的數學知識。近日，來自普渡大學的 Petros Drineas 與 UC Berkeley 的 Michael Mahoney 提交了一篇概述論文《Lectures on Randomized Numerical Linear Algebra》可以作為線性代數知識的參考資料，本文將對其中的部分內容（主要為第二章：線性代數）進行簡單介紹。

論文鏈接：https://arxiv.org/pdf/1712.08880.pdf

簡介

矩陣在計算機科學、統計學和應用數學中佔有獨一無二的地位。一個 m×n 矩陣可以對 m 個對象（每個對象由 n 個特徵描述）在有限單元網格中的離散微分運算元信息進行描述；一個 n×n 正定矩陣可以編碼所有 n 對象配對之間的相關性，或者網路中所有 n 節點對之間的邊連通性等等。受科學和計算機技術發展的影響，近年來我們見證了矩陣演算法理論和實踐上令人興奮的發展。其中最值得注意的是隨機化的使用——通常假設由於生成機制的原因，輸入數據存在雜訊——它可以作為演算法或計算資源用於開發和提升基礎矩陣問題如矩陣乘法、最小二乘（LS）近似、低階矩陣近似等演算法。

隨機數值線性代數（RandNLA）是一個跨學科的研究領域，利用隨機化作為計算資源來開發用於大規模線性代數問題的提升演算法。從基礎的角度來看，RandNLA 源自理論計算機科學（TCS），並與數學有著很深的聯繫（凸面分析、概率論、度量嵌入理論），也與應用數學相關（科學計算、信號處理、數值線性代數）。從應用層面來看，RandNLA 是機器學習、統計和數據分析的重要新工具。很多精心設計的實現已經在大量問題上超越了高度優化的軟體庫，如最小二乘回歸，同時也具有相當的擴展性、平行計算和分布能力。此外，RandNLA 為現代大規模數據分析提供了良好的演算法和統計基礎。

這一章將作為對三種基本 RandNLA 演算法的獨立的入門介紹，分別是隨機矩陣乘法（randomized matrix multiplication）、隨機最小二乘解算器（randomized least-squares solvers），以及用一個隨機演算法計算矩陣的低秩近似。因此，這一章和很多應用數學的領域有非常強的聯繫，特別是它和這一卷的其它許多章節都有很強的聯繫。最重要的是，其中分別包含了 G. Martinsson 的工作，他利用這些方法開發了改進的低秩矩陣近似解算器 [2]；R. Vershynin 的工作，他開發了概率論工具用於分析 RandNLA 演算法 [3]； J. Duchi 的工作，他以互補的方式利用隨機方法求解更通用的優化問題 [4]；以及 M. Maggioni 的工作，他以這些方法作為更複雜的多尺度方法的基礎模塊 [5]。

本論文將在第二節中概述基本的線性代數知識；在第三節概述離散概率的基本知識；在第四節介紹矩陣乘法的隨機演算法；在第五節介紹最小二乘回歸問題的隨機演算法；在第六節介紹低秩近似的隨機演算法。最後我們還介紹了兩個其它關於 RandNLA 的導論資源 [6,7]，供感興趣的讀者參考。

2 線性代數

在這一節，我們將簡要概述基本的線性代數屬性和在這一章中將用到的數學符號。我們假定讀者具備線性代數的基礎（例如，向量的內積和叉積，基本矩陣運算如加法、標量乘法、轉置、上/下三角矩陣，矩陣-向量乘法，矩陣乘法，矩陣的跡等）。

2.1 基礎

我們將完全聚焦於線性空間中的矩陣和向量。我們使用符號 x ∈ R^n 表示 n 維向量，注意向量都是以粗體小寫字母書寫。這裡假定所有的向量都是列向量，除非特別說明。所有元素為零的向量用 0 表示，所有元素為 1 的向量用 1 表示（類似 Broadcasting）；維度會隱含在上下文中或顯式地用下標表示。

我們將使用粗體大寫字母表示矩陣，例如 A ∈ R^mxn 表示一個 mxn 階的矩陣；用 A_i* 表示 A 的第 i 行的行向量，用 A_*i 表示 A 的第 i 列的列向量。單位矩陣表示為 I_n，其中 n 是矩陣的行數和列數。最後，我們用 e_i 表示 I_n 的第 i 列，即第 i 個規範基。

逆矩陣：如果存在一個逆矩陣 A^-1 ∈ R^mxn 滿足以下條件，那麼矩陣 A ∈ R^mxn 被稱為非奇異的或可逆的：

如果 A 的所有列向量（或行向量）線性無關，那麼 A 是可逆的。換句話說，不存在一個非零向量 x ∈ R^n 使得 Ax=0。可逆矩陣的標準性質有： (A^?1 )^? = (A^?)^?1 = A^??（A 逆的轉置等於 A 轉置的逆）和 (AB)^?1 = B^?1* A^?1（A 左乘 B 的逆等於 B 逆左乘 A 逆。註：微信表達式展示不便，準確表達式請查看原材料）。

正交矩陣：如果矩陣 A ∈ R^n×n 滿足 A^?=A^?1，則稱 A 為正交矩陣。等價地說，對所有 i , j 屬於 [1,n]，正交矩陣滿足：

對於 A 的行向量，上述性質同樣滿足。即 A 的所有列（或行）向量都是兩兩正交或互成法向量。

QR 分解：任意的矩陣 A ∈ R^n×n 都可以分解成一個正交矩陣和一個上三角矩陣的乘積：A=QR

其中 Q ∈ R^n×n 是正交矩陣，R ∈ R^n×n 是上三角矩陣。QR 分解在求解線性方程組的時候很有用，它的計算複雜度為 O(n^3)，並且是數值穩定的。為了用 QR 分解求解線性方程組 Ax=b，我們首先對等式兩邊同時左乘一個 Q^?，即 Q^?QRx = Rx = Q^?b。然後，我們用反向代入求解 Rx = Q^?b。

2.2 範數

範數（Norms）被用於度量矩陣的大小，或者相應地，度量向量的長度。範數是一個函數，它將 R^mxn（或 R^n）映射到 R。形式地說：

定義 1：任何函數滿足 || · ||: R^m×n → R 和下列性質，則稱為一個範數：

• 非負性：|| A ||≥0；|| A ||=0 當且僅當 A=0；
• 三角不等律：|| A+B ||≤|| A ||+|| B ||；
• 標量乘法律：|| αA ||=|α| || A ||，α∈R。

可以很容易地證明以下兩個性質：

• || A ||=|| -A ||
• | || A ||-|| B || | ≤ || A-B ||

第二個性質被稱為倒三角型不等式。

2.3 向量範數

若給定 n 維向量 x 和一個整數 p > 1，我們可以定義向量 p-範數為：

最常見的向量 p-範數為：

• 1-範數：

• 歐幾里德（2）範數：

• 無窮（最大）範數：

若給定 n 維向量 x、y，我們可以使用 p-範數作為內積的上確界，即 Cauchy-Schwartz 不等式可以寫為：

一般來說，該不等式給定了兩個向量的歐幾里德範數可以作為它們內積的上確界，Holder 不等式表明：

以下向量 p-範數的不等式性質可以輕易的證明：

2.4 歸納矩陣範數

給定一個 m×n 階矩陣 A，和一個 p > 1 整數，我們定義矩陣的 p-範數為：

一般我們最常用的矩陣 p-範數為：

• 1-範數，取矩陣列加和絕對值的最大值：

• 無窮範數，取矩陣行加和絕對值的最大值：

• 2-範數，

這一系列的範數被稱為「歸納（induced）」，因為它們是通過不取決於 A 和 p 的非零向量 x 而實現的。因此，一般存在一個單位範數向量（p-範數中的單位範數）x 令||A||p = ||Ax||p。歸納矩陣 p-範數遵循以下 submultiplicativity 法則：

此外，矩陣 p-範數對於矩陣的初等變換是不變的，即||PAQ||p = ||A||p，其中 P 和 Q 為對應維度的初等變換矩陣。同樣，如果我們考慮矩陣分割：

那麼子矩陣的範數就和全部矩陣的範數相關：即||B||p <= ||A||p。矩陣 p-範數間的以下關係可以相對簡單地證明。若給定一個 m×n 階矩陣，

此外，||A^T||1 = ||A||∞，||A^T||∞ = ||A||1。其中轉置影響了矩陣的無窮範數和 1-範數，而不影響 2-範數，即||A^T||2 = ||A||2。同樣，矩陣 2-範數並不會受到矩陣 pre(post)- multiplication 操作的影響，其中它的列（或行）為正交向量：||UAV^T||2 = ||A||2，其中 U 和 V 為對應維度的正交矩陣（U^T*U = I and V^T*V = I）。

2.6 奇異值分解

我們知道方陣可以分解為特徵值與特徵向量，但非方陣的矩陣並沒不能實現特徵值分解。因此奇異值分解（SVD）是每個矩陣中最重要的矩陣分解方式，因為不是所有的矩陣都能進行特徵分解，但是所有的矩陣都能進行奇異值分解。

定義 6. 給定一個矩陣 A ∈ R^m×n，我們定義全 SVD 為：

其中 U ∈ R^m×m 和 V ∈ R^n×n 分別是包含 A 的左、右奇異向量的正交矩陣，Σ ∈ R^m×n 是對角矩陣，其中 A 的奇異值在主對角線上遞減。

我們經常使用 u_i（或 v_j），i=1,..., m（或 j=1,..., n）來表示矩陣 U（或 V）的列。同樣，我們將使用σ_i，i = 1,..., min{m, n} 來表示奇異值：

A 的奇異值是非負的，其數目等於 min{m, n}。A 的非零奇異值個數等於 A 的秩。由於正交不變性，我們得到：

其中 P 和 Q 是對應維度上的正交矩陣（P^TP = I 且 Q^TQ = I）。或者說，PAQ 的奇異值與 A 的奇異值相同。

涉及矩陣 A 和 B 的奇異值的以下不等式是非常重要的。首先，如果 A 和 B 都在 R^m×n 上，對於所有 i = 1, ... , min{m, n}，

第二，如果 A ∈ R^p×m 和 B ∈ R^m×n，對於所有 i = 1, ... , min{m, n}，

其中σ_1(A) = ||A||_2。我們經常對於僅保持非零奇異值和相應的（矩陣 A 的）左、右奇異向量感興趣。給定矩陣 A ∈ R^m×n 和 rank(A)=ρ，我們可以定義它的稀疏 SVD。

定義 9. 給定矩陣 A ∈ R^m×n，秩為ρ ≤ min{m, n}，我們定義稀疏 SVD 為：

其中 U ∈ R^m×ρ和 V ∈ R^n×ρ是包含對應於非零奇異值的左、右奇異向量的兩兩正交列（即 U^TU = I 且 V^TV = I）的矩陣；Σ ∈ R^ρ×ρ是 A 的非零奇異值在對角線上遞減的對角矩陣。

如果 A 是非奇異矩陣，我們可以使用 SVD 計算它的逆：

（如果 A 是非奇異的，那麼它是方形和滿秩的，在這種情況下，稀疏 SVD 和全 SVD 是一樣的）眾所周知，SVD 非常重要，任何矩陣的最佳 k 秩近似都可以通過 SVD 來計算。

定理 10. 讓 A = UΣV^? ∈ R^m×n 作為 A 的稀疏 SVD；設 k < rank(A) = ρ為整數，讓

隨後，

換句話說，上述定理指出，如果我們尋找一個矩陣 A 的 k 秩近似，使得「誤差」矩陣的 2-範數或 Frobenius 範數最小化（即 A 和它的近似之間的差異最小化），隨後我們需要保留 A 的最前 k 個奇異值和相應的左、右奇異向量。

我們會經常使用這些符號：讓 U_k ∈ R^m×k（或 V_k ∈ R^n×k）表示矩陣 A 的最前 k 個左（或右）奇異向量的矩陣；讓 Σ_k ∈ R^k×k 表示包含 A 的最前 k 個奇異值的對角矩陣。同樣的，讓 U_k,⊥ ∈ R^m×(ρ?k)（或 V_k,⊥ ∈ R^n×(ρ?k)）表示 A 的底部ρ-k 個非零左（或右）奇異向量的矩陣；然後令Σ_k,⊥ ∈ R^(ρ?k)×(ρ?k) 表示包含 A 的底部ρ-k 個奇異值的對角矩陣。然後，

2.9 Moore-Penrose 偽逆

對於非方矩陣而言，其逆矩陣是沒有定義的。而一種非常出名的推廣型矩陣求逆方法 Moore-Penrose 偽逆在這類問題上取得了一定的進展。形式上來說，若給定 m×n 階矩陣 A，那麼如果矩陣 A? 滿足以下屬性，它就是矩陣 A 的 Moore-Penrose 偽逆：

給定一個秩為ρ的 m×n 階矩陣 A，它的稀疏奇異值分解可以表示為：

它的 Moore-Penrose 偽逆 A? 的稀疏奇異值分解可以表示為：

如果 A 為 n×n 階滿秩矩陣，那麼 A? 就等於矩陣 A 的逆。如果 A 為 m×n 階列滿秩矩陣，那麼 A?A 就等於 n 階單位矩陣，AA?為矩陣 A 列上的投影矩陣。如果 A 為滿行秩矩陣，那麼 AA?就為 m 階單位矩陣，A?A 為矩陣 A 行上的投影矩陣。

關於兩個矩陣乘積的偽逆，有如下特別重要的屬性：對於 m×p 階矩陣 Y1 和 p×n 階矩陣 Y2，且滿足 Rank(Y1)=Rank(Y2)，即秩相等，[9, Theorem 2.2.3] 表明：

（我們強調秩相等的條件是非常重要的：因為兩個矩陣相乘的逆總是等價於矩陣逆的相乘，但這個推斷對於一般的 Moore-Penrose 偽逆 [9] 是不滿足的）此外，Moore-Penrose 偽逆的基空間和所有實際的矩陣都有聯繫。給定一個矩陣 A 和 A 的 Moore-Penrose 偽逆 A?，A?的列空間可以定義為：

A?的列空間和零空間（null space）正交，A?的零空間可以定義為：