双选择性信道下正交啁啾分复用(OCDM)的低复杂度均衡算法研究——论文阅读

举报
DuHz 发表于 2025/10/06 18:51:23 2025/10/06
【摘要】 双选择性信道下正交啁啾分复用(OCDM)的低复杂度均衡算法研究Wang, X.; Jiang, Z.; Shen, X.-H. Low Complexity Equalization of Orthogonal Chirp Division Multiplexing in Doubly-Selective Channels. Sensors 2020, 20, 3125. 摘要本文研究了一...

双选择性信道下正交啁啾分复用(OCDM)的低复杂度均衡算法研究

Wang, X.; Jiang, Z.; Shen, X.-H. Low Complexity Equalization of Orthogonal Chirp Division Multiplexing in Doubly-Selective Channels. Sensors 2020, 20, 3125.

摘要

本文研究了一种用于双选择性信道高速通信的正交啁啾分复用(OCDM)调制方案——统一相位正交啁啾分复用(UP-OCDM)。通过配备统一相位矩阵,UP-OCDM能够在保持OCDM优势的同时减少存储需求。本文证明了UP-OCDM的变换矩阵具有循环特性,并基于此特性揭示了UP-OCDM系统在双选择性信道下的特殊信道结构:(1)等效频域信道矩阵可近似为带状矩阵;(2)基扩展模型(BEM)框架下的变换域信道矩阵是对角矩阵和循环矩阵乘积之和。基于这些特殊结构,提出了两种低复杂度均衡算法,分别基于块LDL^H分解和迭代矩阵求逆,将计算复杂度从O(N3)O(N^3)分别降至O(NQ2)O(NQ^2)O(iNMlogN)O(iNM\log N)

1. 引言与研究背景

1.1 OFDM系统的局限性

正交频分复用(OFDM)是过去二十年中最成功的调制方案之一,其核心优势在于能够在正交子载波上传输信息符号。然而,OFDM系统存在关键缺陷:其采用的余弦信号子载波对多普勒扩展极为敏感。在双选择性信道(同时具有时变和频变特性)条件下,OFDM系统性能会严重恶化。

对于载频fc=10f_c = 10 GHz、子载波间隔Δf=20\Delta f = 20 kHz的OFDM系统,当归一化多普勒频率fdT=0.1f_d T = 0.10.30.3时,对应的移动速度分别达到216 km/h和648 km/h,这在高速移动通信场景中很常见。

1.2 啁啾信号的优势

啁啾信号是频率随时间线性变化的信号,具有以下优点:

  • 自相关函数具有良好的时间分辨率
  • 对多普勒效应不敏感
  • 在雷达和声呐应用中得到广泛使用

基于啁啾信号的正交啁啾分复用(OCDM)系统通过使用啁啾子载波替代传统余弦子载波,在保持与OFDM相似的峰均功率比(PAPR)和频谱效率的同时,实现了更好的抗多普勒性能。

1.3 研究动机与贡献

现有OCDM系统存在两个主要问题:

  1. 使用不同相位矩阵导致额外的存储开销
  2. 缺乏针对双选择性信道的低复杂度均衡算法

本文的主要贡献包括:

  • 提出UP-OCDM方案,通过统一相位矩阵减少50%的存储需求
  • 证明UP-OCDM变换矩阵的循环结构
  • 开发两种低复杂度均衡算法,大幅降低计算复杂度
  • 通过仿真验证算法有效性

2. UP-OCDM系统模型详解

2.1 信号模型的数学构建

考虑一组基带连续啁啾信号,其啁啾率定义为:

a=NT2a = -\frac{N}{T^2}

其中NN是子载波数,TT是符号持续时间。第kk个啁啾子载波可表示为:

ck(t)=ejπa(tkTN)2=ejπNT2(tkTN)2,0t<Tc_k(t) = e^{j\pi a(t-k\frac{T}{N})^2} = e^{-j\pi\frac{N}{T^2}(t-k\frac{T}{N})^2}, \quad 0 \leq t < T

这些啁啾波形满足正交性条件:

0TejπNT2(tmTN)2ejπNT2(tkTN)2dt=δ(mk)\int_0^T e^{-j\pi\frac{N}{T^2}(t-m\frac{T}{N})^2} e^{j\pi\frac{N}{T^2}(t-k\frac{T}{N})^2}dt = \delta(m-k)

