巨大的 MATLAB Dftmtx "N"

Question

我有一个大小为 M（比如 500）的向量，我将其上采样 MM=500，因此我的新向量现在大小为 N=500 x 500=250000。我正在使用优化算法，需要使用 DFT 矩阵而不是内置函数来执行大小为 N 的上采样向量的 fft/dft。

但是，由于内存限制，这变得令人望而却步。有什么办法吗？我在这里看到了类似的问题 Huge Fourier matrix - MATLAB 但这是关于一个巨大的矩阵，解决方案是将矩阵分解成列并逐列进行操作。在我的例子中，向量有 250000 行。

将行拆分成几行是否明智，比如每行 500 次并重复同样的事情 500 次，最后连接结果？

Answer 1

如果使用 FFT 是一个选项，则旋转因子矩阵不会显式出现，因此实际内存需求约为 O(N)。

如果必须使用显式 DFT 矩阵，则可以使用较大 DFT 矩阵的子矩阵分解计算。给定长度 N 的输入 x，并假设我们希望将大型 DFT 矩阵划分为 BlockSize x BlockSize 个子矩阵，这可以使用以下 matlab 代码完成：

y = zeros(size(x));
Imax = ceil(N / BlockSize); % divide the rows into Imax chunks
Jmax = ceil(N / BlockSize); % divide the columns into Jmax chunks

% iterate over the blocks
for i=0:Imax-1
  imin = i*BlockSize;
  imax = min(i*BlockSize+BlockSize-1,N-1);
  for j=0:Jmax-1
    jmin = j*BlockSize;
    jmax = min(j*BlockSize+BlockSize-1,N-1);
    [XX,YY] = meshgrid(jmin:jmax, imin:imax);

    % compute the DFT submatrix
    W = exp(-2* pi * 1i * XX .* YY / N);

    % apply the DFT submatrix on a chunk of the input and add to the output
    y([imin:imax] + 1) = y([imin:imax] + 1) + W * x([jmin:jmax] + 1);
  end
end

如果需要，可以很容易地调整上述代码以沿行使用与沿列不同的块大小。

巨大的 MATLAB Dftmtx "N"

MATLAB Dftmtx for Huge "N"

fft

large-data

dft