I have a 2-D signal that is (1536x128) and that is sparse in the Fourier domain (after applying fft2).

I want to apply compressive sensing to recover the signal using fewer random elements, but I am not sure how to find the orthogonal basis, the DFT for 2-D signals. I have the code of how to apply compressive sensing for 1-D signals with length N, but I am not sure how to modify that for 2-D signals of length (NxM).

N = 256;                % length of signal
P = 2;                  % number of sinusoids
K = 64;                 % number of measurements to take (N < L)

% Generate signal with P randomly spread sinosoids
% Note that a real-valued sinusoid has two peaks in the frequency domain
freq = randperm(N/2)-1;
freq = freq(1:P).';
n = 0:N-1;
x = sum(sin(2*pi*freq/N*n).', 2);

% Orthonormal basis matrix
Psi = dftmtx(N);
Psi_inv = conj(Psi)/N;
X = Psi*x;              % FFT of x(t)

% Plot signals
amp = 1.2*max(abs(x));
figure; subplot(5,1,1); plot(x); xlim([1 N]); ylim([-amp amp]);
title('$\mathbf{x(t)}$', 'Interpreter', 'latex')
subplot(5,1,2); plot(abs(X)); xlim([1 N]);
title('$|\mathbf{X(f)}|$', 'Interpreter', 'latex');

% Obtain K measurements
x_m = zeros(N,1);
q = randperm(N);
q = q(1:K);
x_m(q) = x(q);
subplot(5,1,3); plot(real(x_m)); xlim([1 N]);
title('Measured samples of $\mathbf{x(t)}$', 'Interpreter', 'latex');

A = Psi_inv(q, :);      % sensing matrix
y = A*X;                % measured values

% Perform Compressed Sensing recovery
x0 = A.'*y;
X_hat = l1eq_pd(x0, A, [], y, 1e-5);

subplot(5,1,4); plot(abs(X_hat)); xlim([1 N]);
title('$|\mathbf{\hat{X}(f)}|$', 'Interpreter', 'latex');

x_hat = real(Psi_inv*X_hat);    % IFFT of X_hat(f)

subplot(5,1,5); plot(x_hat); xlim([1 N]);  ylim([-amp amp]);
title('$\mathbf{\hat{x}(t)}$', 'Interpreter', 'latex');

Thank you!

  • $\begingroup$ I appreciate your work, my friend. There is one more beautiful and general way of doing the same that is using Eigenvalue Decomposition technique. $\endgroup$
    Oct 20, 2019 at 12:42
  • $\begingroup$ "I have the code of how to apply compressive sensing for 1-D signals with length N, but I am not sure how to modify that for 2-D signals of length (NxM)": Same way. Just stack your 2-D signal into a long vector with $N \cdot M$ elements. Everything else stays exactly the same. $\endgroup$
    – Florian
    Oct 21, 2019 at 10:29
  • $\begingroup$ Thanks Florian, but for the orthonormal basis, would that just be: Psi = dftmtx(N*M)? $\endgroup$
    – usna11
    Oct 21, 2019 at 21:38

1 Answer 1


If you have a function $ f \left[ m, n \right] \in \mathbb{R}^{M \times N} $ then the DFT of those functions is an orthogonal basis of functions in $ \mathbb{C}^{M \times N} $.

So if we have:

$$ F \left[ k , l \right] = \frac{1}{\sqrt{M N}} \sum_{m = 0}^{M - 1} \sum_{n = 0}^{N - 1} f \left[ m, n \right] {e}^{-j 2 \pi \left( \frac{k}{M} m + \frac{l}{N} n \right)} $$

So the set of $ \left\{ g \left[ m, n \right] = \frac{1}{\sqrt{M N}} {e}^{-j 2 \pi \left( \frac{k}{M} m + \frac{l}{N} n \right)} \right\}_{k, l = 0}^{M - 1, N - 1} $ is the orthogonal basis (Actually Orthonormal).

  • $\begingroup$ I'd add a plus inside parentheses between $m$ and $n$ terms $\endgroup$ Oct 20, 2019 at 10:46
  • 1
    $\begingroup$ @LaurentDuval, Good catch my friend. Fixed. Thank You. $\endgroup$
    – Royi
    Oct 20, 2019 at 11:06
  • $\begingroup$ Thanks Royi and Laurent, but how would you implement that in a Matlab code? From your equation, m and n are the variables, does that mean k and l are fixed? $\endgroup$
    – usna11
    Oct 20, 2019 at 21:27
  • $\begingroup$ @HoussemMarzougui, Since this is a base it has few members in the basis set. This members are parameterized by $ k $ and $ l $. $\endgroup$
    – Royi
    Oct 21, 2019 at 15:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.