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

(Difference between revisions)
 Revision as of 16:09, 12 June 2011 (edit) (→Optional Input Arguments)← Previous diff Revision as of 05:11, 16 June 2011 (edit) (undo)Next diff → 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 $A\in \mathbb{R}^{m\times n}\,(m\,1)$ if $\|R\|_2 > \alpha\|Rp\|_2$, where 0< $\alpha$ <1 is a parameter, $R$ and $Rp$ denote the constraint violations at the current and previous iterations, respectively. |- |- - | Example || Example || Example + | ''''ContParameter'''' || scalar between 0 and 1 || The parameter $\alpha$ (0 < $\alpha$ <1) in the continuation scheme. |- |- - | Example || Example || Example + | ''''ContFactor'''' || scalar greater than 1 || The factor $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 + *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 05: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]

## 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, $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, $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.