Conference proceeding
On the dynamics of ℓ1 decoding: A microscopic approach
2010 IEEE International Symposium on Information Theory, pp.1588-1592
06/2010
DOI: 10.1109/ISIT.2010.5513438
Abstract
ℓ 1 minimization, also called Basis Pursuit, has been known to have strong sparse recovery performance both theoretically and empirically. Previously known analytical approaches for ℓ 1 minimization have limitations in deriving custom stability performance bounds for signals with sparsity (the number of nonzero elements) level beyond the ℓ 1 weak recovery threshold [6]. In this paper, instead of focusing on the static decoding results of ℓ 1 minimization, we develop a microscopic analytical approach by studying the dynamics of ℓ 1 minimization. This approach can give useful characterizations of ℓ 1 decoding results and lead to new performance bounds on ℓ 1 decoding error. Contrary to known stability results for ℓ 1 minimization below the ℓ 1 weak threshold, we prove that ℓ 1 minimization decoding errors can experience an explosive growth in terms of the signal tail immediately beyond the ℓ 1 minimization weak threshold. This new analytical approach is motivated by the applications of analyzing the emerging iterative reweighted ℓ 1 minimization algorithms.
Details
- Title: Subtitle
- On the dynamics of ℓ1 decoding: A microscopic approach
- Creators
- Weiyu Xu - Cornell UniversityAo Tang - Cornell University
- Resource Type
- Conference proceeding
- Publication Details
- 2010 IEEE International Symposium on Information Theory, pp.1588-1592
- Publisher
- IEEE
- DOI
- 10.1109/ISIT.2010.5513438
- ISSN
- 2157-8095
- eISSN
- 2157-8117
- Language
- English
- Date published
- 06/2010
- Academic Unit
- Electrical and Computer Engineering
- Record Identifier
- 9984196968002771
Metrics
9 Record Views