WarmL1: A warm-start homotopy-based reconstruction algorithm for sparse signals
Journal
IEEE International Symposium on Information Theory - Proceedings
Pages
2226-2230
Date Issued
2012
Author(s)
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.2x to 37.5x speeding up or up to 1/5100 l2-error at the same computational cost compared to related works. © 2012 IEEE.
Event(s)
2012 IEEE International Symposium on Information Theory, ISIT 2012
Other Subjects
Computational costs; Computational effort; Dynamic modifications; Homotopies; Linear measurements; Reconstruction algorithms; Reconstruction problems; Reconstruction procedure; Sparse signals; Algorithms; Information theory; Iterative methods
Type
conference paper