精华内容
下载资源
问答
  • 循环矩阵傅里叶对角化

    万次阅读 多人点赞 2016-03-15 14:10:30
    “任意循环矩阵可以被傅里叶变换矩阵对角化”这个概念常常出现在论文中,本文其做简单解释。

    All circulant matrices are made diagonal by the Discrete Fourier Transform (DFT), regardless of the generating vector x.
    任意循环矩阵可以被傅里叶变换矩阵对角化。

    文献中,一般用如下方式表达这一概念:
    X = C ( x ) = F ⋅ d i a g ( x ^ ) ⋅ F H X=C(x)=F \cdot diag(\hat{x}) \cdot F^H X=C(x)=Fdiag(x^)FH

    其中 X X X是循环矩阵, x ^ \hat{x} x^是原向量 x x x的傅里叶变换, F F F是傅里叶变换矩阵,上标H表示共轭转置: X H = ( X ∗ ) T X^H=(X^{*})^T XH=(X)T
    换句话说, X X X相似于对角阵, X X X的特征值是 x ^ \hat x x^的元素。

    另一方面,如果一个矩阵能够表示成两个傅里叶矩阵夹一个对角阵的乘积形式,则它是一个循环矩阵。其生成向量是对角元素的傅里叶逆变换:

    F ⋅ d i a g ( y ) ⋅ F H = C ( F − 1 ( y ) ) F \cdot diag(y) \cdot F^H = C(\mathcal{F}^{-1}(y)) Fdiag(y)FH=C(F1(y))
    这个公式初看疑问很多,以下一一讨论。

    X X X是什么?

    X X X是由原向量 x x x生成的循环矩阵。以矩阵尺寸 K = 4 K=4 K=4为例。

    X = C ( x ) = [ x 1 x 2 x 3 x 4 x 4 x 1 x 2 x 3 x 3 x 4 x 1 x 2 x 2 x 3 x 4 x 1 ] X=C(x)=\begin{bmatrix} x_1 & x_2 & x_3 & x_4 \\ x_4 & x_1 & x_2 & x_3 \\ x_3 & x_4 & x_1 & x_2 \\ x_2 & x_3 & x_4 & x_1 \\ \end{bmatrix} X=C(x)=x1x4x3x2x2x1x4x3x3x2x1x4x4x3x2x1

    F F F 是什么?

    F F F是离散傅里叶矩阵(DFT matrix),可以用一个复数 ω = e − 2 π i / K \omega = e^{-2\pi i/K} ω=e2πi/K表示,其中 K K K为方阵 F F F的尺寸。以 K = 4 K=4 K=4为例。

    F = 1 K [ 1 1 1 1 1 ω ω 2 ω 3 1 ω 2 ω 4 ω 6 1 ω 3 ω 6 ω 9 ] F=\frac{1}{\sqrt{K}} \begin{bmatrix} 1 & 1 & 1 & 1 \\ 1 & \omega & \omega^2 & \omega^3 \\ 1 & \omega^2 & \omega ^4 & \omega^6 \\ 1 & \omega^3 & \omega^6 & \omega^9 \end{bmatrix} F=K 111111ωω2ω31ω2ω4ω61ω3ω6ω9

    ω \omega ω想象成一个角度为 2 π / K 2\pi/K 2π/K的向量,这个矩阵的每一行是这个向量在不断旋转。从上到下,旋转速度越来越快。

    之所以称为DFT matrix,是因为一个信号的DFT变换可以用此矩阵的乘积获得:

    x ^ = D F T ( x ) = K ⋅ F ⋅ x \hat{x}=DFT(x)=\sqrt{K}\cdot F \cdot x x^=DFT(x)=K Fx

    反傅里叶变换也可以通过类似手段得到:

    x = 1 K F − 1 x ^ x=\frac{1}{\sqrt{K}}F^{-1}\hat{x} x=K 1F1x^

    傅里叶矩阵有许多性质:

    • 是对称矩阵,观察 ω \omega ω的规律即可知;
    • 满足 F H F = F F H = I F^HF=FF^H=I FHF=FFH=I,也就是说它是个酉矩阵(unitary)。可以通过将 F H F^{H} FH展开成 ω H \omega^{H} ωH验证。

    注意: F F F是常数,可以提前计算好,和要处理的 x x x无关。

    对角化怎么理解?

    把原公式两边乘以逆矩阵:

    F − 1 ⋅ X ⋅ ( F H ) − 1 = d i a g ( x ^ ) F^{-1} \cdot X \cdot (F^H)^{-1}=diag(\hat{x}) F1X(FH)1=diag(x^)
    利用前述酉矩阵性质:
    左 边 = F H X F = d i a g ( x ^ ) 左边=F^{H}XF=diag(\hat{x}) =FHXF=diag(x^)

    也就是说,矩阵 X X X通过相似变换 F F F变成对角阵 d i a g ( x ^ ) diag(\hat{x}) diag(x^),即对循环矩阵 X X X进行对角化。
    另外, F H X F F^HXF FHXF是矩阵 X X X的2D DFT变换。即傅里叶变换可以把循环矩阵对角化。

    怎么证明?

    可以用构造特征值和特征向量的方法证明(参看这篇论文1的3.1节),此处简单描述。
    考察待证明等式的第k列:
    X ⋅ f k = x ^ k ⋅ f k X\cdot f_k=\hat x_k\cdot f_k Xfk=x^kfk

    其中 f k f_k fk表示DFT矩阵的第k列, x ^ k \hat x_k x^k表示傅里叶变换的第k个元素。等价于求证: f k f_k fk x ^ k \hat x_k x^k X X X的一对特征向量和特征值。

    左边向量的第i个元素为: l e f t i = [ x i , f k ] left_i = \left[ x^i, f_k \right] lefti=[xi,fk] x i x_i xi表示把生成向量 x x x向右移动i位, [ ] [] []表示内积。
    内积只和两个向量的相对位移有关,所以可以把 f k f_k fk向左移动i位: l e f t i = [ x , f k − i ] left_i=\left[ x, f_k^{-i}\right] lefti=[x,fki]
    DFT矩阵列的移位可以通过数乘 ω \omega ω的幂实现: f k i = f 0 ⋅ ω i k f_k^i=f_0\cdot \omega^{ik} fki=f0ωik

    举例: K = 3 K=3 K=3
    F = 1 K [ 1 1 1 1 ω ω 2 1 ω 2 ω 4 ] F=\frac{1}{\sqrt{K}} \begin{bmatrix} 1 & 1 & 1\\ 1 & \omega & \omega^2 \\ 1 & \omega^2 & \omega ^4 \end{bmatrix} F=K 11111ωω21ω2ω4

    利用 ω N = 1 \omega^N=1 ωN=1.
    f 1 ⋅ ω = [ 1 , ω , ω 2 ] ⋅ ω = [ ω , ω 2 , ω 3 ] = [ ω , ω 2 , 1 ] = f 1 − 1 f_1\cdot \omega =[1,\omega,\omega^2]\cdot \omega = [\omega, \omega^2,\omega^3] = [\omega, \omega^2, 1]=f_1^{-1} f1ω=[1,ω,ω2]ω=[ω,ω2,ω3]=[ω,ω2,1]=f11

    f 1 ⋅ ω 2 = [ 1 , ω , ω 2 ] ⋅ ω 2 = [ ω 2 , ω 3 , ω 4 ] = [ ω 2 , 1 , ω ] = f 1 − 2 f_1\cdot \omega^2 =[1,\omega,\omega^2]\cdot \omega^2 = [\omega^2, \omega^3,\omega^4] = [\omega^2, 1, \omega]=f_1^{-2} f1ω2=[1,ω,ω2]ω2=[ω2,ω3,ω4]=[ω2,1,ω]=f12

    于是有:
    l e f t i = [ x , f k ⋅ ω i k ] = [ x , f k ] ⋅ ω i k left_i= \left [x, f_k \cdot \omega^{ik}\right ]=\left [x, f_k\right ] \cdot \omega^{ik} lefti=[x,fkωik]=[x,fk]ωik

    右边的$\hat x = F\cdot x , 考 虑 到 ,考虑到 F 的 第 k 行 和 第 k 列 相 同 , 的第k行和第k列相同, kk\hat x_k=[f_k,x] 。 另 外 。另外 f_k 的 第 i 个 元 素 为 的第i个元素为 i\omega^{ik}$:
    r i g h t i = x ^ k ⋅ f k i = [ f k ∗ , x ] ⋅ ω k i right_i = \hat x_k\cdot f_{ki}=[f_k^*,x]\cdot \omega^{ki} righti=x^kfki=[fk,x]ωki

    对任意k列的第i个元素有: l e f t i = r i g h t i left_i=right_i lefti=righti

    更多性质

    利用对角化,能推导出循环矩阵的许多性质。

    转置

    循环矩阵的转置也是一个循环矩阵(可以查看循环矩阵各元素排列证明),其特征值和原特征值共轭。
    X T = F ⋅ d i a g ( ( x ^ ) ∗ ) ⋅ F H X^T=F \cdot diag((\hat{x})^*) \cdot F^H XT=Fdiag((x^))FH
    可以通过如下方式证明:
    X T = ( F H ) T ⋅ d i a g ( x ^ ) F T X^T=(F^H)^T\cdot diag(\hat x) F^T XT=(FH)Tdiag(x^)FT
    由于 F F F是对称酉矩阵,且已知 X X X是实矩阵:
    X T = F ∗ ⋅ d i a g ( x ^ ) F = ( F ∗ ⋅ d i a g ( x ^ ) F ) ∗ = F ⋅ d i a g ( ( x ^ ) ∗ ) ⋅ F H X^T=F^*\cdot diag(\hat x) F=\left( F^*\cdot diag(\hat x) F\right)^*=F\cdot diag((\hat x)^*) \cdot F^H XT=Fdiag(x^)F=(Fdiag(x^)F)=Fdiag((x^))FH

    如果原生成向量 x x x是对称向量(例如[1,2,3,4,3,2]),则其傅里叶变换为实数,则:
    X T = C ( F − 1 ( x ^ ) ∗ ) = C ( x ) X^T=C\left( \mathcal F^{-1}(\hat x)^* \right)=C(x) XT=C(F1(x^))=C(x)

    卷积

    循环矩阵乘向量等价于生成向量的逆序和该向量卷积,可进一步转化为福利也变化相乘。
    注意卷积本身即包含逆序操作,另外利用了信号与系统中经典的“时域卷积,频域相乘”。

    F ( X y ) = F ( C ( x ) y ) = F ( x ˉ ∗ y ) = F ∗ ( x ) ⊙ F ( y ) \mathcal{F}(Xy) = \mathcal{F}(C(x)y)=\mathcal{F}(\bar x*y)=\mathcal{F}^*(x)\odot \mathcal{F}(y) F(Xy)=F(C(x)y)=F(xˉy)=F(x)F(y)
    其中 x ˉ \bar x xˉ表示把 x x x的元素倒序排列。星号表示共轭。

    相乘

    C , B C,B C,B为循环矩阵,其乘积的特征值等于特征值的乘积:

    A B = F ⋅ d i a g ( a ^ ) ⋅ F H ⋅ F ⋅ d i a g ( b ^ ) ⋅ F H AB = F\cdot diag(\hat a) \cdot F^H \cdot F \cdot diag(\hat b) \cdot F^H AB=Fdiag(a^)FHFdiag(b^)FH

    = F ⋅ d i a g ( a ^ ) ⋅ d i a g ( b ^ ) ⋅ F H = F ⋅ d i a g ( a ^ ⊙ b ^ ) ⋅ F H = F\cdot diag(\hat a) \cdot diag(\hat b) \cdot F^H=F\cdot diag(\hat a \odot \hat b) \cdot F^H =Fdiag(a^)diag(b^)FH=Fdiag(a^b^)FH

    = C ( F − 1 ( a ^ ⊙ b ^ ) ) =C\left( \mathcal F^{-1}(\hat a \odot \hat b)\right) =C(F1(a^b^))
    乘积也是循环矩阵,其生成向量是原生成向量对位相乘的傅里叶逆变换。

    相加

    和的特征值等于特征值的和:
    A + B = F ⋅ d i a g ( a ^ ) ⋅ F H + F ⋅ d i a g ( b ^ ) ⋅ F H = F ⋅ d i a g ( a ^ + b ^ ) ⋅ F H A+B = F\cdot diag(\hat a) \cdot F^H + F \cdot diag(\hat b) \cdot F^H=F\cdot diag(\hat a +\hat b) \cdot F^H A+B=Fdiag(a^)FH+Fdiag(b^)FH=Fdiag(a^+b^)FH

    = C ( F − 1 ( a ^ + b ^ ) ) = C ( F − 1 ( a ^ ) + F − 1 ( b ^ ) ) = C ( a + b ) =C\left( \mathcal F^{-1} (\hat a +\hat b)\right)=C\left( \mathcal F^{-1} (\hat a )+F^{-1} (\hat b )\right)=C\left( a+b\right) =C(F1(a^+b^))=C(F1(a^)+F1(b^))=C(a+b)
    和也是循环矩阵,其生成向量是原生成向量的和。

    求逆

    循环矩阵的逆,等价于将其特征值求逆。
    X − 1 = F ⋅ d i a g ( x ^ ) − 1 F H = C ( F − 1 ( d i a g ( x ^ ) − 1 ) ) X^{-1}=F\cdot diag(\hat{x})^{-1}F^H=C\left( \mathcal F^{-1}(diag(\hat{x})^{-1}) \right) X1=Fdiag(x^)1FH=C(F1(diag(x^)1))
    对角阵求逆等价于对角元素求逆。以下证明:
    F ⋅ d i a g ( x ^ ) − 1 ⋅ F H ⋅ F ⋅ d i a g ( x ^ ) ⋅ F H F\cdot diag(\hat{x})^{-1}\cdot F^H \cdot F\cdot diag(\hat{x}) \cdot F^H Fdiag(x^)1FHFdiag(x^)FH

    = F ⋅ d i a g ( x ^ ) − 1 ⋅ d i a g ( x ^ ) ⋅ F H = F ⋅ F H = I =F\cdot diag(\hat{x})^{-1}\cdot diag(\hat{x}) \cdot F^H=F\cdot F^H=I =Fdiag(x^)1diag(x^)FH=FFH=I

    逆也是循环矩阵

    有什么用?

    该性质可以将循环矩阵的许多运算转换成更简单的运算。例如:

    X H X = F ⋅ d i a g ( x ^ ⊙ x ^ ∗ ) ⋅ F H = C ( F − 1 ( x ^ ⊙ x ^ ∗ ) ) X^HX=F \cdot diag(\hat{x} \odot \hat{x}^*)\cdot F^H=C\left( \mathcal F^{-1}(\hat{x} \odot \hat{x}^*) \right) XHX=Fdiag(x^x^)FH=C(F1(x^x^))

    原始计算量:两个方阵相乘( O ( K 3 ) O(K^3) O(K3)
    转化后的计算量:反向傅里叶( K log ⁡ K K\log K KlogK)+向量点乘( K K K)。

    CV的许多算法中,都利用了这些性质提高运算速度,例如2015年TPAMI的这篇高速跟踪KCF方法2

    二维情况

    以上探讨的都是原始信号为一维的情况。以下证明二维情况下的 F H X F = d i a g ( x ^ ) F^HXF=diag(\hat x) FHXF=diag(x^),推导方法和一维类似。

    x x x是二维生成矩阵,尺寸 N × N N\times N N×N
    X X X是一个 N 2 × N 2 N^2\times N^2 N2×N2的分块循环矩阵,其uv块记为 x u v x^{uv} xuv,表示 x x x下移u行,右移v列。
    F F F N 2 × N 2 N^2\times N^2 N2×N2的二维DFT矩阵,其第uv块记为 f u v = { ω u i + v j } i j f_{uv}=\left\{ \omega^{ui+vj} \right\} _{ij} fuv={ωui+vj}ij

    举例:N=3 f 01 = [ 1 ω ω 2 1 ω ω 2 1 ω ω 2 ] , f 11 = [ 1 ω ω 2 ω ω 2 ω 3 ω 2 ω 3 ω 4 ] f_{01}=\begin{bmatrix} 1 & \omega & \omega^2 \\ 1 & \omega & \omega^2 \\ 1 & \omega & \omega^2\end{bmatrix}, f_{11}=\begin{bmatrix} 1 & \omega & \omega^2 \\ \omega & \omega^2 & \omega^3 \\ \omega^2 & \omega^3 & \omega^4\end{bmatrix}\\ f01=111ωωωω2ω2ω2,f11=1ωω2ωω2ω3ω2ω3ω4

    需要验证的共有 N × N N\times N N×N个等式,其中第 u v uv uv个为:
    [ X , f u v ] = x ^ u v ⋅ f u v [X, f_{uv}]=\hat x_{uv}\cdot f_{uv} [X,fuv]=x^uvfuv
    其中 [ X , f u v ] [X, f_{uv}] [X,fuv]表示把 x u v x^{uv} xuv分别和 f u v f_{uv} fuv做点乘,结果矩阵元素求和。
    这个等式的第ij元素为:
    [ x i j , f u v ] = x ^ u v ⋅ ω u i + v j [x^{ij},f_{uv}]=\hat x_{uv} \cdot \omega^{ui+vj} [xij,fuv]=x^uvωui+vj

    再次利用两个性质:1) 点乘只和两个矩阵相对位移有关,2) f u v f_{uv} fuv的位移可以用乘 ω \omega ω幂实现:
    l e f t i j = [ x , f u v − i − j ] = [ x , f u v ] ⋅ ω u i + v j = x ^ u v ⋅ ω u i + v j = r i g h t i j left_{ij}=[x,f_{uv}^{-i-j}]=[x,f_{uv}]\cdot \omega^{ui+vj}=\hat x_{uv} \cdot \omega^{ui+vj}=right_{ij} leftij=[x,fuvij]=[x,fuv]ωui+vj=x^uvωui+vj=rightij

    代码

    以下matlab代码验证上述性质。需要注意的是,matlab中的dftmatx函数给出的结果和本文定义略有不同,需做一简单转换。另外,matlab中的撇号表示共轭转置,transpose为转置函数,conj为共轭函数。

    clear;clc;close all;
    
    % 1. diagnolize 
    K = 5;      % dimension of problem
    
    x_base = rand(1,K);     % generator vector
    X = zeros(K,K);         % circulant matrix
    for k=1:K
        X(k,:) = circshift(x_base, [0 k-1]);
    end
    
    x_hat = fft(x_base);    % DFT
    
    F = transpose(dftmtx(K))/sqrt(K);       % the " ' " in matlab is transpose + conjugation
    
    X2 = F*diag(x_hat)*F';
    
    display(X);
    display(real(X2));
    
    % 2. fast compute correlation
    C = X'*X;
    C2 = (x_hat.*conj(x_hat))*conj(F)/sqrt(K);
    
    display(C);
    display(C2);
    

    1. Gray, Robert M. Toeplitz and circulant matrices: A review. now publishers inc, 2006. ↩︎

    2. Henriques, João F., et al. “High-speed tracking with kernelized correlation filters.” Pattern Analysis and Machine Intelligence, IEEE Transactions on 37.3 (2015): 583-596. ↩︎

    展开全文
  • 矩阵对角化

    万次阅读 2015-10-16 16:52:47
    一、矩阵对角化的理论 一个映射或者一个线性变换,都有一个矩阵和它相对应。矩阵或者映射是不是可以对角化工程应用来说比较重要,因为对角化后的矩阵,乘积简单,经过多次变换的话,相当于矩阵的多次方。矩阵...

    一、矩阵对角化的理论
    一个映射或者一个线性变换,都有一个矩阵和它相对应。矩阵或者映射是不是可以对角化,对工程应用来说比较重要,因为对角化后的矩阵,乘积简单,经过多次变换的话,相当于矩阵的多次方。矩阵能不能对角化,取决于它的特称向量能否构成矩阵的一个基。
    1.在域 F 上的 n × n 矩阵 A 是可对角化的,当且仅当它的特征空间的维度等于 n,它为真当且仅当存在由 A 的特征向量组成的Fn的基。如果找到了这样的基,可以形成有基向量作为纵列的矩阵 P,而 P-1AP 将是对角矩阵。这个矩阵的对角元素是 A 的特征值。
    2. 线性映射 T : V → V 是可对角化的,当且仅当它的特征空间的维度等于 dim(V),它为真当且仅当存在由 T 的特征向量组成的 V 的基。T 关于这个基将表示为对角矩阵。这个矩阵的对角元素是 T 的特征值。
    另一个特征化: 矩阵或线性映射在域 F 上可对角化的,当且仅当它的极小多项式在 F 上有不同的线性因子。

    下列充分(但非必要)条件经常是有用的。
    1. n × n 矩阵 A 只在域 F 上可对角化的,如果它在 F 中有 n 个不同的特征值,就是说,如果它的特征多项式在 F 中有 n 个不同的根。
    2. 线性映射 T : V → V 带有 n=dim(V) 是可对角化的,如果它有 n 个不同的特征值,就是说它的特征多项式在 F 中有 n 个不同的根。
    3. 在域 F 上的 n × n 矩阵 A,如果重根的维数等于其线性无关的特征向量的个数,则矩阵A可以对角化。
    4.
    二、矩阵对角化过程
    下面例子中,矩阵A是对称的,它可以进行对角化,虽然它只有2个不同的特征值,但是有4个线性无关的特征向量,所以能进行对角化。
    给定矩阵A,求它的特征值、特征向量,并对它进行对角化。
    (1)求特征多项式,matlab命令p= poly(A);
    (2)求解特征多项式,求出特征值,solve(P);
    (3)分别将特征值带入齐次方程组,求出基础解系
    (4)针对每个特征值下的基础解系,进行正交化。
    (5)对正交化后的向量单位化

    例子:已知这里写图片描述

    求出一正交矩阵 使 成对角形.
    解:先求出的 特征值.由这里写图片描述

    即得的特征值为 (三重), .
    其次,求属于1的特征向量.把 代入这里写图片描述
    (*)
    求得基础解系为

    把它们正交化,得这里写图片描述

    再单位化,得这里写图片描述
    这里写图片描述

    这是属于三重特征值 三个标准正交的特征向量.
    再求属于 的特征向量.用代入(*)式求得其基础解系为 .
    把它单位化,得.
    特征向量 构成的一组标准正交基,所求的正交矩阵为这里写图片描述
    .
    这里写图片描述
    .
    三、matlab实现过程
    (1)求特征多项式和特征值

    clc
    clear all
    A=[0 1 1 -1;1 0 -1 1 ;1 -1 0 1;-1 1 1 0]
    p=poly(A)
    % p = 1.0000 0 -6.0000 8.0000 -3.0000
    p1=poly2str(p,’x’)
    % p1 = x^4 - 6 x^2 + 8 x - 3
    p2=sym(‘x^4 - 6 x^2 + 8 x - 3’) %怎样引用前面的平p1
    s1=solve(p2) %查看 s1 =-3
    1
    1
    1
    (2)求1的特征向量
    B=1*eye(4,4)-A
    c=rref(B);

    % c =

    % 1 -1 -1 1
    % 0 0 0 0
    % 0 0 0 0
    % 0 0 0 0
    %相当于 x1-x2-x3+x4=0
    %4个未知数,一个方程,有三个自由变量,自行设置 x1=1 ,x2=1,x3=0,de x4=0
    x1=1 ,x2=0,x3=1,de x4=0
    x1=-1 ,x2=0,x3=0,de x4=1
    %得一个基础解系
    a1=[1 1 0 0];
    a2=[1 0 1 0];
    a3=[-1 0 0 1];
    %对上面的3个向量正交化
    b1=a1;
    b2=a2-a2.*b1/sqrt(b1.*b1);
    b3=a3-a3.*b1/sqrt(b1.*b1)-a3.*b2/sqrt(b2.*b2);
    format rat %分数显示
    jie=[b1;b2;b3]’

    %jie =

    1.0000    0.5000   -0.0000
    1.0000   -0.5000    1.0000
         0    0.5000    1.0000
         0   -0.5000    2.0000
    

    jie(abs(jie)<0.0001)=0;
    %单位化
    format short
    d1=jie(:,1)/norm(jie(:,1));
    d2=jie(:,2)/norm(jie(:,2));
    d3=jie(:,3)/norm(jie(:,3));

    format rat %分数显示

    D=[d1,d2,d3]
    format rat %分数显示
    D =

    0.7071    0.5000   -0.0000
    0.7071   -0.5000    0.4082
         0    0.5000    0.4082
         0   -0.5000    0.8165
    

    % D’*D

    ans =

    1.0000    0.0000    0.2887
    0.0000    1.0000   -0.4082
    0.2887   -0.4082    1.0000
    

    这时第1个列向量和第三个列向量内积不为0,有误差,难道前面的正交化过程有误?

    尝试改进一下
    b1=a1;
    b2=a2 -(a2*b1’/(b1*b1’))*b1;
    b3=a3-(a3*b1’/ (b1*b1’))*b1-(a3*b2’/ (b2*b2’))*b2;
    format rat %分数显示
    jie=[b1;b2;b3]’
    jie =

    1.0000    0.5000   -0.3333
    1.0000   -0.5000    0.3333
         0    1.0000    0.3333
         0         0    1.0000
    

    d1=jie(:,1)/norm(jie(:,1));
    d2=jie(:,2)/norm(jie(:,2));
    d3=jie(:,3)/norm(jie(:,3));
    D =

    0.7071    0.4082   -0.2887
    0.7071   -0.4082    0.2887
         0    0.8165    0.2887
         0         0    0.8660
    

    D’*D

    ans =

    1.0000         0         0
         0    1.0000   -0.0000
         0   -0.0000    1.0000
    

    (3)求-3的特征向量
    B2=(-3)*eye(4,4)-A
    C2=rref(B2)

    %C2 =

     1     0     0    -1
     0     1     0     1
     0     0     1     1
     0     0     0     0
    

    有1个自由变量,取x1=1 得x4=1;x2=-1;x3=-1;
    cc=[1 -1 -1 1]
    cc=cc/norm(cc);

    (4) T=[D,cc]
    (5) T=[D,cc’]

    T =

    0.7071 0.4082 -0.2887 0.5
    0.7071 -0.4082 0.2887 -0.5
    0 0.8165 0.2887 -0.5
    0 0 0.8660 0.5

    T’*A*T
    ans =

    1.0000         0         0         0
         0    1.0000   -0.0000         0
         0         0    1.0000    0.0000
         0         0         0   -3.0000
    

    三 使用matlab函数分解

    clc
    clear all
    A=[0 1 1 -1;1 0 -1 1 ;1 -1 0 1;-1 1 1 0]

    [U,S,V]=svd(A,0)
    U =

    0.5000         0    0.8660   -0.0000
    

    -0.5000 -0.0000 0.2887 0.8165
    -0.5000 0.7071 0.2887 -0.4082
    0.5000 0.7071 -0.2887 0.4082

    S =

    3.0000         0         0         0
         0    1.0000         0         0
         0         0    1.0000         0
         0         0         0    1.0000
    

    % 特征值前面是-3,在这是3;这个影响大不大?
    V =

    -0.5000 0 0.8660 0
    0.5000 0 0.2887 0.8165
    0.5000 0.7071 0.2887 -0.4082
    -0.5000 0.7071 -0.2887 0.4082

    [m,n] = size(A);
    if m > 1, s = diag(S);
    elseif m == 1, s = S(1);
    else s = 0;
    end
    tol = max(m,n) * max(s) * eps(class(A));
    r = sum(s > tol);
    Q = U(:,1:r);
    Q =

    0.5000         0    0.8660   -0.0000
    

    -0.5000 -0.0000 0.2887 0.8165
    -0.5000 0.7071 0.2887 -0.4082
    0.5000 0.7071 -0.2887 0.4082
    Q’*Q

    ans =

    1.0000         0   -0.0000   -0.0000
         0    1.0000         0   -0.0000
    

    -0.0000 0 1.0000 -0.0000
    -0.0000 -0.0000 -0.0000 1.0000
    U*S*V’

    ans =

    0.0000    1.0000    1.0000   -1.0000
    1.0000   -0.0000   -1.0000    1.0000
    1.0000   -1.0000   -0.0000    1.0000
    

    -1.0000 1.0000 1.0000 -0.0000
    U-Q

    ans =

     0     0     0     0
     0     0     0     0
     0     0     0     0
     0     0     0     0
    

    Q*S*Q’

    ans =

    1.5000   -0.5000   -0.5000    0.5000
    

    -0.5000 1.5000 0.5000 -0.5000
    -0.5000 0.5000 1.5000 -0.5000
    0.5000 -0.5000 -0.5000 1.5000

    Q*S*V’

    ans =

    0.0000    1.0000    1.0000   -1.0000
    1.0000   -0.0000   -1.0000    1.0000
    1.0000   -1.0000   -0.0000    1.0000
    

    -1.0000 1.0000 1.0000 -0.0000
    Q*S*V’= U*S*V’,需要注意的是,U和V虽然十分相似,但符号不同,所以U和V不能互相代替。

    展开全文
  • 矩阵对角化,SVD分解

    千次阅读 2019-09-20 12:18:39
    - [矩阵对角化](#矩阵对角化) - [SVD分解](#svd分解) - [参考链接](#参考链接) 矩阵对角化 矩阵的相似 设 A\boldsymbol{A}A、 B\boldsymbol{B}B 为两个nnn阶矩阵,若存在可逆矩阵 P\boldsymbol{P}P,使得...

    矩阵对角化

    矩阵的相似

    A \boldsymbol{A} A B \boldsymbol{B} B 为两个 n n n阶矩阵,若存在可逆矩阵 P \boldsymbol{P} P,使得
    P − 1 A P = B \boldsymbol{P}^{^{-1}}\boldsymbol{A}\boldsymbol{P}=\boldsymbol{B} P1AP=B
    则称 A \boldsymbol{A} A B \boldsymbol{B} B 相似。特别的,如果 B \boldsymbol{B} B 为对角形矩阵,则称 A \boldsymbol{A} A 可(相似)对角化

    n n n阶矩阵 A A A可对角化的充要条件: A \boldsymbol{A} A n n n个线性无关的特征向量 X 1 , X 2 , . . . X n \boldsymbol{X_{1}},\boldsymbol{X_{2}},...\boldsymbol{X_{n}} X1,X2,...Xn。具体的证明我们不在此展开,只做几点说明:

    1. n n n 阶矩阵 A \boldsymbol{A} A m m m 个不同特征值(方程 ∣ λ E − A ∣ = 0 \left | \lambda \boldsymbol{E} -\boldsymbol{A}\right |=0 λEA=0 m m m 个不同实根),则不同特征值对应的特征向量线性无关
    2. 存在 A \boldsymbol{A} A 属于某个特征值的线性无关特征向量
    3. P − 1 A P = d i a g ( λ 1 , λ 2 , . . . λ n ) \boldsymbol{P}^{^{-1}}\boldsymbol{A}\boldsymbol{P}=diag(\lambda _{1},\lambda _{2},...\lambda _{n}) P1AP=diag(λ1λ2...λn) 时, d i a g ( λ 1 , λ 2 , . . . λ n ) diag(\lambda _{1},\lambda _{2},...\lambda _{n}) diag(λ1λ2...λn) n n n个主对角元是 A \boldsymbol{A} A n n n个特征值(含重根); A \boldsymbol{A} A 分别属于 λ 1 , λ 2 , . . . λ n \lambda _{1},\lambda _{2},...\lambda _{n} λ1λ2...λn 的线性无关特征向量 X 1 , X 2 , . . . X n \boldsymbol{X_{1}},\boldsymbol{X_{2}},...\boldsymbol{X_{n}} X1,X2,...Xn 构成了可逆矩阵 P \boldsymbol{P} P 的列向量

    实对称矩阵的对角化

    考虑实对称矩阵的对角化,有如下结论:

    1. n n n阶实对称矩阵 A \boldsymbol{A} A 的特征值都是实数(证明思路:对表达式 A X = λ X \mathbf{AX=\lambda X} AX=λX 左乘复特征向量的共轭转置 X ˉ T \mathbf{\bar{X}^{T}} XˉT,推出 λ \lambda λ 为实数)
    2. 实对称矩阵 A \boldsymbol{A} A 不同特征值对应的特征向量正交(证明思路:列出 A \boldsymbol{A} A 两组不同的特征方程,分别左乘另一个复特征向量的共轭转置,两端取转置后方程相减)
    3. 属于 A \boldsymbol{A} A 的同一个特征值的一组线性无关特征向量不一定正交,但可用施密特正交方法将其正交化
    4. 一定存在正交矩阵 Q \mathbf{Q} Q (满足 Q − 1 = Q T \mathbf{Q}^{-1}=\mathbf{Q}^{T} Q1=QT),使得 Q − 1 A Q \boldsymbol{Q}^{^{-1}}\boldsymbol{A}\boldsymbol{Q} Q1AQ 为对角形矩阵
    5. n n n阶实对称矩阵 A \boldsymbol{A} A 存在 n n n个正交的单位特征向量

    SVD分解

    特征值分解只能用于可逆方阵,奇异值分解(SVD)适用于任意 m × n \mathit{m}\times\mathit{n} m×n 矩阵,定义如下:

    A \boldsymbol{A} A 是一个 m × n \mathit{m}\times\mathit{n} m×n 矩阵,则存在一个分解,使得
    A = U Σ V ∗ \boldsymbol{A}=\boldsymbol{U}\Sigma\boldsymbol{V}^{*} A=UΣV
    其中 U \boldsymbol{U} U m × m m\times m m×m 酉矩阵(满足 U − 1 = U ∗ \boldsymbol{U^{-1}}=\boldsymbol{U}^{*} U1=U), Σ \Sigma Σ m × n m\times n m×n 非负实对称矩阵, V ∗ \boldsymbol{V}^{*} V V \boldsymbol{V} V 的共轭转置,是 n × n n\times n n×n 酉矩阵.

    求解 U \boldsymbol{U} U, Σ \Sigma Σ, V \boldsymbol{V} V 矩阵

    给定一个 A m × n \boldsymbol{A_{m\times n}} Am×n 的奇异值分解,有:
    A ∗ A = V Σ ∗ U ∗ U Σ V ∗ = V ( Σ ∗ Σ ) V ∗ \boldsymbol{A^{*}A}=\boldsymbol{V}\Sigma^{*}\boldsymbol{U}^{*}\boldsymbol{U}\Sigma\boldsymbol{V}^{*}=\boldsymbol{V}(\Sigma^{*}\Sigma)\boldsymbol{V}^{*} AA=VΣUUΣV=V(ΣΣ)V
    A A ∗ = U Σ V ∗ V Σ ∗ U ∗ = U ( Σ Σ ∗ ) U ∗ \boldsymbol{AA^{*}}=\boldsymbol{U}\Sigma\boldsymbol{V}^{*}\boldsymbol{V}\Sigma^{*}\boldsymbol{U}^{*}=\boldsymbol{U}(\Sigma\Sigma^{*})\boldsymbol{U}^{*} AA=UΣVVΣU=U(ΣΣ)U
    关系式右边描述了关系式左边的特征值分解,于是:

    • A ∗ A \boldsymbol{A^{*}A} AA n n n个特征向量(右奇异向量)组成了 V \boldsymbol{V} V 的列向量
    • A A ∗ \boldsymbol{AA^{*}} AA m m m个特征向量(左奇异值向量)组成了 U \boldsymbol{U} U 的列向量
    • Σ \Sigma Σ 的非零对角元(非零奇异值)是 A ∗ A \boldsymbol{A^{*}A} AA A A ∗ \boldsymbol{AA^{*}} AA 的非零特征值(为啥相同?)的平方根,即 Σ = [ σ 1 0 0 0 0 σ 2 ⋯ 0 0 0 ⋱ σ r ⋮ ⋮ ⋮ ⋮ ] m × n \Sigma=\begin{bmatrix} \sigma_{1}& 0& 0& 0 \\ 0& \sigma_{2}& \cdots& 0 \\ 0& 0& \ddots& \sigma_{r} \\ \vdots& \vdots& \vdots& \vdots \end{bmatrix}_{m\times n} Σ=σ1000σ20000σrm×n,其中 r = r a n k ( A ) r=rank(\boldsymbol{A}) r=rank(A)(思考为什么?)且 m > r \mathit{m}>\mathit{r} m>r σ i = λ i ( i = 1 , 2 ⋯ r ) \sigma _{i}=\sqrt{\lambda _{i}}(i=1,2\cdots r) σi=λi (i=1,2r)

    补充1: A A T \boldsymbol{AA^{T}} AAT 性质

    • 对称性: ( A T A ) T = A A T (\boldsymbol{A^{T}A})^{T}=\boldsymbol{AA^{T}} (ATA)T=AAT
    • 半正定性:对任意非零向量 x n × 1 x_{n\times1} xn×1 ,有 x T ( A T A ) x = ( A x ) T ( A x ) ⩾ 0 \boldsymbol{x^{T}}(\boldsymbol{A^{T}A})\boldsymbol{x}=(\boldsymbol{Ax})^{T}(\boldsymbol{Ax})\geqslant 0 xT(ATA)x=(Ax)T(Ax)0

    补充2:奇异值分解 Vs.特征值分解
    SVD_EigenDecomposition

    补充3:正定和半正定矩阵的性质

    • 正定矩阵的行列式恒为正;
    • 实对称矩阵 A A A正定当且仅当 A A A与单位矩阵合同;
    • 对于 n n n阶实对称矩阵 A A A,下列条件是等价的:正定矩阵=一切主子式均为正=一切顺序主子式均为正=特征值均为正;
    • 对于 n n n阶实对称矩阵 A A A,下列条件是等价的:半正定矩阵=所有的主子式非负(顺序主子式非负并不能推出矩阵是半正定的)

    SVD分解的应用
    SVD-application

    参考链接

    1. 中文维基 奇异值分解
    2. 中文维基 可对角化矩阵
    3. 博客园 奇异值分解(SVD)原理与在降维中的应用
    4. 知乎 矩阵对角化与奇异值分解
    5. Markdown语言教程
      Markdown 插入链接
      Markdown 编辑器语法指南
      MarkDown 插入数学公式实验大集合
      如何在Markdown中写公式
    展开全文
  • 相似矩阵、矩阵的相似对角化

    万次阅读 多人点赞 2016-10-19 19:12:47
    特殊的,如果A∼Λ,Λ是角矩阵A \sim \Lambda, \Lambda 是角矩阵, 则称A可以相似对角化。Λ\Lambda是相似标准形。矩阵可相似对角化的充要条件 n阶矩阵A可对角化 ⟺\Longleftrightarrow A有n个线性无关的特征向

    相似矩阵的定义

    A,B都是n阶矩阵。若存在可逆矩阵P,使得 P1AP=B ,则称A相似于B,记作 AB
    特殊的,如果 AΛ,Λ , 则称A可以相似对角化。 Λ 是相似标准形。

    矩阵可相似对角化的充要条件

    • n阶矩阵A可对角化 A有n个线性无关的特征向量。

      注意这里说的不是A的秩为满,也不是 λEA 矩阵秩满时,可以得到A有n个线性无关的特征向量。而是方程 |λEA|=0 可以取得n个特征值。
      一个特征值下有多少无关的特征向量呢?需要代入方程 (λEA)x=0 计算。

    • 不相等的特征值对应的特征向量一定无关。而相同特征值下的特征向量不一定无关(相同特征值还有重数的概念)。即,若 λ1λ2, 则A的对应于 λ1 λ2 的特征向量线性无关。

      由此引出的推论是:若A有n个互不相同的特征值,那么就可以得出A有n个无关的特征向量。从而得出A可以相似对角化,且主对角线元素是n个特征值。

    如果,A有n个线性无关特征向量只有这一种情况的话,将会无聊得太多了。幸而实际上不是。同样的特征值也有可能得出多个无关向量。

    • λi 是n阶矩阵A的 ri 重特征值,则其对应的线性无关特征向量的个数小于等于 ri 个。

    推论:每一个 ri 重特征值对应的线性无关特征向量的个数等于该特征值的重数时,等价于n阶矩阵A可以相似对角化。

    综合上面可以看到,矩阵相似对角化的核心是可以得到矩阵A有n个线性无关的特征向量。已知A可以求出A的特征值,这些特征值不必各个不同,可以部分相同,相同的个数称之为对应的特征值的重数。再根据这个特征值求得的特征向量个数,二者比较,可以得出是不是有n个线性无关的特征向量。

    也就是说,充要条件的限制很大,或者说可选的范围很小。也因此,必要条件就很多。这也成为了解题的一大依据。

    矩阵相似的必要条件

    A simB=(1)|λEA|=|λEB|,(2)r(A)=r(B),(3)AB,(4)|A|=|B|=ni=1λi,(5)ni=1aii=ni=1bii=ni=1λi

    值得注意的是,当两个矩阵相似时,不要认为主对角线秩积等于特征值之积。。。

    初等行变换后,特征值一般会变化。这也是值得注意的点。

    基本上我们常常研究的秩,行列式,特征值,特征方程都相同,但也只是必要条件。

    展开全文
  • 实对称矩阵必可正交对角化证明

    万次阅读 2018-08-05 13:36:26
    n阶矩阵A可正交对角化的充分条件是A是实对称矩阵,即若A是实对称矩阵则A必可正交对角化。 首先,有以下定理: 若的特征值为,且,则存在正交矩阵Q,使A相似于如下三角矩阵: 证明如下(数学归纳法): 设n*n阶...
  • 相似对角化与二次型的标准化联系

    千次阅读 2019-09-27 16:39:29
    n元二次型化标准形,具体解题步骤: 1、写出二次型矩阵A 2、矩阵A的特征值(λ1,λ2,…,λn) 3、矩阵A的特征向量(α1,α2,…,αn) 4、改造特征向量(单位...相似对角化,具体解题步骤: 1、矩阵A的特...
  • 量子力学中的一项基本假定是代表力学量的算符是Hermite算符,由力学量算符的本征方程解出的全部本征值,就是相应力学量的...本文先从数学上严格证明了Hermite矩阵可以酉相似对角化,然后结合物理实例分析了其物理意义。
  • 鉴于此, 提出一种用于线性卷积混合盲分离的联合对角化方法, 将卷积混合模型变换为瞬时模型, 并变换后的模型应用联合对角化求取分离矩阵. 在求解过程中, 引入约束条件解的范围进行限定, 避免了奇异解的出现. ...
  • 线性代数笔记8:矩阵的对角化

    万次阅读 多人点赞 2018-04-02 21:33:36
    本文主要讲矩阵对角化的证明及应用。 矩阵对角化条件 定义一:若存在可逆矩阵SSS,使得S−1ASS−1ASS^{-1}AS为角矩阵,则称为矩阵AAA是可对角化的(diagonalized)。 设n×nn×nn\times n矩阵有nnn个线性...
  • 实对称矩阵相似对角化Matlab程序,用到的朋友可以下载看看。
  • 本微信图文从变换的角度解释了相似矩阵的对角化
  • Note:PCA主成分分析用到实对称阵的相似对角化。1.角阵概念2.矩阵与角阵相似的条件3.一般矩阵的相似对角化4.实对称矩阵的相似对角化5.协方差矩阵的相似对角化(end)...
  • 矩阵的对角化

    千次阅读 2015-03-29 10:16:53
    矩阵的对角化 讲解矩阵的对角化之前,先了解下相似矩阵。 相似矩阵的定义:A、B都是n阶矩阵,若存在可逆矩阵P,使得P-1AP = B,(注意全文中所有的P-1=P的逆矩阵)则定义矩阵B是矩阵A的相似矩阵或称矩阵A与矩阵B...
  • 实对称矩阵,对角化,有两篇论文,内含Matlab实现代码,在文章里的,可以直接写下来使用。测试过,还可以。
  • 矩阵A的所有特征值的和等于A的迹(A的主对角线元素之和)。2.矩阵A的所有特征值的积等于A的行列式。3.关于A的矩阵多项式f(A)的特征值为f(μ)。4.若A可逆,则A−1的特征值为1/μ。5.若A与B相似,则A与B有相同特征多项式...
  • 矩阵的对角化、SVD分解及应用矩阵的对角化、SVD分解及应用矩阵运算的总结矩阵对角化SVD分解张量(tensor)转置(transpose) 矩阵的对角化、SVD分解及应用 许多数学对象可以通过将它们分解成多个组成部分或者找到它们的...
  • matlab对角化

    千次阅读 2017-03-17 18:23:30
    A=[2 2 -2;2 5 -4;-2 -4 5] [V, D]= eig(A) D=inv(V)*A*V
  • python 对角化 特征值 特征向量

    千次阅读 2017-10-22 00:22:53
    python 对角化 特征值 特征向量
  • 判断一个矩阵是否可对角化

    万次阅读 2016-12-31 23:13:48
    原文:... 将矩阵A的特征多项式完全分解,出A的特征值及其重数 若k重特征值都有k个线性无关的特征向量,则A可对角化. 否则不能角化. 实对称矩阵总可对角化,且可正交对角化.
  • 矩阵的对角化(Diagonalizing a Matrix )

    万次阅读 2014-03-26 14:47:17
    1.对角化 我们假设一个n*n的矩阵有n个线性无关的特征向量x1,x2....,xn,所有的向量组成一个特征向量矩阵S,则为特征值矩阵Λ: 证明:根据特征值和特征向量的定义我们有: 我们把矩阵AS拆分成S乘以Λ:
  • Toeplitz 矩阵对角化

    千次阅读 2015-08-13 10:17:07
    Toeplitz 矩阵是一种比较特殊的矩阵:其中任何一条对角线的元素取相同的值,
  • 线性代数笔记(5):矩阵的对角化

    千次阅读 2009-09-23 13:05:00
    根据台湾交通大学开放课程线性代数(莊重 特聘教授主讲)之授课内容整理的线性代数笔记,本文主要涉及教材第五章的内容,讨论特征值和特征向量的定义、矩阵(或算子)对角化有关的一些结论
  • 实对称矩阵的对角化

    千次阅读 2019-09-04 18:09:33
    原来,实对称矩阵对角化是为解决解析几何中二次曲面是何类型而提出的,因为二次曲面的方程可以写成(x,y,z)A(xyz)(x,y,z)A\begin{pmatrix}x\\y\\z\end{pmatrix}(x,y,z)A⎝⎛​xyz​⎠⎞​的形式,而这里的A就是一个实...
  • 4.一定可以用正交矩阵相似对角化(满足的矩阵为正交阵),步骤如下 (1)A的特征值λ1、λ2、λ3 (2)特征向量α1、α2、α3 (3)改造特征向量 a. 如λi≠λj 只需要单位化 ...
  • 友矩阵是方阵的有理标准型中起着重要作用的一类矩阵、本文给出了将友矩阵对角化的变换矩阵的几种方法。
  • 线性代数导论22——对角化和A的幂

    千次阅读 2013-11-01 17:36:24
    第二十二课时:对角化和A的幂 Ax=λx,特征值、特征向量的应用以及为什么需要特征值和特征向量。 对角化 S-1AS=Λ 假设A有n个线性无关的特征向量(大前提),将他们按列组成矩阵S,S为特征向量矩阵,那么S-
  •  最终得到了S和一个以特征值为对角线的对角矩阵的乘积,这个对角矩阵就是特征值矩阵,用Λ表示:  没有人关心线性相关的特征向量,上式有意义的前提是S由n个线性无关的特征向量组成,这意味着S可逆,等式两侧...
  • 今天晚上王小民同学问了助教姐姐一个问题,为什么一个一般的矩阵对角化的时候,我们不用做正交单位化,实对称矩阵对角化的时候却要做呢?这是一个很好的问题,所以和大家分享一下。 最后的结论就是...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 94,202
精华内容 37,680
关键字:

如何求对角化