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]

Björn Popilka, Simon Setzer, Gabriele Steidl. Signal recovery from incomplete measurements in the presence of outliers. Inverse Problems & 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 & Imaging, 2015, 9 (3) : 815-833. doi: 10.3934/ipi.2015.9.815
[3]

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

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

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

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

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

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

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

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

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

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

Kangkang Deng, Zheng Peng, Jianli Chen. Sparse probabilistic Boolean network problems: A partial proximal-type operator splitting method. Journal of Industrial & Management Optimization, 2019, 15 (4) : 1881-1896. doi: 10.3934/jimo.2018127
[14]

Valter Pohjola. An inverse problem for the magnetic Schrödinger operator on a half space with partial data. Inverse Problems & Imaging, 2014, 8 (4) : 1169-1189. doi: 10.3934/ipi.2014.8.1169
[15]

Vianney Perchet, Marc Quincampoix. A differential game on Wasserstein space. Application to weak approachability with partial monitoring. Journal of Dynamics & Games, 2019, 6 (1) : 65-85. doi: 10.3934/jdg.2019005
[16]

Fenglong Qu, Jiaqing Yang. On recovery of an inhomogeneous cavity in inverse acoustic scattering. Inverse Problems & Imaging, 2018, 12 (2) : 281-291. doi: 10.3934/ipi.2018012
[17]

Vinicius Albani, Uri M. Ascher, Xu Yang, Jorge P. Zubelli. Data driven recovery of local volatility surfaces. Inverse Problems & Imaging, 2017, 11 (5) : 799-823. doi: 10.3934/ipi.2017038
[18]

Amin Boumenir, Vu Kim Tuan, Nguyen Hoang. The recovery of a parabolic equation from measurements at a single point. Evolution Equations & Control Theory, 2018, 7 (2) : 197-216. doi: 10.3934/eect.2018010
[19]

Victor Isakov. Recovery of time dependent volatility coefficient by linearization. Evolution Equations & Control Theory, 2014, 3 (1) : 119-134. doi: 10.3934/eect.2014.3.119
[20]

Nguyen Thieu Huy, Pham Van Bang. Invariant stable manifolds for partial neutral functional differential equations in admissible spaces on a half-line. Discrete & Continuous Dynamical Systems - B, 2015, 20 (9) : 2993-3011. doi: 10.3934/dcdsb.2015.20.2993

 Impact Factor: 

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2019 American Institute of Mathematical Sciences