pl_me_nep — Moreau envelope for convex functions, NEP algorithm
[M,P] = pl_me_nep(X,f,S)
column vector. A grid of points on which the function is sampled.
column vector. The value of the function on the grid X: usually f(i)=fu(X(i)) for some function fu.
column vector. The grid on which we want to compute the conjugate: f* is evaluated on S.
column vector. Contains the value of the Moreau envelope M of the function f evaluated on at the points S(j). In other words: M(j) = Min(||S(j) - X(i)||^2 + f(i) | over all indexes i)
proximal mapping, P(j)=Argmin(||S(j) - X(i)||^2 + f(i) | over all indexes i)
Compute numerically the discrete Moreau envelope of a set of planar points (X(i),f(i)) at slopes S(j), i.e.
2 M(j) = min f(i) + || s(j) - x(i) ||. i 2 P(j) = Argmin f(i) + || s(j) - x(i) ||. i
It uses the non-expansiveness of the proximal (NEP) mapping P to run in linear time theta(n+m) with n=length(X)=length(f) and m=length(S).
The algorithm only returns correct result when the proximal mapping P is nonexpansive
. Otherwise, the algorithms may
return an incorrect result. Classes of functions f that have a nonexpansive proximal mapping include convex
functions and
prox-regular
functions.