1

arXiv:1705.08394v1 [] 23 May 2017

Information Theoretic Principles
of Universal Discrete Denoising
Janis Nötzel∗,1,2 and Andreas Winter×,1,3
1
Departament de Fı́sica: Grup d’Informació Quàntica,
Universitat Autònoma de Barcelona, ES-08193 Bellaterra (Barcelona), Spain.
2
Theoretische Nachrichtentechnik, Technische Universität Dresden, D-01187 Dresden, Germany.
3
ICREA—Institució Catalana de Recerca i Estudis Avançats, Pg. Lluis Companys, 23, ES-08010 Barcelona, Spain.
Email: ∗ janis.noetzel@tu-dresden.de, × andreas.winter@uab.cat
(23 May 2017)

Abstract—Today, the internet makes tremendous amounts of
data widely available. Often, the same information is behind
multiple different available data sets. This lends growing importance to latent variable models that try to learn the hidden
information from the available imperfect versions. For example,
social media platforms can contain an abundance of pictures
of the same person or object, yet all of which are taken from
different perspectives. In a simplified scenario, one may consider
pictures taken from the same perspective, which are distorted by
noise. This latter application allows for a rigorous mathematical
treatment, which is the content of this contribution. We apply a
recently developed method of dependent component analysis to
image denoising when multiple distorted copies of one and the
same image are available, each being corrupted by a different
and unknown noise process.
In a simplified scenario, we assume that the distorted image
is corrupted by noise that acts independently on each pixel.
We answer completely the question of how to perform optimal
denoising, when at least three distorted copies are available: First
we define optimality of an algorithm in the presented scenario,
and then we describe an aymptotically optimal universal discrete
denoising algorithm (UDDA). In the case of binary data and
binary symmetric noise, we develop a simplified variant of the
algorithm, dubbed BUDDA, which we prove to attain universal
denoising uniformly.

Keywords: blind detection, image denoising, hidden variable, latent variable, internet of things.
I. I NTRODUCTION
Consider the following, idealised situation of inference from
noisy data: In the past, a number K of pictures has been taken
of an object. Each picture consists of a number n of pixels,
and each pixel takes values in a finite alphabet X of colours,
∣X ∣ = L. We would like to recover from these images a “true”
image, of which we assume all K that we have at our disposal
are noisy copies.
To be precise, we assume that each of the pictures is the
output of a memoryless (i.i.d.) noise process W , mapping an
element x ∈ X to another element y ∈ X with probability
w(y∣x). If we knew W as well as the frequency p(x) of the
colours x in the original, we could choose some permutation
Φ ∶ X → X as the denoising rule. If one is agnostic about
the colour of each pixel and applies any such denoising to a
long enough string on a pixel-by-pixel basis, it will produce a

recovered image that, with high probability, deviates from the
original in a fraction of pixels asymptotically equal to
1 − max ∑ p(τ (x))w(Φ−1 (x)∣τ (x))
τ

x∈X

= 1 − max ∑ p(x)w(τ (x)∣x),
τ

(1)

x∈X

where the maximum is over all permutations τ ∶ X → X .
Given that we are more interested in the structure of the image,
and not in the question whether it is, say, black-and-white or
white-and-black, this is a satisfactory solution.
However, if the number of possible outputs of the noise
process grows, such simple solutions turn out to be not optimal
anymore, because more information is available in the string
that a letter-by-letter algorithm does not see. Consider the
following example, where a channel maps the black and white
pixels represented by the alphabet {1, 2} to three different
colours {1, 2, 3}. Let the probabilistic law of this process be
given by w(1∣1) = w(3∣1) = 1/2 and w(2∣2) = 1. A simple
denoising algorithm may map the elements of the set {1, 2} to
1 and those in {3} to 2. If the input bits are equally distributed,
the probability that this algorithm produces an error is lower
bounded by 1/4 – even if one is agnostic as to an exchange
1 ↔ 2 at the input. Instead, knowing the channel lets one
perform perfect denoising, i.e. with zero error.
The problem is thus to know the channel, which it turns
out can be achieved by looking at several independent noisy
copies instead of only one. We now give another example
about large classes of channels which allow us to achieve a
nontrivial inference about the original by a generic algorithmic
strategy.
Example 1. Let the binary symmetric channels (BSC) W1 ,
W2 , W3 be given, each with a respective probability wi of
transmitting the input bit correctly, and the channel W from
{0, 1} to {0, 1}3 is the product, giving the same input to
all: W (y1 y2 y3 ∣x) = ∏3j=1 wj (yj ∣x). Then, a simple way of
guessing the input bit is to use the majority rule, i.e. the
output is mapped to 0 iff N (0∣y1 y2 y3 ) > N (1∣y1 y2 y3 ). Assume
that the input string has equal number of 0 and 1. For
BSC parameters w1 = 0.1, w2 = 0.45 and w3 = 0.9, this
gives a probability of correct decoding that is bounded as
4/10 ≤ pcorrect ≤ 5/10.

work assumes Gaussian noise, whereas our work is able to
handle any form of noise within the category of finite-alphabet
memoryless noise processes. Sparsity has been exploited for
coloured images in [13], universal compressed sensing in [14].
A new method for image denoising was presented first here
[15] and then further developed in [16]. A scenario that is
related to the one treated here has been investigated in the
recent work [17], but without application to a specific problem.
The focus of the work [17] was to demonstrate that certain
hidden variable models have a one to one correspondence
to a particular subset of probability distributions. The results
presented in [17] are closely related to the famous work
[18] of Kruskal, which forms one theoretical cornerstone
of the PARAFAC model (see the review article [19] to get
an impression of methods in higher order data analysis).
The connections between PARAFAC, multivariate statistical
analysis [20] and more information-theoretic models has also
been used in the recent work [21], where the authors basically
elaborated on methods to efficiently perform step 3 of our
algorithm in the restricted scenario where all channels are
identical: w1 (y∣x) = . . . = wK (y∣x) for all y ∈ Y and x ∈ X .
The interested reader can find details regarding algorithms
for fitting the PARAFAC model in [22]. Further connections
to deep learning, current implementations and other areas of
application are to be found in [23]. Our Theorems 13 and 12
provide an improvement over all the existing algorithms in
a restricted but important scenario. Despite some similarities,
the problem treated here is to be distinguished from the CEO
problem [24], [25], which is also receiving attention recently
[26] but is focussed on rate constraints in the process of data
combining from the multiple sources. In addition, noise levels
are assumed to be known in the CEO problem.

