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

(Difference between revisions)
 Revision as of 06:11, 16 June 2011 (edit)← Previous diff Revision as of 21:57, 20 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, [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]] + 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 46: Line 46: | ''''GrpWeights'''' || nonnegetive n-vector || Weights for the groups/rows. | ''''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). + | ''''nonorthA'''' || true or false || Specify if matrix A has non-orthonormal rows (true) or orthonormal rows (false). |- |- - | ''''ExactLinSolve'''' || 0 or 1 || Specify if linear systems are to be solve exactly (1) or approximately by taking a gradient descent step (0). + | ''''ExactLinSolve'''' || true or false || Specify if linear systems are to be solve exactly (true) or approximately by taking a gradient descent step (false). |- |- | ''''QuadPenaltyPar'''' || nonnegative 2-vector for primal solver or nonnegative scalar for dual solver || Penalty parameters. | ''''QuadPenaltyPar'''' || nonnegative 2-vector for primal solver or nonnegative scalar for dual solver || Penalty parameters. Line 60: Line 60: | ''''Solver'''' || 1 or 2 || Specify which solver to use: 1 for primal solver; 2 for dual solver. | ''''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 $c\,(c\,>\,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. + | ''''Continuation'''' || true or false || Specify if continuation on the penalty parameters is to be used (true) or not (false). The continuation scheme is as follows: multiply the penalty parameters by a factor $c\,(c\,>\,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. Continuation allows small initial penalty parameters for + constraint violations, which lead to faster initial convergence, and it increases those parameters whenever the violation reduction slows down. It leads to overall speedups in most cases. |- |- | ''''ContParameter'''' || scalar between 0 and 1 || The parameter $\alpha$ (0 < $\alpha$ <1) in the continuation scheme. | ''''ContParameter'''' || scalar between 0 and 1 || The parameter $\alpha$ (0 < $\alpha$ <1) in the continuation scheme. Line 66: Line 67: | ''''ContFactor'''' || scalar greater than 1 || The factor $c\,(c\,>\,1)$ in the continuation scheme. | ''''ContFactor'''' || scalar greater than 1 || The factor $c\,(c\,>\,1)$ in the continuation scheme. |} |} - Note: the parameter names are not case-sensitive. + *'''Note''': the parameter names are not case-sensitive. == Output Arguments == == Output Arguments == *'''x''': last iterate (hopefully an approximate solution). *'''x''': last iterate (hopefully an approximate solution). *'''Out''': a structure with fields: *'''Out''': a structure with fields: - **Out.status -- exit information; + **Out.status—exit information; - **Out.iter -- number of iterations taken; + **Out.iter—number of iterations taken; - **Out.cputime -- solver CPU time. + **Out.cputime—solver CPU time. == Examples == == Examples ==

## Revision as of 21:57, 20 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' true or false Specify if matrix A has non-orthonormal rows (true) or orthonormal rows (false).
'ExactLinSolve' true or false Specify if linear systems are to be solve exactly (true) or approximately by taking a gradient descent step (false).
'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' true or false Specify if continuation on the penalty parameters is to be used (true) or not (false). 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. Continuation allows small initial penalty parameters for

constraint violations, which lead to faster initial convergence, and it increases those parameters whenever the violation reduction slows down. It leads to overall speedups in most cases.

'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.