A Fast Algorithm for Recovery of Jointly Sparse Vectors based on
the Alternating Direction Methods
Hongtao Lu Xianzhong Long Jingyuan Lv
MOE-MS Key Laboratory for Intelligent Computing and Intelligent Systems
Department of Computer Science and Engineering
Shanghai Jiao Tong University, Shanghai 200240, China
{htlu,lxz85,lvjingyuan}@sjtu.edu.cn
Abstract
The standard compressive sensing (CS) aims
to recover sparse signal from single mea-
surement vector which is known as SMV
model. By contrast, recovery of sparse sig-
nals from multiple measurement vectors is
called MMV model. In this paper, we con-
sider the recovery of jointly sparse signals in
the MMV model where multiple signal mea-
surements are represented as a matrix and
the sparsity of signal occurs in common lo-
cations. The sparse MMV model can be for-
mulated as a matrix (2, 1)-norm minimiza-
tion problem, which is much more difficult
to solve than the l
1
-norm minimization in
standard CS. In this paper, we propose a
very fast algorithm, called MMV-ADM, to
solve the jointly sparse signal recovery prob-
lem in MMV settings based on the alter-
nating direction method (ADM). The MMV-
ADM alternately updates the recovered sig-
nal matrix, the Lagrangian multiplier and
the residue, and all update rules only involve
matrix or vector multiplications and summa-
tions, so it is simple, easy to implement and
much faster than the state-of-the-art method
MMVprox. Numerical simulations show that
MMV-ADM is at least dozens of times faster
than MMVprox with comparable recovery ac-
curacy.
Appearing in Proceedings of the 14
th
International Con-
ference on Artificial Intelligence and Statistics (AISTATS)
2011, Fort Lauderdale, FL, USA. Volume 15 of JMLR:
W&CP 15. Copyright 2011 by the authors.
1 INTRODUCTION
Many signals of interest often have sparse represen-
tations, meaning that signal is well approximated by
only a few nonzero coefficients in a specific basis. Com-
pressive sensing (CS) has recently emerged as an ac-
tive research area which aims to recover sparse signals
from measurement data (Candes et al., 2006; Donoho,
2006a). In the basic CS, the unknown sparse signal
is recovered from a single measurement vector, this
is referred to as a single measurement vector (SMV)
model. In this paper, we consider the problem of find-
ing sparse representation of signals from multiple mea-
surement vectors, which is known as the MMV model
(Chen et al., 2006). In the MMV model, signals are
represented as matrices and are assumed to have the
same sparsity structure. Specifically, the entire rows
of signal matrix may be 0.
The MMV model was initially motivated by a neu-
romagnetic inverse problem that arises in Magnetoen-
cephalography (MEG), a brain imaging modality (Cot-
ter et al., 2005). It is assumed that MEG signal is a
mixture of activities at a small number of possible acti-
vation regions in the brain. MMV model has also been
found in array processing (Gorodnitsky et al., 1997),
nonparametric spectrum analysis of time series (Sto-
ica et al.,1997), equalization of sparse communication
channel, linear inverse problem (Cotter et al.,2005),
DNA microarrays (Erickson et al., 2008) and source lo-
cation in sensor networks (Malioutov et al.,2003) etc..
Some known theoretical results of SMV have been
generalized to MMV (Chen at al., 2006) such as the
uniqueness under both l
0
-norm criteria and l
1
-norm
criteria, and the equivalence between the l
0
-norm ap-
proach and the l
1
-norm criteria. Several computa-
tion algorithms have also been proposed for solving
MMV problem. It has been proven that under certain
conditions, the orthogonal matching pursuit (OMP)
method can find the sparsest solution for MMV, just