文章目录

1. 大纲

  • 循环矩阵在机器学习，图像处理中的应用
  • 循环卷积矩阵的特征值，特征向量，卷积规则
  • 循环卷积矩阵多项式表达： C = c 0 I + c 1 P + c 2 P 2 + ⋯ + c n − 1 P n − 1 C=c_0 I+c_1P+c_2P^2+\cdots+c_{n-1}P^{n-1} C=c0​I+c1​P+c2​P2+⋯+cn−1​Pn−1
  • 离散傅里叶DFT介绍

2. 循环矩阵

2.1 移位矩阵P

我们定义一个移位矩阵P 表示如下:
P = [ 0 1 0 0 0 0 1 0 0 0 0 1 1 0 0 0 ] ; P x = [ 0 1 0 0 0 0 1 0 0 0 0 1 1 0 0 0 ] [ x 1 x 2 x 3 x 4 ] = [ x 2 x 3 x 4 x 1 ] ; \begin{equation} P=\begin{bmatrix} 0&1&0&0\\\\ 0&0&1&0\\\\ 0&0&0&1\\\\ 1&0&0&0 \end{bmatrix};Px=\begin{bmatrix} 0&1&0&0\\\\ 0&0&1&0\\\\ 0&0&0&1\\\\ 1&0&0&0 \end{bmatrix}\begin{bmatrix} x_1\\\\ x_2\\\\ x_3\\\\ x_4 \end{bmatrix}=\begin{bmatrix} x_2\\\\ x_3\\\\ x_4\\\\ x_1\end{bmatrix}; \end{equation} P= ​0001​1000​0100​0010​ ​;Px= ​0001​1000​0100​0010​ ​ ​x1​x2​x3​x4​​ ​= ​x2​x3​x4​x1​​ ​;​​

  • 那么我们可以将一个循环卷积矩阵C 分解为移位矩阵P的多项式之和：
    在这里插入图片描述
  • numpy 代码实现：
import numpy as np
from scipy.linalg import circulant

np.set_printoptions(suppress=True, precision=3)
np.random.seed(123435)


class PermutationMatrix(object):
    def __init__(self, in_vector):
        self.in_vector = in_vector
        self.vector_size = np.size(self.in_vector)
        self.vector_size_1 = self.vector_size + 1
        self.p_matrix = np.zeros((self.vector_size, self.vector_size))

    def get_p_matrix(self):
        p_vector = np.arange(1, self.vector_size_1) % self.vector_size
        p_matrix = np.eye(len(p_vector))[p_vector]
        p_temp = np.diag(np.ones(self.vector_size))
        result = np.zeros_like(p_matrix)
        for i in range(self.vector_size):
            result += p_temp * self.in_vector[i]
            p_new = p_matrix @ p_temp
            print(f"p_new[{i}]=\n{p_new}")
            p_temp = p_new
        result = result.T
        print(f"result=\n{result}")
        print(f"vector_size={self.vector_size}")
        print(f"p_vector={p_vector}")
        print(f"p_matrix=\n{p_matrix}")
        self.p_matrix = p_matrix
        return self.p_matrix


class CirculantMatrix(object):
    def __init__(self, in_vector):
        self.in_vector = in_vector
        self.vector_size = np.size(self.in_vector)
        self.vector_plus1 = self.vector_size + 1
        self.vector_minus1 = self.vector_size - 1
        self.p_matrix = np.zeros((self.vector_size, self.vector_size))
        self.circulant_matrix = np.zeros_like(self.p_matrix)

    def get_p_matrix(self):
        p_vector = np.arange(1, self.vector_plus1) % self.vector_size
        p_matrix = np.eye(len(p_vector))[p_vector]
        self.p_matrix = p_matrix
        return self.p_matrix

    def get_circulant(self):
        p_temp = np.diag(np.ones(self.vector_size))
        result = np.zeros_like(self.p_matrix)
        my_p_matrix = self.get_p_matrix()
        for i in range(self.vector_size):
            result += p_temp * self.in_vector[i]
            p_new = my_p_matrix @ p_temp
            p_temp = p_new
        result = result.T
        self.circulant_matrix = result
        scipy_ciculant = circulant(self.in_vector)
        check_result = np.allclose(self.circulant_matrix, scipy_ciculant)
        print(f"*" * 50)
        print(f"vector={self.in_vector}")
        print(f"check_result={check_result}")
        print(f"circulant=\n{self.circulant_matrix}")
        print(f"scipy_ciculant=\n{scipy_ciculant}")
        print(f"*" * 50)
        return self.circulant_matrix


