Basis Pursuit Denoise with Nonsmooth Constraints

Abstract

Level-set optimization formulations with data-driven constraints minimize a regularization functional subject to matching observations to a given error level. These formulations are widely used, particularly for matrix completion and sparsity promotion in data interpolation and denoising. The misfit level is typically measured in the l2 norm, or other smooth metrics. In this paper, we present a new flexible algorithmic framework that targets nonsmooth level-set constraints, including L1, Linf, and even L0 norms. These constraints give greater flexibility for modeling deviations in observation and denoising, and have significant impact on the solution. Measuring error in the L1 and L0 norms makes the result more robust to large outliers, while matching many observations exactly. We demonstrate the approach for basis pursuit denoise (BPDN) problems as well as for extensions of BPDN to matrix factorization, with applications to interpolation and denoising of 5D seismic data. The new methods are particularly promising for seismic applications, where the amplitude in the data varies significantly, and measurement noise in low-amplitude regions can wreak havoc for standard Gaussian error models.

11 pages, 10 figures

References in corpus (18)

• Rejoinder to "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Least Angle Regression
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
• Design of Optimal Sparse Feedback Gains via the Alternating Direction Method of Multipliers
• Group-Sparse Signal Denoising: Non-Convex Regularization, Convex Optimization
• Corrupted Sensing: Novel Guarantees for Separating Structured Signals
• Sketchy Decisions: Convex Low-Rank Matrix Optimization with Optimal Storage
• Enhanced Sparsity by Non-Separable Regularization
• A variational approach to stable principal component pursuit
• Beating level-set methods for 3D seismic data interpolation: a primal-dual alternating approach