Computing Proximity Operators of Scale and Signed Permutation Invariant Functions
研究了尺度和符号置换不变函数的邻近算子计算，提出WRD三步法，并给出(ℓ1/ℓ2)^2的显式公式和ℓ1/ℓ2的算法，实验表明在稀疏信号恢复中优于ℓ1方法。
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.