Robust method for finding sparse solutions to linear inverse problems using an L2 regularization

Representation of time-varying signals in terms of a sparse set of atoms from an overcomplete dictionary is important in machine learning, and it has been proposed as one of the fundamental computations of the nervous system. Reconstruction algorithms create an estimate of the observed signal using the appropriate weighted atoms of an overcomplete dictionary. The overcompleteness of the dictionary creates a situation where there are multiple sets of dictionary atoms that reconstruct the signal equally well. Under these conditions, a solution that minimizes the number of dictionary atoms that have a nonzero contribution to the signal is preferred. Directly finding the solution that minimizes the number of atoms used from the dictionary or L0 norm is an NPcomplete problem, making it intractable even for moderately sized dictionaries. However, it has been shown that under very general conditions the solution that minimizes the sum of the absolute values of the contributions of the dictionary atoms or L1 norm can be used to identify the sparsest solution[Don06]. Although there is no analytical expression for the minimal L1 norm solution, there are effective algorithms for finding L1 minimal solutions, which has triggered an explosion of interest in the use of the L1 norm for sparse reconstructions.