3
$\begingroup$

Suppose I have a array of real numbers with $n$ rows and $m$ columns. I want to consider possible ways of dividing that array into rectangular regions of three different possible types: a constant value over the entire region, a linear gradient across rows or a linear gradient across columns.

For example, the array

$\begin{bmatrix}1 & 2 & 3 & 10 \\ 1 & 2 & 3 & 12 \\ 4 & 4 & 4 & 14\end{bmatrix}$

can be decomposed into a horizontal gradient [1-3], a vertical gradient [10-14] and a constant region of value 4.

There are potentially many different ways to decompose any given array (in the extreme case, you can always divide it into $n$ by $m$ constant single-cell regions), so I'm interested in finding a 'simplest' solution (i.e. one with as few regions as possible.)

Has this problem been studied or is it related to another kind of problem that has been studied? It seems like it could be approached using some sort of tree representation where I start with all cells as individual constant regions, then combine them together under larger regions as long as they meet the desired constraints, then evaluate using some fitness function to decide whether it is an optimal (or at least 'good enough') decomposition.


Regarding the optimality constraint, I have some flexibility here, so I can choose a constraint that helps make the problem easier to solve. Ultimately the goal is to have a decomposition that appeals to human sensibilities of the 'patterns' present in the data, so my first thought is that minimizing the number of regions is probably a good constraint.

Some interesting boundary cases to consider:

$\begin{bmatrix}1 & 1 & 0 & 0 & 1 & 1 \\ 1 & 1 & 1 & 1 & 1 & 1 \\ 0 & 0 & 1 & 1 & 0 & 0\end{bmatrix}$

The preferred decomposition here would be three constant 2x2 regions of '1' and three constant regions of '0'. This is preferable to the alternate 6 region decomposition with three 2x2 '0-1' gradients and three constant '1' regions, as constant regions are preferable to gradients if the number of regions is the same.

$\begin{bmatrix}1 & 2 & 3 \\ 2 & 2 & 2 \\ 3 & 2 & 1\end{bmatrix}$

Due to symmetry, this can decompose into either horizontal or vertical gradients. I don't have any preference in this case for which should be chosen as the decomposition.

Regarding distribution of size, it's probably better to avoid at the minimum 1x2 gradients. Any array can be distributed arbitrarily into various single cell constant blocks and 1x2 gradient blocks, so this kind of interpretation is not particularly interesting. In the case where there are no other patterns in a region of the data, I'd rather treat it as single cells, as I can do some post-processing to extract these 'complex' regions and treat them as lookup tables.


Another case:

$\begin{bmatrix}1 & 1 & 2 & 3 & 4\\ 1 & 1 & 2 & 3 & 4\\ 1 & 1 & 2 & 2 & 2\\ 1 & 1 & 2 & 2 & 2\end{bmatrix}$

Here it would be preferable to take the 4x2 '1' region and 2x3 '2' region, with a 2x3 '2-4' gradient region. The alternative '1-4' gradient is worse because it requires splitting the '1' region into two different regions.

$\endgroup$
  • $\begingroup$ How do you define optimal solution? Should the optimal solution should have minimum number of decomposition? Does the distribution of the size of the decomposition matter as well etc. The reason I ask this is because given the optimality condition, greedy local approach might suffice. $\endgroup$ – Tushar Apr 16 '14 at 3:06
  • $\begingroup$ @Tushar, I've included some additional information in the question on optimality. I've thought about a greedy local appproach, perhaps trying to find gradients 1x3 or larger first and then decomposing the remainder into constant regions. $\endgroup$ – Dan Bryant Apr 16 '14 at 12:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.