SHOGUN  4.2.0
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Modules Pages
flsa.h
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 
18 #ifndef FLSA_SLEP
19 #define FLSA_SLEP
20 
21 #include <shogun/lib/config.h>
22 #ifdef USE_GPL_SHOGUN
23 
24 /*
25 
26  In this file, we solve the Fused Lasso Signal Approximator (FLSA) problem:
27 
28  min_x 1/2 \|x-v\|^2 + lambda1 * \|x\|_1 + lambda2 * \|A x\|_1, (1)
29 
30  It can be shown that, if x* is the solution to
31 
32  min_x 1/2 \|x-v\|^2 + lambda2 \|A x\|_1, (2)
33 
34  then
35  x**= sgn(x*) max(|x*|-lambda_1, 0) (3)
36 
37  is the solution to (1).
38 
39  By some derivation (see the description in sfa.h), (2) can be solved by
40 
41  x*= v - A^T z*,
42 
43  where z* is the optimal solution to
44 
45  min_z 1/2 z^T A AT z - < z, A v>,
46  subject to \|z\|_{infty} \leq lambda2 (4)
47  */
48 
49 
50 
51 /*
52 
53  In flsa, we solve (1) corresponding to a given (lambda1, lambda2)
54 
55  void flsa(double *x, double *z, double *gap,
56  double * v, double *z0,
57  double lambda1, double lambda2, int n,
58  int maxStep, double tol, int flag)
59 
60  Output parameters:
61 x: the solution to problem (1)
62 z: the solution to problem (4)
63 infor: the information about running the subgradient finding algorithm
64 infor[0] = gap: the computed gap (either the duality gap
65 or the summation of the absolute change of the adjacent solutions)
66 infor[1] = steps: the number of iterations
67 infor[2] = lambad2_max: the maximal value of lambda2_max
68 infor[3] = numS: the number of elements in the support set
69 
70 Input parameters:
71 v: the input vector to be projected
72 z0: a guess of the solution of z
73 
74 lambad1: the regularization parameter
75 labmda2: the regularization parameter
76 n: the length of v and x
77 
78 maxStep: the maximal allowed iteration steps
79 tol: the tolerance parameter
80 tau: the program sfa is checked every tau iterations for termination
81 flag: the flag for initialization and deciding calling sfa
82 switch ( flag )
83 1-4, 11-14: sfa
84 
85 switch ( flag )
86 case 1, 2, 3, or 4:
87 z0 is a "good" starting point
88 (such as the warm-start of the previous solution,
89 or the user want to test the performance of this starting point;
90 the starting point shall be further projected to the L_{infty} ball,
91 to make sure that it is feasible)
92 
93 case 11, 12, 13, or 14: z0 is a "random" guess, and thus not used
94 (we shall initialize z as follows:
95 if lambda2 >= 0.5 * lambda_2^max, we initialize the solution of the linear system;
96 if lambda2 < 0.5 * lambda_2^max, we initialize with zero
97 this solution is projected to the L_{infty} ball)
98 
99 switch( flag )
100 5, 15: sfa_special
101 
102 switch( flag )
103 5: z0 is a good starting point
104 15: z0 is a bad starting point, use the solution of the linear system
105 
106 
107 switch( flag )
108 6, 16: sfa_one
109 
110 switch( flag )
111 6: z0 is a good starting point
112 16: z0 is a bad starting point, use the solution of the linear system
113 
114 Revision made on October 31, 2009.
115 The input variable z0 is not modified after calling sfa. For this sake, we allocate a new variable zz to replace z0.
116 */
117 void flsa(double *x, double *z, double *infor,
118  double * v, double *z0,
119  double lambda1, double lambda2, int n,
120  int maxStep, double tol, int tau, int flag);
121 #endif //USE_GPL_SHOGUN
122 #endif /* ----- #ifndef FLSA_SLEP ----- */
123 
SHOGUN Machine Learning Toolbox - Documentation