×

An inexact projected gradient method for sparsity-constrained quadratic measurements regression. (English) Zbl 1415.94097

Summary: In this paper, we employ the sparsity-constrained least squares method to reconstruct sparse signals from the noisy measurements in high-dimensional case, and derive the existence of the optimal solution under certain conditions. We propose an inexact sparse-projected gradient method for numerical computation and discuss its convergence. Moreover, we present numerical results to demonstrate the efficiency of the proposed method.

MSC:

94A12 Signal theory (characterization, reconstruction, filtering, etc.)
65K05 Numerical mathematical programming methods
90C26 Nonconvex programming, global optimization

Software:

GESPAR
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Balan, R, Casazza, P and Edidin, D (2006). On signal reconstruction without phase. Applied and Computational Harmonic Analysis, 20(3), 345-356. · Zbl 1090.94006
[2] Bandeira, A, Cahill, J, Mixon, D and Nelson, A (2014). Saving phase: Injectivity and stability for phase retrieval. Applied and Computational Harmonic Analysis, 37(1), 106-125. · Zbl 1305.90330
[3] Beck, A, Stoica, P and Li, J (2008a). Exact and approximate solutions of source localization problems. IEEE Transactions on Signal Processing, 56(5), 1770-1778. · Zbl 1390.94091
[4] Beck, A, Teboulle, M and Chikishev, Z (2008b). Iterative minimization schemes for solving the single source localization problem. SIAM Journal on Optimization, 19(3), 1397-1416. · Zbl 1180.90242
[5] Beck, A and Eldar, Y (2013). Sparsity constrained nonlinear optimization: Optimality conditions and algorithms. SIAM Journal on Optimization, 23(3), 1480-1509. · Zbl 1295.90051
[6] Biswas, P and Ye, Y (2004). Semidefinite programming for ad hoc wireless sensor network localization. In Proc. 3rd Int. Symp. Information Processing in Sensor Networks, IEEE, Berkeley, CA, pp. 46-54.
[7] Blumensath, T (2013). Compressed sensing with nonlinear observations and related nonlinear optimization problems. IEEE Transactions on Information Theory, 59(6), 3466-3474. · Zbl 1364.94111
[8] Blumensath, T and Davies, ME (2009). Iterative hard thresholding for compressed sensing. Applied and Computational Harmonic Analysis, 27(3), 265-274. · Zbl 1174.94008
[9] Candès, EJ, Strohmery, T and Voroninski, V (2013a). PhaseLift: Exact and stable signal recovery from magnitude measurements via convex programming. Communications on Pure and Applied Mathematics, 66(8), 1241-1274. · Zbl 1335.94013
[10] Candès, EJ, Eldar, YC, Strohmery, T and Voroninski, V (2013b). Phase retrieval via matrix completion. SIAM Journal on Imaging Sciences, 6(1), 199-225. · Zbl 1280.49052
[11] Chen, H, Jiang, G and Yoshihira, K (2007). Monitoring high-dimensional data for failure detection and localization in large-scale computing systems. IEEE Transactions on Knowledge Data Engineering, 20(1), 13-25.
[12] Eldar, Y and Mendelson, S (2014). Phase retrieval: Stability and recovery guarantees. Applied and Computational Harmonic Analysis, 36(3), 473-494. · Zbl 06298184
[13] Eldar, Y, Sidorenko, P, Mixon, D, Barel, S and Cohen, O (2015). Sparse phase retrieval from short-time Fourier measurements. IEEE Signal Processing Letters, 22(5), 638-642.
[14] Fan, J, Kong, L, Wang, L and Xiu, N (2016). The uniqueness and greedy method for quadratic compressive sensing. In 2016 IEEE 3rd Int. Conf. Data Science and Advanced Analytics (DSAA), pp. 808-815.
[15] Fan, J, Kong, L, Wang, L and Xiu, N (2018). Variable selection in sparse regression with quadratic measurements. Statistica Sinica, 28(3), 1157-1178. · Zbl 1394.62091
[16] Lauer, F and H Ohlsson (2014). Sparse phase retrieval via group-sparse optimization. arXiv:1402.5803. · Zbl 1347.90078
[17] Lévyleduc, C and Roueff, F (2009). Detection and localization of change-points in high-dimensional network traffic data. Annals of Applied Statistics, 3(2), 3483-3485.
[18] Li, X and Voroninski, V (2012). Sparse signal recovery from quadratic measurements via convex programming. SIAM Journal on Mathematical Analysis, 45(5), 3019-3033. · Zbl 1320.94023
[19] Lung-Yut-Fong, A, Lévy-Leduc, C and Cappé, O (2012). Distributed detection/localization of change-points in high-dimensional network traffic data. Statistics and Computing, 32(2), 485-496. · Zbl 1322.62146
[20] Mao, G, Fidan, B and Anderson, B (2007). Wireless sensor network localization techniques. Computer Networks, 51(10), 2529-2553. · Zbl 1120.68021
[21] Meng, C, Ding, Z and Dasgupta, S (2008). A semidefinite programming approach to source localization in wireless sensor networks. IEEE Signal Processing Letters, 15, 253-256.
[22] Natarajan, B (1995). Sparse approximate solutions to linear systems. SIAM Journal on Computing, 24, 227-234. · Zbl 0827.68054
[23] Ohlsson, H and Eldar, Y (2014). On conditions for uniqueness in sparse phase retrieval. In IEEE Int. Conf. Acoustics, Speech and Signal Processing (ICASSP), pp. 1841-1845.
[24] Ohlsson, H, Yang, A, Dong, R and Sastry, S (2012). CPRL—An extension of compressive sensing to the phase retrieval problem. In Advances in Neural Information Processing Systems, Curran Associates, Inc., Lake Tahoe, Nevada, pp. 1367-1375.
[25] Ohlsson, H, A Yang, R Dong, M Verhaegen and S Sastry (2013). Quadratic basis pursuit. arXiv:1301.7002.
[26] Pan, L, Zhou, S, Xiu, N and Qi, H (2017). A convergent iterative hard thresholding for sparsity and nonnegativity constrained optimization. Pacific Journal of Optimization, 13(2), 325-353. · Zbl 1384.90078
[27] Patterson, S, Eldar, YC and Keidar, I (2014). Distributed compressed sensing for static and time-varying networks. IEEE Transactions on Signal Processing, 62(19), 4931-4946. · Zbl 1394.94450
[28] Qi, H, Xiu, N and Yuan, X (2013). A Lagrangian dual approach to the single-source localization problem. IEEE Transactions on Signal Processing, 61(15), 3815-3826. · Zbl 1393.94401
[29] Shechtman, Y, Eldar, Y, Szameit, A and Segev, M (2011). Sparsity-based sub-wavelength imaging with partially spatially incoherent light via quadratic compressed sensing. Optics Express, 19(16), 14807-14822.
[30] Shechtman, Y, Szameit, A, Bullkich, Eet al. (2012). Sparsity-based single-shot sub-wavelength coherent diffractive imaging. Nature Materials, 11(5), 455-459.
[31] Shechtman, Y, Beck, A and Eldar, Y (2014). GESPAR: Efficient phase retrieval of sparse signals. IEEE Transactions on Signal Processing, 62(4), 928-938. · Zbl 1394.94522
[32] Vlassis, N, Terwijn, B and Krose, B (2002). Auxiliary particle filter robot localization from high-dimensional sensor observations. IEEE International Conference on Robotics and Automation, 1, 7-12.
[33] Wang, Y and Xu, Z (2014). Phase retrieval for sparse signals. Applied and Computational Harmonic Analysis, 37(3), 531-544. · Zbl 1297.94009
[34] Wang, Y, Qi, L and Zhang, X (2009). A practical method for computing the largest M-eigenvalue of a fourth-order partially symmetric tensor. Numerical Linear Algebra with Applications, 16, 589-601. · Zbl 1224.65101
[35] Wang, Y, Caccetta, L and Zhou, G (2015a). Convergence analysis of a block improvement method for polynomial optimization over unit spheres. Numerical Linear Algebra with Applications, 22, 1059-1076. · Zbl 1374.65105
[36] Wang, Y, Liu, W, Caccetta, L and Zhou, G (2015b). Parameter selection for nonnegative \(l_1\) matrix/tensor sparse decomposition. Operations Research Letters, 43, 423-426. · Zbl 1408.15010
[37] Zhang, K and Wang, Y (2016). An H-tensor based iterative scheme for identifying the positive definiteness of multivariate homogeneous forms. Journal of Computational and Applied Mathematics, 305, 1-10. · Zbl 1338.15029
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.