YALL1-Group: A solver for group/joint sparse reconstruction

From Wikimization

(Difference between revisions)
Jump to: navigation, search
(→Optional Input Arguments)
Line 1: Line 1:
-
YALL1-Group is a MATLAB software package for group/joint sparse reconstruction, written by Wei Deng, Wotao Yin and Yin Zhang at Rice University.
+
YALL1-Group is a MATLAB software package for group/joint sparse reconstruction, written by Wei Deng, [http://www.caam.rice.edu/~wy1/google_site/www.wotaoyin.com/ Wotao Yin] and [http://www.caam.rice.edu/~zhang/ Yin Zhang] at Rice University. [[http://yall1.blogs.rice.edu/ Download]]
----
----
Line 12: Line 12:
where <math>A\in \mathbb{R}^{m\times n}\,(m<n)</math>, <math>b\in \mathbb{R}^m</math>, <math>g_i</math> denotes the index set of the <math>i</math>-th group, and <math>w_i\geq0</math> is the weight for the <math>i</math>-th group.
where <math>A\in \mathbb{R}^{m\times n}\,(m<n)</math>, <math>b\in \mathbb{R}^m</math>, <math>g_i</math> denotes the index set of the <math>i</math>-th group, and <math>w_i\geq0</math> is the weight for the <math>i</math>-th group.
-
(2) Jointly-sparse basis pursuit model:
+
(2) Joint-sparse basis pursuit model:
Minimize <math>\|X\|_{w,2,1}:=\sum_{i=1}^n w_i\|x^i\|_2,</math>
Minimize <math>\|X\|_{w,2,1}:=\sum_{i=1}^n w_i\|x^i\|_2,</math>
subject to <math>AX=B,</math>
subject to <math>AX=B,</math>
-
where <math>A\in \mathbb{R}^{m\times n}\,(m<n),\, B\in \mathbb{R}^{m\times l}</math>, <math>x^i</math> denotes the <math>i</math>-th row of matrix <math>X</math>, and <math>w_i\geq0</math> is the weight for the <math>i</math>-th row.
+
where <math>A\in \mathbb{R}^{m\times n}\,(m<n)</math>, <math>B\in \mathbb{R}^{m\times l}</math>, <math>x^i</math> denotes the <math>i</math>-th row of matrix <math>X</math>, and <math>w_i\geq0</math> is the weight for the <math>i</math>-th row.
== Syntax ==
== Syntax ==
Line 23: Line 23:
:[x,Out] = YALL1_group(A,b,groups,'param1',value1,'param2',value2,...);
:[x,Out] = YALL1_group(A,b,groups,'param1',value1,'param2',value2,...);
-
== Required Input Arguments ==
+
== Input Arguments ==
*'''A''': an m-by-n matrix with m < n, or a structure with the following fields:
*'''A''': an m-by-n matrix with m < n, or a structure with the following fields:
-
:1) A.times(required): a function handle for <math>A*x</math>;
+
:1) '''A.times''' (required): a function handle for <math>A*x</math>;
-
:2) A.trans(required): a function handle for <math>A^T*x</math>;
+
:2) '''A.trans''' (required): a function handle for <math>A^T*x</math>;
-
:3) A.invIpAAt: a function handle for <math>(\beta_1I_m+\beta_2AA^T)^{-1}*x</math>;
+
:3) '''A.invIpAAt''': a function handle for <math>(\beta_1I_m+\beta_2AA^T)^{-1}*x</math>;
-
:4) A.invAAt: a function handle for <math>(AA^T)^{-1}*x</math>.
+
:4) '''A.invAAt''': a function handle for <math>(AA^T)^{-1}*x</math>.
-
Note: A.invIpAAt is only required when (a) primal solver is to be used, and b) A is non-orthonormal, and (c) exact linear system solving is to be performed.
+
Note: Field '''A.invIpAAt''' is only required when (a) primal solver is to be used, and b) A is non-orthonormal, and (c) exact linear system solving is to be performed. Field '''A.invAAt''' is only required when (a) dual solver is to be used, and b) A is non-orthonormal, and (c) exact linear system solving is to be performed.
-
A.invAAt is only required when (a) dual solver is to be used, and b) A is non-orthonormal, and (c) exact linear system solving is to be performed.
+
*'''b''': an m-vector for the group-sparse model or an m-by-l matrix for the joint-sparse model.
*'''b''': an m-vector for the group-sparse model or an m-by-l matrix for the joint-sparse model.
Line 38: Line 37:
*'''groups''': an n-vector containing the group number of the corresponding component of <math>x</math> for the group-sparse model, or [] for the joint-sparse model.
*'''groups''': an n-vector containing the group number of the corresponding component of <math>x</math> for the group-sparse model, or [] for the joint-sparse model.
-
== Optional Input Arguments ==
+
*Optional input arguments:
{| class="wikitable"
{| class="wikitable"
|-
|-
-
! Parameter Names !! Value !! Description
+
! Parameter Name !! Value !! Description
|-
|-
-
| ''''StopTolerance'''' || positive scalar || stopping tolerance value
+
| ''''StopTolerance'''' || positive scalar || Stopping tolerance value.
|-
|-
-
| ''''GrpWeights'''' || Example || weights for the groups
+
| ''''GrpWeights'''' || nonnegetive n-vector || Weights for the groups/rows.
|-
|-
-
| Example || Example || Example
+
| ''''nonorthA'''' || 0 or 1 || Specify if matrix A has non-orthonormal rows (1) or orthonormal rows (0).
|-
|-
-
| Example || Example || Example
+
| ''''ExactLinSolve'''' || 0 or 1 || Specify if linear systems are to be solve exactly (1) or approximately by taking a gradient descent step (0).
|-
|-
-
| Example || Example || Example
+
| ''''QuadPenaltyPar'''' || nonnegative 2-vector for primal solver or nonnegative scalar for dual solver || Penalty parameters.
|-
|-
-
| Example || Example || Example
+
| ''''StepLength'''' || nonnegative 2-vector for primal solver or nonnegative scalar for dual solver || Step lengths for updating the multipliers.
|-
|-
-
| Example || Example || Example
+
| ''''maxIter'''' || positive integer || Maximum number of iterations allowed.
|-
|-
-
| Example || Example || Example
+
| ''''xInitial'''' || an n-vector for group-sparse model or an n-by-l matrix for joint-sparse model || An initial estimate of the solution.
|-
|-
-
| Example || Example || Example
+
| ''''Solver'''' || 1 or 2 || Specify which solver to use: 1 for primal solver; 2 for dual solver.
|-
|-
-
| Example || Example || Example
+
| ''''Continuation'''' || 0 or 1 || Specify if continuation on the penalty parameters is to be used (1) or not (0). The continuation scheme is as follows: multiply the penalty parameters by a factor <math>c\,(c\,>\,1)</math> if <math>\|R\|_2 > \alpha\|Rp\|_2</math>, where 0< <math>\alpha</math> <1 is a parameter, <math>R</math> and <math>Rp</math> denote the constraint violations at the current and previous iterations, respectively.
|-
|-
-
| Example || Example || Example
+
| ''''ContParameter'''' || scalar between 0 and 1 || The parameter <math>\alpha</math> (0 < <math>\alpha</math> <1) in the continuation scheme.
|-
|-
-
| Example || Example || Example
+
| ''''ContFactor'''' || scalar greater than 1 || The factor <math>c\,(c\,>\,1)</math> in the continuation scheme.
|}
|}
 +
