Sparse History Matching: Nonlinear-Orthogonal-Matching-Pursuit Algorithm
Authors: Denney Dennis 
Published: February 2015

This article, written by Senior Technology Editor Dennis Denney, contains highlights of paper SPE 163582, ’An Ensemble-Based Nonlinear-Orthogonal-Matching-Pursuit Algorithm for Sparse History Matching of Reservoir Models,’ by Ahmed H. Elsheikh, University of Texas at Austin, King Abdullah University of Science and Technology; Mary F. Wheeler, SPE, University of Texas at Austin; and Ibrahim Hoteit, King Abdullah University of Science and Technology, prepared for the 2013 SPE Reservoir Simulation Symposium, The Woodlands, Texas, 18-20 February. The paper has not been peer reviewed.
A nonlinear orthogonal-matching pursuit (NOMP) for sparse calibration of reservoir models has been proposed. Sparse calibration is a challenging problem because the unknowns are the nonzero components of the solution and their associated weights. NOMP is a greedy algorithm that, at each iteration, discovers components of the basis functions that are most correlated with the residual. The proposed algorithm relies on approximate-gradient estimation by use of an iterative-stochastic-ensemble method (ISEM). ISEM uses an ensemble of directional derivatives to approximate gradients efficiently.
Introduction
Subsurface-flow models rely on many parameters that cannot be measured directly. Instead, a sparse set of measurements may exist at well locations. The complete distributions of these unknown fields commonly are inferred by a model-calibration process that takes into account historical re-cords of the input/output of the model. However, the amount of data available to constrain the models often is limited in quantity and quality. The result is an ill-posed inverse problem that might allow many different solutions. Parameter-estimation techniques that can be applied to this problem can be classified into Bayesian methods based on Markov-chain Monte Carlo methods, gradient-based-optimization methods, and ensemble-Kalman-filter methods.
An important step in the automatic-calibration process is to define a proper parameterization of these unknown fields. Most of the parameterization methods depend on a previous model’s assumptions that define the spatial correlations of the unknown fields implicitly with a parameter-covariance matrix. Karhunen-Loève expansion (KLE) can be used for parameterizing spatially distributed fields. KLE, also known as proper orthogonal decomposition or principal-component analysis in the finite-dimensional case, is widely used for parameterizing the permeability field in subsurface-flow models. KLE is an effective method that is simple to implement; however, it preserves only the second-order moments of the distribution. For complex continuous geological structures such as a channelized domain, KLE fails to preserve higher-order moments.
Sparse calibration and compressed sensing are active research areas in the signal-processing community. Standard reconstruction methods rely on defining a set of basis functions that are orthogonal, as in KLE methods, and then an attempt is made to find the optimal set of weights to reconstruct the measurements. This reconstruction problem is an ill-posed problem, and regularization techniques (i.e., Tikhonov regularization) that constrain the ℓ2 norm of the solution are applied commonly. The quality of the solution depends on the class of basis functions used to parameterize the search space. In sparse-calibration methods, a large collection of basis functions is included in a dictionary, and the solution process consists of picking the best basis functions for accurate reconstruction of the unknown field and finding the associated weights.