American Institute of Mathematical Sciences

Advanced
2014, 4(1): 25-38. doi: 10.3934/naco.2014.4.25

Partial $S$-goodness for partially sparse signal recovery

Lingchen Kong 1, , Naihua Xiu 1, and  Guokai Liu 2,

1. 

Department of Applied Mathematics, Beijing Jiaotong University, Beijing 100044, China, China
2. 

Department of Anesthesia, Dongzhimen Hospital, Beijing University of Chinese Medicine, No.5 Haiyuncang, Dongcheng District, Beijing 100700, China

Received  May 2013 Revised  October 2013 Published  December 2013

In this paper, we will consider the problem of partially sparse signal recovery (PSSR), which is the signal recovery from a certain number of linear measurements when its part is known to be sparse. We establish and characterize partial $s$-goodness for a sensing matrix in PSSR. We show that the partial $s$-goodness condition is equivalent to the partial null space property (NSP), and is weaker than partial restricted isometry property. Moreover, this provides a verifiable approach for partial NSP via partial $s$-goodness constants. We also give exact and stable partially $s$-sparse recovery via the partial $l_1$-norm minimization under mild assumptions.
Keywords: partial $s$-goodness, exact and stable recovery., Partially sparse signal recovery, partial null space property.
Mathematics Subject Classification: Primary: 90C26, 65J22; Secondary: 65K1.
Citation: Lingchen Kong, Naihua Xiu, Guokai Liu. Partial $S$-goodness for partially sparse signal recovery. Numerical Algebra, Control & Optimization, 2014, 4 (1) : 25-38. doi: 10.3934/naco.2014.4.25
References:
[1]

A. Bandeira, K. Scheinberg and L. N. Vicente, Computation of sparse low degree interpolating polynomials and their application to derivative-free optimization,, Math. Program., 134 (2012), 223.  doi: 10.1007/s10107-012-0578-z.  Google Scholar

[2]

A. Bandeira, K. Scheinberg and L. N. Vicente, On partially sparse recovery,, Tech. Rep., (2011).   Google Scholar

[3]

A. M. Bruckstein, D. L. Donoho and M. Elad, From sparse solutions of systems of equations to sparse modeling of signals and images,, SIAM Review, 51 (2009), 34.  doi: 10.1137/060657704.  Google Scholar

[4]

E. J. Candés, J. Romberg and T. Tao, Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information,, IEEE Trans. Inform. Theory, 52 (2006), 489.  doi: 10.1109/TIT.2005.862083.  Google Scholar

[5]

E. J. Candés and T. Tao, Decoding by linear programming,, IEEE Trans. Inform. Theory, 51 (2005), 4203.  doi: 10.1109/TIT.2005.858979.  Google Scholar

[6]

E. J. Candés, M. B. Wakin and S. P. Boyd, Enhancing sparsity by reweighted l1 minimization,, J Fourier Anal Appl., 14 (2008), 877.  doi: 10.1007/s00041-008-9045-x.  Google Scholar

[7]

D. L. Donoho, Compressed sensing,, IEEE Trans. Inform. Theory, 52 (2006), 1289.  doi: 10.1109/TIT.2006.871582.  Google Scholar

[8]

L. Jacques, A short note on compressed sensing with partially known signal support,, Signal Processing, 90 (2010), 3308.   Google Scholar

[9]

A. Juditsky and A. S. Nemirovski, On verifiable sufficient conditions for sparse signal recovery via l1 minimization,, Math. Program., 127 (2011), 57.  doi: 10.1007/s10107-010-0417-z.  Google Scholar

[10]

A. Juditsky, F. Karzan and A. S. Nemirovski, Verifiable conditions of l1-recovery of sparse signals with sign restrictions,, Math. Program., 127 (2011), 89.  doi: 10.1007/s10107-010-0418-y.  Google Scholar

[11]

M. A. Khajehnejad, W. Xu, A. S. Avestimehr and B. Hassibi, Analyzing weighted minimization for sparse recovery with nonuniform sparse models,, IEEE Trans. Signal Process., 59 (2011), 1985.  doi: 10.1109/TSP.2011.2107904.  Google Scholar

[12]

A. Majumdar and R. K. Ward, An algorithm for sparse MRI reconstruction by Schatten p-norm minimization,, Magnetic Resonance Imaging, 29 (2011), 408.   Google Scholar

[13]

N. Vaswani and W. Lu, Modifed-CS: modifying compressive sensing for problems with partially known support,, IEEE Trans. Signal Process., 58 (2010), 4595.  doi: 10.1109/TSP.2010.2051150.  Google Scholar

show all references

References:
[1]

A. Bandeira, K. Scheinberg and L. N. Vicente, Computation of sparse low degree interpolating polynomials and their application to derivative-free optimization,, Math. Program., 134 (2012), 223.  doi: 10.1007/s10107-012-0578-z.  Google Scholar

[2]

