00001 /* This program is free software: you can redistribute it and/or modify 00002 * it under the terms of the GNU General Public License as published by 00003 * the Free Software Foundation, either version 3 of the License, or 00004 * (at your option) any later version. 00005 * 00006 * This program is distributed in the hope that it will be useful, 00007 * but WITHOUT ANY WARRANTY; without even the implied warranty of 00008 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00009 * GNU General Public License for more details. 00010 * 00011 * You should have received a copy of the GNU General Public License 00012 * along with this program. If not, see <http://www.gnu.org/licenses/>. 00013 * 00014 * Copyright (C) 2009 - 2012 Jun Liu and Jieping Ye 00015 */ 00016 00017 #ifndef FLSA_SLEP 00018 #define FLSA_SLEP 00019 00020 /* 00021 00022 In this file, we solve the Fused Lasso Signal Approximator (FLSA) problem: 00023 00024 min_x 1/2 \|x-v\|^2 + lambda1 * \|x\|_1 + lambda2 * \|A x\|_1, (1) 00025 00026 It can be shown that, if x* is the solution to 00027 00028 min_x 1/2 \|x-v\|^2 + lambda2 \|A x\|_1, (2) 00029 00030 then 00031 x**= sgn(x*) max(|x*|-lambda_1, 0) (3) 00032 00033 is the solution to (1). 00034 00035 By some derivation (see the description in sfa.h), (2) can be solved by 00036 00037 x*= v - A^T z*, 00038 00039 where z* is the optimal solution to 00040 00041 min_z 1/2 z^T A AT z - < z, A v>, 00042 subject to \|z\|_{infty} \leq lambda2 (4) 00043 */ 00044 00045 00046 00047 /* 00048 00049 In flsa, we solve (1) corresponding to a given (lambda1, lambda2) 00050 00051 void flsa(double *x, double *z, double *gap, 00052 double * v, double *z0, 00053 double lambda1, double lambda2, int n, 00054 int maxStep, double tol, int flag) 00055 00056 Output parameters: 00057 x: the solution to problem (1) 00058 z: the solution to problem (4) 00059 infor: the information about running the subgradient finding algorithm 00060 infor[0] = gap: the computed gap (either the duality gap 00061 or the summation of the absolute change of the adjacent solutions) 00062 infor[1] = steps: the number of iterations 00063 infor[2] = lambad2_max: the maximal value of lambda2_max 00064 infor[3] = numS: the number of elements in the support set 00065 00066 Input parameters: 00067 v: the input vector to be projected 00068 z0: a guess of the solution of z 00069 00070 lambad1: the regularization parameter 00071 labmda2: the regularization parameter 00072 n: the length of v and x 00073 00074 maxStep: the maximal allowed iteration steps 00075 tol: the tolerance parameter 00076 tau: the program sfa is checked every tau iterations for termination 00077 flag: the flag for initialization and deciding calling sfa 00078 switch ( flag ) 00079 1-4, 11-14: sfa 00080 00081 switch ( flag ) 00082 case 1, 2, 3, or 4: 00083 z0 is a "good" starting point 00084 (such as the warm-start of the previous solution, 00085 or the user want to test the performance of this starting point; 00086 the starting point shall be further projected to the L_{infty} ball, 00087 to make sure that it is feasible) 00088 00089 case 11, 12, 13, or 14: z0 is a "random" guess, and thus not used 00090 (we shall initialize z as follows: 00091 if lambda2 >= 0.5 * lambda_2^max, we initialize the solution of the linear system; 00092 if lambda2 < 0.5 * lambda_2^max, we initialize with zero 00093 this solution is projected to the L_{infty} ball) 00094 00095 switch( flag ) 00096 5, 15: sfa_special 00097 00098 switch( flag ) 00099 5: z0 is a good starting point 00100 15: z0 is a bad starting point, use the solution of the linear system 00101 00102 00103 switch( flag ) 00104 6, 16: sfa_one 00105 00106 switch( flag ) 00107 6: z0 is a good starting point 00108 16: z0 is a bad starting point, use the solution of the linear system 00109 00110 Revision made on October 31, 2009. 00111 The input variable z0 is not modified after calling sfa. For this sake, we allocate a new variable zz to replace z0. 00112 */ 00113 void flsa(double *x, double *z, double *infor, 00114 double * v, double *z0, 00115 double lambda1, double lambda2, int n, 00116 int maxStep, double tol, int tau, int flag); 00117 #endif /* ----- #ifndef FLSA_SLEP ----- */