這份 note 是根據『 Sketching as a Tool for Numerical Linear Algebra — David P. Woodruff 』的講義，以及我們在 2018, fall 的讀書會內容做的簡短整理。

文中的定義都會根據我們在白板上的討論另外改寫，所以不一定會長得跟書本裡一模一樣，不過概念是一致的。

Chapter 2

Section 2.1

Definition 2.1 : A metric $S$ is a $(1\pm \epsilon) \ell_2$ -subspace embedding for the column space of an $n\times d$ matrix $A$ if

$\forall x\in \mathbb{R}^d, \quad \|SAx\|_2^2=(1\pm \epsilon)\|Ax\|_2^2 -- (1)$

作者書中的 $a=(1\pm \epsilon)b$ 其實是表示 $a\in \left[(1-\epsilon)b,(1+\epsilon)b\right]$ 。這個定義是對 $S$ 的描述，意味著這個 $S$ 有下面的性質：他作用後不會對被作用的向量有太大改變，而這指向量的 2-norm 會在原本的 $(1\pm \epsilon)$ 倍之間。又或者我們也可以直接看 $A$ 的 operator norm，意思是一樣的。

這個定義容許的 $S$ 其實蠻廣泛的，反正只要滿足那個條件的 $S$ 都合法。但不過實際上，我們需要這個 embedding 來降維動機其實就是因為原本的矩陣運算太大、太慢，因此通常我們有一些『理想中』的 $S$ ：除了滿足 (1) 以外，會希望他例如很 sparse ，或是至少很好算。

另外，我們可能會希望這個 embedding 可以是事先被選好的。也就是說，希望有一個 universal embedding 他可以對所有的 matrix $A$ 都是個合法的 embedding。這是理想上。但不過通常或許難以得到那麼強的結果，所以可能會放鬆一點要求，例如只要 a class of embedding matrices，或者是說 a distribution over some embedding matrices；而且可能不會是對於任意 matrix $A$ ，而是對於某種特定大小的 matrix $A$ 。於是有了以下定義：

Definition 2.2 : Suppose $\Pi$ is a distribution over $r \times n$ matrices $S$ , where $r:=r(n, d, \epsilon, \delta)$ . We say $\Pi$ is an oblivious $(\epsilon,\delta) \ell_2$ -subspace embedding if for any fixed $n\times d$ matrix $A$ ,

$\Pr_{S\sim \Pi}\left[ S \mbox{ is a }(1\pm \epsilon) \ell_2-\mbox{subspace embedding for }A\right]\geq 1-\delta$

又或者寫開的話，

$\Pr_{S\sim \Pi}\left[\forall x\in \mathbb{R}^d, \|SAx\|_2^2=(1\pm \epsilon)\|Ax\|_2^2\right]\geq 1-\delta$

這是一個蠻強的定義，好用卻不一定好得到，為什麼？因為這個 embedding 的選法跟 $A$ 無關，也就是我們不必看著 $A$ 來『客製化』對他的 embedding，不過好一點的是，我們不必對任意 $A$ 都滿足，而是只要對特定大小： $n\times d$ 這種大小的 $A$ 就行了。

在找到一個夠 sparse、或是夠好算的 $S$ 之前，我們先來找找看單純合法的 $S$ 。其中一種是 Fast Johnson Lindenstrauss Transform (FJLT) matrix，另一種是 Subsampled Randomized Hadamard Transform (SRHT) matrix。本文只會記錄到 FJLT matrix。

FJLT approach

FJLT approach 從字面上看起來，蠻顯然的就是希望利用 Johnson Lindenstrauss Lemma 提供的 random projection 方法來提供一種 embedding。接下來要定義所謂的 JLT matrix。

Definition 2.3.0 : A subset $V\subset \mathbb{R}^n$ is a $f$ -element subset if $|V|=f$ .

也就是該集合只有 $f$ 個元素。這個定義是為了下一個定義。

Definition 2.3 : A random matrix $S\in \mathbb{R}^{k\times n}$ forms a $JLT(\epsilon,\delta,f)$ if

$\Pr_{S}\left[\forall v,v'\in V\quad |\langle Sv,Sv'\rangle-\langle v,v'\rangle|\leq \epsilon\|v\|_2\|v'\|_2\right]\geq 1-\delta$

where $V\subset \mathbb{R}^n$ is any $f$ -element subset.

