2. The minimum adjustment approach

Jeroen Pannekoek and Li-Chun Zhang

Previous | Next

2.1 The optimization problem

We propose to resolve the consistency problem outlined above by adjusting the free variables simultaneously and as little as possible, such that all the edit-rules are satisfied. Let the adjustable part of the record before adjustment be denoted by a $J-$vector $x_0$ and by $\tilde{x}$ the corresponding $J-$vector after the adjustment. The optimization problem can be formulated as:

$$\begin{array}{lll}\tilde{x}\hfill & =\hfill & \arg \underset{x}{\min }D\left(x,x_0\right)\hfill \\ \text{s}\text{.t}\text{.}\hfill & \hfill & A\tilde{x}\le b,\hfill \end{array}(2.1)$$

where $D\left(x\mathrm{,}{x}_0\right)$ is a function measuring the distance (or discrepancy) between $x$ and $x_0,$ and $A$ the $K\times J$ accounting matrix associated with the $K$ constraints on $\tilde{x}$ given in (1.1). We will consider different functions $D$ in Section 2.2.

The conditions for a solution to the minimization problem (2.1) can be found by inspection of the Lagrangian for this problem, which can be written as

$$L\left(x\mathrm{,}\alpha \right)=D\left(x\mathrm{,}{x}_0\right)+{\alpha }^T\left(Ax-b\right)(2.2)$$

where $\alpha$ is a $K-$  vector of Lagrange multipliers, or dual variables, with components ${\alpha }_k,$ one for each of the $K$ constraints, and $a_k$ the $k^{\text{th}}$ row (corresponding to constraint $k)$ of the accounting matrix $A_{K\times J}.$ Notice that an additional non-negativity restriction needs to be applied to each ${\alpha }_k$ corresponding to an inequality constraint, but not the ${\alpha }_k$ of an equality constraint.

From optimization theory it is well known that for a convex function $D\left(x\mathrm{,}{x}_0\right)$ and linear constraints, the solution to (2.1) is given by vectors $\tilde{x}\mathrm{,}\tilde{\alpha }$ that satisfy the so-called Karush-Kuhn-Tucker (KKT) conditions (see, e.g., Luenberger 1984; Boyd and Vandenberghe 2004). One of them is that the gradient of the Lagrangian w.r.t. $x$ is zero when evaluated at $\tilde{x}\mathrm{,}\tilde{\alpha },$ i.e.,

$${L^{\prime }}_{x_j}\left(\tilde{x}\mathrm{,}\tilde{\alpha }\right)={D^{\prime }}_{x_j}\left(\tilde{x}\mathrm{,}{x}_0\right)+{\displaystyle \sum _k{a}_{kj}{\tilde{\alpha }}_k}=0,(2.3)$$

where $a_{kj}$ is the $\left(k\mathrm{,}j\right)-$element of $A,$ and ${L^{\prime }}_{x_j}\left(\tilde{x}\mathrm{,}\tilde{\alpha }\right)$ the gradient of $L$ w.r.t. $x_j$ evaluated at $\tilde{x}$ and $\tilde{\alpha },$ and ${D^{\prime }}_{x_j}$ that of $D.$ From (2.3), we can see how different choices for $D$ lead to different solutions to the adjustment problem, which we will refer to as the adjustment models.

2.2 Distance functions and adjustment models

A widely used distance function in many areas of statistics is the weighted least squares (WLS) function given by $D\left(x\mathrm{,}{x}_0\right)=1/2{\left(x-x_0\right)}^{T}W\left(x-x_0\right),$ where $W$ is a diagonal matrix with diagonal elements $w_j,$ for $j=1,\mathrm{...},J.$ We then obtain, from (2.3), the adjustment model

$${\tilde{x}}_j=x_{\mathrm{0,}j}-\frac{1}{w_j}{\displaystyle \sum _k{a}_{kj}{\tilde{\alpha }}_k}\mathrm{.}(2.4)$$

The WLS-criterion thus results in additive adjustments: the total adjustment to the initial value $x_{\mathrm{0,}j}$ is the weighted sum of the adjustments that correspond to each of the $K$ constraints. The adjustment due to the $k^{\text{th}}$ constraint depends on the following:

• The adjustment parameter (i.e., the dual variable) ${\tilde{\alpha }}_k$ that describes the amount of adjustment. A smaller value for ${\tilde{\alpha }}_k$ (in absolute sense if $k$ refers to an equality constraint) corresponds to a smaller adjustment; a zero value for ${\tilde{\alpha }}_k$ means that no adjustment due to that constraint takes place.

