This content will become publicly available on January 1, 2027

Title: 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$$ ℓ0 function, the ratio of$$\ell _1/\ell _2$$ ℓ1/ℓ2 , 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}}$$ w -step,r-step, andd-step. These steps collectively form a procedure termed as WRD, with the$${\varvec{w}}$$ w -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$$ (ℓ1/ℓ2) 2 and introduce an algorithm for the proximity operator of$$\ell _1/\ell _2$$ ℓ1/ℓ2 . Numerical experiments on sparse signal recovery corroborate the analysis and show that first-order methods equipped with these proximity operators outperform$$\ell _1$$ ℓ1 -based baselines in reconstruction accuracy.  more » « less
Award ID(s):
2208385
PAR ID:
10703161
Author(s) / Creator(s):
; ;
Publisher / Repository:
SIAM
Date Published:
Journal Name:
Journal of Optimization Theory and Applications
Volume:
208
Issue:
1
ISSN:
0022-3239
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. Abstract We study holomorphic mapsFfrom a smooth Levi non-degenerate real hypersurface$$ M_{\ell }\subset {\mathbb {C}}^n $$ Mℓ⊂Cn into a hyperquadric$$ {\mathbb {H}}_{\ell '}^N $$ Hℓ′N with signatures$$ \ell \le (n-1)/2 $$ ℓ≤(n-1)/2 and$$ \ell '\le (N-1)/2,$$ ℓ′≤(N-1)/2, respectively. Assuming that$$ N - n < n - 1,$$ N-n<n-1, we prove that if$$ \ell = \ell ',$$ ℓ=ℓ′, thenFis either CR transversal to$$ {\mathbb {H}}_{\ell }^N $$ HℓN at every point of$$ M_{\ell },$$ Mℓ, or it maps a neighborhood of$$ M_{\ell } $$ Mℓ in$$ {\mathbb {C}}^n $$ Cn into$$ {\mathbb {H}}_{\ell }^N.$$ HℓN . Furthermore, in the case where$$ \ell ' > \ell ,$$ ℓ′>ℓ, we show that ifFis not CR transversal at$$0\in M_\ell ,$$ 0∈Mℓ, then it must be transversally flat. The latter is best possible. 
    more » « less
  2. Abstract For the partition functionp(n), Ramanujan proved the striking identities$$\begin{aligned} \begin{aligned} \mathcal {P}_5(q):=\sum _{n\ge 0} p(5n+4)q^n&=5\prod _{n\ge 1} \frac{\left( q^5;q^5\right) _{\infty }^5}{(q;q)_{\infty }^6},\\ \mathcal {P}_{7}(q):=\sum _{n\ge 0} p(7n+5)q^n&=7\prod _{n\ge 1}\frac{\left( q^7;q^7\right) _{\infty }^3}{(q;q)_{\infty }^4}+49q \prod _{n\ge 1}\frac{\left( q^7;q^7\right) _{\infty }^7}{(q;q)_{\infty }^8}, \end{aligned} \end{aligned}$$ P5(q):= ∑n≥0 p(5n+4)qn =5 ∏n≥1 q5;q5∞5 (q;q)∞6 , P7(q):= ∑n≥0 p(7n+5)qn =7 ∏n≥1 q7;q7∞3 (q;q)∞4 +49q ∏n≥1 q7;q7∞7 (q;q)∞8 , where$$(q;q)_{\infty }:=\prod _{n\ge 1}(1-q^n).$$ (q;q)∞ := ∏n≥1 (1-qn). As these identities imply his celebrated congruences modulo 5 and 7, it is natural to seek, for primes$$\ell \ge 5,$$ ℓ≥5, closed form expressions of the power series$$ \mathcal {P}_{\ell }(q):=\sum _{n\ge 0} p(\ell n-\delta _{\ell })q^n\pmod {\ell }, $$ Pℓ(q):= ∑n≥0 p (ℓn-δℓ) qn (modℓ) , where$$\delta _{\ell }:=\frac{\ell ^2-1}{24}.$$ δℓ:= ℓ2-124 . In this paper, we prove that$$ \mathcal {P}_{\ell }(q)\equiv c_{\ell } \dfrac{\mathcal {T}_{\ell }(q)}{\left( q^\ell ; q^\ell \right) _\infty } \pmod {\ell }, $$ Pℓ(q)≡cℓ Tℓ(q) qℓ;qℓ∞ (modℓ) , where$$c_{\ell }\in \mathbb Z$$ cℓ∈Z is explicit and$${\mathcal {T}}_{\ell }(q)$$ Tℓ(q) is the generating function for the Hecke traces of$$\ell $$ ℓ -ramified values of special Dirichlet series for weight$$\ell -1$$ ℓ-1 cusp forms on$$\textrm{SL}_2(\mathbb Z)$$ SL2(Z) . This is a new proof of Ramanujan’s congruences modulo 5, 7, and 11, as there are no nontrivial cusp forms of weight 4, 6, and 10. 
    more » « less
  3. Abstract LetXbe a compact normal complex space of dimensionnandLbe a holomorphic line bundle onX. Suppose that$$\Sigma =(\Sigma _1,\ldots ,\Sigma _\ell )$$ Σ=(Σ1,…,Σℓ) is an$$\ell $$ ℓ -tuple of distinct irreducible proper analytic subsets ofX,$$\tau =(\tau _1,\ldots ,\tau _\ell )$$ τ=(τ1,…,τℓ) is an$$\ell $$ ℓ -tuple of positive real numbers, and let$$H^0_0(X,L^p)$$ H00(X,Lp) be the space of holomorphic sections of$$L^p:=L^{\otimes p}$$ Lp:=L⊗p that vanish to order at least$$\tau _jp$$ τjp along$$\Sigma _j$$ Σj ,$$1\le j\le \ell $$ 1≤j≤ℓ . If$$Y\subset X$$ Y⊂X is an irreducible analytic subset of dimensionm, we consider the space$$H^0_0 (X|Y, L^p)$$ H00(X|Y,Lp) of holomorphic sections of$$L^p|_Y$$ Lp |Y that extend to global holomorphic sections in$$H^0_0(X,L^p)$$ H00(X,Lp) . Assuming that the triplet$$(L,\Sigma ,\tau )$$ (L,Σ,τ) is big in the sense that$$\dim H^0_0(X,L^p)\sim p^n$$ dimH00(X,Lp)∼pn , we give a general condition onYto ensure that$$\dim H^0_0(X|Y,L^p)\sim p^m$$ dimH00(X|Y,Lp)∼pm . WhenLis endowed with a continuous Hermitian metric, we show that the Fubini-Study currents of the spaces$$H^0_0(X|Y,L^p)$$ H00(X|Y,Lp) converge to a certain equilibrium current onY. We apply this to the study of the equidistribution of zeros inYof random holomorphic sections in$$H^0_0(X|Y,L^p)$$ H00(X|Y,Lp) as$$p\rightarrow \infty $$ p→∞ . 
    more » « less
  4. Abstract A family ofrdistinct sets$$\{A_1,\ldots , A_r\}$$ {A1,…,Ar} is anr-sunflower if for all$$1 \leqslant i < j\leqslant r$$ 1⩽i<j⩽r and$$1 \leqslant i' < j'\leqslant r$$ 1⩽i′<j′⩽r , we have$$A_i\cap A_j = A_{i'}\cap A_{j'}$$ Ai∩Aj=Ai′∩Aj′ . Erdős and Rado conjectured in 1960 that every family$$\mathcal {H}$$ H of$$\ell $$ ℓ -element sets of size at least$$K(r)^\ell $$ K(r)ℓ contains anr-sunflower, whereK(r) is some function that depends only onr. We prove that if$$\mathcal {H}$$ H is a family of$$\ell $$ ℓ -element sets of VC-dimension at mostdand$$|\mathcal H| > (C r(\log d+\log ^*\ell ))^\ell $$ |H|> (Cr(logd+log∗ℓ)) ℓ for some absolute constant$$C > 0$$ C>0 , then$$\mathcal {H}$$ H contains anr-sunflower. This improves a recent result of Fox, Pach, and Suk. When$$d=1$$ d=1 , we obtain a sharp bound, namely that$$|\mathcal H| > (r-1)^\ell $$ |H|>(r-1) ℓ is sufficient. Along the way, we establish a strengthening of the Kahn–Kalai conjecture for set families of bounded VC-dimension, which is of independent interest. 
    more » « less
  5. Abstract In this paper, we analyze the theta series associated to the quadratic form$$Q(\vec {x}) :=x_1^2+x_2^2+x_3^2+x_4^2$$ Q (x→) :=x12+x22+x32+x42 with congruence conditions on$$x_i$$ xi modulo 2, 3, 4 and 6. By employing special operators on modular, non-holomorphic Eisenstein series of weight 2, we construct a basis for Eisenstein space for levels$$2^k, k\le 7$$ 2k,k≤7 ,$$3^{\ell }, \ell \le 3$$ 3ℓ,ℓ≤3 andp, for odd primep. Using the relation between the trace of Frobenius on an elliptic curve and the Fourier coefficients of the cusp form part of theta series corresponding toQ, we establish relation between the number of integer solutions to the equation$$Q(\vec {x}) = p$$ Q(x→)=p and the number of$$\mathbb {F}_p$$ Fp -rational points on the associated elliptic curve under certain congruence conditions onp. 
    more » « less