if __name__ == "__main__":
    my_code = 0
    for i in range(10):
        my_test = np.random.choice(20, 4, replace=False) + 1
        my_circulant = CirculantMatrix(my_test)
        my_circulant.get_circulant()
  • 结果：
**************************************************
vector=[18  2  1 17]
check_result=True
circulant=
[[18. 17.  1.  2.]
 [ 2. 18. 17.  1.]
 [ 1.  2. 18. 17.]
 [17.  1.  2. 18.]]
scipy_ciculant=
[[18 17  1  2]
 [ 2 18 17  1]
 [ 1  2 18 17]
 [17  1  2 18]]
**************************************************
**************************************************
vector=[15 16 12  6]
check_result=True
circulant=
[[15.  6. 12. 16.]
 [16. 15.  6. 12.]
 [12. 16. 15.  6.]
 [ 6. 12. 16. 15.]]
scipy_ciculant=
[[15  6 12 16]
 [16 15  6 12]
 [12 16 15  6]
 [ 6 12 16 15]]
**************************************************
**************************************************
vector=[12  2 10  4]
check_result=True
circulant=
[[12.  4. 10.  2.]
 [ 2. 12.  4. 10.]
 [10.  2. 12.  4.]
 [ 4. 10.  2. 12.]]
scipy_ciculant=
[[12  4 10  2]
 [ 2 12  4 10]
 [10  2 12  4]
 [ 4 10  2 12]]
**************************************************
**************************************************
vector=[5 6 4 7]
check_result=True
circulant=
[[5. 7. 4. 6.]
 [6. 5. 7. 4.]
 [4. 6. 5. 7.]
 [7. 4. 6. 5.]]
scipy_ciculant=
[[5 7 4 6]
 [6 5 7 4]
 [4 6 5 7]
 [7 4 6 5]]
**************************************************
**************************************************
vector=[ 6  9 10 16]
check_result=True
circulant=
[[ 6. 16. 10.  9.]
 [ 9.  6. 16. 10.]
 [10.  9.  6. 16.]
 [16. 10.  9.  6.]]
scipy_ciculant=
[[ 6 16 10  9]
 [ 9  6 16 10]
 [10  9  6 16]
 [16 10  9  6]]
**************************************************
**************************************************
vector=[ 4 16 20  7]
check_result=True
circulant=
[[ 4.  7. 20. 16.]
 [16.  4.  7. 20.]
 [20. 16.  4.  7.]
 [ 7. 20. 16.  4.]]
scipy_ciculant=
[[ 4  7 20 16]
 [16  4  7 20]
 [20 16  4  7]
 [ 7 20 16  4]]
**************************************************
**************************************************
vector=[13 18  2 19]
check_result=True
circulant=
[[13. 19.  2. 18.]
 [18. 13. 19.  2.]
 [ 2. 18. 13. 19.]
 [19.  2. 18. 13.]]
scipy_ciculant=
[[13 19  2 18]
 [18 13 19  2]
 [ 2 18 13 19]
 [19  2 18 13]]
**************************************************
**************************************************
vector=[ 5 11 10  3]
check_result=True
circulant=
[[ 5.  3. 10. 11.]
 [11.  5.  3. 10.]
 [10. 11.  5.  3.]
 [ 3. 10. 11.  5.]]
scipy_ciculant=
[[ 5  3 10 11]
 [11  5  3 10]
 [10 11  5  3]
 [ 3 10 11  5]]
**************************************************
**************************************************
vector=[13  1 18  8]
check_result=True
circulant=
[[13.  8. 18.  1.]
 [ 1. 13.  8. 18.]
 [18.  1. 13.  8.]
 [ 8. 18.  1. 13.]]
scipy_ciculant=
[[13  8 18  1]
 [ 1 13  8 18]
 [18  1 13  8]
 [ 8 18  1 13]]
**************************************************
**************************************************
vector=[20 11  5 19]
check_result=True
circulant=
[[20. 19.  5. 11.]
 [11. 20. 19.  5.]
 [ 5. 11. 20. 19.]
 [19.  5. 11. 20.]]
scipy_ciculant=
[[20 19  5 11]
 [11 20 19  5]
 [ 5 11 20 19]
 [19  5 11 20]]
**************************************************

2.2 P的特征值和特征向量

