second order partial derivatives, given by:

![0_image_0.png](0_image_0.png)

=X

![0_image_1.png](0_image_1.png)

=X
∂λr i λ c j
The number of Lagrange multipliers to be optimized over, which is crucial for the computational cost of e.g. Newton iterations, is equal to m + n**. While this** is sublinear in the size of the data mn**, it is still a daunting number for practical**
sizes of databases. However, the computational and space complexity can often be further reduced, in particular when the numbers of distinct values of d r i and of d c j are small. Indeed, thanks to symmetry and convexity of L**, if** d r i = d r k for specific i and k **the corresponding optimal values of the Lagrange multipliers**
λ r i and λ r k **will be equal as well, and the same goes for the elements of** λ c**. In**
practice this allows one to drastically reduce the number of free variables, down to the sum of the number of distinct **expected row sums** d r i and the number of distinct **expected column sums** d c j
.

Especially for D = {0, 1}**, almost in all practical cases this allows for a**
massive reduction in computational complexity. The number of distinct row and column sums can be upper bounded in terms of the dimensions of D**, the** number of non-zero elements in D**, and the largest row and column sums in** D,
as quantified by the following Lemmas.

Lemma 1. In a binary matrix D ∈ {0, 1}
m×n**, the number of distinct row sums**
me is upper bounded by min(m, n + 1) **and the number of distinct column sums** ne is upper bounded by min(m + 1, n).

Proof. **Let us prove it for row sums only. Clearly the number of distinct row**
sums is bounded by the total number of rows m**. On the other hand, the** only possible values of the row sums are 0, 1, . . . , n, a total of n **+ 1 distinct**
values.

Lemma 2. In a binary matrix D ∈ {0, 1}
m×n with Pi,j D(i, j) = s **(i.e. with**
s ones), the number of distinct row sums me is upper bounded by √2s**, and the**
same holds for the number of distinct column sums ne.

Proof. **Let us prove this bound for the number of rows by contradiction. Assume**
that the number of different row sums is larger than √2s**. This means that the**