Adaptive matching pursuit with constrained total least squares

Huang Tianyao, Liu Yimin, Meng Huadong, Wang, Wang Xiqin

Description

Compressive sensing (CS) can effectively recover a signal when it is sparse in some discrete atoms. However, in some applications, signals are sparse in a continuous parameter space, e.g., frequency space, rather than discrete atoms. Usually, we divide the continuous parameter into finite discrete grid points and build a dictionary from these grid points. However, the actual targets may not exactly lie on the grid points no matter how densely the parameter is grided, which introduces mismatch between the predefined dictionary and the actual one. In this article, a novel method, namely adaptive matching pursuit with constrained total least squares (AMP-CTLS), is proposed to find actual atoms even if they are not included in the initial dictionary. In AMP-CTLS, the grid and the dictionary are adaptively updated to better agree with measurements. The convergence of the algorithm is discussed, and numerical experiments demonstrate the advantages of AMP-CTLS.

Informations

• Publié par: biomed
• Publié le: 01 janvier 2012
• Nombre de lectures: 5
• Langue: English

Extrait

Huang et al. EURASIP Journal on Advances in Signal Processing 2012, 2012:76
http://asp.eurasipjournals.com/content/2012/1/76
RESEARCH Open Access
Adaptive matching pursuit with constrained total
least squares
*Tianyao Huang, Yimin Liu , Huadong Meng and Xiqin Wang
Abstract
Compressive sensing (CS) can effectively recover a signal when it is sparse in some discrete atoms. However, in
some applications, signals are sparse in a continuous parameter space, e.g., frequency space, rather than discrete
atoms. Usually, we divide the continuous parameter into finite discrete grid points and build a dictionary from
these grid points. However, the actual targets may not exactly lie on the grid points no matter how densely the
parameter is grided, which introduces mismatch between the predefined dictionary and the actual one. In this
article, a novel method, namely adaptive matching pursuit with constrained total least squares (AMP-CTLS), is
proposed to find actual atoms even if they are not included in the initial dictionary. In AMP-CTLS, the grid and the
dictionary are adaptively updated to better agree with measurements. The convergence of the algorithm is
discussed, and numerical experiments demonstrate the advantages of AMP-CTLS.
1 Introduction estimate [10-12]), we usually divide a continuous
paraA new class of techniques called compressed sampling or meter space into discrete grid points to generate the
compressive sensing (CS) has been widely used recently, dictionary. For example, in harmonic retrieval, frequency
due to the fact that CS techniques have shown good per- space is divided and dictionary is a discrete Fourier
formance in different areas such as signal processing, transform (DFT) matrix. The off-grid problem emerges
communication and statistics; see, e.g., [1]. Generally, CS when the actual frequencies are placed off the
predefinds the sparsest vector x from measurementsy=Fx, fined grid. The mismatch between the predefined and
whereF is often referred to as dictionary with more col- actual atom can lead to performance degradation in
umns than rows, and each column of the dictionary is sparse recovery (e.g., [13-15]).
called an atom or a basis. The grid misalignment problem in CS has recently
Matching pursuit (MP) is a set of popular greedy received growing interest. The sensitivity of CS to the
approaches to compressive sensing. The basic idea is to mismatch between the predefined and actual atoms is
sequentially find the support set of x and then project on studied in [13]; however, the focus of that article is
the selected atoms. The atoms selected in the support set mainly on mismatch analysis rather than development
are mainly determined by correlations between atoms of an algorithm. Cabrera et al. [16] and Zhu et al. [14],
and the regularized measurements [2]. MP methods respectively, provided an iterative re-weighted
(IRW)include standard MP [3], and several other examples, based and a Lasso-based method to recover an unknown
such as orthogonal matching pursuit (OMP) [4], regular- vector considering the atom misalignment, whereas we
focus on MP methods in this article. Compared withized OMP (ROMP) [5], stage-wise OMP (StOMP) [6],
IRW or Lasso, MP methods greedily find the supportcompressive sampling matching pursuit (CoSaMP) [7]
and subspace pursuit (SP) [2]. set and greatly reduce the dimension of the CS problem;
These MP methods [2-7] do not consider the off-grid thus, they have an advantage in computability. Gabriel
problem in grid-based CS approaches. In some applica- [17] proposed best basis compressive sensing in a
treetions of CS, such as harmonic retrieval and radar signal structured dictionary, but some dictionaries (e.g., DFT
processing (e.g., range profiling [8,9], direction of arrival matrix) do not possess a tree structure.
To alleviate the off-grid problem in matching pursuit,
we developed adaptive matching pursuit with constrained
* Correspondence: [e-mail]
total least squares (AMP-CTLS). In AMP-CTLS, we
Department of Electronic Engineering, Tsinghua University, Beijing, China
© 2012 Huang et al; licensee Springer. This is an Open Access article distributed under the terms of the Creative Commons Attribution
License (http://creativecommons.org/licenses/by/2.0), which permits unrestricted use, distribution, and reproduction in any medium,
provided the original work is properly cited.