BIAS COMPENSATION IN ITERATIVE SOFT-FEEDBACK ALGORITHMS WITH
APPLICATION TO (DISCRETE) COMPRESSED SENSING
Susanne Sparrer, Robert F.H. Fischer

arXiv:1802.07105v1 [] 20 Feb 2018

Institute of Communications Engineering, Ulm University, Germany
ABSTRACT
In all applications in digital communications, it is crucial for
an estimator to be unbiased. Although so-called soft feedback is widely employed in many different fields of engineering, typically the biased estimate is used. In this paper, we
contrast the fundamental unbiasing principles, which can be
directly applied whenever soft feedback is required. To this
end, the problem is treated from a signal-based perspective, as
well as from the approach of estimating the signal based on an
estimate of the noise. Numerical results show that when employed in iterative reconstruction algorithms for Compressed
Sensing, a gain of 1.2 dB due to proper unbiasing is possible.

is available, which can be assumed to be a noisy variant of
the true value x, with the measurement noise n (variance σn2 )
which is independent of x. For brevity, all variables are assumed to be zero-mean; a generalization is straightforward.
The goal is to estimate x given the knowledge of the distributions of x and n, such that the mean-squared error is minimized. To this end, the conditional mean estimator is the
optimum solution [8, 9]. In digital communications, the corresponding estimate is often denoted as soft value xB ; it is
calculated by2 [8, 4] (η(·): real-valued estimator function)

Index Terms— MMSE estimation, Unbiasing, Soft Feedback, Compressed Sensing

The estimate can be written as the sum of the true value x and
the estimation error eB , i.e.,
xB = x + eB ,
(3)

def

η̃

with variance

1. INTRODUCTION
In communications engineering, estimation is very often
based on the minimum mean-squared error (MMSE) criterion, which is also justified by the relation between MMSE
and mutual information [1]. Independent of the problem to be
solved and of the application at hand, the used estimators need
to be unbiased, i.e., no systematic offset has to be present.
While the unbiasing is state of the art for some estimators
such as linear MMSE estimation [2, 3], for the so-called soft
feedback [4], which is used in many different fields such as
successive interference cancellation (SIC), a.k.a. decisionfeedback equalization (DFE) in multiuser detection [5, 6, 7],
unbiasing is generally ignored. In the following, we derive a
general rule for the unbiasing of soft feedback, i.e., nonlinear MMSE estimates, and apply it to iterative algorithms in
Compressed Sensing.
2. UNBIASING OF NONLINEAR MMSE
ESTIMATORS

ςe2B (z) = var{X|z} = EX {EB2 } ,

and mean-squared error

def

σe2B = EZ {ςe2B (Z)} .

(1)

This work was supported by Deutsche Forschungsgemeinschaft (DFG)
under grant FI 982/8-1.
1 Random variables are denoted by capital letters, actual realizations by
lower-case letters.

(4)
(5)

Note that ςe2B is the squared error averaged over the distribution of X and the noise N , thereby keeping the sum of
them, i.e., the observation z, fixed. σe2B , on the other hand,
averages ςe2B over all possible values of Z.
This estimate, as any MMSE solution, is biased (index
.B ), i.e., a part of the useful signal is accounted to the error, as
for any MMSE solution the error is orthogonal to the estimate
EZ {Z EB } = 0.
2.1. Signal-Based Unbiasing
In case of (scalar) linear MMSE estimation, the biased estimate is a scaled version of the observation, i.e., xB = k · z,
with the scaling factor k. In order for an estimate to be unbiased (index .U ), this scaling has to be compensated for, i.e.,
xU = h · xB ,

In many problems, an observation1
z =x+n

def

xB = min E{kη̃(z) − Xk22 } = EX {X|z} = ηX (z) . (2)

(6)

where the unbiasing factor h has to be adjusted such that the
error EU = XU − X present in the unbiased estimate is
orthogonal to X. In the linear case, it follows immediately
h = 1/k.
2 With an abuse of the term “bit”, the soft values are sometimes also denoted as soft bits.

N
X

1/kX
Z

XB

E{X|Z}

X

2.2. Noise-Based Unbiasing
XU

XB

In the previous section, X has been estimated and unbiased
directly. However, since Z = X + N , we can also estimate
N , from which, in turn, X can be calculated. This approach
is visualized in Fig. 2 [12].

