Sign up ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.


$R, F_1, F_2, F_3$ are random (not-convex, not-concave) 2D matrices of size 100x100.
$R$ is a linear combination of $F_1, F_2, F_3$.

Explicitly, $R = w_1 F_1 + w_2 F_2 + w_3 F_3$ where $w_1, w_2, w_3$ are real numbers $ -1 \leq w_i \leq 1 $ (edit: if it makes analysis any easier, we can assume $0\leq w_i \leq 1$)

Now, max-convolution (also called morphological dilation) in our problem is defined as follows using $L_1$ and $L_2$ norms where $x$ and $y$ are indices for rows and columns of $R$, and ($dx$, $dy$) are deviations from specific ($x$, $y$):

$D_R(x,y) = \max_{dx,dy} \left( R(x+dx, y+dy) - d_1 |dx| - d_2 |dy| - d_3(dx)^2 - d_4(dy)^2 \right)$

The question here is if we can express the above max-convolution $D_R$ as weighted sum of max-convolutions of $F$ 's, namely, $D_{F_1}$, $D_{F_2}$, $D_{F_3}$.

For example, $D_R(x,y) = \tilde{w_1} D_{F_1}(x,y) + \tilde{w_2} D_{F_2}(x,y) + \tilde{w_3} D_{F_3}(x,y)$ for all $x$ and for all $y$.

The motivation for coming up with this problem is that we have a lot of $R$ matrices which can be written as linear combinations of $F_1, F_2, F_3$. Then the intuition is that we can save a lot of computations by running the expensive max-convolutions only three times (rather than thousand times) and then reconstruct $D_R$ from some weighted combinations of $D_{F_1}$, $D_{F_2}$, $D_{F_3}$.

I think the ingredients should be $D_{F_1}, D_{F_2}, D_{F_3}, F_1, F_2, F_3, w_1, w_2, w_3, d_1, d_2, d_3 $. Please note that the discount terms $d_1, d_2, d_3$ are included.

I'm not sure if this is a known problem because I couldn't find a similar result from google search. Does anyone have an idea on how to approach this decomposition problem? If there isn't any closed form decomposition, what would be a tight approximation?

share|cite|improve this question
Sorry, I do not get several points: What are $x$, $y$, $dx$ and $dy$? What are the $d_i$'s? What do you mean by "random" matrices (especially in the light that they seem to depend on $x$ and $y$)? – Dirk Sep 19 '11 at 6:13
Edited what $x,y,dx,dy$ are – Jackson Sep 19 '11 at 6:42
$x,y$ range from 1 to matrix height and width. $x+dx, y+dy$ also have the same support. – Jackson Sep 19 '11 at 8:50

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.