|
I was wondering how to go about solving the following problem: min_x ||X^T X - Q||^2 subject to ||X||_1 = ||Q||_1 where X and Q are n x n matrices (Q is given, it's sparse and symmetric). As you can see, I'm basically trying to find a sparse approximation to the square root of the matrix Q. Are there any off-the-shelf solvers for these kinds of problems? |
|
Use the "approximate minimum degree ordering" and do a choleski. A much simpler answer than that of Alexandre, and probably much less optimal. Edit I just saw that your matrix wasn't PD, so I am not sure that my answer applies. That said, it seems strange to me to be looking for a square root of a non positive matrix. |
|
Assuming Q is symmetric positive definite and that you're minimizing the frobenius norm, your objective translates to sum_ij ( xi dot xj - q_ij )^2, which is convex as the square of a convex function is convex and the linear combination of convex functions is convex as well. This means you can get away with using CVX to optimize it if your matrix is not too big. As this optimization problem is not a QP, I don't think there will be more efficient solvers out there than standard convex optimizers. The problem is, Q is symmetric but not positive definite, and it is big (well somewhat, n is in tens of thousands).
(Mar 16 '12 at 09:17)
filox
I actually don't think Q has to be PD, as the function is still elementwise square even if it isn't. Tens of thousands should be ok for cvx.
(Mar 16 '12 at 09:20)
Alexandre Passos ♦
|