Thus, even taking into account our agnostic view regarding
the labelling of the input alphabet, the probability of guessing
the right input up to a permutation is upper bounded by 6/10.
Now consider a genie-aided observer that is given BSC parameters. Such an observer would come to the conclusion that
the second channel, W2 , actually conveys little information to
him, and could decide to not consider its output at all. The
genie-aided observer could then come up with the following
rule for guessing the input bit: The outputs in the set {00, 01}
get mapped to 0, while the outputs in the set {11, 10} get
mapped to 1. Then, the probability of correctly guessing the
input bit would rise to 9/10.
Note that the permutation of the colours is an unavoidable
limit to any recovery procedure in which we do not want
to make any assumptions about the channels and the colour
distribution p.
Based on these considerations, we propose the general
mathematical formulation of our problem is as follows. As
before we assume the existence of one “original” version of the
picture, which is represented by a string xn ∈ X n where n ∈ N.
A number K of copies of the image is given, where each copy
is modelled by a string yj = (y1j , . . . , ynj ), and j ranges from
1 to K. These images are assumed to be influenced by an
i.i.d. noise process, such that the probability of receiving the
matrix y = (yij )n,K
i,j=1 of distorted images is given by
n,K

P(y∣xn ) = ∏ wj (yij ∣xi ).

(2)

i,j=1

The probabilistic laws w1 , . . . , wK crucially are not known.
The question is: What is the optimal way of recovering xn
from the output y? Before we formalize this problem, we give
an overview over the structure of the paper and then of the
related work.

III. D EFINITIONS
A. Notation
The set of permutations of the elements of a finite set X
is denoted SX . Given two finite sets X , Y, their product is
X ×Y ∶= {(x, y) ∶ x ∈ X , y ∈ Y}. For any natural number n, X n
is the n-fold product of X with itself. For a string xn ∈ X n ,
and an element x′ ∈ X , let N (x′ ∣xn ) ∶= ∣{i ∶ xi = x′ }∣ be
the number of times x′ occurs in the string. The probability
distribution N (x′ ∣xn ) ∶= n1 N (x′ ∣xn ) is called the type of xn .
The set P(X ) of probability distributions on X is identified
with the subset

II. R ELATED WORK
The earlier work in the area of image denoising has focussed
mostly on situations where the probabilistic law governing the
noise process is (partially) known. Among the work in that
area are publications like [1]–[4]. In particular, the work [1]
laid the information theoretic foundation of image denoising
when the channel is known. It has been extended to cover
analysis of grayscale images, thereby dealing with the problem
incurred by a large alphabet, here [5]. The DUDE framework
has also been extended to cover continuous alphabets [6]
and in other directions [7]. An extension to cover noise
models with memory has been developed in [8]. Optimality
of the DUDE has been further analyzed in [9], where it
was compared to an omniscient denoiser, that is tuned to
the transmitted noiseless sequence. An algorithm for general
images has e.g. been demonstrated here [10].
Cases where the probabilistic law behind the noise process
is known partially were treated in [3], [4]. A tour of modern
image filtering with focus on denoising can be found in the
work [11]. The feasibility of the task of multi copy image
denoising in a very particular scenario that is similar to the
one treated here has been demonstrated [12]. However, that

{p ∈ R∣X ∣ ∶ p = ∑ p(x)ex }

(3)

x∈X

of R∣X ∣ , where {ex }x∈X is the standard orthonormal basis
of R∣X ∣ . The support of p ∈ P(X ) is supp(p) ∶= {x ∈ X ∶
p(x) > 0}. We define two important subsets of P(X ), for a
conventional numbering X = {x1 , x2 , . . . , xL }:
P> (X ) ∶= {p ∈ P(X ) ∶ p(x) > 0 ∀ x ∈ X } ,

(4)

↓

P (X ) ∶= {p ∈ P(X ) ∶ p(x1 ) ≥ p(x2 ) ≥ . . . ≥ p(xL ) > 0} .
(5)
A subset of elements of P(X ) is the set of its extreme points,
the Dirac measures: for x ∈ X , δx ∈ P(X ) is defined through
2

δx (x′ ) = δ(x, x′ ), where δ(⋅, ⋅) is the usual Kronecker delta
symbol. The indicator functions are defined for subsets S ⊂ X
via 1S (x) = 1 if x ∈ S and 1X (x) = 0 otherwise.
We will have to measure how different two elements p, p′ ∈
P(X ) are. This may
√ be done using (for any α ≥ 1) the αnorms ∥p − p′ ∥α ∶= α ∑x∈X ∣p(x) − p′ (x)∣α . If α = 1, this reduces, up to factor of 2, to the total variational distance, which
we will use in the following while dropping the subscript.
The noise that complicates the task of estimating p is modelled by matrices W of conditional probability distributions
(w(y∣x))x∈X ,y∈Y whose entries are numbers in the interval
[0, 1] satisfying, for all x ∈ X , ∑y∈Y w(y∣x) = 1; such objects
are also called stochastic matrices. To given finite sets X and
Y, the set of all such matrices is denoted C(X , Y) in what
follows. These stochastic matrices are, using standard terminology of Shannon information theory, equivalently called a
“channel”. In this work, we restrict attention to those stochastic
matrices that are invertible, denoting their set C0 (X , Y). A
special channel is the “diagonal” ∆ ∈ C(X , X K ), defined
as ∆(δx ) ∶= δx⊗K . For a probability distribution p ∈ P(X ),
we write p(K) ∶= ∆(p), which assigns probability p(x) to
xx . . . x, and 0 to all other strings. If two channels W1 and W2
act independently in parallel (as in (2) with K = 2 and n = 1),
one writes W1 ⊗ W2 for this channel, and more generally
for K ≥ 2. We will abbreviate the K-tuple (W1 , . . . , WK ) as
W, if K is known from the context. A dependent component
system is simply a collection (p, W) = (p, W1 , . . . , WK ) consisting of a distribution p on X and channels W ∈ C(X , Y).
The distance between two dependent component systems is
defined as

meaning of a pixel color. For example, we do not make any
distinction between a black-and-white picture and a version
of that picture where black and white have been interchanged
throughout. This motivates the following definition.
Definition 3 (Universal algorithm). Let W ∈ C(X , X )K and
p ∈ P(X ) be given. A sequence C = (Cn )n∈N of algorithms
Cn ∶ (X K )n → X n is said to achieve resolution D ≥ 0 on W
with respect to p, if for every ε > 0 there is an N = N (p, W, ε)
such that for all sequences (xn )n∈N of elements of X n with
limit limn→∞ N (⋅∣xn ) = p we have
∀n ≥ N (p, W, ε)
The number
R(p, W) ∶= inf {D ∶

∃ C achieving distortion
}
D with respect to p

(9)

is the resolution of W with respect to p. A sequence of
algorithms is universal if it achieves resolution R(p, W) for
all p and W.
A sequence of algorithms is uniformly universal on S ⊂
C(X , X ) if for all W ∈ S K the number N = N (W, ε) =
N (p, W, ) can be chosen independently of p. If such a
sequence exists, we say that the resolution D is achieved
uniformly. Then,
R(p, W) ∶= inf {D ∶

∃ C uniformly achieving
}
distortion D w.r.t. p

(10)

is called the uniform resolution of W. Clearly, R(p, W) ≤
R(p, W).

∥(r, V) − (s, W)∥DCS ∶= ∥r − s∥1 + ∑ ∥Vj − Wj ∥F B , (6)

Note that, if a sequence of uniformly universal algorithms
exists, this implies that these algorithms deliver provably
optimal performance for every possible input sequence xn ,
if only n ≥ N (W, ε) is large enough.
We stress that the definition of resolution does in general
depend on p, as can be seen from the following example.

