ARCHIVE Snapshot of the Shogun machine learning toolbox website as of 2013: preserved, not maintained. The live site: shogun-toolbox.org
SHOGUN  4.2.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 
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