Gradient Support Projection Algorithm for Affine Feasibility Problem with Sparsity and Nonnegativity

Abstract

Let $A$ be a real $M\times N$ measurement matrix and $b\in {\mathbb{R}}^M$ be an observations vector. The affine feasibility problem with sparsity and nonnegativity ($AF{P}_{SN}$ for short) is to find a sparse and nonnegative vector $x\in {\mathbb{R}}^N$ with $Ax=b$ if such $x$ exists. In this paper, we focus on establishment of optimization approach to solving the $AF{P}_{SN}$. By discussing tangent cone and normal cone of sparse constraint, we give the first necessary optimality conditions, $\alpha$-Stability, T-Stability and N-Stability, and the second necessary and sufficient optimality conditions for the related minimization problems with the $AF{P}_{SN}$. By adopting Armijo-type stepsize rule, we present a framework of gradient support projection algorithm for the $AF{P}_{SN}$ and prove its full convergence when matrix $A$ is $s$-regular. By doing some numerical experiments, we show the excellent performance of the new algorithm for the $AF{P}_{SN}$ without and with noise.