Orthogonal Basis for a 2D Signals (Compressive Sensing)

Question

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!

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).