On the dynamics of ℓ1 decoding: A microscopic approach

ℓ₁ minimization, also called Basis Pursuit, has been known to have strong sparse recovery performance both theoretically and empirically. Previously known analytical approaches for ℓ₁ minimization have limitations in deriving custom stability performance bounds for signals with sparsity (the number of nonzero elements) level beyond the ℓ₁ weak recovery threshold [6]. In this paper, instead of focusing on the static decoding results of ℓ₁ minimization, we develop a microscopic analytical approach by studying the dynamics of ℓ₁ minimization. This approach can give useful characterizations of ℓ₁ decoding results and lead to new performance bounds on ℓ₁ decoding error. Contrary to known stability results for ℓ₁ minimization below the ℓ₁ weak threshold, we prove that ℓ₁ minimization decoding errors can experience an explosive growth in terms of the signal tail immediately beyond the ℓ₁ minimization weak threshold. This new analytical approach is motivated by the applications of analyzing the emerging iterative reweighted ℓ₁ minimization algorithms.