Just as in the noiseless case, these two problems are NP-Hard in general, but can be approximated using pursuit algorithms. More specifically, changing the to an -norm, we obtain which is known as the basis pursuit denoising. Similarly, matching pursuit can be used for approximating the solution of the above problems, finding the locations of the non-zeros one at a time until the error threshold is met. Here as well, theoretical guarantees suggest that BP and MP lead to nearly optimal solutions depending on the properties of and the cardinality of the solution . Another interesting theoretical result refers to the case in which is a unitary matrix. Under this assumption, the problems posed above (with either or ) admit closed-form solutions in the form of non-linear shrinkage. Variations There are several variations to the basic sparse approximation problem. Structured sparsity: In the original version of the problem, any of the atoms in the dictionary can be picked. In the structured (block) sparsity model, instead of picking atoms individually, groups of them are to be picked. These groups can be overlapping and of varying size. The objective is to represent such that it is sparse while forcing this block-structure. Collaborative (joint) sparse coding: The original version of the problem is defined for a single signal . In the collaborative (joint) sparse coding model, a set of signals is available, each believed to emerge from (nearly) the same set of atoms from . In this case, the pursuit task aims to recover a set of sparse representations that best describe the data while forcing them to share the same (or close-by) support. Other structures: More broadly, the sparse approximation problem can be cast while forcing a specific desired structure on the pattern of non-zero locations in . Two cases of interest that have been extensively studied are tree-based structure, and more generally, a Boltzmann distributed support. Algorithms As already mentioned above, there are various approximation (also referred to as pursuit) algorithms that have been developed for addressing the sparse representation problem: We mention below a few of these main methods. Matching pursuit is a greedy iterative algorithm for approximately solving the above problem. It works by gradually finding the locations of the non-zeros in one at a time. The core idea is to find in each step the column (atom) in that best correlates with the current residual (initialized to ),