## Name

pl_me_direct_2d — [For comparison only] 2D Moreau envelope, direct computation

## Calling Sequence

    M = pl_me_direct_2d(Xr,Xc,f,Sr,Sc)

## Parameters

Xr

  column vector of length n.

Xc

  column vector of length m.

f

  matrix of size nxm. The function f is sampled on a grid Xr x Xc so f(i,j)=fu(Xr(i),Xc(j)) for some function fu.

Sr

  column vector of size m1.

Sc

  column vector of size m2. The Moreau envelope is computed on a grid SrxSc.

M

  matrix of size m1xm2 containing the Moreau envelope of the function f.

## Description

Warning: This function is provided only for comparison purposes and unit testing, use more efficient linear-time algorithms for faster computation.

Compute numerically the discrete Moreau envelope of a set of spatial points (Xr(i1),Xc(i2),f(i1,i2)) at slopes (Sr(j1),Sc(j2)), i.e.

                                                     2                   2
        M(j1,j2) =  min [ f(i1,i2) + (Sr(j1) - Xr(i1) + (Sc(j2) - Xc(i2))  ].
                   i1,i2

It uses the separability of the square Euclidean norm to reduce the worst-case time complexity for a grid of size N=n^2 from a brute force computation of O(N^2)=O(n^4) to O(N^(3/2)) = O(n^3), when n=length(Xr)=length(Xc)=length(Sr)=length(Sc).

## Examples

            function f=f(lambda,x),f=lambda * x.^2,endfunction
            function g=g(lambda1,lambda2,x,y),g=f(lambda1,x)+f(lambda2,y),endfunction
            lambda1=1;lambda2=2;
            x1=(-10:10)';x2=(-5:5)';
            [X, Y]=ndgrid(x1,x2);F=g(lambda1,lambda2,X,Y);
            s1=(-4:4)';s2=(-5:6)';
            Xr=x1;Xc=x2;Sr=s1;Sc=s2;
            desired=pl_me_direct_2d(x1,x2,F,s1,s2);
            //1d computation for separable function
            Ms1=pl_me_direct(x1,f(lambda1,x1),s1);
            Ms2=pl_me_direct(x2,f(lambda2,x2),s2);
            t1 = Ms1 * ones(1,size(Ms2,1));
            t2 = ones(size(Ms1,1),1) * Ms2';
            correct=t1+t2;
            b = and(correct == desired);

## See Also

pl_me_brute_2d , pl_me_llt_2d , pl_me_nep_2d , pl_me_pe_2d , pl_me_direct

## Authors

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

## Bibliography

See pl_me_direct

## Used Functions

Computation is reduced to one dimension, which is then handled by pl_me_direct.