信息处理 - 傅里叶变换的限制 - 吾爱随笔录

傅里叶变换的限制

信息处理傅里叶变换自由度压缩传感线性代数

2022-02-01 20:19:33

我目前正在阅读 Candes 等。al. 2006 年关于从不完整频率样本中恢复稀疏信号的论文[ 1 ]。我无法弄清楚傅里叶变换的形式是什么 $\Omega$ , $\hat{f}|_{\Omega}$ ，出现在引理 1.2中。

此限制似乎是双射 $\mathcal{F}_{T \to \Omega}: l_2(T) \to l_2(\Omega)$ ，什么时候 $|T| = |\Omega|$ 和 $T, \Omega$ 是的子集 $\mathbb{Z}_p$ , $p$ 主要。这里， $l_2(C)$ 表示信号的空间 $C$ 作为他们的支持。

有没有这样的具体例子 $\mathcal{F}_{T \to \Omega}$ ，还是我们只能证明它的存在？在 Terence Tao 的论文 [ 2 ] 中包含了这个引理的证明，证明中提到了 $\mathcal{F}_{T \to \Omega}$ 的系数具有类似于范德蒙德矩阵的形式，即它将包含元素 $(e^{- 2 \pi x_i \xi_j / p})$ ，这让我怀疑我们可以得到这种线性变换的具体例子。

1个回答

是的，我们可以明确地构造这样一个例子：维度的 DFT 矩阵 $N$ 是（谁）给的

F = {\exp (- j 2 π i k / N}_{i = 0, \dots, N - 1, k = 0, \dots, N - 1}

$F=\{\exp(-j2\pi ik/N\}_{i=0,\ldots,N-1,k=0,\ldots,N-1}$

现在，如果 $T,\Omega\subset\{0,1,\ldots,N-1\}$ 相应的 DFT 矩阵由下式给出

F_{T \to Ω} = {\exp (- j 2 π i k / N}_{i \in Ω, k \in T}

$F_{T\rightarrow\Omega}=\{\exp(-j2\pi ik/N\}_{i\in\Omega,k\in T}$

我们可以直接在 Python 中实现它：

N = 17  # the order/dimension (P in your notation)
L = 8   # the dimension of T, Omega
# choose some random subsets of 0,...,N-1 for T and Omega
T = np.random.choice(np.arange(N), L, replace=False)
Omega = np.random.choice(np.arange(N), L, replace=False)

# Calculate the DFT matrix
t, o = np.meshgrid(T, Omega)
F = np.exp(2j*np.pi*t*o/N)

import numpy.linalg as lg
# Print its rank. It should be always equal 
# to L to make F a bijection (i.e. invertible)
print (lg.matrix_rank(F))

在上面运行 N=17 的代码时，排名始终为 8。我尝试设置 N=16，结果发现对于某些随机配置，排名可能会变为 7，即 F 不会是双射.

其它你可能感兴趣的问题

上一篇使用 Lucas-Kanade 方法的视频稳定下一篇分数延迟滤波器和截止频率