我们根据P来定义其特征值和特征向量可得：
P x = λ x → x 2 = λ x 1 ; x 3 = λ x 2 ; x 4 = λ x 3 ; x 1 = λ x 4 ; \begin{equation} Px=\lambda x\to x_2=\lambda x_1; x_3=\lambda x_2; x_4=\lambda x_3; x_1=\lambda x_4; \end{equation} Px=λx→x2​=λx1​;x3​=λx2​;x4​=λx3​;x1​=λx4​;​​

  • 整理可得：
    x 1 = λ 4 x 1 → ( 1 − λ 4 ) x 1 = 0 → λ 0 = 1 , λ 1 = i , λ 2 = − 1 , λ 3 = − i \begin{equation} x_1=\lambda ^4x_1\to (1-\lambda^4)x_1=0\to \lambda_0=1,\lambda_1=i,\lambda_2=-1,\lambda_3=-i \end{equation} x1​=λ4x1​→(1−λ4)x1​=0→λ0​=1,λ1​=i,λ2​=−1,λ3​=−i​​
  • 也就是说P的根为 Z N = 1 Z^N=1 ZN=1的根，这里是N=4,所以有4个根；
    在这里插入图片描述

2.3 循环卷积矩阵

我们有一个循环卷积矩阵C，n行n列，因为矩阵C的特殊性，其斜线上的元素相等，所以可得：
C = [ c 0 c 1 c 2 ⋯ c n − 1 c n − 1 c 0 c 1 ⋯ c n − 2 ⋮ ⋱ ⋱ ⋱ ⋮ c 1 c 2 c 3 ⋯ c 0 ] ; \begin{equation} C=\begin{bmatrix} c_0&c_1&c_2&\cdots&c_{n-1}\\\\ c_{n-1}&c_0&c_1&\cdots&c_{n-2}\\\\ \vdots&\ddots&\ddots&\ddots&\vdots\\\\ c_{1}&c_2&c_3&\cdots&c_{0} \end{bmatrix}; \end{equation} C= ​c0​cn−1​⋮c1​​c1​c0​⋱c2​​c2​c1​⋱c3​​⋯⋯⋱⋯​cn−1​cn−2​⋮c0​​ ​;​​

  • 那么可以将上述循环矩阵C用移位矩阵P进行展开可得如下：
    C = c 0 I + c 1 P + c 2 P 2 + ⋯ + c n − 1 P n − 1 \begin{equation}C=c_0 I+c_1P+c_2P^2+\cdots+c_{n-1}P^{n-1}\end{equation} C=c0​I+c1​P+c2​P2+⋯+cn−1​Pn−1​​

2.4 循环卷积计算

假设我们有一个序列 x 1 ( n ) = { 1 , 2 , 3 } , x 2 ( n ) = { 5 , 0 , 4 } x_1(n)=\{1,2,3\},x_2(n)=\{5,0,4\} x1​(n)={1,2,3},x2​(n)={5,0,4},需要对其进行循环卷积计算，根据数字信号分析中可得：
x 1 ( n ) L ◯ x 2 ( n ) = [ ∑ m = 0 L − 1 x 1 ( m ) x 2 ( ( n − m ) ) L ] R L ( n ) \begin{equation} x_1(n)\textcircled{L} x_2(n)=[\sum_{m=0}^{L-1}x_1(m)x_2((n-m))_L]R_L(n) \end{equation} x1​(n)L◯x2​(n)=[m=0∑L−1​x1​(m)x2​((n−m))L​]RL​(n)​​

  • 转换成循环卷积如下：
    [ 5 4 0 0 5 4 4 0 5 ] [ 1 2 3 ] = [ 13 22 19 ] ; \begin{equation} \begin{bmatrix} 5&4&0\\\\ 0&5&4\\\\ 4&0&5 \end{bmatrix}\begin{bmatrix} 1\\\\ 2\\\\ 3 \end{bmatrix}=\begin{bmatrix} 13\\\\ 22\\\\ 19\end{bmatrix}; \end{equation} ​504​450​045​ ​ ​123​ ​= ​132219​ ​;​​
  • 综上所述可得：两个序列的循环卷积运算可以转换为一个序列的循环卷积矩阵与另外一个序列的乘积。
  • Python 代码
import numpy as np
from scipy.linalg import circulant

np.set_printoptions(suppress=True, precision=3)
np.random.seed(123435)


