An improved FOCUSS-based learning algorithm for solving sparse linear inverse problems

We develop an improved algorithm for solving blind sparse linear inverse problems where both the dictionary (possibly overcomplete) and the sources are unknown. The algorithm is derived in the Bayesian framework by the maximum a posteriori method, with the choice of prior distribution restricted to the class of concave/Schur-concave functions, which has been shown previously to be a sufficient condition for sparse solutions. This formulation leads to a constrained and regularized minimization problem which can be solved in part using the FOCUSS (focal underdetermined system solver) algorithm for vector selection. We introduce three key improvements in the algorithm: an efficient way of adjusting the regularization parameter; column normalization that restricts the learned dictionary; reinitialization to escape from local optima. Experiments were performed using synthetic data with matrix sizes up to 64/spl times/128; the algorithm solves the blind identification problem, recovering both the dictionary and the sparse sources. The improved algorithm is much more accurate than the original FOCUSS-dictionary learning algorithm when using large matrices. We also test our algorithm on natural images, and show that a learned overcomplete representation can encode the data more efficiently than a complete basis at the same level of accuracy.