Compressed Sensing

  1. Formulating the problem statement:

    There are essentially two ways to ‘compress’ data. Analog data is generally sampled and then quantized. The quantization process is called encoding. Conventionally, there are several encoding techniques in place which give optimal data compression, bounded by Shannon’s compression limit. More recently, however, people have concentrated on optimum techniques of sampling the data. It can be postulated that if the data is ‘sparse’ in a certain basis, then very few measurements are required to sample the data (typically much lesser than the Nyquist rate), which can later be reconstructed with very low margin of error.

  2. Measurement:

    Given a discrete signal or image with n points, there exists a k such that a minimum of m measurements can be performed that map the n point signal to a m point transform (m is much smaller than n). The discrete signal that is being measured can be complex in nature. In such a case,

    b_i = |\left\langle A_i,x \right\rangle|

    where x is the input vector of length n and A_i is the i'th row of the measurement operator A_{m \times n}, i = 1....m. These measurements are in most cases, random in nature. As an example, one may consider the rectangular matrix A to be m permuted rows of a square Walsh-Hadamard matrix \Omega_{n \times n}.

  3. Reconstruction of measured signal:

    The reverse problem is usually a convex optimization problem. Suppose the signal in consideration x is sparse a certain basis, for instance, wavelet basis. The wavelet transformed signal must hence be sparse. The problem hence becomes

    min ||Wx'||_1

    such that x' is the reconstructed signal and W is an n point wavelet transform, subject to the condition

    b_i = |\left\langle A_i,x' \right\rangle|


Leave a Reply

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

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

Google photo

You are commenting using your Google 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