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

    万次阅读 多人点赞 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)=Fdiag(x^)FHX=C(x)=F \cdot diag(\hat{x}) \cdot F^H

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

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

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

    XX是什么?

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

    X=C(x)=[x1x2x3x4x4x1x2x3x3x4x1x2x2x3x4x1]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}

    FF 是什么?

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

    F=1K[11111ωω2ω31ω2ω4ω61ω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}

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

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

    x^=DFT(x)=KFx\hat{x}=DFT(x)=\sqrt{K}\cdot F \cdot x

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

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

    傅里叶矩阵有许多性质:

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

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

    对角化怎么理解?

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

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

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

    怎么证明?

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

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

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

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

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

    f1ω2=[1,ω,ω2]ω2=[ω2,ω3,ω4]=[ω2,1,ω]=f12f_1\cdot \omega^2 =[1,\omega,\omega^2]\cdot \omega^2 = [\omega^2, \omega^3,\omega^4] = [\omega^2, 1, \omega]=f_1^{-2}

    于是有:
    lefti=[x,fkωik]=[x,fk]ωikleft_i= \left [x, f_k \cdot \omega^{ik}\right ]=\left [x, f_k\right ] \cdot \omega^{ik}

    右边的$\hat x = F\cdot x ,考虑到Fkk的第k行和第k列相同,\hat x_k=[f_k,x]。另外f_ki的第i个元素为\omega^{ik}$:
    righti=x^kfki=[fk,x]ωkiright_i = \hat x_k\cdot f_{ki}=[f_k^*,x]\cdot \omega^{ki}

    对任意k列的第i个元素有:lefti=rightileft_i=right_i

    更多性质

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

    转置

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

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

    卷积

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

    F(Xy)=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)
    其中xˉ\bar x表示把xx的元素倒序排列。星号表示共轭。

    相乘

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

    AB=Fdiag(a^)FHFdiag(b^)FHAB = F\cdot diag(\hat a) \cdot F^H \cdot F \cdot diag(\hat b) \cdot F^H

    =Fdiag(a^)diag(b^)FH=Fdiag(a^b^)FH= F\cdot diag(\hat a) \cdot diag(\hat b) \cdot F^H=F\cdot diag(\hat a \odot \hat b) \cdot F^H

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

    相加

    和的特征值等于特征值的和:
    A+B=Fdiag(a^)FH+Fdiag(b^)FH=Fdiag(a^+b^)FHA+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

    =C(F1(a^+b^))=C(F1(a^)+F1(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)
    和也是循环矩阵,其生成向量是原生成向量的和。

    求逆

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

    =Fdiag(x^)1diag(x^)FH=FFH=I=F\cdot diag(\hat{x})^{-1}\cdot diag(\hat{x}) \cdot F^H=F\cdot F^H=I

    逆也是循环矩阵

    有什么用?

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

    XHX=Fdiag(x^x^)FH=C(F1(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)

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

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

    二维情况

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

    xx是二维生成矩阵,尺寸N×NN\times N
    XX是一个N2×N2N^2\times N^2的分块循环矩阵,其uv块记为xuvx^{uv},表示xx下移u行,右移v列。
    FFN2×N2N^2\times N^2的二维DFT矩阵,其第uv块记为fuv={ωui+vj}ijf_{uv}=\left\{ \omega^{ui+vj} \right\} _{ij}

    举例:N=3 f01=[1ωω21ωω21ωω2],f11=[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}\\

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

    再次利用两个性质:1) 点乘只和两个矩阵相对位移有关,2) fuvf_{uv}的位移可以用乘ω\omega幂实现:
    leftij=[x,fuvij]=[x,fuv]ωui+vj=x^uvωui+vj=rightijleft_{ij}=[x,f_{uv}^{-i-j}]=[x,f_{uv}]\cdot \omega^{ui+vj}=\hat x_{uv} \cdot \omega^{ui+vj}=right_{ij}

    代码

    以下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. ↩︎

    展开全文
  • 文章类容根据《Matrix Analysis and Applied Linear Alebra》第5.8章节内容翻译。

    文章类容根据《Matrix Analysis and Applied Linear Alebra》第5.8章节内容翻译。

    展开全文
  • Toeplitz 矩阵对角化

    千次阅读 2015-08-13 10:17:07
    Toeplitz 矩阵是一种比较特殊的矩阵:其中任何一条对角线的元素取相同的值,

    Toeplitz 矩阵是一种比较特殊的矩阵:其中任何一条对角线的元素取相同的值,即

    An=a0a1a2ana1a0a1an1a2a1a0a1anan+1a1a0

    这里不再展开证明。
    Toeplitz 矩阵可以被Fourier矩阵对角化,即有
    An=FHnΛFn

    F的元素为
    [Fn]ij=1nej2πik/n,0<=i,j<=n1

    Λ是n阶对角矩阵。

    生成一个循环矩阵

     T = toeplitz([2 1 0 0 1]);

    An=2100112100012100012110012

    生成Fourier矩阵

    F = dftmtx(5)

    F=1.00001.00001.00001.00001.00001.00000.30900.9511i0.80900.5878i0.8090+0.5878i0.3090+0.9511i1.00000.80900.5878i0.3090+0.9511i0.30900.9511i0.8090+0.5878i1.00000.8090+0.5878i0.30900.9511i0.3090+0.9511i0.80900.5878i1.00000.3090+0.9511i0.8090+0.5878i0.80900.5878i0.30900.9511i

    对角化

    Λ=FTconj(F)/5;

    Λ=4.0000000000.0000i2.6180+0.0000i0.0000+0.0000i0.00000.0000i0.00000.0000i00.00000.38200.00000.000000.00000.00000.38200.00000+0.0000i0.0000+0.0000i0.0000+0.0000i0.00000.0000i2.61800.0000i

    对角线上的元素便是Toeplitz 矩阵的特征值。
    其实也可以用矩阵An的第一列变换得到
    fft([2 1 0 0 1])

    ans=[4.00002.61800.38200.38202.6180]

    又或者这样得到
    F*[2 1 0 0 1]'

    ans=4.00002.61800.38200.38202.6180

    另一个角度去理解频率域

    空间域,两个序列的x,y卷积,等于其中一个序列排成的Toeplitz矩阵乘以另一个序列,即Toep(x)y
    空间域卷积的结果,等于两个序列各自的傅里叶变换XY之积,即

    Toep(x)y=F1Diag(Fx)Fy

    Toep(x)=F1Diag(X)F

    FToep(x)F1=Diag(X)

    这里用Diag(X)表示以向量X的元素为对角元的对角矩阵,Toep(x)表示用向量x的元素排成的Toeplitz矩阵。即Fourier矩阵将Toeplitz矩阵对角化了。

    参考

    知乎,图像处理中,空间域的卷积相当于频率域的乘积,从矩阵分析角度如何理解?

    展开全文
  • 实对称矩阵的PPP除了满足可逆之外,还是正交矩阵 特征值篇4——实对称矩阵的特殊性 正规矩阵的PPP除了满足可逆之外,还是酉矩阵 酉相似于对角阵的充要条件

    下面给出矩阵可相似对角化的充要条件:
    在这里插入图片描述
    在这里插入图片描述

    摘自 Linear Algebra and its applications David C. Lay
    Chapter 5.3 , page282

    矩阵相似对角化示例1
    在这里插入图片描述
    在这里插入图片描述
    矩阵相似对角化示例2
    在这里插入图片描述

    实对称矩阵的PP除了满足可逆之外,还是正交矩阵
    特征值篇4——实对称矩阵的特殊性

    正规矩阵的PP除了满足可逆之外,还是酉矩阵
    酉相似于对角阵的充要条件

    展开全文
  • 矩阵对角化对有什么作用(1)

    千次阅读 2019-12-20 14:51:16
    1可以从不同角度(简单角度)去描述复杂问题 2.计算
  • 循环矩阵

    千次阅读 2016-12-05 22:46:06
    今天讲讲线性代数中的一类特殊的矩阵———循环矩阵。形如:∥∥∥∥∥∥∥a1anan−1⋯a2a2a1an⋯a3a3a2a31⋯a4⋯⋯⋯⋯⋯anan−1an−2⋯a1∥∥∥∥∥∥∥\begin{Vmatrix} a_1&a_2&a_3 &\cdots &a_n \\ a_n&a_1&a_...
  • 基于Matlab的实对称矩阵对角化

    千次阅读 2013-06-18 20:16:30
    假设两个实对称矩阵A和B,如果存在一个可逆的矩阵X, XAX'=B,已知A和B,知道怎么用matlab求X? 本例中数据如下: A=[0.287402 0 0  0 0.483209 0  0 0 0.000025]; B=[0.287402 -0.028039 -0.0000727  -0....
  • matlab循环矩阵

    千次阅读 2017-03-17 18:45:19
    matlab循环矩阵
  • 矩阵按照对角线的数据累加,并且把结果的一边转换为一个三角形矩阵,在主程序调用怎么实现?
  • 相关滤波、KCF、循环对角化

    千次阅读 2017-06-27 17:25:03
    循环矩阵对角化及其性质在后面有简单介绍。 为化简计算,将输入X表示为循环矩阵的形式,则 X H X X^HX 的特征值为 x ^ ⨀ x ^ ∗ \hat{x}\bigodot\hat{x}^* , I 本身就是一个循环矩阵,其生成向量记为 δ \...
  • public class DoubleArray { public static void main(String args[]) { int a[][] = new int[6][6]; //创建矩阵 for(int i = 0 ; i <= 5 ;i++) { //给矩阵元素赋值 fo...
  • matlab 分块 矩阵 对角 合并

    万次阅读 2016-09-29 10:27:13
    引用:http://www.ilovematlab.cn/thread-74502-1-1.html 如:A=[ 1 2 3  2 3 4]  B=[1 2  3 4 ] 得到一个C=[A 0  0 B]; 在matlab中可以使用blkdiag命令 C = blkd
  • 在Matlab中不用eig()命令求方阵的特征值和特征向量矩阵,并判断其是否可以对角化 #本文仅针对标题所示问题的代码解答,若相关概念不熟,请去资料。 #不要问我为什么放着好好的eig()命令不用,反而去写一堆代码。这得...
  • 循环矩阵充分利用循环矩阵及其特性的是核相关滤波跟踪算法的另一个重要特征,它不仅涉及到目标采样,而且巧妙的将目标特征的频域空间与岭回归相结合,实现了目标特征的快速学习与检测。首先考虑一维样本的情况,设x=...
  • 循环矩阵求特征值的方法

    千次阅读 2020-02-27 17:56:48
    循环矩阵 根据https://max.book118.com/html/2016/0519/43353557.shtm整理修订 1.循环矩阵的定义 定义1 数域P\mathbb{P}P上的n×nn \times nn×n矩阵 Cn=circ(c0,c1,⋯ ,cn−1)=(c0c1c2⋯cn−1cn−1cn−1c0c1⋯cn...
  • 文章目录一、三对角方程数值解(Thomas algorithm或称“追赶法”)二、循环对角方程数值解(Sherman-Morrison formula)三、参考文献 一、三对角方程数值解(Thomas algorithm或称“追赶法”) %{ Function: solve_...
  • // 利用数组输出如下图所示的3*3矩阵,并求该矩阵对角线元素之和 double arr[][] ={{3,5,2.5},{4,7,6},{8,9,10}}; //遍历二维数组 for(int i=0;i<arr.length;i++){//遍历每个元素里面的数组 for(int...
  • 最常见的循环莫过于对矩阵中的每一个元素进行操作,对于编程思维还在C语言或者C++,JAVA的人来说,第一反应就是两层循环,先来个 “for i=1:m”对矩阵的行进行循环,再来个“for j=1:n”对矩阵的列进行循环。...
  • 矩阵论】矩阵的相似标准型(3)

    千次阅读 2020-10-30 15:11:21
    矩阵对角化引入探讨线性变换的对角化问题。(定义、等价命题和定理)
  • Julia 构建对角矩阵 diag matrix

    千次阅读 2019-08-27 07:40:11
    注意,julia中没有diag函数,如果想要定义4*4的对角矩阵,可以使用下面方法: 1. 使用Matrix函数 using LinearAlgebra Matrix{Float64}(I,4,4) 注意,Matrix{Float64}(I,4,4)中是字母I,而不是数字1 ...
  • python 对角化 特征值 特征向量

    千次阅读 2017-10-22 00:22:53
    python 对角化 特征值 特征向量
  • 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
  • 编程-从矩阵左上走到右下

    千次阅读 2016-09-01 22:41:05
    编写一个算法,在非负矩阵中,从左上走到右下,每次只能向左或向下移动一格,输出走过的路径节点坐标和最小权值。 方法:动态规划法 状态转移方程stat[i][j] = min{stat[i-1][j], stat[i][j-1]}。 逻辑:目的...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 27,499
精华内容 10,999
关键字:

循环矩阵可对角化