调制后的传输信号为:

s(t)=k=0N1dkck(t),0t<Ts(t) = \sum_{k=0}^{N-1} d_k c_k(t), \quad 0 \leq t < T

其中dkd_k是第kk个子载波传输的符号,取自有限星座图(如4-QAM、16-QAM、64-QAM)。

2.2 离散信号表示

假设采样频率fs=NTf_s = \frac{N}{T},基带离散信号为:

s(n)=k=0N1dkejπN(nk)2,0n<Ns(n) = \sum_{k=0}^{N-1} d_k e^{-j\frac{\pi}{N}(n-k)^2}, \quad 0 \leq n < N

写成矩阵形式:

s=Φd\mathbf{s} = \boldsymbol{\Phi}\mathbf{d}

其中变换矩阵Φ\boldsymbol{\Phi}(m,n)(m,n)元素为:

Φ(m,n)=ejπN(mn)2=ejπm2Nej2πmnNejπn2N\Phi(m,n) = e^{-j\frac{\pi}{N}(m-n)^2} = e^{-j\pi\frac{m^2}{N}} \cdot e^{j2\pi\frac{mn}{N}} \cdot e^{-j\pi\frac{n^2}{N}}

2.3 变换矩阵的分解

定义相位矩阵:

Γ=diag([1,ejπ12N,...,ejπ(N1)2N])\boldsymbol{\Gamma} = \text{diag}([1, e^{-j\pi\frac{1^2}{N}}, ..., e^{-j\pi\frac{(N-1)^2}{N}}])

则变换矩阵可分解为:

Φ=ΓFHΓ\boldsymbol{\Phi} = \boldsymbol{\Gamma}\mathbf{F}^H\boldsymbol{\Gamma}

其中F\mathbf{F}N×NN \times N的归一化DFT矩阵,其(p,q)(p,q)元素为F(p,q)=N12ej2πpqNF(p,q) = N^{-\frac{1}{2}}e^{-j2\pi\frac{pq}{N}}

这种分解表明UP-OCDM调制可通过三步实现:

  1. 符号向量d\mathbf{d}乘以相位矩阵Γ\boldsymbol{\Gamma}
  2. 执行IFFT运算
  3. 再次乘以相同的相位矩阵Γ\boldsymbol{\Gamma}

2.4 频谱效率分析

UP-OCDM中啁啾子载波的带宽为B=NΔf=NTB = N\Delta f = \frac{N}{T}。模拟UP-OCDM信号理论上占用带宽为B+NT2T=2BB + \frac{N}{T^2}T = 2B。然而,通过谱折叠技术,每个啁啾子载波的频谱可以折叠到基带[B2,B2][-\frac{B}{2}, \frac{B}{2}]范围内,采样率恰好为fs=B=NTf_s = B = \frac{N}{T} Hz。因此,通过上采样,UP-OCDM的频谱可以适配到与OFDM相同的带宽BB内。

3. 循环矩阵结构的理论证明

3.1 循环性质的推导

变换矩阵Φ\boldsymbol{\Phi}具有特殊的循环结构。定义k=mnk = m - nΦ(mn)=Φ(m,n)\Phi(m-n) = \Phi(m,n),可得:

Φ(k)=Φ(m,n)=Φ(n,m)\Phi(k) = \Phi(m,n) = \Phi(n,m)

这表明矩阵是对称的。对于任意整数L[0,N1]L \in [0, N-1]

Φ(NL)=ejπ(NL)2N=ejπN22NL+L2N\Phi(N-L) = e^{-j\pi\frac{(N-L)^2}{N}} = e^{-j\pi\frac{N^2-2NL+L^2}{N}}

展开后得:

Φ(NL)=ejπN×ej2πL×ejπL2N\Phi(N-L) = e^{-j\pi N} \times e^{j2\pi L} \times e^{-j\pi\frac{L^2}{N}}

NN为奇数时,ejπN=1N=1e^{-j\pi N} = -1^N = -1,因此:

Φ(NL)=ejπL2N=Φ(L)\Phi(N-L) = e^{-j\pi\frac{L^2}{N}} = \Phi(L)

这证明了Φ\boldsymbol{\Phi}是循环矩阵,可表示为:

