MATLAB Dftmtx для огромных "N"

Question

У меня есть вектор размера M (скажем, 500), который я увеличиваю с коэффициентом MM = 500, так что мой новый вектор теперь имеет размер N = 500 x 500 = 250000. Я использую алгоритм оптимизации, и мне нужно выполнить fft / dft вектора с повышенной дискретизацией размера N, используя матрицу DFT, а не встроенную функцию.

Однако это становится запретным из-за ограничений памяти. Есть ли способ пойти по этому поводу? Я видел подобный вопрос здесь Огромная матрица Фурье - MATLAB , но это касается Огромной матрицы, где решение состоит в том, чтобы разбить матрицу на столбцы и выполнить операцию столбец за столбцом. В моем случае вектор имеет 250000 строк.

Было бы разумно разделить строки на части, скажем, по 500, повторить одно и то же 500 раз и объединить результаты в итоге?

Answer 1

Если использовать БПФ, опция, матрица коэффициентов твидала не отображается явно, поэтому фактические требования к памяти составляют порядка O(N).

Если вам необходимо использовать явную матрицу DFT, то можно разбить вычисления, используя подматрицы большей матрицы DFT. Учитывая вход x длины N и предполагая, что мы хотим разделить большую матрицу 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

При необходимости было бы довольно легко адаптировать приведенный выше код для использования блоков другого размера по строкам, чем по столбцам.