On phaseless compressed sensing with partially known support

Ying Zhang; Ling Ma; Zheng-Hai Huang

doi:10.3934/jimo.2019014

Previous Article
Statistical inference of semidefinite programming with multiple parameters
JIMO Home
This Issue
Next Article
A class of accelerated conjugate-gradient-like methods based on a modified secant equation

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 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 & 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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[4]	A. S. Bandeira, K. Scheinberg and L. N. Vicente, On partial sparse recovery, preprint, arXiv: 1304.2809 (2013). Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[16]	R. W. Harrison, Phase problem in crystallography, J. Opt. Soc. Am. A., 10 (1993), 1046-1055. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[25]	A. Walther, The question of phase retrieval in optics, J. Modern Opt., 10 (1963), 41-49. doi: 10.1080/713817747. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar

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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[4]	A. S. Bandeira, K. Scheinberg and L. N. Vicente, On partial sparse recovery, preprint, arXiv: 1304.2809 (2013). Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[16]	R. W. Harrison, Phase problem in crystallography, J. Opt. Soc. Am. A., 10 (1993), 1046-1055. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[25]	A. Walther, The question of phase retrieval in optics, J. Modern Opt., 10 (1963), 41-49. doi: 10.1080/713817747. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar

[1]	Zhihua Zhang, Naoki Saito. PHLST with adaptive tiling and its application to antarctic remote sensing image approximation. Inverse Problems & Imaging, 2014, 8 (1) : 321-337. doi: 10.3934/ipi.2014.8.321
[2]	Nhu N. Nguyen, George Yin. Stochastic partial differential equation models for spatially dependent predator-prey equations. Discrete & Continuous Dynamical Systems - B, 2020, 25 (1) : 117-139. doi: 10.3934/dcdsb.2019175
[3]	Bin Pei, Yong Xu, Yuzhen Bai. Convergence of p-th mean in an averaging principle for stochastic partial differential equations driven by fractional Brownian motion. Discrete & Continuous Dynamical Systems - B, 2020, 25 (3) : 1141-1158. doi: 10.3934/dcdsb.2019213
[4]	Hildeberto E. Cabral, Zhihong Xia. Subharmonic solutions in the restricted three-body problem. Discrete & Continuous Dynamical Systems - A, 1995, 1 (4) : 463-474. doi: 10.3934/dcds.1995.1.463
[5]	Guo-Bao Zhang, Ruyun Ma, Xue-Shi Li. Traveling waves of a Lotka-Volterra strong competition system with nonlocal dispersal. Discrete & Continuous Dynamical Systems - B, 2018, 23 (2) : 587-608. doi: 10.3934/dcdsb.2018035
[6]	Michael Grinfeld, Amy Novick-Cohen. Some remarks on stability for a phase field model with memory. Discrete & Continuous Dynamical Systems - A, 2006, 15 (4) : 1089-1117. doi: 10.3934/dcds.2006.15.1089
[7]	Jia Cai, Guanglong Xu, Zhensheng Hu. Sketch-based image retrieval via CAT loss with elastic net regularization. Mathematical Foundations of Computing, 2020, 3 (4) : 219-227. doi: 10.3934/mfc.2020013
[8]	Yuncherl Choi, Taeyoung Ha, Jongmin Han, Sewoong Kim, Doo Seok Lee. Turing instability and dynamic phase transition for the Brusselator model with multiple critical eigenvalues. Discrete & Continuous Dynamical Systems - A, 2021 doi: 10.3934/dcds.2021035
[9]	Valery Y. Glizer. Novel Conditions of Euclidean space controllability for singularly perturbed systems with input delay. Numerical Algebra, Control & Optimization, 2020 doi: 10.3934/naco.2020027
[10]	Alina Chertock, Alexander Kurganov, Mária Lukáčová-Medvi${\rm{\check{d}}}$ová, Șeyma Nur Özcan. An asymptotic preserving scheme for kinetic chemotaxis models in two space dimensions. Kinetic & Related Models, 2019, 12 (1) : 195-216. doi: 10.3934/krm.2019009
[11]	Wei Liu, Pavel Krejčí, Guoju Ye. Continuity properties of Prandtl-Ishlinskii operators in the space of regulated functions. Discrete & Continuous Dynamical Systems - B, 2017, 22 (10) : 3783-3795. doi: 10.3934/dcdsb.2017190
[12]	Tomáš Roubíček. An energy-conserving time-discretisation scheme for poroelastic media with phase-field fracture emitting waves and heat. Discrete & Continuous Dynamical Systems - S, 2017, 10 (4) : 867-893. doi: 10.3934/dcdss.2017044
[13]	Xiaomao Deng, Xiao-Chuan Cai, Jun Zou. A parallel space-time domain decomposition method for unsteady source inversion problems. Inverse Problems & Imaging, 2015, 9 (4) : 1069-1091. doi: 10.3934/ipi.2015.9.1069

American Institute of Mathematical Sciences

On phaseless compressed sensing with partially known support

References:

References:

Tools

Metrics

Other articles
by authors

Tools

Tools

Metrics

Other articles
by authors

American Institute of Mathematical Sciences

On phaseless compressed sensing with partially known support

References:

References:

Tools

Metrics

Other articlesby authors

Tools

Tools

Metrics

Other articlesby authors

Other articles
by authors

Other articles
by authors