Φ=[Φ(0)Φ(N1)Φ(1)Φ(1)Φ(0)Φ(2)Φ(N1)Φ(N2)Φ(0)]\boldsymbol{\Phi} = \begin{bmatrix} \Phi(0) & \Phi(N-1) & \cdots & \Phi(1) \\ \Phi(1) & \Phi(0) & \cdots & \Phi(2) \\ \vdots & \vdots & \ddots & \vdots \\ \Phi(N-1) & \Phi(N-2) & \cdots & \Phi(0) \end{bmatrix}

3.2 循环结构的重要性

循环矩阵具有以下重要性质:

  • 可通过FFT快速实现矩阵-向量乘法
  • 循环矩阵的乘积仍是循环矩阵
  • 可以被DFT矩阵对角化

这些性质为设计低复杂度均衡器提供了理论基础。

4. 双选择性信道模型

4.1 信道建模

双选择性信道同时具有时变和频变特性。为对抗符号间干扰(ISI),在每个传输符号开头添加长度为Lcp=LL_{cp} = L的循环前缀,其中LL是信道长度。去除循环前缀后,接收信号为:

r[n]=l=0L1hl[n]s[nl]+w[n],n=0,1,...,N1r[n] = \sum_{l=0}^{L-1} h_l[n]s[n-l] + w[n], \quad n = 0,1,...,N-1

其中:

  • hl[n]h_l[n]:第ll条路径在时刻nn的复增益
  • w[n]w[n]:方差为σw2\sigma_w^2的复加性高斯白噪声
  • LL:信道长度,最大延迟为(L1)T(L-1)T

矩阵形式为:

r=Hs+w=HΦd+w\mathbf{r} = \mathbf{H}\mathbf{s} + \mathbf{w} = \mathbf{H}\boldsymbol{\Phi}\mathbf{d} + \mathbf{w}

4.2 信道矩阵结构

时域信道矩阵H\mathbf{H}不是循环矩阵,而是具有复杂的时变结构。在双选择性信道下,H\mathbf{H}的每个元素都随时间变化,这给均衡带来了巨大挑战。

5. 低复杂度均衡器设计

5.1 MMSE块均衡器(基准方案)

线性块MMSE均衡的估计为:

d^MMSE=ΦHs^MMSE=ΦH(HHH+γ1IN)1HHr\hat{\mathbf{d}}_{MMSE} = \boldsymbol{\Phi}^H\hat{\mathbf{s}}_{MMSE} = \boldsymbol{\Phi}^H(\mathbf{H}^H\mathbf{H} + \gamma^{-1}\mathbf{I}_N)^{-1}\mathbf{H}^H\mathbf{r}

其中γ=σd2/σw2\gamma = \sigma_d^2/\sigma_w^2是信噪比。矩阵(HHH+γ1IN)(\mathbf{H}^H\mathbf{H} + \gamma^{-1}\mathbf{I}_N)N×NN \times N的厄米矩阵,可通过LDL^H分解求解,但计算复杂度高达O(N3)O(N^3)

5.2 带状MMSE块均衡器

5.2.1 频域处理

对接收信号执行FFT:

rF=Fr=FHs+Fw\mathbf{r}_F = \mathbf{F}\mathbf{r} = \mathbf{F}\mathbf{H}\mathbf{s} + \mathbf{F}\mathbf{w}

s=Φd\mathbf{s} = \boldsymbol{\Phi}\mathbf{d}代入:

rF=FHΦd+wF\mathbf{r}_F = \mathbf{F}\mathbf{H}\boldsymbol{\Phi}\mathbf{d} + \mathbf{w}_F

利用Φ=ΓFHΓ\boldsymbol{\Phi} = \boldsymbol{\Gamma}\mathbf{F}^H\boldsymbol{\Gamma}的分解:

rF=FHFHFΦFHFd+wF=HEdF+wF\mathbf{r}_F = \mathbf{F}\mathbf{H}\mathbf{F}^H\mathbf{F}\boldsymbol{\Phi}\mathbf{F}^H\mathbf{F}\mathbf{d} + \mathbf{w}_F = \mathbf{H}_E\mathbf{d}_F + \mathbf{w}_F

其中等效信道矩阵HE=FHFHFΦFH\mathbf{H}_E = \mathbf{F}\mathbf{H}\mathbf{F}^H\mathbf{F}\boldsymbol{\Phi}\mathbf{F}^H

5.2.2 带状近似

