A method for finding structured sparse solutions to nonnegative least squares problems with applications. (English) Zbl 1282.90239

Esser, Ernie; Lou, Yifei; Xin, Jack

SIAM J. Imaging Sci. 6, No. 4, 2010-2046 (2013).

Summary: Unmixing problems in many areas such as hyperspectral imaging and differential optical absorption spectroscopy (DOAS) often require finding sparse nonnegative linear combinations of dictionary elements that match observed data. We show how aspects of these problems, such as misalignment of DOAS references and uncertainty in hyperspectral endmembers, can be modeled by expanding the dictionary with grouped elements and imposing a structured sparsity assumption that the combinations within each group should be sparse or even 1-sparse. If the dictionary is highly coherent, it is difficult to obtain good solutions using convex or greedy methods, such as nonnegative least squares (NNLS) or orthogonal matching pursuit. We use penalties related to the Hoyer measure, which is the ratio of the \(l_1\) and \(l_2\) norms, as sparsity penalties to be added to the objective in NNLS-type models. For solving the resulting nonconvex models, we propose a scaled gradient projection algorithm that requires solving a sequence of strongly convex quadratic programs. We discuss its close connections to convex splitting methods and difference of convex programming. We also present promising numerical results for DOAS analysis and hyperspectral unmixing problems.

MSC:

90C55	Methods of successive quadratic programming type
90C90	Applications of mathematical programming
65K10	Numerical optimization and variational techniques
49N45	Inverse problems in optimal control

Keywords:

unmixing; nonnegative least squares; basis pursuit; structured sparsity; scaled gradient projection; difference of convex programming; hyperspectral imaging; differential optical absorption spectroscopy