American Institute of Mathematical Sciences

Advanced
May  2020, 16(3): 1519-1526. doi: 10.3934/jimo.2019014

On phaseless compressed sensing with partially known support

Ying Zhang , Ling Ma and  Zheng-Hai Huang ,

School of Mathematics, Tianjin University, Tianjin 300072, China

* Corresponding author: ZHENG-HAI HUANG

Received  May 2018 Revised  October 2018 Published  May 2020 Early access  March 2019

Fund Project: This work was supported by the China Scholarship Council (Grant No. 201706255092) and the National Natural Science Foundation of China (Grant Nos. 11201332, 11431002 and 11871051)

We establish a theoretical framework for the problem of phaseless compressed sensing with partially known signal support, which aims at generalizing the Null Space Property and the Strong Restricted Isometry Property from phase retrieval to partially sparse phase retrieval. We first introduce the concepts of the Partial Null Space Property (P-NSP) and the Partial Strong Restricted Isometry Property (P-SRIP); and then show that both the P-NSP and the P-SRIP are exact recovery conditions for the problem of partially sparse phase retrieval. We also prove that a random Gaussian matrix $ A\in \mathbb{R}^{m\times n} $ satisfies the P-SRIP with high probability when $ m = O(t(k-r)\log(\frac{n-r}{t(k-r)})). $

Keywords: Phase retrieval, compressed sensing, phaseless compressed sensing, partial null space property, partial strong restricted isometry property.
Mathematics Subject Classification: Primary: 90C90; Secondary: 94A12.
Citation: Ying Zhang, Ling Ma, Zheng-Hai Huang. On phaseless compressed sensing with partially known support. Journal of Industrial and Management Optimization, 2020, 16 (3) : 1519-1526. doi: 10.3934/jimo.2019014
References:
[1]

B. Alexeev, A. S. Bandeira, M. Fickus and D. G. Mixon, Phase retrieval with polarization, SIAM J. Imag. Sci., 7 (2014), 35-66.  doi: 10.1137/12089939X.

[2]

R. Balan, B. Bodmann, P. G. Casazza and D. Edidin, Saving phase: injectivity and stability for phase retrieval, J. Fourier Anal. Appl., 15 (2009), 488-501.  doi: 10.1007/s00041-009-9065-1.

[3]

A.S. Bandeira, J. Cahill, D. Mixon and A. Nelson, Painless reconstruction from magnitudes of frame coefficients, Appl. Comput. Harmon. Anal., 37 (2014), 106-125.  doi: 10.1016/j.acha.2013.10.002.

[4]

A. S. Bandeira, K. Scheinberg and L. N. Vicente, On partial sparse recovery, preprint, arXiv: 1304.2809 (2013).

[5]

B. Bodmann and N. Hammen, Stable phase retrieval with low-redundancy frames, Adv. Comput. Math., 41 (2015), 317-331.  doi: 10.1007/s10444-014-9359-y.

[6]

O. Bunk, A. Diza, F. Pfeiffer, C. David, B. Schmitt, D. K. Satapathy and J. F. van der Veen, Diffractive imaging for periodic samples: Retrieving one-dimensional concentration profiles across microfluidic channels, Acta Crystallogr., A, Found. Crystallogr., 63 (2007), 306-314.  doi: 10.1107/S0108767307021903.

[7]

T. Cai and A. Zhang, Sparse representation of a polytope and recovery of sparse signals and low-rank matrices, IEEE Trans. Inf. Theory, 60 (2014), 122-132.  doi: 10.1109/TIT.2013.2288639.

[8]

E. J. Candès, The restricted isometry property and its implications for compressed sensing, C. R. Acad. Sci. Paris, Ser. I, 346 (2008), 589-592.  doi: 10.1016/j.crma.2008.03.014.

[9]

E. J. Candès, Y. C. Eldar, T. Strohmer and V. Voroninski, Phase retrieval via completion, SIAM Review, 57 (2015), 225-251.  doi: 10.1137/151005099.

[10]