• The constant $a_{kj}$ (i.e., an element of the accounting matrix) describes the direction and size of the adjustment to variable $j.$ Often, $a_{kj}$ is 1, -1 or 0 and then describes whether $x_{\mathrm{0,}j}$ is adjusted by ${\tilde{\alpha }}_k,-{\tilde{\alpha }}_k$ or not at all.

• The weight $w_j:$ variables with larger weights are adjusted less than those with smaller weights. The special case of $w_j\equiv 1$ yields the ordinary least squares (LS) criterion, where the amount of adjustment due to each constraint is the same for all the relevant variables.

A specific choice of the weights is $w_j=1/x_{\mathrm{0,}j},$ for $j=1,\mathrm{...},J,$ in which case the squared relative adjustments are minimized and a larger initial value (i.e., $x_{\mathrm{0,}j})$ is adjusted more than a smaller one in absolute sense. Dividing (2.4) by $x_{\mathrm{0,}j}$ we obtain

$$\frac{{\tilde{x}}_j}{x_{\mathrm{0,}j}}=1-{\displaystyle \sum _k{a}_{kj}{\tilde{\alpha }}_k}\mathrm{,}(2.5)$$

which is an additive adjustment model for the ratio between the adjusted and unadjusted values. It may be noticed that this is the first-order Taylor expansion (i.e., around 0 for all the ${\tilde{\alpha }}_k’\text{s)}$ to the multiplicative adjustment given by

$$\frac{{\tilde{x}}_j}{x_{\mathrm{0,}j}}={\displaystyle \prod _k}\left(1-a_{kj}{\tilde{\alpha }}_k\right).(2.6)$$

From (2.5) we see that ${\tilde{\alpha }}_k$ determines the relative change from the initial $x_{\mathrm{0,}j}$ to the adjusted ${\tilde{x}}_j,$ which in absolute sense is usually much smaller than unity. For instance, ${\tilde{\alpha }}_k=\pm 0.2$ implies $\left|20\%\right|$ adjustment of $x_{\mathrm{0,}j}$ if $a_{kj}=\pm 1,$ which is large in practice. The products of the ${\tilde{\alpha }}_k’\text{s}$ are therefore often much smaller than the ${\alpha }_k’\text{s}$ themselves, in which case (2.5) becomes a good approximation to (2.6), and one may regard the WLS adjustment to be roughly given as the product of all the constraint-specific multiplicative adjustments.

Multiplicative adjustment by (2.6) may change the sign of $x_{\mathrm{0,}j}$ if $a_{kj}{\tilde{\alpha }}_k>1$ for some $k.$ Multiplicative adjustments that preserve the sign of the initial $x_{\mathrm{0,}j}$ can be obtained using the Kullback-Leibler (KL) divergence measure (not formally a distance function), given by $D_{KL}=$  ${\displaystyle {\sum }_j{x}_j\left(\ln x_j-\ln x_{\mathrm{0,}j}-1\right)}.$ We then have, from (2.3), the adjustment model

$${\tilde{x}}_j=x_{\mathrm{0,}j}{\displaystyle \prod _k}\exp \left(-a_{kj}{\tilde{\alpha }}_k\right)\mathrm{.}(2.7)$$

The adjustment due to constraint $k$ is equal to $1$ if $a_{kj}$ is $0$ (i.e., no adjustment), it is $\exp \left({\tilde{\alpha }}_k\right)$ if $a_{kj}$ is $1$ and it is $1/\exp \left({\tilde{\alpha }}_k\right)$ if $a_{ik}$ is $-1.$ Since $1-a_{kj}{\tilde{\alpha }}_k$ is the first-order approximation of $\exp \left(-a_{kj}{\tilde{\alpha }}_k\right)$ around ${\tilde{\alpha }}_k=0$ if $a_{kj}\pm 1,$ the WLS and KL criteria can be expected to yield similar adjustments as long as these are small or moderate.

2.3 Methods for solving the minimum adjustment problem

The general convex optimization problem (2.1) can be solved explicitly if the objective function is the weighted least squares and there are only equality constraints. In this case, the Lagrangian is $L\left(x\mathrm{,}\alpha \right)=1/2{\left(x-x_0\right)}^{T}W\left(x-x_0\right)+{\alpha }^T\left(Ax-b\right),$ and the equations to be solved are

$${L^{\prime }}_x\left(x\mathrm{,}\alpha \right)=W\left(x-x_0\right)+A^T\alpha =0(2.8)$$

$${L^{\prime }}_{\alpha }\left(x\mathrm{,}\alpha \right)=Ax-b=0.(2.9)$$

Solving (2.8) for $x$ and substituting the result in (2.9) we obtain

$$\tilde{\alpha }={\left(A{W}^{-1}{A}^T\right)}^{-1}\left(A{x}_0-b\right)$$

and then, on back substitution in (2.8), we obtain explicitly

$$\tilde{x}=x_0-W^{-1}{A}^T{\left(A{W}^{-1}{A}^T\right)}^{-1}\left(A{x}_0-b\right).(2.10)$$

For other objective functions and with inequality constraints in general, there are no explicit solutions to (2.1). However, there are many free or commercial algorithms for the convex optimization problem. For the application in this paper we used the R programming language and applied the so-called row-action or Successive Projection Algorithms (SPA) - see e.g., Censor and Zenios (1997). The SPA is an iterative algorithm that uses the constraints (rows of the accounting matrix) one by one. In one iteration the $\text{x}-$vector is sequentially adjusted to each of the constraints. The operation of adjusting to a single constraint requires only to update the elements of the $\text{x}-$vector that are involved in that constraint (corresponding to the non-zero elements of the currently processed row of the accounting matrix). After all constraints are visited one iteration is completed and the next one is started. For the WLS criterion, an R-package is available that implements the SPA and is especially designed for the adjustment problem (van der Loo 2012).

2.4 Example revisited

Table 2.1 shows the minimum adjustments of the example record in Table 1.1, using the LS-, WLS- and KL-criterion, respectively. The observed values are treated as fixed and shown in bold, the imputed values are adjustable. For the WLS method we use $w_j=1/x_{0,j},$ giving results that are equal to the KL-criterion up to the first decimal.

For both response patterns, the LS adjustment procedure leads to a negative value for Turnover other which is not acceptable (Table 2.1). When the LS-procedure is rerun with a non-negativity constraint for the variable Turnover other, the result is simply a zero for that variable and 950 for Turnover main due to constraint $a2.$ Without the non-negativity constraint, the LS-adjustments are -40 for $x_3$ and $x_4,$ and -16 for $x_6$ and $x_7,$ i.e., same adjustment for each pair of variables that appear in the same constraint. The variable Total costs $\left(x_8\right)$ is part of two constraints and the total adjustment to this variable consists of two additive components. One component is due to constraint $a1,$ and the other due to $a3.$ For response pattern (I), the first component is -48 and the second component is 16, and the two add up to -32 in Table 2.1.

Table 2.1
Imputation and adjustment of business record in Table 1.1. DI: Partial donor imputation without adjustment; LS: Least-squares distance; WLS: Weighted least-squares distance; KL: Kullback-Leibler divergence measure; GR: Generalized ratio adjustments
Table summary
This table displays the results of Imputation and adjustment of business record in Table 1.1. DI: Partial donor imputation without adjustment; LS: Least-squares distance; WLS: Weighted least-squares distance; KL: Kullback-Leibler divergence measure; GR: Generalized ratio adjustments. The information is grouped by Variable (appearing as row headers), Name, Response (I) and Response (II) (appearing as column headers).

Variable	Name	Response (I)				Response (II)
		DI	LS	WLS/KL	GR	DI	LS	WLS/KL	GR
${\text{x}}_1$	Profit	330	282	291	304	330	260	249	239
${\text{x}}_2$	Employees	20	20	20	18	25	25	25	25
${\text{x}}_3$	Turnover Main	1,000	960	922	922	1,000	960	922	921
${\text{x}}_4$	Turnover Other	30	-10	28	28	30	-10	28	29
${\text{x}}_5$	Turnover	950	950	950	950	950	950	950	950
${\text{x}}_6$	Wages	500	484	470	461	550	550	550	550
${\text{x}}_7$	Other costs	200	184	188	184	200	140	151	161
${\text{x}}_8$	Total costs	700	668	658	646	700	690	701	711

The WLS/KL adjustments are larger, in absolute sense, for larger imputed values than for smaller ones. In particular, the adjustment to Turnover other is only -2.3, so that no negative adjusted value results in this case, whereas the adjustment to Turnover main is -77.7. The multiplicative nature of these adjustments can be observed as the adjustment factor for both these variables is 0.92 (for both response patterns). The adjustment factor for Wages and Other costs in response pattern (I) is equally 0.94 because these variables are in the same constraint $a3,$ such that the ratio between their initial values is unaffected by this adjustment. However, the initial ratio of each of these variables to Total Costs is not preserved because Total Costs has a different sign in the constraint $a3$ and, moreover, Total Costs is also part of constraint $a1$ so that it is subjected to two adjustment factors.

Previous | Next