Sparse Recovery Using Scale and Signed Permutation Invariant Functions

Recovering sparse signals from limited and noisy measurements is an important problem in modern data processing. Traditional methods, which often rely on convex relaxations such as the $\ell_1$ norm, struggle in scenarios with high coherence or large dynamic ranges. A major challenge in these settings is to develop a unified and computationally efficient framework that can accommodate a broad class of sparsity-promoting functions. In this dissertation, we overcome these challenges by introducing a general framework for all scale and signed permutation invariant functions. This dissertation has three main parts. In the first part, we introduce the $(\ell_1/\ell_2)^2$-model for sparse recovery and analyze its properties using fractional programming techniques and Dinkelbach’s procedure, leading to efficient solution algorithms with convergence guarantees. In the second part, we develop a systematic procedure termed the WRD procedure to compute the proximity operators for any function that is scale and signed permutation invariant. This procedure decomposes the computation into three intuitive steps, thereby bridging theory and algorithmic design practice. In the third part, we integrate the derived proximity operators into state-of-the-art optimization frameworks, including Accelerated Proximal Gradient and the Alternating Direction Method of Multipliers, and demonstrate their effectiveness in compressive sensing and image restoration through extensive numerical experiments.