Note: the parameter names are not case-sensitive.
 +
 +
== Output Arguments ==
 +
*'''x''': last iterate (hopefully an approximate solution).
 +
*'''Out''': a structure with fields:
 +
**Out.status -- exit information;
 +
**Out.iter -- number of iterations taken;
 +
**Out.cputime -- solver CPU time.
 +
 +
== Examples ==
 +
Please see the demo files.
 +
 +
== Technical Report ==
 +
The description and theory of the YALL1-Group algorithm can be found in
 +
*Wei Deng, Wotao Yin, and Yin Zhang, [http://www.caam.rice.edu/~optimization/L1/GroupSparsity/group110419.pdf Group Sparse Optimization by Alternating Direction Method]. (TR11-06, Department of Computational and Applied Mathematics, Rice University, 2011)

Revision as of 06:11, 16 June 2011

YALL1-Group is a MATLAB software package for group/joint sparse reconstruction, written by Wei Deng, Wotao Yin and Yin Zhang at Rice University. [Download]

Contents

Model

(1) Group-sparse basis pursuit model: 

                  Minimize     LaTeX: \|x\|_{w,2,1}:=\sum_{i=1}^s w_i\|x_{g_i}\|_2,
  
                  subject to   LaTeX: Ax=b,

where LaTeX: A\in \mathbb{R}^{m\times n}\,(m<n), LaTeX: b\in \mathbb{R}^m, LaTeX: g_i denotes the index set of the LaTeX: i-th group, and LaTeX: w_i\geq0 is the weight for the LaTeX: i-th group.

(2) Joint-sparse basis pursuit model: 

                  Minimize     LaTeX: \|X\|_{w,2,1}:=\sum_{i=1}^n w_i\|x^i\|_2,
                  subject to   LaTeX: AX=B,

where LaTeX: A\in \mathbb{R}^{m\times n}\,(m<n), LaTeX: B\in \mathbb{R}^{m\times l}, LaTeX: x^i denotes the LaTeX: i-th row of matrix LaTeX: X, and LaTeX: w_i\geq0 is the weight for the LaTeX: i-th row.

Syntax

[x,Out] = YALL1_group(A,b,groups,'param1',value1,'param2',value2,...);

Input Arguments

  • A: an m-by-n matrix with m < n, or a structure with the following fields:
1) A.times (required): a function handle for LaTeX: A*x;
2) A.trans (required): a function handle for LaTeX: A^T*x;
3) A.invIpAAt: a function handle for LaTeX: (\beta_1I_m+\beta_2AA^T)^{-1}*x;
4) A.invAAt: a function handle for LaTeX: (AA^T)^{-1}*x.

