Let's use the concept of hash functions and see if that helps
In this instance, think of one key that is run through different hash functions yielding several hashes. The goal of a hash function is to among other things to reduce the size of the information from the initial key: each hash is smaller bit-wise compared to the initial key.
The hash functions used in Compressive Sensing are linear functionals of the key. Random numbers are used to produce these linear functionals.It is generally difficult if not impossible to get the original key from one hash, but with Compressive Sensing it is possible to recover a key from the different hashes produces by several hash functions.When you look at the details, you'll find that the number of hash functions needed to recover the initial key is small if the initial key has some regularity (it has a lot of the same character in it, for a vector representing that key we say that it is sparse, i.e it has a lot of zeros in it).The number of hashes (produced each with a different hash function) needed to recover the initial key (and never have a collision with another key) depends on the "regularity" of the key, not on the large dimensional space in which the key resides.This is why the field is called Compressive Sensing , if you were to sense keys through different simple hash functions, then if the keys have some sorts of regularity (sparsity), the number of hash functions needed to recover these keys is proportional to the regularity of the key not the high dimensional space in which the key lives. The compression comes from the few number of hashes needed to determine uniquely a key. Compressive Sensing also provides the machinery to recover that key from several hashes
Credit: wikipedia on hash functions
Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.