Computing Proximity Operators of Scale and Signed Permutation Invariant Functions

Abstract This paper investigates the computation of proximity operators for scale and signed permutation invariant functions. A scale invariant function remains unchanged under uniform scaling, while a signed permutation invariant function retains its structure despite permutations and sign changes applied to its input variables. Noteworthy examples include the $$\ell _0$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>ℓ</mml:mi> <mml:mn>0</mml:mn> </mml:msub> </mml:math> function, the ratio of $$\ell _1/\ell _2$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msub> <mml:mi>ℓ</mml:mi> <mml:mn>1</mml:mn> </mml:msub> <mml:mo>/</mml:mo> <mml:msub> <mml:mi>ℓ</mml:mi> <mml:mn>2</mml:mn> </mml:msub> </mml:mrow> </mml:math> , and its square, with their proximity operators being particularly crucial in sparse signal recovery. We delve into the properties of scale and signed permutation invariant functions, delineating the computation of their proximity operators into three sequential steps: the $${\varvec{w}}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>w</mml:mi> </mml:mrow> </mml:math> -step, r -step, and d -step. These steps collectively form a procedure termed as WRD, with the $${\varvec{w}}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>w</mml:mi> </mml:mrow> </mml:math> -step being of utmost importance and requiring careful treatment. Leveraging this procedure, we present a method for explicitly and efficiently computing the proximity operator of $$(\ell _1/\ell _2)^2$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mrow> <mml:mo>(</mml:mo> <mml:msub> <mml:mi>ℓ</mml:mi> <mml:mn>1</mml:mn> </mml:msub> <mml:mo>/</mml:mo> <mml:msub> <mml:mi>ℓ</mml:mi> <mml:mn>2</mml:mn> </mml:msub> <mml:mo>)</mml:mo> </mml:mrow> <mml:mn>2</mml:mn> </mml:msup> </mml:math> and introduce an algorithm for the proximity operator of $$\ell _1/\ell _2$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msub> <mml:mi>ℓ</mml:mi> <mml:mn>1</mml:mn> </mml:msub> <mml:mo>/</mml:mo> <mml:msub> <mml:mi>ℓ</mml:mi> <mml:mn>2</mml:mn> </mml:msub> </mml:mrow> </mml:math> . Numerical experiments on sparse signal recovery corroborate the analysis and show that first-order methods equipped with these proximity operators outperform $$\ell _1$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>ℓ</mml:mi> <mml:mn>1</mml:mn> </mml:msub> </mml:math> -based baselines in reconstruction accuracy.