Note: Field A.invIpAAt is only required when (a) primal solver is to be used, and b) A is non-orthonormal, and (c) exact linear system solving is to be performed. Field A.invAAt is only required when (a) dual solver is to be used, and b) A is non-orthonormal, and (c) exact linear system solving is to be performed.

  • b: an m-vector for the group-sparse model or an m-by-l matrix for the joint-sparse model.
  • groups: an n-vector containing the group number of the corresponding component of LaTeX: x for the group-sparse model, or [] for the joint-sparse model.
  • Optional input arguments:
Parameter Name Value Description
'StopTolerance' positive scalar Stopping tolerance value.
'GrpWeights' nonnegetive n-vector Weights for the groups/rows.
'nonorthA' 0 or 1 Specify if matrix A has non-orthonormal rows (1) or orthonormal rows (0).
'ExactLinSolve' 0 or 1 Specify if linear systems are to be solve exactly (1) or approximately by taking a gradient descent step (0).
'QuadPenaltyPar' nonnegative 2-vector for primal solver or nonnegative scalar for dual solver Penalty parameters.
'StepLength' nonnegative 2-vector for primal solver or nonnegative scalar for dual solver Step lengths for updating the multipliers.
'maxIter' positive integer Maximum number of iterations allowed.
'xInitial' an n-vector for group-sparse model or an n-by-l matrix for joint-sparse model An initial estimate of the solution.
'Solver' 1 or 2 Specify which solver to use: 1 for primal solver; 2 for dual solver.
'Continuation' 0 or 1 Specify if continuation on the penalty parameters is to be used (1) or not (0). The continuation scheme is as follows: multiply the penalty parameters by a factor LaTeX: c\,(c\,>\,1) if LaTeX: \|R\|_2 > \alpha\|Rp\|_2, where 0< LaTeX: \alpha <1 is a parameter, LaTeX: R and LaTeX: Rp denote the constraint violations at the current and previous iterations, respectively.
'ContParameter' scalar between 0 and 1 The parameter LaTeX: \alpha (0 < LaTeX: \alpha <1) in the continuation scheme.
'ContFactor' scalar greater than 1 The factor LaTeX: c\,(c\,>\,1) in the continuation scheme.

Note: the parameter names are not case-sensitive.

Output Arguments

  • x: last iterate (hopefully an approximate solution).
  • Out: a structure with fields:
    • Out.status -- exit information;
    • Out.iter -- number of iterations taken;
    • Out.cputime -- solver CPU time.

Examples

Please see the demo files.

Technical Report

The description and theory of the YALL1-Group algorithm can be found in

Retrieved from "http://www.convexoptimization.com/wikimization/index.php/YALL1-Group:_A_solver_for_group/joint_sparse_reconstruction"
Personal tools