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

From Wikimization

(Difference between revisions)
Jump to: navigation, search
Line 42: Line 42:
== 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 ==
== Examples ==

Revision as of 15:07, 29 May 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



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.


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)


  • 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)


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


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


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