芜湖做网站的公司排名,百度竞价ocpc投放策略,自己做热图的网站,做网站英文文章目录 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 范德蒙… 文章目录 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_{k1}\ge\cdots\ge\sigma_{n} \end{equation} σ1≥σ2≥⋯≥σk≥σk1≥⋯≥σn
如果满足如下条件 σ k 1 0 , σ k 0 \begin{equation} \sigma_{k1}0,\sigma_k0 \end{equation} σk10,σk0 那么可得 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σ1u1v1Tσ2u2v2T⋯σkukvkT
1.2 矩阵压缩PCA
我们的世界里面有很多数据如果我们原封不动的发送数据那么会导致数据量的增大我们希望对数据进行压缩后再打包压缩这样的话我们能够在带宽一定的情况下发送更多的数据举例假设我们有一个矩阵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_{k1}u_{k1}v_{k1}^T\cdots\sigma_nu_nv_n^T\end{equation} Xσ1u1v1Tσ2u2v2T⋯σkukvkTσk1uk1vk1T⋯σnunvnT 我们知道矩阵X的奇异值关系如下 σ 1 ≥ σ 2 ≥ ⋯ ≥ σ k ≥ σ k 1 ≥ ⋯ ≥ σ n \begin{equation} \sigma_1\ge\sigma_2\ge\cdots\ge\sigma_k\ge\sigma_{k1}\ge\cdots\ge\sigma_{n} \end{equation} σ1≥σ2≥⋯≥σk≥σk1≥⋯≥σn 如果矩阵X的秩为k那么可得 σ k 1 ⋯ σ n 0 \begin{equation} \sigma_{k1}\cdots\sigma_{n}0 \end{equation} σk1⋯σn0 在没有低秩压缩的情况下我们发送数据大小 S 1 S_1 S1为,直接长n宽n相乘 S 1 n ∗ n n 2 \begin{equation} S_1n*nn^2 \end{equation} S1n∗nn2 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σ1u1v1Tσ2u2v2T⋯σkukvkT 在低秩压缩的后下我们发送数据大小 S 2 S_2 S2为其中每个 S 2 ( n n ) ∗ k 2 n k \begin{equation} S_2(nn)*k2nk \end{equation} S2(nn)∗k2nk 那么我们可以得到如下 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_31 \end{equation} r1(1−22 )r;r2(1−22 )r;r31那么拆解后数据的秩表示如下 r k ( 2 − 2 ) r 1 \begin{equation} r_k(2-\sqrt{2})r1 \end{equation} rk(2−2 )r1小结对于一个原始的日本国旗图像来说我们通过对称的原理不断的对称分解得到三个最小的无法对称的三个小图像这样我们可以将原来的日本国旗图像最后分解为三个小图像发给对方当对方收到三个小图像后可以通过对称原理进行还原这样数据就压缩了我们可以进行数据低秩压缩处理。整体思路如下:
3. 秩的相关性质
3.1 秩的公差轴表示
假设我们有一个公差 0 ϵ 1 0\epsilon1 0ϵ1, 如果满足 σ k 1 ≤ ϵ σ 1 ( x ) , σ k ≥ ϵ σ 1 ( x ) \sigma_{k1}\le \epsilon\sigma_1(x),\sigma_{k}\ge \epsilon\sigma_1(x) σk1≤ϵσ1(x),σk≥ϵσ1(x),则 r a n k ϵ k rank_{\epsilon}k rankϵk
我们知道 0 ϵ 1 0\epsilon1 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°\theta90° 0°θ90°所以可得 90 ° β 180 ° 90°\beta180° 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_{k1}||A-A_k|| σk1∣∣A−Ak∣∣暂时不会后面补充吧
4. 低秩矩阵
4.1 低秩矩阵描述 4.1 hilbert 希尔伯特矩阵 我们定义希尔伯特矩阵如下 H j k 1 j k − 1 \begin{equation} H_{jk}\frac{1}{jk-1} \end{equation} Hjkjk−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} 1x_1x_1^2\cdotsx_1^{n-1}\\\\ 1x_2x_2^2\cdotsx_2^{n-1}\\\\ \vdots\vdots\vdots\cdots\vdots\\\\ 1x_nx_n^2\cdotsx_n^{n-1} \end{bmatrix} \end{equation} Vn 11⋮1x1x2⋮xnx12x22⋮xn2⋯⋯⋯⋯x1n−1x2n−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} aijxij−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)1xxy\rightarrow X_{jk}P(j,k) \end{equation} P(x,y)1xxy→XjkP(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} 11\cdots1 \end{bmatrix}\begin{bmatrix} 1\\\\2\\\\\vdots\\\\n \end{bmatrix}\begin{bmatrix} 11\cdots1 \end{bmatrix}\begin{bmatrix} 1\\\\2\\\\\vdots\\\\n \end{bmatrix}\begin{bmatrix} 12\cdotsn \end{bmatrix} \end{equation} X 11⋮1 [11⋯1] 12⋮n [11⋯1] 12⋮n [12⋯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_{s0}^{m-1}\sum_{t0}^{m-1}a_{st}x^sy^t,X_{jk}p(j,k) \end{equation} p(x,y)s0∑m−1t0∑m−1astxsyt,Xjkp(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}{jk-1},f(x,y)\frac{1}{xy-1} Xjkjk−11,f(x,y)xy−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 \epsilon10^{-15} ϵ10−15,Reades 大神得到秩为 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} AXXBC \end{equation} AXXBC
其中A、B及C是已知的矩阵问题是要找出符合条件的X。其中所有矩阵的系数都是复数。为了要使方程成立矩阵的行和列需要满足一定条件A和B都要是方阵大小分别是n和m而X和C要是n行m列的矩阵n和m也可以相等四个矩阵都是大小相同的方阵。 西尔维斯特方程有唯一解X的充分必要条件是A和-B没有共同的特征值。 AXXBC也可以视为是可能无穷维中巴拿赫空间中有界算子的方程。此情形下唯一解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} 11\cdots1\\\\ 11\cdots1\\\\ \vdots\vdots\cdots\vdots\\\\ 11\cdots1 \end{bmatrix} \end{equation} 2123⋱n−21 H−H −21−23⋱−n21 11⋮111⋮1⋯⋯⋯⋯11⋮1
我们那H中的第i,j项目来说 H i j 1 i j − 1 \begin{equation} H_{ij}\frac{1}{ij-1} \end{equation} Hijij−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}{ij-1}-(-j\frac{1}{2})\frac{1}{ij-1}\frac{ij-1}{ij-1}1 \end{equation} (i−21)⋅ij−11−(−j21)ij−11ij−1ij−11既然每个元素结果为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} 00\cdots-1\\\\ 100\cdots\cdot\\\\ 010\ddots0\\\\ 0010\end{bmatrix}; C\begin{bmatrix} 000x_1^n1\\\\ 000x_2^n1\\\\ 000\vdots\\\\ 000x_n^n1 \end{bmatrix}; \end{equation} A x1x2⋱xn ;B 01000010001⋯⋯⋱−1⋅00 ;C 000000000000x1n1x2n1⋮xnn1 ;
5.3 西尔维斯特方程
如果 X满足如下方程 A X − X B C \begin{equation} AX-XBC \end{equation} AX−XBC
A,B是正规矩阵E为A的特征值集合F为B的的特征值集合那么可以得到如下 σ r k 1 ( X ) ≤ Z k [ σ ( A ) , σ ( B ) ] σ 1 ( X ) → r a n k ( C ) r ; \begin{equation} \sigma_{rk1}(X)\le Z_{k}[\sigma(A),\sigma(B)]\sigma_1(X)\rightarrow rank(C)r; \end{equation} σrk1(X)≤Zk[σ(A),σ(B)]σ1(X)→rank(C)r;
