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

From Wikimization

(Difference between revisions)
Jump to: navigation, search
m (Unprotected "YALL1-Group: A solver for group/joint sparse reconstruction": "Access Forbidden" error)
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 [http://dengwei.blogs.rice.edu 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 8: Line 8:
== Model ==
== Model ==
-
The following weighted <math>\ell_{2,1}</math>-regularization is known to facilitate group/joint sparsity in the solution.
+
<math>\ell_{2,1}</math>-based minimizatoin is one of the approaches for group or joint sparse reconstruction.
 +
*YALL1-Group solves models (1) and (2), and its future versions will support extensions of (1) and (2).
(1) Group-sparse basis pursuit model with or without nonnegativity constraint:
(1) Group-sparse basis pursuit model with or without nonnegativity constraint:
Line 16: Line 17:
<math>x\geq0</math> (optional)
<math>x\geq0</math> (optional)
-
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>w_i\geq0</math> is the weight for the <math>i</math>-th group;
 +
*<math>g_i</math> denotes the index set of the <math>i</math>-th group;
 +
*the groups may overlap.
(2) Joint-sparse basis pursuit model with or without nonnegativity constraint:
(2) Joint-sparse basis pursuit model with or without nonnegativity constraint:
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> or <math>A_jx_j=b_j</math>, for j=1,...,l
<math>X\geq0</math> (optional)
<math>X\geq0</math> (optional)
-
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.
+
where
 +
* the sensing matrix can be the same <math>A\in \mathbb{R}^{m\times n}\,(m<n)</math> for each channel (column) of X, or can be different <math>A_j\in \mathbb{R}^{m\times n}\,(m<n)</math> for each channel;
 +
* <math>B\in \mathbb{R}^{m\times l}</math>;
 +
* <math>x^i</math> and <math>x_j</math> denote the i-th row and j-th column of matrix <math>X</math>, respectively;
 +
* <math>w_i\geq0</math> is the weight for the <math>i</math>-th row.
== Syntax ==
== Syntax ==
Line 32: Line 42:
== Input Arguments ==
== Input Arguments ==
-
*'''A''': an m-by-n matrix with m < n, or a structure with the following fields:
+
*'''A''': multiple types of A can be accepted
-
:1) '''A.times''' (required): a function handle for <math>A*x</math>;
+
:1) an m-by-n matrix with m < n;
-
:2) '''A.trans''' (required): a function handle for <math>A^T*x</math>;
+
:2) a cell array of m-by-n matrices (for joint-sparse model with different sensing matrices);
-
:3) '''A.invIpAAt''': a function handle for <math>(\beta_1I_m+\beta_2AA^T)^{-1}*x</math>;
+
:3) a structure with the following fields:
-
:4) '''A.invAAt''': a function handle for <math>(AA^T)^{-1}*x</math>.
+
::a) '''A.times''' (required): a function handle for <math>A*x</math>;
 +
::b) '''A.trans''' (required): a function handle for <math>A^T*x</math>;
 +
::c) '''A.invIpAAt''': a function handle for <math>(\beta_1I_m+\beta_2AA^T)^{-1}*x</math>;
 +
