<< lft_version | CCA (Computational Convex Analysis) | pl_me_pe_2d >>

CCA (Computational Convex Analysis) >> CCA (Computational Convex Analysis) > pl_me_pe

# pl_me_pe

Moreau envelope, Parabolic Envelope algorithm

### Calling Sequence

    M = pl_me_pe(x0,xn,f)

### Parameters

x0

  real number. Lower bound of the interval.

xn

  real number. Upper bound of the interval.

f

  column vector. The value of the function on the grid X=(x0:h:xn)'; where n=length(f), and h=(xn-x0)/(n-1); so f(i)=fu(X(i)) for some function fu.

M

  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)

### Description

Compute numerically the discrete Moreau envelope of a set of planar points (X(i),f(i)) at slopes S(j)=X(j), i.e.

    2
    M(j) = min f(i) + || s(j) - x(i) ||.
    i

It reduces computation to a 1,..,n grid with

    2               2                    2
    M(j)= h * min [ ||j-i|| + f(x_0 + i * h) / h  ]
        i

The algorithms runs in linear time Theta(n) with n=length(X)=length(f) by computing the lower parabolic envelope (PE).

### Examples

    X=[-5:0.5:5]';
    Y=X.^2;
    M=pl_me_pe(-5,5,Y)

### See Also

- pl_me_pe_2d
- pl_me_direct
- pl_me_llt
- pl_me_nep

### Authors

`Yves Lucet`, University of British Columbia, BC, Canada

### Bibliography

- Y. Lucet, 2007, Fast Moreau Envelope Computation I: Numerical Algorithms, Numerical Algorithms, 43(3):235-249.
- P. F. Felzenszwalb and D. P. Huttenlocher, 2004, Distance transforms of sampled functions, Tech. Rep. TR2004-1963, Cornell Computing and Information Science.

<< lft_version | CCA (Computational Convex Analysis) | pl_me_pe_2d >>