定義 2.3 是用來描述另一種 $S$ 。這個定義跟我們熟悉的 Johnson Lindenstrauss Lemma 比較有關係，他是說 $S$ 會使 $V$ 中任兩點距離經過作用後仍然保值。這個定義有幾個地方蠻值得注意一下的，一個是他竟然是用 inner product 作為他要保值的對象；另一個是那個很奇怪的 $f$ -element subset $V$ 。

首先關於第一點，如果將所有 $v\in V$ 都限定是 unit vector，那麼這個要求跟要求 2-norm 保值是一樣的。因為

$\langle Sv,Sv'\rangle = \left(\|S(v+v')\|_2^2-\|Sv\|_2^2-\|Sv'\|_2^2\right)/2 --(2)$

如果現在改要求 2-norm 保值，也就是要求

$\|S(v+v')\|_2^2=(1\pm \epsilon)\|v+v'\|_2^2, \forall v, v'\in V$ and $\|Sv\|_2^2=(1\pm \epsilon)\|v\|_2^2, \forall v\in V$

那麼

$(2) = ((1\pm \epsilon)\|v+v'\|_2^2-(1\pm \epsilon)\|v\|_2^2-(1\pm \epsilon)\|v'\|_2^2)/2= \langle v,v'\rangle+\mathcal{O}(\epsilon)$

也就是說，在這狀況下，2-norm 保值就會 imply inner product 保值。

至於那個 $f$ -element subset $V$ ，其實是在說這個 $S$ 其實無法同時適用於所有 $\mathbb{R}^n$ space 的元素，而只能保證某有限多個點經由 $S$ 降維後可以保持他們的距離。這跟 JL Lemma 只能做到的東西很像：一個空間要裝 $n$ 個點，且能彼此之間是分得夠開的（可分辨的），那麼那個空間就至少要是 $\mathcal{O}(\log (n)/\epsilon^2)$ 那麼多維。

因此這裡我們發現，定義 2.3 跟定義 2.2 的強度落差蠻大的，因為定義 2.2 的那個 $S$ 是可以對所有的 $Ax$ ，而定義 2.3 竟然只能說 $f$ 個點之間的距離會保值。到了這裡大概可以想像後面的故事要怎麼發展了：可能是希望說定義 2.3 這個看起來比較弱的 $S$ 其實用一些不知道怎麼搞的操作，竟然會是一個符合定義 2.2 的合法 embedding。而下面的定理 2.1 ，作者真的就先直接給我們一個弱的 $S$ 。

Theorem 2.1: Let $0<\epsilon,\delta<1$ and $S=\frac{1}{\sqrt{k}}\mathbf{R}\in \mathbb{R}^{k\times n}$ , where all entries of $\mathbf{R}$ are independent standard normal random variables. If $k=\Omega\left(\epsilon^{-2}\log(f/\delta)\right)$ , then $S$ is a $JLT(\epsilon,\delta,f)$ .

從這個定理我們驚訝的知道，原來就一個那麼單純、容易建構的 $S$ ，只要他 matrix 的大小夠大（ $k=\Omega\left(\epsilon^{-2}\log(f/\delta)\right)$ ），那麼它就是一個 $JLT(\epsilon,\delta,f)$ 。這個定理的證明稍後再證，我們先來看一下有了這個弱的 $S$ 後，到底可以怎麼證明他其實也符合 definition 2.2 中那個比較強的條件。也是我們最終要證的目標。

Theorem 2.3 : Let $0<\epsilon,\delta<1$ and $S=\frac{1}{\sqrt{k}}\mathbf{R}\in \mathbb{R}^{k\times n}$ , where all entries of $\mathbf{R}$ are independent standard normal random variables. If $k=\Theta\left(\epsilon^{-2}(d+\log(1/\delta))\right)$ , then for any fixed $n\times d$ matrix $A$ ,

$\Pr_S\left[\forall x\in \mathbb{R}^d, \quad \|SAx\|_2^2=(1\pm \epsilon)\|Ax\|_2^2\right]\geq 1-\delta$

（proof idea of Theorem 2.3）：

證明這個定理需要花點工夫，不過雖然這個定理看起來很長，很多東西都是重複的，像是最前面一大段描述那個 $S$ 的樣子，跟定理 2.1 是一樣的。（那段雖是描寫 $S$ 的樣子，但其實會發現其實他也是在說明那麼 $\Pi$ 長什麼樣子。很顯然的， $\Pi$ 就是一個 distribution over random matrix $S$ 所有可能出現的值。）要用定理 2.1 來證明定理 2.3 ，大致的流程會長這樣：

如果 random matrix $S$ 的 $k=\Omega\left(\epsilon^{-2}\log(f/\delta)\right)$

$\Rightarrow$ $S$ 是一個 $JLT(\epsilon,\delta,f)\quad$ — by Thm 2.1

$\Leftrightarrow$ $\Pr_{S}\left[\forall v,v'\in V\quad |\langle Sv,Sv'\rangle-\langle v,v'\rangle|\leq \epsilon\|v\|_2\|v'\|_2\right]\geq 1-\delta$ , 其中 $V$ 是一個只有 $f$ 個元素的集合。 — by def 2.3

$\Rightarrow$ $\Pr_S\left[\forall x\in \mathbb{R}^d, \quad \|SAx\|_2^2=(1\pm \epsilon)\|Ax\|_2^2\right]\geq 1-\delta$ — hope

然後就證完了！很顯然的，要完成上述證明有一些事情必須解決：

證明定理 2.1（by JL Lemma）
證明那個 “hope"，也就是證明：如果 $\forall v,v'\in V\quad |\langle Sv,Sv'\rangle-\langle v,v'\rangle|\leq \epsilon\|v\|_2\|v'\|_2$ ，那麼 $\forall y\in M, \|Sy\|_2^2=(1\pm \epsilon)\|y\|_2^2$ ，其中 $M=\{y\in \mathbb{R}^n | y=Ax \mbox{ for some }x\in \mathbb{R}^d\mbox{ and }\|y\|_2=1\}$ 。
要滿足證明最剛開始的『如果』。那個『如果』一旦不成立，那後面的東西就完蛋了。因此得決定 $S$ 到底該是多大的 matrix。要決定 $S$ 的樣子，就得知道 $f$ 是多少，也就是知道某個 $V$ 究竟可以有幾個元素。

（proof of Thm 2.1）

這個證明比較容易理解，因此寫得比較簡短。證明可以直接從如果 $S=\frac{1}{\sqrt{k}}\mathbf{R}\in \mathbb{R}^{k\times n}$ ，其中 $k=\mathcal{O}(\epsilon^{-2}\log (1/\delta))$ ，那麼

$\forall v\in \mathbb{R}^n,\quad \Pr_{S}\left(\|Sv\|_2^2=(1\pm \epsilon)\|v\|_2^2\right)\geq 1-\delta$

也就是對任何 $v\in \mathbb{R}^n$ ，有很高機率經過 $S$ 作用後都能保值。而如果現在我們空間中有 $f$ 個點需要經由 $S$ 降為，那麼用 union bound 後，就會得到

$\Pr_S \left(\forall v,v'\in [f],\quad |\langle Sv,Sv' \rangle-\langle v,v' \rangle|=\pm \epsilon \|v\|_2\|v'\|_2 \right)\leq 1-f^2\delta$

也就是降維後，有很高的機率，這 $f$ 個點兩兩之間的距離都會保值。而為了要讓最後的機率跟 $f$ 無關，因此回頭適當的調整 $k$ 。因此就會得到定理 2.1 中 $k=\mathcal{O}(\epsilon^{-2}\log (f/\delta))$ 。

除了定理 2.1 以外，要完成其他兩件事，看起來都跟那個 $V$ 很有關係。

很明顯的，" hope " 中的落差是 $V$ 是一個只有有限多個元素的集合，而 $M$ 是一個有無限多個元素的集合，一個常見解決這種事情的方法是找 $M$ 的 $\epsilon$ -covering。也就是說找一個 $V\subset M$ ，這個 $V$ 滿足的性質是

$\forall m\in M, \exists v\in V$ 使得 $\|m-v\|_2\leq \epsilon\quad --(a)$

接著要說明 $V$ 只要取 $M$ 的 $1/2$ -covering，真的就夠我們證明這件事了。

（proof of hope ）

首先，每個 $y\in M$ 都可以用 $V$ 中的展開： $y=y^0+y^1+y^2+\dots$ 。其中 $\|y^i\|\leq 1/2^i$ ，且 $y^i$ 是 $V$ 中的點乘以某個常數倍。那麼

$\|Sy\|_2^2=\|S(y^0+y^1+y^2+\cdots)\|_2^2$

$=\sum\limits_{0\leq i<j<\infty}\|Sy^i\|_2^2+2\langle Sy^i,Sy^j\rangle$ — 展開

$=\left(\sum\limits_{0\leq i<j<\infty}(1\pm\epsilon)\|y^i\|_2^2+\right)+\left(\sum\limits_{0\leq i<j<\infty}\langle y^i,y^j\rangle\pm\epsilon\|y^i\|_2\|y^j\|_2\right)$ — by 第 1 點的『如果』

$=1\pm \mathcal{O}(\epsilon)$ — by $\|y\|_2=1$

於是我們證明了對於每個 $y\in M$ ，真的都滿足 1. 了！

第二件事是決定 $S$ 到底該是多大的 matrix。依照前一點， $V$ 是某個從跟 $A$ 有關的集合 $M$ 構造出來的。但由於我們希望 $S$ 的建造只跟 $A$ 的大小（ $n\times d$ ）有關，而跟 $A$ 的內容物無關，因此我們要說 $S$ 的建造（決定 $k$ ）其實可以只跟 $d$ 有關（當然還有 $\epsilon, \delta$ ），而且還要驗證 $k$ 真的是有限多個。

（show that $\log(|V|)\leq \mathcal{O}(d)$ ）

這其實就是一個 “packing and covering" 問題。記得的人就不用繼續看了。關鍵就是 $\epsilon$ -packing 問題的 optimal 不小於 $\epsilon$ -covering 問題的 optimal。也就是令 $F()$ 表示括號內問題的最佳解，那麼

$F( \epsilon-\mbox{covering})\leq F(\epsilon-\mbox{packing})$ — (b)

因此只要能給 $\epsilon$ -packing 的 optimal 一個上界就行了。

我們可以用空間中塞小球來試想這個狀況。在證明中，我們對 $V$ 的要求是滿足 (a) 式，現在把 $V$ 的元素想像成是小球的紅色球心。滿足 (a) 意思其實就是對於空間中任何點，距離它半徑 $\epsilon$ 的範圍以內，一定存在一個的紅色球心。因此要有夠多的紅色球心，使得從球心開一個半徑為 $\epsilon$ 的小球（黃球），這些小球會將整個空間蓋滿不會有空隙（如圖）。因此問題變成問『黃球數量至少多少（才能填滿空間）？』

這個『至少』問題不好解，因為只要比 optimal 大的答案都是對的，所以我當然可以塞越多越好。不過在原問題中，我希望 $V$ 點不要太多，這要怎麼處理呢？現在我不僅希望所有空間中的點，半徑 $\epsilon$ 的範圍以內，一定存在一個的紅色球心；還希望所有紅色球心彼此的距離都不小於 $\epsilon$ ，這樣點才不會太多。同樣這問題可以用球來想像，也就是現在從球心開一個半徑為 $\latex \epsilon/2$ 的小球（藍球），這些球彼此不會互相重疊。

現在我可以改用藍球問題來解黃球問題，也就是利用 (b) 式，並給藍球的 optimal 一個上界就搞定了。至於為什麼 (b) 式是呈現這個關係，若要認真寫證明其實也不難，可以參考『Lecture』。不過偷懶一點的話，其實光是看上圖就知道了。上圖的黃球和藍球的紅色球心重合，而這組紅色球心，正好都是黃球問題和藍球問題的合法解，此時黃球和藍球一樣多。而黃球問題的 optimal 只會更少（拿掉幾個還是可以覆蓋整張圖），而藍球問題的 optimal 只會更多（可以再多塞幾個藍球），因此顯然 (b) 式是對的。

最後最後，藍球問題的上界怎麼求呢？可以考慮藍球在單位球之內的狀況，顯然個數就是球的體積比。不過還有一件小事就是，事實上我們允許球心在邊界上，所以藍色球覆蓋的區域會稍微更大一點，整個大球半徑會是 $1+\epsilon/2$ 。所以

$|V|\leq\frac{(1+\epsilon/2)^d}{(\epsilon/2)^d}=\mathcal{O}(1+(2/\epsilon)^d)$

至此我們證完定理 2.3 以及它所需要的所有事情了！

Numerical Linear Algebra — subspace embedding

Chapter 2

Section 2.1

FJLT approach

發表者：turtleang

發表留言取消回覆

Chapter 2

Section 2.1

FJLT approach

分享此文：

相關

發表者：turtleang

發表留言 取消回覆

發表留言取消回覆