j=1

where ∥Vj − Wj ∥F B ∶= maxx ∑y ∣vj (y∣x) − wj (y∣x)∣.
Finally, we quantify the distance between an image (or
string of letters) and another such image (or string of letters).
Definition 2 (Distortion measure). Any function d ∶ X × X →
R≥0 is said to be a distortion measure. Clearly, this definition
includes as a subclass the distortion measures that are at the
same time a metric. The special case d(x, x′ ) ∶= δ(x, x′ ) of
the Kronecker delta is known as the Hamming metric. It is
understood that any distortion measure d naturally extends to
a distortion measure on X n × X n via
1 n
∑ d(xi , yi ).
n i=1

τ

(8)

K

d(xn , y n ) ∶=

P (min d(Cn (⋅), τ ⊗n (xn )) > D) < ε.

Example 4. Let W ∈ C({0, 1, 2}, {0, 1}) be defined by
w(0∣0) = w(0∣1) = 1 and w(1∣2) = 1 and d be the hamming distortion. Then, clearly, every two p, p̂ ∈ P({0, 1, 2})
satisfying p(2) = p̂(2) = 0 have the property W (p) = W (p̂).
Thus, no two sequences xn , x̂n ∈ {0, 1, 2}n having N (2∣xn ) =
N (2∣x̂n ) = 0 can be distinguished from each other after having
passed through the channel.
Let Cn be any decoder, assuming without loss of generality
that Cn (1n ) = 1n . Consider xn = 0n/2 1n/2 ; it follows that
minτ d(Cn (⋅), τ ⊗n (xn )) = 21 with probability 1.
The same decoder applied to x̂n = 1n or x̃n =
0n obviously has minτ d(Cn (⋅), τ ⊗n (x̂n )) = 0 and
minτ d(Cn (⋅), τ ⊗n (x̃n )) = 0, both once more with probability
1.
This demonstrates the dependence of R(p, W) on p for
simple cases where K = 1 and the channel matrix is noninvertible.

(7)

B. Definition of Resolution
In the following, we assume a distortion measure d on
X × X . With respect to such a measure, the performance of a
denoising algorithm can be defined. In the special case treated
here, we are interested in a form of universal performance that
does not depend on any knowledge regarding the specific noise
parameters. Our way of defining universality is in the spirit
of Shannon information theory. Such a definition brings with
it two important features: First, it is an asymptotic definition,
and secondly it is a definition that is agnostic as to the specific

Remark 5. Note that our definition of universality explicitly
forbids an algorithm to know the probabilistic laws according
3

5) For each i ∈ [n], apply the MCA decoder to the
sequence (yi1 , . . . , yiK ). This generates a sequence x̂n =
x̂1 . . . x̂n .
6) Output x̂n .

to which the original image gets distorted. In that sense, it
respects a stronger definition of universality as for instance
the DUDE algorithm [1]: the DUDE algorithm has to know
the probabilistic law, which is assumed to be represented by
an invertible stochastic matrix. We will see in Theorem 7 in
which situations an algorithm obeying our stronger definition
can be expected to deliver provably optimal performance, and
what its drawbacks in terms of performance are.

Remark 8. An obvious modification of this algorithm is to
deviate from the above definition in step 4, and instead run the
DUDE algorithm from Ref. [1] or one of its modifications. The
results in [27] imply that optimality holds also in that case,
since the deviation of the estimated tuple (r, V1 , . . . , VK ) from
the original (p, W1 , . . . , WK ) goes to 0 as n → ∞.

Definition 6 (Minimal clairvoyant ambiguous distortion). Let
W ∈ C(X , Y) be a channel and p ∈ P(X ) a probability
distribution. Let d ∶ X × X → R be a distortion measure.
The number
dMCA (p, W ) ∶= min

Definition 9. The DCA algorithm from [17] is defined by the
following simple rule:

′
∑ p(x)d(x, x )w(Tτ (x′ ) ∣x), (11)

K

τ ∈SX ,T x,x′ ∈X

q̂ z→ arg min {∥(⊗ Vi )r(K) − q̂∥ ∶
i=1

is called the minimal clairvoyant ambiguous (MCA) distortion,
where each T = {Tx }x∈X is partition of Y, i.e. Tx ∩Tx′ = ∅ for
all x ≠ x′ and ⋃x Tx = Y. It is the smallest expected distortion
obtainable if the original xn is distributed according to p⊗n
and the dependent component system (p, W ) is known to the
decoder. We call a minimizing partition T MCA decoder.
For each collection W = (W1 , . . . , WK ) of channels we
define

The reason that this simple algorithm yields correct solutions is based on the following observation, which is a
reformulation of [17, Thm. 1] and stated without proof.
Theorem 10. Let K ≥ 3, p ∈ P(X ) and let W1 , . . . , WK ∈
C0 (X , X ) be invertible channels. There are exactly ∣X ∣! tuples
(V1 , . . . , VK , p′ ) of channels V1 , . . . , VK ∈ C(X , X ) and
probability distributions p′ ∈ P(X ) satisfying the equation

K

dMCA (p, W) ∶= dMCA (p, (⊗ Wj ) ○ ∆) ,

K

(12)

K

′

∑ ∏ wi (yi ∣x)p(x) = ∑ ∏ vi (yi ∣x)p (x)

j=1

x∈X i=1

with the “diagonal” channel ∆ ∈ C(X , X K ).

(15)

x∈X i=1

simultaneously for all y1 , . . . , yK ∈ X . These are as follows:
For every permutations τ ∶ X → X , the matrices Vi = Wi ○ τ −1
and the probability distribution p′ = τ (p) solve (15), and these
are the only solutions. As a consequence, the function Θ ∶
P(X ) × W(X , X )K → P(X K ) defined by

IV. M AIN RESULTS
In this section, we state our main result regarding universal denoising and present two algorithms. The first one is
universal, while the second one is even uniformly universal,
but unfortunately only if restricted to dependent component
systems with binary symmetric channels.

K

L

i=1

i=1

Θ[(p, T1 , . . . , TK )] ∶= (⊗ Ti ) (∑ p(i)δi⊗K )

(16)

is invertible if restricted to the correct subset: there exists a
function Θ′ ∶ ran(Θ) → P ↓ (X ) such that

A. The universal discrete denoising algorithm

Θ′ (Θ[(p, T1 , . . . , TK )]) = p,

Theorem 7. Let K ≥ 3 and d be a distortion measure on
X × X . Let W = (W1 , . . . , WK ) ∈ C(X , X )K be such that
their associated stochastic matrices are invertible, and p ∈
P(X ). Then, the resolution of W with respect to p is
R(p, W) = dMCA (p, W).

r ∈ P ↓ (X ),
} . (14)
Vi ∈ C(X , X )

(17)

for all p ∈ P ↓ (X ) ∩ P> (X ) and (T1 , . . . , TK ) ∈ C0 (X , X )K .
B. A uniformly universal algorithm

(13)

An important distinction that we made in the definitions is
that between a universal and a uniformly universal algorithm.
We will now explain this difference based on the restricted
class of binary symmetric channels (BSCs). Then, we present
an algorithm that is uniformly universal if restricted to dependent component s ystems allowing only BSCs.
For this class of channels we know the following from [28,
Theorem 3]:

There exists an algorithm which is universal on the set
C0 (X , X )K . Below, this universal discrete denoising algorithm (UDDA) is described.
Algorithm 1 (UDDA: Universal discrete denoising algorithm).
The following steps produce the desired estimate x̂n for xn :
1) Input is (yij )n,K
i,j=1 .
2) Calculate q̂(⋅) ∶= n1 N (⋅∣(y1 , . . . , yK )) ∈ P(X K ).
3) Run the DCA algorithm [17] (see Definition 9 below)
with input q̂ to find stochastic matrices V1 , . . . , VK ∈
C(X , X ) and r ∈ P(X ).
4) Find the minimal clairvoyant ambiguous recovery T for
(r, V1 , . . . , VK ).

Theorem 11. Let X = Y1 = Y2 {0, 1} and K = 2. Let A, C ∈
C0 (X , Y1 ) and B, D ∈ C0 (X , Y2 )be BSCs and p, r ∈ P> (X ).
The four equations
∑ a(y1 ∣x)b(y2 ∣x)p(x) = ∑ c(y1 ∣x)d(y2 ∣x)r(x)

x∈X

4

x∈X

(18)

(one for each choice of y1 , y2 ∈ {0, 1}) have exactly the
following two families of solutions: either A = C, B = D
and p = r, or A = C ○ F, B = D ○ F, p = F(r).

When treating BSCs, it turns out that a universal algorithm
(called BUDDA in the following) may be defined based on
analytical formulas rather than outcomes of an optimisation
procedure such as in the definition of UDDA. The core of this
approach is the content of the following theorem.

Since our goal now is to understand the intricacies of
uniform universality, let us for the moment assume that UDDA
is uniformly universal. Taking into account the content of
Theorem 11, this might lead one to conclude that it is already
universal for the set of invertible BSCs and K = 2. That this
is not the case can be seen as follows: Let p ∈ X be such
that p(0) = p(1) = 1/2; this is the input distribution explicitly
excluded in Theorem 11. Then (see the appendix for a proof)
we get the output distribution defined by
q(x1 , x2 ) = p(x1 )c(x2 ∣x)

∀x1 , x2 ∈ {0, 1},

Theorem 13. Let X = {0, 1} and K ≥ 2. There exists
a function fK ∶ P(X K ) → [0, 1] such that the following
holds: If p ∈ P> (X ), B1 , . . . , BK ∈ C(X , X ) are binary
symmetric channels and q ∈ P(X K ) is the output distribution of the dependent component system (p, B1 , . . . , BK ) and
q1 , . . . , qK ∈ P(X ) denote the marginals of q on the respective
alphabets, then

(19)

p(0) =

where the number c(0∣0) is given by c(0∣0) = 1 − a(0∣0) −
b(0∣0) + 2 ⋅ a(0∣0) ⋅ b(0∣0). Obviously, there is a large number
of channels A and B leading to the same channel C, so that
UDDA cannot choose the correct one uniquely. This is also
reflected in Fig. 1.

δ11

The explicit nature of Theorem 13 (the definition of fK is
the content of its proof) allows us to develop error bounds
in the determination of p, when instead of the correct q an
estimate q̂ is used for the calculation. This in turn makes it
possible to prove Theorem 12 based on the following definition
of BUDDA.

δ01

Algorithm 2. BSC-UDDA To any pair r, s ∈ P({0, 1} such
that r↓ (0) < s↓ (0), we let b(r, s) ∶= (s + r − 1)/(2s − 1) be the
parameter such that a BSC B with b(0∣0) = b(r, s) satisfies
B(s) = r.
The following steps produce the desired estimate x̂n for xn
when K ≥ 3:

δ11

δ10

δ10

1)
2)
3)
4)

δ01

Fig. 1: Output distributions q parameterised by the BSC
parameters b1 (0∣0) and b2 (0∣0) for p(1) = 0.45 (left) and
p(1) = 1/2 (right). The geometric shape of the set of output
distributions already hints at the fact that it is not possible to
retrieve b1 (0∣0) and b2 (0∣0) from q. Cf. [17, Fig. 3].

5)
6)

Fortunately, it is enough to go to K = 3 and the following
still holds.
Theorem 12. Let K ≥ 3 and d be a distortion measure on
X × X . Let B = (B1 , . . . , BK ) be taken from the set {B ∶ B
is a BSC with b(0∣0) ≠ 1/2}K , and p ∈ P(X ). The uniform
resolution of W with respect to p is
R(p, W) = dMCA (p, W).

(21)

The mapping q ↦ p(0) is henceforth denoted EK .

δ00

δ00

1/K
∣ ∏K
1
i=1 (1 − 2 ⋅ qi (0))∣
(1 +
).
2
fK (q)

7)
8)

(20)
9)

There is an algorithm that is uniformly universal
on the set of invertible binary symmetric channels
{B ∶ B BSC with b(0∣0) ≠ 12 }.