A. Bandeira, K. Scheinberg and L. N. Vicente, On partially sparse recovery,, Tech. Rep., (2011).   Google Scholar

[3]

A. M. Bruckstein, D. L. Donoho and M. Elad, From sparse solutions of systems of equations to sparse modeling of signals and images,, SIAM Review, 51 (2009), 34.  doi: 10.1137/060657704.  Google Scholar

[4]

E. J. Candés, J. Romberg and T. Tao, Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information,, IEEE Trans. Inform. Theory, 52 (2006), 489.  doi: 10.1109/TIT.2005.862083.  Google Scholar

[5]

E. J. Candés and T. Tao, Decoding by linear programming,, IEEE Trans. Inform. Theory, 51 (2005), 4203.  doi: 10.1109/TIT.2005.858979.  Google Scholar

[6]

E. J. Candés, M. B. Wakin and S. P. Boyd, Enhancing sparsity by reweighted l1 minimization,, J Fourier Anal Appl., 14 (2008), 877.  doi: 10.1007/s00041-008-9045-x.  Google Scholar

[7]

D. L. Donoho, Compressed sensing,, IEEE Trans. Inform. Theory, 52 (2006), 1289.  doi: 10.1109/TIT.2006.871582.  Google Scholar

[8]

L. Jacques, A short note on compressed sensing with partially known signal support,, Signal Processing, 90 (2010), 3308.   Google Scholar

[9]

A. Juditsky and A. S. Nemirovski, On verifiable sufficient conditions for sparse signal recovery via l1 minimization,, Math. Program., 127 (2011), 57.  doi: 10.1007/s10107-010-0417-z.  Google Scholar

[10]

A. Juditsky, F. Karzan and A. S. Nemirovski, Verifiable conditions of l1-recovery of sparse signals with sign restrictions,, Math. Program., 127 (2011), 89.  doi: 10.1007/s10107-010-0418-y.  Google Scholar

[11]

M. A. Khajehnejad, W. Xu, A. S. Avestimehr and B. Hassibi, Analyzing weighted minimization for sparse recovery with nonuniform sparse models,, IEEE Trans. Signal Process., 59 (2011), 1985.  doi: 10.1109/TSP.2011.2107904.  Google Scholar

[12]

A. Majumdar and R. K. Ward, An algorithm for sparse MRI reconstruction by Schatten p-norm minimization,, Magnetic Resonance Imaging, 29 (2011), 408.   Google Scholar

[13]

N. Vaswani and W. Lu, Modifed-CS: modifying compressive sensing for problems with partially known support,, IEEE Trans. Signal Process., 58 (2010), 4595.  doi: 10.1109/TSP.2010.2051150.  Google Scholar

[1]

Xuemei Chen, Julia Dobrosotskaya. Inpainting via sparse recovery with directional constraints. Mathematical Foundations of Computing, 2020, 3 (4) : 229-247. doi: 10.3934/mfc.2020025
[2]

Andy Hammerlindl, Jana Rodriguez Hertz, Raúl Ures. Ergodicity and partial hyperbolicity on Seifert manifolds. Journal of Modern Dynamics, 2020, 16: 331-348. doi: 10.3934/jmd.2020012
[3]

Tommi Brander, Joonas Ilmavirta, Petteri Piiroinen, Teemu Tyni. Optimal recovery of a radiating source with multiple frequencies along one line. Inverse Problems & Imaging, 2020, 14 (6) : 967-983. doi: 10.3934/ipi.2020044
[4]

Hua Qiu, Zheng-An Yao. The regularized Boussinesq equations with partial dissipations in dimension two. Electronic Research Archive, 2020, 28 (4) : 1375-1393. doi: 10.3934/era.2020073
[5]

Lorenzo Zambotti. A brief and personal history of stochastic partial differential equations. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 471-487. doi: 10.3934/dcds.2020264
[6]

Yueyang Zheng, Jingtao Shi. A stackelberg game of backward stochastic differential equations with partial information. Mathematical Control & Related Fields, 2020  doi: 10.3934/mcrf.2020047
[7]

Mostafa Mbekhta. Representation and approximation of the polar factor of an operator on a Hilbert space. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020463
[8]

Yu Zhou, Xinfeng Dong, Yongzhuang Wei, Fengrong Zhang. A note on the Signal-to-noise ratio of $ (n, m) $-functions. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020117
[9]

Hirokazu Ninomiya. Entire solutions of the Allen–Cahn–Nagumo equation in a multi-dimensional space. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 395-412. doi: 10.3934/dcds.2020364
[10]

Marion Darbas, Jérémy Heleine, Stephanie Lohrengel. Numerical resolution by the quasi-reversibility method of a data completion problem for Maxwell's equations. Inverse Problems & Imaging, 2020, 14 (6) : 1107-1133. doi: 10.3934/ipi.2020056

 Impact Factor: 

Tools

Metrics

  • PDF downloads (33)
  • HTML views (0)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2020 American Institute of Mathematical Sciences