class PermutationMatrix(object):
    def __init__(self, in_vector):
        self.in_vector = in_vector
        self.vector_size = np.size(self.in_vector)
        self.vector_size_1 = self.vector_size + 1
        self.p_matrix = np.zeros((self.vector_size, self.vector_size))

    def get_p_matrix(self):
        p_vector = np.arange(1, self.vector_size_1) % self.vector_size
        p_matrix = np.eye(len(p_vector))[p_vector]
        p_temp = np.diag(np.ones(self.vector_size))
        result = np.zeros_like(p_matrix)
        for i in range(self.vector_size):
            result += p_temp * self.in_vector[i]
            p_new = p_matrix @ p_temp
            print(f"p_new[{i}]=\n{p_new}")
            p_temp = p_new
        result = result.T
        print(f"result=\n{result}")
        print(f"vector_size={self.vector_size}")
        print(f"p_vector={p_vector}")
        print(f"p_matrix=\n{p_matrix}")
        self.p_matrix = p_matrix
        return self.p_matrix


class CirculantMatrix(object):
    def __init__(self, in_vector):
        self.in_vector = in_vector
        self.vector_size = np.size(self.in_vector)
        self.vector_plus1 = self.vector_size + 1
        self.vector_minus1 = self.vector_size - 1
        self.p_matrix = np.zeros((self.vector_size, self.vector_size))
        self.circulant_matrix = np.zeros_like(self.p_matrix)

    def get_p_matrix(self):
        p_vector = np.arange(1, self.vector_plus1) % self.vector_size
        p_matrix = np.eye(len(p_vector))[p_vector]
        self.p_matrix = p_matrix
        return self.p_matrix

    def get_circulant(self):
        p_temp = np.diag(np.ones(self.vector_size))
        result = np.zeros_like(self.p_matrix)
        my_p_matrix = self.get_p_matrix()
        for i in range(self.vector_size):
            result += p_temp * self.in_vector[i]
            p_new = my_p_matrix @ p_temp
            p_temp = p_new
        result = result.T
        self.circulant_matrix = result
        scipy_ciculant = circulant(self.in_vector)
        check_result = np.allclose(self.circulant_matrix, scipy_ciculant)
        print(f"*" * 50)
        print(f"vector={self.in_vector}")
        print(f"check_result={check_result}")
        print(f"circulant=\n{self.circulant_matrix}")
        print(f"scipy_ciculant=\n{scipy_ciculant}")
        print(f"*" * 50)
        return self.circulant_matrix


if __name__ == "__main__":
    my_code = 0
    vector1 = np.array([5, 0, 4])
    vector2 = np.array([1, 2, 3])
    my_cir_vector = CirculantMatrix(vector1)
    my_cir_vector_matrix = my_cir_vector.get_circulant()
    result = my_cir_vector_matrix @ vector2
    print(f"vector1={vector1}")
    print(f"vector2={vector2}")
    print(f"result=\n{result}")
  • 结果：
**************************************************
vector=[5 0 4]
check_result=True
circulant=
[[5. 4. 0.]
 [0. 5. 4.]
 [4. 0. 5.]]
scipy_ciculant=
[[5 4 0]
 [0 5 4]
 [4 0 5]]
**************************************************
vector1=[5 0 4]
vector2=[1 2 3]
result=
[13. 22. 19.]

3. 傅里叶矩阵

