WarmL1: A warm-start homotopy-based reconstruction algorithm for sparse signals
Authors:
- 1 July 2012
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 2226-2230
Abstract
A sparse signal can be reconstructed from a small amount of random and linear measurements by solving a system of underdetermined equations. In this paper, we study the reconstruction problem while the system undergoes dynamic modifications. Resolving this problem from scratch requires high computational efforts. Therefore, we propose an efficient homotopy-based reconstruction algorithm with warmstart, named WarmL1. WarmL1 quickly updates the previous solution to the desired one. Based on the concept of homotopy, WarmL1 breaks the reconstruction procedure into simple steps, and solves the problem iteratively. Four possible applications are presented and discussed to demonstrate the usage of WarmL1 for different warm-start situations. Experiments on these applications are performed. The results show that WarmL1 achieves 3.2× to 37.5× speeding up or up to 1/5100 l2-error at the same computational cost compared to related works.Keywords
This publication has 10 references indexed in Scilit:
- Identifying bad measurements in compressive sensing2011
- Sparse signal recovery and dynamic update of the underdetermined system2010
- Deconvolutional networks2010
- Dynamic updating for sparse time varying signals2009
- Fast Solution of $\ell _{1}$-Norm Minimization Problems When the Solution May Be SparseIEEE Transactions on Information Theory, 2008
- Gradient Projection for Sparse Reconstruction: Application to Compressed Sensing and Other Inverse ProblemsIEEE Journal of Selected Topics in Signal Processing, 2007
- $rm K$-SVD: An Algorithm for Designing Overcomplete Dictionaries for Sparse RepresentationIEEE Transactions on Signal Processing, 2006
- Compressed sensingIEEE Transactions on Information Theory, 2006
- Stable signal recovery from incomplete and inaccurate measurementsCommunications on Pure and Applied Mathematics, 2006
- Row Modifications of a Sparse Cholesky FactorizationSIAM Journal on Matrix Analysis and Applications, 2005