User jackson - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-24T07:29:55Z http://mathoverflow.net/feeds/user/17707 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/76917/how-do-i-optimize-over-this-individually-convex-but-not-jointly-convex-problem How do I optimize over this individually convex but not-jointly convex problem? Jackson 2011-10-01T11:52:50Z 2011-10-02T04:48:33Z <p>I have the following optimization problem where I know how to optimize w.r.t $\alpha_i$ but want to derive an update rule or an equation to optimize over $X$ and $Y$. Does anyone have an idea on how to approach this? <br></p> <p>I've tried deriving a Lagrangian dual but couldn't proceed after taking derivative wrt $X$ and the same for $Y$ because equation for optimal $X$ has $Y$ in it and vice versa. Hence, it's not easy to get a Lagrangian dual (only in terms of the dual variable corresponding to the constraint and knowns $P_i$, $\mathbf{\alpha}_i$).</p> <p>The update equation doesn't have to use Lagrangian dual. It could be possible to massage this problem into a known problem using linear algebra tricks.</p> <p>For dimensions, </p> <p>$P_i$ are $k$ by $k$, <br> $X,Y$ are $k$ by $J$ where $J >> k$, <br> $\mathbf{\alpha}_i$ are $J$ by $1$ <br> $\mathbf{e}_i$ are unit vectors $J$ by $1$ <br></p> <p>$$\min_{X,Y} ~ \sum_{i=1}^n || P_i - X \mathbf{diag}( \boldsymbol{\alpha}_i ) Y^T ||_F$$</p> <p>$$\text{s.t.} ~~ ||X \Lambda_j Y^T||_F^2 ~ \leq 1 ~~~~ \text{where } \Lambda_j=\mathbf{diag}(\mathbf{e}_j) ~~~~ \forall j = {1, ..., J}$$ </p> <p>Or equivalently, </p> <p>$$\min_{X,Y} ~ \sum_{i=1}^{n} || \mathbf{vec}(P_i) - [ \mathbf{vec}(\mathbf{x}_1 \mathbf{y}_1^T) , ... , \mathbf{vec}(\mathbf{x}_J \mathbf{y}_J^T) ] \boldsymbol{\alpha}_i ||_2^2$$</p> <p>$$\text{s.t.} ~~ ||\mathbf{vec} (\mathbf{x}_j \mathbf{y}_j^T )||_2^2 \leq 1 ~~~ \forall j = {1, ..., J}$$</p> <p><br> <br></p> <p>When I write the Lagrangian and take derivative w.r.t. $X$, I get the following but I'm stuck</p> <p>$$\sum_{i=1}^n P_i \tilde Y_i^T = X \left( \sum_{i=1}^n \tilde Y_i \tilde Y_i^T + \sum_{j=1}^J \lambda_j \hat Y_j \hat Y_j^T \right)$$ $\text{where} ~ \tilde Y_i = \mathbf{diag}(\mathbf{\alpha}_i) Y^T$ and $\hat Y_j = \Lambda_j Y^T$ Lagrangian might not be the way to go about this. Does anyone have a suggestion?</p> 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> http://mathoverflow.net/questions/75051/how-do-i-optimize-over-or-take-derivative-wrt-a-square-diagonal-matrix How do I optimize over (or take derivative wrt) a square diagonal matrix? Jackson 2011-09-09T23:24:46Z 2011-09-10T04:36:44Z <p>Hello. I'd like to solve the following optimization problem.</p> <p>$P_i$ is a 6x6 matrix<br> $X$, $Y$ is a 6xk matrix<br> $w_i$ is a kx1 vector<br> $diag(w_i)$ is a square diagonal matrix with diagonal entries equal to $w_i$</p> <p>$\min_{w_i} ~ ||P_i - X diag(w_i) Y^T||_F^2$</p> <p>So the question is how to optimize over $diag(w_i)$.</p> <p>Does anyone know how to take derivative wrt a diagonal matrix?</p> <p>Or would it work if treat $diag(w_i)$ as a square matrix, solve it,<br> and then set off-diagonal entries to zeros?</p> http://mathoverflow.net/questions/76917/how-do-i-optimize-over-this-individually-convex-but-not-jointly-convex-problem/76922#76922 Comment by Jackson Jackson 2011-10-04T21:41:19Z 2011-10-04T21:41:19Z You haven't shown anything useful in answering the original question. Solving the subproblems is not as trivial as solving a homework question. If you don't know how to derive the update rule, why don't you acknowledge it and not pretend like you know the answer? http://mathoverflow.net/questions/76917/how-do-i-optimize-over-this-individually-convex-but-not-jointly-convex-problem/76922#76922 Comment by Jackson Jackson 2011-10-03T22:52:58Z 2011-10-03T22:52:58Z Your answer is not any useful because you failed to provide (either iterative or closed-form) update rule for X and Y. Obviously, I'm interested in &quot;HOW&quot; to solve the subproblems. http://mathoverflow.net/questions/76917/how-do-i-optimize-over-this-individually-convex-but-not-jointly-convex-problem/76922#76922 Comment by Jackson Jackson 2011-10-03T07:18:07Z 2011-10-03T07:18:07Z I'm sorry but this is not helpful at all http://mathoverflow.net/questions/76917/how-do-i-optimize-over-this-individually-convex-but-not-jointly-convex-problem/76922#76922 Comment by Jackson Jackson 2011-10-01T16:26:40Z 2011-10-01T16:26:40Z How would I find an update formula for X and Y to find such a local optimum? http://mathoverflow.net/questions/75820/decomposing-max-convolution-of-sum-of-functions Comment by Jackson Jackson 2011-09-19T08:50:04Z 2011-09-19T08:50:04Z $x,y$ range from 1 to matrix height and width. $x+dx, y+dy$ also have the same support. http://mathoverflow.net/questions/75820/decomposing-max-convolution-of-sum-of-functions Comment by Jackson Jackson 2011-09-19T06:42:47Z 2011-09-19T06:42:47Z Edited what $x,y,dx,dy$ are http://mathoverflow.net/questions/75051/how-do-i-optimize-over-or-take-derivative-wrt-a-square-diagonal-matrix/75066#75066 Comment by Jackson Jackson 2011-09-10T08:29:47Z 2011-09-10T08:29:47Z Wow I admire your intuition. At the moment I asked the question I had no idea how to approached the problem but now it turns out to be one of the easiest problems in Linear Algebra. Thank you very much.