我们知道移位矩阵P的特征值为 z N = 1 z^N=1 zN=1的复数根，其特征向量如下：
q k = [ 1 , λ k , λ k 2 , ⋯   , λ k N − 1 ] ; λ k = e 2 π i N \begin{equation} q_k=\begin{bmatrix} 1,\lambda_k,\lambda_k^2,\cdots,\lambda_k^{N-1} \end{bmatrix};\lambda_k=\mathrm{e}^{\frac{2\pi i}{N}} \end{equation} qk​=[1,λk​,λk2​,⋯,λkN−1​​];λk​=eN2πi​​​

  • 我们之前推导过对于任意的循环卷积矩阵C来说可以表示如下：
    C = c 0 I + c 1 P + c 2 P 2 + ⋯ + c n − 1 P n − 1 \begin{equation}C=c_0 I+c_1P+c_2P^2+\cdots+c_{n-1}P^{n-1}\end{equation} C=c0​I+c1​P+c2​P2+⋯+cn−1​Pn−1​​
  • 我们可得矩阵C的特征值和特征向量与P的特征值特征向量相同。我们两边同时乘以 q k q_k qk​，且定义如下
    C q k = λ k ( C ) q k , P q k = λ k q k Cq_k=\lambda_k(C) q_k,Pq_k=\lambda_kq_k Cqk​=λk​(C)qk​,Pqk​=λk​qk​
    C q k = c 0 q k + c 1 P q k + c 2 P 2 q k + ⋯ + c n − 1 P n − 1 q k \begin{equation}Cq_k=c_0q_k+c_1Pq_k+c_2P^2q_k+\cdots+c_{n-1}P^{n-1}q_k\end{equation} Cqk​=c0​qk​+c1​Pqk​+c2​P2qk​+⋯+cn−1​Pn−1qk​​​
  • 代入特征方程可得:
    λ k ( C ) q k = c 0 q k + c 1 P q k + c 2 P 2 q k + ⋯ + c n − 1 P n − 1 q k \begin{equation}\lambda_k(C)q_k=c_0q_k+c_1Pq_k+c_2P^2q_k+\cdots+c_{n-1}P^{n-1}q_k\end{equation} λk​(C)qk​=c0​qk​+c1​Pqk​+c2​P2qk​+⋯+cn−1​Pn−1qk​​​
  • 整理可得:
    λ k ( C ) q k = c 0 q k + c 1 λ k q k + c 2 λ k 2 q k + ⋯ + c n − 1 λ k n − 1 q k \begin{equation}\lambda_k(C)q_k=c_0q_k+c_1\lambda_kq_k+c_2\lambda_k^2q_k+\cdots+c_{n-1}\lambda_k^{n-1}q_k\end{equation} λk​(C)qk​=c0​qk​+c1​λk​qk​+c2​λk2​qk​+⋯+cn−1​λkn−1​qk​​​
  • 整理可得:
    λ k ( C ) = c 0 + c 1 λ k + c 2 λ k 2 + ⋯ + c n − 1 λ k n − 1 \begin{equation}\lambda_k(C)=c_0+c_1\lambda_k+c_2\lambda_k^2+\cdots+c_{n-1}\lambda_k^{n-1}\end{equation} λk​(C)=c0​+c1​λk​+c2​λk2​+⋯+cn−1​λkn−1​​​
  • 我们知道: λ k = e 2 π k N = w k , w = e 2 π N \lambda_k=\mathrm{e}^{\frac{2\pi k}{N}}=w^k,w=\mathrm{e}^{\frac{2\pi }{N}} λk​=eN2πk​=wk,w=eN2π​
  • 那么可得：
    在这里插入图片描述
  • 小结1：这么做的主要用于：[后续补充，要补充的逻辑思路太多了]
    两个序列的循环卷积为离散傅里叶 D F T 变换下的序列相乘 两个序列的循环卷积为离散傅里叶DFT变换下的序列相乘 两个序列的循环卷积为离散傅里叶DFT变换下的序列相乘
  • 小结2： 所有的循环卷积矩阵都可以分解为离散傅里叶矩阵F和系数序列c相乘，它们的特征向量一致。
    后续更新逻辑思维图 后续更新逻辑思维图 后续更新逻辑思维图
# 线性代数 # 机器学习 # 矩阵
Logo
DAMO开发者矩阵

DAMO开发者矩阵，由阿里巴巴达摩院和中国互联网协会联合发起，致力于探讨最前沿的技术趋势与应用成果，搭建高质量的交流与分享平台，推动技术创新与产业应用链接，围绕“人工智能与新型计算”构建开放共享的开发者生态。

更多推荐

cover

Design Token 的变更审批流：企业级设计系统变更的自动化通知机器人

avatar DAMO开发者矩阵

LangChain 大模型应用开发全流程实战：从环境搭建到四大落地项目

你好！ 这是你第一次使用# LangChain 大模型应用开发全流程实战：从环境搭建到四大落地项目很多开发者初学大模型应用时，第一反应是直接调用各家模型的 HTTP API：把提示词拼好、发请求、拿返回结果，几十行代码就能跑通一个"聊天机器人"。但一旦业务场景从"问一句答一句"升级为"结合企业内部知识库回答"“多轮对话保持记忆”“让模型调用计算器和搜索引擎”“输出严格格式化的 JSON”，裸调 A

avatar DAMO开发者矩阵

2026深度解读：Work Agent如何实现复杂长程自动化任务

AI的交互形态正在发生本质的迭代，早期AI产品的核心定位停留在对话问答，用户给出一句指令，模型输出一轮回复，任务随即宣告结束。随着大模型工具调用能力持续成熟，应用形态逐步经历单轮问答、多轮对话、工具调用，最终走向自主任务链模式。聊天机器人只负责响应单次提问，而Work Agent可以承接跨度更长、步骤更多的复杂工作，长程任务执行能力，正是二者最核心的分界点。

avatar DAMO开发者矩阵