Take a n*m matrix filled with floating point values between 0 and 1.
Example:
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.
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.
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)
)
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()
?
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
but not like this:
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:
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
But these inequalities do not provide enough information to deduce the value M(n,m), except for some trivial cases.