SHOGUN
v3.2.0
首页
模块
类
文件
文件列表
文件成员
全部
类
命名空间
文件
函数
变量
类型定义
枚举
枚举值
友元
宏定义
组
src
shogun
lib
slep
flsa
flsa.h
浏览该文件的文档.
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 FLSA_SLEP
18
#define FLSA_SLEP
19
20
/*
21
22
In this file, we solve the Fused Lasso Signal Approximator (FLSA) problem:
23
24
min_x 1/2 \|x-v\|^2 + lambda1 * \|x\|_1 + lambda2 * \|A x\|_1, (1)
25
26
It can be shown that, if x* is the solution to
27
28
min_x 1/2 \|x-v\|^2 + lambda2 \|A x\|_1, (2)
29
30
then
31
x**= sgn(x*) max(|x*|-lambda_1, 0) (3)
32
33
is the solution to (1).
34
35
By some derivation (see the description in sfa.h), (2) can be solved by
36
37
x*= v - A^T z*,
38
39
where z* is the optimal solution to
40
41
min_z 1/2 z^T A AT z - < z, A v>,
42
subject to \|z\|_{infty} \leq lambda2 (4)
43
*/
44
45
46
47
/*
48
49
In flsa, we solve (1) corresponding to a given (lambda1, lambda2)
50
51
void flsa(double *x, double *z, double *gap,
52
double * v, double *z0,
53
double lambda1, double lambda2, int n,
54
int maxStep, double tol, int flag)
55
56
Output parameters:
57
x: the solution to problem (1)
58
z: the solution to problem (4)
59
infor: the information about running the subgradient finding algorithm
60
infor[0] = gap: the computed gap (either the duality gap
61
or the summation of the absolute change of the adjacent solutions)
62
infor[1] = steps: the number of iterations
63
infor[2] = lambad2_max: the maximal value of lambda2_max
64
infor[3] = numS: the number of elements in the support set
65
66
Input parameters:
67
v: the input vector to be projected
68
z0: a guess of the solution of z
69
70
lambad1: the regularization parameter
71
labmda2: the regularization parameter
72
n: the length of v and x
73
74
maxStep: the maximal allowed iteration steps
75
tol: the tolerance parameter
76
tau: the program sfa is checked every tau iterations for termination
77
flag: the flag for initialization and deciding calling sfa
78
switch ( flag )
79
1-4, 11-14: sfa
80
81
switch ( flag )
82
case 1, 2, 3, or 4:
83
z0 is a "good" starting point
84
(such as the warm-start of the previous solution,
85
or the user want to test the performance of this starting point;
86
the starting point shall be further projected to the L_{infty} ball,
87
to make sure that it is feasible)
88
89
case 11, 12, 13, or 14: z0 is a "random" guess, and thus not used
90
(we shall initialize z as follows:
91
if lambda2 >= 0.5 * lambda_2^max, we initialize the solution of the linear system;
92
if lambda2 < 0.5 * lambda_2^max, we initialize with zero
93
this solution is projected to the L_{infty} ball)
94
95
switch( flag )
96
5, 15: sfa_special
97
98
switch( flag )
99
5: z0 is a good starting point
100
15: z0 is a bad starting point, use the solution of the linear system
101
102
103
switch( flag )
104
6, 16: sfa_one
105
106
switch( flag )
107
6: z0 is a good starting point
108
16: z0 is a bad starting point, use the solution of the linear system
109
110
Revision made on October 31, 2009.
111
The input variable z0 is not modified after calling sfa. For this sake, we allocate a new variable zz to replace z0.
112
*/
113
void
flsa
(
double
*x,
double
*z,
double
*infor,
114
double
* v,
double
*z0,
115
double
lambda1,
double
lambda2,
int
n,
116
int
maxStep,
double
tol,
int
tau,
int
flag);
117
#endif
/* ----- #ifndef FLSA_SLEP ----- */
flsa
void flsa(double *x, double *z, double *infor, double *v, double *z0, double lambda1, double lambda2, int n, int maxStep, double tol, int tau, int flag)
Definition:
flsa.cpp:24
SHOGUN
Machine Learning Toolbox - Documentation