精华内容
下载资源
问答
  • 循环矩阵可对角化
    千次阅读
    2015-08-13 10:17:07

    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矩阵对角化了。

    参考

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

    更多相关内容
  • 循环矩阵傅里叶对角化

    千次阅读 2021-03-07 22:44:09
    All circulant matrices are made diagonal by the Discrete Fourier Transform (DFT)...任意循环矩阵可以被傅里叶变换矩阵对角化。 文献中,一般用如下方式表达这一概念: 其中XXX是循环矩阵,x^\hat{x}x^是原向量x

    转载自https://blog.csdn.net/shenxiaolu1984/article/details/50884830

    相关KCF跟踪算法讲解:

    https://blog.csdn.net/shenxiaolu1984/article/details/50905283
    https://www.cnblogs.com/YiXiaoZhou/p/5925019.html

    Matlab代码实现:
    https://blog.csdn.net/bitopyx/article/details/81948875?spm=1001.2014.3001.5502

    https://blog.csdn.net/weixin_38128100/article/details/95729653

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

    文献中,一般用如下方式表达这一概念:
    在这里插入图片描述
    其中 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^的元素。

    另一方面,如果一个矩阵能够表示成两个傅里叶矩阵夹一个对角阵的乘积形式,则它是一个循环矩阵。其生成向量是对角元素的傅里叶逆变换。
    在这里插入图片描述
    这个公式初看疑问很多,以下意义讨论。

    X X X是什么?

    X X X是由原向量 x x x生成的循环矩阵。以矩阵尺寸 K = 4 K=4 K=4为例。
    在这里插入图片描述

    F F F是什么?

    F F F是离散傅里叶矩阵(DFT matrix),可以用一个复数 w = e − 2 π i / K w=e^{-2\pi i/K} w=e2πi/K表示,其中 K K K为方阵 F F F的尺寸,以 K = 4 K=4 K=4为例。
    在这里插入图片描述
    w w w想象成一个角度为 2 π / K 2\pi /K 2π/K的向量,这个矩阵的每一行是这个向量不断旋转。从上到下,旋转速度越来越快。
    之所以称为DFT matrix,是因为一个信号的DFT变换可以用此矩阵的乘积获得:
    在这里插入图片描述
    反傅里叶变换也可以通过类似手段得到:
    在这里插入图片描述
    傅里叶矩阵有许多性质:

    • 是对称矩阵,观察 w w w的规律即可知;
    • 满足 F H F = F F H = I F^HF=FF^H=I FHF=FFH=I,也就是说它是个酉矩阵。
      注意: F F F是常数,可以提前计算好,和要处理的 x x 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变换。即傅里叶变换可以把循环矩阵对角化。

    怎么证明?

    可以用构造特征值和特征向量的方法证明(参看这篇论文(Gray, Robert M. Toeplitz and circulant matrices: A review. now publishers inc, 2006.)的3.1节)。此处简单描述。
    考察待证明等式的第k列:
    在这里插入图片描述
    其中, 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=[x^i,f_k] 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=[x,f_k^{-i}] lefti=[x,fki]。DFT矩阵列的移位可以通过数乘 w w w的幂实现: f k i = f 0 ⋅ w i k f_k^i=f_0\cdot w^{ik} fki=f0wik

    更多性质

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

    转置

    循环矩阵的转置也是一个循环矩阵(可以查看循环矩阵各元素排列证明),其特征值和原特征值共轭。
    在这里插入图片描述
    可以通过如下方式证明:
    在这里插入图片描述
    由于 F F F是对称酉矩阵,且已知 X X X是实矩阵:
    在这里插入图片描述
    如果原生成向量 x x x是对称向量(例如[1,2,3,4,3,2]),则其傅里叶变换为实数,则:
    在这里插入图片描述

    卷积

    循环矩阵乘向量等价于生成向量的逆序和该向量卷积,可进一步转化为傅里叶变换相乘。注意卷积本身即包含逆序操作,另外利用了信号与系统中经典的“时域卷积,频域相乘”。
    在这里插入图片描述
    其中 x ˉ \bar x xˉ表示把 x x x的元素倒序排列。星号表示共轭。

    相乘

    A , B A, B A,B为循环矩阵,其乘积的特征值等于特征值的乘积:
    在这里插入图片描述
    乘积也是循环矩阵,其生成向量是原生成向量对位相乘的傅立叶逆变换。

    相加

    和的特征值等于特征值的和。
    在这里插入图片描述
    和也是循环矩阵,其生成向量是原生成向量的和。

    求逆

    循环矩阵的逆,等价于将其特征值求逆。
    在这里插入图片描述
    对角阵求逆等价于对角元素求逆,以下证明:
    在这里插入图片描述
    逆也是循环矩阵。

    有什么用?

    该性质可以将循环矩阵的许多运算转换成更简单的运算。例如:
    在这里插入图片描述
    原始计算量:两个方阵相乘 ( O ( K 3 ) ) (O(K^3)) (O(K3))
    转化后的计算量:反向傅里叶 ( K l o g K ) + (K logK)+ (KlogK)+向量点乘 ( K ) (K) (K)
    CV的许多算法中,都利用了这些性质提高运算速度,例如2015年TPAMI的这篇高速跟踪KCF方法。

    二维情况

    以上探讨的都是原始信号为一维的情况,以下证明二维情况下的 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 = { w u i + v j } i j f_{uv}=\{w^{ui+vj}\}_{ij} fuv={wui+vj}ij
    在这里插入图片描述
    需要验证的共有 N × N N\times N N×N个等式,其中第uv个为:
    在这里插入图片描述
    其中, [ X , f u v ] [X,f_{uv}] [X,fuv]表示把 x u v x^{uv} xuv分别和 f u v f_{uv} fuv做点乘,结果矩阵元素求和。
    这个等式的第ij元素为:
    在这里插入图片描述
    再次利用两个性质:(1)点乘只和两个矩阵相对位移有关(2) f u v f_{uv} fuv的位移可以用乘 w w w幂实现:
    在这里插入图片描述

    代码

    以下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);
    
    展开全文
  • 在讨论今天的主题之前,我们先给出三类矩阵的定义,分别是相似矩阵、可逆矩阵对角矩阵。相似矩阵:在线性代数中,相似矩阵指的是存在相似关系的矩阵,设A、B为n阶矩阵,如果有n阶可逆矩阵P存在,使得P^(-1)AP=B。...

    在讨论今天的主题之前,我们先给出三类矩阵的定义,分别是相似矩阵、可逆矩阵、对角矩阵。

    相似矩阵:在线性代数中,相似矩阵指的是存在相似关系的矩阵,设A、B为n阶矩阵,如果有n阶可逆矩阵P存在,使得P^(-1)AP=B。

    可逆矩阵:存在n阶矩阵A和n阶矩阵B,使得矩阵A、B的乘积为单位矩阵,则称A为可逆矩阵,B为A的逆矩阵。

    对角矩阵:一个主对角线之外的元素都为0的矩阵。

    根据我的主题,大家也能够想到今天要谈的,便是关于相似矩阵中的可逆矩阵P能否对角化。

    相似矩阵不用多说,大家也清楚,证明两个矩阵相似,便是存在n阶可逆矩阵P,满足上面的定义。

    那么对于判断矩阵A与对角矩阵相似呢,我直接给出定理,这也是书本上提到的。

    n阶矩阵A与对角矩阵相似的充分必要条件是矩阵A有n个线性无关的特征向量。

    话不多说,接下来就给出一道实际的例题,来让大家详细了解一下:

    如图所示,这道例题便是告诉我们两个矩阵相似,其中各个矩阵之中都有未知数,让我们通过相似矩阵的性质来求出未知数的值。

    这里笔者当时在做的时候,有个点没有注意到,那便是相似矩阵两者的迹数相等,也就是主对角线上所有元素之和相等,导致我没有列出第一个式子,至于第二个式子,大家也都知道,就是行列式的值相等。

    这是第二小题的做法,它的目的是让我们求出可逆矩阵P,满足P^(-1)AP是对角矩阵,对于这类题型而言,正如图中所说,是有如下步骤的:

    1、求出全部的特征值,这里因为矩阵A和矩阵B相似,所以求矩阵B的特征值更好求,得到1,1,5。

    2、然后对每一个特征值求特征向量,写出基础解系。

    3、然后代入到可逆矩阵P中,算出答案。

    最后总结一下,对于求相似矩阵包含的未知数而言,最基本最重要的就是记住相似矩阵的性质,而对于求可逆矩阵P而言,最重要的就是知道解题步骤,清楚特征值特征向量该如何使用。

    展开全文
  • 循环矩阵的傅里叶对角化

    千次阅读 2019-10-13 22:15:29
    文章类容根据《Matrix Analysis and Applied Linear Alebra》第5.8章节内容翻译。

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

    展开全文
  • 通过引入循环矩阵自身所具有的特性,研究了相似族矩阵的对角化问题,给出了相似族矩阵可对角化的一个条件。
  • r-循环矩阵与矩阵的对角化 希望又需要的人有帮助
  • 对于矩阵中一类重要的矩阵循环矩阵,从定义出发研究了它的各种性质,并利用矩阵对角化的方法给出了循环矩阵的逆矩阵和行列式的表达式。然后讨论了推广的循环矩阵,即准循环矩阵和广义循环矩阵,利用类似方法,也给出了...
  • 利用实循环矩阵与实斜循环矩阵可进行酉对角化的结论,研究g斜实循环矩阵的酉对角化,并给出g斜实循环矩阵的酉对角化的谱分解结果.
  • matlab循环矩阵

    千次阅读 2021-04-20 01:17:59
    clear; h = [10 9 8 7 6 5 4 3 2 1]; size=length(h); t=zeros(1,size); t(1)=h(1); t(1,2:size)=h(size:-1:2); H=toeplitz(h,t) 这个也ok: clc;clear;... 对角化: [V, D]= eig(newh) D=inv(V)*newh*V
  • latex对角矩阵diag

    2021-04-21 18:30:50
    对角阵在实际上的应用特别广泛,对角阵解决现实问题上很方便,通过对角矩阵可以最简单...Gerschgorin 圆盘定理在严格对角占优矩阵中的应用【摘要】 利用 Gerschgorin 圆盘...diagonlly dominant matrice;eigenvalue 1 ...
  • 刚拿到这道题,可能还有不少的小伙伴们不知道3*3主对角...# 求3*3矩阵对角线元素之和if __name__ == "__main__": # 编写一个程序的入口a = [] # 创建一个空列表sum = 0 # 初始sum值for i in range(3): # 创建一...
  • 高效且紧凑的代码,用于在不使用 for 循环的情况下获取 2D 矩阵中每个对角线(或反对角线)的平均值。 适用于大型矩阵,尤其适用于高矩阵或宽矩阵。 请注意,使用 diag() 函数的 for 循环实现可能更快,并且在应用...
  • 循环矩阵

    千次阅读 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_...
  • 判断 矩阵对角线元素相等

    千次阅读 2021-03-05 17:54:54
    如该矩阵对角线上的元素相等,则输出 True,否则输出 False 下面上代码 def is_toeplitz_matrix(matrix): line_nums = len(matrix) per_line_nums = len(matrix[0]) col = 0 while col < per_line_nums -1...
  • 在Matlab中不用eig()命令求方阵的特征值和特征向量矩阵,并判断其是否可以对角化 #本文仅针对标题所示问题的代码解答,若相关概念不熟,请去资料。 #不要问我为什么放着好好的eig()命令不用,反而去写一堆代码。这得...
  • 循环矩阵的性质及其应用

    千次阅读 2019-10-03 23:49:53
    $\S 1$ 循环矩阵的定义及多项式表示 设 $K$ 为数域. 任取 $K$ 中 $n$ 个数 $a_1,a_2,\cdots,a_n$,下列矩阵称为 $K$ 上的 $n$ 阶循环矩阵: $$A=\begin{pmatrix}a_1 & a_2 & a_3 & \cdots & a_n \\ ...
  • 相关滤波、KCF、循环对角化

    千次阅读 2017-06-27 17:25:03
    循环矩阵对角化及其性质在后面有简单介绍。 为化简计算,将输入X表示为循环矩阵的形式,则 X H X X^HX 的特征值为 x ^ ⨀ x ^ ∗ \hat{x}\bigodot\hat{x}^* , I 本身就是一个循环矩阵,其生成向量记为 δ \...
  • 求一个3×3的整数矩阵对角线之和

    千次阅读 多人点赞 2021-10-26 23:53:04
    本关任务:求一个3×3的整数矩阵对角线之和,如如下矩阵: 1 2 3 4 5 6 7 8 9 对角线元素之和为: 1+5+9+3+5+7=30 相关知识 为了完成本关任务,你需要掌握: 1.二维数组的定义; 2.二维数组的初始; 3.二维...
  • 循环矩阵求特征值的方法

    千次阅读 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...
  • 用数学归纳法证明了n1n2…nk阶(n1,n2,…,nk)型k重循环矩阵可以酉对角化,并给出了一种仅用其第一行的元素就可以判断其非异性的简便方法。
  • Python二维数组实现求出3*3矩阵对角线元素的和示例题目:求一个3*3矩阵对角线元素之和。程序分析:利用双重for循环控制输入二维数组,再将a[i][i]累加后输出。def two_dimensionalArray(self):'二维数组实现求三阶...
  • 基于3*3矩阵对角线之和,我写出求n*n矩阵对角线之和的方法。 这个n<11是我做的题目,你们可以改成其他数。 #include<stdio.h> int main() { int a[10][10]; //这里先定义数组 int i,k,sum,n; //i和k...
  • 针对校验矩阵形如准循环对角阵的结构LDPC码,对比研究了两类高效的编码算法:矩阵分解编码算法和分项累加递归编码算法,证明了两类算法从实现角度是等价的,但分项累加递归编码算法推导更为直观,且便于硬件并行...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 34,358
精华内容 13,743
关键字:

循环矩阵可对角化

友情链接: ZhuzhouDSP2812.rar