GPSR Gradient Projection for Sparse Reconstruction. Many problems in signal processing and statistical inference are based on finding a sparse solution to an undetermined linear system of equations. Basis Pursuit, the Least Absolute Shrinkage and Selection Operator (LASSO), wavelet-based deconvolution, and Compressed Sensing are just a few well-known examples. Computationally, the problem can be formulated in different ways, most of them being convex optimization problems. We considered a formulation in which a penalty term involving the scaled l1-norm of the signal is added to a least-squares term, a problem that can be reformulated as a convex quadratic program with bound constraints. This problem has a potentially extremely large number of variables (though only a small fraction of them are away from their bounds at the solution) and the data that defines it can often not be stored explicitly. We found that a solver of gradient projection type, using special line search and termination techniques, gave faster solutions on our test problems than other techniques that had been proposed previously, including interior-point techniques. A debiasing step based on the conjugate-gradient algorithm improves the results further.

Keywords for this software

Anything in here will be replaced on browsers that support the canvas element