Abstract
In this paper, we consider the zero-norm minimization problem with linear equation and nonnegativity constraints. By introducing the concept of generalized Z-matrix for a rectangular matrix, we show that this zero-norm minimization with such a kind of measurement matrices and nonnegative observations can be exactly solved via the corresponding p-norm minimization with p in the open interval from zero to one. Moreover, the lower bound of sample number for exact recovery is allowed to be the same as the sparsity of the original image or signal by the underlying zero-norm minimization. A practical application in communications is presented, which satisfies the generalized Z-matrix recovery condition.
This is a preview of subscription content, log in via an institution to check access.
References
Donoho, D.L.: Compressed sensing. IEEE Trans. Inf. Theory 52(4), 1289–1306 (2006)
Candés, E., Romberg, J., Tao, T.: Stable signal recovery from incomplete and inaccurate measurements. Commun. Pure Appl. Math. 59(8), 1207–1223 (2006)
Candés, E., Tao, T.: Decoding by linear programming. IEEE Trans. Inf. Theory 51, 4203–4215 (2005)
Bruckstein, A.M., Donoho, D.L., Elad, M.: From sparse solutions of systems of equations to sparse modeling of signals and images. SIAM Rev. 51, 34–81 (2009)
Davenport, M., Duarte, M., Eldar, Y., Kutyniok, G.: Introduction to compressed sensing. In: Compressed Sensing: Theory and Applications. Cambridge University Press, Cambridge (2012)
Donoho, D.L., Tanner, J.: Precise undersampling theorems. Proc. IEEE 98, 913–924 (2010)
Harmany, Z.T., Marcia, R.F., Willett, R.M.: Spiral out of convexity: Sparsity-regularized algorithms for photon-limited imaging. In: Bouman, C.A., et al. (eds.) Computational Imaging VIII, San Jose, CA, January 2010. Proc. SPIE-IS&T Electron. Imaging, vol. 7533 (2010)
Khajehnejad, M.A., Dimakis, A.G., Xu, W., Hassibi, B.: Sparse recovery of nonnegative signals with minimal expansion. IEEE Trans. Signal Process. 59(1), 196–208 (2011)
Liu, Y., Dai, Y., Luo, Z.: Joint power and admission control via linear programming deflation. accepted for publication in ICASSP 2012. http://www.icassp2012.org/Papers/ViewPapers.asp?PaperNum=2411
Sheikh, M.A., Sarvotham, S., Milenkovic, O., Baraniuk, R.G.: DNA array decoding from nonlinear measurements by belief propagation. In: IEEE Proceedings of the 14th Workshop on Statistical Signal Processing, Washington, DC, USA, pp. 215–219 (2007)
Ge, D., Jiang, X., Ye, Y.: A note on complexity of l p minimization. Math. Program. 129, 285–299 (2011)
Natarajan, B.K.: Sparse approximate solutions to linear systems. SIAM J. Comput. 24, 227–234 (1995)
Bruckstein, A.M., Elad, M., Zibulevsky, M.: On the uniqueness of nonnegative sparse solutions to underdetermined systems of equations. IEEE Trans. Inf. Theory 54, 4813–4820 (2008)
Donoho, D.L., Tanner, J.: Sparse nonnegative solutions of underdetermined linear equations by linear programming. Proc. Natl. Acad. Sci. USA 102, 9446–9451 (2005)
Donoho, D.L., Tanner, J.: Counting the faces of randomly-projected hypercubes and orthants with applications. Discrete Comput. Geom. 43, 522–541 (2008)
Juditsky, A., Karzan, F.K., Nemirovski, A.: Verifiable conditions of l 1 recovery for sparse signals with sign restrictions. Math. Program., Ser. B 127, 89–122 (2011)
Qin, L.X., Xiu, N.H., Kong, L.C., Li, Y.: Linear Program Relaxation of Sparse Nonnegative Recovery in Compressive Sensing Microarrays. Preprint, Department of Mathematics, Beijing Jiaotong University (2012)
Wang, M., Xu, W., Tang, A.: A unique “nonnegative” solution to an underdetermined systems: from vector to matrices. IEEE Trans. Signal Process. 59(3), 1007–1016 (2011)
Zhang, Y.: A simple proof for the recoverability of l 1-minimization (II): The nonnegative case. Technical report TR05-10, Department of Computational and Applied Mathematical, Rice University, Houston, TX (2005)
Berman, A., Plemmons, R.J. (eds.): Nonnegative Matrices in the Mathematical Sciences. SIAM, Philadelphia (1994)
Cottle, R.W., Pang, J.S., Stone, R.E. (eds.): The Linear Complementarity Problem. Academic Press, Boston (1992)
Chen, X.J., Xiang, S.H.: Implicit solution function of P 0 and Z matrix linear complementarity constraints. Math. Program., Ser. A 128, 1–18 (2011)
Chen, X.J., Xiang, S.H.: Newton iterations in implicit time-stepping scheme for differential linear complementarity systems. Math. Program., Ser. A (2012). doi:10.1007/s10107-012-0527-x
Candés, E., Romberg, J.: Sparsity and incoherence in compressive sampling. Inverse Probl. 23(3), 969–985 (2007)
Do Ba, K., Indyk, P., Price, E., Woodruff, D.: Lower bounds for sparse recovery. In: Proc. 19th Annu. ACM–SIAM Symp. Discrete Algorithms (2010)
Fiedler, M., Ptàk, V.: On matrices with non-positive off-diagonal elements and positive principle minors. Czechoslov. Math. J. 12, 382–400 (1962)
Song, D.C., Feng, Z.X.: Properties of generalized Z-matrices and M-matrices. J. Fushun Petroleum Inst. 23(4), 78–80 (2003)
Fung, G., Mangasarian, O.: Equivalence of minimal l 0- and l p -norm solutions of linear equalities, inequalities and linear programs for sufficiently small p. J. Optim. Theory Appl. 151(1), 1–10 (2011)
Acknowledgements
This research was supported by the National Basic Research Program of China (2010CB732501), the National Natural Science Foundation of China (11101248), and the State Key Laboratory of Rail Traffic Control and Safety (Contract No. RCS2012ZQ001), Beijing Jiaotong University.
Author information
Authors and Affiliations
Corresponding author
Additional information
Communicated by Vaithilingam Jeyakumar.
Rights and permissions
About this article
Cite this article
Luo, Z., Qin, L., Kong, L. et al. The Nonnegative Zero-Norm Minimization Under Generalized Z-Matrix Measurement. J Optim Theory Appl 160, 854–864 (2014). https://doi.org/10.1007/s10957-013-0325-5
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10957-013-0325-5