Weak Stability of ℓ₁-Minimization Methods in Sparse Data Reconstruction

References

• Andersson J, Strömberg JO (2014) On the theorem of uniform recovery of structured random matrices. IEEE Trans. Inform. Theory 60(3):1700–1710.Crossref, Google Scholar
• Bruckstein A, Donoho D, Elad M (2009) From sparse solutions of systems of equations to sparse modeling of signals and images. SIAM Rev. 51(1):34–81.Crossref, Google Scholar
• Cahill J, Chen X, Wang R (2016) The gap between the null space property and the restricted isometry property. Linear Algebra Appl. 501(July):363–375.Crossref, Google Scholar
• Cai T, Zhang A (2013) Sharp RIP bound for sparse signal and low-rank matrix recovery. Appl. Comput. Harmonic Anal. 35(1):74–93.Crossref, Google Scholar
• Cai T, Zhang A (2014) Sparse representation of a polytope and recovery of sparse signals and low-rank matrices. IEEE Trans. Inform Theory 60(1):122–132.Crossref, Google Scholar
• Cai T, Wang L, Xu G (2010) New bounds for restricted isometry constants. IEEE Trans. Inform. Theory 56(9):4388–4394.Crossref, Google Scholar
• Candes E, Tao T (2007) The Dantzig selector: Statistical estimation when p is much larger than n. Ann. Statist. 35(6):2313–2351.Crossref, Google Scholar
• Candès E (2008) The restricted isometry property and its implications for compressed sensing. C. R. Math. Acad. Sci. Paris 346(9–10):589–592.Crossref, Google Scholar
• Candès E, Tao T (2005) Decoding by linear programming. IEEE Trans. Inform. Theory 51(12):4203–4215.Crossref, Google Scholar
• Candès E, Tao T (2006) Near optimal signal recovery from random projections: Universal encoding strategies? IEEE Trans. Inform. Theory 52(12):5406–5425.Crossref, Google Scholar
• Candès E, Romberg J, Tao T (2006) Stable signal recovery from incomplete and inacurate measurements. Comm. Pure Appl. Math. 59(8):1207–1223.Crossref, Google Scholar
• Candès E, Wakin M, Boyd S (2008) Enhancing sparsity by reweighted ℓ1 minimization. J. Fourier Anal. Appl. 14(5–6):877–905.Crossref, Google Scholar
• Cheang G, Barron AR (2000) A better approximation for balls. J. Approx. Theory. 104(2):183–203.Crossref, Google Scholar
• Chen S, Donoho D, Saunders M (1998) Atomic decomposition by ℓ1-minimization. SIAM J. Sci. Comput. 20(1):33–61.Crossref, Google Scholar
• Cohen A, Dahmen W, Devore R (2009) Compressed sensing and best k-term aproximation. J. Amer. Math. Soc. 22(1):211–231.Crossref, Google Scholar
• Donoho D, Elad M (2003) Optimally sparse representation in general (nonorthogonal) dictionaries via ℓ1 minimization. Proc. Natl. Acad. Sci. USA 100(5):2197–2202.Crossref, Google Scholar
• Donoho D, Huo X (2001) Uncertainty principles and ideal atomic decomposition. IEEE Trans. Inform. Theory 47(7):2845–2862.Crossref, Google Scholar
• Donoho D, Logan B (1992) Signal recovery and the large sieve. SIAM J. Appl. Math. 52(2):577–591.Crossref, Google Scholar
• Donoho D, Elad M, Temlyahov V (2006) Stable recovery of sparse overcomplete representations in the presence of noise. IEEE Trans. Inform. Theory 52(1):6–18.Crossref, Google Scholar
• Dudley R (1974) Matric entropy of some classes of sets with differentiable bounaries. J. Approx. Theory 10(3):227–236.Crossref, Google Scholar
• Elad M (2010) Sparse and Redundant Representations: From Theory to Applications in Signal and Image Processing (Springer, New York).Crossref, Google Scholar
• Eldar Y, Kutyniok G (2012) Compressed Sensing: Theory and Applications (Cambridge University Press, New York).Crossref, Google Scholar
• Foucart S (2014) Stability and robustness of ℓ1-minimization with Weibull matrices and redundant dictionaries. Linear Algebra Appl. 441(January):4–21.Crossref, Google Scholar
• Foucart S, Lai M (2009) Sparsest solutions of undetermined linear systems via ℓp-minimization for 0 < q ≤ 1. Appl. Comput. Harmonic Anal. 26(3):395–407.Crossref, Google Scholar
• Foucart S, Rauhut H (2013) A Mathematical Introduction to Compressive Sensing (Springer, New York).Crossref, Google Scholar
• Fuchs J (2004) On sparse representations in arbitrary redundant bases. IEEE Trans. Inform. Theory 50(6):1341–1344.Crossref, Google Scholar
• Grasmair M, Sherzer O, Haltmeier M (2011) Necessary and sufficient conditions for linear convergence of ℓ1-regularization. Comm. Pure Appl. Math. 64(2):161–182.Crossref, Google Scholar
• Gribonval R, Nielsen M (2003) Sparse representation in unions of basis. IEEE Trans. Inform. Theory 49(12):3320–3325.Crossref, Google Scholar
• Hastie T, Tibshirani R, Wainwright M (2015) Statistical Learning with Sparsity: The Lasso and Generalizations (Chapman & Hall/CRC, New York).Crossref, Google Scholar
• Hoffman AJ (1952) On the approximation solution of systems of linear inequalities. J. Res. Natl. Bureau Standards 49(4):263–265.Crossref, Google Scholar
• Levy S, Fullagar P (1981) Reconstruction of a sparse spike train from a portion of its spectrum and application to high-resolution deconvolution. Geophysics 46(9):1235–1243.Crossref, Google Scholar
• Logan B (1965) Properties of high-pass signals. Unpublished Ph.D. thesis, Columbia University, New York.Google Scholar
• Mangasarian OL (1996) Machine learning via polydedral concave minimization. Fischer H, Riedmueller B, Schaeffler S, eds. Applied Mathematics and Parallel Computing-Festschrift for Klaus Ritter (Springer, Heidelberg, Germany), 175–188.Crossref, Google Scholar
• Mangasarian OL (1999) Minimum-support solutions of polyhedral concave programs. Optimization 45(1–4):149–162.Crossref, Google Scholar
• Mo Q, Li S (2011) New bounds on the restricted isometry constant δ2k. Appl. Comput. Harmonic Anal. 31(3):460–468.Crossref, Google Scholar
• Plumbley M (2007) On polar polytopes and the recovery of sparse representations. IEEE Trans. Inform. Theory 53(9):3188–3195.Crossref, Google Scholar
• Robinson SM (1973) Bounds for error in the solution set of a perturbed linear program. Linear Algebra Appl. 6:69–81.Crossref, Google Scholar
• Sun Q (2012) Recovery of sparsest signals via ℓq-minimization. Appl. Comput. Harmonic Anal. 32(3):329–341.Crossref, Google Scholar
• Taylor H, Banks S, McCoy J (1979) Deconvolution with the ℓ1 norm. Geophysics 44(1):39–52.Crossref, Google Scholar
• Tibshirani T (1996) Regression shrinkage and selection via the Lasso. J. Roy. Statist. Soc. Ser. B 58(1):267–288.Crossref, Google Scholar
• Tropp JA (2004) Greed is good: Algorithmic results for sparse approximation. IEEE Trans. Inform. Theory 50(10):2231–2242.Crossref, Google Scholar
• Zhang H, Yan M, Yin W (2016) One condition for solution uniqueness and robustness of both l1-synthesis and l1-analysis minimization. Adv. Comput. Math 42(6):1381–1399.Crossref, Google Scholar
• Zhang H, Yin W, Cheng L (2015) Necessary and sufficient conditions of solution uniqueness in 1-norm minimization. J. Optim. Theory Appl. 164(1):109–122.Crossref, Google Scholar
• Zhang Y (2013) Theory of compressive sensing via ℓ1-mimimization: A non-RIP analysis and extensions. J. Oper. Res. Soc. China 1(1):79–105.Crossref, Google Scholar
• Zhao Y-B (2013) RSP-based analysis for sparsest and least ℓ1-norm solutions to underdetermined linear systems. IEEE Trans. Signal Process. 61((22):5777–5788.Crossref, Google Scholar
• Zhao Y-B (2014) Equivalence and strong equivalence between sparsest and least ℓ1-norm nonnegative solutions of linear systems and their applications. J. Oper. Res. Soc. China 2(2):171–193.Crossref, Google Scholar
• Zhao Y-B, Kocvara M (2015) A new computational method for the sparsest solutions to systems of linear equations. SIAM J. Optim. 25(2):1110–1134.Crossref, Google Scholar
• Zhao Y-B, Li D (2012) Reweighted ℓ1-minimization for sparse solutions to underdetermined linear systems. SIAM J. Optim. 22(3):1065–1088.Crossref, Google Scholar
• Zhao Y-B, Xu C (2016) 1-Bit compressive sensing: Reformulation and RRSP-based sign recovery theory. Sci. China Math. 59(10):2049–2074.Crossref, Google Scholar