::d) '''A.invAAt''': a function handle for <math>(AA^T)^{-1}*x</math>.
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.
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.
Line 42: Line 55:
*'''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.
-
*'''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''': different types of inputs for different models.
 +
:1) For non-overlapping group-sparse model -- an n-vector containing the group number of the corresponding component of x.
 +
:2) For overlapping group-sparse model -- a cell array whose i-th cell contains the indices of i-th group in a column vector.
 +
:3) For joint-sparse model -- [].
*Optional input arguments:
*Optional input arguments:
Line 52: Line 68:
|-
|-
| ''''GrpWeights'''' || nonnegetive n-vector || Weights for the groups/rows.
| ''''GrpWeights'''' || nonnegetive n-vector || Weights for the groups/rows.
 +
|-
 +
| ''''overlap'''' || true or false || True for overlapping groups.
|-
|-
| ''''Nonnegative'''' || true or false || True for imposing nonnegativity constraints.
| ''''Nonnegative'''' || true or false || True for imposing nonnegativity constraints.
Line 86: Line 104:
== Examples ==
== Examples ==
-
Please see the demo files.
+
Please see the demo files in the ''YALL1-Group'' package [http://yall1.blogs.rice.edu/ Download]:
 +
*''demo_group.m'': a demo of solving non-overlapping group-sparse model.
 +
*''demo_overlap_group.m'': a demo of solving overlapping group-sparse model.
 +
*''demo_joint.m'': a demo of solving joint-sparse model.
 +
*''demo_joint_multiple_A.m'': a demo of solving joint-sparse model with different sensing matrices A for the multiple measurements.
 +
*''demo_nonnegative.m'': a demo of imposing nonnegativity constraints in the group-sparse model.
== Technical Report ==
== Technical Report ==
The description and theory of the YALL1-Group algorithm can be found in
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)
*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 13:37, 21 August 2014

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

Introduction

In the last few years, finding sparse solutions to underdetermined linear systems has become an active research topic, particularly in the area of compressive sensing, statistics and machine learning. Sparsity allows us to reconstruct high dimensional data with only a small number of samples. In order to further enhance the recoverability, recent studies propose to go beyond sparsity and take into account additional information about the underlying structure of the solutions.

In practice, a wide class of solutions are known to have group sparsity structure. Namely, the solution has a natural grouping of its components, and the components within a group are likely to be either all zeros or all nonzeros. Joint sparsity is an interesting special case of the group sparsity structure. Joint sparse solutions consist of multiple sparse solutions that share a common nonzero support. Encoding the group/joint sparsity structure can reduce the degrees of freedom in the solution, thereby leading to better recovery performance.

Model

LaTeX: \ell_{2,1}-based minimizatoin is one of the approaches for group or joint sparse reconstruction.

  • YALL1-Group solves models (1) and (2), and its future versions will support extensions of (1) and (2).

(1) Group-sparse basis pursuit model with or without nonnegativity constraint:

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

where

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

(2) Joint-sparse basis pursuit model with or without nonnegativity constraint:

                  Minimize     LaTeX: \|X\|_{w,2,1}:=\sum_{i=1}^n w_i\|x^i\|_2
                  subject to   LaTeX: AX=B\, or LaTeX: A_jx_j=b_j, for j=1,...,l
                               LaTeX: X\geq0 (optional)

where

  • the sensing matrix can be the same LaTeX: A\in \mathbb{R}^{m\times n}\,(m<n) for each channel (column) of X, or can be different LaTeX: A_j\in \mathbb{R}^{m\times n}\,(m<n) for each channel;
  • LaTeX: B\in \mathbb{R}^{m\times l};
  • LaTeX: x^i and LaTeX: x_j denote the i-th row and j-th column of matrix LaTeX: X, respectively;
  • 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: multiple types of A can be accepted
1) an m-by-n matrix with m < n;
2) a cell array of m-by-n matrices (for joint-sparse model with different sensing matrices);
3) a structure with the following fields:
a) A.times (required): a function handle for LaTeX: A*x;
b) A.trans (required): a function handle for LaTeX: A^T*x;
c) A.invIpAAt: a function handle for LaTeX: (\beta_1I_m+\beta_2AA^T)^{-1}*x;
d) 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: different types of inputs for different models.
1) For non-overlapping group-sparse model -- an n-vector containing the group number of the corresponding component of x.
2) For overlapping group-sparse model -- a cell array whose i-th cell contains the indices of i-th group in a column vector.
3) For 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.
'overlap' true or false True for overlapping groups.
'Nonnegative' true or false True for imposing nonnegativity constraints.
'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.

Examples

Please see the demo files in the YALL1-Group package Download:

  • demo_group.m: a demo of solving non-overlapping group-sparse model.
  • demo_overlap_group.m: a demo of solving overlapping group-sparse model.
  • demo_joint.m: a demo of solving joint-sparse model.
  • demo_joint_multiple_A.m: a demo of solving joint-sparse model with different sensing matrices A for the multiple measurements.
  • demo_nonnegative.m: a demo of imposing nonnegativity constraints in the group-sparse model.

Technical Report

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

Personal tools