Overview of Compressed Sensing

The conventional way of acquiring a signal is to sample the data at the Nyquist rate. It results in a huge amount of data which consumes large storage space. So a compression is inevitable for storage and transmission. The fundamental question is “instead of creating too many data and compress it, can we directly acquire compressed measurements”. This is the key idea in Compressive Sensing. So the whole part of Compressed Sensing is to directly acquire compressed data. Compressive Sensing is based on the fact that the acquired signal ‘x’ has a sparse representation in some basis. Compressed Sensing enables us to beat Nyquist Sampling theorem. As stated above, sampling and compression are now performed in one step. The whole theory can be described using the following matrix notation:

y= Φ x

Here x is a column vector (Nx1) and only a few of them are non-zero. There are only K non-zero entries. Φ is a random matrix (MxN) matrix. Therefore y is a column vector (Mx1). So the goal is to recover x from y. The idea basically is that the φ matrix will preserve the sparse signal.

The input sparse vector x is in RN and the output vector y is in RM. The sensing matrix which maps the space RN to RM, has a Rank less than or equal to M (which is  << N).

Properties to be satisfied by Φ:

  • Random Gaussian matrix (M x N) such that:
    Φ x1 ≠ Φ x2 for all K-sparse x1 ≠ x2.
    This property is to make sure that the mapping is invertible so that no two output vectors are mapped to the same vector, while recovery. In cases where the above equation fails during recovery, Φ will not yield a unique signal, ‘x’.
  • There are K unknown values and K unknown positions in x. So Φ must have an at-least 2K number of rows. Otherwise, there exist K-sparse x1 and x2, such that x1 – x2 = 0.
  • The Restricted Isomeric Property (RIP), can be defined as:

In order to recover the signal back from a fewer number of measurements, L1 minimization is used. Here ‘y’ is an M x 1 measurement vector and ‘x’, is an N x 1 vector, where M << N. Since it is very difficult to reconstruct the original data from fewer observations, we need to go for some kind of minimization techniques. With a prior knowledge that our signal is sparse in some domain, we can use the method of Compressed Sensing along with an appropriate minimization technique to recover the original signal. L1 minimization will give us the required solution.

For any discrete signal x[n] of length N, Lp norm can be defined as:


The procedure we followed:

  • Consider an image which is sparse in the spatial domain. Sparsity is the fundamental hypothesis in Compressive Sensing.
  • Find the number of non-zero elements in the image. Let it be named as count.
  • Generate a random matrix with numbers of rows = 4 * count and number of columns same as that of the image. Let this random matrix be named A.
  • y=A * x, y=Measurement vector, A= Gaussian random vector, x=input image reshaped as a 1D vector.
  • Reconstruction of x from y: Here we have used L1 minimization and this is done with the help of cvx (convex optimization package). The reconstructed value is called as x^
  • Find the PSNR and MSE of x and x^.

An under-determined system of linear equations has more unknowns than equations and generally has an infinite number of solutions. In order to choose a solution to such a system, one must impose extra constraints or conditions (such as smoothness) as appropriate. In compressed sensing, one adds the constraint of sparsity, allowing only solutions which have a small number of nonzero coefficients. Not all under-determined systems of linear equations have a sparse solution. However, if there is a unique sparse solution to the under-determined system, then the compressed sensing framework allows the recovery of that solution.

The field of compressive sensing is related to several topics in signal processing and computational mathematics, such as under-determined linear-systems, group testing, heavy hitters, sparse coding, multiplexing, sparse sampling, and finite rate of innovation. Its broad scope and generality have enabled several innovative CS-enhanced approaches in signal processing and compression, the solution of inverse problems, the design of radiating systems, radar and through-the-wall imaging, and antenna characterization. Imaging techniques having a strong affinity with compressive sensing include the coded aperture and computational photography. Implementations of compressive sensing in hardware at different technology readiness levels are available.

This is a portion of my BTech final year project which I accomplished along with Harikrishnan NB and our guide, Ms. Gayathri Narayanan.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

Create a website or blog at WordPress.com

Up ↑

%d bloggers like this: