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

SHOGUN Machine Learning Toolbox - Documentation