Journal Home > Volume 22 , Issue 1

Sparse signal recovery problems are common in parameter estimation, image processing, pattern recognition, and so on. The problem of recovering a sparse signal representation from a signal dictionary might be classified as a linear constraint 0-quasinorm minimization problem, which is thought to be a Non-deterministic Polynomial-time (NP)-hard problem. Although several approximation methods have been developed to solve this problem via convex relaxation, researchers find the nonconvex methods to be more efficient in solving sparse recovery problems than convex methods. In this paper a nonconvex Exponential Metric Approximation (EMA) method is proposed to solve the sparse signal recovery problem. Our proposed EMA method aims to minimize a nonconvex negative exponential metric function to attain the sparse approximation and, with proper transformation, solve the problem via Difference Convex (DC) programming. Numerical simulations show that exponential metric function approximation yields better sparse recovery performance than other methods, and our proposed EMA-DC method is an efficient way to recover the sparse signals that are buried in noise.


menu
Abstract
Full text
Outline
About this article

Sparse Signal Recovery via Exponential Metric Approximation

Show Author's information Jian Pan( )Jun TangWei Zhu
Department of Electronic Engineering, Tsinghua University, Beijing 100084, China.

Abstract

Sparse signal recovery problems are common in parameter estimation, image processing, pattern recognition, and so on. The problem of recovering a sparse signal representation from a signal dictionary might be classified as a linear constraint 0-quasinorm minimization problem, which is thought to be a Non-deterministic Polynomial-time (NP)-hard problem. Although several approximation methods have been developed to solve this problem via convex relaxation, researchers find the nonconvex methods to be more efficient in solving sparse recovery problems than convex methods. In this paper a nonconvex Exponential Metric Approximation (EMA) method is proposed to solve the sparse signal recovery problem. Our proposed EMA method aims to minimize a nonconvex negative exponential metric function to attain the sparse approximation and, with proper transformation, solve the problem via Difference Convex (DC) programming. Numerical simulations show that exponential metric function approximation yields better sparse recovery performance than other methods, and our proposed EMA-DC method is an efficient way to recover the sparse signals that are buried in noise.

Keywords: sparse recovery, exponential metric approximation, sparsity tolerance, DC optimization, signal-to-noise-ratio

References(18)

[1]
Donoho D., Compressed sensing, IEEE Trans. Inf. Theory, vol. 52, no. 4, pp. 1289-1306, 2006.
[2]
Candes E., Romberg J., and Tao T., Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information, IEEE Trans. Inf. Theory, vol. 52, no. 2, pp. 489-509, 2006.
[3]
Tropp J. A., Recovery of short, complex linear combinations via minimization, IEEE Trans. Inf. Theory, vol. 51, no. 4, pp. 1568-1570, 2005.
[4]
Candes E., The restricted isometry property and its implications for compressed sensing, Comptes Rendus Mathematique, vol. 346, no. 9, pp. 589-592, 2008.
[5]
Foucart S. and Lai M., Sparsest solutions of underdetermined linear systems via p-minimization for 0<p1, Appl. Comput. Harmon. Anal., vol. 26, no. 3, pp. 395-407, 2009.
[6]
Xu Z., Chang X., Xu F., and Zhang H., L1/2 regularization: A thresholding representation theory and a fast solver, IEEE Trans. Neural Netw., Vol. 23, No. 7, 2012.;
[7]
Chartrand R. and Yin W., Iteratively reweighted algorithms for compressive sensing, in Proc. Int. Conf. Acoust., Speech, Signal Process. (ICASSP), 2008, pp. 3869-3872.
DOI
[8]
Gasso G., Rakotomamonjy A., and Canu S., Recovering sparse signals with a certain family of nonconvex penalties and DC programming, IEEE Trans. Signal Process, vol. 57, no. 12, pp. 4686-4698, 2009.
[9]
Tao P. D. and An L. T. H., Dc optimization algorithms for solving the trust region subproblem, SIAM J. Optimiz., vol. 8, no. 2, pp. 476-505, 1998.
[10]
Horst R. and Thoai N. V., DC programming: Overview, Journal of Optimization Theory and Application, no. 1, pp. 1-43, 1999.
[11]
Vial J., Strong and weak convexity of sets and functions, Math. Oper. Res., vol. 8, no. 2, pp. 231-259, 1983.
[12]
Boyd S. and Vandenberghe L., Convex Optimization. Cambridge, UK: Cambridge Univ. Press, 2004.
DOI
[13]
Clarke F., Generalized gradients and applications, Trans. Amer. Math. Soc., vol. 202, pp. 247-262, 1975.
[14]
Tao P. D. and Hoai L. T., DC optimization algorithms for solving the trust region subproblem, SIAM J. Optim., vol. 8, pp. 476-505, 1998.
[15]
Lethi H. A. and Tao P. D., The DC (Difference of Convex Functions) programming and DCA revisited with DC models of real world nonconvex optimization problems, Annals of Operations Research, vol. 133, pp. 23-46, 2005.
[16]
Rockafellar R. T., Convex Analysis. Princeton, NJ, USA: Princeton Univ. Press, 1970.
DOI
[17]
Grant M. and Boyd S., CVX: Matlab software for disciplined convex programming version 2.0 beta, http://cvxr.com/cvx, 2012
[18]
Tropp J. and Gilbert A., Signal recovery from random measurements via orthogonal matching pursuit, IEEE Trans. Inf. Theory, vol. 53, no. 12, pp. 4655-4666, 2007.
Publication history
Copyright
Acknowledgements
Rights and permissions

Publication history

Received: 14 March 2016
Revised: 24 October 2016
Accepted: 11 November 2016
Published: 26 January 2017
Issue date: February 2017

Copyright

© The author(s) 2017

Acknowledgements

This work supported in part by the National Natural Science Foundation of China (Nos. 61171120 and 61501504), the Key National Ministry Foundation of China (No. 9140A07020212JW0101), and the Foundation of Tsinghua University (No. 20141081772).

Rights and permissions

Return