XU

X
kX

WX

1/kX

N

1/kN
Z

E{N|Z}

N̂B

N̂U
−

Fig. 1. Block diagram of signal-based unbiasing.
While the scaling factor k is obvious for linear estimators,
in the case of non-linear estimators an average scaling has to
be calculated. To this end, the nonlinear estimate ηX (Z) is
represented as the sum of a linear estimate kX X and noise
WX , which is uncorrelated to the linear estimate [10, 11]
as visualized in the block diagram given in Fig. 1, and in
Fig. 4. Adjusting kX according to the MMSE criterion, i.e.,
such that
o
n
2
2
} → min ,
EXN (XB − kX · X) = EXN {WX
(8)

leads to [11]
EXN {XB X}
EXN {ηX (X + N ) X}
=
.
2
EX {X }
EX {X 2 }

(9)

With EXN {XB N } = σe2B [14] and EXN {XB Z} = σx2 , it
calculates to
σ2 − σ2
σ2
EXN {XB Z} − EXN {XB N }
kX =
= x 2 eB = x2B .
2
EX {X }
σx
σx
(10)
Hence, plugging h = 1/kX into (6) gives
σ2
xU = 2 x 2 · xB = (1 − CX ) · xB ,
σx − σeB

def
where we defined CX = σe2B / σe2B − σx2 .

(11)

(12)

EXEU {X · EU } = 0 .

With straightforward reformulations, the variance of EU
reads
=
=

2
EX {EU
} = EX {(xU −

2
2
·
1 − CX · ςe2B + CX

2

X) }

σx2

.

(13)

if no unbiasing is applied, a
Thus, instead of the variance
tradeoff between ςe2B and σx2 is active.
ςe2B

kN

WN

+

N̂U
−
1/kN

XU

Z

Fig. 2. Block diagram of error-based unbiasing.
Note that the nonlinear estimator of the noise is connected
to the estimator of the signal by
def

ηN (z) = EN {N |z} = EN {(Z − X)|z} = z − ηX (z) .
(14)
Hence, the output of the estimator can be written as N̂B =
Z − XB . Similar to the signal-based case, we linearize the
estimator ηN (z) by
N̂B = kN N + WN ,

(15)

σe2B ,

the scaling factor is

where, again using EXN {XB N } =
calculated by [12, 14]
kN =

σn2 − σe2B
EXN {N̂B N }
EXN {(Z − XB )N }
=
=
.
EN {N 2 }
EN {N 2 }
σn2
(16)

Plugging n̂U = 1/kN · n̂B into (14) gives the unbiased estimate3 for x
1
· n̂B = (1 − CN ) · xB + CN · z ,
(17)
xU = z −
kN
def

The estimate can be written as noisy variant of the true
value, i.e., xU = x + eU . As for any unbiased estimate, the
(zero-mean) error eU is the one with minimum mean-squared
2
error EXN {EU
}, which is orthogonal to the signal to be estimated

ςe2U

N̂B

(7)

XB = ηX (Z) = kX X + WX ,

kX =

N

XU

with CN = σe2B /(σe2B − σn2 ). Due to construction, in this
case the estimation error EU is not orthogonal to X, but to N .
Noteworthy, in contrast to the signal-based estimation where
the unbiased estimate was a scaled version of xB , it depends
on xB as well as on z if noise-based unbiasing is applied.
The unbiased error variance (w.r.t. X, eU = xU − x) can
be calculated by
 2
2
2
2
} = 1 − CN
ςe2U = EX {EU
· σn2 .
(18)
· ςeB + CN
2.3. Discussion

Examples of the characteristic curves (top) of the biased and
unbiased soft values, as well as the corresponding error variances (bottom), are given in Fig. 3 [12]. While the character3 In

[15], the (scaled) unbiased estimator is denoted as divergence-free.

−0.5

−1

−1

−1.5
−1.5

−1

−0.5

0.25

0

z→

0.5

1

1.5

−1

−0.5

0.25

0

z→

0.5

1

1.5

σe2• →

0.2

σe2• →

0.2

0.15

0.15

0.1

EU

kX · X

B

XB

X

XU

EU X

Fig. 4. Visualization of the variables present in the estimation
process [12]. Linear estimation (left), nonlinear estimation
(right). Red: Signal-based unbiasing. Blue: Noise-based unbiasing.

0.1

0.05
0
−1.5

−1.5
−1.5

XU

XU

EB

−0.5

Z

EU

0

EB
WX

0

XB

XU

Nˆ

0.5

Z,

η• →

0.5

η• →

1

N

1.5

1

N, EU

1.5

0.05

−1

−0.5

0

z→

0.5

1

1.5

0
−1.5

−1

−0.5

0

z→

0.5

1

1.5

Fig. 3. Characteristic curves of biased (blue) and unbiased
(green: signal-based, red: noise-based) soft values for σn2 =
0.1 (left) and σn2 = 0.01 (right). Soft values (top), error variance (bottom).
istic curves of the biased (blue) and the signal-based unbiased
(green) estimates are strictly monotonically increasing, the
noise-based unbiased curves (red) do not fulfill this property.
As for all MMSE solutions, the unbiased estimates converge
to the biased values if σn2 tends to zero, since the deviation of
the (biased) estimates from the correct value is negligible in
this case.
The variables present in the estimation process are visualized in Fig. 4, where the squared length of a vector corresponds to the variance of the corresponding variable [8]. The
given variables X and N are orthogonal, and Z = X + N . In
case of a linear estimator, XB and XU are scaled versions of
Z, and EB ⊥ Z, cf. Fig. 4, left part. In case of signal-based
unbiasing (red), EU has to be orthogonal to Z, and hence
XU = Z. For noise-based unbiasing (blue), EU has to be
orthogonal to N , and hence XU = 0.
The nonlinearity of soft feedback calculation introduces
an additional degree of freedom, i.e., a three-dimensional signal space is needed to represent the variables. In particular, XB will point out of the X-N -plane; this additional dimension, orthogonal to X and N , is denoted as vertical dimension V in the following. The visualization in the right
part of Fig. 4 is a two-dimensional projection of the threedimensional graph. Due to the orthogonality conditions, XU
is an elongation of XB on the N -V -plane for signal-based unbiasing; for noise-based unbiasing, XU is determined by the
intersection of an elongation of N̂B with the X-V -plane.
Hence, while the unbiased error EU remains in the N -V plane in case of signal-based unbiasing, if noise-based unbiasing is applied it lays in the X-V -plane, i.e., EU is orthogonal
to the noise. If applied in an algorithm where linear estimation
and soft-feedback calculation are iterated, in case of signalbased unbiasing the error is constantly in the N -V -plane. For
noise-based unbiasing the error alternates between the N -V -

and X-V -plane every other iteration, which is beneficial for
convergence and accuracy.
2.4. Connection to Average Variances
Often, the soft values of a vector z have to be calculated. In
this case, the unbiasing equations ((11) and (13) in the signalbased case, (17) and (18) for noise-based unbiasing) are applied for each element individually, leading to individual estimates and individual error variances.
However, in some situations, instead of individual variances, an average variance (averaged over the entire vector)
should characterize the reliability. To this end, all elements of
z are assumed to have the same average noise variance σn2 .
Then, ςe2B of the individual elements (Eq. (4)) has to be replaced by σe2B (in practice, the expectation according to (5)
is replaced by σ̄e2B that is averaging ςe2B over the vector elements), leading to the unbiasing equations (for the lth element
of the vector)
−1

1
1
xB,l
2
2
,
σeU =
− 2
xU,l = σeU · 2 ,
σ̄eB
σ̄e2B
σx
for signal-based unbiasing, and



−1
xB,l
1
zl
1
2
2
xU,l = σeU ·
,
− 2 , σeU =
− 2
σ̄e2B
σ̄n
σ̄e2B
σ̄n

in the noise-based case. Note that the latter equations equal
the ones used in [13, 14, 15] without any justification, in particular not the above given interpretation.
3. APPLICATION TO COMPRESSED SENSING
In Compressed Sensing, a sparse vector x has to be estimated
from an underdetermined system of linear equations, which is
given by [16]
y = Ax + w ,
(19)
where the received vector y ∈ RK depends on the measurement (channel) matrix A ∈ RK×L , L > K, and on the sparse
vector x ∈ C L (with sparsity s), where C ⊆ R. Furthermore,
the measurements are corrupted by i.i.d. zero-mean Gaussian
2
noise w with variance σw
per component, which is independent of x. In discrete Compressed Sensing, the elements of

−3

10

IMS
xuIMS
nuIMS
TMS
BAMP

−4

10

SER →

x are furthermore assumed to be drawn from a finite set, i.e.,
C = {0, c1 , . . . , c|C|−1 }.
Due to the sparsity constraint and the discrete alphabet,
the problem of estimating x based on (19) is non-convex.
Different algorithms for the approximate solution of the problem are available in the literature; for a detailed discussion
thereon, cf., e.g., [13, 14].

−5

10

3.1. Algorithm

2
Alg. 1 x̂ = recover y, A, σw
, s, C
Variants: B: IMS, U: (·)uIMS
1 : xL,U = 0, σe2

N,U,l

= s/L ∀ l



2 : while stopping criterion not met {
3 : (xL,U , σ 2e
) = unbiased linear MMSE estimate (A, y, xN,U , σ 2e
L,U

4 :

(xN,B,l , ςe2

N,B,l

5B: (xN,U,l , σe2
5U: (xN,U,l ,

N,U

) = biased soft feedback (xL,U,l , σe2

L,U,l

) = (xN,B,l , ςe2

N,U,l
)
σe2
N,U,l

N,B,l

)

= unbias(xN,B,l , ςe2

6 : }
7 : x̂ = QC (xN,B )

)

, s, C)

N,B,l

)

3.2. Simulation Results
The performance of IMS with unbiasing is shown in Fig. 5 for
L = 258, K = 129, s = 15, C = {−1, 0, +1}. The measurement matrix is a random Gaussian matrix, with the columns
normalized to unit norm. In the upper part, the symbol error rate (SER) over the noise variance is shown. In order to
ensure convergence, all algorithms perform 50 iterations. Besides IMS and (·)uIMS, also the results for noise-based unbiasing with average variances (TMS [14]) and for the BAMP
algorithm [18] are shown.
While IMS without unbiasing (green) performs even
worse than TMS (blue) which tracks only average instead
of individual variances, the performance can be improved
if individual signal-based unbiasing (xuIMS, red dashed) is
applied. Individual noise-based unbiasing (nuIMS, red solid),

−6

10

16

16.5

17

17.5

18

18.5

19

10 log10 (1/σn2 ) [dB] →

−2

10

−3

10

SER →

In [13], an iterative algorithm denoted as IMS has been proposed which splits the estimation problem into two parts,
alternatingly estimating x w.r.t. the Gaussian noise (Linear
MMSE estimation, index .L ), and w.r.t. s and C (Nonlinear
MMSE estimation (soft feedback), index .N )). The pseudocode of this algorithm is given in Alg. 1.
While the MMSE estimate in the first step is unbiased,
the soft values in the second step are not unbiased in the
original algorithm (i.e., biased, Line 5B). Thus, we apply the
equations for individual signal- or noise-based unbiasing derived in this paper and denote the new algorithm, including
the unbiasing, as xuIMS and nuIMS, respectively (cf. Alg. 1,
Line 5U).
Note that the TMS algorithm [14] (strongly related to
OAMP or VAMP [15, 17]) is similar to nuIMS, however using average variances instead of individual ones; thus, it does
not benefit from the information about the reliability of the
particular elements as does uIMS.

−4

10

−5

10

−6

10

2

4

6

8

10

12

14

16

18

20

# Iter →

Fig. 5. SER of the proposed algorithm with unbiasing over
the noise level 1/σn2 in dB (top), and over the iterations for
10 log10 (1/σn2 ) = 18 dB (bottom). L = 258, K = 129,
s = 15, C = {−1, +1}. Gaussian matrix, kA(:, l)k2 = 1 ∀ l.
however, clearly outperforms the other algorithms by 0.7 dB
and 0.5 dB, respectively. Hence, the disadvantage that the
unbiased error is not orthogonal to the signal, is overcompensated by the orthogonality of the noise/input error and
the estimation error (cf. Sec. 2.3). Furthermore, the BAMP
algorithm (black), which is state of the art in Compressed
Sensing, is also clearly outperformed.
In the lower part if Fig. 5, the SER over the number of
iterations is shown for 10 log10 (1/σn2 ) = 18 dB. Noteworthy,
IMS and both variants of uIMS converge significantly faster
than TMS, i.e., the tracking of individual instead of average
variances does not only improve the performance, but accelerates also the convergence. Furthermore, BAMP performs
again worst.
4. CONCLUSION
In this paper, we have discussed the unbiasing for soft feedback, treating the estimation problem from the signal as well
as from the noise perspective. Both approaches have been
compared, and the connection to solutions with average variances, as they are widely used in the literature, has been
pointed out. Furthermore, both derived unbiasing variants
have been employed in an iterative algorithm, and the gains
due to the unbiasing have been investigated by numerical
results.