Input is (yij )n,K
i,j=1 .
Calculate q̂(⋅) ∶= n1 N (⋅∣(y1 , . . . , yK )) ∈ P(X K ).
Calculate p̂ = EK (q̂).
Let i ∈ {0, 1} be the number such that N (y1n ∣i) >
N (y1n ∣i ⊕ 1) where ⊕ is addition modulo two. Without
loss of generality we assume in the following description that i = 0. Calculate the conditional distribution
q̂(⋅∣y1 = 0) ∈ P(X K−1 ).
If ∥p̂−π∥ > mini ∥q̂i (⋅∣y1 = 0)−π∥, set b̂i (0∣0) ∶= b(q̂i , p̂).
If ∥p̂ − π∥ < mini ∥q̂i (⋅∣y1 = 0) − π∥, calculate p̂1 ∶=
EK−1 (q̂(⋅∣y1 = 0) and p̂2 ∶= EK−1 (q̂(⋅∣y2 = 0). Then,
set b̂i (0∣0) ∶= b(q̂i (⋅∣y1 = 0), p̂1 ) for i = 2, . . . , K and
b̂1 (0∣0) = b(q̂i (⋅∣y2 = 0), p̂2 .
Find the minimal clairvoyant ambiguous recovery T for
(p̂, B̂1 , . . . , B̂K ).
For each i ∈ [n], apply the MCA decoder to the
sequence (yi1 , . . . , yiK ). This generates a sequence x̂n =
x̂1 . . . x̂n .
Output x̂n .

As explained earlier, the fifth and sixth step in the algorithm
allows one to reliably deal with those situations where p ≈ π.
Note that either of the two procedures may fail: the one in
step five if p ≈ π, the one in step six if p(0) = 1 − a1 . Luckily
however, in the limit of n → ∞ it is not possible that both
conditions are fulfilled. The fact that one output of the system
is used to create a bias explains why at least three copies are
needed.

The intuition behind the proof of this result is inspired by
the following observation: If K = 3 then the distribution of X
given X1 is not uniform anymore. Thus, conditioned on the
outcome of the first observed variable being e.g. a 0, we can
use the content of Theorem 11 to determine b2 (0∣0), b3 (0∣0)
and B1 (p) (note that B1 (p) = p holds).
5

X
Y1

Y3

Y2

Fig. 5: K = 7. Left: denoised image; right: denoised and
inverted for easier comparison with the original.

Fig. 2: Dependent component system with three outputs. Solid
arrows denote information flow in the original model. Dashed
arrows denote information flow when instead of the ”hidden
variable“ X the first visible alphabet Y1 is treated as input
to a dependent component system which then has only two
outputs, Y2 , Y3 .

Fig. 6: K = 10. Left: denoised image; right: denoised and
inverted for easier comparison with the original.
This is especially important in the light of findings such as [22]
which demonstrate the instability of contemporary algorithms
for fitting of tensor models.

VI. P ROOFS
Proof of Theorem 7. Let the empirical distribution of the output pixels produced in step 2 of the algorithm be q̂ ∈ P(X K )
and ε > 0. Application of the Chernoff-Hoeffding bound [29]
yields

V. S IMULATION R ESULTS
Here we present simulations with a sample picture (a part
of Leonardo da Vinci’s Mona Lisa, Fig. 3), distorted by ten
different BSCs.

K

P (∥q̂ − (⊗ Wj ) p(K) ∥ ≤ ε) ≥ 1 − 2L 2−2nε .
K

2

(22)

j=1

This implies that step 2 of the algorithm produces a distribution which is, with arbitrarily high accuracy and probability
converging to 1 as n tends to infinity and independently of the
(K)
type of xn , close to the distribution (⊗K
. Based
j=1 Wj ) p
on this estimate, we know by simple application of the triangle
inequality that the function E ∶ P(X K ) → P ↓ (X K ) defined
by

Fig. 3: The original image, a 200 × 200 pixels black-and-white
picture of a part of Leonardo da Vinci’s Mona Lisa.
The parameters of the ten BSCs are chosen as

K

E(q) ∶= (⊗ Vj ) r(K) ,

(0.71, 0.32, 0.41, 0.49, 0.48, 0.82, 0.81, 0.51, 0.84, 0.17).

(23)

j=1

The distorted images are shown in Fig. 4.

where (note that this next step is the implementation of the
DCA algorithm)
K

(r, V) = arg min ∥(⊗ Vj ) r↓(K) − q∥ ,
(r ↓ ,V)

(24)

j=1

satisfies
K
⎛
⎞
K
2
P ∥E(q̂) − (⊗ Wj ) p(K) ∥ ≤ 2ε ≥ 1 − 2L 2−2nε . (25)
⎝
⎠
j=1
1

As a consequence, we get
Fig. 4: The ten distorted versions of the original.

K
⎛
⎞
P ∥E(q̂) − (⊗ Wj ) p(K) ∥ ≤ n−ε/2 Ð→ 1
⎝
⎠
j=1
1

Using K = 7 if the noisy copies, the channel parameters
estimated by BUDDA are

(26)

as n → ∞. Take the function Θ′′ from Ref. [17, Theorem 1],
which for r ∈ P> (X ) and channels V1 , . . . , VK with invertible
transition probability matrices is defined as a one-sided inverse
to Θ:

(0.28, 0.67, 0.59, 0.51, 0.52, 0.17, 0.18),
and the algorithm returns the denoised image shown in Fig. 5.
Now we proceed to use all our K = 10 copies. Then,
BUDDA produces the following estimates for the channels:

K

Θ′′ ((⊗ Vj ) r(K) ) ∶= (r↓ , V ○ τ ),

(27)

j=1

(0.29, 0.68, 0.59, 0.51, 0.52, 0.17, 0.19, 0.49, 0.16, 0.83),

with τ ∈ SX being a permutation with the property r(x) =
r↓ (τ (x)) for all x ∈ X , and r↓ ∈ P ↓ (X ). According to Lemma

and the denoised image shown in Fig. 6.
6

15 below, Θ′′ is continuous if restricted to the set P> (X ).
Based on the above observation, see in particular eq. (26), Θ′′
satisfies

As a consequence, the restriction of Θ to P ↓ (X ) ×
C(X , X )K , which is invertible according to [17, Theorem 1],
is continuous as well.

P(∥Θ′′ ○ E(q̂) − (p, W)∥DCS ≤ δDCS (p, W, εn )) Ð→ 1

Lemma 15. There exists a function δDCS ∶ P ↓ (X ) ×
C(X , X )K × R≥0 → R≥0 , monotonic and continuous in the
real argument and with δDCS (r, W, 0) = 0, such that for
every two dependent component systems (s, W) and (r, V)
with r, s ∈ P ↓ (X ),

as n Ð→ ∞. Thus, with probability approaching 1 when n
tends to infinity and the image types N (⋅∣xn ) are in a small
enough vicinity of some distribution s′ , we know that our
estimate of the system (p, W) will be accurate up to an
unknown permutation, and small deviations incurred by the
properties of δDCS (p, W, ε). According to Lemma 16, the
minimum clairvoyant ambiguous recovery computed based on
the estimated system Θ′′ ○ E(q̂) is asymptotically optimal
for the true system (p, W). Using the Chernoff-Hoeffding
inequality [29], we can prove that application of the MCA
decoder separately to each letter yi1 , . . . , yiK yields a sequence
x̂n with the property n−1 ∑ni=1 d(τ (xi ), x̂i ) < D with high
probability for every D > dM CA (p, W). Thus a look at (2)
finishes the proof.

(30)

∥(s, W) − (r, V)∥DCS ≤ δDCS (r, V, ε).

(31)

min ∑ p′ (x)d(x, x′ )c′ (Tτ (x′ ) ∣x)

(28)

(32)

τ ∈SX x,x′

≥ dMCA (p, C) − 2∣X ∣∣Y∣ max d(x, y).
x,y

Proof. We use a telescope sum identity: for arbitrary matrices
A1 , . . . , AK+1 and B1 , . . . , BK+1 we have

(33)

Proof. The prerequisites of the lemma imply ∣p(x)w(y∣x) −
p′ (x)w′ (y∣x)∣ ≤ ε for all x, y ∈ X , Y. Thus

A1 ⋅ . . . ⋅ AK+1 − B1 ⋅ . . . ⋅ BK+1

min ∑ p′ (x)d(x, x′ )c′ (Tτ (x′ ) ∣x)

(29)

(34)

τ ∈SX x,x′

≥ min ∑ p(x)d(x, x′ )c(Tτ (x′ ) ∣x)

i=1

τ ∈SX x,x′

We apply it to the channel matrices and input distributions as
follows. Let Ai ∶= 1⊗(i−1) ⊗Vi ⊗ 1⊗(n−i) , Bi ∶= 1⊗(i−1) ⊗Wi ⊗
1⊗(n−i) for i ∈ [K]; furthermore AK+1 ∶= r(K) , BK+1 ∶= s(K) ,
where we interpret probability distributions on an alphabet as
channels from a set with one element. Now we have

− 2∣X × Y∣ max d(x, y),
x,y

(35)

concluding the proof.
Proof of Theorem 13. Let X = {0, 1}, B1 , . . . , BK ∈
C0 (X , X ) be BSCs and p ∈ P(X ). Let qi ∶= Bi (p). Then
the following equation holds true:

(K)
(K)
∥(⊗K
∥
− (⊗K
i=1 Vi )r
i=1 Wi )s

= ∥A1 ⋅ . . . ⋅ AK+1 − B1 ⋅ . . . ⋅ BK+1 ∥

1/K

K+1

p(0) =

= ∥ ∑ A1 ⋯Ai−1 (Ai − Bi )Bi+1 ⋯BK+1 ∥
i=1
K+1

j=1

Lemma 16. Let p, p′ ∈ P(X ) and C, C ′ ∈ C(X , Y). Let d be
any distortion on X × X and T , T ′ be the MCA decoders
for (p, C) and (p′ , C ′ ), respectively. If ∥p − p′ ∥ ≤ ε and
∥C − C ′ ∥F B ≤ ε, then the minimal clairvoyant ambiguous
distortions satisfy

That is, Θ is continuous with respect to ∥ ⋅ ∥DCS .

= ∑ A1 ⋅ . . . ⋅ Ai−1 ⋅ (Ai − Bi )Bi+1 ⋅ . . . ⋅ BK+1 .

j=1

Proof. Under the premise of the lemma, the function Θ is
both continuous on a connected domain (as a consequence of
Lemma 14) and invertible (as a consequence of [17, Thm. 1]).
Thus, the inverse of Θ is continuous, implying the claim.

(K)
Lemma 14. Set Θ(s, W) ∶= (⊗K
. Then for every
j=1 Wj ) s
two dependent component systems (r, V) and (s, W), we have

K+1

K

implies

We now state and prove the lemmas required above.

∥Θ(r, V) − Θ(s, W)∥ ≤ ∥(r, V) − (s, W)∥DCS .

K

∥(⊗ Wj ) s(K) − (⊗ Vj ) r(K) ∥ ≤ ε

FB

K
1⎛
1 − 2 ⋅ qi (0)
1 + ∏∣
∣
2⎝
1 − 2 ⋅ bi
i=1

⎞
,
⎠

(36)

where bi ∶= bi (0∣0), i = 1, . . . , K. It turns out that, for even K,
the expression in the denominator can be derived as a function
of q = (B1 ⊗ . . . ⊗ BK )p(K) in a very natural way. Set

≤ ∑ ∥A1 ⋯Ai−1 (Ai − Bi )Bi+1 ⋯BK+1 ∥F B
i=1
K+1

= ∑ ∥V1 ⊗ ⋯ ⊗ Vi−1 ⊗ (Vi − Wi ) ⊗ Wi+1 ⊗ ⋯ ⊗ WK+1 ∥F B

fK (q) ∶= ∑ sgn(τ )q(τ1 (1), . . . , τK (1)),

i=1
K+1

(37)

τ ∈S2K

= ∑ ∥Vi − Wi ∥F B

where S2K is the K-fold cartesian product of the set S2 of
permutations on {0, 1} with itself. Note that, given empirical
data as a string y, fK ( n1 N (⋅∣y)) can be calculated for even
K as

i=1
K

= ∑∥Vi − Wi ∥F B + ∥r(K) − s(K) ∥
i=1

= ∥(r, V) − (s, W)∥DCS ,

n

K

fK ( n1 N (⋅∣y)) = ∑(−1)∑j=1 yij .

concluding the proof.

i=1

7

(38)

xn ∈ {0, 1}n . This implies that probabilities are calculated with
respect to the distribution on the K-fold product {0, 1}K that
is defined as the marginal on Y K of

This formula may be particularly useful for calculating fK in
an online fashion, while data is being retrieved from a source.
Going further, we see that it holds (with p ∶= p(0) and p′ ∶=
p(1):

K
1
P(Y = y1 , . . . , yK , X = x) = ∏ bj (yj ∣x) N (x∣xn ).
n
j=1

K

fK (q) = ∑ sgn(τ )p ⋅ ∏ bi (τi (0)∣0)
τ ∈S2K

i=1

K

Since it simplifies notation, all following steps are however
performed as if p ∈ P({0, 1}) was an arbitrary (meaning that
it is not necessarily an empirical distribution) parameter of the
system.
To every such parameter p, there is a set of associated distributions pX (⋅∣Yi = 0), i = 1, . . . , K, which are calculated from
(50) as pX (X = x∣Yi = 0) = P(X = x, Yi = 0) ⋅ P(Yi = 0)−1
if P(Yi = 0) > 0, and pX (X = x∣Yi = 0) = δ1 (x) otherwise.
Since BUDDA always assumes that N (0∣xn ) ≥ N (1∣xn ), this
latter choice is justified.
By definition of EK in Theorem 13, it is clear that EK
is continuous. Thus, from the Chernoff-Hoeffding bound (see
e.g. [30, Thm. 1.1]) we have that for every ε > 0 there is
an N1 = N1 (ε, B1 , . . . , BK ) ∈ N such that, if n ≥ N1 , the
probability of the set S0 ∶= {y n ∶ ∥EK (q) − p↓ ∥1 ≤ ε} satisfies

i=1

P(S0 ) ≥ 1 − ν(n)

K

′

+ ∑ sgn(τ )p ⋅ ∏ bi (τi (0)∣1)
τ ∈S2K

(39)

i=1

K

= p ∑ sgn(τ ) ∏ bi (τi (0)∣0)
τ ∈S2K

i=1

K

+ p′ ∑ sgn(τ ) ∏ bi (τi (0)∣1)
τ ∈S2K

(40)

i=1

K

= p ∑ sgn(τ ) ∏ bi (τi (0)∣0)
τ ∈S2K

i=1

K

+ p′ ∑ sgn(τ ○ F⊗4 ) ∏ bi (τi ○ F(0)∣1)
τ ∈S2K

(41)

i=1

= p ∑ sgn(τ ) ∏ bi (τi (0)∣0)
τ ∈S2K

τ ∈S2K

(42)

i=1

K

= p ∑ sgn(τ ) ∏ bi (τi (0)∣0)
i=1

K

+ p′ ∑ sgn(τ ) ∏ bi (τi (0)∣0)
τ ∈S2K

(43)

i=1

Si ∶= {y n ∶ ∥EK−1 (q(⋅∣yi = 0)) − pX (⋅∣yi = 0)∥1 ≤ ε},

K

= ∑ sgn(τ ) ∏ bi (τi (0)∣0),
τ ∈S2K

(44)

P(∩K
i=0 Si ) ≥ 1 − (K + 1)ν(n).

so it does not depend on the distribution p at all. Going further,
we see that
(45)

i=1

K

= ∏ ∑ sgn(τ )ai (τ (0)∣0)

(46)

i=1 τ ∈S2
K

= ∏(ai − 1 + ai )

(47)

= ∏(1 − 2ai ).

(48)

i=1
K
i=1

For uneven K, K ≥ 3, the above calculations demonstrate one
can define fK by
K

fK (q) ∶= (∏ fK−1 (q≠i ))

(53)

It is critical to note here that we use one and the same function
ν over and over again. Theoretically, we would need to update
the constant c at each use. We do however step away from such
explicit calculation, since any positive c′ < c that would arise
e.g. from setting c′ ∶= min{c1 , . . . , cK } is sufficient for our
proof. Thus we use one and the same constant repeatedly in
what follows.
As an outcome of the calculation of p via application
of EK to q, one is in principle able to obtain an estimate
of the channels B1 , . . . , BK . However, the precision of this
estimate depends critically on the distance ∥p − π∥ and thus
any algorithm using only such estimate cannot be uniformly
universal because the equality p = π may hold. Define

K

τ ∈S2K

(52)

we have then

i=1

fK (q) = ∑ sgn(τ ) ∏ ai (τi (0)∣0)

(51)

for some function ν ∶ N → (0, 1) of the form ν(n) = 2−nc
for some constant c > 0 depending only on the channels
B1 , . . . , BK . Obviously, ν converges to 0 when n goes to
infinity. The fact that this convergence is exponentially fast
makes it possible to prove that a larger number of events has
asymptotically the probability one by repeated union bounds.
Setting

K

+ p′ ∑ sgn(τ ) ∏ bi (τi (1)∣1)

τ ∈S2K

(50)

1/K

E ∶= {y n ∶ ∥EK (q̂) − π∥ > min ∥EK−1 (q̂(⋅∣yi = 0)) − π∥}
i

(49)

(54)

i=1

where q≠i is the marginal of q on all but the i-th alphabet.
This proves the Theorem.

and
F ∶= {y n ∶ ∥EK (q̂) − π∥ ≤ min ∥EK−1 (q̂(⋅∣yi = 0)) − π∥}.

Proof of Theorem 12. In the remainder, it is assumed that p
is the (empirical) distribution of the sought after data string

i

(55)
8

Observe that the distribution of X given X1 = 0 satisfies
P(X = 0∣Y1 = 0) =

p(0) ⋅ b1
.
p(0) ⋅ b1 + (1 − p(0))(1 − b1 )

A PPENDIX A: A DDITIONAL P ROOFS
Proof of eq. (19). Let A, B ∈ C0 ({0, 1}, {0, 1}) be BSCs and
p = π. Then the following holds true:

(56)

1
1
(A ⊗ B)p(2) = (A ⊗ B) ∑ e⊗2
i
2
i=0

The left hand side in (56) takes on the value b1 ≠ 1/2 at
p(0) = 1/2, and the value 1/2 at p(0) = 1 − b1 . Since by
assumption we have that bi ≠ 1/2 for all i = 1, . . . , K it is
clear that, asymptotically, either S1 or S2 has large probability.
Thus, depending on the distribution p, we have either
P(E) ≥ 1 − ν(n)

(57)

1
1
= (A ○ B T ⊗ 1) ∑ e⊗2
i
2
i=0

(60)

1
1
= (C ⊗ 1) ∑ e⊗2
i
2
i=0

(61)

where C = A ○ B T . Since B T = B for a BSC, this implies
C = A ○ B, and especially that

or else

c = ab + (1 − a)(1 − b)
P(F ) ≥ 1 − ν(n),

(59)

= 2ab + 1 − a − b,

(58)

(62)
(63)

where we used the abbreviation c ∶= c(0∣0), b ∶= b(0∣0) and
a ∶= a(0∣0).

but always P(E ∩ F ) < ν(n). This reasoning forms the basis
of step 5) of BUDDA. If y n ∈ S2 , the proof of Theorem 7
shows that BUDDA succeeds with probability lower bounded
′
by 1 − 2−nc for some c′ > 0 depending only on the channels
B1 , . . . , BK . If y n ∈ S3 , then one introduces a bias by
viewing the outcome Y1 as the source of the system, and
then conditioning on the outcomes of Y1 : Delete all rows in
y n = (yi,j )K,n
i,j=1 with indices j such that y1,j = 1. The resulting
empirical distribution q̂(⋅∣y1 = 0) serves as input to EK−1 .
It produces a dependent component system (b̂2 , . . . , b̂K , p̂0 ).
Performing the same step with k set to two yields a second
such system with an additional value for b̂1 .
Thus steps 1) to 6) of BUDDA succeed with probability
lower bounded by 1 − (K + 4)ν(n), independently of the
sequence xn . The remaining steps of the proof are identical
to those in the proof of Theorem 7. They are based on
further application of the union bound and the fact that
limn→∞ M ⋅ 2−nc = 0 for every M ∈ N.

Lemma 18. Let W ∈ C(X , Y). Given x ∈ X , let Yx denote
the random variable with distribution w(⋅∣x). Let T be an
estimator achieving Λ = ∑x p(x)w(Tx ∣x). If xn has type
p, then for every possible input string xn the letter-by-letter
application of T to the output sequences of W ⊗n given input
xn has the following property:
P (∣

1 n
−2ε2 n
.
∑ δ(xi , T (Yxi )) − Λ∣ ≥ ε) ≤ 2 ⋅ 2
n i=1

(64)

Proof. The expectation of the function Φ defined by Φ(y n ) ∶=
n
1
δ(xi , T (Yxi )) is calculated as
n ∑i=1
EΦ = ∑ p(x) ∑ δ(x, y)w(T (y)∣x) = Λ.
x

(65)

y

Thus by Hoeffding’s inequality [30, Thm. 1.1] or alternatively
McDiarmid’s inequality [31],

Remark 17. A more optimized choice of estimator arises when
one picks instead of the first and the second system those two
systems for which ∥EK−1 (q̂(⋅∣yi = 0))−π∥ takes on the largest
and second largest value, respectively.

P (∣

1 n
−2ε2 n
.
∑ δ(xi , T (Yxi )) − Λ∣ ≥ ε) ≤ 2 ⋅ 2
n i=1

(66)

Remark 19. As a consequence of this lemma, an algorithm
that knows p and W but not xn can calculate the MCA
decoder T corresponding to p and W , after which it applies
the MCA decoder in order to obtain the best possible estimate
on xn .

VII. C ONCLUSIONS
We have laid the information theoretic foundations of universal discrete denoising and demonstrated the in-principle
feasibility of our new algorithm UDDA based on discrete
dependent component analysis. We proved that the resolution
equals the minimal clairvoyant ambiguous distortion. We
conjecture that, in fact, the same distortion can be achieved
uniformly in the input distribution, i.e. that the equality
R(p, W) = dM CA (p, W) holds, but have only been able to
prove this for a restricted class of models and with some slight
modifications to UDDA.

Acknowledgments. The present research was funded by the
German Research Council (DFG), grant no. 1129/1-1, the
BMWi and ESF, grant 03EFHSN102 (JN), the ERC Advanced
Grant IRQUAT, the Spanish MINECO, projects FIS201340627-P and FIS2016-86681-P, with the support of FEDER
funds, and the Generalitat de Catalunya, CIRIT project 2014SGR-966 (AW and JN).
9

R EFERENCES

[15] A. Buades, B. Coll, and J. M. Morel, “A non-local algorithm for
image denoising,” in Proc. 2005 IEEE Computer Society Conference
on Computer Vision and Pattern Recognition (CVPR’05), vol. 2, June
2005, pp. 60–65.
[16] ——, “Image denoising methods. a new nonlocal principle,” SIAM
Review, vol. 52, no. 1, pp. 113–147, Feb 2010.
[17] J. Nötzel and W. Swetly, “Deducing truth from correlation,” IEEE Trans.
Inf. Theory, vol. 62, no. 12, pp. 7505–7517, Dec 2016.
[18] J. B. Kruskal, “More factors than subjects, tests and treatments: an
indeterminacy theorem for canonical decomposition and individual differences scaling,” Psychometrika, vol. 41, no. 3, pp. 281–293, Sep 1976.
[19] E. Acar and B. Yener, “Unsupervised multiway data analysis: A literature survey,” IEEE Transactions on Knowledge and Data Engineering,
vol. 21, no. 1, pp. 6–20, Jan 2009.
[20] A. C. Rencher and W. F. Christensen, Methods of Multivariate Analysis.
Wiley Series in Probability and Statistics, 2012.
[21] A. Anandkumar, R. Ge, D. Hsu, S. M. Kakade, and M. Telgarsky,
“Tensor decompositions for learning latent variable models,” J. Machine
Learning Res., vol. 15, no. 12, pp. 2773–2832, 2014.
[22] G. Tomasi and R. Bro, “A comparison of algorithms for fitting the
parafac model,” Computational Statistics & Data Analysis, vol. 50, pp.
1700–1734, Apr 2006.
[23] J. Kossaifi, Y. Panagakis, and M. Pantic, “Tensorly: Tensor learning in
python,” ArXiv e-prints, arXiv:1210.7559, Oct 2016.
[24] V. Prabhakaran, D. Tse, and K. Ramachandran, “Rate region of the
quadratic gaussian CEO problem,” in International Symposium onInformation Theory, 2004. ISIT 2004. Proceedings., June 2004, pp. 119–.
[25] T. Berger and Z. Zhang, “On the CEO problem,” in Proceedings of
1994 IEEE International Symposium on Information Theory, Jun 1994,
pp. 201–.
[26] A. J. G. A. Kipnis, S. Rini, “Compress and estimate in multiterminal
source coding,” ArXiv e-prints, arXiv:1602.02201, 2017.
[27] G. M. Gemelos, S. Sigurjonsson, and T. Weissman, “Universal Minimax Discrete Denoising Under Channel Uncertainty,” IEEE Trans. Inf.
Theory, vol. 52, no. 8, pp. 3476–3497, Aug 2006.
[28] J. Nötzel and C. Arendt, “Using dependent component analysis for
blind channel estimation in distributed antenna systems,” in 2016 IEEE
Global Conference on Signal and Information Processing (GlobalSIP),
Dec 2016, pp. 1116–1121.
[29] W. Hoeffding, “Probability Inequalities for Sums of Bounded Random
Variables,” J. Amer. Stat. Assoc., vol. 58, no. 301, pp. 13–30, Mar 1963.
[30] D. D. Dubhashi and A. Panconesi, Concentration of Measure for the
Analysis of Randomized Algorithms. Cambridge University Press, 2012.
[31] C. McDiarmid, On the method of bounded differences, ser. London
Mathematical Society Lecture Note Series. Cambridge University Press,
1989, pp. 148–188.

[1] T. Weissman, E. Ordentlich, G. Seroussi, S. Verdú, and M. J. Weinberger,
“Universal discrete denoising: known channel,” IEEE Trans. Inf. Theory,
vol. 51, no. 1, pp. 5–28, Jan 2005.
[2] E. Ordentlich, G. Seroussi, and M. Weinberger, “Modeling enhancements in the DUDE framework for grayscale image denoising,” in Proc.
2010 IEEE Information Theory Workshop (ITW 2010, Cairo), Jan 2010,
pp. 1–5.
[3] G. Gemelos, S. Sigurjonsson, and T. Weissman, “Universal minimax discrete denoising under channel uncertainty,” in Proc. 2004 International
Symposium on Information Theory (ISIT 2004), June 2004, p. 199.
[4] G. M. Gemelos, S. Sigurjonsson, and T. Weissman, “Algorithms for
discrete denoising under channel uncertainty,” IEEE Trans. Signal Proc.,
vol. 54, no. 6, pp. 2263–2276, June 2006.
[5] G. Motta, E. Ordentlich, I. Ramirez, G. Seroussi, and M. J. Weinberger,
“The iDUDE Framework for Grayscale Image Denoising,” IEEE Trans.
Image Proc., vol. 20, no. 1, pp. 1–21, Jan 2011.
[6] ——, “The DUDE framework for continuous tone image denoising,” in
Proc. 2005 IEEE International Conference on Image Processing, vol. 3,
Sept 2005, pp. III–345–8.
[7] E. Ordentlich, K. Viswanathan, and M. J. Weinberger, “Twice-universal
denoising,” IEEE Trans. Inf. Theory, vol. 59, no. 1, pp. 526–545, Jan
2013.
[8] C. D. Giurcaneanu and B. Yu, “Efficient algorithms for discrete universal
denoising for channels with memory,” in Proc. 2005 International
Symposium on Information Theory (ISIT 2005), Sept 2005, pp. 1275–
1279.
[9] K. Viswanathan and E. Ordentlich, “Lower limits of discrete universal
denoising,” in Proc. 2006 IEEE International Symposium on Information
Theory (ISIT 2006), July 2006, pp. 2363–2367.
[10] Y. Cao, Y. Luo, and S. Yang, “Image Denoising with Gaussian Mixture
Model,” in Proc. 2008 Congress on Image and Signal Processing (CISP
’08), vol. 3, May 2008, pp. 339–343.
[11] P. Milanfar, “A tour of modern image filtering: New insights and methods, both practical and theoretical,” IEEE Signal Processing Magazine,
vol. 30, no. 1, pp. 106–128, Jan 2013.
[12] Y. Shih, V. Kwatra, T. Chinen, H. Fang, and S. Ioffe, “Joint noise
level estimation from personal photo collections,” in Proc. 2013 IEEE
International Conference on Computer Vision, Dec 2013, pp. 2896–
2903.
[13] J. Mairal, M. Elad, and G. Sapiro, “Sparse representation for color image
restoration,” IEEE Trans. Image Proc., vol. 17, no. 1, pp. 53–69, Jan
2008.
[14] S. Jalali and H. V. Poor, “Universal compressed sensing,” in Proc. 2016
International Symposium on Information Theory (ISIT 2016), July 2016,
pp. 2369–2373.

10