E. J. Candès, T. Strohmer and V. Voroninski, Exact and stable signal recovery from magnitude measurements via convex programming, Commun. Pure Appl. Math., 66 (2013), 1241-1274.  doi: 10.1002/cpa.21432.

[11]

A. Conca, D. Edidin, M. Hering and C. Vinzant, An algebraic characterization of injectivity in phase retrieval, Appl. Comput. Harmon. Anal., 38 (2015), 346-356.  doi: 10.1016/j.acha.2014.06.005.

[12]

J. V. Corbett, The pauli problem, state reconstruction and quantum real numbers, Rep. Math. Phys., 57 (2006), 53-68.  doi: 10.1016/S0034-4877(06)80008-X.

[13]

L. Demanet and V. Jugnon, Convex recovery from interferometric measurements, IEEE Trans. Comput. Imaging, 3 (2017), 282–295, arXiv: 1307.6864. doi: 10.1109/TCI.2017.2688923.

[14]

M. P. Friedlander, H. Mansour, R. Saab and O. Yilmaz, Recovering compressively sampled signals using partial support information, IEEE Trans. Inf. Theory, 58 (2012), 1122-1134.  doi: 10.1109/TIT.2011.2167214.

[15]

B. Gao, Y. Wang and Z. Q. Xu, Stable signal recovery from phaseless measurements, J. Fourier Anal. Appl., 22 (2016), 787-808.  doi: 10.1007/s00041-015-9434-x.

[16]

R. W. Harrison, Phase problem in crystallography, J. Opt. Soc. Am. A., 10 (1993), 1046-1055. 

[17]

L. Jacques, A short note on compressed sensing with partially known signal support, Signal Process., 90 (2010), 3308-3312.  doi: 10.1016/j.sigpro.2010.05.025.

[18]

L. C. Kong and N. H. Xiu, Low-rank matrix recovery via nonconvex schatten p-minimization, Asia-Pac. J. Oper. Res., 30 (2013), 1340010. doi: 10.1142/S0217595913400101.

[19]

J. Miao, T. Ishikawa, Q. Shen and T. Earnest, Extending X-ray crystallography to allow the imagine of non-crystalline materials, cells and single protein complexes, Annu. Rev. Phys. Chem., 59 (2008), 387-410. 

[20]

R. P. Millane, Phase retrieval in crystallography and optics, J. Opt. Soc. Am. A., 7 (1990), 394-411.  doi: 10.1364/JOSAA.7.000394.

[21]

D. T. Peng, N. H. Xiu and J. Yu, $S_{1/2}$ regularization methods and fixed point algorithms for affine rank minimization problems, Comput. Optim. Appl., 67 (2017), 543-569.  doi: 10.1007/s10589-017-9898-5.

[22]

H. Qiu, X. Chen, W. Liu, G. Zhou, Y. J. Wang and J. Lai, A fast $l_1$-solver and its applications to robust face recognition, J. Ind. Manag. Optim., 8 (2012), 163-178.  doi: 10.3934/jimo.2012.8.163.

[23]

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

[24]

V. Voroninski and Z. Q. Xu, A strong restricted isometry property, with an application to phaseless compressed sensing, Appl. Comput. Harmon. Anal., 40 (2016), 386-395.  doi: 10.1016/j.acha.2015.06.004.

[25]

A. Walther, The question of phase retrieval in optics, J. Modern Opt., 10 (1963), 41-49.  doi: 10.1080/713817747.

[26]

Y. Wang and Z. Q. Xu, Phase retrieval for sparse signals, Appl. Comput. Harmon. Anal., 37 (2014), 531-544.  doi: 10.1016/j.acha.2014.04.001.

[27]

Y. Wang, W. Liu, L. Caccetta and G. Zhou, Parameter selection for nonnegative $l_1$ matrix/tensor sparse decomposition, Oper. Res. Lett., 43 (2015), 423-426.  doi: 10.1016/j.orl.2015.06.005.

[28]

Y. Wang, G. Zhou, L. Caccetta and W. Liu, An alternative Lagrange-dual based algorithm for sparse signal reconstruction, IEEE Trans. Signal Process., 59 (2011), 1895-1901.  doi: 10.1109/TSP.2010.2103066.

[29]

C. L. Xud an Y. B. Zhao, Uniqueness conditions for a class of $l_0$-minimization problems, Asia-Pac. J. Oper. Res., 32 (2015), 1540002, 17pp. doi: 10.1142/S0217595915400023.

[30]

G. W. You, Z. H. Huang and Y. Wang, A theoretical perspective of solving phaseless compressive sensing via its nonconvex relaxation, Inform. Sci., 415 (2017), 254-268.  doi: 10.1016/j.ins.2017.06.020.

[31]

L. J. Zhang, L. C. Kong, Y. Li and S. L. Zhou, A smoothing iterative method for quantile regression with nonconvex $l_p$ penalty, J. Ind. Manag. Optim., 13 (2017), 93-112.  doi: 10.3934/jimo.2016006.

show all references

References:
[1]

B. Alexeev, A. S. Bandeira, M. Fickus and D. G. Mixon, Phase retrieval with polarization, SIAM J. Imag. Sci., 7 (2014), 35-66.  doi: 10.1137/12089939X.

[2]

R. Balan, B. Bodmann, P. G. Casazza and D. Edidin, Saving phase: injectivity and stability for phase retrieval, J. Fourier Anal. Appl., 15 (2009), 488-501.  doi: 10.1007/s00041-009-9065-1.

[3]

A.S. Bandeira, J. Cahill, D. Mixon and A. Nelson, Painless reconstruction from magnitudes of frame coefficients, Appl. Comput. Harmon. Anal., 37 (2014), 106-125.  doi: 10.1016/j.acha.2013.10.002.

[4]

A. S. Bandeira, K. Scheinberg and L. N. Vicente, On partial sparse recovery, preprint, arXiv: 1304.2809 (2013).

[5]

B. Bodmann and N. Hammen, Stable phase retrieval with low-redundancy frames, Adv. Comput. Math., 41 (2015), 317-331.  doi: 10.1007/s10444-014-9359-y.

[6]

O. Bunk, A. Diza, F. Pfeiffer, C. David, B. Schmitt, D. K. Satapathy and J. F. van der Veen, Diffractive imaging for periodic samples: Retrieving one-dimensional concentration profiles across microfluidic channels, Acta Crystallogr., A, Found. Crystallogr., 63 (2007), 306-314.  doi: 10.1107/S0108767307021903.

[7]

T. Cai and A. Zhang, Sparse representation of a polytope and recovery of sparse signals and low-rank matrices, IEEE Trans. Inf. Theory, 60 (2014), 122-132.  doi: 10.1109/TIT.2013.2288639.

[8]

E. J. Candès, The restricted isometry property and its implications for compressed sensing, C. R. Acad. Sci. Paris, Ser. I, 346 (2008), 589-592.  doi: 10.1016/j.crma.2008.03.014.

[9]

E. J. Candès, Y. C. Eldar, T. Strohmer and V. Voroninski, Phase retrieval via completion, SIAM Review, 57 (2015), 225-251.  doi: 10.1137/151005099.

[10]

E. J. Candès, T. Strohmer and V. Voroninski, Exact and stable signal recovery from magnitude measurements via convex programming, Commun. Pure Appl. Math., 66 (2013), 1241-1274.  doi: 10.1002/cpa.21432.

[11]

A. Conca, D. Edidin, M. Hering and C. Vinzant, An algebraic characterization of injectivity in phase retrieval, Appl. Comput. Harmon. Anal., 38 (2015), 346-356.  doi: 10.1016/j.acha.2014.06.005.

[12]

J. V. Corbett, The pauli problem, state reconstruction and quantum real numbers, Rep. Math. Phys., 57 (2006), 53-68.  doi: 10.1016/S0034-4877(06)80008-X.

[13]

L. Demanet and V. Jugnon, Convex recovery from interferometric measurements, IEEE Trans. Comput. Imaging, 3 (2017), 282–295, arXiv: 1307.6864. doi: 10.1109/TCI.2017.2688923.

[14]

M. P. Friedlander, H. Mansour, R. Saab and O. Yilmaz, Recovering compressively sampled signals using partial support information, IEEE Trans. Inf. Theory, 58 (2012), 1122-1134.  doi: 10.1109/TIT.2011.2167214.

[15]

B. Gao, Y. Wang and Z. Q. Xu, Stable signal recovery from phaseless measurements, J. Fourier Anal. Appl., 22 (2016), 787-808.  doi: 10.1007/s00041-015-9434-x.

[16]

R. W. Harrison, Phase problem in crystallography, J. Opt. Soc. Am. A., 10 (1993), 1046-1055. 

[17]

L. Jacques, A short note on compressed sensing with partially known signal support, Signal Process., 90 (2010), 3308-3312.  doi: 10.1016/j.sigpro.2010.05.025.

[18]

L. C. Kong and N. H. Xiu, Low-rank matrix recovery via nonconvex schatten p-minimization, Asia-Pac. J. Oper. Res., 30 (2013), 1340010. doi: 10.1142/S0217595913400101.

[19]

J. Miao, T. Ishikawa, Q. Shen and T. Earnest, Extending X-ray crystallography to allow the imagine of non-crystalline materials, cells and single protein complexes, Annu. Rev. Phys. Chem., 59 (2008), 387-410. 

[20]

R. P. Millane, Phase retrieval in crystallography and optics, J. Opt. Soc. Am. A., 7 (1990), 394-411.  doi: 10.1364/JOSAA.7.000394.

[21]

D. T. Peng, N. H. Xiu and J. Yu, $S_{1/2}$ regularization methods and fixed point algorithms for affine rank minimization problems, Comput. Optim. Appl., 67 (2017), 543-569.  doi: 10.1007/s10589-017-9898-5.

[22]

H. Qiu, X. Chen, W. Liu, G. Zhou, Y. J. Wang and J. Lai, A fast $l_1$-solver and its applications to robust face recognition, J. Ind. Manag. Optim., 8 (2012), 163-178.  doi: 10.3934/jimo.2012.8.163.

[23]

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

[24]

V. Voroninski and Z. Q. Xu, A strong restricted isometry property, with an application to phaseless compressed sensing, Appl. Comput. Harmon. Anal., 40 (2016), 386-395.  doi: 10.1016/j.acha.2015.06.004.

[25]

A. Walther, The question of phase retrieval in optics, J. Modern Opt., 10 (1963), 41-49.  doi: 10.1080/713817747.

[26]

Y. Wang and Z. Q. Xu, Phase retrieval for sparse signals, Appl. Comput. Harmon. Anal., 37 (2014), 531-544.  doi: 10.1016/j.acha.2014.04.001.

[27]

Y. Wang, W. Liu, L. Caccetta and G. Zhou, Parameter selection for nonnegative $l_1$ matrix/tensor sparse decomposition, Oper. Res. Lett., 43 (2015), 423-426.  doi: 10.1016/j.orl.2015.06.005.

[28]

Y. Wang, G. Zhou, L. Caccetta and W. Liu, An alternative Lagrange-dual based algorithm for sparse signal reconstruction, IEEE Trans. Signal Process., 59 (2011), 1895-1901.  doi: 10.1109/TSP.2010.2103066.

[29]

C. L. Xud an Y. B. Zhao, Uniqueness conditions for a class of $l_0$-minimization problems, Asia-Pac. J. Oper. Res., 32 (2015), 1540002, 17pp. doi: 10.1142/S0217595915400023.

[30]

G. W. You, Z. H. Huang and Y. Wang, A theoretical perspective of solving phaseless compressive sensing via its nonconvex relaxation, Inform. Sci., 415 (2017), 254-268.  doi: 10.1016/j.ins.2017.06.020.

[31]

L. J. Zhang, L. C. Kong, Y. Li and S. L. Zhou, A smoothing iterative method for quantile regression with nonconvex $l_p$ penalty, J. Ind. Manag. Optim., 13 (2017), 93-112.  doi: 10.3934/jimo.2016006.

[1]

