Convex optimisation matlab toolbox: user guide
Contents
1. 1 tol ly alle 1 tol default le 3 param verbose Log parameter 0 no log 1 a summary at convergence 2 print main steps default 1 JULY 2012 9 16 LTS2 EPFL 6 EXAMPLES 5 4 Sum of proximal operator This function allows the user to solve the proximal operator of K functions K ol prox y g min x 2 3 A wngn 2 n 1 The associated Matlab function prox_sumG takes three parameters sol prox_sumG x lambda param param is a Matlab structure that containing a set of parameters The following two fields are specific to the prox_sumG function param w w the weight all equal by default Note that D param W i 1 G is an array of structures representing the functions gj 92 gK Each of these structures needs at least two fields G i norm and G i prox with i 1 2 K The former is a Matlab function that takes as input a vector x RY and returns the value f x the latter is a Matlab function that takes as input a vector RY a strictly positiv real number T and returns the vector prox 1 In Matlab write G i prox x T prox_gi x T where prox_gi x T solves the problem prox z given in equation 3 param gamma step size parameter y for the generalized forward backward algorithm This constant should satisfy y e 2 8 e for e 0 1 param epsilon This parameter is used to define the stopping criterion of the problem The2. TV_ norm This function compute the TV norm of x x llzllrv norm_ nuclear This function compute the nuclear norm of x x l Table 5 List of norm functions JULY 2012 15 16 LTS2 EPFL REFERENCES References 1 D Gabay Applications of the method of multipliers to variational inequalities in Augmented Lagrangian Methods Applications to the Numerical Solution of Boundary Value Problems M Fortin and R Glowinski Eds Amsterdam North Holland 1983 pp 299 331 2 P Tseng Applications of a splitting algorithm to decomposition in convex programming and variational inequalities SIAM J Control Optim vol 29 pp 119 138 1991 3 P L Combettes and V R Wajs Signal recovery by proximal forward backward splitting Multiscale Modeling and Simulation vol 4 no 4 pp 1168 1200 Nov 2005 4 J Douglas and H H Rachford On the numerical solution of heat conduction problems in two or three space variables Trans Amer Math Soc vol 82 pp 421 439 1956 5 P L Lions and B Mercier Splitting algorithms for the sum of two nonlinear operators SIAM J Numer Anal vol 16 pp 964 979 1979 6 J Eckstein and D P Bertsekas On the Douglas Rachford splitting method and the proximal point algorithm for maximal monotone operators Math Programming vol 55 pp 293 318 1992 7 P L Combettes Solving monotone inclusions via compositions of no
3. the linear operator L can be defined in a matrix form F i L By default the identity matrix is chosen Finally param contains a list of parameters The list of parameters is described in Section 4 5 The following two fields are specific to the sdmm function param gamma step size parameter y This constant should satisfy y e 2 6 e for e 0 min 1 1 8 4 5 General optional parameter for solvers The optional parameter param can be used to tune most of the functions in the toolbox see section 7 The table 4 5 summarizes the principal optional parameters Parameter Explanation Default value param epsilon This parameter is used to define the stopping crite 107 rion of the problem The algorithm stops if fA f t 1 ner ee f t where f t is the function to be minimized at itera tion t e R param max_iter The maximum number of iterations 200 param verbose Log parameter 0 no log 1 a summary at conver 1 gence 2 print main steps Table 1 Optional parameter for solvers JULY 2012 5 16 LTS2 EPFL 5 PROXIMAL OPERATORS 5 Proximal operators 5 1 Presentation of different norms Usual proximal operator minimize norm In the following table we present the main of them For a continuous signal x t defined on a open set Q C R we define different norms in table 2 For a discrete signal x n with n 1 2 N we also define norms in table 2 Na
4. Prox_ Linf fy norm proximal operator Solve X lambda i param min lle 213 AlE e l T prox_ TV TV norm proximal operator Solve Xx lambda param wd 2 min ll 213 Allallrv a 2 prox_ TV3D TV norm proximal operator in 3 dimension Solve X lambda param gl 2 min ll 213 Allllrv z 2 prox_L12 12 norm proximal operator Solve X lambda param sl 2 min 5 a 2113 Allali2 x 2 prox_Llinf 1 norm proximal operator Solve X lambda param 2 1 2 min lx 2113 Alla 1c0 x 2 prox_Nuclear_ Norm norm proximal operator Solve X lambda param gol 2 min gt 213 Alla 22 ProjB1 Projection on Bl ball lambda is an unused param x lambda eter for compatibility reasons Solve param min lle z st lali lt e x ProjB2 Projection on B2 ball lambda is an unused param x lambda eter for compatibility reasons Solve param min lle 2115 st zllo lt e zx sum_ proxG Compute the proximal operator of a sum of functions x lambda Solve param min 0 5 x la zl A gt Gilx 2 Table 4 List of proximal operators JULY 2012 14 16 LTS2 EPFL 7 SUMMARY OF ALL FUNCTIONS Function Explanation Argument normL12 This function compute the 2 norm of x The group x g_d g_t ensemble is denoted G l li2 gt gt llzgll2 gEG normLlinf This function compute the norm of x The group x g_d g_t ensemble is denoted G l lli IZ ollo gEG
5. be formulated s min t7 a lrv st b Aallo lt e 13 JULY 2012 10 16 LTS2 EPFL 6 EXAMPLES with x RM The reconstructed image is I f s This problem is solved with DR algorithm To apply this algorithm 13 is split into two sub functions f and fo fi is the TV norm fi llrv Xlv 14 fo is the indicator function of the convex set S ax Ax b lt e i e B2 ball of radius e centred in b It is defined by 0 if Am bll2 lt 15 co otherwise fo ica Note that the proximal operator of f is a projection onto the set S The solution of the problem is shown on figure 1 See the code Example douglas rachford m for more details Original image Depleted image Reconstructed image Figure 1 Inpainting demonstration with Douglas Rachford 50 percent of the pixels have been removed e 107 6 2 Example 2 denoising Here the goal is to remove a Gaussian noise on the image Tree assumptions have been made The image is not very different from the measurement It has a small TV norm and its Haar wavelet s decomposition is sparse Definition are the same as in example 1 with a difference b t 1 G 0 with G 0 a M x M matrix made of o variance random Gaussian noise The problem can be expressed with this equation s min bl 71 gt X llev 72 HC 16 where H Image decompose the image in Haar wavelet and X t a The denoised
6. image is Taf Ma As there are three functions in this problem it s not possible to apply directly the forward backward algorithm which require only two functions But this problem can be solve with a generalized forward backward algorithm Two functions are be defined g1 T X rv and g2 72 H X 1 Solving 16 is equivalent as searching the solution of the proximal operator on g g2 x The function sum_proxG in the toolbox find the solution of the proximal operator of a sum of function Thus it is called to solve 16 The solution is shown on figure 2 For more details see Example_ prox _multi_function m JULY 2012 11 16 LTS2 EPFL 6 EXAMPLES Original image Reconstructed image ES F es Figure 2 Denoising demonstration with generalized forward backward splitting The noise is Gaussian with o 10 7 20 et 12 3 JULY 2012 12 16 LTS2 EPFL 7 SUMMARY OF ALL FUNCTIONS 7 Summary of all functions Function Explanation Argument douglas rachford This function solves the optimization problem of minimizing the sum of f and f2 using the Douglas Rachford algorithm Both functions have to be con vex min fi x fo x x0 fl f2 param forward_ backward This function solves the optimization problem of minimizing the sum of f and fz using the forward backward algorithm Both functions have to be con vex and one needs to be Lipsch
7. main steps default 1 Other specific parameters are described for each prox function lt 5 2 1 f norm proximal operator The norm proximal operator solves the problem sarl prox py 2 min 5 lle zl Alt 6 The associated Matlab function prox_L1 is function sol prox_L1 x lambda param The following fields of param are specific to the prox_L1 function param Psit Operator Y default Id param Psi Adjoint of Y Y default Id param tight 1 if Y is a tight frame or 0 if not default 1 param nu v is a bound on the norm of the operator Y i e Wa lt v x default 1 param weights weights for a weighted Ll norm default 1 5 2 2 2 norm proximal operator The 2 norm proximal operator solves the problem 1 Prox J 2 min 5 x 2112 Allzll12 The associated Matlab function prox_L12 is function sol prox_L12 x lambda param The following fields of param are specific to the prox_L12 function param g_d contains the indices of the elements to be grouped row vector param g_t contains the size of the different group row vector param g_b just call back perm g_d This argument is optional but it may accelerate the algorithm parm multi_group in order to use group with overlap activate the multi_ group option set it to 1 default 0 param weights2 weights for a weighted 2 norm works on the norm 2 default
8. ones param weights1 weights for a weighted 2 norm works on the norm default ones Example param g_d and param g_t Suppose we have x 21 2 3 4 5 6 we want to group 21 2 14 05 and 13 16 Then we set param g_d 1 2 4 5 3 6 and param g_t 4 2 It is also possible to set param g_d 4 5 3 6 1 2 and param g_t 2 4 Overlaping group In order to make overlapping group param g_d param g_t must be vectors of non overlapping group Example param g_d g_d1 g_d2 g_dn param g t g_t1 g_t2 g_tn There must be no overlap in g_d1 g_d2 g_dn JULY 2012 7 16 LTS2 EPFL 5 PROXIMAL OPERATORS 5 2 3 i norm proximal operator The fioo norm proximal operator solves the problem 1 2 PrOX 1112 2 min lx z 2 Allzll10o The associated Matlab function prox_Llinf is function sol prox_Llinf x lambda param The following fields of param are specific to the prox_L1iinf function param g_d contains the indices of the elements to be grouped row vector param g_t contains the size of the different group row vector param g_b just call back perm g_d This argument is optional but it may accelerate the algorithm parm multi_group in order to use group with overlap activate the multi_ group option set it to 1 default 0 param weights2 weights for a weighted 2 norm works on the norm 2 default ones param weights1
9. Example Opa la a ae e ee Se ae ee 10 6 2 Example 2 denoising ee 11 7 Summary of all functions 13 References 16 JULY 2012 i LTS2 EPFL 3 SOLVER 1 Introduction This toolbox is designed to solve convex optimization problems of the form min f x fo z 1 TERN or more generally TERN K min 5 Talt 2 where the f are lower semi continuous convex functions from R to o0 00 We assume limy 2 00 sa fate oo and the f have non empty domains where the domain of a func tion f is given by domf x R f a lt 00 In problem 2 and when both f and f2 are smooth functions gradient descent methods can be used to solve 1 however gradient descent methods cannot be used to solve 1 when f and or fa are not smooth In order to solve such problems more generally we implement several algorithms including the forward backward algorithm 1 3 and the Douglas Rachford algorithm 4 8 Both the forward backward and Douglas Rachford algorithms fall into the class of proximal splitting algorithms The term proximal refers to their use of proximity operators which are generalizations of convex projection operators The proximity operator of a lower semi continuous convex function f RN R is defined by proxy x argmin Ske yl a 3 Note that the minimization problem in 3 has a unique solution for every x RY so prox f RY RY is w
10. LTS2 EPFL CONTENTS UNLOCBOX SHORT USER GUIDE MATLAB CONVEX OPTIMIZATION TOOLBOX Lausanne July 2012 PERRAUDIN Nathana l SHUMAN David VANDERGHEYNST Pierre and Puy Gilles LTS2 EPFL Contents 1 Introduction 1 2 Installation and initialisation 1 3 Solver 1 3 1 Forward backward algorithm o e 1 3 2 Douglas Rachford uses aa o rd a ee ew a 2 4 The Douglas Rachford Algorithm 2 4 1 Alternating direction method of multipliers ADMM 3 4 2 Forward backward algorithm e 4 4 3 Generalized Douglas Rachford or parallel proximal algorithm PPXA 4 4 4 Simultaneous direction method of multipliers SDMM 5 4 5 General optional parameter for solvers 2 o 000000 eee 5 5 Proximal operators 6 5 1 Presentation of different norms aoaaa eee ee ee 6 5 2 Norm proximal operators 6 5 2 1 amp norm proximal operator e T 5 2 2 i2 norm proximal operator e T 5 2 3 i norm proximal operator e 8 5 2 4 TV norm proximal Operator e 8 5 2 5 3D TV norm proximal operator o 8 5 2 6 Nuclear norm proximal operator 0000 ee eee 9 Did Projection Operator oae manda a bd be ed ae Oa AAA 9 5 3 1 Projection on Bl ball us 64 GAA EERE ee E E 9 9 32 Projection on B2 ball esse ace ae Ee ree a PE ere 9 5 4 Sum of proximal operator o ee a e 2 ee aa a a aa a a ae a a aa 10 6 Examples 10 Oil
11. THE DOUGLAS RACHFORD ALGORITHM The convergence of the Douglas Rachford algorithm is analyzed in 7 Corollary 5 2 and 8 Theorem 20 which also show that the algorithm can be accelerated by allowing the step size to change at every iteration of the algorithm Note that while the Douglas Rachford algorithm does not require any smoothness assumptions on f or f2 it requires two proximal steps at each iteration as compared to one proximal step per iteration for the forward backward algorithm The associated Matlab function douglas_rachford takes four parameters function sol douglas_rachford x0 f1 f2 param As in Section 3 1 x0 RY is the starting point for the algorithm f1 and f2 are two Matlab structures that represent the functions f and f2 The Matlab structure f1 contains the fields f1 norm and f1 prox The former is a Matlab function that takes as input a vector x RY and returns the value f x the latter is a Matlab function that takes as input a vector x RY a strictly positiv real number 7 and returns the vector prox y 1 The Matlab structure 2 contains the exact same fields but for the function f2 Finally param contains a list of parameters The list of parameters is described in Section 4 5 The following two fields are specific to the douglas_rachford function param lambda A acts as a stepsize parameter Let e 0 1 A should be in the interval e 2 e Its default value is 1 param ga
12. algorithm stops if f t f t 1 F t where f t is the function to be minimized at iteration t e R4 default 107 param max_iter The maximum number of iterations default 100 param verbose Log parameter 0 no log 1 a summary at convergence 2 print main steps default 1 param lambda_t A weight of the update term e 1 for the generalized forward backward algorithm By default it s equal to one lt Remark The generalized forward backward solver is used to solve this problem 6 Examples In this Section we illustrate the use of the toolbox with two different examples All the proximal operators used for these are already implemented in the toolbox 6 1 Example 1 inpainting The goal is to recover some missing pixels in an image The pixels values form a M x M matrix Let s define a function t X that transform a M x M matrix into a row vector of size M The inverse function will be written t a Suppose that the original image is J and the missing pixel are represented by 0 in mask My the other values are 1 The number of known pixels is K The measurements are simply b t M eI t Mr et I m e i Ai with e the element by element product and A a K x M binary matrix with only one single 1 value per line where the pixels are knows The image is recovered using a Total Variation prior The L1 norm of the magnitude of the gradient for details see 13 The problem can
13. ection on B1 ball The B1 Ball projection operator solves the problem min x 2 5s t w z 1 lt epsilon z The associated Matlab function proj_B1 is function sol proj_B1 x lambda param x is the vector be projected lambda is compatibility parameter It is not used in the function The following fields of param are specific to the proj_B1 function param w contain the weigths default ones param epsilon Radius of the L1 ball default le 3 param verbose Log parameter 0 no log 1 a summary at convergence 2 print main steps default 1 5 3 2 Projection on B2 ball The B2 Ball projection operator solves the problem min x z 3s t y Az l2 lt epsilon zZ The associated Matlab function proj_B2 is function sol proj_B2 x lambda param x is the vector be projected lambda is compatibility parameter It is not used in the function The following fields of param are specific to the proj_B1 function param A Operator A default Id param At Adjoint of A A default Id param tight 1 if Y is a tight frame or 0 if not default 1 param nu v is a bound on the norm of the operator Y i e Wa lt v x default 1 param epsilon Radius of the L2 ball default le 3 param max_iter The maximum number of iterations default 200 param tol tolerance for the projection onto the L2 ball The algorithms stops if lt ly A lt
14. ell defined The proximity operator is a useful tool because see e g 9 10 2 is a minimizer in 1 if and only if for any y gt 0 Z proxy 412 27 4 The term splitting refers to the fact that the proximal splitting algorithms do not directly evaluate the proximity operator prox s z but rather try to find a solution to 4 through sequences of computations involving the proximity operators prox y 1 and prox y 1 separately The recent survey 11 provides an excellent review of proximal splitting algorithms used to solve 1 and related convex optimization problems 2 Installation and initialisation 3 Solver 3 1 Forward backward algorithm The forward backward algorithm can be used to solve min filz falo when either f or fo is a continuously differentiable convex function with a Lipschitz continuous gradient A function f has a 6 Lipschitz continuous gradient V f if IV f x Vf o lla lt Lle yll Yz y RY 5 1 In fact the toolbox implements generalized versions of these algorithms that can solve problems with sums of a general number of such functions but for simplicity we discuss here the simplest case of two functions JULY 2012 1 16 LTS2 EPFL 4 THE DOUGLAS RACHFORD ALGORITHM where 6 gt 0 If without loss of generality fg is the function with a P Lipschitz continuous gradient V fa then x is a solution to 1 if and only if for any y gt 0 see e g 3 Pr
15. f x In Matlab write 2 grad x grad_f2 x where grad_f2 x return the value of V fa x Finally param is a Matlab structure that containing a set of optional parameters The list of parameters is described in Section 4 5 The following two fields are specific to the forward_backward function param method ISTA or FISTA Specify the method used to solve problem 1 ISTA stands for the original forward backward algorithm while FISTA stands for its accelerated version for details see 12 param gamma step size parameter y This constant should satisfy y e 2 8 e for e 0 minf1 1 8 param lambda A weight of the update term used in ISTA method e 1 By default it s equal to one 3 2 Douglas Rachford 4 The Douglas Rachford Algorithm The Douglas Rachford algorithm is a more general algorithm to solve min file fale that does not require any assumptions on the smoothness of f or f2 For any constant y gt 0 a point x R is a solution to 1 if and only if there exists a y RY such that 8 Proposition 18 x prox y and 8 prox y Y prox y 2prox y y y 9 To find x and y that satisfy 8 and 9 the Douglas Rachford algorithm computes the following sequence of points for any fixed y gt 0 and stepsize A 0 2 q Prox fy y and 10 y ED y 4A proxy 22 y 20 11 JULY 2012 2 16 LTS2 EPFL 4
16. itz min f1 2 fal x0 fl f2 param admm This function solves the optimization problem of minimizing the sum of f and f2 using the alternating direction method of multipliers ADMM algorithm Both functions have to be convex min fi 2 fo y suchthat y Le x0 fl f param L generalized forward _ backward This function solves the optimization problem of minimizing the sum of F using the generalized forward backward algorithm All functions need to be convex and one needs to be 6 Lipschitz denoted f min f x 9 wiFi 2 x0 F f param ppxa This function solves the optimization problem of minimizing the sum of F using the parallel proxi mal algorithm PPXA which is a generalization of the forward backward algorithm All functions have to be convex 2 x0 F param sdmm This function solves the optimization problem of minimizing the sum of F using the simultaneous direction method of multipliers SDMM algorithm All functions need to be convex min Y F Lix F param RLR This function solves a common optimisation prob lem min Ax zoll 2 x0 f A At param Table 3 List of main functions JULY 2012 13 16 LTS2 EPFL 7 SUMMARY OF ALL FUNCTIONS Function Explanation Argument prox_ Ll l norm proximal operator Solve X lambda a param min zle 2112 AIW o lh zx
17. me Continuous definition Discrete definition Notation Matlab Function L1 norm amp leli f jela norm 1 ten N leli S len n 1 L2 norm BE ot ua a t 2dt lla L12 mixed norm Lia 1 2 p lt I 2 roll t1 1 t2EQ2 gEG with xy C Lloo mixed norm Liss normLting 648 0 folie f mag letto ats leli D leol tem H2EN2 geG with ty Cu TV norm trv lalrv f Velat TV_norm or ten lcllry y Vz n n TV_norm3D Nuclear norm For z a m byn matrix Ly with singular values o norm_nuclear we have min m n llel SO o i 1 Table 2 Presentation of the norms 5 2 Norm proximal operators Minimizing norm presented in table 2 leads to common proximal operators We present them in this section All Matlab prox functions take three parameters x lambda param First x is the initial signal Then lambda is the weight of the objective function Finally param is a Matlab structure that containing a set of optional parameters JULY 2012 6 16 LTS2 EPFL 5 PROXIMAL OPERATORS param max_iter The maximum number of iterations default 200 param epsilon This parameter is used to define the stopping criterion of the problem The algorithm stops if fO f t 1 F t where f t is the function to be minimized at iteration t e RF default 1074 param verbose Log parameter 0 no log 1 a summary at convergence 2 print
18. mma y gt 0 controls the speed of convergence Its default value is 1 4 1 Alternating direction method of multipliers ADMM Augmented Lagrangian techniques are classical approaches for solving problem like min f x f2 Lo 12 TERN First we reformulate 12 to min x EA Lx y We then solve this problem using the augmented Lagrangian technique Warning the proximal operator of function f is defined to be 1 prox 2 argmin r fi 2 La all TERN The ADMM algorithm can be used when f and fz are in To RN and in To R4 with LTL invertible and ridomf N L ridomf2 4 The associated Matlab function ADMM takes five pa rameters function sol admm x_0 f1 2 L param As in Section 3 1 x0 RY is the starting point for the algorithm f1 and f2 are two Matlab structures that represent the functions f and f2 The Matlab structure f1 contains the fields f1 norm and f1 prox The former is a Matlab function that takes as input a vector x RY and returns the value f x the latter is a Matlab function that takes as input a vector x RY a strictly positiv real number 7 and returns the vector prox y 1 The Matlab structure 2 contains the exact same fields but for the function f Finally param contains a list of parameters The list of parameters is described in Section 4 5 The following two fields are specific to the douglas_rachford function param gamma y gt 0 controls the speed of con
19. nexpansive averaged operators Optimization vol 53 pp 475 504 2004 8 P L Combettes and J C Pesquet A Douglas Rachford splitting approach to nonsmooth convex variational signal recovery IEEE J Selected Topics Signal Process vol 1 pp 564 574 2007 B Martinet Determination approch e d un point fixe d une application pseudo contractante Cas de l application prox Comptes Rendus de l Academie des Sciences Paris S rie A vol 274 pp 163 165 1972 10 R Rockafellar Monotone operators and the proximal point algorithm SIAM J Control Optim vol 14 pp 877 898 1976 11 P L Combettes and J C Pesquet Proximal splitting methods in signal processing in Fixed Point Algorithms for Inverse Problems in Science and Engineering H H Bauschke R Burachik P L Combettes V Elser D R Luke and H Wolkowicz Eds Springer Verlag 2011 pp 185 212 12 A Beck and M Teboulle A fast iterative shrinkage thresholding algorithm for linear inverse problems SIAM J Img Sci vol 2 pp 183 202 March 2009 Online Available http dl acm org citation cfm id 1658360 1658364 13 A Chambolle An algorithm for total variation minimization and applications J Math Imaging Vis vol 20 pp 89 97 Jan 2004 9 JULY 2012 16 16
20. oposition 3 1 x prox p 1 YV fa 2 6 The forward backward algorithm finds a point satisfying 6 by computing a sequence ot ip via jase q prox f 2 VW fa e 7 For any 2 the sequence 24 0 1 converges to a point satisfying 6 which is therefore a minimizer of 1 For a detailed convergence analysis that includes generalizations of 7 which may result in improved convergence rates see 3 Theorem 3 4 The associated Matlab function forward_backward takes four parameters function sol forward_backward x0 f1 f2 param x0 RY is the starting point for the algorithm f1 and f2 are two Matlab structures that represent the functions f and f2 Each of these structures needs at least two fields The Matlab structure f1 contains the fields 1 norm and f1 prox The former is a Matlab function that takes as input a vector x RY and returns the value f x the latter is a Matlab function that takes as input a vector x RY a strictly positiv real number 7 and returns the vector prox x In Matlab write f1 prox 0 x T prox_f1 x T where prox_f1 x T solves the problem proxys 1 given in equation 3 In the same way the Matlab structure 2 contains the fields 2 norm and f2 grad The former is a Matlab function that takes as input a vector x R and returns the value f2 x the latter is also a Matlab function that takes as input a vector x RY and returns the vector V
21. param contains a list of parameters The list of parameters is described in Section 4 5 The following two fields are specific to the ppxa function param W W the weight all equal by default Note that ek param W 1 param gamma step size parameter y This constant should satisfy y e 2 6 e for e 0 min 1 1 8 param lambda A weight of the update term used e 1 By default it s equal to one JuLY 2012 4 16 LTS2 EPFL 4 THE DOUGLAS RACHFORD ALGORITHM 4 4 Simultaneous direction method of multipliers SDMM The SDMM algorithm can be used to minimize K functions problem of the form K mai 2 Pala with fn nefi 2 K To RY and Ln ne i 2 k linear operators such that a Lt Ln is invertible The associated Matlab function SDMM takes two parameters sol sdmm F param F is an array of structures representing the functions f1 fo fx Each of these structures needs at least three fields F i norm F i prox and F i x0 with 1 2 K The first is a Matlab function that takes as input a vector x RY and returns the value f a the second is a Matlab function that takes as input a vector RY a strictly positiv real number 7 and returns the vector prox x In Matlab write F i prox x T prox_fi x T where prox_fi x T solves the problem proxy y x given in equation 3 and the last F i x0 is the vector used as starting point Additionally
22. vergence Its default value is 1 JuLY 2012 3 16 LTS2 EPFL 4 THE DOUGLAS RACHFORD ALGORITHM 4 2 Forward backward algorithm The forward backward algorithm can be used to minimize K functions problems of the form K min 2 fale with fn nes1 2 K To RV and with at least one continuously differentiable convex function denoted f with P Lipschitz continuous gradient V f1 Vf 2 Yf lt lle yl Ve y E RY x RY where P gt 0 The associated Matlab function generalized_forward_backward takes four parameters function sol generalized_forward_backward x_0 F f1 param x0 RY is the starting point for the algorithm f1 is a Matlab structures that represent the functions f It contains the fields f1 norm and f1 grad The former is a Matlab function that takes as input a vector x RY and returns the value f 1 the latter is also a Matlab function that takes as input a vector x RY and returns the vector V f2 x In Matlab write f2 grad 0 x grad_f2 x where grad_f2 x return the value of V f x F is an array of structures representing the functions fo f3 fg Each of these structures needs at least two fields F i norm and F i prox with i 1 2 4 amp 1 The former is a Matlab function that takes as input a vector x RY and returns the value f z the latter is a Matlab function that takes as input a vector RY a strictly positiv real number 7 and returns the vector pro
23. weights for a weighted 12 norm works on the norm default ones Example param g_d and param g_t Suppose we have x 21 2 2 3 4 5 6 we want to group 21 2 4 5 and 13 16 Then we set param g_d 1 2 4 5 3 6 and param g_t 4 2 It is also possible to set param g_d 4 5 3 6 1 2 and param g_t 2 4 Overlaping group In order to make overlapping group param g_d param g_t must be vectors of non overlapping group Example param g_d g_d1 g_d2 g_dn param g_t g_t1 g_t2 g_tn There must be no overlap in g_d1 g_d2 g_dn 5 2 4 TV norm proximal operator The py norm proximal operator solves the problem sak 2 PIOX y 2 min a 2112 Allelirv The associated Matlab function prox_TV is function sol prox_TV x lambda param where x is a 1 or 2 dimensions matrix 5 2 5 3D TV norm proximal operator The 3pry norm proximal operator solves the problem el 2 POX ry 2 min lx 2ll2 Allzlirv The associated Matlab function prox_TV3D is function sol prox_TV3D x lambda param where x is a 1 2 or 3 dimensions matrix JULY 2012 8 16 LTS2 EPFL 5 PROXIMAL OPERATORS 5 2 6 Nuclear norm proximal operator The norm proximal operator solves the problem wy 2 Proxy 2 min lle 2112 Allel The associated Matlab function prox_NuclearNorm is function sol prox_NuclearNorm x lambda param 5 3 Projection operator 5 3 1 Proj
24. x Taa x In Matlab write F i prox x T prox_fi x T where prox_fi x T solves the problem proxy f x given in equation 3 Finally param is a Matlab structure that containing a set of optional parameters The list of pa rameters is described in Section 4 5 The following two fields are specific to the generalized_forward_backward function param gamma step size parameter y This constant should satisfy y e 2 8 e for e EJO min 1 1 8 param lambda A weight of the update term e 1 By default it s equal to one 4 3 Generalized Douglas Rachford or parallel proximal algorithm PPXA The PPXA algorithm can be used to minimize K functions problem of the form TERN K min 5 fale 1 with fn ne 1 2 K To R The associated Matlab function ppxa takes three parameters function sol ppxa x0 F param x0 RY is the starting point for the algorithm Then F is an array of structures representing the functions f1 fa fx Each of these structures needs at least two fields F i norm and F i prox with i 1 2 K The former is a Matlab function that takes as input a vector x R and returns the value f x the latter is a Matlab function that takes as input a vec tor RY a strictly positiv real number 7 and returns the vector prox a In Matlab write F i prox x T prox_fi x T where prox_fi x T solves the problem proxy x given in equation 3 Finally
Download Pdf Manuals
Related Search