SHOGUN
6.0.0
src
shogun
lib
slep
flsa
tesla_proj.cpp
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
#ifdef USE_GPL_SHOGUN
18
19
#ifndef TESLA_PROJ_SLEP
20
#define TESLA_PROJ_SLEP
21
22
#include <stdlib.h>
23
#include <stdio.h>
24
#include <time.h>
25
#include <math.h>
26
#include <
shogun/lib/slep/flsa/flsa.h
>
27
28
29
/*
30
31
Functions contained in "flsa.h"
32
33
void flsa(double *x, double *z, double *infor,
34
double * v, double *z0,
35
double lambda1, double lambda2, int n,
36
int maxStep, double tol, int tau, int flag)
37
38
*/
39
40
/*
41
In this file, we need to make use of the function flsa for solving the following problem
42
43
min 1/2 \|X - V\|_2^2 + lambda1 * \|X\|_1 + lambda2 \|X A^T\|_1 (1)
44
45
where X and V are of size p x n
46
47
For the definition of A, please refer to "flsa.h" and the included "sfa.h".
48
49
The problem can be decoupled into the following
50
51
min_x 1/2 \|x-v\|^2 + lambda1 * \|x\|_1 + lambda2 * \|A x\|_1, (2)
52
53
where x and v correspond to a row of of X and V, respectively.
54
55
The problem (2) is essentially the flsa problem, and can be solved by the function flsa.
56
57
58
void tesla_proj(double *X, double *Z, double *gap,
59
double *V, double *Z0,
60
double lambda1, double lambda2, int p, int n,
61
int maxStep, double tol, int flag)
62
63
Output parameters:
64
X: the solution (of size p x n)
65
Z: the auxiliary variable (result by subgradient finding),
66
Z can be used as a warm start for the next "tesla_proj",
67
size: p x (n-1)
68
gap: the gap for each decoupled flsa problem (of size p x 1)
69
70
Input parameters:
71
V: the one to be projected
72
Z0: the starting point (see flag for whether it is used as the starting point)
73
size: p x (n-1)
74
75
lambda1: the regularization parameter
76
lambda2: the regularization parameter
77
p: the number of rows in X and V
78
n: the number of columns in X and V
79
80
maxStep: the maximal allowed iteration steps
81
tol: the tolerance parameter
82
flag: the flag for initialization and deciding calling sfa
83
switch ( flag )
84
1-4, 11-14: sfa
85
86
switch ( flag )
87
case 1, 2, 3, or 4:
88
z0 is a "good" starting point
89
(such as the warm-start of the previous solution,
90
or the user want to test the performance of this starting point;
91
the starting point shall be further projected to the L_{infty} ball,
92
to make sure that it is feasible)
93
94
case 11, 12, 13, or 14: z0 is a "random" guess, and thus not used
95
(we shall initialize z as follows:
96
if lambda2 >= 0.5 * lambda_2^max, we initialize the solution of the linear system;
97
if lambda2 < 0.5 * lambda_2^max, we initialize with zero
98
this solution is projected to the L_{infty} ball)
99
100
switch( flag )
101
5, 15: sfa_special
102
103
switch( flag )
104
5: z0 is a good starting point
105
15: z0 is a bad starting point, use the solution of the linear system
106
107
108
switch( flag )
109
6, 16: sfa_one
110
111
switch( flag )
112
6: z0 is a good starting point
113
16: z0 is a bad starting point, use the solution of the linear system
114
115
*/
116
117
void
tesla_proj(
double
*X,
double
*Z,
double
*gap,
118
double
*V,
double
*Z0,
119
double
lambda1,
double
lambda2,
int
p,
int
n,
120
int
maxStep,
double
tol,
int
tau,
int
flag){
121
/*
122
We assume that X and V are of size p x n
123
*/
124
125
int
i, j;
126
int
nn=n-1;
127
double
128
*x =(
double
*) malloc(
sizeof
(
double
)*n),
129
*v =(
double
*) malloc(
sizeof
(
double
)*n),
130
*z =(
double
*) malloc(
sizeof
(
double
)*nn),
131
*z0 =(
double
*) malloc(
sizeof
(
double
)*nn),
132
*infor=(
double
*) malloc(
sizeof
(
double
)*4);
133
//double temp;
134
135
136
137
if
(n<3){
138
printf(
"\n n should be equal to or larger than 3"
);
139
exit(-1);
140
}
141
142
143
for
(i=0;i<p; i++){
144
145
/*
146
copy a row of V to v
147
*/
148
for
(j=0;j<n; j++)
149
v[j]=V[j*p + i];
150
151
/*
152
copy a row of Z0 to z0
153
*/
154
for
(j=0;j<nn; j++)
155
z0[j]=Z0[j*p + i];
156
157
/*
158
call flsa to compute x
159
*/
160
161
flsa(x, z, infor,
162
v, z0,
163
lambda1, lambda2, n,
164
maxStep, tol, tau, flag);
165
166
167
/*
168
store the solution x to X
169
*/
170
for
(j=0;j<n; j++)
171
X[j*p + i]=x[j];
172
173
/*
174
store the solution z to Z
175
*/
176
for
(j=0;j<nn; j++)
177
Z[j*p + i]=z[j];
178
179
gap[i]=infor[0];
180
}
181
182
183
free(x);
184
free(v);
185
free(z);
186
free(z0);
187
free(infor);
188
189
}
190
#endif
/* ----- #ifndef TESLA_PROJ_SLEP ----- */
191
192
#endif //USE_GPL_SHOGUN
flsa.h
SHOGUN
Machine Learning Toolbox - Documentation