<< pl_me_llt | CCA (Computational Convex Analysis) | pl_me_nep >>

CCA (Computational Convex Analysis) >> CCA (Computational Convex Analysis) > pl_me_llt_2d

# pl_me_llt_2d

2D Moreau envelope, LLT algorithm

### Calling Sequence

    [M,g,Conjpartial,Conj] = pl_me_llt_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.

g

  matrix of size nxm containing the function g (see formula below).

Conjpartial

  matrix containing the partial conjugate of the function g i.e. the one dimensional conjugate applied to each row.

Conj

  matrix of size m1xm2 containing the conjugate of the function g (see formula below).

### Description

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 reduces computation to one dimension, and computes the Legendre conjugate through the formula

    2                                                      2
    M(j) = s(j) - 2 g*(j) with g*(j) = max [ s(j) * x(i) - 1/2 * (x(i) + f(i)) ]
                             i

thereby resulting in a theta(n*m + m1*m2) linear-time algorithm.

### 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_llt_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_direct_2d
- pl_me_nep_2d
- pl_me_pe_2d
- pl_me_llt

### Authors

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

### Bibliography

See pl_me_llt

### Used Functions

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

<< pl_me_llt | CCA (Computational Convex Analysis) | pl_me_nep >>