Site Map
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 ∈ RN. 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., ‖s‖0 = 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 |
|
(3) |
where ϵ is a small tolerance. Note that problem P1 is a convex optimization problem. The reconstruction complexity is O(M2N3⁄2) if the problem is solved using interior point methods.
To learn more about various applications of compressed sensing, check out the following links: