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 & 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.

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

[7]

D. L. Donoho, Compressed sensing,, IEEE Trans. Inform. Theory, 52 (2006), 1289. 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.

[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.

[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.

[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.

[12]

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

[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.

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.

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

[7]

D. L. Donoho, Compressed sensing,, IEEE Trans. Inform. Theory, 52 (2006), 1289. 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.

[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.

[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.

[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.

[12]

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

[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.

[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]

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

[8]

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

[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]

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

[14]

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

[15]

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

[16]

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

[17]

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

[18]

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

[19]

Rafael Potrie. Partially hyperbolic diffeomorphisms with a trapping property. Discrete & Continuous Dynamical Systems - A, 2015, 35 (10) : 5037-5054. doi: 10.3934/dcds.2015.35.5037

[20]

Heiko Enderling, Alexander R.A. Anderson, Mark A.J. Chaplain, Glenn W.A. Rowe. Visualisation of the numerical solution of partial differential equation systems in three space dimensions and its importance for mathematical models in biology. Mathematical Biosciences & Engineering, 2006, 3 (4) : 571-582. doi: 10.3934/mbe.2006.3.571

 Impact Factor: 

Metrics

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

Other articles
by authors

[Back to Top]