(e.g. Boyd and Vandeberghe, 2004). Combining this with Theorem 2 yields an overall worst-case complexity of at most O(
√s 3**) per iteration for Newton's**
method and at most O(s**) for first order methods such as gradient descent. The**
space complexity for Newton's method is determined by the size of the Hessian, such that it is bounded by O(s**) and thus of the order of the size of the database**
in sparse representation. For gradient-based or conjugate gradient methods, it is bounded by the size of the gradient O(
√s**). As we will see in the experiments,**
these results make the MaxEnt approach amenable for practical problems of very large scale.

The reader may be left with one concern: the fact that the MaxEnt **model**
is a product distribution of independent distributions for each D(i, j**) seems**
to suggest that parameters need to be stored for each of these m × n **element**
distributions. However, it should be pointed out that one does not need to store the value of λ r i + λ c j for each pair of i and j**. It suffices to store just the** λ r i and λ c j to compute the probabilities for any D(i, j**) in constant time. Hence, the**
space required to store the resulting model is O(m + n**), sublinear in the size of**
the data.

## 4 The Invariance Of The Maxent Matrix Distribution To Δ**-Swaps**

The MaxEnt models introduced in Sec. 3 are explicitly represented probability distributions. As a result, they are useful for defining analytically computable measures of interestingness, as outlined in Sec. 2.2, and we will demonstrate this by designing a concrete interestingness measure in Sec. 5.2. Still, it is instructive to point out some relations between our MaxEnt models and the previously proposed swap randomization approaches and generalizations.

## 4.1 Δ**-Swaps: A Randomization Operation On Matrices**

First, let us generalize the definition of a swap as follows.

Definition 1 (δ-swap). Given an m × n matrix D, a δ-swap for rows i, k and columns j, l is the operation that adds a fixed number δ to D(i, k) and D(**j, l**) and subtracts the same number from D(i, l) and D(**j, k**).

Of course, for a δ-swap to be useful, it must be ensured that D(i, j) +
δ, D(k, j) − δ, D(i, l) − δ, D(k, l) + δ ∈ D. We will refer to such δ**-swaps as**
allowed δ**-swaps.**
Definition 2 (Allowed δ-swap). A δ-swap for rows i, k and columns j, l **is said**
to be allowed for a given matrix D over the domain D iff D(i, j) + δ, D(**k, j**) − δ, D(i, l) − δ, D(k, l) + δ ∈ D.

Clearly, an allowed δ**-swap leaves the row and column sums invariant. The**
following Theorem is more interesting.