SHOGUN  4.1.0
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Modules Pages
epph.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 #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