频率响应矩阵HF=FHFH\mathbf{H}_F = \mathbf{F}\mathbf{H}\mathbf{F}^H在双选择性信道下不是对角矩阵,但可近似为带状矩阵。定义带状近似:

HB=HFT\mathbf{H}_B = \mathbf{H}_F \odot \mathbf{T}

其中\odot是逐元素乘积,T\mathbf{T}是带宽为2Q+12Q+1的带状矩阵模板。

由于FΦFH\mathbf{F}\boldsymbol{\Phi}\mathbf{F}^H是对角矩阵,其第(k,k)(k,k)个元素为ejπ(k2N14)e^{j\pi(\frac{k^2}{N}-\frac{1}{4})},记为Λ\boldsymbol{\Lambda},则:

HE=HFΛ\mathbf{H}_E = \mathbf{H}_F\boldsymbol{\Lambda}

由于Λ\boldsymbol{\Lambda}对角元素的模为1,HE\mathbf{H}_E也可近似为带宽2Q+12Q+1的带状矩阵E=HBΛ\mathbf{E} = \mathbf{H}_B\boldsymbol{\Lambda}

5.2.3 带状LDL^H分解算法

构造矩阵R=EEH+γ1IN\mathbf{R} = \mathbf{E}\mathbf{E}^H + \gamma^{-1}\mathbf{I}_N,它也是带宽为2Q+12Q+1的带状厄米矩阵。带状LDL^H分解算法如下:

算法1:带状LDL^H分解

输入: 带状矩阵R,带宽参数Q
输出: 下三角矩阵L,对角矩阵D

初始化: v = 0_{N×1}, L = I_N, D = I_N
for k = 0 to N-1 do
    m = max{0, k-Q}
    n = min{k+Q, N-1}
    for i = m to k-1 do
        v_i = L*_{k,i}D_{i,i}
    end for
    v_k = R_{k,k} - L_{k,m:k-1}v_{m:k-1}
    D_{k,k} = v_k
    L_{k+1:n,k} = (R_{k+1:n,k} - L_{k+1:n,m:k-1}v_{m:k-1})/v_k
end for

5.3 迭代LSQR块均衡器

5.3.1 基扩展模型(BEM)

采用BEM对时变信道建模,每个信道抽头增益表示为:

hl[n]=m=0M1cl,mφm[n]h_l[n] = \sum_{m=0}^{M-1} c_{l,m}\varphi_m[n]

其中MM是BEM阶数,cl,mc_{l,m}是基系数,φm[n]\varphi_m[n]是基函数(如复指数基、多项式基等)。

5.3.2 变换域信道矩阵构建

将BEM模型代入传输方程:

r=m=0M1PmGms+w\mathbf{r} = \sum_{m=0}^{M-1} \mathbf{P}_m\mathbf{G}_m\mathbf{s} + \mathbf{w}

其中:

  • Pm=diag([φm[0],φm[1],...,φm[N1]])\mathbf{P}_m = \text{diag}([\varphi_m[0], \varphi_m[1], ..., \varphi_m[N-1]]):BEM基的对角矩阵
  • Gm\mathbf{G}_m:首列为[c0,m,c1,m,...,cL1,m,0,...,0]T[c_{0,m}, c_{1,m}, ..., c_{L-1,m}, 0, ..., 0]^T的循环矩阵

由于s=Φd\mathbf{s} = \boldsymbol{\Phi}\mathbf{d},且Φ\boldsymbol{\Phi}Gm\mathbf{G}_m都是循环矩阵,其乘积Θm=GmΦ\boldsymbol{\Theta}_m = \mathbf{G}_m\boldsymbol{\Phi}也是循环矩阵。变换域信道矩阵为:

C=m=0M1PmΘm\mathbf{C} = \sum_{m=0}^{M-1} \mathbf{P}_m\boldsymbol{\Theta}_m

5.3.3 快速构建算法

利用循环矩阵可通过DFT对角化的性质:

Θm=FHDmΛF\boldsymbol{\Theta}_m = \mathbf{F}^H\mathbf{D}_m\boldsymbol{\Lambda}\mathbf{F}

其中Dm\mathbf{D}_m是对角矩阵,其对角元素为BEM系数cl,mc_{l,m}零填充到长度NN后的DFT:

Dm=diag(F[c0,m,c1,m,...,cL1,m,0,...,0]T)\mathbf{D}_m = \text{diag}(\mathbf{F}[c_{0,m}, c_{1,m}, ..., c_{L-1,m}, 0, ..., 0]^T)

