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 xRN. We further assume that there exists an invertible N × N transform matrix Ψ such that

 x = Ψs (1)

where s is a K-sparse vector, i.e., ‖s0 = K with K < N, and where ‖·‖p represents p-norm. 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, NP-hard, but if Ψ̃ obeys the restricted isometry principal (RIP), then the original signal can be determined through the optimization problem

 P1: minimize ‖s‖1
 subject to :‖y – Ψ̃s‖ 2 < ϵ 2
(3)

where ϵ is a small tolerance.

Note that problem P1 is a convex optimization problem. The reconstruction complexity is O(M2N32) if the problem is solved using interior point methods.