Timeline for Block Covariance Matrix - Positive Definite? (Quadratic Optimization)
Current License: CC BY-SA 3.0
15 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 9, 2014 at 11:37 | comment | added | akuz | @FedericoPoloni thank you! I will try to do change of basis for the entire problem. | |
| Mar 8, 2014 at 18:00 | comment | added | Federico Poloni | @akuz To understand what happens after diagonalization, think about the "test problem" $\min_{x,y} ax+by+dx^2$, that you get for $m=[a;b]$, $M=\begin{bmatrix}d & 0\\ 0 & 0\end{bmatrix}$. If $b\neq 0$, then the problem was ill-posed to start with and has no minimum. If $b=0$, then you can remove $y$. | |
| Mar 8, 2014 at 17:49 | comment | added | Suvrit | @akuz: to avoid worrying about this loss of strict positivity, try solving $\min m^Tx + (1/2)x^T(M + \epsilon I)x$, where $\epsilon$ is tiny. This will mean, $[C+\epsilon I, C; C, C+\epsilon I]$ for you. | |
| Mar 8, 2014 at 17:05 | comment | added | akuz | @FedericoPoloni but won't it change the solution of the optimization problem? | |
| Mar 8, 2014 at 14:20 | comment | added | Federico Poloni | Change basis everywhere to make a row and a column of zeros in $M$, then remove said row/column from everything. | |
| Mar 8, 2014 at 13:47 | comment | added | akuz | Let's say I have a problem $min\, m^T x + 0.5 x^T M x$ - how would you reformulate it fir a deflated matrix M'? | |
| Mar 8, 2014 at 13:07 | vote | accept | akuz | ||
| Mar 8, 2014 at 13:07 | comment | added | akuz | @FedericoPoloni you are right - numerical error is detected as small negative eigenvalues within the optimization package... I will check if there is a way to set a larger tolerance. But if not, how would I deflate the problem? I know how I could deflate the matrix, for example by doing SVD, but then I would need to translate my optimization problem in that space... Hopefully I can just increase the tolerance or error | |
| Mar 8, 2014 at 9:21 | comment | added | Federico Poloni | It's semidefinite, so it means there is an eigenvalue which is exactly zero. If your optimization routine computes a matrix factorization, it might be the case that numerical errors perturb an eigenvalue to $-10^{-16}$ or the like. It would be best if you reformulated the problem deflating manually out the zero subspace (which you can compute explicitly). | |
| Mar 8, 2014 at 2:40 | comment | added | akuz | Thanks @Suvrit a lot for your answer. I will check the details, sorry I'm not too familiar with this subject. All I'm saying is that when I specify [ C C; C C ] matrix in my optimization routine (joptimizer), it complains it's not positive (semi-)definite. That might be a bug in their code too... | |
| Mar 7, 2014 at 21:39 | history | edited | Suvrit | CC BY-SA 3.0 |
added alternative proof...
|
| Mar 7, 2014 at 20:42 | comment | added | Suvrit | @akuz: my answer addresses what you wrote in the question. I just proved the said matrix to be semidefinite but given your comment it seems that you are not convinced :-) please read the wikipedia page on Kronecker products to feel more convinced :-) | |
| Mar 7, 2014 at 19:41 | comment | added | akuz | please see above comment. also, here it seems like there are additional conditions: math.stackexchange.com/questions/391852/… | |
| Mar 7, 2014 at 19:27 | comment | added | akuz | Strange, then why is my optimization package complaining it's not either positive definite, nor positive semi-definite? Are you sure? (Sorry for this lame question!) | |
| Mar 7, 2014 at 19:24 | history | answered | Suvrit | CC BY-SA 3.0 |