SHOGUN  4.2.0
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Modules Pages
tesla_proj.cpp
Go to the documentation of this file.
1 /* This program is free software: you can redistribute it and/or modify
2  * it under the terms of the GNU General Public License as published by
3  * the Free Software Foundation, either version 3 of the License, or
4  * (at your option) any later version.
5  *
6  * This program is distributed in the hope that it will be useful,
7  * but WITHOUT ANY WARRANTY; without even the implied warranty of
8  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
9  * GNU General Public License for more details.
10  *
11  * You should have received a copy of the GNU General Public License
12  * along with this program. If not, see <http://www.gnu.org/licenses/>.
13  *
14  * Copyright (C) 2009 - 2012 Jun Liu and Jieping Ye
15  */
16 
17 #ifdef USE_GPL_SHOGUN
18 
19 #ifndef TESLA_PROJ_SLEP
20 #define TESLA_PROJ_SLEP
21 
22 #include <stdlib.h>
23 #include <stdio.h>
24 #include <time.h>
25 #include <math.h>
27 
28 
29 /*
30 
31  Functions contained in "flsa.h"
32 
33  void flsa(double *x, double *z, double *infor,
34  double * v, double *z0,
35  double lambda1, double lambda2, int n,
36  int maxStep, double tol, int tau, int flag)
37 
38 */
39 
40 /*
41  In this file, we need to make use of the function flsa for solving the following problem
42 
43  min 1/2 \|X - V\|_2^2 + lambda1 * \|X\|_1 + lambda2 \|X A^T\|_1 (1)
44 
45  where X and V are of size p x n
46 
47  For the definition of A, please refer to "flsa.h" and the included "sfa.h".
48 
49  The problem can be decoupled into the following
50 
51  min_x 1/2 \|x-v\|^2 + lambda1 * \|x\|_1 + lambda2 * \|A x\|_1, (2)
52 
53  where x and v correspond to a row of of X and V, respectively.
54 
55  The problem (2) is essentially the flsa problem, and can be solved by the function flsa.
56 
57 
58  void tesla_proj(double *X, double *Z, double *gap,
59  double *V, double *Z0,
60  double lambda1, double lambda2, int p, int n,
61  int maxStep, double tol, int flag)
62 
63  Output parameters:
64 X: the solution (of size p x n)
65 Z: the auxiliary variable (result by subgradient finding),
66 Z can be used as a warm start for the next "tesla_proj",
67 size: p x (n-1)
68 gap: the gap for each decoupled flsa problem (of size p x 1)
69 
70 Input parameters:
71 V: the one to be projected
72 Z0: the starting point (see flag for whether it is used as the starting point)
73 size: p x (n-1)
74 
75 lambda1: the regularization parameter
76 lambda2: the regularization parameter
77 p: the number of rows in X and V
78 n: the number of columns in X and V
79 
80 maxStep: the maximal allowed iteration steps
81 tol: the tolerance parameter
82 flag: the flag for initialization and deciding calling sfa
83 switch ( flag )
84 1-4, 11-14: sfa
85 
86 switch ( flag )
87 case 1, 2, 3, or 4:
88 z0 is a "good" starting point
89 (such as the warm-start of the previous solution,
90 or the user want to test the performance of this starting point;
91 the starting point shall be further projected to the L_{infty} ball,
92 to make sure that it is feasible)
93 
94 case 11, 12, 13, or 14: z0 is a "random" guess, and thus not used
95 (we shall initialize z as follows:
96 if lambda2 >= 0.5 * lambda_2^max, we initialize the solution of the linear system;
97 if lambda2 < 0.5 * lambda_2^max, we initialize with zero
98 this solution is projected to the L_{infty} ball)
99 
100 switch( flag )
101 5, 15: sfa_special
102 
103 switch( flag )
104 5: z0 is a good starting point
105 15: z0 is a bad starting point, use the solution of the linear system
106 
107 
108 switch( flag )
109 6, 16: sfa_one
110 
111 switch( flag )
112  6: z0 is a good starting point
113  16: z0 is a bad starting point, use the solution of the linear system
114 
115  */
116 
117  void tesla_proj(double *X, double *Z, double *gap,
118  double *V, double *Z0,
119  double lambda1, double lambda2, int p, int n,
120  int maxStep, double tol, int tau, int flag){
121  /*
122  We assume that X and V are of size p x n
123  */
124 
125  int i, j;
126  int nn=n-1;
127  double
128  *x =(double *) malloc(sizeof(double)*n),
129  *v =(double *) malloc(sizeof(double)*n),
130  *z =(double *) malloc(sizeof(double)*nn),
131  *z0 =(double *) malloc(sizeof(double)*nn),
132  *infor=(double *) malloc(sizeof(double)*4);
133  //double temp;
134 
135 
136 
137  if (n<3){
138  printf("\n n should be equal to or larger than 3");
139  exit(-1);
140  }
141 
142 
143  for(i=0;i<p; i++){
144 
145  /*
146  copy a row of V to v
147  */
148  for (j=0;j<n; j++)
149  v[j]=V[j*p + i];
150 
151  /*
152  copy a row of Z0 to z0
153  */
154  for (j=0;j<nn; j++)
155  z0[j]=Z0[j*p + i];
156 
157  /*
158  call flsa to compute x
159  */
160 
161  flsa(x, z, infor,
162  v, z0,
163  lambda1, lambda2, n,
164  maxStep, tol, tau, flag);
165 
166 
167  /*
168  store the solution x to X
169  */
170  for (j=0;j<n; j++)
171  X[j*p + i]=x[j];
172 
173  /*
174  store the solution z to Z
175  */
176  for (j=0;j<nn; j++)
177  Z[j*p + i]=z[j];
178 
179  gap[i]=infor[0];
180  }
181 
182 
183  free(x);
184  free(v);
185  free(z);
186  free(z0);
187  free(infor);
188 
189  }
190 #endif /* ----- #ifndef TESLA_PROJ_SLEP ----- */
191 
192 #endif //USE_GPL_SHOGUN

SHOGUN Machine Learning Toolbox - Documentation