SHOGUN  5.0.0
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Modules
flsa.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 
18 #ifdef USE_GPL_SHOGUN
19 
21 #include <stdlib.h>
22 #include <stdio.h>
23 #include <time.h>
24 #include <math.h>
25 
26 void flsa(double *x, double *z, double *infor,
27  double * v, double *z0,
28  double lambda1, double lambda2, int n,
29  int maxStep, double tol, int tau, int flag)
30 {
31 
32  int i, nn=n-1, m;
33  double zMax, temp;
34  double *Av, *g, *s;
35  int iterStep, numS;
36  double gap;
37  double *zz = NULL; /*to replace z0, so that z0 shall not revised after */
38 
39 
40  Av=(double *) malloc(sizeof(double)*nn);
41 
42  /*
43  Compute Av= A*v (n=4, nn=3)
44  A= [ -1 1 0 0;
45  0 -1 1 0;
46  0 0 -1 1]
47  */
48 
49  for (i=0;i<nn; i++)
50  Av[i]=v[i+1]-v[i];
51 
52  /*
53  Sovlve the linear system via Thomas's algorithm or Rose's algorithm
54  B * z0 = Av
55  */
56 
57  Thomas(&zMax, z, Av, nn);
58 
59  /*
60  We consider two cases:
61  1) lambda2 >= zMax, which leads to a solution with same entry values
62  2) lambda2 < zMax, which needs to first run sfa, and then perform soft thresholding
63  */
64 
65  /*
66  First case: lambda2 >= zMax
67  */
68  if (lambda2 >= zMax){
69 
70  temp=0;
71  m=n%5;
72  if (m!=0){
73  for (i=0;i<m;i++)
74  temp+=v[i];
75  }
76  for (i=m;i<n;i+=5){
77  temp += v[i] + v[i+1] + v[i+2] + v[i+3] + v[i+4];
78  }
79  temp/=n;
80  /* temp is the mean value of v*/
81 
82 
83  /*
84  soft thresholding by lambda1
85  */
86  if (temp> lambda1)
87  temp= temp-lambda1;
88  else
89  if (temp < -lambda1)
90  temp= temp+lambda1;
91  else
92  temp=0;
93 
94  m=n%7;
95  if (m!=0){
96  for (i=0;i<m;i++)
97  x[i]=temp;
98  }
99  for (i=m;i<n;i+=7){
100  x[i] =temp;
101  x[i+1] =temp;
102  x[i+2] =temp;
103  x[i+3] =temp;
104  x[i+4] =temp;
105  x[i+5] =temp;
106  x[i+6] =temp;
107  }
108 
109  gap=0;
110 
111  free(Av);
112 
113  if (infor)
114  {
115  infor[0]= gap;
116  infor[1]= 0;
117  infor[2]=zMax;
118  infor[3]=0;
119  }
120 
121  return;
122  }
123 
124 
125  /*
126  Second case: lambda2 < zMax
127 
128  We need to call sfa for computing x, and then do soft thresholding
129 
130  Before calling sfa, we need to allocate memory for g and s,
131  and initialize z and z0.
132  */
133 
134 
135  /*
136  Allocate memory for g and s
137  */
138 
139  g =(double *) malloc(sizeof(double)*nn),
140  s =(double *) malloc(sizeof(double)*nn);
141 
142 
143 
144  m=flag /10;
145  /*
146 
147  If m=0, then this shows that, z0 is a "good" starting point. (m=1-6)
148 
149  Otherwise (m=11-16), we shall set z as either the solution to the linear system.
150  or the zero point
151 
152 */
153  if (m==0){
154  for (i=0;i<nn;i++){
155  if (z0[i] > lambda2)
156  z[i]=lambda2;
157  else
158  if (z0[i]<-lambda2)
159  z[i]=-lambda2;
160  else
161  z[i]=z0[i];
162  }
163  }
164  else{
165  if (lambda2 >= 0.5 * zMax){
166  for (i=0;i<nn;i++){
167  if (z[i] > lambda2)
168  z[i]=lambda2;
169  else
170  if (z[i]<-lambda2)
171  z[i]=-lambda2;
172  }
173  }
174  else{
175  for (i=0;i<nn;i++)
176  z[i]=0;
177 
178  }
179  }
180 
181  flag=flag %10; /*
182  flag is now in [1:6]
183 
184  for sfa, i.e., flag in [1:4], we need initialize z0 with zero
185  */
186 
187  if (flag>=1 && flag<=4){
188  zz =(double *) malloc(sizeof(double)*nn);
189 
190  for (i=0;i<nn;i++)
191  zz[i]=0;
192  }
193 
194  /*
195  call sfa, sfa_one, or sfa_special to compute z, for finding the subgradient
196  and x
197  */
198 
199  if (flag==6)
200  iterStep=sfa_one(x, &gap, &numS,
201  z, v, Av,
202  lambda2, nn, maxStep,
203  s, g,
204  tol, tau);
205  else
206  if (flag==5)
207  iterStep=sfa_special(x, &gap, &numS,
208  z, v, Av,
209  lambda2, nn, maxStep,
210  s, g,
211  tol, tau);
212  else{
213  iterStep=sfa(x, &gap, &numS,
214  z, zz, v, Av,
215  lambda2, nn, maxStep,
216  s, g,
217  tol,tau, flag);
218 
219  free (zz);
220  /*free the variable zz*/
221  }
222 
223 
224  /*
225  soft thresholding by lambda1
226  */
227 
228  for(i=0;i<n;i++)
229  if (x[i] > lambda1)
230  x[i]-=lambda1;
231  else
232  if (x[i]<-lambda1)
233  x[i]+=lambda1;
234  else
235  x[i]=0;
236 
237 
238  free(Av);
239  free(g);
240  free(s);
241 
242  if (infor)
243  {
244  infor[0]=gap;
245  infor[1]=iterStep;
246  infor[2]=zMax;
247  infor[3]=numS;
248  }
249 }
250 
251 #endif //USE_GPL_SHOGUN

SHOGUN Machine Learning Toolbox - Documentation