Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Does anyone know any efficient method to solve the following problem?

$ (\alpha,\beta) = \text{argmax} \log \det (\alpha K_1 + \beta K_2)$

s.t. $c_1 \alpha + c_2 \beta = c_3, \alpha\geq0, \beta\geq 0$

where $K_1$ and $K_2$ are known positive semi-definite matrix and $c_1$, $c_2$ and $c_3$ are known constant.

Many thanks!

share|improve this question
    
How big will $K_1$ and $K_2$ approximately be? In case they are large: are they sparse or do they have some other additional structure besides being s.p.d.? –  Elmar Zander Feb 16 '13 at 12:26
    
@ElmarZander $K_1$ and $K_2$ are high-dimensional (about several hundreds), sparse and diagonally dominant matrices –  Hugo Feb 17 '13 at 7:55

2 Answers 2

I guess you can use below property:

The determinant behaves like a linear function on the rows of the matrix such as

$$ det(\alpha K + \beta L)=\begin{vmatrix} \alpha K_{1,1}+\beta L_{1,1}&\alpha K_{1,2}+\beta L_{1,2}\\\alpha K_{2,1}+\beta L_{2,1}&\alpha K_{2,1}+\beta L_{2,2}\end{vmatrix}$$

$$\Rightarrow \alpha^2\begin{vmatrix} K_{1,1}&K_{1,2}\\K_{2,1} & K_{2,1}\end{vmatrix}+\alpha \beta\begin{vmatrix} K_{1,1}&K_{1,2}\\L_{2,1} & L_{2,1}\end{vmatrix}+\alpha \beta\begin{vmatrix} L_{1,1}&L_{1,2}\\K_{2,1} & K_{2,1}\end{vmatrix}+\beta^2\begin{vmatrix} L_{1,1}&L_{1,2}\\L_{2,1} & L_{2,1}\end{vmatrix}$$

It may be easier to construct the matrices than taking inverses.

share|improve this answer

Here is a simple starting point, say if $K_1$ is (strictly) positive definite. Since $$\det(\alpha K_1 + \beta K_2) = \det(K_2) \det(\alpha K_2^{-1} K_1 + \beta I),$$ the problem is reduced to the case where one of the matrices is identity.

Now, let $K_2^{-1} K_1 = U \Lambda U^T$ be a spectral decomposition, where $\Lambda = \text{diag}(\lambda_1,\dots,\lambda_n)$. Then, the problem is $$ \max \sum_{i=1}^n \log(\alpha \lambda_i + \beta) $$ subject to constraints. Assuming that one of $c_1$ or $c_2$ is $>0$, say $c_1 > 0$, you can write $\alpha = c'_3 + c_2' \beta$ and turn the problem into a one dimensional problem on $\beta$.

If none of $K_1$ or $K_2$ is p.d., you might try adding a perturbation, say $K_2' = K_2 + \epsilon I$.

share|improve this answer
    
That's indeed a very good starting point. However, $K_1$, $K_2$ here are large matrix, thus it's costly to compute the inverse. Sorry for the confusion. –  Hugo Feb 17 '13 at 6:09
    
You don't need to compute the inverse. You only need to solve the generalized eigenvalue problem $K_1 v = \lambda K_2 v$. It might be possible to do this faster (not sure.) –  passerby51 Feb 17 '13 at 12:19
    
True, but computing the spectral decomposition isn't cheap either, if $K_1$ and $K_2$ are large. –  Elmar Zander Feb 18 '13 at 13:44

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.