5. REFERENCES
[1] D. Guo, Y. Wu, S. Shamai, S. Verdú. Estimation in Gaussian Noise:
Properties of the Minimum Mean-Square Error. IEEE Transactions on
Information Theory, vol. 57, no. 4, pp. 2371–2385, Apr. 2011.
[2] G. D. Forney Jr. “On the Role of MMSE Estimation in Approaching
the Information-Theoretic Limits of Linear Gaussian Channels: Shannon Meets Wiener.” Proc. Allerton Conference, pp. 430–439, Oct.
2003.
[3] R.F.H. Fischer. Precoding and Signal Shaping for Digital Transmission, John Wiley & Sons, New York, 2002.
[4] F. Tarköy. “MMSE-Optimal Feedback and its Applications.” Proc.
IEEE International Symposium on Information Theory (ISIT), p. 334,
Sep. 1995.
[5] T. Frey, M. Reinhardt. “Signal Estimation for Interference Cancellation and Decision Feedback Equalization.” Proc. IEEE Vehicular
Technology Conference (VTC), pp. 113–121, May 1997.
[6] A. Lampe, J.B. Huber. “On Improved Multiuser Detection with Iterated Soft Decision Interference Cancellation.” Proc. Communications
Theory Mini-Conference at GLOBECOM, pp. 172–176, June 1999.
[7] R.R. Müller, J.B. Huber. “Iterated Soft-Decision Interference Cancellation for CDMA.” Broadband Wireless Communications, eds. M.
Luise and S. Pupolin, pp. 110–115, Springer, London, 1998.
[8] A. Papoulis. Probability, Random Variables, and Stochastic Processes, McGraw-Hill, Inc., Tokyo, Japan, 1965.
[9] S.M. Kay. Fundamentals of Statistical Signal Processing: Estimation
Theory, Prentice-Hall Inc., Upper Saddle River, NJ, USA, 1993.
[10] P. Banelli. “Non-Linear Transformations of Gaussians and GaussianMixtures with Implications on Estimation and Information Theory.”
arXiv, 1111.5950v3, 10. May 2013.
[11] H.E. Rowe. “Memoryless Nonlinearities With Gaussian Inputs: Elementary Results.” The Bell System Technical Journal, vol. 61, no. 7,
Sep. 1982.
[12] R.F.H. Fischer. Notes on MMSE Estimation and Bias Compensation.
Unpublished Manuscript, 2016.
[13] S. Sparrer, R.F.H. Fischer. “Algorithms for the Iterative Estimation of
Discrete-Valued Sparse Vectors.” Proc. ITG Conference on Systems,
Communications and Coding (SCC), Feb. 2017.
[14] S. Sparrer, R.F.H. Fischer. “Unveiling Bias Compensation in TurboBased Algorithms for (Discrete) Compressed Sensing.” Proc. European Signal Processing Conference (EUSIPCO), Aug. 2017.
[15] J. Ma, L. Ping. “Orthogonal AMP.” IEEE Access, vol. 5 pp. 2020–
2033, Jan. 2017.
[16] D.L. Donoho. “Compressed Sensing”. IEEE Transactions on Information Theory, vol. 52, no. 4, pp. 1289–1306, Apr. 2006.
[17] S. Rangan, P. Schniter, A.K. Fletcher. “Vector Approximate Message
Passing.” Proc. IEEE International Symposium on Information Theory
(ISIT), pp. 1588–1592, June 2017.
[18] D.L. Donoho, A. Maleki, A. Montanari. “Message Passing Algorithms
for Compressed Sensing: I. Motivation and Construction.” Proc. Information Theory Workshop (ITW), Jan. 2010.

