# 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|$