Compressed sensing (CS) is a theory which states that, assuming some conditions are met, a vector can be compressed and sampled simultaneously (hence the name).
Assume we have a signal x ∈ R^{N}. We further assume that there exists an invertible N × N transform matrix Ψ such that
x = Ψs  (1) 
where s is a Ksparse vector, i.e., ‖s‖_{0} = K with K < N, and where ‖·‖_{p} represents pnorm. This means that the image has a sparse representation in some transformed domain, e.g., wavelet. The signal is measured by taking M < N linear combinations as
y = Φx = Φs = Ψ̃s  (2) 
It would initially seem that since M < N there would be no way to recover x. However, it was proven that if the measurement matrix Φ is sufficiently incoherent with respect to the sparsifying matrix Ψ, and K is smaller than a given threshold (i.e., the sparse representation s of the original signal x is “sparse enough”), then the original x can be recovered by finding the sparsest solution that satisfies (2). However, the problem above is, in general, NPhard, but if Ψ̃ obeys the restricted isometry principal (RIP), then the original signal can be determined through the optimization problem
P1: minimize ‖s‖_{1} 

(3) 
where ϵ is a small tolerance.
Note that problem P1 is a convex optimization problem. The reconstruction complexity is O(M^{2}N^{3⁄2}) if the problem is solved using interior point methods.
For more information about applications of compressed sensing:
 Recovery of Audio Signals with Compressed Sensing
 Compressed Sensing of Images
 Noise Resiliency with Compressed Sensing
 Interference Cancellation in Compressed Sensed Signals
 Adaptive Parity Error Detection for Compressive Imaging
 Multipath Channel Estimation with Compressed Sensing
 Overview of Encryption of Compressed Sensed Images
 Gradient Projection Reconstruction of Compressed Sensing Signals
 Error Correction Using Compressed Sensing Techniques