从行和列的总和重建矩阵 [英] reconstruct a matrix from its row and column sums

问题描述

获取一个n * m矩阵，其中填充了0到1之间的浮点值.

Take a n*m matrix filled with floating point values between 0 and 1.

示例:

0    0.5  0    0
0    0.5  1    0.4
0.2  1    0.3  0
0    1    0    0

目标是重建此矩阵中的值.

The goal is to reconstruct the values in this matrix.

我无权访问此矩阵，所以一开始我不知道其任何值. 有一个函数可以计算每个值calc_value(m,n).因此，重构此矩阵的一种简单方法是为每个值调用calc_value(m,n).
但是调用此函数是一项非常昂贵的操作，因此我想尽可能少地调用此函数.

I do not have access to this matrix, so I do not know any of its values at the beginning. There is a function to calculate each value, calc_value(m,n). So a simple way to reconstruct this matrix is to call calc_value(m,n) for each value.
But calling this function is a very expensive operation, so I would like to call this function as few times as possible.

我知道矩阵中所有值的总和，以及每一行和每一列中的值之和. (计算这些总和并不比调用calc_value(m,n)更昂贵)

I know the total sum of all values in the matrix, and the sum of values in each individual row and column. (calculating each of these sums is no more expensive than a call to calc_value(m,n))

使用行和列的总和作为附加信息，如何用对calc_value()的调用次数最少的方法填充矩阵中的所有值?

Using the row and column sums as additional information, how can I fill all values in the matrix with the least amount of calls to calc_value()?

是否可以用少于O(n*m)个电话?

Is it possible with fewer than O(n*m) calls?

该矩阵还有一个附加的约束可能会有所帮助:每行和每一列中的值都是单调递增到最大值，然后在该最大值之后单调递减.因此，单行可能看起来像这样:

There is one additional constraint for the matrix that may help: the values in each row and column will be be monotonous increasing up to a maximum, then monotonous decreasing after that maximum. So a single row could look like this:

0 0.5 0.5 1 1 0.5 0

但不是这样:

0 1 0 1 0 1 

例如不允许有多个不同的局部最大值

e.g. more than one distinct local maximum is not allowed

这是我自己的尝试状态:

This is the status of my own attempts:

到目前为止，我发现了以下不平等现象.对于矩阵M(n，m)的给定值:

So far I discovered the following inequalities. For a given value of the matrix M(n,m):

M(n,m) <= Min ( sum_of_row_n, sum_of_column_m)
M(n,m) >= sum_of_row_n - sum_of_all_columns_except_m
M(n,m) >= sum_of_column_m - sum_of_all_rows_except_n

但是，除了一些琐碎的情况之外，这些不等式不能提供足够的信息来推导M(n，m)值.

But these inequalities do not provide enough information to deduce the value M(n,m), except for some trivial cases.

推荐答案

根据您的描述，您的矩阵似乎具有m * n个自由度.范围和单调性约束不会降低自由度.每个总和(行，列，总数)都会除去一个自由度-直到达到(m-1)*(n-1)度. (由于所有行总和与所有列总和等于总和，因此您只能利用这些约束的m + n-1).

From what you describe it seems that your matrix has m*n degrees of freedom. The range and monotonicity constraints do not reduce the degrees of freedom. Each sum (row, column, total) removes one degree of freedom - until (m-1)*(n-1) degrees have been reached. (Since the sum of all row sums and the sum of all column sums equals the total sum you can only exploit m+n-1 of these constraints).

因此，根据给定的信息，您可以做的是:

So with the given information all you can do is:

计算矩阵元素a_ij，1 ＜＝ i ＜i. m，1< = j< n与calc_value(i，j)
1. 通过行/列总和属性计算每个行/列和a_mn的缺失元素

1. calculate the matrix elements a_ij, 1 <= i< m, 1 <=j < n with calc_value(i,j)
2. compute the missing element of each row/column and a_mn via the row/col sum properties

这篇关于从行和列的总和重建矩阵的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！