Extended Compressed Sensing: Filtering Inspired Methods for Sparse Signal Recovery and Their Nonlinear Variants

New methods are presented for sparse signal recovery from a sequence of noisy observations. The sparse recovery problem, which is NP-hard in general, is addressed by resorting to convex and non-convex relaxations. The body of algorithms in this work extends and consolidate the recently introduced Kalman filtering (KF)-based compressed sensing methods. These simple methods, which are briefly reviewed here, rely on a pseudo-measurement trick for incorporating the norm relaxations following from CS theory. The extension of the methods to the nonlinear case is discussed and the notion of local CS is introduced. The essential idea is that CS can be applied for recovering sufficiently small and sparse state perturbations thereby improving nonlinear estimation in cases where the sensing function maps the state onto a lower-dimensional space. Other two methods are considered in this work. The extended Baum-Welch (EBW), a popular algorithm for discriminative training of speech models, is amended here for recovery of normalized sparse signals. This method naturally handles nonlinearities and therefore has a prominent advantage over the nonlinear extensions of the KF-based algorithms which rely on validity of linearization. The last method derived in this work is based on a Markov chain Monte Carlo (MCMC) mechanism. This method roughly divides the sparse recovery problem into two parts. Thus, the MCMC is used for optimizing the support of the signal while an auxiliary estimation algorithm yields the value of elements. An extensive numerical study is provided in which the methods are compared and analyzed. As part of this, the KF-based algorithm is applied to lossy speech compression.

By: Avishy Carmi; Pini Gurfil; Dimitri Kanevsky; Bhuvana Ramabhadran

Published in: RC24755 in 2009


This Research Report is available. This report has been submitted for publication outside of IBM and will probably be copyrighted if accepted for publication. It has been issued as a Research Report for early dissemination of its contents. In view of the transfer of copyright to the outside publisher, its distribution outside of IBM prior to publication should be limited to peer communications and specific requests. After outside publication, requests should be filled only by reprints or legally obtained copies of the article (e.g., payment of royalties). I have read and understand this notice and am a member of the scientific community outside or inside of IBM seeking a single copy only.


Questions about this service can be mailed to reports@us.ibm.com .