00001 /* This program is free software: you can redistribute it and/or modify 00002 * it under the terms of the GNU General Public License as published by 00003 * the Free Software Foundation, either version 3 of the License, or 00004 * (at your option) any later version. 00005 * 00006 * This program is distributed in the hope that it will be useful, 00007 * but WITHOUT ANY WARRANTY; without even the implied warranty of 00008 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00009 * GNU General Public License for more details. 00010 * 00011 * You should have received a copy of the GNU General Public License 00012 * along with this program. If not, see <http://www.gnu.org/licenses/>. 00013 * 00014 * Copyright (C) 2009 - 2012 Jun Liu and Jieping Ye 00015 */ 00016 00017 #ifndef EPPHQ1_SLEP 00018 #define EPPHQ1_SLEP 00019 00020 /* -------------------------- Function eplb ----------------------------- 00021 00022 Euclidean Projection onto l1 Ball (eplb) 00023 00024 min 1/2 ||x- v||_2^2 00025 s.t. ||x||_1 <= z 00026 00027 which is converted to the following zero finding problem 00028 00029 f(lambda)= sum( max( |v|-lambda,0) )-z=0 00030 00031 For detail, please refer to our paper: 00032 00033 Jun Liu and Jieping Ye. Efficient Euclidean Projections in Linear Time, 00034 ICML 2009. 00035 00036 Usage (in matlab): 00037 [x, lambda, iter_step]=eplb(v, n, z, lambda0); 00038 00039 -------------------------- Function eplb ----------------------------- 00040 */ 00041 void eplb(double * x, double *root, int * steps, double * v,int n, double z, double lambda0); 00042 00043 /* -------------------------- Function epp1 ----------------------------- 00044 00045 The L1-norm Regularized Euclidean Projection (epp1) 00046 00047 min 1/2 ||x- v||_2^2 + rho ||x||_1 00048 00049 which has the closed form solution 00050 00051 x= sign(v) max( |v|- rho, 0) 00052 00053 Usage (in matlab) 00054 x=epp1(v, n, rho); 00055 00056 -------------------------- Function epp1 ----------------------------- 00057 */ 00058 void epp1(double *x, double *v, int n, double rho); 00059 00060 /* -------------------------- Function epp2 ----------------------------- 00061 00062 The L2-norm Regularized Euclidean Projection (epp2) 00063 00064 min 1/2 ||x- v||_2^2 + rho ||x||_2 00065 00066 which has the closed form solution 00067 00068 x= max( ||v||_2- rho, 0) / ||v||_2 * v 00069 00070 Usage (in matlab) 00071 x=epp2(v, n, rho); 00072 00073 -------------------------- Function epp2 ----------------------------- 00074 */ 00075 void epp2(double *x, double *v, int n, double rho); 00076 00077 /* -------------------------- Function eppInf ----------------------------- 00078 00079 The LInf-norm Regularized Euclidean Projection (eppInf) 00080 00081 min 1/2 ||x- v||_2^2 + rho ||x||_Inf 00082 00083 which is can be solved by using eplb 00084 00085 Usage (in matlab) 00086 [x, lambda, iter_step]=eppInf(v, n, rho, rho0); 00087 00088 -------------------------- Function eppInf ----------------------------- 00089 */ 00090 void eppInf(double *x, double * c, int * iter_step, double *v, int n, double rho, double c0); 00091 00092 /* -------------------------- Function zerofind ----------------------------- 00093 00094 Find the root for the function: f(x) = x + c x^{p-1} - v, 00095 0 <= x <= v, v>=0 00096 1< p < infty, p \neq 2 00097 00098 Property: when p>2, f(x) is a convex function 00099 when 1<p<2, f(x) is a concave function 00100 00101 Method: we use Newton's method (other methods such as bisection can also work) 00102 00103 Note: we donot check the valid of the parameter. 00104 Since it is only employed in eepO, 00105 we can assure that these parameters satisfy the above conditions. 00106 00107 Usage (in matlab) 00108 [root, interStep]=eppInf(v, p, c, x0); 00109 00110 -------------------------- Function zerofind ----------------------------- 00111 */ 00112 void zerofind(double *root, int * iterStep, double v, double p, double c, double x0); 00113 00114 /* -------------------------- Function norm ----------------------------- 00115 00116 Compute the p-norm 00117 00118 -------------------------- Function norm ----------------------------- 00119 */ 00120 double norm(double * v, double p, int n); 00121 00122 /* -------------------------- Function eppInf ----------------------------- 00123 00124 The Lp-norm Regularized Euclidean Projection (eppO) for 1< p<Inf 00125 00126 min 1/2 ||x- v||_2^2 + rho ||x||_p 00127 00128 We solve two simple zero finding algorithms 00129 00130 Usage (in matlab) 00131 [x, c, iter_step]=eppO(v, n, rho, p); 00132 00133 -------------------------- Function eppInf ----------------------------- 00134 */ 00135 void eppO(double *x, double * cc, int * iter_step, double *v, int n, double rho, double p); 00136 00137 /* -------------------------- Function epp ----------------------------- 00138 00139 The Lp-norm Regularized Euclidean Projection (epp) for all p>=1 00140 00141 min 1/2 ||x- v||_2^2 + rho ||x||_p 00142 00143 This function uses the previously defined functions. 00144 00145 Usage (in matlab) 00146 [x, c, iter_step]=eppO(v, n, rho, p, c0); 00147 00148 -------------------------- Function epp ----------------------------- 00149 */ 00150 void epp(double *x, double * c, int * iter_step, double * v, int n, double rho, double p, double c0); 00151 #endif /* ----- #ifndef EPPHQ1_SLEP ----- */ 00152