因此:

C=m=0M1PmFHVmF\mathbf{C} = \sum_{m=0}^{M-1} \mathbf{P}_m\mathbf{F}^H\mathbf{V}_m\mathbf{F}

其中Vm=DmΛ\mathbf{V}_m = \mathbf{D}_m\boldsymbol{\Lambda}

5.3.4 LSQR迭代算法

LSQR算法在Krylov子空间中寻找最优解:

K(CHC,CHr,i)=span{CHr,(CHC)CHr,...,(CHC)i1CHr}\mathcal{K}(\mathbf{C}^H\mathbf{C}, \mathbf{C}^H\mathbf{r}, i) = \text{span}\{\mathbf{C}^H\mathbf{r}, (\mathbf{C}^H\mathbf{C})\mathbf{C}^H\mathbf{r}, ..., (\mathbf{C}^H\mathbf{C})^{i-1}\mathbf{C}^H\mathbf{r}\}

算法通过最小化每次迭代的残差范数,逐步逼近最优解。收敛速度受条件数影响:

cond(C)=CC1\text{cond}(\mathbf{C}) = ||\mathbf{C}|| \cdot ||\mathbf{C}^{-1}||

5.4 复杂度分析对比

算法 MMSE均衡 带状MMSE均衡 迭代LSQR均衡
复杂度 O(N3)O(N^3) O(NQ2)O(NQ^2) O(iNMlogN)O(iNM\log N)
存储需求 O(N2)O(N^2) O(NQ)O(NQ) O(MN)O(MN)
适用场景 小规模系统 中等多普勒扩展 高多普勒扩展

6. 仿真结果与性能分析

6.1 仿真参数设置

  • 符号持续时间:T=64T = 64 μs
  • 子载波数:N=256N = 256
  • 采样周期:T/N=0.25T/N = 0.25 μs
  • 信道模型:16径瑞利衰落,指数衰减功率时延谱(每径损失2 dB)
  • 信道编码:码率1/2的卷积码
  • 多普勒谱:Jakes模型
  • 归一化多普勒扩展:fdT{0.1,0.3}f_dT \in \{0.1, 0.3\}

6.2 性能对比分析

图2:MMSE均衡器下的BER性能

image.png

图2描述:该图展示了UP-OCDM、OCDM和OFDM三种系统在MMSE均衡器下的误码率(BER)性能对比。横轴为Eb/N0E_b/N_0(比特能量与噪声功率密度之比),纵轴为BER(对数刻度)。图(a)对应归一化多普勒扩展0.1,图(b)对应0.3。

从图2可以观察到:

  • UP-OCDM(红色曲线)和OCDM(蓝色曲线)性能几乎重合,证明统一相位矩阵不影响性能
  • 两者均显著优于OFDM(绿色曲线),特别是在高SNR区域
  • 4-QAM时,UP-OCDM/OCDM在SNR=5dB处开始优于OFDM
  • 16-QAM时,交叉点移至SNR=10dB
  • 64-QAM时,即使在最恶劣条件(fdT=0.3f_dT=0.3),SNR>22dB时仍优于OFDM

这种性能提升源于啁啾子载波带来的时频分集增益。每个符号的能量分布在整个时频平面上,而非OFDM中的单一频点,从而获得更强的抗衰落能力。

图3:带状MMSE均衡器性能

image.png

图3描述:该图比较了UP-OCDM和OFDM在不同带宽参数QQ下的带状MMSE均衡器性能。蓝色曲线代表OFDM,红色曲线代表UP-OCDM。三组曲线分别对应Q=2Q=2(最细线)、Q=4Q=4(中等粗细)、Q=6Q=6(最粗线)。

关键观察:

  • UP-OCDM在所有QQ值下均优于OFDM
  • 随着QQ增大,两系统性能都改善,因为信道矩阵近似更精确
  • 高多普勒扩展(图b)下性能下降,因为带外ICI泄漏增加
  • Q=4Q=4时UP-OCDM已能实现可靠传输,复杂度从O(N3)O(N^3)降至O(16N)O(16N)

性能优势的理论解释:UP-OCDM可视为预编码OFDM,符号向量d\mathbf{d}F\mathbf{F}预编码,使每个符号能量分布在NN个子载波上,获得分集增益。

