SHOGUN  v2.0.0
overlapping.h
Go to the documentation of this file.
1 /* This program is free software: you can redistribute it and/or modify
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 #ifndef OVERLAPPING_SLEP
18 #define OVERLAPPING_SLEP
19
20 #include <stdio.h>
21 #include <stdlib.h>
22 #include <math.h>
23 #include <string.h>
24
25
26 /*
27  * -------------------------------------------------------------------
28  * Function and parameter
29  * -------------------------------------------------------------------
30  *
31  * In this file, we focus solving the following problem
32  *
33  * 1/2 \|x-v\|^2 + \lambda_1 \|x\|_1 + \lambda_2 \sum w_i \|x_{G_i}\|,
34  *
35  * where x and v are of dimension p,
36  * w >0, and G_i contains the indices for the i-th group
37  *
38  * The file is implemented in the following in Matlab:
39  *
40  * x=overlapping(v, p, g, lambda1, lambda2, w, G, Y, maxIter, flag, tol);
41  *
42  * x and v are vectors of dimension p
43  *
44  * g denotes the number of groups
45  *
46  * lambda1 and labmda2 are non-negative regularization paramter
47  *
48  * G is a vector containing the indices for the groups
49  * G_1, G_2, ..., G_g
50  *
51  * w is a 3xg matrix
52  * w(1,i) contains the starting index of the i-th group in G
53  * w(2,i) contains the ending index of the i-th group in G
54  * w(3,i) contains the weight for the i-th group
55  *
56  * Y is the dual of \|x_{G_i}\|, it is of the same size as G
57  *
58  * maxIter is the maximal number of iteration
59  *
60  * flag=0, we apply the pure projected gradient descent
61  * (forward and backward line search is used)
62  *
63  * flag=1, we apply the projected gradient descent with restart
64  *
65  * in the future, we may apply the accelerated gradient descent
66  * with adaptive line search (see our KDD'09 paper) with other "flag"
67  *
68  *
69  * Note:
70  *
71  * 1. One should ensure w(2,i)-w(1,i)+1=|G_i|.
72  * !! The program does not check w(2,i)-w(1,i)+1=|G_i|.!!
73  *
74  * 2. The index in G and w starts from 0
75  *
76  * -------------------------------------------------------------------
77  * History:
78  * -------------------------------------------------------------------
79  *
80  * Composed by Jun Liu on May 17, 2010
81  *
82  * For any question or suggestion, please email j.liu@asu.edu or
83  * jun.liu.80@gmail.com
84  *
85  */
86
87
88 /*
89  * --------------------------------------------------------------------
90  * Identifying some zero Entries
91  * --------------------------------------------------------------------
92  *
93  * lambda1, lambda2 should be non-negative
94  *
95  * v is the vector of size p to be projected
96  *
97  *
98  * zeroGroupFlag is a vector of size g
99  *
100  * zeroGroupFlag[i]=0 denotes that the corresponding group is definitely zero
101  * zeroGroupFlag[i]=1 denotes that the corresponding group is (possibly) nonzero
102  *
103  *
104  * u is a vector of size p
105  *
106  *
107  * entrySignFlag is a vector of size p
108  *
109  * entrySignFlag[i]=0 denotes that the corresponding entry is definitely zero
110  * entrySignFlag[i]=1 denotes that the corresponding entry is (possibly) positive
111  * entrySignFlag[i]=-1 denotes that the corresponding entry is (possibly) negative
112  *
113  */
114 void identifySomeZeroEntries(double * u, int * zeroGroupFlag, int *entrySignFlag,
115  int *pp, int *gg,
116  double *v, double lambda1, double lambda2,
117  int p, int g, double * w, double *G);
118
119 /*
120  *
121  * function: xFromY
122  *
123  * compute x=max(u-Y * e, 0);
124  *
125  * xFromY(x, y, u, Y, p, g, zeroGroupFlag, G, w);
126  *
127  * y=u-Y * e - max( u - Y * e, 0)
128  *
129  */
130 void xFromY(double *x, double *y,
131  double *u, double *Y,
132  int p, int g, int *zeroGroupFlag,
133  double *G, double *w);
134
135 /*
136  *
137  * function: YFromx
138  *
140  *
141  * YFromx(Y, xnew, Ynew, lambda2, g, zeroGroupFlag, G, w);
142  *
143  * The idea is that, if x_{G_i} is nonzero,
144  * we compute Y^i as x_{G_i}/ \|x_{G_i}\| * lambda2 * w[3*i+2]
145  * otherwise
146  * Y^i=Ynew^i
147  *
148  */
149 void YFromx(double *Y,
150  double *xnew, double *Ynew,
151  double lambda2, int g, int *zeroGroupFlag,
152  double *G, double *w);
153
154 /*
155  * function: dualityGap
156  *
157  * compute the duality gap for the approximate solution (x, Y)
158  *
159  * Meanwhile, we compute
160  *
161  * penalty2=\sum_{i=1}^g w_i \|x_{G_i}\|
162  *
163  */
164 void dualityGap(double *gap, double *penalty2,
165  double *x, double *Y, int g, int *zeroGroupFlag,
166  double *G, double *w, double lambda2);
167
168 /*
169  * we solve the proximal opeartor:
170  *
171  * 1/2 \|x-v\|^2 + \lambda_1 \|x\|_1 + \lambda_2 \sum w_i \|x_{G_i}\|
172  *
173  * See the description of the variables in the beginning of this file
174  *
175  * x is the primal variable, each of its entry is non-negative
176  *
177  * Y is the dual variable, each of its entry should be non-negative
178  *
179  * flag =0: no restart
180  * flag =1; restart
181  *
182  * tol: the precision parameter
183  *
184  * The following code apply the projected gradient descent method
185  *
186  */
187 void overlapping_gd(double *x, double *gap, double *penalty2,
188  double *v, int p, int g, double lambda1, double lambda2,
189  double *w, double *G, double *Y, int maxIter, int flag, double tol);
190
191 /*
192  *
193  * do a gradient descent step based (x, Y) to get (xnew, Ynew)
194  *
195  * (x, Y) is known. Here we do a line search for determining the value of L
196  *
197  * gradientDescentStep(double *xnew, double *Ynew,
198  double *LL, double *u,
199  double *x, double *Y, int p, int g, int * zeroGroupFlag,
200  double *G, double *w)
201  *
202  */
203 void gradientDescentStep(double *xnew, double *Ynew,
204  double *LL, double *u, double *y, int *entrySignFlag, double lambda2,
205  double *x, double *Y, int p, int g, int * zeroGroupFlag,
206  double *G, double *w);
207
208 /*
209  *
210  * we use the accelerated gradient descent
211  *
212  */
213 void overlapping_agd(double *x, double *gap, double *penalty2,
214  double *v, int p, int g, double lambda1, double lambda2,
215  double *w, double *G, double *Y, int maxIter, int flag, double tol);
216
217 /*
218  * This is main function for the projection
219  *
220  * It calls overlapping_gd and overlapping_agd based on flag
221  *
222  *
223  */
224 void overlapping(double *x, double *gap, double *penalty2,
225  double *v, int p, int g, double lambda1, double lambda2,
226  double *w, double *G, double *Y, int maxIter, int flag, double tol);
227
228 #endif /* ----- #ifndef OVERLAPPING_SLEP ----- */

SHOGUN Machine Learning Toolbox - Documentation