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

SHOGUN Machine Learning Toolbox - Documentation