图4:迭代LSQR均衡器性能

image.png

图4描述:该图展示了不同迭代次数ii下的LSQR均衡器性能。蓝色曲线为UP-OCDM,绿色和红色曲线分别为两种OFDM的LSQR均衡器实现。实线、虚线、点线分别对应i=1,4,8i=1,4,8

性能特点:

  • UP-OCDM的LSQR均衡器在高多普勒场景下表现优异
  • 迭代4次即可接近MMSE性能,8次基本达到最优
  • 低SNR区域存在半收敛现象:过多迭代可能放大噪声
  • 相比OFDM的LSQR,UP-OCDM复杂度降低O(NlogN)O(N\log N)

图5:算法综合比较

image.png

图5描述:该图在相同复杂度约束下比较三种均衡器。将算法按复杂度配对:Q=2/i=1Q=2/i=1(蓝色,最低复杂度)、Q=4/i=4Q=4/i=4(红色,中等复杂度)、Q=6/i=8Q=6/i=8(绿色,较高复杂度)。黑色曲线为O(N3)O(N^3)复杂度的MMSE基准。

综合分析:

  • 低多普勒扩展时,带状MMSE均衡器性价比最高
  • 高多普勒扩展时,迭代LSQR均衡器更优
  • 带状MMSE的性能改善随复杂度增加趋于饱和
  • 迭代LSQR的性能随复杂度增加持续改善

附录A:循环矩阵性质

A.1 循环矩阵的DFT对角化

定理A.1:任何N×NN \times N循环矩阵C\mathbf{C}可以被DFT矩阵对角化:

C=FHDF\mathbf{C} = \mathbf{F}^H\mathbf{D}\mathbf{F}

其中D\mathbf{D}是对角矩阵,其对角元素是C\mathbf{C}第一列的DFT。

证明:设循环矩阵C\mathbf{C}的第一列为c=[c0,c1,...,cN1]T\mathbf{c} = [c_0, c_1, ..., c_{N-1}]^T。定义生成多项式:

c(z)=k=0N1ckzkc(z) = \sum_{k=0}^{N-1} c_k z^k

对于DFT矩阵的第nnfn\mathbf{f}_n,有:

Cfn=c(ωn)fn\mathbf{C}\mathbf{f}_n = c(\omega_n)\mathbf{f}_n

其中ωn=ej2πn/N\omega_n = e^{-j2\pi n/N}是第nnNN次单位根。因此fn\mathbf{f}_n是特征向量,c(ωn)c(\omega_n)是对应特征值。

由于{f0,f1,...,fN1}\{\mathbf{f}_0, \mathbf{f}_1, ..., \mathbf{f}_{N-1}\}构成正交基,得:

C=n=0N1c(ωn)fnfnH=FHdiag([c(ω0),...,c(ωN1)])F\mathbf{C} = \sum_{n=0}^{N-1} c(\omega_n)\mathbf{f}_n\mathbf{f}_n^H = \mathbf{F}^H\text{diag}([c(\omega_0), ..., c(\omega_{N-1})])\mathbf{F}

[c(ω0),...,c(ωN1)]T=Fc[c(\omega_0), ..., c(\omega_{N-1})]^T = \mathbf{F}\mathbf{c}正是第一列的DFT。

A.2 UP-OCDM变换矩阵循环性

定理A.2:当NN为奇数时,UP-OCDM的变换矩阵Φ\boldsymbol{\Phi}是循环矩阵。

证明:需要证明Φ(i,j)\Phi(i,j)只依赖于(ij)modN(i-j) \bmod N

从定义出发:

Φ(i,j)=ejπ(ij)2/N\Phi(i,j) = e^{-j\pi(i-j)^2/N}

k=(ij)modNk = (i-j) \bmod N,则存在整数mm使得ij=k+mNi-j = k + mN。代入:

Φ(i,j)=ejπ(k+mN)2/N=ejπk2/Nej2πmkejπm2N\Phi(i,j) = e^{-j\pi(k+mN)^2/N} = e^{-j\pi k^2/N} \cdot e^{-j2\pi mk} \cdot e^{-j\pi m^2N}

由于ej2πmk=1e^{-j2\pi mk} = 1m,km,k均为整数),且当NN为奇数时ejπm2N=1e^{-j\pi m^2N} = 1,因此:

