arrow
Volume 10, Issue 4
Sparse Recovery via ℓ$_q$-Minimization for Polynomial Chaos Expansions

Ling Guo, Yongle Liu & Liang Yan

Numer. Math. Theor. Meth. Appl., 10 (2017), pp. 775-797.

Published online: 2017-11

Export citation
  • Abstract

In this paper we consider the algorithm for recovering sparse orthogonal polynomials using stochastic collocation via ℓq minimization. The main results include: 1) By using the norm inequality between ℓq and ℓ2 and the square root lifting inequality, we present several theoretical estimates regarding the recoverability for both sparse and non-sparse signals via ℓq minimization; 2) We then combine this method with the stochastic collocation to identify the coefficients of sparse orthogonal polynomial expansions, stemming from the field of uncertainty quantification. We obtain recoverability results for both sparse polynomial functions and general non-sparse functions. We also present various numerical experiments to show the performance of the ℓq algorithm. We first present some benchmark tests to demonstrate the ability of ℓq minimization to recover exactly sparse signals, and then consider three classical analytical functions to show the advantage of this method over the standard ℓ1 and reweighted ℓ1 minimization. All the numerical results indicate that the ℓq method performs better than standard ℓ1 and reweighted ℓ1 minimization.

  • AMS Subject Headings

65D05, 42C05, 41A10

  • Copyright

COPYRIGHT: © Global Science Press

  • Email address
  • BibTex
  • RIS
  • TXT
@Article{NMTMA-10-775, author = {}, title = {Sparse Recovery via ℓ$_q$-Minimization for Polynomial Chaos Expansions}, journal = {Numerical Mathematics: Theory, Methods and Applications}, year = {2017}, volume = {10}, number = {4}, pages = {775--797}, abstract = {

In this paper we consider the algorithm for recovering sparse orthogonal polynomials using stochastic collocation via ℓq minimization. The main results include: 1) By using the norm inequality between ℓq and ℓ2 and the square root lifting inequality, we present several theoretical estimates regarding the recoverability for both sparse and non-sparse signals via ℓq minimization; 2) We then combine this method with the stochastic collocation to identify the coefficients of sparse orthogonal polynomial expansions, stemming from the field of uncertainty quantification. We obtain recoverability results for both sparse polynomial functions and general non-sparse functions. We also present various numerical experiments to show the performance of the ℓq algorithm. We first present some benchmark tests to demonstrate the ability of ℓq minimization to recover exactly sparse signals, and then consider three classical analytical functions to show the advantage of this method over the standard ℓ1 and reweighted ℓ1 minimization. All the numerical results indicate that the ℓq method performs better than standard ℓ1 and reweighted ℓ1 minimization.

}, issn = {2079-7338}, doi = {https://doi.org/10.4208/nmtma.2017.0001}, url = {http://global-sci.org/intro/article_detail/nmtma/10456.html} }
TY - JOUR T1 - Sparse Recovery via ℓ$_q$-Minimization for Polynomial Chaos Expansions JO - Numerical Mathematics: Theory, Methods and Applications VL - 4 SP - 775 EP - 797 PY - 2017 DA - 2017/11 SN - 10 DO - http://doi.org/10.4208/nmtma.2017.0001 UR - https://global-sci.org/intro/article_detail/nmtma/10456.html KW - Uncertainty quantification, stochastic collocation, ℓ$_q$-minimization, polynomial chaos expansions. AB -

In this paper we consider the algorithm for recovering sparse orthogonal polynomials using stochastic collocation via ℓq minimization. The main results include: 1) By using the norm inequality between ℓq and ℓ2 and the square root lifting inequality, we present several theoretical estimates regarding the recoverability for both sparse and non-sparse signals via ℓq minimization; 2) We then combine this method with the stochastic collocation to identify the coefficients of sparse orthogonal polynomial expansions, stemming from the field of uncertainty quantification. We obtain recoverability results for both sparse polynomial functions and general non-sparse functions. We also present various numerical experiments to show the performance of the ℓq algorithm. We first present some benchmark tests to demonstrate the ability of ℓq minimization to recover exactly sparse signals, and then consider three classical analytical functions to show the advantage of this method over the standard ℓ1 and reweighted ℓ1 minimization. All the numerical results indicate that the ℓq method performs better than standard ℓ1 and reweighted ℓ1 minimization.

Ling Guo, Yongle Liu & Liang Yan. (2019). Sparse Recovery via ℓ$_q$-Minimization for Polynomial Chaos Expansions. Numerical Mathematics: Theory, Methods and Applications. 10 (4). 775-797. doi:10.4208/nmtma.2017.0001
Copy to clipboard
The citation has been copied to your clipboard