SHOGUN
4.2.0
Main Page
Related Pages
Modules
Classes
Files
File List
File Members
All
Classes
Namespaces
Files
Functions
Variables
Typedefs
Enumerations
Enumerator
Friends
Macros
Modules
Pages
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