做網站項目后臺的seo技術專員招聘
文章目錄
- 1. 為什么要低秩矩陣
- 1.1 矩陣A的秩定義
- 1.2 矩陣壓縮PCA
- 2. 低秩矩陣圖像處理
- 3. 秩的相關性質
- 3.1 秩的公差軸表示
- 3.2 Eckart-Young 定理
- 4. 低秩矩陣
- 4.1 低秩矩陣描述
- 4.2 函數低秩矩陣形式
- 4.3通項小結
- 4.4 函數采樣擬合
- 5. 西爾維斯特方程
- 5.1 希爾伯特矩陣舉例
- 5.2 范德蒙矩陣舉例
- 5.3 西爾維斯特方程
1. 為什么要低秩矩陣
1.1 矩陣A的秩定義
如果矩陣X為n行n列實數矩陣，其有n個特征值如下：
σ 1 ≥ σ 2 ≥ ? ≥ σ k ≥ σ k + 1 ≥ ? ≥ σ n \begin{equation} \sigma_1\ge\sigma_2\ge\cdots\ge\sigma_k\ge\sigma_{k+1}\ge\cdots\ge\sigma_{n} \end{equation} σ1?≥σ2?≥?≥σk?≥σk+1?≥?≥σn???
- 如果滿足如下條件
σ k + 1 = 0 , σ k > 0 \begin{equation} \sigma_{k+1}=0,\sigma_k>0 \end{equation} σk+1?=0,σk?>0??
那么可得：
r a n k ( X ) = k , X = σ 1 u 1 v 1 T + σ 2 u 2 v 2 T + ? + σ k u k v k T \begin{equation} rank(X)=k,X=\sigma_1u_1v_1^T+\sigma_2u_2v_2^T+\cdots+\sigma_ku_kv_k^T \end{equation} rank(X)=k,X=σ1?u1?v1T?+σ2?u2?v2T?+?+σk?uk?vkT???
1.2 矩陣壓縮PCA
我們的世界里面有很多數據，如果我們原封不動的發(fā)送數據，那么會導致數據量的增大，我們希望對數據進行壓縮后再打包壓縮，這樣的話我們能夠在帶寬一定的情況下發(fā)送更多的數據，舉例，假設我們有一個矩陣X，我們可以經過SVD奇異值分解得到如下：
-
假設矩陣 n × n n\times n n×n 矩陣的秩為k
X = σ 1 u 1 v 1 T + σ 2 u 2 v 2 T + ? + σ k u k v k T + σ k + 1 u k + 1 v k + 1 T + ? + σ n u n v n T \begin{equation} X=\sigma_1u_1v_1^T+\sigma_2u_2v_2^T+\cdots+\sigma_ku_kv_k^T+\sigma_{k+1}u_{k+1}v_{k+1}^T+\cdots+\sigma_nu_nv_n^T\end{equation} X=σ1?u1?v1T?+σ2?u2?v2T?+?+σk?uk?vkT?+σk+1?uk+1?vk+1T?+?+σn?un?vnT??? -
我們知道矩陣X的奇異值關系如下：
σ 1 ≥ σ 2 ≥ ? ≥ σ k ≥ σ k + 1 ≥ ? ≥ σ n \begin{equation} \sigma_1\ge\sigma_2\ge\cdots\ge\sigma_k\ge\sigma_{k+1}\ge\cdots\ge\sigma_{n} \end{equation} σ1?≥σ2?≥?≥σk?≥σk+1?≥?≥σn??? -
如果矩陣X的秩為k，那么可得：
σ k + 1 = ? = σ n = 0 \begin{equation} \sigma_{k+1}=\cdots=\sigma_{n}=0 \end{equation} σk+1?=?=σn?=0?? -
在沒有低秩壓縮的情況下，我們發(fā)送數據大小 S 1 S_1 S1?為,直接長=n寬=n相乘
S 1 = n ? n = n 2 \begin{equation} S_1=n*n=n^2 \end{equation} S1?=n?n=n2?? -
SVD奇異值分解后可得：
X = σ 1 u 1 v 1 T + σ 2 u 2 v 2 T + ? + σ k u k v k T \begin{equation} X=\sigma_1u_1v_1^T+\sigma_2u_2v_2^T+\cdots+\sigma_ku_kv_k^T \end{equation} X=σ1?u1?v1T?+σ2?u2?v2T?+?+σk?uk?vkT??? -
在低秩壓縮的后下，我們發(fā)送數據大小 S 2 S_2 S2?為，其中每個
S 2 = ( n + n ) ? k = 2 n k \begin{equation} S_2=(n+n)*k=2nk \end{equation} S2?=(n+n)?k=2nk??
-
那么我們可以得到如下：
2 n k ≤ n 2 → k ≤ n 2 \begin{equation} 2nk\leq n^2\rightarrow k\leq\frac{n}{2} \end{equation} 2nk≤n2→k≤2n??? -
那問題來了，我們能夠做得更好嗎？我們能夠用更小的數據來壓縮嗎？
2. 低秩矩陣圖像處理
假設我們有一張日本國旗的圖像表示如下，我們
- 如圖所示，我們可以依據對稱性，將一個日本國旗拆解為如下三個部分，每個部分的秩表示如下,注意要取整：
r 1 = ( 1 ? 2 2 ) r ; r 2 = ( 1 ? 2 2 ) r ; r 3 = 1 \begin{equation} r_1=(1-\frac{\sqrt{2}}{2})r;r_2=(1-\frac{\sqrt{2}}{2})r;r_3=1 \end{equation} r1?=(1?22??)r;r2?=(1?22??)r;r3?=1?? - 那么拆解后，數據的秩表示如下：
r k = ( 2 ? 2 ) r + 1 \begin{equation} r_k=(2-\sqrt{2})r+1 \end{equation} rk?=(2?2?)r+1?? - 小結：對于一個原始的日本國旗圖像來說，我們通過對稱的原理，不斷的對稱分解得到三個最小的無法對稱的三個小圖像，這樣我們可以將原來的日本國旗圖像最后分解為三個小圖像發(fā)給對方，當對方收到三個小圖像后，可以通過對稱原理進行還原，這樣數據就壓縮了，我們可以進行數據低秩壓縮處理。
- 整體思路如下:
3. 秩的相關性質
3.1 秩的公差軸表示
假設我們有一個公差 0 < ? < 1 0<\epsilon<1 0<?<1, 如果滿足 σ k + 1 ≤ ? σ 1 ( x ) , σ k ≥ ? σ 1 ( x ) \sigma_{k+1}\le \epsilon\sigma_1(x),\sigma_{k}\ge \epsilon\sigma_1(x) σk+1?≤?σ1?(x),σk?≥?σ1?(x),則 r a n k ? = k rank_{\epsilon}=k rank??=k
- 我們知道 0 < ? < 1 0<\epsilon<1 0<?<1，兩百年乘以 σ 1 ( x ) \sigma_1(x) σ1?(x) 可得：
0 < ? σ 1 ( x ) < σ 1 ( x ) \begin{equation} 0<\epsilon\sigma_1(x)<\sigma_1(x) \end{equation} 0<?σ1?(x)<σ1?(x)?? - 也就是說 ? σ 1 ( x ) \epsilon\sigma_1(x) ?σ1?(x) 可以取到所有大于零的奇異值
- 也就是說我們能夠在 σ k ( x ) \sigma_k(x) σk?(x)這個點上面找到奇異值的正負邊界，那么我們就能夠知道秩為k。
3.2 Eckart-Young 定理
假設矩陣B有和矩陣 A k A_k Ak?一樣的值為k，那么可得如下結論：
∣ ∣ A ? B ∣ ∣ ≥ ∣ ∣ A ? A k ∣ ∣ \begin{equation} ||A-B|| \geq ||A-A_k|| \end{equation} ∣∣A?B∣∣≥∣∣A?Ak?∣∣??
- 畫圖證明：
假設我們定義矩陣A為一個向量， A k A_k Ak?為矩陣A向量的子向量,定義矩陣B的秩為k，那么矩陣B向量的長度和向量 A k A_k Ak?長度一樣，方向不同，具體如下圖所述：
-由于 0 ° < θ < 90 ° 0°<\theta<90° 0°<θ<90°，所以可得 90 ° < β < 180 ° 90°<\beta<180° 90°<β<180°，也就是說在新的三角形中， β \beta β是鈍角，那么鈍角對應的邊最大，所以可得 ∣ ∣ C ∣ ∣ ≥ ∣ ∣ D ∣ ∣ ||C||\ge ||D|| ∣∣C∣∣≥∣∣D∣∣,可以得到結論如下：
∣ ∣ A ? B ∣ ∣ ≥ ∣ ∣ A ? A k ∣ ∣ \begin{equation} ||A-B||\geq ||A-A_k|| \end{equation} ∣∣A?B∣∣≥∣∣A?Ak?∣∣?? - 那么 σ k + 1 = ∣ ∣ A ? A k ∣ ∣ \sigma_{k+1}=||A-A_k|| σk+1?=∣∣A?Ak?∣∣暫時不會，后面補充吧！！
4. 低秩矩陣
4.1 低秩矩陣描述
-
4.1 hilbert 希爾伯特矩陣
我們定義希爾伯特矩陣如下：
H j k = 1 j + k ? 1 \begin{equation} H_{jk}=\frac{1}{j+k-1} \end{equation} Hjk?=j+k?11??? -
4.2 Vandermonde 范德蒙矩陣
我們定義范德蒙矩陣如下：
V n = [ 1 x 1 x 1 2 ? x 1 n ? 1 1 x 2 x 2 2 ? x 2 n ? 1 ? ? ? ? ? 1 x n x n 2 ? x n n ? 1 ] \begin{equation} V_{n}=\begin{bmatrix} 1&x_1&x_1^2&\cdots&x_1^{n-1}\\\\ 1&x_2&x_2^2&\cdots&x_2^{n-1}\\\\ \vdots&\vdots&\vdots&\cdots&\vdots\\\\ 1&x_n&x_n^2&\cdots&x_n^{n-1} \end{bmatrix} \end{equation} Vn?= ?11?1?x1?x2??xn??x12?x22??xn2???????x1n?1?x2n?1??xnn?1?? ??? -
其中 A n = [ a i j ] A_n=[a_{ij}] An?=[aij?]時一個 n × n n\times n n×n階矩陣，每個元素為 a i j = x i j ? 1 a_{ij}=x_i^{j-1} aij?=xij?1?
經常我們需要求解 V n ? 1 V_{n}^{-1} Vn?1?,但是因為 V n V_n Vn?是低秩矩陣，所以很難求解其逆矩陣，那為什么這么難求這些低秩矩陣的逆呢？原因居然是世界是平滑的，所以存在很多低秩的矩陣。
4.2 函數低秩矩陣形式
假設我們有一個函數表示如下：
P ( x , y ) = 1 + x + x y → X j k = P ( j , k ) \begin{equation} P(x,y)=1+x+xy\rightarrow X_{jk}=P(j,k) \end{equation} P(x,y)=1+x+xy→Xjk?=P(j,k)??
- 那么矩陣X可以表示如下：
X = [ 1 1 ? 1 ] [ 1 1 ? 1 ] + [ 1 2 ? n ] [ 1 1 ? 1 ] + [ 1 2 ? n ] [ 1 2 ? n ] \begin{equation} X=\begin{bmatrix} 1\\\\1\\\\\vdots\\\\1 \end{bmatrix}\begin{bmatrix} 1&1&\cdots&1 \end{bmatrix}+\begin{bmatrix} 1\\\\2\\\\\vdots\\\\n \end{bmatrix}\begin{bmatrix} 1&1&\cdots&1 \end{bmatrix}+\begin{bmatrix} 1\\\\2\\\\\vdots\\\\n \end{bmatrix}\begin{bmatrix} 1&2&\cdots&n \end{bmatrix} \end{equation} X= ?11?1? ?[1?1???1?]+ ?12?n? ?[1?1???1?]+ ?12?n? ?[1?2???n?]?? - 那么可以得到矩陣X的秩小于3，即 R a n k ( X ) ≤ 3 Rank(X)\le3 Rank(X)≤3
4.3通項小結
假設我們有如下函數
p ( x , y ) = ∑ s = 0 m ? 1 ∑ t = 0 m ? 1 a s t x s y t , X j k = p ( j , k ) \begin{equation} p(x,y)=\sum_{s=0}^{m-1}\sum_{t=0}^{m-1}a_{st}x^sy^t,X_{jk}=p(j,k) \end{equation} p(x,y)=s=0∑m?1?t=0∑m?1?ast?xsyt,Xjk?=p(j,k)??
- 那么我們可以得到矩陣X的秩有如下關系：
r a n k ( X ) ≤ m 2 \begin{equation} rank(X)\leq m^2 \end{equation} rank(X)≤m2??
4.4 函數采樣擬合
假設我們有一個矩陣X且 X j k = 1 j + k ? 1 , f ( x , y ) = 1 x + y ? 1 X_{jk}=\frac{1}{j+k-1},f(x,y)=\frac{1}{x+y-1} Xjk?=j+k?11?,f(x,y)=x+y?11?,我們希望通過在 f ( x , y ) f(x,y) f(x,y)函數中采樣的方法得到一個近似的函數 p ( x , y ) p(x,y) p(x,y)，使得我們能夠在進行了有限的采樣后，我們只需要用 p ( x , y ) p(x,y) p(x,y)近似于原函數 f ( x , y ) f(x,y) f(x,y)
∣ f ( x , y ) ? p ( x , y ) ∣ ≤ ? n ∣ ∣ x ∣ ∣ 2 \begin{equation} |f(x,y)-p(x,y)|\leq \frac{\epsilon}{n}||x||_2 \end{equation} ∣f(x,y)?p(x,y)∣≤n??∣∣x∣∣2???
- 是不是很神奇，用有限的采樣可以擬合出來原來的函數。
假設我們有一個希爾伯特矩陣，其秩為1000，假設我們有一個公差 ? = 1 0 ? 15 \epsilon=10^{-15} ?=10?15,Reade's大神得到秩為
r a n k ? ( H 1000 ) ≤ 719 \begin{equation} rank_{\epsilon}(H_{1000})\leq 719 \end{equation} rank??(H1000?)≤719??
5. 西爾維斯特方程
Sylvester 方程：
A X + X B = C \begin{equation} AX+XB=C \end{equation} AX+XB=C??
其中A、B及C是已知的矩陣，問題是要找出符合條件的X。其中所有矩陣的系數都是復數。為了要使方程成立，矩陣的行和列需要滿足一定條件，A和B都要是方陣，大小分別是n和m，而X和C要是n行m列的矩陣，n和m也可以相等，四個矩陣都是大小相同的方陣。
西爾維斯特方程有唯一解X的充分必要條件是A和-B沒有共同的特征值。
AX+XB=C也可以視為是（可能無窮維中）巴拿赫空間中有界算子的方程。此情形下，唯一解X的充份必要條件幾乎相同：唯一解X的充份必要條件是A和-B的譜互為不交集
5.1 希爾伯特矩陣舉例
[ 1 2 3 2 ? n ? 1 2 ] H ? H [ ? 1 2 ? 3 2 ? ? n + 1 2 ] = [ 1 1 ? 1 1 1 ? 1 ? ? ? ? 1 1 ? 1 ] \begin{equation} \begin{bmatrix} \frac{1}{2}\\\\ &\frac{3}{2}\\\\ &&\ddots\\\\ &&&n-\frac{1}{2} \end{bmatrix}H-H\begin{bmatrix} -\frac{1}{2}\\\\ &-\frac{3}{2}\\\\ &&\ddots\\\\ &&&-n+\frac{1}{2} \end{bmatrix}=\begin{bmatrix} 1&1&\cdots&1\\\\ 1&1&\cdots&1\\\\ \vdots&\vdots&\cdots&\vdots\\\\ 1&1&\cdots&1 \end{bmatrix} \end{equation} ?21??23????n?21?? ?H?H ??21???23?????n+21?? ?= ?11?1?11?1??????11?1? ???
- 我們那H中的第i,j項目來說；
H i j = 1 i + j ? 1 \begin{equation} H_{ij}=\frac{1}{i+j-1} \end{equation} Hij?=i+j?11???
( i ? 1 2 ) ? 1 i + j ? 1 ? ( ? j + 1 2 ) 1 i + j ? 1 = i + j ? 1 i + j ? 1 = 1 \begin{equation} (i-\frac{1}{2})\cdot\frac{1}{i+j-1}-(-j+\frac{1}{2})\frac{1}{i+j-1}=\frac{i+j-1}{i+j-1}=1 \end{equation} (i?21?)?i+j?11??(?j+21?)i+j?11?=i+j?1i+j?1?=1?? - 既然每個元素結果為1，所以最后結果為全1矩陣。
5.2 范德蒙矩陣舉例
A = [ x 1 x 2 ? x n ] ; B = [ 0 0 ? ? 1 1 0 0 ? ? 0 1 0 ? 0 0 0 1 0 ] ; C = [ 0 0 0 x 1 n + 1 0 0 0 x 2 n + 1 0 0 0 ? 0 0 0 x n n + 1 ] ; \begin{equation} A=\begin{bmatrix}x_1\\\\ &x_2\\\\ &&\ddots\\\\ &&&x_n\end{bmatrix}; B=\begin{bmatrix} 0&0&&\cdots&-1\\\\ 1&0&0&\cdots&\cdot\\\\ 0&1&0&\ddots&0\\\\ 0&0&1&&0\end{bmatrix}; C=\begin{bmatrix} 0&0&0&x_1^n+1\\\\ 0&0&0&x_2^n+1\\\\ 0&0&0&\vdots\\\\ 0&0&0&x_n^n+1 \end{bmatrix}; \end{equation} A= ?x1??x2????xn?? ?;B= ?0100?0010?001??????1?00? ?;C= ?0000?0000?0000?x1n?+1x2n?+1?xnn?+1? ?;??
5.3 西爾維斯特方程
如果 X滿足如下方程：
A X ? X B = C \begin{equation} AX-XB=C \end{equation} AX?XB=C??
- A,B是正規(guī)矩陣，E為A的特征值集合，F為B的的特征值集合，那么可以得到如下：
σ r k + 1 ( X ) ≤ Z k [ σ ( A ) , σ ( B ) ] σ 1 ( X ) → r a n k ( C ) = r ; \begin{equation} \sigma_{rk+1}(X)\le Z_{k}[\sigma(A),\sigma(B)]\sigma_1(X)\rightarrow rank(C)=r; \end{equation} σrk+1?(X)≤Zk?[σ(A),σ(B)]σ1?(X)→rank(C)=r;??