# Orthogonal Basis for a 2D Signals (Compressive Sensing)

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!

• I appreciate your work, my friend. There is one more beautiful and general way of doing the same that is using Eigenvalue Decomposition technique. Oct 20, 2019 at 12:42
• "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. Oct 21, 2019 at 10:29
• Thanks Florian, but for the orthonormal basis, would that just be: Psi = dftmtx(N*M)?
– ZABA
Oct 21, 2019 at 21:38

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

• I'd add a plus inside parentheses between $m$ and $n$ terms Oct 20, 2019 at 10:46
• @LaurentDuval, Good catch my friend. Fixed. Thank You.
– Royi
Oct 20, 2019 at 11:06
• 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?
– ZABA
Oct 20, 2019 at 21:27
• @HoussemMarzougui, Since this is a base it has few members in the basis set. This members are parameterized by $k$ and $l$.
– Royi
Oct 21, 2019 at 15:55