Sparse approximation using \(\ell_1-\ell_2\) minimization and its application to stochastic collocation. (English) Zbl 1381.94029
Summary: We discuss the properties of sparse approximation using \(\ell_1-\ell_2\) minimization. We present several theoretical estimates regarding its recoverability for both sparse and nonsparse signals. We then apply the method to sparse orthogonal polynomial approximations for stochastic collocation, with a focus on the use of Legendre polynomials. We study the recoverability of both the standard \(\ell_1-\ell_2\) minimization and Chebyshev weighted \(\ell_1-\ell_2\) minimization. It is noted that the Chebyshev weighted version is advantageous only at low dimensions, whereas the standard nonweighted version is preferred in high dimensions. Various numerical examples are presented to verify the theoretical findings.
MSC:
| 94A08 | Image processing (compression, reconstruction, etc.) in information and communication theory |
| 65D05 | Numerical interpolation |
| 65D15 | Algorithms for approximation of functions |
| 42C05 | Orthogonal functions and polynomials, general theory of nontrigonometric harmonic analysis |
| 90C90 | Applications of mathematical programming |
Keywords:
\(\ell_1-\ell_2\) minimization; stochastic collocation; sparse approximation; orthogonal polynomialsReferences:
| [1] | T. T. Cai, L. Wang, and G. Xu, {\it New bounds for restricted isometry constants}, IEEE Trans. Inform. Theory, 56 (2010), pp. 4388-4394. · Zbl 1366.94181 |
| [2] | T. T. Cai, L. Wang, and G. Xu, {\it Shifting inequality and recovery of sparse signals}, IEEE Trans. Signal Process., 58 (2010), pp. 1300-1308. · Zbl 1392.94117 |
| [3] | E. J. Candès, {\it The restricted isometry property and its implications for compressed sensing}, C. R. Math. Acad. Sci. Paris, 346 (2008), pp. 589-592. · Zbl 1153.94002 |
| [4] | E. J. Candès, J. K. 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. Candès and T. Tao, {\it Decoding by linear programming}, IEEE Trans. Inform. Theory, 51 (2005), pp. 4203-4215. · Zbl 1264.94121 |
| [6] | E. J. Candès and T. Tao, {\it Near-optimal signal recovery from random projections: Universal encoding strategies?}, IEEE Trans. Inform. Theory, 52 (2006), pp. 5406-5425. · Zbl 1309.94033 |
| [7] | E. J. Candès, M. B. Wakin, and S. P. Boyd, {\it Enhancing sparsity by reweighted \(ℓ_1\) minimization}, J. Fourier Anal. Appl., 14 (2008), pp. 877-905. · Zbl 1176.94014 |
| [8] | R. Chartrand, {\it Exact reconstruction of sparse signals via nonconvex minimization}, IEEE Signal Proc. Lett., 14 (2007), pp. 707-710, . |
| [9] | R. Chartrand and W. Yin, {\it Iteratively reweighted algorithms for compressive sensing}, in IEEE International Conference on Acoustics, Speech and Signal Processing, Las Vegas, NV, IEEE, 2008, pp. 3869-3872, . |
| [10] | D. L. Donoho, {\it Compressed sensing}, IEEE Trans. Inform. Theory, 52 (2006), pp. 1289-1306. · Zbl 1288.94016 |
| [11] | A. Doostan and H. Owhadi, {\it A non-adapted sparse approximation of PDEs with stochastic inputs}, J. Comput. Phys., 230 (2011), pp. 3015-3034. · Zbl 1218.65008 |
| [12] | R. G. Ghanem and P. Spanos, {\it Stochastic Finite Elements: A Spectral Approach}, Springer-Verlag, New York, 1991. · Zbl 0722.73080 |
| [13] | M.-J. Lai, Y. Xu, and W. Yin, {\it Improved iteratively reweighted least squares for unconstrained smoothed \(ℓ_q\) minimization}, SIAM J. Numer. Anal., 51 (2013), pp. 927-957, . · Zbl 1268.49038 |
| [14] | Y. Lou, P. Yin, Q. He, and J. Xin, {\it Computing sparse representation in a highly coherent dictionary based on difference of \(l_1\) and \(l_2\)}, J. Sci. Comput., 64 (2015), pp. 178-196. · Zbl 1327.65111 |
| [15] | L. Mathelin and K. A. Gallivan, {\it A compressed sensing approach for partial differential equations with random input data}, Commun. Comput. Phys., 12 (2012), pp. 919-954. · Zbl 1388.65018 |
| [16] | B. K. Natarajan, {\it Sparse approximate solutions to linear systems}, SIAM J. Comput., 24 (1995), pp. 227-234, . · Zbl 0827.68054 |
| [17] | H. Rauhut, {\it Compressive sensing and structured random matrices}, in Theoretical Foundations and Numerical Methods for Sparse Recovery, M. Fornasier, ed., Walter De Gruyter, Berlin, 2010, pp. 1-92. · Zbl 1208.15027 |
| [18] | H. Rauhut and R. Ward, {\it Sparse Legendre expansions via \(ℓ_1\)-minimization}, J. Approx. Theory, 164 (2012), pp. 517-533. · Zbl 1239.65018 |
| [19] | P .D. Tao and L. T. H. An, {\it Convex analysis approach to D.C. programming: Theory, algorithms and applications}, Acta Math. Vietnam, 22 (1997), pp. 289-355. · Zbl 0895.90152 |
| [20] | D. Xiu, {\it Numerical Methods for Stochastic Computations}, Princeton Univeristy Press, Princeton, NJ, 2010. · Zbl 1210.65002 |
| [21] | D. Xiu and J. S. Hesthaven, {\it High-order collocation methods for differential equations with random inputs}, SIAM J. Sci. Comput., 27 (2005), pp. 1118-1139, . · Zbl 1091.65006 |
| [22] | D. Xiu and G. E. Karniadakis, {\it The Wiener-Askey polynomial chaos for stochastic differential equations}, SIAM J. Sci. Comput., 24 (2002), pp. 619-644, . · Zbl 1014.65004 |
| [23] | L. Yan, L. Guo, and D. Xiu, {\it Stochastic collocation algorithms using \(ℓ_1\)-minimization}, Int. J. Uncertain. Quantif., 2 (2012), pp. 279-293. · Zbl 1291.65024 |
| [24] | P. Yin, Y. Lou, Q. He, and J. Xin, {\it Minimization of \(ℓ_{1-2}\) for compressed sensing}, SIAM J. Sci. Comput., 37 (2015), pp. A536-A563, . · Zbl 1316.90037 |
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.
