SHOGUN  6.0.0
epph.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
18 #ifndef EPPHQ1_SLEP
19 #define EPPHQ1_SLEP
20
21 #include <shogun/lib/config.h>
22 #ifdef USE_GPL_SHOGUN
23
24 /* -------------------------- Function eplb -----------------------------
25
26  Euclidean Projection onto l1 Ball (eplb)
27
28  min 1/2 ||x- v||_2^2
29  s.t. ||x||_1 <= z
30
31  which is converted to the following zero finding problem
32
33  f(lambda)= sum( max( |v|-lambda,0) )-z=0
34
35  For detail, please refer to our paper:
36
37  Jun Liu and Jieping Ye. Efficient Euclidean Projections in Linear Time,
38  ICML 2009.
39
40  Usage (in matlab):
41  [x, lambda, iter_step]=eplb(v, n, z, lambda0);
42
43  -------------------------- Function eplb -----------------------------
44  */
45 void eplb(double * x, double *root, int * steps, double * v,int n, double z, double lambda0);
46
47 /* -------------------------- Function epp1 -----------------------------
48
49  The L1-norm Regularized Euclidean Projection (epp1)
50
51  min 1/2 ||x- v||_2^2 + rho ||x||_1
52
53  which has the closed form solution
54
55  x= sign(v) max( |v|- rho, 0)
56
57  Usage (in matlab)
58  x=epp1(v, n, rho);
59
60  -------------------------- Function epp1 -----------------------------
61  */
62 void epp1(double *x, double *v, int n, double rho);
63
64 /* -------------------------- Function epp2 -----------------------------
65
66  The L2-norm Regularized Euclidean Projection (epp2)
67
68  min 1/2 ||x- v||_2^2 + rho ||x||_2
69
70  which has the closed form solution
71
72  x= max( ||v||_2- rho, 0) / ||v||_2 * v
73
74  Usage (in matlab)
75  x=epp2(v, n, rho);
76
77  -------------------------- Function epp2 -----------------------------
78  */
79 void epp2(double *x, double *v, int n, double rho);
80
81 /* -------------------------- Function eppInf -----------------------------
82
83  The LInf-norm Regularized Euclidean Projection (eppInf)
84
85  min 1/2 ||x- v||_2^2 + rho ||x||_Inf
86
87  which is can be solved by using eplb
88
89  Usage (in matlab)
90  [x, lambda, iter_step]=eppInf(v, n, rho, rho0);
91
92  -------------------------- Function eppInf -----------------------------
93  */
94 void eppInf(double *x, double * c, int * iter_step, double *v, int n, double rho, double c0);
95
96 /* -------------------------- Function zerofind -----------------------------
97
98  Find the root for the function: f(x) = x + c x^{p-1} - v,
99  0 <= x <= v, v>=0
100  1< p < infty, p \neq 2
101
102  Property: when p>2, f(x) is a convex function
103  when 1<p<2, f(x) is a concave function
104
105  Method: we use Newton's method (other methods such as bisection can also work)
106
107  Note: we donot check the valid of the parameter.
108  Since it is only employed in eepO,
109  we can assure that these parameters satisfy the above conditions.
110
111  Usage (in matlab)
112  [root, interStep]=eppInf(v, p, c, x0);
113
114  -------------------------- Function zerofind -----------------------------
115  */
116 void zerofind(double *root, int * iterStep, double v, double p, double c, double x0);
117
118 /* -------------------------- Function norm -----------------------------
119
120  Compute the p-norm
121
122  -------------------------- Function norm -----------------------------
123  */
124 double norm(double * v, double p, int n);
125
126 /* -------------------------- Function eppInf -----------------------------
127
128  The Lp-norm Regularized Euclidean Projection (eppO) for 1< p<Inf
129
130  min 1/2 ||x- v||_2^2 + rho ||x||_p
131
132  We solve two simple zero finding algorithms
133
134  Usage (in matlab)
135  [x, c, iter_step]=eppO(v, n, rho, p);
136
137  -------------------------- Function eppInf -----------------------------
138  */
139 void eppO(double *x, double * cc, int * iter_step, double *v, int n, double rho, double p);
140
141 /* -------------------------- Function epp -----------------------------
142
143  The Lp-norm Regularized Euclidean Projection (epp) for all p>=1
144
145  min 1/2 ||x- v||_2^2 + rho ||x||_p
146
147  This function uses the previously defined functions.
148
149  Usage (in matlab)
150  [x, c, iter_step]=eppO(v, n, rho, p, c0);
151
152  -------------------------- Function epp -----------------------------
153  */
154 void epp(double *x, double * c, int * iter_step, double * v, int n, double rho, double p, double c0);
155 #endif //USE_GPL_SHOGUN
156 #endif /* ----- #ifndef EPPHQ1_SLEP ----- */
157

SHOGUN Machine Learning Toolbox - Documentation