Sparse Image Recovery under Non-convex ℓp/ℓq Ratio Regularisation

Abstract

We study sparse image recovery under the non-convex ℓp/ℓq ratio regularisation, a generalisation of the classical ℓ1/ℓ2 ratio. The problem is non-convex and non-smooth, and arises in compressed-sensing image reconstruction and sparse-representation-based classification. A genuine Gauss–Seidel coordinate-descent solver is proposed, which operates on signed variables, introduces no auxiliary variable, and requires only a single hyper-parameter. A small positive offset is added to the denominator to keep the ratio well-defined at the origin. At every coordinate update the residual gradient and the denominator weight are refreshed on-line, reducing the per-coordinate sub-problem to a standard $\ell _p^p$ prox that admits a closed form for the canonical low values of p and a smoothed inverse-power IRL1 update for any other p. A convergence guarantee is established for the surrogate iterates, and a separate remark addresses the surrogate-consistency gap to the original ratio problem. Across three experimental phases the six GS-ℓp/ℓq variants match or exceed the strongest baseline on all five classification datasets, gain +1.5dB over the ℓ1/ℓ2 ADMM baseline on BSD68 denoising, and run one to two orders of magnitude faster per reconstruction. Code and data are released with the paper.