A fast convex conjugated algorithm for sparse recovery

Sparse recovery aims to find the sparsest solution of an underdetermined system Xβ=yXβ=y. This paper studies simple yet efficient sparse recovery algorithms from a novel viewpoint of convex conjugacy. To this end, we induce a family of convex conjugated loss functions as a smooth approximation of l0-norml0-norm. Then we apply the additive form of half-quadratic (HQ) optimization to solve these loss functions and to reformulate the sparse recovery problem as an augmented quadratic constraint problem that can be efficiently computed by alternate minimization. At each iteration, we compute the auxiliary vector of HQ via minimizer function and then we project this vector into the nullspace of the homogeneous linear system Xβ=0Xβ=0 such that a feasible and sparser solution is obtained. Extensive experiments on random sparse signals and robust face recognition corroborate our claims and validate that our method outperforms the state-of-the-art l1 minimization algorithms in terms of computational cost and estimation error.