Compressed sensing with sparse corruptions: Fault-tolerant sparse collocation approximations

Abstract

The recovery of approximately sparse or compressible coefficients in a Polynomial Chaos Expansion is a common goal in modern parametric uncertainty quantification (UQ). However, relatively little effort in UQ has been directed toward theoretical and computational strategies for addressing the sparse corruptions problem, where a small number of measurements are highly corrupted. Such a situation has become pertinent today since modern computational frameworks are sufficiently complex with many interdependent components that may introduce hardware and software failures, some of which can be difficult to detect and result in a highly polluted simulation result. In this paper we present a novel compressive sampling-based theoretical analysis for a regularized ${\ell }^1$ minimization algorithm that aims to recover sparse expansion coefficients in the presence of measurement corruptions. Our recovery results are uniform, and prescribe algorithmic regularization parameters in terms of a user-defined a priori estimate on the ratio of measurements that are believed to be corrupted. We also propose an iteratively reweighted optimization algorithm that automatically refines the value of the regularization parameter, and empirically produces superior results. Our numerical results test our framework on several medium-to-high dimensional examples of solutions to parameterized differential equations, and demonstrate the effectiveness of our approach.

27 pages, 7 figures

References in corpus (8)

• Compressive Sampling of Polynomial Chaos Expansions: Convergence Analysis and Sampling Strategies
• Polynomial approximation via compressed sensing of high-dimensional functions on lower sets
• Compressed Sensing and Parallel Acquisition
• On asymptotic structure in compressed sensing
• A generalized sampling and preconditioning scheme for sparse approximation of polynomial chaos expansions
• Compressed sensing with local structure: uniform recovery guarantees for the sparsity in levels class
• Data recovery from corrupted observations via l1 minimization
• Compressed sensing with corrupted Fourier measurements

Cited by in corpus (10)

• The benefits of acting locally: Reconstruction algorithms for sparse in levels signals with stable and robust recovery guarantees
• Uniform Recovery Bounds for Structured Random Matrices in Corrupted Compressed Sensing
• Compressed sensing with local structure: uniform recovery guarantees for the sparsity in levels class
• Correcting for unknown errors in sparse high-dimensional function approximation
• Outlier-robust estimation of a sparse linear model using ${\ell }_1$-penalized Huber's $M$-estimator
• The greedy side of the LASSO: New algorithms for weighted sparse recovery via loss function-based orthogonal matching pursuit
• Recovery guarantees for polynomial approximation from dependent data with outliers
• Outlier-robust sparse/low-rank least-squares regression and robust matrix completion
• Noise-robust multi-fidelity surrogate modelling for parametric partial differential equations
• Iterative and greedy algorithms for the sparsity in levels model in compressed sensing