Optimal injectivity conditions for bilinear inverse problems with applications to identifiability of deconvolution problems. (English) Zbl 1365.15021
Summary: We study identifiability for bilinear inverse problems under sparsity and subspace constraints. We show that, up to a global scaling ambiguity, almost all such maps are injective on the set of pairs of sparse vectors if the number of measurements \(m\) exceeds \(2(s_1+s_2)-2\), where \(s_1\) and \(s_2\) denote the sparsity of the two input vectors, and injective on the set of pairs of vectors lying in known subspaces of dimensions \(n_1\) and \(n_2\) if \(m\geq 2(n_1+n_2)-4\). We also prove that both these bounds are tight in the sense that one cannot have injectivity for a smaller number of measurements. Our proof technique draws from algebraic geometry. As an application we derive optimal identifiability conditions for the deconvolution problem, thus improving on recent work of Y. Li, K. Lee, and Y. Bresler [“Identifiability and stability in blind deconvolution under minimal assumptions”, Preprint, arXiv:1507.01308].
MSC:
| 15A29 | Inverse problems in linear algebra |
| 15A63 | Quadratic and bilinear forms, inner products |
| 51N35 | Questions of classical algebraic geometry |
| 14N05 | Projective techniques in algebraic geometry |
| 94A08 | Image processing (compression, reconstruction, etc.) in information and communication theory |
Software:
PhaseLiftReferences:
| [1] | A. Ahmed, B. Recht, and J. Romberg, {\it Blind deconvolution using convex programming}, IEEE Trans. Inform. Theory, 60 (2014), pp. 1711-1732. · Zbl 1360.94057 |
| [2] | R. Balan, P. Casazza, and D. Edidin, {\it On signal reconstruction without phase.}, Appl. Comput. Harmon. Anal., 20 (2006), pp. 345-356. · Zbl 1090.94006 |
| [3] | A. S. Bandeira, Y. Chen, and D. G. Mixon, {\it Phase retrieval from power spectra of masked signals}, Inform. Inference, 3 (2014), pp. 83-102. · Zbl 1308.94031 |
| [4] | E. Candès, J. Romberg, and T. Tao, {\it Stable signal recovery from incomplete and inaccurate measurements}, Comm. Pure Appl. Math., 59 (2006), pp. 1207-1223. · Zbl 1098.94009 |
| [5] | E. J. Candes, X. Li, and M. Soltanolkotabi, {\it Phase retrieval from coded diffraction patterns}, Appl. Comput. Harmon. Anal., 39 (2015), pp. 277-299. · Zbl 1329.78056 |
| [6] | E. J. Candès and B. Recht, {\it Exact matrix completion via convex optimization}, Found. Comput. Math., 9 (2009), pp. 717-772. · Zbl 1219.90124 |
| [7] | E. J. Candès, T. Strohmer, and V. Voroninski, {\it PhaseLift: Exact and stable signal recovery from magnitude measurements via convex programming}, Comm. Pure Appl. Math., 66 (2013), pp. 1241-1274. · Zbl 1335.94013 |
| [8] | V. Chandrasekaran, B. Recht, P. Parrilo, and A. S. Willsky, {\it The convex geometry of linear inverse problems}, Found. Comput. Math., 12 (2012), pp. 805-849. · Zbl 1280.52008 |
| [9] | S. Choudhary and U. Mitra, {\it Identifiability Scaling Laws in Bilinear Inverse Problems}, preprint, , 2014. |
| [10] | S. Choudhary and U. Mitra, {\it Sparse blind deconvolution: What cannot be done}, in Proceedings of the IEEE International Symposium on Information Theory (ISIT), IEEE, Washington, DC, 2014, pp. 3002-3006. |
| [11] | A. Conca, D. Edidin, M. Hering, and C. Vinzant, {\it An algebraic characterization of injectivity in phase retrieval}, Appl. Comput. Harmon. Anal., 38 (2015), pp. 346-356. · Zbl 1354.42003 |
| [12] | D. Donoho, {\it Compressed sensing}, IEEE Trans. Inform. Theory, 52 (2006), pp. 1289-1306. · Zbl 1288.94016 |
| [13] | D. L. Donoho and M. Elad, {\it Optimally sparse representation in general (non-orthogonal) dictionaries via \(ℓ^1\) minimization}, Proc. Natl. Acad. Sci. USA, 100 (2003), pp. 2197-2202. · Zbl 1064.94011 |
| [14] | Y. C. Eldar and S. Mendelson, {\it Phase retrieval: Stability and recovery guarantees}, Appl. Comput. Harmon. Anal., 36 (2014), pp. 473-494. · Zbl 06298184 |
| [15] | Y. C. Eldar, D. Needell, and Y. Plan, {\it Uniqueness conditions for low-rank matrix recovery}, Appl. Comput. Harmon. Anal., 33 (2012), pp. 309-314. · Zbl 1247.65056 |
| [16] | S. Foucart and H. Rauhut, {\it A Mathematical Introduction to Compressive Sensing}, Appl. Numer. Harmon. Anal., Birkhäuser/Springer, New York, 2013. · Zbl 1315.94002 |
| [17] | D. Gross, F. Krahmer, and R. Küng, {\it Improved recovery guarantees for phase retrieval from coded diffraction patterns}, Appl. Comput. Harmon. Anal., 42 (2017), pp. 37-64. · Zbl 1393.94250 |
| [18] | J. Harris, {\it Algebraic Geometry: A First Course}, Grad. Texts in Math. 133, Springer, New York, 2013. |
| [19] | R. Hartshorne, {\it Algebraic Geometry}, Grad. Texts in Math. 52, Springer, New York, 1977. · Zbl 0367.14001 |
| [20] | M. Kech and M. M. Wolf, {\it Quantum Tomography of Semi-Algebraic Sets with Constrained Measurements}, preprint, , 2015. · Zbl 1386.94010 |
| [21] | F. Krahmer, Y. Lin, B. McAdoo, K. Ott, J. Wang, D. Widemann, and B. Wohlberg, {\it Blind image deconvolution: Motion blur estimation}, IMA Preprint Ser., 21 (2006), pp. 33-35. |
| [22] | F. Krahmer, S. Mendelson, and H. Rauhut, {\it Suprema of chaos processes and the restricted isometry property}, Comm. Pure Appl. Math., 67 (2014), pp. 1877-1904. · Zbl 1310.94024 |
| [23] | F. Krahmer and H. Rauhut, {\it Structured random measurements in signal processing}, GAMM-Mitt., 37 (2014), pp. 217-238. · Zbl 1308.94033 |
| [24] | K. Lee, Y. Wu, and Y. Bresler, {\it Near Optimal Compressed Sensing of Sparse Low-Rank Matrices via Sparse Power Factorization}, preprint, , 2013. · Zbl 1390.94261 |
| [25] | Y. Li, K. Lee, and Y. Bresler, {\it Identifiability and Stability in Blind Deconvolution under Minimal Assumptions}, preprint, , 2015. · Zbl 1370.94582 |
| [26] | Y. Li, K. Lee, and Y. Bresler, {\it A Unified Framework for Identifiability Analysis in Bilinear Inverse Problems with Applications to Subspace and Sparsity Models}, preprint, , 2015. |
| [27] | Y. Li, K. Lee, and Y. Bresler, {\it Identifiability in blind deconvolution with subspace or sparsity constraints}, IEEE Trans. Inform. Theory, 62 (2016), pp. 4266-4275. · Zbl 1359.94124 |
| [28] | S. Ling and T. Strohmer, {\it Blind Deconvolution Meets Blind Demixing: Algorithms and Performance Bounds}, preprint, , 2015. · Zbl 1370.94583 |
| [29] | S. Ling and T. Strohmer, {\it Self-calibration and biconvex compressive sensing}, Inverse Problems, 31 (2015), 115002. · Zbl 1327.93183 |
| [30] | H. Liu, G. Xu, L. Tong, and T. Kailath, {\it Recent developments in blind channel equalization: From cyclostationarity to subspaces}, Signal Process., 50 (1996), pp. 83-99. · Zbl 0866.94006 |
| [31] | M. Lustig, D. Donoho, and J. Pauly, {\it Sparse MRI: The application of compressed sensing for rapid MRI imaging}, Magnetic Resonance in Medicine, 58 (2007), pp. 1182-1195. |
| [32] | R. F. Marcia and R. M. Willett, {\it Compressive coded aperture superresolution image reconstruction}, in Proceedings of the IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), IEEE, Washington, DC, 2008, pp. 833-836. |
| [33] | V. D. Milman and G. Schechtman, {\it Asymptotic Theory of Finite-Dimensional Normed Spaces: Isoperimetric Inequalities in Riemannian Manifolds}, Lecture Notes in Math. 1200, Springer, Berlin, 1986. · Zbl 0606.46013 |
| [34] | D. Mumford, {\it The Red Book of Varieties and Schemes: Includes the Michigan Lectures (1974) on Curves and Their Jacobians}, 2nd ed., Lecture Notes in Math. 1358, Springer, Berlin, 1999. · Zbl 0945.14001 |
| [35] | E. Riegler, D. Stotz, and H. Bölcskei, {\it Information-theoretic limits of matrix completion}, in Proceedings of the IEEE International Symposium on Information Theory (ISIT), IEEE, Washington, DC, 2015, pp. 1836-1840. |
| [36] | M. Rudelson and R. Vershynin, {\it On sparse reconstruction from Fourier and Gaussian measurements}, Comm. Pure Appl. Math., 61 (2008), pp. 1025-1045. · Zbl 1149.94010 |
| [37] | C. Vinzant, {\it A small frame and a certificate of its injectivity}, in Proceedings of the International Conference on Sampling Theory and Applications (SampTA), American University, Washington, DC, 2015, pp. 197-200. |
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.
