tesla_proj.cpp

Go to the documentation of this file.
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  TESLA_PROJ_SLEP
00018 #define  TESLA_PROJ_SLEP
00019 
00020 #include <stdlib.h>
00021 #include <stdio.h>
00022 #include <time.h>
00023 #include <math.h>
00024 #include <shogun/lib/slep/flsa/flsa.h>
00025 
00026 
00027 /*
00028 
00029    Functions contained in "flsa.h"
00030 
00031    void flsa(double *x, double *z, double *infor,
00032    double * v, double *z0, 
00033    double lambda1, double lambda2, int n, 
00034    int maxStep, double tol, int tau, int flag)
00035 
00036 */
00037 
00038 /*
00039    In this file, we need to make use of the function flsa for solving the following problem
00040 
00041    min 1/2 \|X - V\|_2^2  + lambda1 * \|X\|_1 + lambda2 \|X A^T\|_1   (1)
00042 
00043    where X and V are of size p x n
00044 
00045    For the definition of A, please refer to "flsa.h" and the included "sfa.h".
00046 
00047    The problem can be decoupled into the following 
00048 
00049    min_x  1/2 \|x-v\|^2  + lambda1 * \|x\|_1 + lambda2 * \|A x\|_1,   (2)
00050 
00051    where x and v correspond to a row of of X and V, respectively.
00052 
00053    The problem (2) is essentially the flsa problem, and can be solved by the function flsa.
00054 
00055 
00056    void tesla_proj(double *X, double *Z, double *gap,
00057    double *V, double *Z0,
00058    double lambda1, double lambda2, int p, int n,
00059    int maxStep, double tol, int flag)
00060 
00061    Output parameters:
00062 X:          the solution (of size p x n)
00063 Z:          the auxiliary variable (result by subgradient finding),
00064 Z can be used as a warm start for the next "tesla_proj", 
00065 size: p x (n-1)
00066 gap:        the gap for each decoupled flsa problem (of size p x 1)
00067 
00068 Input parameters:
00069 V:          the one to be projected
00070 Z0:         the starting point (see flag for whether it is used as the starting point)
00071 size: p x (n-1)
00072 
00073 lambda1:    the regularization parameter
00074 lambda2:    the regularization parameter
00075 p:          the number of rows in X and V
00076 n:          the number of columns in X and V
00077 
00078 maxStep:    the maximal allowed iteration steps
00079 tol:    the tolerance parameter
00080 flag:     the flag for initialization and deciding calling sfa
00081 switch ( flag )
00082 1-4, 11-14: sfa
00083 
00084 switch ( flag )
00085 case 1, 2, 3, or 4: 
00086 z0 is a "good" starting point 
00087 (such as the warm-start of the previous solution,
00088 or the user want to test the performance of this starting point;
00089 the starting point shall be further projected to the L_{infty} ball,
00090 to make sure that it is feasible)
00091 
00092 case 11, 12, 13, or 14: z0 is a "random" guess, and thus not used
00093 (we shall initialize z as follows:
00094 if lambda2 >= 0.5 * lambda_2^max, we initialize the solution of the linear system;
00095 if lambda2 <  0.5 * lambda_2^max, we initialize with zero
00096 this solution is projected to the L_{infty} ball)
00097 
00098 switch( flag )
00099 5, 15: sfa_special
00100 
00101 switch( flag )
00102 5:  z0 is a good starting point
00103 15: z0 is a bad starting point, use the solution of the linear system
00104 
00105 
00106 switch( flag )
00107 6, 16: sfa_one
00108 
00109 switch( flag )
00110     6:  z0 is a good starting point
00111     16: z0 is a bad starting point, use the solution of the linear system
00112 
00113     */
00114 
00115     void tesla_proj(double *X, double *Z, double *gap,
00116             double *V, double *Z0,
00117             double lambda1, double lambda2, int p, int n,
00118             int maxStep, double tol, int tau, int flag){
00119         /*
00120            We assume that X and V are of size p x n
00121            */
00122 
00123         int i, j;
00124         int nn=n-1;
00125         double
00126             *x    =(double *) malloc(sizeof(double)*n), 
00127             *v    =(double *) malloc(sizeof(double)*n),
00128             *z    =(double *) malloc(sizeof(double)*nn),
00129             *z0   =(double *) malloc(sizeof(double)*nn),
00130             *infor=(double *) malloc(sizeof(double)*4);
00131         //double temp;
00132 
00133 
00134 
00135         if (n<3){
00136             printf("\n n should be equal to or larger than 3");
00137             exit(-1);
00138         }
00139 
00140 
00141         for(i=0;i<p; i++){
00142 
00143             /*
00144                copy a row of V to v
00145                */
00146             for (j=0;j<n; j++)
00147                 v[j]=V[j*p + i];
00148 
00149             /*
00150                copy a row of Z0 to z0
00151                */
00152             for (j=0;j<nn; j++)
00153                 z0[j]=Z0[j*p + i];
00154 
00155             /*
00156                call flsa to compute x
00157                */
00158 
00159             flsa(x, z, infor,
00160                     v, z0, 
00161                     lambda1, lambda2, n, 
00162                     maxStep, tol, tau, flag);
00163 
00164 
00165             /*
00166                store the solution x to X
00167                */
00168             for (j=0;j<n; j++)
00169                 X[j*p + i]=x[j];
00170 
00171             /*
00172                store the solution z to Z
00173                */
00174             for (j=0;j<nn; j++)
00175                 Z[j*p + i]=z[j];
00176 
00177             gap[i]=infor[0];
00178         }
00179 
00180 
00181         free(x);
00182         free(v);
00183         free(z);
00184         free(z0);
00185         free(infor);
00186 
00187     }
00188 #endif   /* ----- #ifndef TESLA_PROJ_SLEP  ----- */
00189 
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines

SHOGUN Machine Learning Toolbox - Documentation