Decomposing max-convolution of sum of functions ? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-20T19:53:08Z http://mathoverflow.net/feeds/question/75820 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/75820/decomposing-max-convolution-of-sum-of-functions Decomposing max-convolution of sum of functions ? Jackson 2011-09-19T05:45:00Z 2011-09-21T22:35:03Z <p>Hello.</p> <p>$R, F_1, F_2, F_3$ are random (not-convex, not-concave) 2D matrices of size 100x100. <br> $R$ is a linear combination of $F_1, F_2, F_3$. </p> <p>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$)</p> <p>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$):</p> <p>$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)$</p> <p>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}$. </p> <p>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$.</p> <p>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}$. <br></p> <p>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. </p> <p>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?</p>