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

SHOGUN Machine Learning Toolbox - Documentation