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

From Wikimization

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 1 Model 2 Syntax 3 Input Arguments 4 Output Arguments 5 Examples 6 Technical Report

Model

(1) Group-sparse basis pursuit model:

                  Minimize     
  
                  subject to   

where , , denotes the index set of the -th group, and is the weight for the -th group.

(2) Joint-sparse basis pursuit model:

                  Minimize     
                  subject to   

where , , denotes the -th row of matrix , and is the weight for the -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 ;

2) A.trans (required): a function handle for ;

3) A.invIpAAt: a function handle for ;

4) A.invAAt: a function handle for .

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 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 if , where 0< <1 is a parameter, and denote the constraint violations at the current and previous iterations, respectively.
'ContParameter'	scalar between 0 and 1	The parameter (0 < <1) in the continuation scheme.
'ContFactor'	scalar greater than 1	The factor 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, Group Sparse Optimization by Alternating Direction Method. (TR11-06, Department of Computational and Applied Mathematics, Rice University, 2011)