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

Partial $S$-goodness for partially sparse signal recovery

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.
Citation: Lingchen Kong, Naihua Xiu, Guokai Liu. Partial $S$-goodness for partially sparse signal recovery. Numerical Algebra, Control and 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-257. doi: 10.1007/s10107-012-0578-z.

[2]

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

[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-81. doi: 10.1137/060657704.

[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-509. doi: 10.1109/TIT.2005.862083.

[5]

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

[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-905. doi: 10.1007/s00041-008-9045-x.

[7]

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

[8]

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

[9]

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

[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-122. doi: 10.1007/s10107-010-0418-y.

[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-2001. doi: 10.1109/TSP.2011.2107904.

[12]

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

[13]

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

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-257. doi: 10.1007/s10107-012-0578-z.

[2]

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

[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-81. doi: 10.1137/060657704.

[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-509. doi: 10.1109/TIT.2005.862083.

[5]

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

[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-905. doi: 10.1007/s00041-008-9045-x.

[7]

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

[8]

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

[9]

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

[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-122. doi: 10.1007/s10107-010-0418-y.

[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-2001. doi: 10.1109/TSP.2011.2107904.

[12]

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

[13]

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

[1]

Björn Popilka, Simon Setzer, Gabriele Steidl. Signal recovery from incomplete measurements in the presence of outliers. Inverse Problems and Imaging, 2007, 1 (4) : 661-672. doi: 10.3934/ipi.2007.1.661

[2]

Wanyou Cheng, Zixin Chen, Donghui Li. Nomonotone spectral gradient method for sparse recovery. Inverse Problems and Imaging, 2015, 9 (3) : 815-833. doi: 10.3934/ipi.2015.9.815

[3]

Hang Xu, Song Li. Analysis non-sparse recovery for relaxed ALASSO. Communications on Pure and Applied Analysis, 2020, 19 (8) : 4055-4068. doi: 10.3934/cpaa.2020179

[4]

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

[5]

Ting Chen, Fusheng Lv, Wenchang Sun. Uniform Approximation Property of Frames with Applications to Erasure Recovery. Communications on Pure and Applied Analysis, 2022, 21 (3) : 1093-1107. doi: 10.3934/cpaa.2022011

[6]

Abdulkarim Hassan Ibrahim, Poom Kumam, Min Sun, Parin Chaipunya, Auwal Bala Abubakar. Projection method with inertial step for nonlinear equations: Application to signal recovery. Journal of Industrial and Management Optimization, 2021  doi: 10.3934/jimo.2021173

[7]

Yi Shen, Song Li. Sparse signals recovery from noisy measurements by orthogonal matching pursuit. Inverse Problems and Imaging, 2015, 9 (1) : 231-238. doi: 10.3934/ipi.2015.9.231

[8]

Farid Ammar Khodja, Franz Chouly, Michel Duprez. Partial null controllability of parabolic linear systems. Mathematical Control and Related Fields, 2016, 6 (2) : 185-216. doi: 10.3934/mcrf.2016001

[9]

Plamen Stefanov, Gunther Uhlmann, Andras Vasy. On the stable recovery of a metric from the hyperbolic DN map with incomplete data. Inverse Problems and Imaging, 2016, 10 (4) : 1141-1147. doi: 10.3934/ipi.2016035

[10]

Jie Chen, Maarten de Hoop. The inverse problem for electroseismic conversion: Stable recovery of the conductivity and the electrokinetic mobility parameter. Inverse Problems and Imaging, 2016, 10 (3) : 641-658. doi: 10.3934/ipi.2016015

[11]

Barbara Abraham-Shrauner. Exact solutions of nonlinear partial differential equations. Discrete and Continuous Dynamical Systems - S, 2018, 11 (4) : 577-582. doi: 10.3934/dcdss.2018032

[12]

Wengu Chen, Huanmin Ge. Recovery of block sparse signals under the conditions on block RIC and ROC by BOMP and BOMMP. Inverse Problems and Imaging, 2018, 12 (1) : 153-174. doi: 10.3934/ipi.2018006

[13]

Onur Alp İlhan. Solvability of some partial integral equations in Hilbert space. Communications on Pure and Applied Analysis, 2008, 7 (4) : 837-844. doi: 10.3934/cpaa.2008.7.837

[14]

Yavar Kian, Alexander Tetlow. Hölder-stable recovery of time-dependent electromagnetic potentials appearing in a dynamical anisotropic Schrödinger equation. Inverse Problems and Imaging, 2020, 14 (5) : 819-839. doi: 10.3934/ipi.2020038

[15]

Yosra Soussi. Stable recovery of a non-compactly supported coefficient of a Schrödinger equation on an infinite waveguide. Inverse Problems and Imaging, 2021, 15 (5) : 929-950. doi: 10.3934/ipi.2021022

[16]

Alessandro Ferriero. A direct proof of the Tonelli's partial regularity result. Discrete and Continuous Dynamical Systems, 2012, 32 (6) : 2089-2099. doi: 10.3934/dcds.2012.32.2089

[17]

Moncef Aouadi, Kaouther Boulehmi. Partial exact controllability for inhomogeneous multidimensional thermoelastic diffusion problem. Evolution Equations and Control Theory, 2016, 5 (2) : 201-224. doi: 10.3934/eect.2016001

[18]

Huifang Jia, Gongbao Li, Xiao Luo. Stable standing waves for cubic nonlinear Schrödinger systems with partial confinement. Discrete and Continuous Dynamical Systems, 2020, 40 (5) : 2739-2766. doi: 10.3934/dcds.2020148

[19]

Mostafa Fazly, Yuan Li. Partial regularity and Liouville theorems for stable solutions of anisotropic elliptic equations. Discrete and Continuous Dynamical Systems, 2021, 41 (9) : 4185-4206. doi: 10.3934/dcds.2021033

[20]

Amin Boumenir, Vu Kim Tuan. Recovery of the heat coefficient by two measurements. Inverse Problems and Imaging, 2011, 5 (4) : 775-791. doi: 10.3934/ipi.2011.5.775

 Impact Factor: 

Metrics

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

Other articles
by authors

[Back to Top]