- 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.
Given a discrete signal or image with points, there exists a such that a minimum of measurements can be performed that map the point signal to a point transform ( is much smaller than ). The discrete signal that is being measured can be complex in nature. In such a case,
where is the input vector of length and is the row of the measurement operator , . These measurements are in most cases, random in nature. As an example, one may consider the rectangular matrix to be permuted rows of a square Walsh-Hadamard matrix .
- Reconstruction of measured signal:
The reverse problem is usually a convex optimization problem. Suppose the signal in consideration is sparse a certain basis, for instance, wavelet basis. The wavelet transformed signal must hence be sparse. The problem hence becomes
such that is the reconstructed signal and is an point wavelet transform, subject to the condition