Steven L. Brunton, Joshua L. Proctor, Jonathan H. Tu, J. Nathan Kutz. Compressed sensing and dynamic mode decomposition. Journal of Computational Dynamics, 2015, 2 (2) : 165-191. doi: 10.3934/jcd.2015002
[2]

Zohre Aminifard, Saman Babaie-Kafaki. Diagonally scaled memoryless quasi–Newton methods with application to compressed sensing. Journal of Industrial and Management Optimization, 2021  doi: 10.3934/jimo.2021191
[3]

Yingying Li, Stanley Osher. Coordinate descent optimization for l1 minimization with application to compressed sensing; a greedy algorithm. Inverse Problems and Imaging, 2009, 3 (3) : 487-503. doi: 10.3934/ipi.2009.3.487
[4]

Song Li, Junhong Lin. Compressed sensing with coherent tight frames via $l_q$-minimization for $0 < q \leq 1$. Inverse Problems and Imaging, 2014, 8 (3) : 761-777. doi: 10.3934/ipi.2014.8.761
[5]

Mikhail Krastanov, Michael Malisoff, Peter Wolenski. On the strong invariance property for non-Lipschitz dynamics. Communications on Pure and Applied Analysis, 2006, 5 (1) : 107-124. doi: 10.3934/cpaa.2006.5.107
[6]

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

Jonathan Meddaugh. Shadowing as a structural property of the space of dynamical systems. Discrete and Continuous Dynamical Systems, 2022, 42 (5) : 2439-2451. doi: 10.3934/dcds.2021197
[8]

Yangyang Xu, Wotao Yin, Stanley Osher. Learning circulant sensing kernels. Inverse Problems and Imaging, 2014, 8 (3) : 901-923. doi: 10.3934/ipi.2014.8.901
[9]

Vikram Krishnamurthy, William Hoiles. Information diffusion in social sensing. Numerical Algebra, Control and Optimization, 2016, 6 (3) : 365-411. doi: 10.3934/naco.2016017
[10]

Zdzisław Brzeźniak, Paul André Razafimandimby. Irreducibility and strong Feller property for stochastic evolution equations in Banach spaces. Discrete and Continuous Dynamical Systems - B, 2016, 21 (4) : 1051-1077. doi: 10.3934/dcdsb.2016.21.1051
[11]

Taige Wang, Dihong Xu. A quantitative strong unique continuation property of a diffusive SIS model. Discrete and Continuous Dynamical Systems - S, 2022, 15 (6) : 1599-1614. doi: 10.3934/dcdss.2022024
[12]

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

Michael Röckner, Jiyong Shin, Gerald Trutnau. Non-symmetric distorted Brownian motion: Strong solutions, strong Feller property and non-explosion results. Discrete and Continuous Dynamical Systems - B, 2016, 21 (9) : 3219-3237. doi: 10.3934/dcdsb.2016095
[14]

Masahito Ohta. Strong instability of standing waves for nonlinear Schrödinger equations with a partial confinement. Communications on Pure and Applied Analysis, 2018, 17 (4) : 1671-1680. doi: 10.3934/cpaa.2018080
[15]

Hong Jiang, Wei Deng, Zuowei Shen. Surveillance video processing using compressive sensing. Inverse Problems and Imaging, 2012, 6 (2) : 201-214. doi: 10.3934/ipi.2012.6.201
[16]

Zhi-An Wang. A kinetic chemotaxis model with internal states and temporal sensing. Kinetic and Related Models, 2022, 15 (1) : 27-48. doi: 10.3934/krm.2021043
[17]

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

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

Kazuhiro Sakai. The oe-property of diffeomorphisms. Discrete and Continuous Dynamical Systems, 1998, 4 (3) : 581-591. doi: 10.3934/dcds.1998.4.581
[20]

Pablo Sánchez, Jaume Sempere. Conflict, private and communal property. Journal of Dynamics and Games, 2016, 3 (4) : 355-369. doi: 10.3934/jdg.2016019

2020 Impact Factor: 1.801

Tools

Metrics

  • PDF downloads (226)
  • HTML views (916)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy