Sparse Signal Recovery via Kalman-Filter-based ℓ1 Minimization

Abstract In many problems high-dimensional discrete signals need to be reconstructed from noisy and often undersampled data, raising the issue of solving nominally underdetermined noise-contaminated systems of equations. The theory of compressed sensing states (and proves) that such signals can uniquely be reconstructed. The nullspace property of the sensing matrix ensures the recovery of the sparse/compressible representation by l1 minimization, which can be realized either by convex optimization approaches or alternatively by estimation-theoretic approaches, e.g., by extended linearized Kalman filters. Herewith, we establish new results on sparse signal recovery via l1 minimization using such a Kalman filter. First, we use a convergence acceleration scheme, which makes the algorithm converge to the same solution as the primal-dual algorithm by Chambolle & Pock. Then, we complement the l1-minimizing Kalman filter with an external thresholding. Let s be the sparsity and m the number of rows of A . The results show that the l1-minimizing Kalman filter with external thresholding yields a faster algorithm for the reconstruction of x → with s/m  & Pock. In the noiseless case the l1-minimizing Kalman filter with external thresholding used less iterations than the Orthogonal Matching Pursuit.