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 TESLA_PROJ_SLEP 00018 #define TESLA_PROJ_SLEP 00019 00020 #include <stdlib.h> 00021 #include <stdio.h> 00022 #include <time.h> 00023 #include <math.h> 00024 #include <shogun/lib/slep/flsa/flsa.h> 00025 00026 00027 /* 00028 00029 Functions contained in "flsa.h" 00030 00031 void flsa(double *x, double *z, double *infor, 00032 double * v, double *z0, 00033 double lambda1, double lambda2, int n, 00034 int maxStep, double tol, int tau, int flag) 00035 00036 */ 00037 00038 /* 00039 In this file, we need to make use of the function flsa for solving the following problem 00040 00041 min 1/2 \|X - V\|_2^2 + lambda1 * \|X\|_1 + lambda2 \|X A^T\|_1 (1) 00042 00043 where X and V are of size p x n 00044 00045 For the definition of A, please refer to "flsa.h" and the included "sfa.h". 00046 00047 The problem can be decoupled into the following 00048 00049 min_x 1/2 \|x-v\|^2 + lambda1 * \|x\|_1 + lambda2 * \|A x\|_1, (2) 00050 00051 where x and v correspond to a row of of X and V, respectively. 00052 00053 The problem (2) is essentially the flsa problem, and can be solved by the function flsa. 00054 00055 00056 void tesla_proj(double *X, double *Z, double *gap, 00057 double *V, double *Z0, 00058 double lambda1, double lambda2, int p, int n, 00059 int maxStep, double tol, int flag) 00060 00061 Output parameters: 00062 X: the solution (of size p x n) 00063 Z: the auxiliary variable (result by subgradient finding), 00064 Z can be used as a warm start for the next "tesla_proj", 00065 size: p x (n-1) 00066 gap: the gap for each decoupled flsa problem (of size p x 1) 00067 00068 Input parameters: 00069 V: the one to be projected 00070 Z0: the starting point (see flag for whether it is used as the starting point) 00071 size: p x (n-1) 00072 00073 lambda1: the regularization parameter 00074 lambda2: the regularization parameter 00075 p: the number of rows in X and V 00076 n: the number of columns in X and V 00077 00078 maxStep: the maximal allowed iteration steps 00079 tol: the tolerance parameter 00080 flag: the flag for initialization and deciding calling sfa 00081 switch ( flag ) 00082 1-4, 11-14: sfa 00083 00084 switch ( flag ) 00085 case 1, 2, 3, or 4: 00086 z0 is a "good" starting point 00087 (such as the warm-start of the previous solution, 00088 or the user want to test the performance of this starting point; 00089 the starting point shall be further projected to the L_{infty} ball, 00090 to make sure that it is feasible) 00091 00092 case 11, 12, 13, or 14: z0 is a "random" guess, and thus not used 00093 (we shall initialize z as follows: 00094 if lambda2 >= 0.5 * lambda_2^max, we initialize the solution of the linear system; 00095 if lambda2 < 0.5 * lambda_2^max, we initialize with zero 00096 this solution is projected to the L_{infty} ball) 00097 00098 switch( flag ) 00099 5, 15: sfa_special 00100 00101 switch( flag ) 00102 5: z0 is a good starting point 00103 15: z0 is a bad starting point, use the solution of the linear system 00104 00105 00106 switch( flag ) 00107 6, 16: sfa_one 00108 00109 switch( flag ) 00110 6: z0 is a good starting point 00111 16: z0 is a bad starting point, use the solution of the linear system 00112 00113 */ 00114 00115 void tesla_proj(double *X, double *Z, double *gap, 00116 double *V, double *Z0, 00117 double lambda1, double lambda2, int p, int n, 00118 int maxStep, double tol, int tau, int flag){ 00119 /* 00120 We assume that X and V are of size p x n 00121 */ 00122 00123 int i, j; 00124 int nn=n-1; 00125 double 00126 *x =(double *) malloc(sizeof(double)*n), 00127 *v =(double *) malloc(sizeof(double)*n), 00128 *z =(double *) malloc(sizeof(double)*nn), 00129 *z0 =(double *) malloc(sizeof(double)*nn), 00130 *infor=(double *) malloc(sizeof(double)*4); 00131 //double temp; 00132 00133 00134 00135 if (n<3){ 00136 printf("\n n should be equal to or larger than 3"); 00137 exit(-1); 00138 } 00139 00140 00141 for(i=0;i<p; i++){ 00142 00143 /* 00144 copy a row of V to v 00145 */ 00146 for (j=0;j<n; j++) 00147 v[j]=V[j*p + i]; 00148 00149 /* 00150 copy a row of Z0 to z0 00151 */ 00152 for (j=0;j<nn; j++) 00153 z0[j]=Z0[j*p + i]; 00154 00155 /* 00156 call flsa to compute x 00157 */ 00158 00159 flsa(x, z, infor, 00160 v, z0, 00161 lambda1, lambda2, n, 00162 maxStep, tol, tau, flag); 00163 00164 00165 /* 00166 store the solution x to X 00167 */ 00168 for (j=0;j<n; j++) 00169 X[j*p + i]=x[j]; 00170 00171 /* 00172 store the solution z to Z 00173 */ 00174 for (j=0;j<nn; j++) 00175 Z[j*p + i]=z[j]; 00176 00177 gap[i]=infor[0]; 00178 } 00179 00180 00181 free(x); 00182 free(v); 00183 free(z); 00184 free(z0); 00185 free(infor); 00186 00187 } 00188 #endif /* ----- #ifndef TESLA_PROJ_SLEP ----- */ 00189