MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

12 edited title; edited tags

# Decomposing max-convolution of sum of functions ?

11 added 74 characters in body; deleted 1 characters in body

Hello.

$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$) :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? 10 deleted 3 characters in body Hello.$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 $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}, 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$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?