×

Spark-level sparsity and the \(\ell_1\) tail minimization. (English) Zbl 1397.94018

Summary: Solving compressed sensing problems relies on the properties of sparse signals. It is commonly assumed that the sparsity \(s\) needs to be less than one half of the spark of the sensing matrix \(A\), and then the unique sparsest solution exists, and is recoverable by \(\ell_1\)-minimization or related procedures. We discover, however, a measure theoretical uniqueness exists for nearly spark-level sparsity from compressed measurements \(A x = b\). Specifically, suppose \(A\) is of full spark with \(m\) rows, and suppose \(\frac{m}{2} < s < m\). Then the solution to \(A x = b\) is unique for \(x\) with \(\| x \|_0 \leq s\) up to a set of measure 0 in every \(s\)-sparse plane. This phenomenon is observed and confirmed by an \(\ell_1\)-tail minimization procedure, which recovers sparse signals uniquely with \(s > \frac{m}{2}\) in thousands and thousands of random tests. We further show instead that the mere \(\ell_1\)-minimization would actually fail if \(s > \frac{m}{2}\) even from the same measure theoretical point of view.

MSC:

94A12 Signal theory (characterization, reconstruction, filtering, etc.)
65K10 Numerical optimization and variational techniques

Software:

CoSaMP; PDCO
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Alexeev, B.; Cahill, J.; Mixon, D., Full spark frames, J. Fourier Anal. Appl., 18, 1167-1194 (2012) · Zbl 1257.42040
[2] Blumensath, T.; Davies, M. E., Iterative thresholding for sparse approximations, J. Fourier Anal. Appl., 14, 5-6, 629-654 (2008) · Zbl 1175.94060
[3] Candè, E. J.; Wakin, M. B., An introduction to compressive sampling, IEEE Signal Process. Mag., 25, 2, 21-30 (2008)
[4] Candes, E. J.; Eldar, Y. C.; Needell, D.; Randall, P., Compressed sensing with coherent and redundant dictionaries, Appl. Comput. Harmon. Anal., 31, 1, 59-73 (2011) · Zbl 1215.94026
[5] Candès, E. J.; Romberg, J.; Tao, T., Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information, IEEE Trans. Inform. Theory, 52, 2, 489-509 (2006) · Zbl 1231.94017
[6] Candes, E. J.; Tao, T., Near-optimal signal recovery from random projections: universal encoding strategies?, IEEE Trans. Inform. Theory, 52, 12, 5406-5425 (2006) · Zbl 1309.94033
[7] Chen, S. S.; Donoho, D. L.; Saunders, M. A., Atomic decomposition by basis pursuit, SIAM Rev., 43, 1, 129-159 (2001) · Zbl 0979.94010
[8] Chen, X.; Wang, H.; Wang, R., A null space analysis of the \(\ell_1\)-synthesis method in dictionary-based compressed sensing, Appl. Comput. Harmon. Anal., 37, 3, 492-515 (2014) · Zbl 1311.94017
[9] Christensen, O., An Introduction to Frames and Riesz Bases (2013), Springer Science & Business Media
[10] Dai, W.; Milenkovic, O., Subspace pursuit for compressive sensing signal reconstruction, IEEE Trans. Inform. Theory, 55, 5, 2230-2249 (2009) · Zbl 1367.94082
[11] Donoho, D. L., High-dimensional centrally symmetric polytopes with neighborliness proportional to dimension, Discrete Comput. Geom., 35, 4, 617-652 (2006) · Zbl 1095.52500
[12] Donoho, D. L.; Elad, M., Optimally sparse representation in general (nonorthogonal) dictionaries via \(\ell_1\) minimization, Proc. Natl. Acad. Sci., 100, 5, 2197-2202 (2003) · Zbl 1064.94011
[13] Donoho, D. L.; Tsaig, Y.; Drori, I.; Starck, J.-L., Sparse solution of underdetermined systems of linear equations by stagewise orthogonal matching pursuit, IEEE Trans. Inform. Theory, 58, 2, 1094-1121 (2012) · Zbl 1365.94069
[14] Elad, M.; Milanfar, P.; Rubinstein, R., Analysis versus synthesis in signal priors, Inverse Probl., 23, 3, 947 (2007) · Zbl 1138.93055
[15] Ender, J. H., On compressive sensing applied to radar, Signal Process., 90, 5, 1402-1414 (2010) · Zbl 1194.94084
[16] Fannjiang, A. C.; Strohmer, T.; Yan, P., Compressed remote sensing of sparse objects, SIAM J. Imaging Sci., 3, 3, 595-618 (2010) · Zbl 1201.45017
[17] Foucart, S.; Rauhut, H., A mathematical introduction to compressive sensing, (Applied and Numerical Harmonic Analysis (2013), Birkhäuser Boston Inc.: Birkhäuser Boston Inc. Boston, MA) · Zbl 1315.94002
[18] Ge, D.; Jiang, X.; Ye, Y., A note on the complexity of l p minimization, Math. Program., 129, 2, 285-299 (2011) · Zbl 1226.90076
[19] Kim, S.-J.; Koh, K.; Lustig, M.; Boyd, S.; Gorinevsky, D., An interior-point method for large-scale l 1-regularized least squares, IEEE J. Sel. Top. Signal Process., 1, 4, 606-617 (2007)
[20] Liu, Y.; Mi, T.; Li, S., Compressed sensing with general frames via optimal-dual-based-analysis, IEEE Trans. Inform. Theory, 58, 7, 4201-4214 (2012) · Zbl 1365.94181
[21] Lustig, M.; Donoho, D.; Pauly, J. M., Sparse MRI: the application of compressed sensing for rapid MR imaging, Magn. Reson. Med., 58, 6, 1182-1195 (2007)
[22] Needell, D.; Tropp, J. A., Cosamp: iterative signal recovery from incomplete and inaccurate samples, Appl. Comput. Harmon. Anal., 26, 3, 301-321 (2009) · Zbl 1163.94003
[23] Rauhut, H., Random sampling of sparse trigonometric polynomials, Appl. Comput. Harmon. Anal., 22, 1, 16-42 (2007) · Zbl 1123.94004
[24] Rauhut, H., Stability results for random sampling of sparse trigonometric polynomials, IEEE Trans. Inform. Theory, 54, 12, 5661-5670 (2008) · Zbl 1247.94010
[25] Rauhut, H., Compressive sensing and structured random matrices, (Theoretical Foundations and Numerical Methods for Sparse Recovery, vol. 9 (2010)), 1-92 · Zbl 1208.15027
[26] Rauhut, H.; Schnass, K.; Vandergheynst, P., Compressed sensing and redundant dictionaries, IEEE Trans. Inform. Theory, 54, 5, 2210-2219 (2008) · Zbl 1332.94022
[27] Rudelson, M.; Vershynin, R., On sparse reconstruction from Fourier and Gaussian measurements, Comm. Pure Appl. Math., 61, 8, 1025-1045 (2008) · Zbl 1149.94010
[28] Wang, Y.; Yin, W., Sparse signal reconstruction via iterative support detection, SIAM J. Imaging Sci., 3, 3, 462-491 (2010) · Zbl 1206.68340
[29] Zeng, C.; Zhu, S.; Li, S.; Liao, Q.; Wang, L., Sparse frame DOA estimations via a rank-one correlation model for low SNR and limited snapshots, Appl. Comput. Harmon. Anal. (2016) · Zbl 1360.94104
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.