Φ(i,j)=ejπk2/N=Φ(k)\Phi(i,j) = e^{-j\pi k^2/N} = \Phi(k)

这证明了Φ\boldsymbol{\Phi}是循环矩阵。

附录B:带状矩阵LDL^H分解的计算复杂度分析

B.1 运算计数

对于带宽为2Q+12Q+1N×NN \times N带状厄米矩阵R\mathbf{R},LDL^H分解的运算包括:

kk步(k=0,1,...,N1k=0,1,...,N-1

  1. 计算vi=Lj,iDi,iv_i = L_{j,i}^*D_{i,i}i[m,k1]i \in [m,k-1]

    • 复数乘法(CM):min(k,Q)\min(k,Q)
    • 无复数加法
  2. 计算vk=Rk,kLk,m:k1vm:k1v_k = R_{k,k} - \mathbf{L}_{k,m:k-1}\mathbf{v}_{m:k-1}

    • CM:min(k,Q)\min(k,Q)
    • 复数加法(CA):min(k,Q)\min(k,Q)
  3. 计算Lk+1:n,k=(Rk+1:n,kLk+1:n,m:k1vm:k1)/vk\mathbf{L}_{k+1:n,k} = (\mathbf{R}_{k+1:n,k} - \mathbf{L}_{k+1:n,m:k-1}\mathbf{v}_{m:k-1})/v_k

    • 向量长度:min(Nk1,Q)\min(N-k-1,Q)
    • 矩阵-向量乘法:min(Nk1,Q)×min(k,Q)\min(N-k-1,Q) \times \min(k,Q) CM和CA
    • 除法:min(Nk1,Q)\min(N-k-1,Q)次CM

B.2 总复杂度

忽略边界效应,假设QNQ \ll N

  • 总CM数:k=0N1[2Q+Q2](2Q+Q2)N\sum_{k=0}^{N-1}[2Q + Q^2] \approx (2Q + Q^2)N
  • 总CA数:k=0N1[Q+Q2](Q+Q2)N\sum_{k=0}^{N-1}[Q + Q^2] \approx (Q + Q^2)N

转换为浮点运算数(1个CM = 6 flops,1个CA = 2 flops):

总flops6(2Q+Q2)N+2(Q+Q2)N=(14Q+8Q2)N\text{总flops} \approx 6(2Q + Q^2)N + 2(Q + Q^2)N = (14Q + 8Q^2)N

简化后得复杂度为O(Q2N)O(Q^2N),当QQ固定时为O(N)O(N)

附录C:LSQR算法的收敛性分析

C.1 条件数与收敛速度

LSQR的收敛速度由矩阵条件数决定。对于矩阵C\mathbf{C},第ii次迭代的相对残差满足:

rir0(κ1κ+1)i\frac{||\mathbf{r}_i||}{||\mathbf{r}_0||} \leq \left(\frac{\kappa - 1}{\kappa + 1}\right)^i

其中κ=cond(C)\kappa = \text{cond}(\mathbf{C})是条件数。

C.2 半收敛现象

在有噪声的情况下,LSQR表现出半收敛性:

  • 初期:残差快速下降,解逐渐接近真实值
  • 中期:达到最优点,误差最小
  • 后期:继续迭代会放大噪声分量,误差反而增大

最优迭代次数iopti_{opt}与SNR相关:

ioptlog(SNR)2log(κ+1κ1)i_{opt} \approx \frac{\log(\text{SNR})}{2\log(\frac{\kappa+1}{\kappa-1})}

C.3 预条件技术

通过预条件可以改善条件数。对于系统Cd=r\mathbf{C}\mathbf{d} = \mathbf{r},引入预条件矩阵M\mathbf{M}

M1Cd=M1r\mathbf{M}^{-1}\mathbf{C}\mathbf{d} = \mathbf{M}^{-1}\mathbf{r}

理想的M\mathbf{M}应满足:

  1. cond(M1C)cond(C)\text{cond}(\mathbf{M}^{-1}\mathbf{C}) \ll \text{cond}(\mathbf{C})
  2. M1v\mathbf{M}^{-1}\mathbf{v}易于计算

对于UP-OCDM,可选择M\mathbf{M}C\mathbf{C}的带状近似或不完全LU分解。

【声明】本内容来自华为云开发者社区博主,不代表华为云及华为云开发者社区的观点和立场。转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息,否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。