User jackson - MathOverflow

How do I optimize over this individually convex but not-jointly convex problem?

2011-10-01T11:52:50Z

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?

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$).

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.

For dimensions,

$P_i$ are $k$ by $k$,
$X,Y$ are $k$ by $J$ where $J >> k$,
$\mathbf{\alpha}_i$ are $J$ by $1$
$\mathbf{e}_i$ are unit vectors $J$ by $1$

$$ \min_{X,Y} ~ \sum_{i=1}^n || P_i - X \mathbf{diag}( \boldsymbol{\alpha}_i ) Y^T ||_F $$

$$\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} $$

Or equivalently,

$$ \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 $$

$$ \text{s.t.} ~~ ||\mathbf{vec} (\mathbf{x}_j \mathbf{y}_j^T )||_2^2 \leq 1 ~~~ \forall j = {1, ..., J} $$

When I write the Lagrangian and take derivative w.r.t. $X$, I get the following but I'm stuck

$$\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?

Decomposing max-convolution of sum of functions ?

2011-09-19T05:45:00Z

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$):

$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?

How do I optimize over (or take derivative wrt) a square diagonal matrix?

2011-09-09T23:24:46Z

Hello. I'd like to solve the following optimization problem.

$P_i$ is a 6x6 matrix
$X$, $Y$ is a 6xk matrix
$w_i$ is a kx1 vector
$diag(w_i)$ is a square diagonal matrix with diagonal entries equal to $w_i$

$\min_{w_i} ~ ||P_i - X diag(w_i) Y^T||_F^2$

So the question is how to optimize over $diag(w_i)$.

Does anyone know how to take derivative wrt a diagonal matrix?

Or would it work if treat $diag(w_i)$ as a square matrix, solve it,
and then set off-diagonal entries to zeros?

Comment by Jackson

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?

Comment by Jackson

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 "HOW" to solve the subproblems.

Comment by Jackson

2011-10-03T07:18:07Z

I'm sorry but this is not helpful at all

Comment by Jackson

2011-10-01T16:26:40Z

How would I find an update formula for X and Y to find such a local optimum?

Comment by Jackson

2011-09-19T08:50:04Z

$x,y$ range from 1 to matrix height and width. $x+dx, y+dy$ also have the same support.

Comment by Jackson

2011-09-19T06:42:47Z

Edited what $x,y,dx,dy$ are

Comment by Jackson

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.