ISD
A New Sparse Signal Reconstruction Algorithm via Iterative Support Detection

Introduction

ISD is as fast as L1-minimization but requires fewer measurements. ISD addresses wrong solutions of L1 construction due to insufficient measurements. It will learn from such wrong solutions and solve new minimization problems that return a perfect or a better solution. A demo is given on Pages 4 and 5 of our report.

You can download an efficient implementation of ISD, called threshold-ISD, for recovering signals with fast decaying distributions of nonzeros from compressive measurements. The package includes numerical experiments showing that ISD has significant overall advantages over the classical L1 minimization approach, as well as two other state-of-the-art algorithms: the iterative reweighted L1 minimization algorithm (IRL1) [link] and the iterative reweighted least--squares algorithm (IRLS) [link].

History

The idea and algorithm were initially come up in August 2008.

Status

  • Latest revision on June 11, 2010.
  • EdgeCS: edge guided compressive sensing reconstruction, published in VCIP'10, joint work with Weihong Guo. [pdf]
  • A joint-sparsity version and is under development.
  • Version 1.1 is online with video tutorials.

Citation

Y. Wang and W. Yin. Sparse signal reconstruction via iterative support detection. SIAM Journal on Imaging Sciences, 3(3), pp. 462-491 (2010).

Previously as: Compressed sensing via iterative support detection, Rice University CAAM Technical Report TR09-30, 2009.

Download

  • Tech report [pdf] by Y. Wang and W. Yin, last updated in June 2010
  • Slides: Wotao Yin @ Duke CS workshop, Feburary 2009 [link]; Yilun Wang PhD defense, June 2009 [link].

Version 1.1 (November 3, 2009). [download]
  • This version is much simpler and clearer than ver 1.0 below.
  • Video tutorials: Demo [online] or [download]; Main code [online] or [download].
  • To adapter the code to your data and sparse/compressible signal and for best results, please (i) tune the thresholding methods and parameters, and (ii) consider replacing YALL1 by one designed for your data. The technical report [pdf] describes ideas of effective thresholding.
  • Despite the small problems given in the demos, the code is capable of solving large-scale, multi-dimensional problems. Ver 1.0 below includes large-scale tests. The allowed size of the problem is merely subject to the limit posted by the subproblem solver used.
  • The main code can be extended to deal with multi-dimensional signals in a straightforward way.

Version 1.0 (September 23, 2009). [download]
  • Contents: threshold-ISD, test problems, YALL1 solver
  • Language: MATLAB (tested on versions 2007 - 2009)

License

Threshold-ISD Copyright (C) 2009-2010, Yilun Wang, Wotao Yin

This program is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version.

This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.

You should have received a copy of the GNU General Public License along with this program. If not, see <http://www.gnu.org/licenses/>.

Related Software and Links